Opened 7 years ago

Closed 7 years ago

#8702 closed enhancement (fixed)

Datastructure for objects with prototype (clone) design pattern.

Reported by: hivert Owned by: hivert
Priority: major Milestone: sage-4.6.2
Component: combinatorics Keywords:
Cc: novoselt, mhansen, sage-combinat Merged in: sage-4.6.2.alpha0
Authors: Florent Hivert Reviewers: Mike Hansen
Report Upstream: N/A Work issues:
Branch: Commit:
Dependencies: Stopgaps:

Description (last modified by hivert)

The idea is inspired from the "prototype" design pattern (see [Pro], [GOF]).

I want to define subclasses of Element with the following behavior: Those classes are intended to be used to model *mathematical* objects, which are by essence immutable. However, in many occasions, one wants to construct the data-structure encoding of a new mathematical object by small modifications of the data structure encoding some already built object. This is a very common stuff for example in matrices: For example: given a matrix M we want to replace every non_zero position by 1

            res = copy(M)
            for pos in res._nonzero_positions_by_row():
                res[pos] = 1
            res.set_immutable()

However in many cases, for the resulting data-structure to correctly encode the mathematical object, some structural invariants must hold (say for example we want that the matrix is symmetric). One problem is that, in many cases, during the modification process, there is no possibility but to break the invariants. Here there is no way to keep the matrix symmetric during the replacement by 1...

A typical example in combinatorics, in a list modeling a permutation of {1,...,n}, the integers must be distinct. A very common operation is to take a permutation to make a copy with some small modifications, like exchanging two consecutive values in the list or cycling some values. Though the result is clearly a permutations there's no way to avoid breaking the permutations invariants at some point during the modifications.

So the idea is the following: to allows local breaking of invariant on a locally mutable copy and to check that things are restored in a proper state at the end. So I wrote a small class called ClonableElement and several derived subclasses (clone is the standard name for the copy method in the "prototype" design pattern):

A class C inheriting from ClonableElement? must implement the following two methods

    - obj.__copy__() -- returns a fresh copy of obj
    - obj.check() -- returns nothing, raise an exception if obj
      doesn't satisfies the data structure invariants

Then, given an instance obj of C, the following sequences of instructions ensures that the invariants of new_obj are properly restored at the end

       with obj.clone() as new_obj:
           ...
           # lot of invariant breaking modifications on new_obj
           ...
       # invariants are ensured to be fulfilled

The following equivalent sequence of instructions can be used if speed is needed, in particular in Cython code (unfortunately, the handling of the with instruction make some overhead)...

       new_obj = obj.__copy__()
       ...
       # lot of invariant breaking modifications on new_obj
       ...
       new_obj.set_immutable()
       new_obj.check()
       # invariants are ensured to be fulfilled

I also took to chance to handle hashing...

This is the future Cython replacement for CombinatorialObject.

[Pro] Prototype pattern http://en.wikipedia.org/wiki/Prototype_pattern

[GOF] Design Patterns: Elements of Reusable Object-Oriented Software. E. Gamma; R. Helm; R. Johnson; J. Vlissides (1994). Addison-Wesley. ISBN 0-201-63361-2.

Attachments (3)

diff-8702 (6.1 KB) - added by hivert 7 years ago.
trac_8702-list_clone-fh.2.patch (69.9 KB) - added by hivert 7 years ago.
trac_8702-list_clone-fh.patch (71.3 KB) - added by hivert 7 years ago.

Download all attachments as: .zip

Change History (17)

comment:1 Changed 7 years ago by hivert

  • Status changed from new to needs_review

comment:2 Changed 7 years ago by novoselt

  • Cc novoselt added
  • Milestone set to sage-4.4.4
  • Type changed from defect to enhancement

comment:3 Changed 7 years ago by hivert

  • Description modified (diff)

comment:4 follow-up: Changed 7 years ago by hivert

  • Cc mhansen added
  • Reviewers set to Mike Hansen

Hi mike,

I adressed your comment:

  1. Is there a good use case for allowing None to be passed in to

ClonableArray?, ClonableList?, and ConableIntArray?. There is a bit of mental overhead in always having to remember to check that self._list is always an actual list.

and updated a new patch... Please review.

comment:5 in reply to: ↑ 4 Changed 7 years ago by hivert

and updated a new patch... Please review.

Sorry: I should have said that I also folded your review patch... Thanks for it.

comment:6 follow-up: Changed 7 years ago by mhansen

  • Status changed from needs_review to positive_review

Looks good to me.

comment:7 in reply to: ↑ 6 Changed 7 years ago by hivert

Replying to mhansen:

Looks good to me.

Thanks for the review !

comment:8 follow-up: Changed 7 years ago by jdemeyer

  • Status changed from positive_review to needs_work

I get doctest errors:

**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.6.1.alpha1/devel/sage-main/sage/structure/list_clone_timings.py", line 8:
    sage: from sage.structure.list_clone_timmings import *
Exception raised:
    Traceback (most recent call last):
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.6.1.alpha1/local/bin/ncadoctest.py", line 1231, in run_one_test
        self.run_one_example(test, example, filename, compileflags)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.6.1.alpha1/local/bin/sagedoctest.py", line 38, in run_one_example
        OrigDocTestRunner.run_one_example(self, test, example, filename, compileflags)
      File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.6.1.alpha1/local/bin/ncadoctest.py", line 1172, in run_one_example
        compileflags, 1) in test.globs
      File "<doctest __main__.example_0[2]>", line 1, in <module>
        from sage.structure.list_clone_timmings import *###line 8:
    sage: from sage.structure.list_clone_timmings import *
    ImportError: No module named list_clone_timmings
**********************************************************************

Changed 7 years ago by hivert

comment:9 in reply to: ↑ 8 Changed 7 years ago by hivert

  • Status changed from needs_work to needs_review

Replying to jdemeyer:

I get doctest errors:

**********************************************************************
File "/mnt/usb1/scratch/jdemeyer/merger/sage-4.6.1.alpha1/devel/sage-main/sage/structure/list_clone_timings.py", line 8:
    sage: from sage.structure.list_clone_timmings import *
[...]

Oups ! I forgot to fold some corrective patches. I just resubmitted the corrected version. To ease the review I also uploaded the diff between the older version and the new one. Do not apply this chunk of code.

Only apply trac_8702-list_clone-fh.patch

Changed 7 years ago by hivert

comment:10 Changed 7 years ago by hivert

Added a missing utf8 tag on the file list_clone_timings.py...

Apply only trac_8702-list_clone-fh.2.patch

Changed 7 years ago by hivert

comment:11 Changed 7 years ago by hivert

Oops ! I forgot to add Copyright notices... Sorry for the mess.

Apply only trac_8702-list_clone-fh.patch

comment:12 Changed 7 years ago by nthiery

  • Cc sage-combinat added
  • Status changed from needs_review to positive_review

comment:13 Changed 7 years ago by jdemeyer

  • Milestone changed from sage-4.6.1 to sage-4.6.2

comment:14 Changed 7 years ago by jdemeyer

  • Merged in set to sage-4.6.2.alpha0
  • Resolution set to fixed
  • Status changed from positive_review to closed
Note: See TracTickets for help on using tickets.