[Zope-CVS] CVS: Packages/pypes/pypes - query.py:1.4

[Casey Duncan]

Update of /cvs-repository/Packages/pypes/pypes
In directory cvs.zope.org:/tmp/cvs-serv22218

Modified Files:
	query.py 
Log Message:
Implement greater-join query primitive.
Remove optimization reordering join inputs, it's premature at this point


=== Packages/pypes/pypes/query.py 1.3 => 1.4 ===
--- Packages/pypes/pypes/query.py:1.3	Fri Apr  2 22:50:23 2004
+++ Packages/pypes/pypes/query.py	Sun Apr  4 00:27:09 2004
@@ -46,6 +46,7 @@
 $Id$"""
 
 from zope.interface import implements
+from BTrees.OOBTree import OOBTree
 from pypes.interfaces import IQueryEngine
 from pypes.exceptions import PypesLookupError, PypesQueryInputError
 
@@ -155,22 +156,7 @@
     
     Complexity: O(N+M) where N=len(left), M=len(right)
     """
-    try:
-        # See if we can measure the lengths and put the 
-        # shorter sequence on the left so we use less memory
-        left_len = len(left_iter)
-        right_len = len(right_iter)
-    except TypeError:
-        pass # Can't measure length, may be iterator(s)
-    else:
-        if left_len > right_len:
-            tmp = left_len
-            left_len = right_len
-            right_len = tmp
-            tmp = left_expr
-            left_expr = right_expr
-            right_expr = tmp
-    left_by_val = {} # map of values => list of left matches
+    left_by_val = {}
     for obj in left_iter:
         val = left_expr(obj)
         try:
@@ -185,4 +171,31 @@
             continue # No matching left objects
         else:
             for left in left_matches:
-                yield (left, right)
+                yield left, right
+
+def greater_join(left_iter, left_expr, right_iter, right_expr):
+    """Join the values of the left_iter and right_iter iterables where the
+    value of left_expr is greater than the value of right_expr.
+    
+    left_expr and right_expr are callables accepting the members of their
+    respective iterable input as a single argument which derive the values
+    to be compared.
+    
+    Generate the resulting (left, right) tuple pairs where a join is made.
+    The resulting tuples are yielded in arbitrary order.
+    """
+    left_by_val = OOBTree() # (ordered) map of values => left members
+    for obj in left_iter:
+        left_val = left_expr(obj)
+        try:
+            left_by_val[left_val].append(obj)
+        except KeyError:
+            left_by_val[left_val] = [obj]
+    for right in right_iter:
+        right_val = right_expr(right)        
+        for left_val, left_matches in left_by_val.items(right_val, None):
+            if left_val > right_val:
+                for left in left_matches:
+                    yield left, right
+
+