"""
myodict.py  -- V.1.2, Apr 12 2007, by leonardo maffi

Dictionary in which the *insertion* order of items is preserved (using an internal double
linked list). In this implementation replacing an existing item keeps it at its original
position.


Requires Python V.2.4 or successive.

NOTE: the print and repr of Odicts are 'deterministic' because the order of elements
  is defined. The output of _repr isn't defined, it contains the repr of the underlying
  normal dict.

INTERNAL REPRESENTATION: values of this Odict:
  +-----------+----------+-----------+
  | <pred key | true val | succ key> |
  +-----------+----------+-----------+
The sequence of elements uses as a double linked list. The 'links' are dict keys.
  self.lh and self.lt are the keys of first and last element inserted in the Odict.
(In a C re-implementation of this data structure, things can be simplified (and
  speed up) a lot if given a value you can at the same time find its key. With
  that, you can use normal C pointers.)


MEMORY USED (Python 2.5):
set(int): 28.2 bytes/element
dict(int:None): 36.2 bytes/element
Odict(int:None): 102 bytes/element

SPEED:
- This Odict is about 20-25 times slower than a dict, for insert and del operations.
- del too is O(1).

The following code is too much slow for another Odict implementation that stores
the key order with a list:
n = 100000
o = Odict().fromkeys(xrange(n))
for i in xrange(n): del o[i]

sort() is available too, to have keys in their natural order (but they don't keep
being sorted if you add more keys later, you have to sort them again.)
To sort according to the values:
someodict.sort(key=someodict.__getitem__)

-----------------------------

Doctests of len, __contains__, has_key, reversed:
>>> o = Odict()
>>> print len(o)
0
>>> for i in [1,2,3]: o[str(i)] = i
>>> print len(o)
3
>>> o['2'] = 20
>>> o.lh, o.lt, o
('1', '3', Odict([('1', 1), ('2', 20), ('3', 3)]))
>>> '2' in o
True
>>> o.has_key('2')
True
>>> o.has_key('9')
False
>>> '4' not in o
True
>>> list(reversed(o))
['3', '2', '1']
"""


class _Nil:
    """Class of the 'pointer' to the null key. For internal use only."""
    def __repr__(self): # Useful for Odict._repr()
        return "nil"

_nil = _Nil() # 'Pointer' to the null key.


class Odict(dict):
    """
    Ordered dict data structure, with O(1) complexity for dict operations
    that modify one element.
    Overwriting values doesn't change their original sequential order."""

    def __init__(self, data=(), **kwds):
        """This doesn't accept keyword initialization as normal dicts to avoid a trap:
        inside a function or method the keyword args are accessible only as a dict,
        without a defined order, so their original order is lost.

        __init__ test, with keyword args:
        >>> Odict(a=1)
        Traceback (most recent call last):
          ...
        TypeError: __init__() of ordered dict takes no keyword arguments to avoid an ordering trap.

        If initialized with a dict the order of elements is undefined!:
        >>> o = Odict({"a":1, "b":2, "c":3, "d":4})
        >>> print o
        {'a': 1, 'c': 3, 'b': 2, 'd': 4}
        """
        if kwds:
            raise TypeError("__init__() of ordered dict takes no keyword arguments to"
                            " avoid an ordering trap.")
        dict.__init__(self)
        self.lh = _nil # Double-linked list header
        self.lt = _nil # Double-linked list tail
        # If you give a normal dict, then the order of elements is undefined
        if hasattr(data, "iteritems"):
            for key, val in data.iteritems():
                self[key] = val
        else:
            for key, val in data:
                self[key] = val


    # len, has_key. __contains__ don't need to be defined


    def __getitem__(self, key):
        """
        >>> o = Odict()
        >>> o.lh, o.lt, o
        (nil, nil, Odict())
        >>> o._repr()
        'Odict low level repr lh,lt,data: nil, nil, {}'
        >>> o["1"] = 2
        >>> o["1"]
        2
        >>> o["2"]
        Traceback (most recent call last):
          ...
        KeyError: '2'
        """
        return dict.__getitem__(self, key)[1]


    def __setitem__(self, key, val):
        """
        >>> o = Odict()
        >>> o.lh, o.lt, o
        (nil, nil, Odict())
        >>> o["1"] = 1
        >>> o.lh, o.lt, o
        ('1', '1', Odict([('1', 1)]))
        >>> o._repr()
        "Odict low level repr lh,lt,data: '1', '1', {'1': [nil, 1, nil]}"
        >>> o["2"] = 2
        >>> o.lh, o.lt, o
        ('1', '2', Odict([('1', 1), ('2', 2)]))
        >>> o._repr()
        "Odict low level repr lh,lt,data: '1', '2', {'1': [nil, 1, '2'], '2': ['1', 2, nil]}"
        >>> o["3"] = 3
        >>> o.lh, o.lt, o
        ('1', '3', Odict([('1', 1), ('2', 2), ('3', 3)]))
        >>> o._repr()
        "Odict low level repr lh,lt,data: '1', '3', {'1': [nil, 1, '2'], '3': ['2', 3, nil], '2': ['1', 2, '3']}"
        """
        if key in self:
            dict.__getitem__(self, key)[1] = val
        else:
            new = [self.lt, val, _nil]
            dict.__setitem__(self, key, new)
            if self.lt is _nil:
                self.lh = key
            else:
                dict.__getitem__(self, self.lt)[2] = key
            self.lt = key


    def __delitem__(self, key):
        """
        del test 1, removal from empty Odict:
        >>> o = Odict()
        >>> del o["1"]
        Traceback (most recent call last):
          ...
        KeyError: '1'

        del test 2, removal from Odict with one element:
        >>> o = Odict()
        >>> o["1"] = 1
        >>> del o["1"]
        >>> o.lh, o.lt, o, o
        (nil, nil, Odict(), Odict())
        >>> o._repr()
        'Odict low level repr lh,lt,data: nil, nil, {}'

        del test 3, removal firt element of the Odict sequence:
        >>> o = Odict()
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> del o["1"]
        >>> o.lh, o.lt, o
        ('2', '3', Odict([('2', 2), ('3', 3)]))
        >>> o._repr()
        "Odict low level repr lh,lt,data: '2', '3', {'3': ['2', 3, nil], '2': [nil, 2, '3']}"

        del test 4, removal element in the middle of the Odict sequence:
        >>> o = Odict()
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> del o["2"]
        >>> o.lh, o.lt, o
        ('1', '3', Odict([('1', 1), ('3', 3)]))
        >>> o._repr()
        "Odict low level repr lh,lt,data: '1', '3', {'1': [nil, 1, '3'], '3': ['1', 3, nil]}"

        del test 5, removal element at the end of the Odict sequence:
        >>> o = Odict()
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> del o["3"]
        >>> o.lh, o.lt, o
        ('1', '2', Odict([('1', 1), ('2', 2)]))
        >>> o._repr()
        "Odict low level repr lh,lt,data: '1', '2', {'1': [nil, 1, '2'], '2': ['1', 2, nil]}"
        """
        if key in self:
            pred, _ ,succ= dict.__getitem__(self, key)
            if pred is _nil:
                self.lh = succ
            else:
                dict.__getitem__(self, pred)[2] = succ
            if succ is _nil:
                self.lt = pred
            else:
                dict.__getitem__(self, succ)[0] = pred
            dict.__delitem__(self, key)
        else:
            raise KeyError, key


    def __str__(self):
        """
        >>> o = Odict()
        >>> o["a"] = 'hello'
        >>> o[2] = 'hallo'
        >>> o['hallo'] = 3
        >>> print o
        {'a': 'hello', 2: 'hallo', 'hallo': 3}
        """
        pairs = ("%r: %r" % (k, v) for k, v in self.iteritems())
        return "{%s}" % ", ".join(pairs)


    def __repr__(self):
        """
        >>> o = Odict()
        >>> o["a"] = 'hello'
        >>> o[2] = 'hallo'
        >>> o['hallo'] = 3
        >>> print repr(o)
        Odict([('a', 'hello'), (2, 'hallo'), ('hallo', 3)])
        """
        if self:
            pairs = ("(%r, %r)" % (k, v) for k, v in self.iteritems())
            return "Odict([%s])" % ", ".join(pairs)
        else:
            return "Odict()"


    def get(self, k, x=None):
        """
        >>> o = Odict()
        >>> o["1"] = 1
        >>> print o.get(5)
        None
        >>> o.get(5, 10)
        10
        >>> o.get("1")
        1
        >>> o.get("1", 10)
        1
        """
        if k in self:
            return dict.__getitem__(self, k)[1]
        else:
            return x


    def __iter__(self):
        """
        >>> o = Odict()
        >>> print len(o)
        0
        >>> print list(o)
        []
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> print list(o)
        ['1', '2', '3']
        """
        curr_key = self.lh
        while curr_key is not _nil:
            yield curr_key
            curr_key = dict.__getitem__(self, curr_key)[2]


    iterkeys = __iter__


    def keys(self):
        """
        >>> o = Odict()
        >>> list(o.iterkeys())
        []
        >>> o.keys()
        []
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> list(o.iterkeys())
        ['1', '2', '3']
        >>> o.keys()
        ['1', '2', '3']
        """
        return list(self.iterkeys())


    def itervalues(self):
        """
        >>> o = Odict()
        >>> list(o.itervalues())
        []
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> list(o.itervalues())
        [1, 2, 3]
        """
        curr_key = self.lh
        while curr_key is not _nil:
            _, val, curr_key = dict.__getitem__(self, curr_key)
            yield val


    def values(self):
        """
        >>> o = Odict()
        >>> o.values()
        []
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> o.values()
        [1, 2, 3]
        """
        return list(self.itervalues())


    def iteritems(self):
        """
        >>> o = Odict()
        >>> list(o.iteritems())
        []
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> list(o.iteritems())
        [('1', 1), ('2', 2), ('3', 3)]
        """
        curr_key = self.lh
        while curr_key is not _nil:
            _, val, next_key = dict.__getitem__(self, curr_key)
            yield curr_key, val
            curr_key = next_key


    def items(self):
        """
        >>> o = Odict()
        >>> o.items()
        []
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> o.items()
        [('1', 1), ('2', 2), ('3', 3)]
        """
        return list(self.iteritems())


    def clear(self):
        """
        >>> o = Odict()
        >>> list(o)
        []
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> list(o)
        ['1', '2', '3']
        >>> o.clear()
        >>> list(o)
        []
        >>> o._repr()
        'Odict low level repr lh,lt,data: nil, nil, {}'
        """
        dict.clear(self)
        self.lh = _nil
        self.lt = _nil


    def copy(self):
        """
        >>> o1 = Odict()
        >>> for i in [1,2,3]: o1[str(i)] = i
        >>> o1.lh, o1.lt, o1
        ('1', '3', Odict([('1', 1), ('2', 2), ('3', 3)]))
        >>> o2 = o1.copy()
        >>> o2.lh, o2.lt, o2
        ('1', '3', Odict([('1', 1), ('2', 2), ('3', 3)]))
        >>> del o1["1"]
        >>> o1.lh, o1.lt, o1
        ('2', '3', Odict([('2', 2), ('3', 3)]))
        >>> o2.lh, o2.lt, o2
        ('1', '3', Odict([('1', 1), ('2', 2), ('3', 3)]))
        """
        return self.__class__(self)


    def update(self, data=(), **kwds):
        """
        First group of update tests:
        >>> o = Odict()
        >>> o.update( [(1,2), (3,4)] )
        >>> print o
        {1: 2, 3: 4}
        >>> o.update( [(1,5), (6,7)] )
        >>> print o
        {1: 5, 3: 4, 6: 7}
        >>> o2 = Odict([(8, 9)])
        >>> print o2
        {8: 9}
        >>> o2.update(o)
        >>> print o2
        {8: 9, 1: 5, 3: 4, 6: 7}

        Assert that update doesn't create a new Odict object:
        >>> o = Odict()
        >>> id1 = id(o)
        >>> o2 = o.update([(2,3), (3,4)])
        >>> id(o2) == id1
        False

        update test, it refuses keyword arguments:
        >>> o = Odict()
        >>> o.update(a=1)
        Traceback (most recent call last):
          ...
        TypeError: update() of ordered dict takes no keyword arguments to avoid an ordering trap.
        """
        if kwds:
            raise TypeError("update() of ordered dict takes no keyword arguments"
                            " to avoid an ordering trap.")
        if hasattr(data, "iteritems"):
            for key, val in data.iteritems():
                self[key] = val
        else:
            for key, val in data:
                self[key] = val


    @classmethod
    def fromkeys(cls, seq, value=None):
        """
        >>> print Odict().fromkeys("abc")
        {'a': None, 'b': None, 'c': None}
        >>> print Odict.fromkeys("abc", 1)
        {'a': 1, 'b': 1, 'c': 1}

        >>> print Odict().fromkeys()
        Traceback (most recent call last):
          ...
        TypeError: fromkeys() takes at least 2 arguments (1 given)
        >>> dict.fromkeys()
        Traceback (most recent call last):
          ...
        TypeError: fromkeys expected at least 1 arguments, got 0
        """
        new = cls()
        for key in seq:
            new[key] = value
        return new


    def setdefault(self, k, x=None):
        """a[k] if k in a
        else x, also setting it.

        >>> o = Odict()
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> d = dict()
        >>> for i in [1,2,3]: d[str(i)] = i
        >>> print o.setdefault('4')
        None
        >>> print d.setdefault('4')
        None
        >>> print o
        {'1': 1, '2': 2, '3': 3, '4': None}
        >>> print d
        {'1': 1, '3': 3, '2': 2, '4': None}
        >>> print o.setdefault('5', 5)
        5
        >>> print d.setdefault('5', 5)
        5
        >>> print o.setdefault('1', 6)
        1
        >>> print d.setdefault('1', 6)
        1
        >>> print o
        {'1': 1, '2': 2, '3': 3, '4': None, '5': 5}
        >>> print d
        {'1': 1, '3': 3, '2': 2, '5': 5, '4': None}
        """
        if k in self:
            return self[k]
        else:
            self[k] = x
            return x


    def pop(self, k, x=_nil):
        """a[k] if k in a, and remove k
        else x.

        >>> o = Odict()
        >>> for i in [1,2,3]: o[str(i)] = i+3
        >>> d = dict()
        >>> for i in [1,2,3]: d[str(i)] = i+3
        >>> print o.pop()
        Traceback (most recent call last):
          ...
        TypeError: pop() takes at least 2 arguments (1 given)
        >>> print d.pop()
        Traceback (most recent call last):
          ...
        TypeError: pop expected at least 1 arguments, got 0
        >>> print o.pop(7)
        Traceback (most recent call last):
          ...
        KeyError: 7
        >>> print d.pop(7)
        Traceback (most recent call last):
          ...
        KeyError: 7
        >>> print o.pop(7, 8)
        8
        >>> print o
        {'1': 4, '2': 5, '3': 6}
        >>> print d.pop(7, 8)
        8
        >>> print d
        {'1': 4, '3': 6, '2': 5}
        >>> print o.pop('1')
        4
        >>> print o
        {'2': 5, '3': 6}
        >>> print d.pop('1')
        4
        >>> print d
        {'3': 6, '2': 5}
        >>> print o.pop('2', "A")
        5
        >>> print o
        {'3': 6}
        >>> print d.pop('2', "A")
        5
        >>> print d
        {'3': 6}
        >>> print o.pop(5, None)
        None
        >>> print d.pop(5, None)
        None
        >>> print o
        {'3': 6}
        >>> o.pop(5)
        Traceback (most recent call last):
          ...
        KeyError: 5
        """
        if k in self:
            val = self[k]
            del self[k]
            return val
        elif x is _nil:
            raise KeyError(k)
        else:
            return x


    def popitem(self):
        """remove and return the last (key, value) pair.

        >>> o = Odict()
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> print o
        {'1': 1, '2': 2, '3': 3}
        >>> o.popitem()
        ('3', 3)
        >>> o.popitem()
        ('2', 2)
        >>> o.popitem()
        ('1', 1)
        >>> o.lh, o.lt, o
        (nil, nil, Odict())
        >>> o.popitem()
        Traceback (most recent call last):
          ...
        KeyError: "'popitem(): ordered dictionary is empty'"
        """
        if self:
            key = self.lt
            val = dict.__getitem__(self, key)[1]
            self.__delitem__(key)
            return key, val
        else:
            raise KeyError("'popitem(): ordered dictionary is empty'")


    # Some Odict-specific methods ----------------------------------------

    def riterkeys(self):
        """To iterate on keys in reversed order.

        >>> o = Odict()
        >>> list(o.riterkeys())
        []
        >>> for i in [1,2,3]: o[str(i)] = i+3
        >>> print o
        {'1': 4, '2': 5, '3': 6}
        >>> list(o.riterkeys())
        ['3', '2', '1']
        """
        curr_key = self.lt
        while curr_key is not _nil:
            yield curr_key
            curr_key = dict.__getitem__(self, curr_key)[0]


    __reversed__ = riterkeys


    def rkeys(self):
        """List of the keys in reversed order.

        >>> o = Odict()
        >>> o.rkeys()
        []
        >>> for i in [1,2,3]: o[str(i)] = i+3
        >>> print o
        {'1': 4, '2': 5, '3': 6}
        >>> o.rkeys()
        ['3', '2', '1']
        """
        return list(self.riterkeys())


    def ritervalues(self):
        """To iterate on values in reversed order.

        >>> o = Odict()
        >>> list(o.ritervalues())
        []
        >>> for i in [1,2,3]: o[str(i)] = i+3
        >>> print o
        {'1': 4, '2': 5, '3': 6}
        >>> list(o.ritervalues())
        [6, 5, 4]
        """
        curr_key = self.lt
        while curr_key is not _nil:
            curr_key, val, _ = dict.__getitem__(self, curr_key)
            yield val


    def rvalues(self):
        """List of the values in reversed order.

        >>> o = Odict()
        >>> o.rvalues()
        []
        >>> for i in [1,2,3]: o[str(i)] = i+3
        >>> print o
        {'1': 4, '2': 5, '3': 6}
        >>> o.rvalues()
        [6, 5, 4]
        """
        return list(self.ritervalues())


    def riteritems(self):
        """To iterate on (key, value) in reversed order.

        >>> o = Odict()
        >>> list(o.riteritems())
        []
        >>> for i in [1,2,3]: o[str(i)] = i+3
        >>> print o
        {'1': 4, '2': 5, '3': 6}
        >>> list(o.riteritems())
        [('3', 6), ('2', 5), ('1', 4)]
        """
        curr_key = self.lt
        while curr_key is not _nil:
            pred_key, val, _ = dict.__getitem__(self, curr_key)
            yield curr_key, val
            curr_key = pred_key


    def ritems(self):
        """List of the (key, value) in reversed order.

        >>> o = Odict()
        >>> o.ritems()
        []
        >>> for i in [1,2,3]: o[str(i)] = i+3
        >>> print o
        {'1': 4, '2': 5, '3': 6}
        >>> o.ritems()
        [('3', 6), ('2', 5), ('1', 4)]
        """
        return list(self.riteritems())


    def firstkey(self):
        """
        >>> o = Odict()
        >>> o.firstkey()
        Traceback (most recent call last):
          ...
        KeyError: "'firstkey(): ordered dictionary is empty'"
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> print o
        {'1': 1, '2': 2, '3': 3}
        >>> o.firstkey()
        '1'
        """
        if self:
            return self.lh
        else:
            raise KeyError("'firstkey(): ordered dictionary is empty'")


    def lastkey(self):
        """
        >>> o = Odict()
        >>> o.lastkey()
        Traceback (most recent call last):
          ...
        KeyError: "'lastkey(): ordered dictionary is empty'"
        >>> for i in [1,2,3]: o[str(i)] = i
        >>> o.lastkey()
        '3'
        """
        if self:
            return self.lt
        else:
            raise KeyError("'lastkey(): ordered dictionary is empty'")


    def _repr(self):
        """_repr(): low level repr of the whole data contained in the Odict.
        Useful for debugging."""
        form = "Odict low level repr lh,lt,data: %r, %r, %s"
        return form % (self.lh, self.lt, dict.__repr__(self))


    def sort(self, **kwds):
        """
        >>> o = Odict([('2', 20), ('1', 1), ('3', 3)])
        >>> o.sort()
        >>> o
        Odict([('1', 1), ('2', 20), ('3', 3)])
        >>> from operator import itemgetter
        >>> o.sort(reverse=True)
        >>> o
        Odict([('3', 3), ('2', 20), ('1', 1)])
        >>> o._repr()
        "Odict low level repr lh,lt,data: '3', '1', {'1': ['2', 1, nil], '3': [nil, 3, '2'], '2': ['3', 20, '1']}"
        >>> o.sort(key=o.__getitem__) # to sort according to the values:
        >>> o
        Odict([('1', 1), ('3', 3), ('2', 20)])
        """
        if dict:
            sorted_keys = sorted(dict.iterkeys(self), **kwds)
            self.lh = sorted_keys[0]
            self.lt = sorted_keys[-1]

            pred_key = _nil
            for pos in xrange(len(sorted_keys) - 1):
                curr_key = sorted_keys[pos]
                _, val, _ = dict.__getitem__(self, curr_key)
                new = [pred_key, val, sorted_keys[pos+1]]
                dict.__setitem__(self, curr_key, new)
                pred_key = curr_key

            curr_key = sorted_keys[-1]
            _, val, _ = dict.__getitem__(self, curr_key)
            new = [pred_key, val, _nil]
            dict.__setitem__(self, curr_key, new)


def _speed_test(start=14, stop=19):
    """Function to test the speed of this Odict implementation against the speed of
    normal dicts for inserts and deletions."""
    from time import clock

    for p in xrange(start, stop):
        n = 2 ** p
        print "n = 2**%d = %d:" % (p, n)

        t = clock()
        d = {}
        for i in xrange(n): d[i] = None
        tadd_dict = round(clock()-t, 3)
        print "  dict add:", tadd_dict, "s"
        t = clock()
        for i in xrange(n): del d[i]
        tdel_dict = round(clock()-t, 3)
        print "  dict del:", tdel_dict, "s"

        t = clock()
        o1 = Odict()
        for i in xrange(n): o1[i] = None
        tadd_odict = round(clock()-t, 2)
        print "  Odict add:", tadd_odict, "s,", round(tadd_odict / tadd_dict, 1), "times."
        t = clock()
        for i in xrange(n): del o1[i]
        tdel_odict = round(clock()-t, 2)
        print "  Odict del:", tdel_odict, "s,", round(tdel_odict / tdel_dict, 1), "times."
        print

    raw_input("Press a key to finish.")


if __name__ == "__main__":
    import doctest
    doctest.testmod()
    #_speed_test() # Uncomment this to test the speed of this Odict implementation against the speed of normal dicts for inserts and deletions.
    print "Tests finished."