.. image:: https://img.shields.io/pypi/v/odict.svg
:target: https://pypi.python.org/pypi/odict
:alt: Latest PyPI version
.. image:: https://img.shields.io/pypi/dm/odict.svg
:target: https://pypi.python.org/pypi/odict
:alt: Number of PyPI downloads
.. image:: https://github.com/conestack/odict/actions/workflows/test.yaml/badge.svg
:target: https://github.com/conestack/odict/actions/workflows/test.yaml
:alt: Test odict
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.
.. code-block:: python
[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.
Motivation
When this package was created, collections.OrderedDict
not existed yet.
Another problem is that dict
cannot always be inherited from in conjunction
with other base classes. This may result in instance layout conflicts or other
errors. So odict
is written in a way that let you alter the dictionary
base implementation.
Usage
Import and create ordered dictionary.
.. code-block:: python
from odict import odict
od = odict()
Custom odict
It is possible to use _odict
base class to implement an ordered dict not
inheriting from dict
type. This is useful i.e. when persisting to ZODB.
Inheriting from dict
and Persistent
at the same time fails. Also,
using a regular list
for the internal double linked list representation
causes problems, so we define a custom class for it as well.
.. code-block:: python
from persistent.dict import PersistentDict
from persistent.list import PersistentList
class podict(_odict, PersistentDict):
def _dict_impl(self):
return PersistentDict
def _list_factory(self):
return PersistentList
Python < 3.7
In Python < 3.7 casting to dict will fail. The reason for this can be found
here <http://bugs.python.org/issue1615701>
_. The __init__
function of
dict checks whether arg is subclass of dict
, and ignores overwritten
__getitem__
& co if so. This was fixed and later reverted due to
behavioural problems with pickle:
.. code-block:: pycon
>>> dict(odict([(1, 1)]))
{1: [nil, 1, nil]}
Use one of the following ways for type conversion.
.. code-block:: pycon
>>> dict(odict([(1, 1)]).items())
{1: 1}
>>> odict([(1, 1)]).as_dict()
{1: 1}
Misc
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.
Python Versions
Contributors
under the Python Software Foundation License <http://www.opensource.org/licenses/PythonSoftFoundation.php>
_.
Changes
1.9.0 (2022-05-15)
-
Add movebefore
, moveafter
, movefirst
and movelast
functions
to odict
.
[rnix]
-
Use first_key
and last_key
in insertfirst
and insertlast
instead of reading all keys.
[rnix]
1.8.1 (2022-03-17)
1.8.0
-
Add next_key
and prev_key
functions.
[rnix]
-
Add first_key
and last_key
properties.
[rnix]
-
Add _list_factory
on _odict
base class. Can be used to alter
the list implementation used for internal value triples.
[rnix]
1.7.0
- Add
swap
, insertbefore
, insertafter
, insertfirst
and
insertlast
functions to odict
.
[rnix]
1.6.2
- Use class name instead of 'odict()' in
__repr__
.
[rnix]
1.6.1
1.6.0
- Compatible with Python 3 and pypy.
[rnix]
1.5.2
- Fix permission problem in 1.5.1 release, some files were only rw by user.
[jensens, 2016-11-25]
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
License
PYTHON SOFTWARE FOUNDATION LICENSE VERSION 2
-
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.
-
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.
-
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.
-
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.
-
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.
-
This License Agreement will automatically terminate upon a material
breach of its terms and conditions.
-
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.
-
By copying, installing or otherwise using Python, Licensee
agrees to be bound by the terms and conditions of this License
Agreement.