Mercurial > codeOptimizer

annotate DepGraph.py @ 1:a1224150b8f6

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
Cleanup and making code easier to read.
author Tom Fredrik Blenning Klaussen <bfg@blenning.no>
date Sun, 16 Sep 2012 10:35:39 +0200
parents 28b636105ed6
children 3a56cd936c59
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
rev   line source
0
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
1 from types import *
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
2
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
3 class DepGraph:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
4 def __init__(self):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
5 self.deps = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
6 self.values = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
7
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
8 def add(self, value):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
9 if value in self.values:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
10 raise ValueError
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
11 self.values.append(value)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
12
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
13
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
14 def addDependency(self, src, dst):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
15 if not type(dst) is ListType:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
16 dst = [ dst ]
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
17
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
18 vl = len(self.values)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
19 dl = len(self.deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
20 si = self.values.index(src)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
21
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
22
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
23 if dl != vl:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
24 full = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
25 for i in range(0, vl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
26 full.append(False)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
27
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
28 exp = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
29 for i in range(dl, vl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
30 exp.append(False)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
31 self.deps.append(full[:])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
32
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
33 for i in range(0, dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
34 self.deps[i].append(exp[:])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
35
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
36 for d in dst:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
37 if d in self.values:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
38 di = self.values.index(d)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
39 self.deps[si][di] = True
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
40
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
41
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
42 @staticmethod
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
43 def directedGraphInternal(deps):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
44 dl = len(deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
45 myVals = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
46 for i in range(dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
47 if not max(deps[i]):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
48 myVals.append(i)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
49
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
50 for i in myVals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
51 for j in range(dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
52 deps[j][i] = False
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
53
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
54 retVal = myVals
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
55
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
56 if len(deps) != len(myVals):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
57 subVals = self.directedGraphInternal(deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
58 for val in myVals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
59 if val in subVals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
60 ind = subVals.index(val)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
61 del subVals[ind]
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
62
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
63 if subVals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
64 retVal.extend(subVals)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
65
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
66 return retVal
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
67
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
68 @staticmethod
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
69 def printableDepgraph(deps):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
70 res=''
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
71 for i in range(len(deps)):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
72 if res:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
73 res += '\n'
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
74 s = ''
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
75 for j in range(len(deps[i])):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
76 if deps[i][j]:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
77 s += '1'
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
78 else:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
79 s += '0'
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
80 res += s
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
81 return res
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
82
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
83 def directedGraph(self):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
84 deps = self.deps[:][:]
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
85 vals = self.directedGraphInternal(deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
86 retVal = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
87 for i in vals:
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
88 retVal.append(self.values[i])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
89 return retVal
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
90
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
91
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
92 def toplevelDependencies(self):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
93 dl = len(self.deps)
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
94 retVal = []
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
95 for i in range(dl):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
96 if not max(self.deps[i]):
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
97 print max(self.deps[i])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
98 retVal.append(self.values[i])
28b636105ed6 Working version of codeOptimizer.
Tom Fredrik Blenning Klaussen <bfg@blenning.no>
parents:
diff changeset
99 return retVal