{
    "info": {
        "author": "Deterministic Arts",
        "author_email": "contact@deterministic-arts.de",
        "bugtrack_url": null,
        "classifiers": [],
        "description": "LRU Dictionaries\r\n=================\r\n\r\n    >>> from darts.lib.utils.lru import LRUDict\r\n\r\nAn `LRUDict` is basically a simple dictionary, which has a defined\r\nmaximum capacity, that may be supplied at construction time, or modified\r\nat run-time via the `capacity` property::\r\n\r\n    >>> cache = LRUDict(1)\r\n    >>> cache.capacity\r\n    1\r\n\r\nThe minimum capacity value is 1, and LRU dicts will complain, if someone\r\nattempts to use a value smaller than that::\r\n\r\n    >>> cache.capacity = -1                              #doctest: +ELLIPSIS\r\n    Traceback (most recent call last):\r\n    ...\r\n    ValueError: -1 is not a valid capacity\r\n    >>> LRUDict(-1)                                      #doctest: +ELLIPSIS\r\n    Traceback (most recent call last):\r\n    ...\r\n    ValueError: -1 is not a valid capacity\r\n\r\nLRU dictionaries can never contain more elements than their capacity value\r\nindicates, so::\r\n\r\n    >>> cache[1] = \"First\"\r\n    >>> cache[2] = \"Second\"\r\n    >>> len(cache)\r\n    1\r\n\r\nIn order to ensure this behaviour, the dictionary will evict entries if\r\nit needs to make room for new ones. So::\r\n\r\n    >>> 1 in cache\r\n    False\r\n    >>> 2 in cache\r\n    True\r\n\r\nThe capacity can be adjusted at run-time. Growing the capacity does not\r\naffect the number of elements present in an LRU dictionary::\r\n\r\n    >>> cache.capacity = 3\r\n    >>> len(cache)\r\n    1\r\n    >>> cache[1] = \"First\"\r\n    >>> cache[3] = \"Third\"\r\n    >>> len(cache)\r\n    3\r\n\r\nbut shrinking does::\r\n\r\n    >>> cache.capacity = 2\r\n    >>> len(cache)\r\n    2\r\n    >>> sorted(list(cache.iterkeys()))\r\n    [1, 3]\r\n\r\nNote, that the entry with key `2` was evicted, because it was the oldest\r\nentry at the time of the modification of `capacity`. The new oldest entry\r\nis the one with key `1`, which can be seen, when we try to add another\r\nentry to the dict::\r\n\r\n    >>> cache[4] = \"Fourth\"\r\n    >>> sorted(list(cache.iterkeys()))\r\n    [3, 4]\r\n\r\nThe following operations affect an entry's priority::\r\n\r\n- `get`\r\n- `__getitem__`\r\n- `__setitem__`\r\n- `__contains__`\r\n\r\nCalling any of these operations on an existing key will boost the key's\r\npriority, making it more unlikely to get evicted, when the dictionary needs\r\nto make room for new entries. There is a special `peek` operation, which\r\nreturns the current value associated to a key without boosting the priority\r\nof the entry::\r\n\r\n    >>> cache.peek(3)\r\n    'Third'\r\n    >>> cache[5] = \"Fifth\"\r\n    >>> sorted(list(cache.iterkeys()))\r\n    [4, 5]\r\n\r\nAs you can see, even though we accessed the entry with key `3` as the last\r\none, the entry is now gone, because it did not get a priority boost from \r\nthe call to `peek`.\r\n\r\nThe class `LRUDict` supports a subset of the standard Python `dict` \r\ninterface. In particular, we can iterate over the key, values, and \r\nitems of an LRU dict::\r\n\r\n    >>> sorted([k for k in cache.iterkeys()])\r\n    [4, 5]\r\n    >>> sorted([v for v in cache.itervalues()])\r\n    ['Fifth', 'Fourth']\r\n    >>> sorted([p for p in cache.iteritems()])\r\n    [(4, 'Fourth'), (5, 'Fifth')]\r\n    >>> sorted(list(cache))\r\n    [4, 5]\r\n\r\nNote, that there is no guaranteed order; in particular, the elements are \r\nnot generated in priority order or somesuch. Similar to regular `dict`s,\r\nan LRU dict's `__iter__` is actually any alias for `iterkeys`.\r\n\r\nFurthermore, we can remove all elements from the dict:\r\n\r\n    >>> cache.clear()\r\n    >>> sorted(list(cache.iterkeys()))\r\n    []\r\n\r\n\r\nThread-safety\r\n--------------\r\n\r\nInstances of class `LRUDict` are not thread safe. Worse: even concurrent\r\nread-only access is not thread-safe and has to be synchronized by the\r\nclient application.\r\n\r\nThere is, however, the class `SynchronizedLRUDict`, which exposes the\r\nsame interface as plain `LRUDict`, but fully thread-safe. The following \r\nsession contains exactly the steps, we already tried with a plain `LRUDict`, \r\nbut now using the synchronized version::\r\n\r\n    >>> from darts.lib.utils.lru import SynchronizedLRUDict\r\n    >>> cache = SynchronizedLRUDict(1)\r\n    >>> cache.capacity\r\n    1\r\n    >>> cache.capacity = -1                              #doctest: +ELLIPSIS\r\n    Traceback (most recent call last):\r\n    ...\r\n    ValueError: -1 is not a valid capacity\r\n    >>> LRUDict(-1)                                      #doctest: +ELLIPSIS\r\n    Traceback (most recent call last):\r\n    ...\r\n    ValueError: -1 is not a valid capacity\r\n    >>> cache[1] = \"First\"\r\n    >>> cache[2] = \"Second\"\r\n    >>> len(cache)\r\n    1\r\n    >>> 1 in cache\r\n    False\r\n    >>> 2 in cache\r\n    True\r\n    >>> cache.capacity = 3\r\n    >>> len(cache)\r\n    1\r\n    >>> cache[1] = \"First\"\r\n    >>> cache[3] = \"Third\"\r\n    >>> len(cache)\r\n    3\r\n    >>> cache.capacity = 2\r\n    >>> len(cache)\r\n    2\r\n    >>> sorted(list(cache.iterkeys()))\r\n    [1, 3]\r\n    >>> cache[4] = \"Fourth\"\r\n    >>> sorted(list(cache.iterkeys()))\r\n    [3, 4]\r\n    >>> cache.peek(3)\r\n    'Third'\r\n    >>> cache[5] = \"Fifth\"\r\n    >>> sorted(list(cache.iterkeys()))\r\n    [4, 5]\r\n    >>> sorted([k for k in cache.iterkeys()])\r\n    [4, 5]\r\n    >>> sorted([v for v in cache.itervalues()])\r\n    ['Fifth', 'Fourth']\r\n    >>> sorted([p for p in cache.iteritems()])\r\n    [(4, 'Fourth'), (5, 'Fifth')]\r\n    >>> sorted(list(cache))\r\n    [4, 5]\r\n    >>> cache.clear()\r\n    >>> sorted(list(cache.iterkeys()))\r\n    []\r\n\r\n\r\nAuto-loading Caches\r\n====================\r\n\r\nHaving some kind of dictionary which is capable of cleaning itself\r\nup is nice, but in order to implement caching, there is still something\r\nmissing: the mechanism, which actually loads something into our dict.\r\nThis part of the story is implemented by the `AutoLRUCache`::\r\n\r\n    >>> from darts.lib.utils.lru import AutoLRUCache\r\n\r\nLet's first define a load function::\r\n\r\n    >>> def load_resource(key):\r\n    ...    if key < 10:\r\n    ...        print \"Loading %r\" % (key,)\r\n    ...        return \"R(%s)\" % (key,)\r\n\r\nand a cache::\r\n\r\n    >>> cache = AutoLRUCache(load_resource, capacity=3)\r\n    >>> cache.load(1)\r\n    Loading 1\r\n    'R(1)'\r\n    >>> cache.load(1)\r\n    'R(1)'\r\n\r\nAs you can see, the first time, an actual element is loaded, the load\r\nfunction provided to the constructor is called, in order to provide the\r\nactual resource value. On subsequent calls to `load`, the cached value\r\nis returned.\r\n\r\nInternally, the `AutoLRUCache` class uses an `LRUDict` to cache values,\r\nso::\r\n\r\n    >>> cache.load(2)\r\n    Loading 2\r\n    'R(2)'\r\n    >>> cache.load(3)\r\n    Loading 3\r\n    'R(3)'\r\n    >>> cache.load(4)\r\n    Loading 4\r\n    'R(4)'\r\n    >>> cache.load(1)\r\n    Loading 1\r\n    'R(1)'\r\n\r\nNote the \"Loading 1\" line in the last example. The cache has been initialized\r\nwith a capacity of 3, so the value of key `1` had to be evicted when the one\r\nfor key `4` was loaded. When we tried to obtain `1` again, the cache had to\r\nproperly reload it, calling the loader function.\r\n\r\nIf there is actually no resource for a given key value, the loader function\r\nmust return `None`. It follows, that `None` is never a valid resource value\r\nto be associated with some key in an `AutoLRUCache`.\r\n\r\n    >>> cache.load(11, 'Oops')\r\n    'Oops'\r\n\r\n\r\nThread-safety\r\n--------------\r\n\r\nInstances of class `AutoLRUCache` are fully thread safe. Be warned, though,\r\nthat the loader function is called outside of any synchronization scope the\r\nclass may internally use, and has to provide its own synchronization if \r\nrequired.\r\n\r\nThe cache class actually tries to minimize the number of invocations of the\r\nloader by making sure, that no two concurrent threads will try to load the\r\nsame key value (though any number of concurrent threads might be busy loading\r\nthe resources associated with different keys).\r\n\r\n\r\nCaching and stale entries\r\n==========================\r\n\r\nThere is another `AutoLRUCache`-like class provided by the LRU module,\r\nwhich gives more control over timing out of entries than `AutoLRUCache` does.\r\n\r\n\r\n    >>> from darts.lib.utils.lru import DecayingLRUCache\r\n    >>> current_time = 0\r\n    >>> def tick():\r\n    ...     global current_time\r\n    ...     current_time += 1\r\n\r\nHere, we defined a simple \"clock\". We could have used the system clock,\r\nbut roling our own here gives us more control over the notion of \"time\".\r\nNow, let's define a simple cache entry:\r\n\r\n    >>> from collections import namedtuple\r\n    >>> Entry = namedtuple(\"Entry\", \"timestamp payload\")\r\n    >>> def make_entry(payload):\r\n    ...     return Entry(current_time, payload)\r\n\r\nand a loader function\r\n\r\n    >>> def load(full_key):\r\n    ...     print \"Loading\", full_key\r\n    ...     return make_entry(u\"Entry for %r\" % (full_key,))\r\n\r\nFor the following parts, we consider an entry to be \"too old\", if it has\r\nbeen created more then two \"ticks\" ago:\r\n\r\n    >>> def is_still_current(entry):\r\n    ...    return current_time - entry.timestamp <= 2\r\n\r\nFinally, we create another cache thingy\r\n\r\n    >>> cache = DecayingLRUCache(load, tester=is_still_current, capacity=3)\r\n\r\nThe `DecayingLRUCache` shows much of the same behaviour of the `AutoLRUCache`,\r\nnamely:\r\n\r\n    >>> cache.load(1)\r\n    Loading 1\r\n    Entry(timestamp=0, payload=u'Entry for 1')\r\n    >>> cache.load(2)\r\n    Loading 2\r\n    Entry(timestamp=0, payload=u'Entry for 2')\r\n    >>> cache.load(3)\r\n    Loading 3\r\n    Entry(timestamp=0, payload=u'Entry for 3')\r\n    >>> cache.load(4)\r\n    Loading 4\r\n    Entry(timestamp=0, payload=u'Entry for 4')\r\n    >>> cache.load(1)\r\n    Loading 1\r\n    Entry(timestamp=0, payload=u'Entry for 1')\r\n    \r\nThe entry with key `1` had to be reloaded, since the cache has a capacity of\r\n3, and the old entry for `1` was evicted when the entry for `4` was loaded\r\nand we needed to make room.\r\n\r\n    >>> cache.load(3)\r\n    Entry(timestamp=0, payload=u'Entry for 3')\r\n\r\nNow, let's advance time\r\n\r\n    >>> tick()\r\n    >>> cache.load(3)\r\n    Entry(timestamp=0, payload=u'Entry for 3')\r\n\r\nThe entry is still available. \r\n\r\n    >>> tick()\r\n    >>> cache.load(3)\r\n    Entry(timestamp=0, payload=u'Entry for 3')\r\n    >>> tick()\r\n    >>> cache.load(3)\r\n    Loading 3\r\n    Entry(timestamp=3, payload=u'Entry for 3')\r\n\r\nNote, that eviction is still based on LRU, not on the age test. \r\n\r\n\r\nChange Log\r\n==========\r\n\r\nVersion 0.5\r\n------------\r\n\r\nAdded a \"from __future__ import with_statement\" for Python 2.5 compatibility.\r\nNote, that supporting py2.5 is not a real goal, and I did not test the code\r\nusing that version.\r\n\r\nVersion 0.4\r\n------------\r\n\r\nAdded class `DecayingLRUCache` \r\n\r\nVersion 0.3\r\n------------\r\n\r\nAdded class `SynchronizedLRUDict` as thread-safe counterpart for `LRUDict`.",
        "description_content_type": null,
        "docs_url": "https://pythonhosted.org/darts.util.lru/",
        "download_url": "UNKNOWN",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://github.com/deterministic-arts/DartsPyLRU",
        "keywords": "",
        "license": "MIT",
        "maintainer": "",
        "maintainer_email": "",
        "name": "darts.util.lru",
        "package_url": "https://pypi.org/project/darts.util.lru/",
        "platform": "UNKNOWN",
        "project_url": "https://pypi.org/project/darts.util.lru/",
        "project_urls": {
            "Download": "UNKNOWN",
            "Homepage": "https://github.com/deterministic-arts/DartsPyLRU"
        },
        "release_url": "https://pypi.org/project/darts.util.lru/0.5/",
        "requires_dist": null,
        "requires_python": null,
        "summary": "Simple dictionary with LRU behaviour",
        "version": "0.5"
    },
    "last_serial": 815737,
    "releases": {
        "0.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "78c18d4d8b9651729b6e584bcf88ebd6",
                    "sha256": "e0fbd4052addabc3f95b3eb720df9ebe49235c854a69b6755f50fd323570461e"
                },
                "downloads": -1,
                "filename": "darts.util.lru-0.1.tar.gz",
                "has_sig": false,
                "md5_digest": "78c18d4d8b9651729b6e584bcf88ebd6",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 8811,
                "upload_time": "2011-01-19T16:09:29",
                "url": "https://files.pythonhosted.org/packages/11/58/8d874cc058740fedba476f65535664912b26b4704c5fb26f66eebe33a08b/darts.util.lru-0.1.tar.gz"
            }
        ],
        "0.2": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "f60844ac4c7f488d9bbfc906531574cb",
                    "sha256": "2ab428efeccb6a5420e41f32ee5ee144ed5452fd6cfef48417838c64b02773e4"
                },
                "downloads": -1,
                "filename": "darts.util.lru-0.2.tar.gz",
                "has_sig": false,
                "md5_digest": "f60844ac4c7f488d9bbfc906531574cb",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 8902,
                "upload_time": "2011-01-19T16:31:46",
                "url": "https://files.pythonhosted.org/packages/fe/d7/5581cc3661f6a6772031932c7b630671dfb7db4ece2545b81bd0c6aeb81e/darts.util.lru-0.2.tar.gz"
            }
        ],
        "0.3": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "51e2d3b961e11eb37aaf311dec3f9c5c",
                    "sha256": "c57325a39acb845266ac6f414a38c289ea42e1c8d95d35f1db488c74ac701eda"
                },
                "downloads": -1,
                "filename": "darts.util.lru-0.3.tar.gz",
                "has_sig": false,
                "md5_digest": "51e2d3b961e11eb37aaf311dec3f9c5c",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 17512,
                "upload_time": "2011-02-28T15:37:16",
                "url": "https://files.pythonhosted.org/packages/aa/15/8e7db709367cedf9f12bdef6c190af0152205d3540d71655a4dc04efd2c7/darts.util.lru-0.3.tar.gz"
            }
        ],
        "0.4": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "c73f56b171c01c6669479f9141a99955",
                    "sha256": "bcd7b6db23b002e35d0bdcc007aa54b01bb612067d9127819710df6618cb9651"
                },
                "downloads": -1,
                "filename": "darts.util.lru-0.4.tar.gz",
                "has_sig": false,
                "md5_digest": "c73f56b171c01c6669479f9141a99955",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 11648,
                "upload_time": "2013-03-25T11:33:03",
                "url": "https://files.pythonhosted.org/packages/a0/4d/61a2145ee267b005df86d103883e45e55c121dde8a2ee17eee884bcef9b9/darts.util.lru-0.4.tar.gz"
            },
            {
                "comment_text": "",
                "digests": {
                    "md5": "5c776e755a4d8dea134e7fa2050882b3",
                    "sha256": "58c50fea1e2f7a6419964781c78a77452012ab71a32d81796e2038e99a38488a"
                },
                "downloads": -1,
                "filename": "darts.util.lru-0.5.tar.gz",
                "has_sig": false,
                "md5_digest": "5c776e755a4d8dea134e7fa2050882b3",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 11765,
                "upload_time": "2013-07-15T12:08:33",
                "url": "https://files.pythonhosted.org/packages/8d/dd/cb3dba7d0217fb0e14924a042abed19268c4aac3d721b5aa75fe249a06e1/darts.util.lru-0.5.tar.gz"
            }
        ],
        "0.5": []
    },
    "urls": []
}