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

1 files changed, 85 insertions, 0 deletions

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