[Checkins] SVN: zope.index/branches/nadako-sorting/ Create a branch for implementing sorting by indexed values.

[Dan Korostelev]

Log message for revision 94347:
  Create a branch for implementing sorting by indexed values.

Changed:
  A   zope.index/branches/nadako-sorting/
  U   zope.index/branches/nadako-sorting/src/zope/index/field/README.txt
  U   zope.index/branches/nadako-sorting/src/zope/index/field/index.py
  U   zope.index/branches/nadako-sorting/src/zope/index/field/tests.py
  U   zope.index/branches/nadako-sorting/src/zope/index/interfaces.py

-=-
Modified: zope.index/branches/nadako-sorting/src/zope/index/field/README.txt
===================================================================
--- zope.index/trunk/src/zope/index/field/README.txt	2008-12-26 14:09:49 UTC (rev 94346)
+++ zope.index/branches/nadako-sorting/src/zope/index/field/README.txt	2008-12-26 15:41:26 UTC (rev 94347)
@@ -108,6 +108,36 @@
     >>> index.apply((30, 70))
     IFSet([])
 
+Sorting
+-------
+
+Field indexes also implement IIndexSort interface that
+provides a method for sorting document ids by their indexed
+values.
+
+    >>> index.index_doc(1, 9)
+    >>> index.index_doc(2, 8)
+    >>> index.index_doc(3, 7)
+    >>> index.index_doc(4, 6)
+    >>> index.index_doc(5, 5)
+    >>> index.index_doc(6, 4)
+    >>> index.index_doc(7, 3)
+    >>> index.index_doc(8, 2)
+    >>> index.index_doc(9, 1)
+
+    >>> index.sort([4, 2, 9, 7, 4, 1, 5])
+    [9, 7, 5, 4, 2, 1]
+
+If we pass an id that is not indexed by this index, the
+KeyError is raised as Interface declares:
+
+    >>> index.sort([10])
+    Traceback (most recent call last):
+    ...
+    KeyError: 'docid 10 is not indexed by <zope.index.field.index.FieldIndex object at 0x...>'
+
+    >>> index.clear()
+
 Bugfix testing:
 ---------------
 Happened at least once that the value dropped out of the forward index,

Modified: zope.index/branches/nadako-sorting/src/zope/index/field/index.py
===================================================================
--- zope.index/trunk/src/zope/index/field/index.py	2008-12-26 14:09:49 UTC (rev 94346)
+++ zope.index/branches/nadako-sorting/src/zope/index/field/index.py	2008-12-26 15:41:26 UTC (rev 94347)
@@ -31,6 +31,7 @@
         interfaces.IInjection,
         interfaces.IStatistics,
         interfaces.IIndexSearch,
+        interfaces.IIndexSort,
         )
 
     family = BTrees.family32
@@ -107,3 +108,23 @@
             raise TypeError("two-length tuple expected", query)
         return self.family.IF.multiunion(
             self._fwd_index.values(*query))
+
+    def sort(self, docids):
+        values = self._rev_index
+        sorted = self.family.OO.BTree()
+
+        for docid in docids:
+            value = values.get(docid, None)
+            if value is None:
+                raise KeyError('docid %d is not indexed by %s' % (docid, self))
+            ids = sorted.get(value, None)
+            if ids is None:
+                ids = self.family.OO.Set()
+                sorted[value] = ids
+            ids.insert(docid)
+        
+        result = []
+        for _, ids in sorted.items():
+            result.extend(ids)
+
+        return result

Modified: zope.index/branches/nadako-sorting/src/zope/index/field/tests.py
===================================================================
--- zope.index/trunk/src/zope/index/field/tests.py	2008-12-26 14:09:49 UTC (rev 94346)
+++ zope.index/branches/nadako-sorting/src/zope/index/field/tests.py	2008-12-26 15:41:26 UTC (rev 94347)
@@ -19,7 +19,7 @@
 from zope.testing import doctest
 
 def test_suite():
-    return doctest.DocFileSuite('README.txt')
+    return doctest.DocFileSuite('README.txt', optionflags=doctest.ELLIPSIS)
 
 if __name__=='__main__':
     unittest.main(defaultTest='test_suite')

Modified: zope.index/branches/nadako-sorting/src/zope/index/interfaces.py
===================================================================
--- zope.index/trunk/src/zope/index/interfaces.py	2008-12-26 14:09:49 UTC (rev 94346)
+++ zope.index/branches/nadako-sorting/src/zope/index/interfaces.py	2008-12-26 15:41:26 UTC (rev 94347)
@@ -82,6 +82,18 @@
 
         """
 
+class IIndexSort(Interface):
+
+    def sort(docids):
+        """Sort document ids sequence using indexed values
+        
+        If some of docids are not in index, KeyError is 
+        raised.
+        
+        Return an ordered sequence of document ids. 
+        
+        """
+
 class IStatistics(Interface):
     """An index that provides statistical information about itself."""