Metadata-Version: 2.1
Name: odict
Version: 1.6.0.dev0
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
        inserted in the odict.
        
        In a C reimplementation of this data structure, things could 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 (Python 3.4)
        ------------------------
        
        When running the benchmark script, you get results similar to the one below on
        recent common hardware.
        
        Adding and deleting builtin ``dict`` objects
        
        +----------------+-------------+
        | Add       1000 | 0.63800ms   |
        +----------------+-------------+
        | Delete    1000 | 0.36900ms   |
        +----------------+-------------+
        | Add      10000 | 5.74600ms   |
        +----------------+-------------+
        | Delete   10000 | 3.97000ms   |
        +----------------+-------------+
        | Add     100000 | 69.40600ms  |
        +----------------+-------------+
        | Delete  100000 | 47.30000ms  |
        +----------------+-------------+
        | Add    1000000 | 807.09100ms |
        +----------------+-------------+
        | Delete 1000000 | 495.33400ms |
        +----------------+-------------+
        
        Adding and deleting ``collection.OrderedDict`` objects
        
        +----------------+---------------+
        | Add       1000 | 8.15200ms     |
        +----------------+---------------+
        | Delete    1000 | 0.50800ms     |
        +----------------+---------------+
        | Add      10000 | 91.45800ms    |
        +----------------+---------------+
        | Delete   10000 | 7.10200ms     |
        +----------------+---------------+
        | Add     100000 | 982.35500ms   |
        +----------------+---------------+
        | Delete  100000 | 71.02300ms    |
        +----------------+---------------+
        | Add    1000000 | 10222.78300ms |
        +----------------+---------------+
        | Delete 1000000 | 715.35100ms   |
        +----------------+---------------+
        
        Adding and deleting ``odict`` objects provided by this package
        
        +----------------+--------------+
        | Add       1000 | 46.75600ms   |
        +----------------+--------------+
        | Delete    1000 | 0.35700ms    |
        +----------------+--------------+
        | Add      10000 | 23.97900ms   |
        +----------------+--------------+
        | Delete   10000 | 4.79100ms    |
        +----------------+--------------+
        | Add     100000 | 276.15900ms  |
        +----------------+--------------+
        | Delete  100000 | 49.02700ms   |
        +----------------+--------------+
        | Add    1000000 | 3244.68600ms |
        +----------------+--------------+
        | Delete 1000000 | 539.16500ms  |
        +----------------+--------------+
        
        Relation ``dict : odict``
        
        +---------------------------+----------+
        | creating     1000 objects | 1:73.285 |
        +---------------------------+----------+
        | deleting     1000 objects | 1: 0.967 |
        +---------------------------+----------+
        | creating    10000 objects | 1: 4.173 |
        +---------------------------+----------+
        | deleting    10000 objects | 1: 1.207 |
        +---------------------------+----------+
        | creating   100000 objects | 1: 3.979 |
        +---------------------------+----------+
        | deleting   100000 objects | 1: 1.037 |
        +---------------------------+----------+
        | creating  1000000 objects | 1: 4.020 |
        +---------------------------+----------+
        | deleting  1000000 objects | 1: 1.088 |
        +---------------------------+----------+
        
        Relation ``OrderedDict : odict``
        
        +---------------------------+----------+
        | creating     1000 objects | 1: 5.736 |
        +---------------------------+----------+
        | deleting     1000 objects | 1: 0.703 |
        +---------------------------+----------+
        | creating    10000 objects | 1: 0.262 |
        +---------------------------+----------+
        | deleting    10000 objects | 1: 0.675 |
        +---------------------------+----------+
        | creating   100000 objects | 1: 0.281 |
        +---------------------------+----------+
        | deleting   100000 objects | 1: 0.690 |
        +---------------------------+----------+
        | creating  1000000 objects | 1: 0.317 |
        +---------------------------+----------+
        | deleting  1000000 objects | 1: 0.754 |
        +---------------------------+----------+
        
        
        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.7.x, 3.4+, pypy
        
        - May work with other versions (untested)
        
        
        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>
        
        - Jens Klein <jens@bluedynamics.com>
        
        under the `Python Software Foundation License <http://www.opensource.org/licenses/PythonSoftFoundation.php>`_.
        
        Changes
        =======
        
        1.6.0 (unreleased)
        ------------------
        
        - Compatible with pypy.
          [rnix, 2015-01-03]
        
        - Compatible with Python 3.4, skip compatibility with Python < 2.7.
          [jensens, 2014-11-03]
        
        
        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]
        
        
        1.5.0
        -----
        
        - Implement ``alter_key``.
          [rnix, 2012-05-18]
        
        
        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]
        
        
        1.4.3
        -----
        
        - Get rid of annoying warning about "global" usage in ``bench.py``.
          [jensens, 2011-09-20]
        
        
        1.4.2
        -----
        
        - More ``copy`` testing.
          [rnix, 2010-12-18]
        
        - Add ``has_key`` to odict.
          [rnix, 2010-12-18]
        
        
        1.4.1
        -----
        
        - Fix release, README.rst was missing, added MANIFEST.in file to include it.
          [jensens, 2010-11-29]
        
        
        1.4.0
        -----
        
        - Full test coverage.
          [chaoflow, rnix, 2010-08-17]
        
        - Code cleanup and optimizing.
          [chaoflow, rnix, 2010-08-17]
        
        
        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]
        
        
        1.3.1
        -----
        
        - Add test for bool evaluation.
          [rnix, 2010-04-21]
        
        
        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]
        
        
        1.2.6
        -----
        
        - Make ``odict`` serialize and deserialize properly.
          [gogo, 2010-01-12]
        
        
        1.2.5
        -----
        
        - Add ``as_dict`` function. Supports type conto ordinary ``dict``.
          [rnix, 2009-12-19]
        
        - Add benchmark script.
          [rnix, 2009-12-19]
        
        
        1.2.4
        -----
        
        - Do not check for ``key in self`` on ``__delitem__``, ``KeyError`` is raised
          properly anyway. Huge Speedup!
          [rnix, jensens, 2009-12-18]
        
        
        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]
        
        
        1.2.2
        -----
        
        - Use try/except instead of ``__iter__`` in ``__setitem__`` to determine if
          value was already set.
          [rnix, 2009-07-17]
        
        
        1.2.1
        -----
        
        - Add missing ``__len__`` and ``__contains__`` functions.
          [rnix, 2009-03-17]
        
        
        1.2.0
        -----
        
        - Eggified
          [rnix, 2009-03-17]
        
        
        < 1.2
        -----
        
        - http://code.activestate.com/recipes/498195/
          [bearophile, 2006-10-12]
        
          License
        =======
        
        PYTHON SOFTWARE FOUNDATION LICENSE VERSION 2
        --------------------------------------------
        
        1. This LICENSE AGREEMENT is between the Python Software Foundation
        ("PSF"), and the Individual or Organization ("Licensee") accessing and
        otherwise using this software ("Python") in source or binary form and
        its associated documentation.
        
        2. Subject to the terms and conditions of this License Agreement, PSF
        hereby grants Licensee a nonexclusive, royalty-free, world-wide
        license to reproduce, analyze, test, perform and/or display publicly,
        prepare derivative works, distribute, and otherwise use Python
        alone or in any derivative version, provided, however, that PSF's
        License Agreement and PSF's notice of copyright, i.e., "Copyright (c)
        2001, 2002, 2003, 2004, 2005, 2006 Python Software Foundation; All Rights
        Reserved" are retained in Python alone or in any derivative version
        prepared by Licensee.
        
        3. In the event Licensee prepares a derivative work that is based on
        or incorporates Python or any part thereof, and wants to make
        the derivative work available to others as provided herein, then
        Licensee hereby agrees to include in any such work a brief summary of
        the changes made to Python.
        
        4. PSF is making Python available to Licensee on an "AS IS"
        basis. PSF MAKES NO REPRESENTATIONS OR WARRANTIES, EXPRESS OR
        IMPLIED. BY WAY OF EXAMPLE, BUT NOT LIMITATION, PSF MAKES NO AND
        DISCLAIMS ANY REPRESENTATION OR WARRANTY OF MERCHANTABILITY OR FITNESS
        FOR ANY PARTICULAR PURPOSE OR THAT THE USE OF PYTHON WILL NOT
        INFRINGE ANY THIRD PARTY RIGHTS.
        
        5. PSF SHALL NOT BE LIABLE TO LICENSEE OR ANY OTHER USERS OF PYTHON
        FOR ANY INCIDENTAL, SPECIAL, OR CONSEQUENTIAL DAMAGES OR LOSS AS
        A RESULT OF MODIFYING, DISTRIBUTING, OR OTHERWISE USING PYTHON,
        OR ANY DERIVATIVE THEREOF, EVEN IF ADVISED OF THE POSSIBILITY THEREOF.
        
        6. This License Agreement will automatically terminate upon a material
        breach of its terms and conditions.
        
        7. Nothing in this License Agreement shall be deemed to create any
        relationship of agency, partnership, or joint venture between PSF and
        Licensee. This License Agreement does not grant permission to use PSF
        trademarks or trade name in a trademark sense to endorse or promote
        products or services of Licensee, or any third party.
        
        8. By copying, installing or otherwise using Python, Licensee
        agrees to be bound by the terms and conditions of this License
        Agreement.
        
        
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 :: 2.7
Classifier: Programming Language :: Python :: 3.4
Classifier: Topic :: Software Development
Provides-Extra: test
