{
    "info": {
        "author": "Geert Jansen",
        "author_email": "geertj@gmail.com",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 5 - Production/Stable",
            "License :: OSI Approved :: MIT License",
            "Operating System :: MacOS :: MacOS X",
            "Operating System :: Microsoft :: Windows",
            "Operating System :: POSIX",
            "Programming Language :: Python :: 2.7",
            "Programming Language :: Python :: 3.3",
            "Programming Language :: Python :: 3.4"
        ],
        "description": "Welcome to PySkipList\n=====================\n\n.. image:: https://travis-ci.org/geertj/pyskiplist.svg?branch=master\n    :target: https://travis-ci.org/geertj/pyskiplist\n\n.. image:: https://coveralls.io/repos/geertj/pyskiplist/badge.svg?branch=master\n    :target: https://coveralls.io/r/geertj/pyskiplist\n\nPySkipList is a fast, pure Python implementation of an indexable skiplist. It\nimplements a ``SkipList`` data structure that provides an always sorted,\nlist-like data structure for (key, value) pairs. It efficiently supports the\nfollowing operations:\n\n* Insert a pair in the list, maintaining sorted order.\n* Find the value of a given key.\n* Remove a given pair based on a key.\n* Iterate over all pairs in sorted order.\n* Find the position of a given key.\n* Access a pair at a certain position.\n* Delete a pair at a certain position.\n  \nSince PySkipList is a pure Python implementation, it should work well on\nalternative Python implementations such as PyPy and Jython.\n\n\nExample\n-------\n\nThe following provides a few examples on how to use the ``SkipList`` API::\n\n  >>> from pyskiplist import SkipList\n  >>> sl = SkipList()\n  >>> sl.insert('foo', 'bar')\n  >>> sl.insert('baz', 'qux')\n  >>> sl\n  SkipList((('baz', 'qux'), ('foo', 'bar')))\n  >>> sl.search('foo')\n  'bar'\n  >>> sl[0]\n  ('baz', 'qux')\n  >>> sl.remove('foo')  # remove by key\n  >>> del sl[0]  # remove by position\n\n\nAsymptotic Complexity\n---------------------\n\nBelow are the Big-O complexities of the various operations implemented by\npyskiplist:\n\n==================  ==========\nOperation           Complexity\n==================  ==========\ninsertion           O(log N)\nsearch by key       O(log N)\nremoval by key      O(log N) \nforward iteration   O(1)\nfind by position    O(log N)\naccess by position  O(log N)\ndelete by position  O(log N)\n==================  ==========\n\n\nPerformance\n-----------\n\nBelow are the results of some performance tests. These are for Python 3.4.2 on\nmy Linux laptop:\n\n===================  ===================\nTest                 Operations / second\n===================  ===================\nInsert @ 1k nodes    45,056\nInsert @ 10k nodes   42,137\nInsert @ 100k nodes  28,086\nRemove @ 1k nodes    54,316\nRemove @ 10k nodes   46,240\nRemove @ 100k nodes  35,114\nSearch @ 1k nodes    137,248\nSearch @ 10k nodes   109,480\nSearch @ 100k nodes  77,939\n===================  ===================\n\n\nMemory usage\n------------\n\nPySkipList tries to be efficient with regards to memory usage. The numbers\nbelow are for Python 3.4.2 on my Linux laptop. This specific test stores pairs\nof integer keys and an integer values in a skiplist. The total size of the two\nintegers on this Python version is 56 bytes.\n\n=====  ============  =================\nNodes  Bytes / node  Overhead (fixed)\n=====  ============  =================\n1k     164           108\n10k    162           106\n100k   162           106\n=====  ============  =================\n\n\nImplementation notes\n--------------------\n\nReference papers on skiplists:\n\n* ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf (original paper)\n* http://drum.lib.umd.edu/bitstream/1903/544/2/CS-TR-2286.1.pdf (cookbook)\n\nThis implementation uses a novel (as far as I know) technique where it stores\njust a single link width per node, and only in nodes with level > 0. The link\ncorresponds to the number of nodes skipped by the highest incoming link. Other\nimplementations that I've seen all store a width for every link. This approach\nsaves a lot of memory. The overhead should just be 1/e (0.37) integers per\nnode. It makes an indexable skiplist almost as memory efficient as its\nnon-indexable cousin.\n\nDuplicate keys are allowed in this implementation, and insertion order is\nmaintained.\n\nSkiplist nodes are implemented as plain lists instead of objects. This saves\nmemory. Kudos to http://pythonsweetness.tumblr.com/post/45227295342 for the\nidea.\n\nThe built-in Mersenne Twister is used as the random source. This is preferable\nover SystemRandom since it doesn't require a system call and there is no need\nfor cryptographically secure numbers.\n",
        "description_content_type": null,
        "docs_url": null,
        "download_url": null,
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/geertj/pyskiplist",
        "keywords": null,
        "license": "MIT",
        "maintainer": null,
        "maintainer_email": null,
        "name": "pyskiplist",
        "package_url": "https://pypi.org/project/pyskiplist/",
        "platform": "UNKNOWN",
        "project_url": "https://pypi.org/project/pyskiplist/",
        "project_urls": {
            "Homepage": "https://github.com/geertj/pyskiplist"
        },
        "release_url": "https://pypi.org/project/pyskiplist/1.0.0/",
        "requires_dist": null,
        "requires_python": null,
        "summary": "Fast, pure Python indexable skip list",
        "version": "1.0.0"
    },
    "last_serial": 1609610,
    "releases": {
        "1.0.0": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "af517550031d59489edaf3161d39209c",
                    "sha256": "5fba901abf577538f4e97e909a1b629c63550cef8c9205c2414c822a3fc7a458"
                },
                "downloads": -1,
                "filename": "pyskiplist-1.0.0-py2.py3-none-any.whl",
                "has_sig": false,
                "md5_digest": "af517550031d59489edaf3161d39209c",
                "packagetype": "bdist_wheel",
                "python_version": "py2.py3",
                "requires_python": null,
                "size": 8580,
                "upload_time": "2015-06-27T23:51:16",
                "url": "https://files.pythonhosted.org/packages/31/db/576c89e0f78a7b29d62633548edf7ef871f3dc62d680a315e4f49d06f0db/pyskiplist-1.0.0-py2.py3-none-any.whl"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "bfee80f564d04937315dd6cbce9c75f7",
                    "sha256": "2296f67e6591e01c57ea1837aa7ae722fa8f4701a38069cc33ffd3e56d807ffa"
                },
                "downloads": -1,
                "filename": "pyskiplist-1.0.0.tar.gz",
                "has_sig": false,
                "md5_digest": "bfee80f564d04937315dd6cbce9c75f7",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 7999,
                "upload_time": "2015-06-27T23:51:20",
                "url": "https://files.pythonhosted.org/packages/eb/93/8263fe0e391f65f9a9ade497ff9a165f4fc9559a84aa3db15190a85e768b/pyskiplist-1.0.0.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "af517550031d59489edaf3161d39209c",
                "sha256": "5fba901abf577538f4e97e909a1b629c63550cef8c9205c2414c822a3fc7a458"
            },
            "downloads": -1,
            "filename": "pyskiplist-1.0.0-py2.py3-none-any.whl",
            "has_sig": false,
            "md5_digest": "af517550031d59489edaf3161d39209c",
            "packagetype": "bdist_wheel",
            "python_version": "py2.py3",
            "requires_python": null,
            "size": 8580,
            "upload_time": "2015-06-27T23:51:16",
            "url": "https://files.pythonhosted.org/packages/31/db/576c89e0f78a7b29d62633548edf7ef871f3dc62d680a315e4f49d06f0db/pyskiplist-1.0.0-py2.py3-none-any.whl"
        },
        {
            "comment_text": "",
            "digests": {
                "md5": "bfee80f564d04937315dd6cbce9c75f7",
                "sha256": "2296f67e6591e01c57ea1837aa7ae722fa8f4701a38069cc33ffd3e56d807ffa"
            },
            "downloads": -1,
            "filename": "pyskiplist-1.0.0.tar.gz",
            "has_sig": false,
            "md5_digest": "bfee80f564d04937315dd6cbce9c75f7",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 7999,
            "upload_time": "2015-06-27T23:51:20",
            "url": "https://files.pythonhosted.org/packages/eb/93/8263fe0e391f65f9a9ade497ff9a165f4fc9559a84aa3db15190a85e768b/pyskiplist-1.0.0.tar.gz"
        }
    ]
}