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

[Casey Duncan]

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

Modified Files:
	query.py 
Log Message:
Implement equi-join query primitive


=== Packages/pypes/pypes/query.py 1.2 => 1.3 ===
--- Packages/pypes/pypes/query.py:1.2	Wed Mar 31 00:00:52 2004
+++ Packages/pypes/pypes/query.py	Fri Apr  2 22:50:23 2004
@@ -141,3 +141,48 @@
         sortable = sortable[:limit]
     # XXX We should be make this lazy
     return [i for key, i in sortable]
+
+def equijoin(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 equals 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.
+    
+    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
+    for obj in left_iter:
+        val = left_expr(obj)
+        try:
+            left_by_val[val].append(obj)
+        except KeyError:
+            left_by_val[val] = [obj]
+    for right in right_iter:
+        val = right_expr(right)
+        try:
+            left_matches = left_by_val[val]
+        except KeyError:
+            continue # No matching left objects
+        else:
+            for left in left_matches:
+                yield (left, right)