
odict
=====

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.

Internal representation: values of the dict:
::

    [pred_key, 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 
inseted in the odict. In a C reimplementation 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

Performance
-----------

When running the benchmark script, you get results similar to the one below
on recent common hardware.

Adding and deleting ``dict`` objects.
::

    +----------------+--------------------+
    | Add 1000       | 0.000653028488159  |
    +----------------+--------------------+
    | Delete 1000    | 0.000339031219482  |
    +----------------+--------------------+
    | Add 10000      | 0.00774908065796   |
    +----------------+--------------------+
    | Delete 10000   | 0.00406503677368   |
    +----------------+--------------------+
    | Add 100000     | 0.130412101746     |
    +----------------+--------------------+
    | Delete 100000  | 0.0517508983612    |
    +----------------+--------------------+
    | Add 1000000    | 3.17614817619      |
    +----------------+--------------------+
    | Delete 1000000 | 0.564585924149     |
    +----------------+--------------------+

Adding and deleting ``odict`` objects.
::

    +----------------+--------------------+
    | Add 1000       | 0.0096800327301    |
    +----------------+--------------------+
    | Delete 1000    | 0.00276303291321   |
    +----------------+--------------------+
    | Add 10000      | 0.107849836349     |
    +----------------+--------------------+
    | Delete 10000   | 0.0282921791077    |
    +----------------+--------------------+
    | Add 100000     | 1.05564808846      |
    +----------------+--------------------+
    | Delete 100000  | 0.297379016876     |
    +----------------+--------------------+
    | Add 1000000    | 16.451695919       |
    +----------------+--------------------+
    | Delete 1000000 | 3.03641605377      |
    +----------------+--------------------+

Relation ``dict:odict`` of creating and deleting.
::

    +---------------------------+-----------+
    | creating 1000 objects     | 1:14.823  |
    +---------------------------+-----------+
    | deleting 1000 objects     | 1:8.1497  |
    +---------------------------+-----------+
    | creating 10000 objects    | 1:13.917  |
    +---------------------------+-----------+
    | deleting 10000 objects    | 1:6.9598  |
    +---------------------------+-----------+
    | creating 100000 objects   | 1:8.0947  |
    +---------------------------+-----------+
    | deleting 100000 objects   | 1:5.7463  |
    +---------------------------+-----------+
    | creating 1000000 objects  | 1:5.1797  |
    +---------------------------+-----------+
    | deleting 1000000 objects  | 1:5.3781  |
    +---------------------------+-----------+

Usage
-----

Import and create ordered dictionary.
::

    >>> from odict import odict
    >>> od = odict()

type conversion to ordinary ``dict``. This will fail.
::

    >>> dict(odict([(1, 1)]))
    {1: [nil, 1, nil]}

The reason for this is here -> http://bugs.python.org/issue1615701

The ``__init__`` function of ``dict`` checks wether arg is subclass of dict,
and ignores overwritten ``__getitem__`` & co if so.

This was fixed and later reverted due to behavioural problems with ``pickle``.

Use one of the following ways for type conversion.
::
    
    >>> dict(odict([(1, 1)]).items())
    {1: 1}
    
    >>> odict([(1, 1)]).as_dict()
    {1: 1}

Requires
-------- 

    -Python 2.4+

Changes
=======

Version 1.3.1
-------------

    -Add test for bool evaluation
     rnix, 2010-04-21

Version 1.3.0
-------------

    -Fix access to ``odict.lt`` and ``odict.lh`` properties. Now it's possible
     to overwrite ``__setattr__`` and ``__getattr__`` on ``odict`` subclass
     without hassle.
     rnix, 2010-04-06

    -Add ``sort`` function to odict.
     rnix, 2010-03-03

Version 1.2.6
-------------

    -Make ``odict`` serialize and deserialize properly
     gogo, 2010-01-12

Version 1.2.5
-------------

    -Add ``as_dict`` function. Supports type conversion to ordinary ``dict``.
     rnix, 2009-12-19

    -Add benchmark script
     rnix, 2009-12-19

Version 1.2.4
-------------

    -Do not check for ``key in self`` on ``__delitem__``, ``KeyError`` is raised
     properly anyway. Huge Speedup!
     rnix, jensens, 2009-12-18

Version 1.2.3
-------------

    -Move tests to seperate file and make egg testable with 
     ``python setup.py test``.
     rnix, 2009-12-07

    -improve ``lt`` and ``lh`` properties to make ``odict`` work with 
     ``copy.deepcopy``.
     rnix, 2009-12-07

Version 1.2.2
-------------

    -Use try/except instead of ``__iter__`` in ``__setitem__`` to determine if
     value was already set.
     rnix, 2009-07-17

Version 1.2.1
-------------

    -Add missing ``__len__`` and ``__contains__`` functions.
     rnix, 2009-03-17
   
Version 1.2.0
-------------

    -eggified
     rnix, 2009-03-17

Version < 1.2
-------------

    -http://code.activestate.com/recipes/498195/
     bearophile, 2006-10-12
 
Credits
=======
  
    -bearophile
    
    -Robert Niederreiter <rnix@squarewave.at>
    
    -Georg Bernhard <g.bernhard@akbild.ac.at>
