Source code for tryalgo.Sequence


Doubly-linked circular list for maintaining a sequence of items
subject to insertions and deletions.

Copyright D. Eppstein, November 2003. Under the MIT licence.

Modified by
Rami Benelmir, Christoph Dürr, Erisa Kohansal - 2023

we adapted the data structure to store only objects and to permit to replace objects easily.
we changed the name of the function "append" to "add" for simplifying our code.

import math
import sys

[docs] class SequenceError(Exception): pass
[docs] class Sequence: """Maintain a sequence of items subject to insertions and removals. All sequence operations take constant time except indexing, which takes time proportional to the index. """ def __init__(self, iterable=[], key=id): """We represent the sequence as a doubly-linked circular linked list, stored in two dictionaries, self._next and self._prev. We also store a pointer self._first to the first item in the sequence. If key is supplied, key(x) is used in place of x to look up item positions; e.g. using key=id allows sequences of lists or sets. """ self._key = key self._items = {} self._next = {} self._prev = {} self._first = None for x in iterable: self.add(x) def __iter__(self): """Iterate through the objects in the sequence. May give unpredictable results if sequence changes mid-iteration. """ item = self._first while self._next: yield self._items.get(item,item) item = self._next[item] if item == self._first: return def __getitem__(self,i): """Return the ith item in the sequence.""" item = self._first while i: item = self._next[item] if item == self._first: raise IndexError("Index out of range") i -= 1 return self._items.get(item,item) def __len__(self): """Number of items in the sequence.""" return len(self._next) def __repr__(self): """Printable representation of the sequence.""" output = [] for x in self: output.append(repr(x)) return 'Sequence([' + ','.join(output) + '])'
[docs] def key(self,x): """Apply supplied key function.""" if not self._key: return x key = self._key(x) self._items[key] = x return key
def _insafter(self,x,y): """Unkeyed version of insertAfter.""" if y in self._next: raise SequenceError("Item already in sequence: "+repr(y)) self._next[y] = z = self._next[x] self._next[x] = self._prev[z] = y self._prev[y] = x
[docs] def add(self,x): """Add x to the end of the sequence.""" x = self.key(x) if not self._next: # add to empty sequence self._next = {x:x} self._prev = {x:x} self._first = x else: self._insafter(self._prev[self._first],x)
[docs] def remove(self,x): """Remove x from the sequence.""" x = self.key(x) prev = self._prev[x] self._next[prev] = next = self._next[x] self._prev[next] = prev if x == self._first: self._first = next del self._next[x], self._prev[x]
[docs] def insertAfter(self, x, y): """Add y after x in the sequence.""" y = self.key(y) x = self.key(x) self._insafter(x,y)
[docs] def insertBefore(self, x, y): """Add y before x in the sequence.""" y = self.key(y) x = self.key(x) self._insafter(self._prev[x],y) if self._first == x: self._first = y
[docs] def predecessor(self,x): """Find the previous element in the sequence.""" x = self.key(x) prev = self._prev[x] return self._items.get(prev,prev)
[docs] def successor(self,x): """Find the next element in the sequence.""" x = self.key(x) next = self._next[x] return self._items.get(next,next)
[docs] def replace(self, old, new): """ Replace an object by another one, preserving the position in the sequence """ self.insertAfter(old, new) self.remove(old)