Elements, Array and Lists With Clone Protocol
This module defines several classes which are subclasses of Element and which roughly implement the “prototype” design pattern (see [Pro], [GOF]). 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. For the resulting data-structure to correctly encode the mathematical object, some structural invariants must hold. One problem is that, in many cases, during the modification process, there is no possibility but to break the invariants.
For example, in a list modeling a permutation of \(\{1,\dots,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.
The main purpose of this module is to define the class
and its subclasses:
See also
The following parents from sage.structure.list_clone_demo demonstrate how to use them:
EXAMPLES:
We now demonstrate how IncreasingArray works, creating an instance el through its parent IncreasingArrays():
sage: from sage.structure.list_clone_demo import IncreasingArrays
sage: P = IncreasingArrays()
sage: P([1, 4 ,8])
[1, 4, 8]
If one tries to create this way a list which in not increasing, an error is raised:
sage: IncreasingArrays()([5, 4 ,8])
Traceback (most recent call last):
...
ValueError: array is not increasing
Once created modifying el is forbidden:
sage: el = P([1, 4 ,8])
sage: el[1] = 3
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
However, you can modify a temporarily mutable clone:
sage: with el.clone() as elc:
....: elc[1] = 3
sage: [el, elc]
[[1, 4, 8], [1, 3, 8]]
We check that the original and the modified copy now are in a proper immutable state:
sage: el.is_immutable(), elc.is_immutable()
(True, True)
sage: elc[1] = 5
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
You can break the property that the list is increasing during the modification:
sage: with el.clone() as elc2:
....: elc2[1] = 12
....: print elc2
....: elc2[2] = 25
[1, 12, 8]
sage: elc2
[1, 12, 25]
But this property must be restored at the end of the with block; otherwise an error is raised:
sage: with elc2.clone() as el3:
....: el3[1] = 100
Traceback (most recent call last):
...
ValueError: array is not increasing
Finally, as an alternative to the with syntax one can use:
sage: el4 = copy(elc2)
sage: el4[1] = 10
sage: el4.set_immutable()
sage: el4.check()
REFERENCES:
[Pro] (1, 2) Prototype pattern http://en.wikipedia.org/wiki/Prototype_pattern
[GOF] (1, 2) Design Patterns: Elements of Reusable Object-Oriented Software. E. Gamma; R. Helm; R. Johnson; J. Vlissides (1994). Addison-Wesley. ISBN 0-201-63361-2.
AUTHORS:
Bases: sage.structure.list_clone.ClonableElement
Array with clone protocol
The class of objects which are Element behave as arrays (i.e. lists of fixed length) and implement the clone protocol. See ClonableElement for details about clone protocol.
INPUT:
See also
IncreasingArray for an example of usage.
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingArrays
sage: IA = IncreasingArrays()
sage: ia1 = IA([1, 4, 6]); ia1
[1, 4, 6]
sage: with ia1.clone() as ia2:
....: ia2[1] = 5
sage: ia2
[1, 5, 6]
sage: with ia1.clone() as ia2:
....: ia2[1] = 7
Traceback (most recent call last):
...
ValueError: array is not increasing
Check that self fulfill the invariants
This is an abstract method. Subclasses are supposed to overload check.
EXAMPLES:
sage: from sage.structure.list_clone import ClonableArray
sage: ClonableArray(Parent(), [1,2,3]) # indirect doctest
Traceback (most recent call last):
...
NotImplementedError: this should never be called, please overload the check method
sage: from sage.structure.list_clone_demo import IncreasingArrays
sage: el = IncreasingArrays()([1,2,4]) # indirect doctest
Returns number of i‘s for which s[i] == key
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingArrays
sage: c = IncreasingArrays()([1,2,2,4])
sage: c.count(1)
1
sage: c.count(2)
2
sage: c.count(3)
0
Returns the smallest k such that s[k] == x and i <= k < j
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingArrays
sage: c = IncreasingArrays()([1,2,4])
sage: c.index(1)
0
sage: c.index(4)
2
sage: c.index(5)
Traceback (most recent call last):
...
ValueError: 5 is not in list
Bases: sage.structure.element.Element
Abstract class for elements with clone protocol
This class is a subclass of Element and implements the “prototype” design pattern (see [Pro], [GOF]). The role of this class is:
A class C inheriting from ClonableElement must implement the following two methods
and ensure to call obj._require_mutable() at the beginning of any modifying method.
Additionally, one can also implement
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:
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
Finally, if the class implements the _hash_ method, then ClonableElement ensures that the hash value can only be computed on an immutable object. It furthermore caches it so that it is only computed once.
Warning
for the hash caching mechanism to work correctly, the hash value cannot be 0.
EXAMPLES:
The following code shows a minimal example of usage of ClonableElement. We implement a class or pairs \((x,y)\) such that \(x < y\):
sage: from sage.structure.list_clone import ClonableElement
sage: class IntPair(ClonableElement):
....: def __init__(self, parent, x, y):
....: ClonableElement.__init__(self, parent=parent)
....: self._x = x
....: self._y = y
....: self.set_immutable()
....: self.check()
....: def _repr_(self):
....: return "(x=%s, y=%s)"%(self._x, self._y)
....: def check(self):
....: if self._x >= self._y:
....: raise ValueError, "Incorrectly ordered pair"
....: def get_x(self): return self._x
....: def get_y(self): return self._y
....: def set_x(self, v): self._require_mutable(); self._x = v
....: def set_y(self, v): self._require_mutable(); self._y = v
Note
we don’t need to define __copy__ since it is properly inherited from Element.
We now demonstrate the behavior. Let’s create an IntPair:
sage: myParent = Parent()
sage: el = IntPair(myParent, 1, 3); el
(x=1, y=3)
sage: el.get_x()
1
Modifying it is forbidden:
sage: el.set_x(4)
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
However, you can modify a mutable copy:
sage: with el.clone() as el1:
....: el1.set_x(2)
sage: [el, el1]
[(x=1, y=3), (x=2, y=3)]
We check that the original and the modified copy are in a proper immutable state:
sage: el.is_immutable(), el1.is_immutable()
(True, True)
sage: el1.set_x(4)
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
A modification which doesn’t restore the invariant \(x < y\) at the end is illegal and raise an exception:
sage: with el.clone() as elc2:
....: elc2.set_x(5)
Traceback (most recent call last):
...
ValueError: Incorrectly ordered pair
Returns a clone that is mutable copy of self.
INPUT:
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingArrays
sage: el = IncreasingArrays()([1,2,3])
sage: with el.clone() as el1:
....: el1[2] = 5
sage: el1
[1, 2, 5]
Returns True if self is immutable (can not be changed) and False if it is not.
To make self immutable use self.set_immutable().
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingArrays
sage: el = IncreasingArrays()([1,2,3])
sage: el.is_immutable()
True
sage: copy(el).is_immutable()
False
sage: with el.clone() as el1:
....: print [el.is_immutable(), el1.is_immutable()]
[True, False]
Returns True if self is mutable (can be changed) and False if it is not.
To make this object immutable use self.set_immutable().
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingArrays
sage: el = IncreasingArrays()([1,2,3])
sage: el.is_mutable()
False
sage: copy(el).is_mutable()
True
sage: with el.clone() as el1:
....: print [el.is_mutable(), el1.is_mutable()]
[False, True]
Makes self immutable, so it can never again be changed.
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingArrays
sage: el = IncreasingArrays()([1,2,3])
sage: el1 = copy(el); el1.is_mutable()
True
sage: el1.set_immutable(); el1.is_mutable()
False
sage: el1[2] = 4
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
Bases: sage.structure.list_clone.ClonableElement
Array of int with clone protocol
The class of objects which are Element behave as list of int and implement the clone protocol. See ClonableElement for details about clone protocol.
INPUT:
See also
IncreasingIntArray for an example of usage.
Check that self fulfill the invariants
This is an abstract method. Subclasses are supposed to overload check.
EXAMPLES:
sage: from sage.structure.list_clone import ClonableArray
sage: ClonableArray(Parent(), [1,2,3]) # indirect doctest
Traceback (most recent call last):
...
NotImplementedError: this should never be called, please overload the check method
sage: from sage.structure.list_clone_demo import IncreasingIntArrays
sage: el = IncreasingIntArrays()([1,2,4]) # indirect doctest
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingIntArrays
sage: c = IncreasingIntArrays()([1,2,4])
sage: c.index(1)
0
sage: c.index(4)
2
sage: c.index(5)
Traceback (most recent call last):
...
ValueError: list.index(x): x not in list
Convert self into a Python list.
EXAMPLE:
sage: from sage.structure.list_clone_demo import IncreasingIntArrays
sage: I = IncreasingIntArrays()(range(5))
sage: I == range(5)
False
sage: I.list() == range(5)
True
sage: I = IncreasingIntArrays()(range(1000))
sage: I.list() == range(1000)
True
Bases: sage.structure.list_clone.ClonableArray
List with clone protocol
The class of objects which are Element behave as lists and implement the clone protocol. See ClonableElement for details about clone protocol.
See also
IncreasingList for an example of usage.
Appends el to self
INPUT: el – any object
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingLists
sage: el = IncreasingLists()([1])
sage: el.append(3)
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
sage: with el.clone() as elc:
....: elc.append(4)
....: elc.append(6)
sage: elc
[1, 4, 6]
sage: with el.clone() as elc:
....: elc.append(4)
....: elc.append(2)
Traceback (most recent call last):
...
ValueError: array is not increasing
Extends self by the content of the iterable it
INPUT: it – any iterable
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingLists
sage: el = IncreasingLists()([1, 4, 5, 8, 9])
sage: el.extend((10,11))
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
sage: with el.clone() as elc:
....: elc.extend((10,11))
sage: elc
[1, 4, 5, 8, 9, 10, 11]
sage: el2 = IncreasingLists()([15, 16])
sage: with el.clone() as elc:
....: elc.extend(el2)
sage: elc
[1, 4, 5, 8, 9, 15, 16]
sage: with el.clone() as elc:
....: elc.extend((6,7))
Traceback (most recent call last):
...
ValueError: array is not increasing
Inserts el in self at position index
INPUT:
- el – any object
- index – any int
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingLists
sage: el = IncreasingLists()([1, 4, 5, 8, 9])
sage: el.insert(3, 6)
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
sage: with el.clone() as elc:
....: elc.insert(3, 6)
sage: elc
[1, 4, 5, 6, 8, 9]
sage: with el.clone() as elc:
....: elc.insert(2, 6)
Traceback (most recent call last):
...
ValueError: array is not increasing
Remove self[index] from self and returns it
INPUT: index - any int, default to -1
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingLists
sage: el = IncreasingLists()([1, 4, 5, 8, 9])
sage: el.pop()
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
sage: with el.clone() as elc:
....: print elc.pop()
9
sage: elc
[1, 4, 5, 8]
sage: with el.clone() as elc:
....: print elc.pop(2)
5
sage: elc
[1, 4, 8, 9]
Remove the first occurence of el from self
INPUT: el - any object
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingLists
sage: el = IncreasingLists()([1, 4, 5, 8, 9])
sage: el.remove(4)
Traceback (most recent call last):
...
ValueError: object is immutable; please change a copy instead.
sage: with el.clone() as elc:
....: elc.remove(4)
sage: elc
[1, 5, 8, 9]
sage: with el.clone() as elc:
....: elc.remove(10)
Traceback (most recent call last):
...
ValueError: list.remove(x): x not in list
Bases: sage.structure.list_clone.ClonableList
List with clone protocol and normal form
This is a subclass of ClonableList which call a method normalize() at creation and after any modification of its instance.
See also
SortedList for an example of usage.
EXAMPLES:
We construct a sorted list through its parent:
sage: from sage.structure.list_clone_demo import SortedLists
sage: SL = SortedLists()
sage: sl1 = SL([4,2,6,1]); sl1
[1, 2, 4, 6]
Normalization is also performed atfer modification:
sage: with sl1.clone() as sl2:
....: sl2[1] = 12
sage: sl2
[1, 4, 6, 12]
Normalize self
This is an abstract method. Subclasses are supposed to overload normalize(). The call self.normalize() is supposed to
EXAMPLES:
sage: from sage.structure.list_clone_demo import SortedList, SortedLists
sage: l = SortedList(SortedLists(), [2,3,2], False, False)
sage: l
[2, 2, 3]
sage: l.check()
Traceback (most recent call last):
...
ValueError: list is not strictly increasing