Back to index

plone3  3.1.7
sorting.py
Go to the documentation of this file.
00001 # Copyright (C) 2003-2006 by Dr. Dieter Maurer, Eichendorffstr. 23, D-66386 St. Ingbert, Germany
00002 #       $Id: sorting.py,v 1.3 2006/11/09 19:27:33 dieter Exp $
00003 '''Auxiliary sorting module'''
00004 
00005 from BTrees.IIBTree import difference, IISet, IITreeSet
00006 from BTrees.OOBTree import OOBTree
00007 
00008 from AdvancedQuery import _notPassed, intersection
00009 
00010 def sort(seq, sortSpecs, withSortValue):
00011   '''sort 'IISet/IITreeSet' *seq* according to *sortSpec*.
00012 
00013   *sortSpecs* is a sequence of sort specs.
00014 
00015   The result has '__getitem__' and '__len__' methods.
00016   '__getitem__' must be called with sucessive integers, starting
00017   with '0'. This is sufficient for 'LazyMap'.
00018 
00019   If *withSortValue*, '__getitem__' returns triple
00020   *sortValue*, 'None', *documentId*, otherwise *documentId*.
00021   '''
00022   n = len(seq)
00023   if not withSortValue and (not sortSpecs or n <= 1): return seq
00024   return _SortAccess(n, _sort(seq, sortSpecs, withSortValue))
00025 
00026 
00027 class _SortAccess:
00028   '''auxiliary wrapper class (to provide '__getattr__' and '__len__').'''
00029   def __init__(self, len, generator):
00030     self._index = 0
00031     self._len = len
00032     self._iter = generator
00033 
00034   def __getitem__(self,index):
00035     if index >= self._len: raise IndexError
00036     if index != self._index:
00037       raise SystemError('unconsequtive access')
00038     self._index += 1
00039     s = self._iter.next()
00040     if isinstance(s, tuple):
00041       # with sort values
00042       sv, did = s
00043       s = None, sv, did
00044     return s
00045 
00046   def __len__(self): return self._len
00047 
00048 
00049 def _sort(seq, sortSpecs, withSortValues):
00050   # Note: "set" is an "IISet" or "IITreeSet"
00051   ns = len(seq)
00052   if ns == 1 and not withSortValues: yield seq.keys()[0]; return
00053 
00054   if not sortSpecs:
00055     wrap = withSortValues and (lambda did, e=(): (e, did)) or (lambda did: did)
00056     for s in seq.keys(): yield wrap(s)
00057     return
00058 
00059   sortSpecs = sortSpecs[:]
00060   sortSpec = sortSpecs.pop(0)
00061   for value, subseq in sortSpec.group(seq):
00062     subseq = _sort(subseq, sortSpecs, withSortValues)
00063     if withSortValues:
00064       for sv, did in subseq: yield (value,) + sv, did
00065     else:
00066       for did in subseq: yield did
00067 
00068 
00069 class Sorter(object):
00070   '''abstract base class to handle sorting with respect to one sort level.'''
00071   def group(self, seq):
00072     '''group *seq* (a set) generating pairs (*value*, *subseq*).
00073 
00074     All elements in *subseq* (a set) have *value* as sort value on this level.
00075     The union of all *subseq* gives *seq*.
00076 
00077     Elements not sorted on this level go into the last generated
00078     pair with 'None' as value.
00079     '''
00080     raise NotImplementedError
00081 
00082 
00083 class IndexSorter(Sorter):
00084   '''sorting with respect to an index.'''
00085   def __init__(self, sortIndex, sortReverse):
00086     self._sortIndex = sortIndex; self._sortReverse = sortReverse
00087 
00088   def group(self, seq):
00089     sortIndex = self._sortIndex; sortReverse = self._sortReverse
00090     ns = len(seq); ni = len(sortIndex)
00091     if ns >= 0.1 * ni:
00092       # result large compared to index -- sort via index
00093       handled = IISet(); hn = 0
00094       _load = getattr(sortIndex, '_load', None)
00095       if _load is None:
00096         # not an optimized index
00097         items = sortIndex.items()
00098         
00099         _load = lambda (x1, x2): x2
00100         if sortReverse: items.reverse()
00101       elif sortReverse:
00102         gRO = getattr(sortIndex, 'getReverseOrder', None)
00103         items = gRO and gRO()
00104         if items is None:
00105           items = list(sortIndex._index.keys()); items.reverse()
00106       else: items = sortIndex._index.keys()
00107       for i in items:
00108         ids = intersection(seq, _load(i))
00109         if ids:
00110           handled.update(ids); hn += len(ids)
00111           yield i, ids
00112       if hn != len(seq): yield None, difference(seq, handled)
00113     else:
00114       # result relatively small -- sort via result
00115       keyFor = sortIndex.keyForDocument; m = OOBTree()
00116       noValue = IITreeSet()
00117       for doc in seq.keys():
00118         try: k = keyFor(doc)
00119         except KeyError: noValue.insert(doc); continue
00120         l = m.get(k)
00121         if l is None: l = m[k] = IITreeSet()
00122         l.insert(doc)
00123       items = m.items()
00124       if sortReverse: items = list(items); items.reverse()
00125       for i in items: yield i
00126       if noValue: yield None, noValue
00127 
00128 
00129 def normSortSpecs(specs, withSortValue, cat):
00130   '''normalize sort specs *specs* and *withSortValue*.
00131 
00132   *specs* is a sequence of sort specifications.
00133   A sort specification is either a 'RankSpec', an index name
00134   or a pair index name + sorting order ('asc'/'desc').
00135 
00136   If 'withSortValue' is '_notPassed', then it is set to 'True',
00137   is *specs* contains a 'RankSpec', otherwise to 'False'.
00138   '''
00139   l= []; withValue = False
00140   for s in specs:
00141     if hasattr(s, '_prepare'): s = s._prepare(cat); withValue = True
00142     else:
00143       if isinstance(s, tuple): si,so= s
00144       else: si=s; so= 'asc'
00145       i= cat.indexes[si]
00146       # ensure, the index supports sorting
00147       if not hasattr(i,'documentToKeyMap'):
00148         raise ValueError,'Index not adequate for sorting: %s' % si
00149       # check whether we should reverse the order
00150       so= so.lower()
00151       if so in ('asc', 'ascending'): sr= 0
00152       elif so in ('desc', 'descending', 'reverse'): sr= 1
00153       s = IndexSorter(i, sr)
00154     l.append(s)
00155   if withSortValue is _notPassed: withSortValue = withValue
00156   return l, withSortValue