dm.incrementalsearch 2.0

Example usage

incrementalsearch is rarely used directly but usually indirectly via a higher level search engine such as Products.AdvancedQuery. Let’s nevertheless look at some examples.

Assume we want to find elements available in each of a sequence of integer BTrees seq_btrees. I.e. we are interested in elements contained in the intersection of these BTrees.

>>> from dm.incrementalsearch import IBTree, IAnd_int, Unspecified, \
...     AT_END, INLIST_SUCCESS

We transform the BTrees into incrementally searchable objects by applying the IBTree operator (Incremental BTree). Then we combine them by IAnd_int and indicate that no more searches will be added by calling complete. This causes several optimizations to take place.

>>> isearch = IAnd_int(*map(IBTree, seq_btrees))
>>> isearch.complete()

An ISearch has attributes value (the current value) and classification (it indicates whether the current value is a hit and whether there may be more values) and methods advanceFrom and advanceTo to move forward in the search. To determine the first hit, we can use:

>>> cl = isearch.advanceFrom(Unspecified, Unspecified)
>>> if cl != AT_END:
...     first_hit = isearch.value

The next hit is determined by

>>> cl = isearch.advanceFrom(isearch.value, Unspecified)
>>> if cl != AT_END:
...     next_hit = isearch.value

If we know that hits at or below 1000 are irrelevant, we can use

>>> cl = isearch.advanceFrom(1000, Unspecified)
>>> if cl != AT_END:
...     hit_above_1000 = isearch.value

We can also indicate that we are interested only in hits below some upper value.

>>> cl = isearch.advanceFrom(2000, 10000)
>>> if cl == INLIST_SUCCESS:
...     hit_above_2000_below_10000 = isearch.value

We can use the asSet method to obtain all hits as a (BTree) set. asSet should only be called on fresh, i.e. (as yet) unadvanced isearches (we may remove this restriction later, if there is a need to).

>>> isearch = IAnd_int(*map(IBTree, seq_btrees))
>>> isearch.complete()
>>> bset = isearch.asSet()

Isearches also support iteration.

>>> for hit in isearch:
...   ...

ISearch constructors

The primary ISearch constructors are

IBTree

turns a ZODB.BTrees object (tree, bucket, set or treeset) into an ISearch.

IAnd

combines ISearches by an and

Ior

combines ISearches by an or

INot

negates an ISearch

IFilter

a filtering ISearch

IEmpty

the empty ISearch

ISearch

a base class to define your own ISearch es

Any ISearch needs to know its keytype. Only ISearch es of the same keytype can be combined.

IBTree and INot can determine the keytype themselves. For the other constructors, the keytype is the first parameter. For convenience, IAnd, IOr and IFilter have specializations with fixed keytype, e.g. IAnd_int, IAnd_obj and IAnd_long.

INot and IFilter need an enumerator when their advanceFrom is called. The enumerator enumerates the elements in the search domain (the possible hits). It has the methods check(elem) which checks whether elem is in the domain and next(elem) which returns the element following elem in the domain or Unspecified. The Enumerator class in dm.incrementalsearch turns a BTree into an enumerator.

For more information, see the docstrings.

Installation

dm.incrementalsearch is a bit complex to install.

First, it needs access to the ZODB source code and you must tell setup.py where this source code is located by storing the path to it in the envvar ZODB_HOME. If you use the ZODB packaged with Zope2, then you use the path to Zope’s lib/python as value.

There are reports that the C parts of dm.incrementalsearch do not compile under Windows. Apparently, some extension of the GNU C preprocessor is used which is unavailable with the Microsoft C compiler. Thus, you probably need Cygwin when you want to use dm.incrementalsearch under Windows (or need at least the GNU C preprocessor and convince the Microsoft compiler to use it as preprocessor).

The C parts are tightly coupled with the BTrees implementation (part of the ZODB). If the data structures for BTrees change drastically, then these parts may break (the danger is small, though). In this case, the content of btrees_structs.h need to be adapted. See the comment at the start of this file.

Advance requirement

We must not use an advance function to move backward, in the following precise sense:

1. when key is passed as first argument to advanceTo, then any first argument to later calls for an advance function of this isearch must not be smaller than key.

2. when fromKey is passed as first argument to advanceFrom, then any first argument to later calls for an advance function of this isearch must be (strictly) larger then fromKey.

The behaviour is undefined when the condition is violated.

Advance function return values

Isearches may not be completely obedient – in that they can advance further than you told them to. However, they will not move over any hit. Conceptionally, an ISearch is a sorted list of hits which is lazily computed. The advance functions’ return value tell the caller how obedient the call has been:

INLIST_SUCCESS

The call did precisely what the caller told it and the current value is in the list (i.e. a hit)

INLIST_SUCCESS is the integer 0.

INLIST

The call could not do what the caller told it (there was no hit there) and moved further to the next hit

CANDIDATE

The call could not do what the caller told it (there was no hit there) and moved further. The current value may or may not be a hit.

NOT_INLIST

The call advanced to a non hit. advanceFrom (unlike advanceTo) must not return this value.

AT_START

The iteration over the list did not yet start; the current value is undefined

AT_END

the list is exhausted, there are no more hits; the current value is undefined and further advance calls are no longer allowed.

The result of the last advance call is stored as attribute classification.