"""Sequence.py Doubly-linked circular list for maintaining a sequence of items subject to insertions and deletions. D. Eppstein, November 2003. """ import math import sys class SequenceError(Exception): pass 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=None): """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.append(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) + '])' 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 def append(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) 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] def insertAfter(self,x,y): """Add y after x in the sequence.""" y = self.key(y) x = self.key(x) self._insafter(x,y) 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 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) 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)