#8702: Datastructure for objects with prototype (clone) design pattern.
------------------------------+---------------------------------------------
Reporter: hivert | Owner: hivert
Type: enhancement | Status: needs_review
Priority: major | Milestone: sage-4.4.4
Component: combinatorics | Keywords:
Author: Florent Hivert | Upstream: N/A
Reviewer: | Merged:
Work_issues: |
------------------------------+---------------------------------------------
Description changed by hivert:
Old description:
> This is the future Cython replacement for CombinatorialObject.
>
> Patch in preparation in sage-combinat queue
New description:
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.
--
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/8702#comment:3>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
