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() (see IncreasingArray and the parent class IncreasingArrays)

• IncreasingLists() (see IncreasingList and the parent class IncreasingLists)

• SortedLists() (see SortedList and the parent class SortedLists)

• IncreasingIntArrays() (see IncreasingIntArray and the parent class IncreasingIntArrays)

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:

• [Prototype_pattern]

• [GHJV1994]

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. See ClonableElement for details about clone protocol.

INPUT:

• parent – a Parent

• lst – a list

• check – a boolean specifying if the invariant must be checked using method check().

• immutable – a boolean telling whether the created element is immutable (defaults to True)

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 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

count(key)

Return 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

index(x, start=None, stop=None)

Return 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

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 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 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 of obj.

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

clone(check=True)

Return a clone that is mutable copy of self.

INPUT:

• check – a boolean indicating if self.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 if self is immutable (cannot 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]

is_mutable()

Return 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]

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. See ClonableElement for details about clone protocol.

INPUT:

• parent – a Parent

• lst – a list

• check – a boolean specifying if the invariant must be checked using method check()

• immutable – a boolean telling whether the created element is immutable (defaults to True)

See also

IncreasingIntArray for an example of usage.

check()

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

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. See ClonableElement for details about clone protocol.

See also

IncreasingList for an example of usage.

append(el)

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

extend(it)

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

insert(index, el)

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

pop(index=-1)

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(el)

Remove the first occurrence 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

class sage.structure.list_clone.NormalizedClonableList

Bases: 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()

Normalize self

This is an abstract method. Subclasses are supposed to overload normalize(). The call self.normalize() is supposed to

• call self._require_mutable() to check that self is in a proper mutable state

• modify 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