{
    "info": {
        "author": "Dieter Maurer",
        "author_email": "dieter@handshake.de",
        "bugtrack_url": null,
        "classifiers": [
            "Development Status :: 5 - Production/Stable",
            "Framework :: ZODB",
            "Intended Audience :: Developers",
            "License :: OSI Approved :: BSD License",
            "Operating System :: OS Independent",
            "Programming Language :: C",
            "Programming Language :: Python",
            "Programming Language :: Python :: 2.7",
            "Programming Language :: Python :: 3",
            "Programming Language :: Python :: Implementation :: CPython",
            "Topic :: Utilities"
        ],
        "description": "dm.incrementalsearch\n====================\n\n``dm.incrementalsearch`` is an efficient low level search execution engine.\nIts primary purpose is to incrementally perform searches involving\n``and``, ``or`` and ``not`` queries over ``ZODB.BTrees``.\n\nIncrementally means here\nthat hits are determined one at a time: the first hit, then the second hit,\nthen the third hit, etc. Therefore, the first few hits can be determined\nextremely fast. But even if all hits need to be determined, the\nincremental execution of subqueries can lead to speedups of several orders\nfor some query types (especially those dominated by specific ``and`` queries).\n\nQueries involving large ``or`` subqueries are difficult to optimize\nin the standard way. But often they can be replaced by incremental\nfiltering. With this technique, a subquery is removed from the\noriginal search, the modified search executed and the result filtered\nby the removed subquery. ``incrementalsearch`` supports incremental filtering\nand thereby can again gain serveral orders of speedup for otherwise\ndifficult to treat query types.\n\nThe primary concept is that of an ``ISearch`` (incremental search).\nThis is conceptionally a sorted list, computed incrementally\n(or lazily). The elements of this list are the ``ISearch``'s hits.\nThe ``ISearch``'s ``keytype`` determines the type of the list\nelements. Currently supported are ``OBJECT`` (comparable Python objects),\n``INT`` (Python 32 bit integers) and ``LONG`` (Python 64 bit integers).\n\nExample usage\n-------------\n``incrementalsearch`` is rarely used directly but usually indirectly\nvia a higher level search engine such as ``Products.AdvancedQuery``.\nLet's nevertheless look at some examples.\n\nAssume we want to find elements available in each of a sequence\nof integer BTrees ``seq_btrees``. I.e. we are interested in elements contained\nin the intersection of these BTrees.\n\n>>> from dm.incrementalsearch import IBTree, IAnd_int, Unspecified, \\\n...     AT_END, INLIST_SUCCESS\n\nWe transform the BTrees into incrementally searchable objects by\napplying the ``IBTree`` operator (Incremental BTree). Then\nwe combine them by ``IAnd_int`` and indicate that no more searches\nwill be added by calling ``complete``. This causes several optimizations\nto take place.\n\n>>> isearch = IAnd_int(*map(IBTree, seq_btrees))\n>>> isearch.complete()\n\nAn ``ISearch`` has attributes ``value`` (the current value) and ``classification``\n(it indicates whether the current value is a hit and whether there may be\nmore values) and methods ``advanceFrom`` and ``advanceTo`` to move forward\nin the search. To determine the first hit, we can use:\n\n>>> cl = isearch.advanceFrom(Unspecified, Unspecified)\n>>> if cl != AT_END:\n...     first_hit = isearch.value\n\nThe next hit is determined by\n\n>>> cl = isearch.advanceFrom(isearch.value, Unspecified)\n>>> if cl != AT_END:\n...     next_hit = isearch.value\n\nIf we know that hits at or below 1000 are irrelevant, we can use\n\n>>> cl = isearch.advanceFrom(1000, Unspecified)\n>>> if cl != AT_END:\n...     hit_above_1000 = isearch.value\n\nWe can also indicate that we are interested only in hits below\nsome upper value.\n\n>>> cl = isearch.advanceFrom(2000, 10000)\n>>> if cl == INLIST_SUCCESS:\n...     hit_above_2000_below_10000 = isearch.value\n\nWe can use the ``asSet`` method to obtain all hits\nas a (BTree) set. ``asSet`` should only be called on fresh, i.e. (as yet)\nunadvanced isearches (we may remove this restriction later, if there\nis a need to).\n\n>>> isearch = IAnd_int(*map(IBTree, seq_btrees))\n>>> isearch.complete()\n>>> bset = isearch.asSet()\n\nIsearches also support iteration.\n\n>>> for hit in isearch:\n...   ...\n\n\n``ISearch`` constructors\n------------------------\n\nThe primary ``ISearch`` constructors are\n\n``IBTree``\n  turns a ``ZODB.BTrees`` object (tree, bucket, set or treeset) into\n  an ``ISearch``.\n``IAnd``\n  combines ``ISearches`` by an ``and``\n``Ior``\n  combines ``ISearches`` by an ``or``\n``INot``\n  negates an ``ISearch``\n``IFilter``\n  a filtering ``ISearch``\n``IEmpty``\n  the empty ``ISearch``\n``ISearch``\n  a base class to define your own ``ISearch`` es\n\nAny ``ISearch`` needs to know its keytype. Only ``ISearch`` es\nof the same keytype can be combined.\n\n``IBTree`` and\n``INot`` can determine the keytype themselves. \nFor the other constructors, the keytype is the first parameter.\nFor convenience, ``IAnd``, ``IOr`` and ``IFilter`` have\nspecializations with fixed keytype, e.g. ``IAnd_int``,\n``IAnd_obj`` and ``IAnd_long``.\n\n``INot`` and ``IFilter`` need an enumerator when their ``advanceFrom``\nis called. The enumerator enumerates the elements in the search\ndomain (the possible hits). It has the methods ``check(elem)`` which\nchecks whether *elem* is in the domain and ``next(elem)``\nwhich returns the element following *elem* in the domain or\n``Unspecified``. The ``Enumerator`` class in ``dm.incrementalsearch``\nturns a ``BTree`` into an enumerator.\n\nFor more information, see the docstrings.\n\nInstallation\n------------\n\nThere are reports that the C parts of ``dm.incrementalsearch``\ndo not compile under Windows. Apparently, some extension\nof the GNU C preprocessor is used which is unavailable\nwith the Microsoft C compiler. Thus, you probably need Cygwin\nwhen you want to use ``dm.incrementalsearch`` under Windows\n(or need at least the GNU C preprocessor and convince the Microsoft\ncompiler to use it as preprocessor).\n\nThe C parts are tightly coupled with the ``BTrees`` implementation\n(part of the ZODB). If the data structures for ``BTrees``\nchange drastically, then these parts may break (the danger is small, though).\nIn this case, the content of ``btrees_structs.h`` need to be\nadapted. See the comment at the start of this file.\n\n\nAdvance requirement\n-------------------\n\nWe must not use an ``advance`` function to move backward, in\nthe following precise sense:\n\n 1. when *key* is passed as first argument to ``advanceTo``,\n    then any first argument to later calls for an ``advance`` function\n    of this isearch must not be smaller than *key*.\n\n 2. when *fromKey* is passed as first argument to ``advanceFrom``,\n    then any first argument to later calls for an ``advance`` function\n    of this isearch must be (strictly) larger then *fromKey*.\n\nThe behaviour is undefined when the condition is violated.\n\n\nAdvance function return values\n------------------------------\n\nIsearches may not be completely obedient -- in that they can advance\nfurther than you told them to. However, they will not move\nover any hit. Conceptionally, an ``ISearch`` is a sorted list\nof hits which is lazily computed. The ``advance`` functions'\nreturn value tells the caller how obedient the call has been:\n\n``INLIST_SUCCESS``\n  The call did precisely what the caller told it and the\n  current value is in the list (i.e. a hit)\n\n  ``INLIST_SUCCESS`` is the integer ``0``.\n``INLIST``\n  The call could not do what the caller told it (there was\n  no hit there) and moved further to the next hit\n``CANDIDATE``\n  The call could not do what the caller told it (there was\n  no hit there) and moved further. The current value may\n  or may not be a hit.\n``NOT_INLIST``\n  The call advanced to a non hit. ``advanceFrom`` (unlike ``advanceTo``) must\n  not return this value.\n``AT_START``\n  The iteration over the list did not yet start; the current value is\n  undefined\n``AT_END``\n  the list is exhausted, there are no more hits; the current value is\n  undefined and further ``advance`` calls are no longer allowed.\n\nThe result of the last ``advance`` call is stored as attribute\n``classification``.\n\n\n\nHistory\n-------\n\n\n3.1\n\n  Fix: handle ``None`` in trees with object keys (which failed in Python 3\n  with a ``TypeError``)\n\n  Also define ``union`` and ``difference`` (beside ``intersection``).\n  (Unlike ``intersection``) they are likely less efficient than\n  the corresponding ``BTrees``\n  operations but can handle inhomogenous structures provided\n  they have the same key type. For example, you can compute\n  the union of an ``IISet`` with an ``IOBTree``.\n\n  ``estimatedSize`` can now be set externally for ``IBTree`` objects\n  (to support caching).\n\n3.0\n\n  For Python 2.7/3.4+, BTrees 4+\n  Tested under *nix only\n\n2.0\n\n  For Python 2.4.5+, ZODB 3.8+ (Zope 2.11+)\n  Tested under *nix only; now runs on 64 bit architecture as well",
        "description_content_type": "",
        "docs_url": null,
        "download_url": "",
        "downloads": {
            "last_day": -1,
            "last_month": -1,
            "last_week": -1
        },
        "home_page": "https://pypi.org/project/dm.incrementalsearch",
        "keywords": "search",
        "license": "BSD (see \"dm/incrementalsearch/LICENSE.txt\", for details)",
        "maintainer": "",
        "maintainer_email": "",
        "name": "dm.incrementalsearch",
        "package_url": "https://pypi.org/project/dm.incrementalsearch/",
        "platform": "",
        "project_url": "https://pypi.org/project/dm.incrementalsearch/",
        "project_urls": {
            "Homepage": "https://pypi.org/project/dm.incrementalsearch"
        },
        "release_url": "https://pypi.org/project/dm.incrementalsearch/3.1/",
        "requires_dist": null,
        "requires_python": "",
        "summary": "An efficient low level search execution engine on top of ZODB.BTrees.",
        "version": "3.1"
    },
    "last_serial": 5180650,
    "releases": {
        "2.0": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "1237a18ed954d85596145444ea203a08",
                    "sha256": "64a5f8656fe31d0d01f1a2722f50977c72a8e1a7f2697487195f140be94d3893"
                },
                "downloads": -1,
                "filename": "dm.incrementalsearch-2.0.tar.gz",
                "has_sig": false,
                "md5_digest": "1237a18ed954d85596145444ea203a08",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 33050,
                "upload_time": "2008-06-27T19:27:38",
                "url": "https://files.pythonhosted.org/packages/1d/9e/713b8a92e8d57b5aa1e304fcc839c065756420ea4886ea43211a9e5211a9/dm.incrementalsearch-2.0.tar.gz"
            }
        ],
        "3.0": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "93e5541b5f4dd3e071d441ba6c316977",
                    "sha256": "2b3c9c0da5532cf3d24b6dfe3ee5a933549e78732dc5c31d2abf85a83f8700c5"
                },
                "downloads": -1,
                "filename": "dm.incrementalsearch-3.0.tar.gz",
                "has_sig": false,
                "md5_digest": "93e5541b5f4dd3e071d441ba6c316977",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 37539,
                "upload_time": "2018-11-28T09:53:27",
                "url": "https://files.pythonhosted.org/packages/c5/34/ef162b94258c597c052d20c93962d0e3cbe50372fa23120d48cd66097c3b/dm.incrementalsearch-3.0.tar.gz"
            }
        ],
        "3.0.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "b7b7849ba4eb296821eab33190347dda",
                    "sha256": "2f6a1b1b95de2192a08f3b273c3c0c0e12c914c95ffc5f969cf76a3b0c18cd1d"
                },
                "downloads": -1,
                "filename": "dm.incrementalsearch-3.0.1.tar.gz",
                "has_sig": false,
                "md5_digest": "b7b7849ba4eb296821eab33190347dda",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 37267,
                "upload_time": "2018-11-28T10:03:40",
                "url": "https://files.pythonhosted.org/packages/ae/ca/3254acfb7b52578c58a3253b402f335659269adb44b72298f2b1d6facacc/dm.incrementalsearch-3.0.1.tar.gz"
            }
        ],
        "3.1": [
            {
                "comment_text": "",
                "digests": {
                    "md5": "9a6c5275e03a37e81f21f9a1dabf84c4",
                    "sha256": "0216798204270a2e23f7012383de4c2da5f6dddb097eca3338d845ab977a3293"
                },
                "downloads": -1,
                "filename": "dm.incrementalsearch-3.1.tar.gz",
                "has_sig": false,
                "md5_digest": "9a6c5275e03a37e81f21f9a1dabf84c4",
                "packagetype": "sdist",
                "python_version": "source",
                "requires_python": null,
                "size": 38521,
                "upload_time": "2019-04-24T06:57:50",
                "url": "https://files.pythonhosted.org/packages/db/8a/6404b5daef236297413da7aaeb69502ed2fb50f1cf5fe4dccae9eb7c0b13/dm.incrementalsearch-3.1.tar.gz"
            }
        ]
    },
    "urls": [
        {
            "comment_text": "",
            "digests": {
                "md5": "9a6c5275e03a37e81f21f9a1dabf84c4",
                "sha256": "0216798204270a2e23f7012383de4c2da5f6dddb097eca3338d845ab977a3293"
            },
            "downloads": -1,
            "filename": "dm.incrementalsearch-3.1.tar.gz",
            "has_sig": false,
            "md5_digest": "9a6c5275e03a37e81f21f9a1dabf84c4",
            "packagetype": "sdist",
            "python_version": "source",
            "requires_python": null,
            "size": 38521,
            "upload_time": "2019-04-24T06:57:50",
            "url": "https://files.pythonhosted.org/packages/db/8a/6404b5daef236297413da7aaeb69502ed2fb50f1cf5fe4dccae9eb7c0b13/dm.incrementalsearch-3.1.tar.gz"
        }
    ]
}