Merge large rework from W. Trevor King.

1 files changed, 37 insertions, 19 deletions

diff --git a/libbe/tree.py b/libbe/tree.py
index 54b927e..45ae085 100644
--- a/libbe/tree.py
+++ b/libbe/tree.py
@@ -1,20 +1,19 @@
 # Bugs Everywhere, a distributed bugtracker
 # Copyright (C) 2008-2009 W. Trevor King <wking@drexel.edu>
 #
-#  This program is free software; you can redistribute it and/or modify
-#  it under the terms of the GNU General Public License as published by
-#  the Free Software Foundation; either version 2 of the License, or
-#  (at your option) any later version.
+# This program is free software; you can redistribute it and/or modify
+# it under the terms of the GNU General Public License as published by
+# the Free Software Foundation; either version 2 of the License, or
+# (at your option) any later version.
 #
-#  This program is distributed in the hope that it will be useful,
-#  but WITHOUT ANY WARRANTY; without even the implied warranty of
-#  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
-#  GNU General Public License for more details.
+# This program is distributed in the hope that it will be useful,
+# but WITHOUT ANY WARRANTY; without even the implied warranty of
+# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
+# GNU General Public License for more details.
 #
-#  You should have received a copy of the GNU General Public License
-#  along with this program; if not, write to the Free Software
-#  Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
-#  02110-1301, USA
+# You should have received a copy of the GNU General Public License along
+# with this program; if not, write to the Free Software Foundation, Inc.,
+# 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
 
 import doctest
 
@@ -36,7 +35,7 @@ class Tree(list):
     >>> a = Tree();       a.n = "a"
     >>> a.append(c)
     >>> a.append(b)
-    
+
     >>> a.branch_len()
     5
     >>> a.sort(key=lambda node : -node.branch_len())
@@ -45,7 +44,7 @@ class Tree(list):
     >>> a.sort(key=lambda node : node.branch_len())
     >>> "".join([node.n for node in a.traverse()])
     'abdgcefhi'
-    >>> "".join([node.n for node in a.traverse(depthFirst=False)])
+    >>> "".join([node.n for node in a.traverse(depth_first=False)])
     'abcdefghi'
     >>> for depth,node in a.thread():
     ...     print "%*s" % (2*depth+1, node.n)
@@ -69,7 +68,18 @@ class Tree(list):
     f
     h
     i
+    >>> a.has_descendant(g)
+    True
+    >>> c.has_descendant(g)
+    False
+    >>> a.has_descendant(a)
+    False
+    >>> a.has_descendant(a, match_self=True)
+    True
     """
+    def __eq__(self, other):
+        return id(self) == id(other)
+
     def branch_len(self):
         """
         Exhaustive search every time == SLOW.
@@ -98,11 +108,11 @@ class Tree(list):
         for child in self:
             child.sort(*args, **kwargs)
 
-    def traverse(self, depthFirst=True):
+    def traverse(self, depth_first=True):
         """
         Note: you might want to sort() your tree first.
         """
-        if depthFirst == True:
+        if depth_first == True:
             yield self
             for child in self:
                 for descendant in child.traverse():
@@ -120,7 +130,7 @@ class Tree(list):
         When flatten==False, the depth of any node is one greater than
         the depth of its parent.  That way the inheritance is
         explicit, but you can end up with highly indented threads.
-        
+
         When flatten==True, the depth of any node is only greater than
         the depth of its parent when there is a branch, and the node
         is not the last child.  This can lead to ancestry ambiguity,
@@ -139,8 +149,8 @@ class Tree(list):
         stack = [] # ancestry of the current node
         if flatten == True:
             depthDict = {}
-        
-        for node in self.traverse(depthFirst=True):
+
+        for node in self.traverse(depth_first=True):
             while len(stack) > 0 \
                     and id(node) not in [id(c) for c in stack[-1]]:
                 stack.pop(-1)
@@ -158,4 +168,12 @@ class Tree(list):
             yield (depth,node)
             stack.append(node)
 
+    def has_descendant(self, descendant, depth_first=True, match_self=False):
+        if descendant == self:
+            return match_self
+        for d in self.traverse(depth_first):
+            if descendant == d:
+                return True
+        return False
+
 suite = doctest.DocTestSuite()