[Zope-CVS] CVS: Packages/pypes/pypes - exceptions.py:1.7
query.py:1.13
Casey Duncan
casey at zope.com
Wed May 12 01:10:38 EDT 2004
Update of /cvs-repository/Packages/pypes/pypes
In directory cvs.zope.org:/tmp/cvs-serv1583
Modified Files:
exceptions.py query.py
Log Message:
Implement "in" join primitive
Basic iterResult() method implementation for Join
=== Packages/pypes/pypes/exceptions.py 1.6 => 1.7 ===
--- Packages/pypes/pypes/exceptions.py:1.6 Tue May 4 23:37:38 2004
+++ Packages/pypes/pypes/exceptions.py Wed May 12 01:10:36 2004
@@ -22,7 +22,8 @@
"""Cannot process requested operation.
An internal error used to signal to a caller to use an alernate method to
- perform a given operation. Not general propagated to applications"""
+ perform a given operation. Not general propagated to applications
+ """
class PypesLookupError(PypesError, LookupError):
"""Persistent pypes component lookup failure"""
=== Packages/pypes/pypes/query.py 1.12 => 1.13 ===
--- Packages/pypes/pypes/query.py:1.12 Wed May 5 00:06:35 2004
+++ Packages/pypes/pypes/query.py Wed May 12 01:10:36 2004
@@ -47,6 +47,7 @@
from operator import mul
from sets import Set
+from itertools import imap
from zope.interface import implements
from compiler import ast
from BTrees.OOBTree import OOBTree
@@ -209,6 +210,89 @@
criteria is satisfied
"""
+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)
+ """
+ left_by_val = {}
+ 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
+
+def injoin(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 contained in 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.
+ """
+ right_by_val = {}
+ for obj in right_iter:
+ for val in right_expr(obj):
+ try:
+ right_by_val[val].add(obj)
+ except KeyError:
+ right_by_val[val] = Set((obj,))
+ for obj in left_iter:
+ left = left_expr(obj)
+ try:
+ right_matches = right_by_val[left]
+ except KeyError:
+ continue # No matching right objects
+ else:
+ for right in right_matches:
+ yield left, right
+
+def greaterjoin(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
+
class Join:
"""Join of multiple inputs using a criteria expression.
@@ -219,6 +303,11 @@
implements(IPartialResult)
+ _join_ops = {
+ '==': equijoin,
+ '>': greaterjoin,
+ 'in': injoin}
+
def __init__(self, input_map, criteria):
"""Construct the joins
@@ -232,6 +321,7 @@
is raised.
"""
self._inputs = input_map
+ self._criteria = criteria
if len(criteria.freeNames()) != 2:
raise CantProcess, 'join criteria must have 2 free variables'
compare_node = criteria.ast().getChildNodes()[0]
@@ -240,26 +330,82 @@
raise CantProcess, ('join criteria must be single comparison '
'between two terms')
left, operator, right = compare_node.getChildren()
- if operator not in ('==', 'in', '<', '>'):
- raise CantProcess, (
- 'operator %s not suppported for join' % operator)
if operator == '<':
# Only greater join is directly supported
operator = '>'
left, right = right, left
+ self.reverse = True
+ else:
+ self.reverse = False
+ if operator not in self._join_ops.keys():
+ raise CantProcess, (
+ 'operator %s not supported for join' % operator)
bindings = criteria.bindings()
- self._left = Expression.fromAstNode(left, bindings)
- self._right = Expression.fromAstNode(right, bindings)
+ left_expr = Expression.fromAstNode(left, bindings)
+ right_expr = Expression.fromAstNode(right, bindings)
self._operator = operator
- left_names = self._left.freeNames()
- right_names = self._right.freeNames()
+ left_names = list(left_expr.freeNames())
+ right_names = list(right_expr.freeNames())
if (len(left_names) != 1
- or iter(left_names).next() not in input_map
+ or left_names[0] not in input_map
or len(right_names) != 1
- or iter(right_names).next() not in input_map):
+ or right_names[0] not in input_map):
raise CantProcess, ('left and right join criteria operands '
'must contain a single input term')
+ self._left_name, = left_names
+ self._left_func = left_expr.makeFunction(left_names)
+ self._right_name, = right_names
+ self._right_func = right_expr.makeFunction(right_names)
+
+ def inputMap(self):
+ return self._inputs.copy()
+
+ def criteriaExpr(self):
+ return self._criteria
+
+ def namesUsed(self):
+ return self._criteria.freeNames(self._inputs.keys())
+ def _iterJoin(self, reverse=False):
+ # Generates (left, right) pairs of joined terms
+ join = self._join_ops[self._operator]
+ if reverse:
+ return join(
+ self._inputs[self._right_name], self._right_func,
+ self._inputs[self._left_name], self._left_func)
+ else:
+ return join(
+ self._inputs[self._left_name], self._left_func,
+ self._inputs[self._right_name], self._right_func)
+
+ def iterResult(self, *names):
+ if len(names) == 2 and names == (self._left_name, self._right_name):
+ # Special case, names match join terms in order exactly
+ # No transform of the raw join is required
+ # This case is expected to be relatively common
+ return self._iterJoin(self.reverse)
+ joined_names = []
+ other_names = []
+ free_names = self._criteria.freeNames()
+ for n in names:
+ if n in free_names:
+ joined_names.append(n)
+ else:
+ other_names.append(n)
+ if not other_names:
+ # No names other than the joined names were selected
+ if names == (self._left_name,):
+ output = lambda row: row[0]
+ elif names == (self._right_name,):
+ output = lambda row: row[1]
+ elif names == (self._right_name, self._left_name):
+ output = lambda row: (row[1], row[0])
+ else:
+ # Ok, something is wrong with this picture
+ raise RuntimeError('Bug in join result tranformation')
+ return imap(output, self._iterJoin(self.reverse))
+ else:
+ raise NotImplementedError
def sort(iterable, expression, order=ascending, limit=None):
"""Return a sequence containing the elements of iterable sorted in order
@@ -284,60 +430,5 @@
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)
- """
- left_by_val = {}
- 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
-
-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
More information about the Zope-CVS
mailing list