# Source code for tryalgo.Sequence

```"""Sequence.py

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

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]
"""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)

```