← Back to branch summary

~landscape/zope3/ztk-1.1.3

« back to all changes in this revision

Viewing changes to src/zope/index/field/sorting.py

  • Committer: Sidnei da Silva
  • Date: 2010-07-05 21:07:01 UTC
  • Revision ID: sidnei.da.silva@canonical.com-20100705210701-zmqhqrbzad1mhzsl
- Reduce deps

Show diffs side-by-side

added added

removed removed

Lines of Context:
src/zope/index/field/sorting.py
1
 
##############################################################################
2
 
#
3
 
# Copyright (c) 2009 Zope Foundation and Contributors.
4
 
# All Rights Reserved.
5
 
#
6
 
# This software is subject to the provisions of the Zope Public License,
7
 
# Version 2.1 (ZPL).  A copy of the ZPL should accompany this distribution.
8
 
# THIS SOFTWARE IS PROVIDED "AS IS" AND ANY AND ALL EXPRESS OR IMPLIED
9
 
# WARRANTIES ARE DISCLAIMED, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
10
 
# WARRANTIES OF TITLE, MERCHANTABILITY, AGAINST INFRINGEMENT, AND FITNESS
11
 
# FOR A PARTICULAR PURPOSE.
12
 
#
13
 
##############################################################################
14
 
"""A sorting mixin class for FieldIndex-like indexes.
15
 
 
16
 
$Id: sorting.py 100839 2009-06-11 06:15:27Z tseaver $
17
 
"""
18
 
import heapq
19
 
import bisect
20
 
from itertools import islice
21
 
 
22
 
from zope.interface import implements
23
 
from zope.index.interfaces import IIndexSort
24
 
 
25
 
class SortingIndexMixin(object):
26
 
 
27
 
    implements(IIndexSort)
28
 
 
29
 
    _sorting_num_docs_attr = '_num_docs'   # Length object
30
 
    _sorting_fwd_index_attr = '_fwd_index' # forward BTree index
31
 
    _sorting_rev_index_attr = '_rev_index' # reverse BTree index
32
 
 
33
 
    def sort(self, docids, reverse=False, limit=None):
34
 
        if (limit is not None) and (limit < 1):
35
 
            raise ValueError('limit value must be 1 or greater')
36
 
 
37
 
        numdocs = getattr(self, self._sorting_num_docs_attr).value
38
 
        if not numdocs:
39
 
            raise StopIteration
40
 
 
41
 
        if not isinstance(docids,
42
 
                          (self.family.IF.Set, self.family.IF.TreeSet)):
43
 
            docids = self.family.IF.Set(docids)
44
 
        if not docids:
45
 
            raise StopIteration
46
 
 
47
 
        rlen = len(docids)
48
 
 
49
 
        fwd_index = getattr(self, self._sorting_fwd_index_attr)
50
 
        rev_index = getattr(self, self._sorting_rev_index_attr)
51
 
        getValue = rev_index.get
52
 
        marker = object()
53
 
 
54
 
        # use_lazy and use_nbest computations lifted wholesale from
55
 
        # Zope2 catalog without questioning reasoning
56
 
        use_lazy = rlen > numdocs * (rlen / 100 + 1)
57
 
        use_nbest = limit and limit * 4 < rlen
58
 
 
59
 
        # overrides for unit tests
60
 
        if getattr(self, '_use_lazy', False):
61
 
            use_lazy = True
62
 
        if getattr(self, '_use_nbest', False):
63
 
            use_nbest = True
64
 
        
65
 
        if use_nbest:
66
 
            # this is a sort with a limit that appears useful, try to
67
 
            # take advantage of the fact that we can keep a smaller
68
 
            # set of simultaneous values in memory; use generators
69
 
            # and heapq functions to do so.
70
 
 
71
 
            def nsort():
72
 
                for docid in docids:
73
 
                    val = getValue(docid, marker)
74
 
                    if val is not marker:
75
 
                        yield (val, docid)
76
 
 
77
 
            iterable = nsort()
78
 
 
79
 
            if reverse:
80
 
                # we use a generator as an iterable in the reverse
81
 
                # sort case because the nlargest implementation does
82
 
                # not manifest the whole thing into memory at once if
83
 
                # we do so.
84
 
                for val in heapq.nlargest(limit, iterable):
85
 
                    yield val[1]
86
 
            else:
87
 
                # lifted from heapq.nsmallest
88
 
                it = iter(iterable)
89
 
                result = sorted(islice(it, 0, limit))
90
 
                if not result:
91
 
                    raise StopIteration
92
 
                insort = bisect.insort
93
 
                pop = result.pop
94
 
                los = result[-1]    # los --> Largest of the nsmallest
95
 
                for elem in it:
96
 
                    if los <= elem:
97
 
                        continue
98
 
                    insort(result, elem)
99
 
                    pop()
100
 
                    los = result[-1]
101
 
                for val in result:
102
 
                    yield val[1]
103
 
 
104
 
        else:
105
 
            if use_lazy and not reverse:
106
 
                # Since this the sort is not reversed, and the number
107
 
                # of results in the search result set is much larger
108
 
                # than the number of items in this index, we assume it
109
 
                # will be fastest to iterate over all of our forward
110
 
                # BTree's items instead of using a full sort, as our
111
 
                # forward index is already sorted in ascending order
112
 
                # by value. The Zope 2 catalog implementation claims
113
 
                # that this case is rarely exercised in practice.
114
 
                n = 0
115
 
                for stored_docids in fwd_index.values():
116
 
                    for docid in self.family.IF.intersection(docids,
117
 
                                                             stored_docids):
118
 
                        n += 1
119
 
                        yield docid
120
 
                        if limit and n >= limit:
121
 
                            raise StopIteration
122
 
            else:
123
 
                # If the result set is not much larger than the number
124
 
                # of documents in this index, or if we need to sort in
125
 
                # reverse order, use a non-lazy sort.
126
 
                n = 0
127
 
                for docid in sorted(docids, key=getValue, reverse=reverse):
128
 
                    if getValue(docid, marker) is not marker:
129
 
                        n += 1
130
 
                        yield docid
131
 
                        if limit and n >= limit:
132
 
                            raise StopIteration