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 [Prototype_pattern], [GHJV1994]). 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
ClonableElement
as an abstract super class,
and its subclasses:
ClonableArray
for arrays (lists of fixed length) of objects;ClonableList
for (resizable) lists of objects;NormalizedClonableList
for lists of objects with a normalization method;ClonableIntArray
for arrays of int.
See also
The following parents from sage.structure.list_clone_demo
demonstrate how to use them:
IncreasingArrays()
(seeIncreasingArray
and the parent classIncreasingArrays
)IncreasingLists()
(seeIncreasingList
and the parent classIncreasingLists
)SortedLists()
(seeSortedList
and the parent classSortedLists
)IncreasingIntArrays()
(seeIncreasingIntArray
and the parent classIncreasingIntArrays
)
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:
AUTHORS:
Florent Hivert (2010-03): initial revision
- class sage.structure.list_clone.ClonableArray#
Bases:
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. SeeClonableElement
for details about clone protocol.INPUT:
parent
– aParent
lst
– a listcheck
– a boolean specifying if the invariant must be checked using methodcheck()
.immutable
– a boolean telling whether the created element is immutable (defaults toTrue
)
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()#
Check that
self
fulfill the invariantsThis 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
- count(key)#
Return number of
i
’s for whichs[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
- index(x, start=None, stop=None)#
Return the smallest
k
such thats[k] == x
andi <= 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
- class sage.structure.list_clone.ClonableElement#
Bases:
Element
Abstract class for elements with clone protocol
This class is a subclass of
Element
and implements the “prototype” design pattern (see [Prototype_pattern], [GHJV1994]). The role of this class is:to manage copy and mutability and hashing of elements
to ensure that at the end of a piece of code an object is restored in a meaningful mathematical state.
A class
C
inheriting fromClonableElement
must implement the following two methodsobj.__copy__()
– returns a fresh copy of objobj.check()
– returns nothing, raise an exception ifobj
doesn’t satisfy the data structure invariants
and ensure to call
obj._require_mutable()
at the beginning of any modifying method.Additionally, one can also implement
obj._hash_()
– return the hash value ofobj
.
Then, given an instance
obj
ofC
, the following sequences of instructions ensures that the invariants ofnew_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, thenClonableElement
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 fromElement
.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
- clone(check=True)#
Return a clone that is mutable copy of
self
.INPUT:
check
– a boolean indicating ifself.check()
must be called after modifications.
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]
- is_immutable()#
Return
True
ifself
is immutable (cannot be changed) andFalse
if it is not.To make
self
immutable useself.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]
- is_mutable()#
Return
True
ifself
is mutable (can be changed) andFalse
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]
- set_immutable()#
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.
- class sage.structure.list_clone.ClonableIntArray#
Bases:
ClonableElement
Array of int with clone protocol
The class of objects which are
Element
behave as list of int and implement the clone protocol. SeeClonableElement
for details about clone protocol.INPUT:
parent
– aParent
lst
– a listcheck
– a boolean specifying if the invariant must be checked using methodcheck()
immutable
– a boolean telling whether the created element is immutable (defaults toTrue
)
See also
IncreasingIntArray
for an example of usage.- check()#
Check that
self
fulfill the invariantsThis 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
- index(item)#
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
- list()#
Convert self into a Python list.
EXAMPLES:
sage: from sage.structure.list_clone_demo import IncreasingIntArrays sage: I = IncreasingIntArrays()(range(5)) sage: I == list(range(5)) False sage: I.list() == list(range(5)) True sage: I = IncreasingIntArrays()(range(1000)) sage: I.list() == list(range(1000)) True
- class sage.structure.list_clone.ClonableList#
Bases:
ClonableArray
List with clone protocol
The class of objects which are
Element
behave as lists and implement the clone protocol. SeeClonableElement
for details about clone protocol.See also
IncreasingList
for an example of usage.- append(el)#
Appends
el
toself
INPUT:
el
– any objectEXAMPLES:
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
- extend(it)#
Extends
self
by the content of the iterableit
INPUT:
it
– any iterableEXAMPLES:
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
- insert(index, el)#
Inserts
el
inself
at positionindex
INPUT:
el
– any objectindex
– 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
- pop(index=-1)#
Remove
self[index]
fromself
and returns itINPUT:
index
- any int, default to -1EXAMPLES:
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(el)#
Remove the first occurrence of
el
fromself
INPUT:
el
- any objectEXAMPLES:
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
- class sage.structure.list_clone.NormalizedClonableList#
Bases:
ClonableList
List with clone protocol and normal form
This is a subclass of
ClonableList
which call a methodnormalize()
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()#
Normalize
self
This is an abstract method. Subclasses are supposed to overload
normalize()
. The callself.normalize()
is supposed tocall
self._require_mutable()
to check thatself
is in a proper mutable statemodify
self
to put it in a normal form
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