[patch] New digraph

new-digraph.patch (text/plain), 5.51 KB, created by Jason Stubbs (RETIRED) on 2006-09-15 22:32:13 UTC

--- pym/portage.py.orig	2006-09-17 01:39:25.000000000 +0000
+++ pym/portage.py	2006-09-17 14:25:19.000000000 +0000
@@ -313,84 +313,125 @@
 
 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 addnode(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 delnode(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()
+		return self.order[:]
 
 	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
+		"""Returns the first node with no children or else the first node
+		only soft-deps on children. Returns None if all children on every
+		node are hard-deps."""
+		
+		for node in self.order:
+			if not self.nodes[node][0]:
+				return node
 		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
+		zeros = []
+		for node in self.nodes:
+			if not self.nodes[node][0]:
+				zeros.append(node)
+		return zeros
+
+	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 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
+		for node in self.nodes:
+			if self.nodes[node][0]:
+				return False
+		return True
 
 	def empty(self):
-		if len(self.dict)==0:
-			return 1
-		return 0
+		"""Checks if the digraph is empty"""
+		return len(self.nodes) == 0
 
-	def hasnode(self,mynode):
-		return self.dict.has_key(mynode)
+	def hasnode(self, node):
+		"""Checks if the digraph contains mynode"""
+		return node in self.nodes
 
 	def copy(self):
-		mygraph=digraph()
-		for x in self.dict.keys():
-			mygraph.dict[x]=self.dict[x][:]
-			mygraph.okeys=self.okeys[:]
-		return mygraph
+		clone = digraph()
+		clone.nodes = copy.deepcopy(self.nodes)
+		clone.order = self.order[:]
+		return clone
+	
+	def child_nodes(self, node):
+		return self.nodes[node][0].keys()
+	
+	def parent_nodes(self, node):
+		return self.nodes[node][1].keys()
+
 
 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)