[Zope-CVS] CVS: Packages/pypes/pypes - order.py:1.2

[Casey Duncan]

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

Modified Files:
	order.py 
Log Message:
refactor multi-expression sort algorithm, it now seems to return correct results and should hopefully be easier to follow.


=== Packages/pypes/pypes/order.py 1.1 => 1.2 ===
--- Packages/pypes/pypes/order.py:1.1	Fri Aug 20 16:21:23 2004
+++ Packages/pypes/pypes/order.py	Mon Nov 29 02:02:34 2004
@@ -80,7 +80,12 @@
                             yield value
                 else:
                     for key, value in sortiter:
-                        if key in groups:
+                        try:
+                            key_in_groups = key in groups
+                        except TypeError:
+                            # Key is unhashable and couldn't possibly be in a group
+                            key_in_groups = False
+                        if key_in_groups:
                             stack.append((sortiter, groups))
                             sorted, groups = groups[key]
                             depth += 1
@@ -180,54 +185,52 @@
     if len(exprs) == 1:
         return _sort_single(iterable, exprs[0])
     sortfuncs = _make_sort_funcs(exprs)
-    top_groups = {} # sort key => group trees
-    top_ordered = OOBTree() # sort key => object or group tree
-    deferred = []
-    for obj in itertools.chain(iterable, deferred):
-        groups = top_groups
-        ordered = top_ordered
-        for sortkey in sortfuncs:
-            key = sortkey(obj)
+    sortfunc_indexes = range(len(sortfuncs))
+    max_sortfunc_index = sortfunc_indexes[-1]
+    root_groups = {} # sort key => group trees
+    root_ordered = OOBTree() # sort key => object or group tree
+    for obj in iterable:
+        groups = root_groups
+        ordered = root_ordered
+        for i in sortfunc_indexes:
+            key = sortfuncs[i](obj)
             try:
                 ingroup = key in groups
             except TypeError:
                 # Key is not hashable, switch to BTree
                 if isinstance(groups, dict):
-                    if groups is top_groups:
-                        top_groups = groups = OOBTree(groups)
+                    if groups is root_groups:
+                        root_groups = groups = OOBTree(groups)
                     else:
                         groups = OOBTree(groups)
                 else:
                     raise
             if ingroup:
-                groups, ordered = groups[key]
+                # Duplicate key
+                ordered, groups = groups[key]
             elif ordered.insert(key, obj):
+                # New key inserted
                 break
             else:
-                depth = sortfuncs.index(sortkey) + 1
-                firstobj = ordered[key]
-                try:
-                    sortkey = sortfuncs[depth]
-                except IndexError:
-                    groups[key] = ordered[key] = [firstobj, obj]
+                # First collision for this key
+                if i < max_sortfunc_index:
+                    # Add a new child group and tree
+                    firstobj = ordered[key]
+                    groups[key] = ordered[key] = OOBTree(), {}
+                    ordered, groups = groups[key]
+                    firstobj_key = sortfuncs[i + 1](firstobj)
+                    ordered[firstobj_key] = firstobj
                 else:
-                    old_groups = groups
-                    groups = {}
-                    old_groups[key] = ordered[key] = groups, OOBTree()
-                    firstkey = sortkey(firstobj)
-                    if firstkey != key:
-                        ordered[firstkey] = firstobj
-                    else:
-                        # come back for this one later
-                        deferred.append(firstobj)
-                    ordered[key] = obj
-                break
+                    # This is the last sort function
+                    # collect the colliding objects into leaf list 
+                    groups[key] = ordered[key] = [firstobj, obj]
+                    break
         else:
             if key in groups:
                 groups[key].append(obj)
             else:
                 groups[key] = ordered[key] = [ordered[key], obj]
-    return top_ordered, top_groups
+    return root_ordered, root_groups
 
 
 def _make_sort_funcs(exprs):