OrderedSequence.py

"""OrderedSequence.py

Classes for sequences of items subject to insertions and deletions,
with fast comparisons of the positions of two items in a sequence.

D. Eppstein, November 2003.
"""

import sys
from Sequence import Sequence

class SimpleOrderedSequence(Sequence):
    """Maintain a sequence of items subject to insertions, removals,
    and comparisons of the positions of pairs of items.  In addition to
    the information stored for a Sequence, we store an integer tag
    for each item, with the order of tags the same as the sequence order.
    When two tags collide, we renumber the whole sequence; this behavior
    can be changed by overriding the rebalance method.  Renumbers happen
    infrequently (roughly one in every log(sys.maxint) insertions)
    but take time proportional to the number of items, so it is preferable
    to use this data structure only for sequences of very few items.
    """

    def __init__(self,iterable=[],key=None):
        """The only additional data we maintain over a vanilla Sequence
        is a dictionary self._tag mapping sequence items to integers,
        such that an item is earlier than another iff its tag is smaller.
        """
        self._tag = {}
        Sequence.__init__(self,iterable,key=key)

    def cmp(self,x,y):
        """Compare the positions of x and y in the sequence."""
        return cmp(self._tag[self.key(x)],self._tag[self.key(y)])

    def append(self,x):
        """Add x to the end of the sequence."""
        if not self._next:  # add to empty sequence
            Sequence.append(self,x)
            self._tag[self.key(x)] = sys.maxint//2
        else:
            self.insertAfter(self._prev[self._first],x)

    def insertAfter(self,x,y):
        """Add y after x and compute a tag for it."""
        Sequence.insertAfter(self,x,y)
        x = self.key(x)
        y = self.key(y)
        next = self._next[y]
        if next == self._first:
            nexttag = sys.maxint
        else:
            nexttag = self._tag[next]
        xtag = self._tag[x]
        self._tag[y] = xtag + (nexttag - xtag + 1)//2
        if self._tag[y] == nexttag:
            self.rebalance(y)

    def insertBefore(self,x,y):
        """Add y before x in the sequence."""
        Sequence.insertBefore(self,x,y)
        x = self.key(x)
        y = self.key(y)
        if self._first == y:
            self._tag[y] = self._tag[x]//2
            if self._tag[y] == self._tag[x]:
                self.rebalance(y)

    def rebalance(self,x):
        """Clean up after x and its successor's tags collide."""
        base = 0
        increment = sys.maxint//len(self)
        for y in self:
            self._tag[y] = base
            base += increment

class LogarithmicOrderedSequence(SimpleOrderedSequence):
    """Maintain a sequence of items subject to insertions, removals,
    and comparisons of the positions of pairs of items.  We use the
    method of Bender, et al, ``Two Simplified Algorithms for Maintaining
    Order in a List,'' ESA 2002 (LNCS #2461) pp. 152-164,
    http://theory.lcs.mit.edu/~edemaine/papers/DietzSleator_ESA2002/
    Due to rebalancing on the integer tags used to maintain order,
    the amortized time per insertion in an n-item list is O(log n).
    """

    def rebalance(self,x):
        """Clean up after x and its successor's tags collide.

        At each iteration of the rebalancing algorithm, we look at
        a contiguous subsequence of items, defined as the items for which
        self._tag &~ mask == base.  We keep track of the first and last
        items in the subsequence, and the number of items, until we find
        a subsequence with sufficiently low density, at which point
        we space the tags evenly throughout the available values.

        The multiplier controls the growth of the threshhold density;
        it is 2/T for the T parameter described by Bender et al.
        Large multipliers lead to fewer relabels, while small items allow
        us to handle more items with machine integer tags, so we vary the
        multiplier dynamically to allow it to be as large as possible
        without producing integer overflows.
        """
        base = self._tag[x]
        mask = 0
        threshhold = 1.0
        first = last = x
        nItems = 1
        multiplier = 2/(2*len(self))**(1/30.)
        while 1:
            while first != self._first and \
                    self._tag[self._prev[first]] &~ mask == base:
                first = self._prev[first]
                nItems += 1
            while self._next[last] != self._first and \
                    self._tag[self._next[last]] &~ mask == base:
                last = self._next[last]
                nItems += 1
            increment = (mask+1)//nItems
            if increment >= threshhold:     # found rebalanceable range
                item = first
                while item != last:
                    self._tag[item] = base
                    item = self._next[item]
                    base += increment
                self._tag[last] = base
                return
            mask = (mask << 1) + 1          # expand to next power of two
            base = base &~ mask
            threshhold *= multiplier