Metadata-Version: 1.0
Name: odict
Version: 1.5.1
Summary: Ordered dictionary.
Home-page: https://github.com/bluedynamics/odict
Author: BlueDynamics Alliance
Author-email: dev@bluedynamics.com
License: Python Software Foundation License
Description: 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}
        
        It is possible to use abstract mixin class ``_odict`` to hook another dict base
        implementation. This is useful i.e. when persisting to ZODB. Inheriting from
        ``dict`` and ``Persistent`` at the same time fails::
        
            >>> from persistent.dict import PersistentDict 
            >>> class podict(_odict, PersistentDict):
            ...     def _dict_impl(self):
            ...         return PersistentDict
        
        
        Requires
        --------
        
        - Python 2.4+
        
        
        Changes
        =======
        
        
        Version 1.5.1
        -------------
        
        - Implement ``__copy__`` and ``__deepcopy__`` in order to work with Python 2.7.
          [rnix, 2012-10-15]
        
        - Use ``try/except`` instead of ``in`` in ``__contains__``.
          [rnix, 2012-10-15]
        
        
        Version 1.5.0
        -------------
        
        - Implement ``alter_key``.
          [rnix, 2012-05-18]
        
        
        Version 1.4.4
        -------------
        
        - Remove unused error variable.
          [rnix, 2011-11-28]
        
        - Add note on why to check with ``==`` and ``!=`` against ``_nil``.
          [rnix, 2011-11-28]
        
        
        Version 1.4.3
        -------------
        
        - Get rid of annoying warning about "global" usage in ``bench.py``.
          [jensens, 2011-09-20]
        
        
        Version 1.4.2
        -------------
        
        - More ``copy`` testing.
          [rnix, 2010-12-18]
        
        - Add ``has_key`` to odict.
          [rnix, 2010-12-18]
        
        
        Version 1.4.1
        -------------
        
        - Fix release, README.rst was missing, added MANIFEST.in file to include it.
          [jensens, 2010-11-29]
        
        
        Version 1.4.0
        -------------
        
        - Full test coverage.
          [chaoflow, rnix, 2010-08-17]
        
        - Code cleanup and optimizing.
          [chaoflow, rnix, 2010-08-17]
        
        
        Version 1.3.2
        -------------
        
        - Access ``dict`` API providing class via function ``_dict_impl()`` and
          provide odict logic as abstract base class ``_odict``.
          [rnix, 2010-07-08]
        
        
        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]
        
        
        Contributors
        ============
        
        - bearophile
        
        - Robert Niederreiter <rnix [at] squarewave [dot] at>
        
        - Georg Bernhard <g [dot] bernhard [at] akbild [dot] ac [dot] at>
        
        - Florian Friesdorf <flo [at] chaoflow [dot] net>
        
        under the `Python Software Foundation License 
        <http://www.opensource.org/licenses/PythonSoftFoundation.php>`_.
        
        License
        =======
        
        Copyright (c) 2010, BlueDynamics Alliance, Austria
        All rights reserved.
        
        Redistribution and use in source and binary forms, with or without
        modification, are permitted provided that the following conditions are met:
        
        * Redistributions of source code must retain the above copyright notice, this 
          list of conditions and the following disclaimer.
        * Redistributions in binary form must reproduce the above copyright notice, this 
          list of conditions and the following disclaimer in the documentation and/or 
          other materials provided with the distribution.
        * Neither the name of the BlueDynamics Alliance nor the names of its 
          contributors may be used to endorse or promote products derived from this 
          software without specific prior written permission.
              
        THIS SOFTWARE IS PROVIDED BY BlueDynamics Alliance ``AS IS`` AND ANY
        EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
        WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
        DISCLAIMED. IN NO EVENT SHALL BlueDynamics Alliance BE LIABLE FOR ANY
        DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES
        (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES;
        LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
        ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
        (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
        SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
        
Keywords: odict dict ordered dictionary mapping collection tree
Platform: UNKNOWN
Classifier: Development Status :: 5 - Production/Stable
Classifier: License :: OSI Approved :: Python Software Foundation License
Classifier: Operating System :: OS Independent
Classifier: Programming Language :: Python
Classifier: Topic :: Software Development
