Changeset 723

Timestamp:

10/16/03 14:22:15 (5 years ago)

Author:

sholloway

Message:

*** empty log message ***

Files:

• trunk/RBFoundation/RBFoundation/Utilities.py (modified) (1 diff)

trunk/RBFoundation/RBFoundation/Utilities.py

@@ -119 +119 @@
-
-#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+#~ Tree Iteration/Searching
+#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
+
+class TreeDict(dict):
+    def addleaf(self, leaf):
+        self[None] = leaf
+    def addbranch(self, key, branch):
+        self[key] = branch
+
+class TreeIterator(object):
+    TreeFactory = TreeDict
+
+    def __init__(self, root=()):
+        self.SetRoot(root)
+
+    def GetRoot(self, root):
+        return self._root
+    def SetRoot(self, root):
+        self._root = root
+
+    def isBranch(self, key, value):
+        return bool(key)
+
+    def asTree(self):
+        resulttree = self.TreeFactory()
+        workqueue = [(resulttree, self._GetRootAsIter())]
+        while workqueue:
+            tree, itemcollection = workqueue.pop()
+            for key, item in itemcollection:
+                if self.isBranch(key, item):
+                    try: 
+                        itemtree=tree[key]
+                    except LookupError:
+                        itemtree=self.TreeFactory()
+                        tree.addbranch(key, itemtree)
+                    workqueue.append((itemtree, item))
+                else:
+                    tree.addleaf(item)
+        return resulttree
+
+    def iterByDepth(self, yieldkeys=False, filterDuplicates=False):
+        iterResult = self._iter(yieldkeys, -1)
+        if filterDuplicates:
+            return self.iterFilterDuplicates(iterResult, yieldkeys)
+        else:
+            return iterResult
+
+    def iterByBreadth(self, yieldkeys=False, filterDuplicates=False):
+        iterResult = self._iter(yieldkeys, 0)
+        if filterDuplicates:
+            return self.iterFilterDuplicates(iterResult, yieldkeys)
+        else:
+            return iterResult
+
+    def iterFilterDuplicates(self, iterable, resultDecorated=False):
+        if resultDecorated:
+            getvalue = lambda x:x[-1]
+        else: 
+            getvalue = lambda x:x
+
+        allresults = {}
+        for item in iterable:
+            value = getvalue(item)
+            if value not in allresults:
+                allresults[value]=None
+                yield item
+
+    def _GetRootAsIter(self):
+        if callable(self._root):
+            return self._root()
+        else:
+            return iter(self._root)
+
+    def _iter(self, yieldkeys=False, popindex=-1):
+        workqueue = [((), self._GetRootAsIter())]
+        while workqueue:
+            path, itemcollection = workqueue.pop(popindex)
+            tempqueue = []
+            for key, item in itemcollection:
+                newkey = path+(key,)
+                if self.isBranch(key, item):
+                    tempqueue.append((newkey, item))
+                elif yieldkeys:
+                    yield newkey, item
+                else:
+                    yield item
+            if popindex<0:
+                tempqueue.reverse()
+            workqueue.extend(tempqueue)
+
+#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
-#~ Testing 
-#~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~