objects.utils: Added Traversable base and implemented it for commits including a test

4 files changed, 117 insertions, 1 deletions

diff --git a/lib/git/objects/commit.py b/lib/git/objects/commit.py
index c7824ca6..bb458921 100644
--- a/lib/git/objects/commit.py
+++ b/lib/git/objects/commit.py
@@ -13,7 +13,7 @@ import utils
 import tempfile
 import os
 
-class Commit(base.Object, Iterable, diff.Diffable):
+class Commit(base.Object, Iterable, diff.Diffable, utils.Traversable):
 	"""
 	Wraps a git Commit object.
 	
@@ -74,6 +74,10 @@ class Commit(base.Object, Iterable, diff.Diffable):
 		if self.sha and tree is not None:
 			self.tree = Tree(repo, tree, path='')
 		# END id to tree conversion
+		
+	@classmethod
+	def _get_intermediate_items(cls, commit):
+		return commit.parents
 
 	def _set_cache_(self, attr):
 		"""
diff --git a/lib/git/objects/tree.py b/lib/git/objects/tree.py
index f88096b3..d070c0d3 100644
--- a/lib/git/objects/tree.py
+++ b/lib/git/objects/tree.py
@@ -173,6 +173,7 @@ class Tree(base.IndexObject, diff.Diffable):
 		Returns
 		
 			Iterator to traverse the tree recursively up to the given level.
+			The traversal is depth-first.
 			The iterator returns Blob and Tree objects with paths relative to their 
 			repository.
 		
diff --git a/lib/git/objects/utils.py b/lib/git/objects/utils.py
index 7bb4e8e2..6c45f039 100644
--- a/lib/git/objects/utils.py
+++ b/lib/git/objects/utils.py
@@ -7,6 +7,7 @@
 Module for general utility functions
 """
 import re
+from collections import deque as Deque
 from git.actor import Actor
 
 def get_object_type_by_name(object_type_name):
@@ -70,3 +71,87 @@ class ProcessStreamAdapter(object):
 	
 	def __getattr__(self, attr):
 		return getattr(self._stream, attr)
+		
+		
+class Traversable(object):
+	"""Simple interface to perforam depth-first or breadth-first traversals 
+	into one direction.
+	Subclasses only need to implement one function.
+	Instances of the Subclass must be hashable"""
+	__slots__ = tuple()
+	
+	@classmethod
+	def _get_intermediate_items(cls, item):
+		"""
+		Returns:
+			List of items connected to the given item.
+			Must be implemented in subclass
+		"""
+		raise NotImplementedError("To be implemented in subclass")
+			
+	
+	def traverse( self, predicate = lambda i: True,
+						   prune = lambda i: False, depth = -1, branch_first=True,
+						   visit_once = True, ignore_self=1 ):
+		"""
+		``Returns``
+			iterator yieling of items found when traversing self
+			
+		``predicate``
+			f(i) returns False if item i should not be included in the result
+			
+		``prune``
+			f(i) return True if the search should stop at item i.
+			Item i will not be returned.
+			
+		``depth``
+			define at which level the iteration should not go deeper
+			if -1, there is no limit
+			if 0, you would effectively only get self, the root of the iteration
+			i.e. if 1, you would only get the first level of predessessors/successors
+			
+		``branch_first``
+			if True, items will be returned branch first, otherwise depth first
+			
+		``visit_once``
+			if True, items will only be returned once, although they might be encountered
+			several times. Loops are prevented that way.
+			
+		``ignore_self``
+			if True, self will be ignored and automatically pruned from
+			the result. Otherwise it will be the first item to be returned"""
+		visited = set()
+		stack = Deque()
+		stack.append( ( 0 ,self ) )		# self is always depth level 0
+	
+		def addToStack( stack, lst, branch_first, dpth ):
+			if branch_first:
+				stack.extendleft( ( dpth , item ) for item in lst )
+			else:
+				reviter = ( ( dpth , lst[i] ) for i in range( len( lst )-1,-1,-1) )
+				stack.extend( reviter )
+		# END addToStack local method
+	
+		while stack:
+			d, item = stack.pop()			# depth of item, item
+	
+			if item in visited:
+				continue
+	
+			if visit_once:
+				visited.add( item )
+	
+			if prune( item ):
+				continue
+	
+			skipStartItem = ignore_self and ( item == self )
+			if not skipStartItem and predicate( item ):
+				yield item
+	
+			# only continue to next level if this is appropriate !
+			nd = d + 1
+			if depth > -1 and nd > depth:
+				continue
+	
+			addToStack( stack, self._get_intermediate_items( item ), branch_first, nd )
+		# END for each item on work stack
diff --git a/test/git/test_commit.py b/test/git/test_commit.py
index 2e3f131e..e06e35f4 100644
--- a/test/git/test_commit.py
+++ b/test/git/test_commit.py
@@ -48,6 +48,32 @@ class TestCommit(TestBase):
 		assert commit.committed_date == 1210193388
 		assert commit.message == "initial project"
 		
+	def test_traversal(self):
+		start = self.rorepo.commit("a4d06724202afccd2b5c54f81bcf2bf26dea7fff")
+		p0 = start.parents[0]
+		p1 = start.parents[1]
+		p00 = p0.parents[0]
+		
+		# basic branch first, depth first
+		dfirst = start.traverse(branch_first=False)
+		bfirts = start.traverse(branch_first=True)
+		assert dfirst.next() == p0
+		assert dfirst.next() == p00
+		assert bfirts.next() == p0
+		assert bfirts.next() == p1
+		
+		# ignore self
+		assert start.traverse(ignore_self=False).next() == start
+		
+		# depth 
+		assert len(list(start.traverse(ignore_self=False, depth=0))) == 1
+		
+		# prune
+		assert start.traverse(branch_first=1, prune=lambda i: i==p0).next() == p1
+		
+		# predicate
+		assert start.traverse(branch_first=1, predicate=lambda i: i==p1).next() == p1
+		
 	@patch_object(Git, '_call_process')
 	def test_rev_list_bisect_all(self, git):
 		"""