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 , 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:
The following parents 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 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):
...
AssertionError: 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):
...
AssertionError: 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.
Check that self fulfill the invariants
This is an abstract method. Subclasses are supposed to overload check.
EXAMPLES:
sage: ClonableArray(Parent(), [1,2,3]) # indirect doctest
Traceback (most recent call last):
...
AssertionError: This should never be called, please overload
sage: from sage.structure.list_clone 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 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 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 subclasse 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
such that
:
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):
... assert self._x < self._y, "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 at the end is
illegal and raise an exception:
sage: with el.clone() as elc2:
... elc2.set_x(5)
Traceback (most recent call last):
...
AssertionError: Incorrectly ordered pair
Returns a clone that is mutable copy of self.
INPUT:
EXAMPLES:
sage: from sage.structure.list_clone 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 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 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 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.
Check that self fulfill the invariants
This is an abstract method. Subclasses are supposed to overload check.
EXAMPLES:
sage: ClonableArray(Parent(), [1,2,3]) # indirect doctest
Traceback (most recent call last):
...
AssertionError: This should never be called, please overload
sage: from sage.structure.list_clone import IncreasingIntArrays
sage: el = IncreasingIntArrays()([1,2,4]) # indirect doctest
EXAMPLES:
sage: from sage.structure.list_clone 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 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.
Appends el to self
INPUT: el – any object
EXAMPLES:
sage: from sage.structure.list_clone 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):
...
AssertionError: array is not increasing
Extends self by the content of the iterable it
INPUT: it – any iterable
EXAMPLES:
sage: from sage.structure.list_clone 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):
...
AssertionError: 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 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):
...
AssertionError: 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 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 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.ClonableArray
A small extension class for testing ClonableArray.
TESTS:
sage: from sage.structure.list_clone import IncreasingArrays
sage: TestSuite(IncreasingArrays()([1,2,3])).run()
sage: TestSuite(IncreasingArrays()([])).run()
Check that self is increasing.
EXAMPLES:
sage: from sage.structure.list_clone import IncreasingArrays
sage: IncreasingArrays()([1,2,3]) # indirect doctest
[1, 2, 3]
sage: IncreasingArrays()([3,2,1]) # indirect doctest
Traceback (most recent call last):
...
AssertionError: array is not increasing
Bases: sage.structure.unique_representation.UniqueRepresentation, sage.structure.parent.Parent
A small (incomplete) parent for testing ClonableArray
TESTS:
sage: from sage.structure.list_clone import IncreasingArrays
sage: IncreasingArrays().element_class
<type 'sage.structure.list_clone.IncreasingArray'>
alias of IncreasingArray
Bases: sage.structure.list_clone.ClonableIntArray
A small extension class for testing ClonableIntArray.
TESTS:
sage: from sage.structure.list_clone import IncreasingIntArrays
sage: TestSuite(IncreasingIntArrays()([1,2,3])).run()
sage: TestSuite(IncreasingIntArrays()([])).run()
Check that self is increasing.
EXAMPLES:
sage: from sage.structure.list_clone import IncreasingIntArrays
sage: IncreasingIntArrays()([1,2,3]) # indirect doctest
[1, 2, 3]
sage: IncreasingIntArrays()([3,2,1]) # indirect doctest
Traceback (most recent call last):
...
AssertionError: array is not increasing
Bases: sage.structure.list_clone.IncreasingArrays
A small (incomplete) parent for testing ClonableIntArray
TESTS:
sage: from sage.structure.list_clone import IncreasingIntArrays
sage: IncreasingIntArrays().element_class
<type 'sage.structure.list_clone.IncreasingIntArray'>
alias of IncreasingIntArray
Bases: sage.structure.list_clone.ClonableList
A small extension class for testing ClonableList
TESTS:
sage: from sage.structure.list_clone import IncreasingLists
sage: TestSuite(IncreasingLists()([1,2,3])).run()
sage: TestSuite(IncreasingLists()([])).run()
Check that self is increasing
EXAMPLES:
sage: from sage.structure.list_clone import IncreasingLists
sage: IncreasingLists()([1,2,3]) # indirect doctest
[1, 2, 3]
sage: IncreasingLists()([3,2,1]) # indirect doctest
Traceback (most recent call last):
...
AssertionError: array is not increasing
Bases: sage.structure.list_clone.IncreasingArrays
A small (incomplete) parent for testing ClonableArray
TESTS:
sage: from sage.structure.list_clone import IncreasingLists
sage: IncreasingLists().element_class
<type 'sage.structure.list_clone.IncreasingList'>
alias of IncreasingList