[patch] New digraph v2

new-digraph.patch (text/plain), 5.73 KB, created by Jason Stubbs (RETIRED) on 2006-09-15 23:09:58 UTC

--- pym/portage.py.orig	2006-09-17 01:39:25.000000000 +0000
+++ pym/portage.py	2006-09-17 15:06:50.000000000 +0000
@@ -313,84 +313,134 @@
 
 class digraph:
 	def __init__(self):
-		self.dict={}
-		#okeys = keys, in order they were added (to optimize firstzero() ordering)
-		self.okeys=[]
-
-	def addnode(self,mykey,myparent):
-		if not self.dict.has_key(mykey):
-			self.okeys.append(mykey)
-			if myparent is None:
-				self.dict[mykey]=[0,[]]
-			else:
-				self.dict[mykey]=[0,[myparent]]
-				self.dict[myparent][0]=self.dict[myparent][0]+1
+		"""Create an empty digraph"""
+		
+		# { node : ( { child : hard_dep } , { parent : hard_dep } ) }
+		self.nodes = {}
+		self.order = []
+
+	def add(self, node, parent, hard_dep=True):
+		"""Adds the specified node with the specified parent. If the dep
+		is a hard-dep and the node already has a relationship to the parent
+		the relationship is ensured to be hard."""
+		
+		if node not in self.nodes:
+			self.nodes[node] = ({}, {})
+			self.order.append(node)
+		
+		if not parent:
 			return
-		if myparent and (not myparent in self.dict[mykey][1]):
-			self.dict[mykey][1].append(myparent)
-			self.dict[myparent][0]=self.dict[myparent][0]+1
-
-	def delnode(self,mykey):
-		if not self.dict.has_key(mykey):
+		
+		if parent not in self.nodes:
+			self.nodes[parent] = ({}, {})
+			self.order.append(parent)
+		
+		if parent in self.nodes[node][1]:
+			if hard_dep:
+				self.nodes[node][1][parent] = True
+		else:
+			self.nodes[node][1][parent] = hard_dep
+		
+		if node in self.nodes[parent][0]:
+			if hard_dep:
+				self.nodes[parent][0][node] = True
+		else:
+			self.nodes[parent][0][node] = hard_dep
+
+	def remove(self, node):
+		"""Removes the specified node from the digraph, also removing
+		and ties to other nodes in the digraph. Does nothing if the node
+		doesn't exist."""
+		
+		if node not in self.nodes:
 			return
-		for x in self.dict[mykey][1]:
-			self.dict[x][0]=self.dict[x][0]-1
-		del self.dict[mykey]
-		while 1:
-			try:
-				self.okeys.remove(mykey)
-			except ValueError:
-				break
+		
+		for parent in self.nodes[node][1]:
+			del self.nodes[parent][0][node]
+		for child in self.nodes[node][0]:
+			del self.nodes[child][1][node]
+		
+		del self.nodes[node]
+		self.order.remove(node)
 
-	def allnodes(self):
-		"returns all nodes in the dictionary"
-		return self.dict.keys()
+	def contains(self, node):
+		"""Checks if the digraph contains mynode"""
+		return node in self.nodes
+
+	def all_nodes(self):
+		return self.order[:]
+
+	def child_nodes(self, node):
+		return self.nodes[node][0].keys()
+	
+	def parent_nodes(self, node):
+		return self.nodes[node][1].keys()
+
+	def leaf_nodes(self, include_soft_deps=False):
+		leaf_nodes = []
+		for node in self.nodes:
+			is_leaf_node = True
+			if include_soft_deps:
+				for child in self.nodes[node][0]:
+					if self.nodes[node][0][child]:
+						is_leaf_node = False
+						break
+			if is_leaf_node:
+				leaf_nodes.append(node)
+		return leaf_nodes
+
+	def is_empty(self):
+		"""Checks if the digraph is empty"""
+		return len(self.nodes) == 0
+
+	def clone(self):
+		clone = digraph()
+		clone.nodes = copy.deepcopy(self.nodes)
+		clone.order = self.order[:]
+		return clone
+
+	# Backward compatibility
+	addnode = add
+	delnode = remove
+	allnodes = all_nodes
+	allzeros = leaf_nodes
+	hasnode = contains
+	empty = is_empty
+	copy = clone
 
 	def firstzero(self):
-		"returns first node with zero references, or NULL if no such node exists"
-		for x in self.okeys:
-			if self.dict[x][0]==0:
-				return x
+		leaf_nodes = self.leaf_nodes()
+		if leaf_nodes:
+			return leaf_nodes[0]
 		return None
 
-	def depth(self, mykey):
-		depth=0
-		while (self.dict[mykey][1]):
-			depth=depth+1
-			mykey=self.dict[mykey][1][0]
-		return depth
-
-	def allzeros(self):
-		"returns all nodes with zero references, or NULL if no such node exists"
-		zerolist = []
-		for x in self.dict.keys():
-			mys = string.split(x)
-			if mys[0] != "blocks" and self.dict[x][0]==0:
-				zerolist.append(x)
-		return zerolist
-
 	def hasallzeros(self):
-		"returns 0/1, Are all nodes zeros? 1 : 0"
-		zerolist = []
-		for x in self.dict.keys():
-			if self.dict[x][0]!=0:
-				return 0
-		return 1
+		return len(self.leaf_nodes() == 0)
 
-	def empty(self):
-		if len(self.dict)==0:
-			return 1
-		return 0
+	def depth(self, node):
+		"""Find how many nodes are in the parent chain of the passed node
+		
+		This method doesn't make sense unless there is no more than one
+		parent for each node. As this digraph is capable of having multiple
+		parents on a node, this implementation chooses an arbitrary parent
+		for calculations, stopping as soon as a loop is detected in order
+		to mimic the sorts of counts that would have previously been
+		returned.
+		
+		This method is only used by emerge's --tree option. That option
+		needs to be reworked to not use this so that this method can be
+		removed altogether."""
+		
+		parents = {}
+		while self.nodes[node][1]:
+			parent = self.nodes[node][1].keys()[0]
+			if parent in parents:
+				break
+			parents[parent] = True
+			node = parent
+		return len(parents)
 
-	def hasnode(self,mynode):
-		return self.dict.has_key(mynode)
 
-	def copy(self):
-		mygraph=digraph()
-		for x in self.dict.keys():
-			mygraph.dict[x]=self.dict[x][:]
-			mygraph.okeys=self.okeys[:]
-		return mygraph
 
 def elog_process(cpv, mysettings):
 	mylogfiles = listdir(mysettings["T"]+"/logging/")
--- bin/emerge.orig	2006-09-17 14:07:15.000000000 +0000
+++ bin/emerge	2006-09-17 14:07:54.000000000 +0000
@@ -1207,8 +1207,8 @@
 			if not mycurkey:
 				print "!!! Error: circular dependencies:"
 				print
-				for x in mygraph.dict.keys():
-					for y in mygraph.dict[x][1]:
+				for x in mygraph.allnodes():
+					for y in mygraph.parent_nodes(x):
 						print y,"depends on",x
 				print
 				sys.exit(1)