indexed.IndexedOrderedDict: a dictionary that is indexed by insertion order
===========================================================================
.. image:: https://github.com/niklasf/indexed.py/actions/workflows/test.yml/badge.svg
:target: https://github.com/niklasf/indexed.py/actions/workflows/test.yml
:alt: Test
.. image:: https://badge.fury.io/py/indexed.svg
:target: https://pypi.python.org/pypi/indexed
:alt: PyPI package
Introduction
------------
``indexed.IndexedOrderedDict`` (alias ``indexed.Dict``) is feature compatible
with ``collections.OrderedDict`` as of Python 3.11 and can be used as
a drop in replacement.
The main difference is that key, value and item views support accessing
elements by their index.
.. code-block:: python
d = indexed.IndexedOrderedDict()
d["first-key"] = "first-value"
d["second-key"] = "second-value"
d["third-key"] = "third-value"
values = d.values()
assert values[2] == "third-value"
assert d.keys().index("second-key") == 1
Features
--------
* Access keys, values and items by index, e.g., ``d.keys()[5]``.
* Find the index of a key, e.g., ``d.keys().index("key")``.
* Sort keys in place, e.g., ``d.sort()``.
Excluding those additions the API is the same as the API of
``collections.OrderedDict()``.
Installing
----------
::
pip install indexed
Performance
-----------
Performance is practically on the same order of magnitude as the built in
``collections.OrderedDict``, with exceptions in bold:
================= ========== ================== ======== ======================
d ``collections.OrderedDict`` ``indexed.IndexedOrderedDict``
----------------- ----------------------------- -------------------------------
Operation Avergage Worst case Average Worst case
================= ========== ================== ======== ======================
d.copy() O(n) O(n) O(n) O(n)
----------------- ---------- ------------------ -------- ----------------------
d[key] O(1) O(n) O(1) O(n)
----------------- ---------- ------------------ -------- ----------------------
d[key] = value O(1) O(n) [#a]_ O(1) O(n) [#a]_
----------------- ---------- ------------------ -------- ----------------------
del d[key] **O(1)** O(n) O(n) O(n)
----------------- ---------- ------------------ -------- ----------------------
d.keys()[i] O(n) [#k]_ O(n) [#k]_ **O(1)** **O(1)**
----------------- ---------- ------------------ -------- ----------------------
d.values()[i] O(n) [#v]_ O(n) [#v]_ **O(1)** O(n)
----------------- ---------- ------------------ -------- ----------------------
d.items()[i] O(n) [#v]_ O(n) [#v]_ **O(1)** O(n)
----------------- ---------- ------------------ -------- ----------------------
d.keys().index(x) O(n) [#v]_ O(n) [#v]_ O(n) O(n)
================= ========== ================== ======== ======================
.. [#a] These are amortized_ worst case runtimes.
.. [#k] This does not work in Python 3 because ``colections.KeysView`` is not
indexable. One of the theoretically best work arounds is
``next(itertools.islice(d.keys(), i, i + 1))``.
.. [#v] Assuming the theoretically best possible workaround.
License
-------
This library is derived from CPython's ``collections.OrderedDict``
and licensed under the PSFL.
See the LICENSE file for the full license text.
.. _amortized: http://en.wikipedia.org/wiki/Amortized_analysis
Raw data
{
"_id": null,
"home_page": "http://github.com/niklasf/indexed.py",
"name": "indexed",
"maintainer": "",
"docs_url": null,
"requires_python": "",
"maintainer_email": "",
"keywords": "",
"author": "Niklas Fiekas",
"author_email": "niklas.fiekas@backscattering.de",
"download_url": "https://files.pythonhosted.org/packages/07/91/ebbff25d520fd4c904fcec67a1e4800c6e37c17f4c64057693e38aa2455b/indexed-1.3.0.tar.gz",
"platform": null,
"description": "indexed.IndexedOrderedDict: a dictionary that is indexed by insertion order\n===========================================================================\n\n.. image:: https://github.com/niklasf/indexed.py/actions/workflows/test.yml/badge.svg\n :target: https://github.com/niklasf/indexed.py/actions/workflows/test.yml\n :alt: Test\n\n.. image:: https://badge.fury.io/py/indexed.svg\n :target: https://pypi.python.org/pypi/indexed\n :alt: PyPI package\n\nIntroduction\n------------\n\n``indexed.IndexedOrderedDict`` (alias ``indexed.Dict``) is feature compatible\nwith ``collections.OrderedDict`` as of Python 3.11 and can be used as\na drop in replacement.\nThe main difference is that key, value and item views support accessing\nelements by their index.\n\n.. code-block:: python\n\n d = indexed.IndexedOrderedDict()\n d[\"first-key\"] = \"first-value\"\n d[\"second-key\"] = \"second-value\"\n d[\"third-key\"] = \"third-value\"\n\n values = d.values()\n assert values[2] == \"third-value\"\n\n assert d.keys().index(\"second-key\") == 1\n\nFeatures\n--------\n\n* Access keys, values and items by index, e.g., ``d.keys()[5]``.\n\n* Find the index of a key, e.g., ``d.keys().index(\"key\")``.\n\n* Sort keys in place, e.g., ``d.sort()``.\n\nExcluding those additions the API is the same as the API of\n``collections.OrderedDict()``.\n\nInstalling\n----------\n\n::\n\n pip install indexed\n\n\nPerformance\n-----------\n\nPerformance is practically on the same order of magnitude as the built in\n``collections.OrderedDict``, with exceptions in bold:\n\n================= ========== ================== ======== ======================\nd ``collections.OrderedDict`` ``indexed.IndexedOrderedDict``\n----------------- ----------------------------- -------------------------------\nOperation Avergage Worst case Average Worst case\n================= ========== ================== ======== ======================\nd.copy() O(n) O(n) O(n) O(n) \n----------------- ---------- ------------------ -------- ----------------------\nd[key] O(1) O(n) O(1) O(n)\n----------------- ---------- ------------------ -------- ----------------------\nd[key] = value O(1) O(n) [#a]_ O(1) O(n) [#a]_\n----------------- ---------- ------------------ -------- ----------------------\ndel d[key] **O(1)** O(n) O(n) O(n)\n----------------- ---------- ------------------ -------- ----------------------\nd.keys()[i] O(n) [#k]_ O(n) [#k]_ **O(1)** **O(1)**\n----------------- ---------- ------------------ -------- ----------------------\nd.values()[i] O(n) [#v]_ O(n) [#v]_ **O(1)** O(n)\n----------------- ---------- ------------------ -------- ----------------------\nd.items()[i] O(n) [#v]_ O(n) [#v]_ **O(1)** O(n)\n----------------- ---------- ------------------ -------- ----------------------\nd.keys().index(x) O(n) [#v]_ O(n) [#v]_ O(n) O(n)\n================= ========== ================== ======== ======================\n\n.. [#a] These are amortized_ worst case runtimes.\n.. [#k] This does not work in Python 3 because ``colections.KeysView`` is not\n indexable. One of the theoretically best work arounds is\n ``next(itertools.islice(d.keys(), i, i + 1))``.\n.. [#v] Assuming the theoretically best possible workaround.\n\nLicense\n-------\n\nThis library is derived from CPython's ``collections.OrderedDict``\nand licensed under the PSFL.\nSee the LICENSE file for the full license text.\n\n.. _amortized: http://en.wikipedia.org/wiki/Amortized_analysis\n",
"bugtrack_url": null,
"license": "PSFL",
"summary": "A dictionary that is indexed by insertion order.",
"version": "1.3.0",
"split_keywords": [],
"urls": [
{
"comment_text": "",
"digests": {
"blake2b_256": "628be5c5af4bb7f87409afd3addd3612bc471b2e141987d3edf64c7693cae7c4",
"md5": "dbf36950704c2e4cd1a63ee5233d43d0",
"sha256": "a35db8644bef9273be710f5f06b5ffe71b8699d9212593cbae422b5e3c5f64c6"
},
"downloads": -1,
"filename": "indexed-1.3.0-py3-none-any.whl",
"has_sig": true,
"md5_digest": "dbf36950704c2e4cd1a63ee5233d43d0",
"packagetype": "bdist_wheel",
"python_version": "py3",
"requires_python": null,
"size": 5619,
"upload_time": "2022-10-26T20:53:06",
"upload_time_iso_8601": "2022-10-26T20:53:06.536567Z",
"url": "https://files.pythonhosted.org/packages/62/8b/e5c5af4bb7f87409afd3addd3612bc471b2e141987d3edf64c7693cae7c4/indexed-1.3.0-py3-none-any.whl",
"yanked": false,
"yanked_reason": null
},
{
"comment_text": "",
"digests": {
"blake2b_256": "0791ebbff25d520fd4c904fcec67a1e4800c6e37c17f4c64057693e38aa2455b",
"md5": "ec17f5f3d2d10cbf84a729ea4363c195",
"sha256": "6a0dd1f164db2eef6f9983bf1c5302d4b250a05b784f15c4c3f436d8778243d9"
},
"downloads": -1,
"filename": "indexed-1.3.0.tar.gz",
"has_sig": true,
"md5_digest": "ec17f5f3d2d10cbf84a729ea4363c195",
"packagetype": "sdist",
"python_version": "source",
"requires_python": null,
"size": 5458,
"upload_time": "2022-10-26T20:53:09",
"upload_time_iso_8601": "2022-10-26T20:53:09.176315Z",
"url": "https://files.pythonhosted.org/packages/07/91/ebbff25d520fd4c904fcec67a1e4800c6e37c17f4c64057693e38aa2455b/indexed-1.3.0.tar.gz",
"yanked": false,
"yanked_reason": null
}
],
"upload_time": "2022-10-26 20:53:09",
"github": true,
"gitlab": false,
"bitbucket": false,
"github_user": "niklasf",
"github_project": "indexed.py",
"travis_ci": false,
"coveralls": false,
"github_actions": true,
"tox": true,
"lcname": "indexed"
}
JSON
