/b-gtk/fix-viz

To get this branch, use:
bzr branch http://gegoxaren.bato24.eu/bzr/b-gtk/fix-viz

« back to all changes in this revision

Viewing changes to viz/linegraph.py

  • Committer: Gary van der Merwe
  • Date: 2007-08-16 21:41:24 UTC
  • mto: (256.2.37 gtk)
  • mto: This revision was merged to the branch mainline in revision 289.
  • Revision ID: garyvdm@gmail.com-20070816214124-d5coudtv62jhqmio
New viz lines algorithm. Not 100% yet - but close.

Show diffs side-by-side

added added

removed removed

Lines of Context:
viz/linegraph.py
51
51
                directparent = ""
52
52
            directparentcache[childindex] = directparent
53
53
        return directparent
54
 
        
 
54
    
 
55
    def find_column_from_branchlineid(branchlineid):
 
56
        for index, column in enumerate(columns):
 
57
            if column is not None and column["branchlineid"] == branchlineid:
 
58
                return (index, column)
 
59
        return (None, None)
 
60
    
 
61
    def find_finished_child_column(index, children):
 
62
        for childrevid in children:
 
63
            childbranchlineid = branchlineids[revindex[childrevid]]
 
64
            (columnindex, column) = \
 
65
                find_column_from_branchlineid(childbranchlineid)
 
66
            if column is not None and column["maxindex"] <= index:
 
67
                return (columnindex, column)
 
68
        return (None, None)
 
69
    
 
70
    def has_no_nodes_between (column, startindex, endindex):
 
71
        for nodeindex in column["nodeindexes"]:
 
72
            if nodeindex > startindex and nodeindex < endindex:
 
73
                return False
 
74
        return True
 
75
    
 
76
    def append_line (column , startindex, endindex):
 
77
        column["lines"].append((startindex,endindex))
 
78
        if endindex > column["maxindex"] :
 
79
            column["maxindex"] = endindex
55
80
 
56
81
    
57
 
    #This will hold the branchlines that we are current tracking.
58
 
    #The position of the branchline in this list indicates the column, and it
59
 
    #it may change if we need to make space for other branchlines.
60
 
    #Each typle in the list is in the form (child index, parent revision)
61
 
    #A item may be None to indicate that there is no line for a column
62
 
    branchlines = []
 
82
    # This will hold what we plan to put in each column.
 
83
    # The position of the item in this list indicates the column, and it
 
84
    # it may change if we need to make space for other things.
 
85
    # Each typle in the list is in the form:
 
86
    # (branchlineid, nodeindexes, lines, maxindex)
 
87
    # A item may be None to indicate that there is nothing in the column
 
88
    columns = []
63
89
    
64
90
    linegraph = []
65
91
    
66
 
    lastcolour = 0
 
92
    lastbranchlineid = 0
 
93
    branchlineids = []
 
94
    revisionchildren = [[] for revision in revisions]
67
95
    
68
96
    for (index, revision) in enumerate(revisions):
69
 
        parents = [parent for parent in revisionparents[index]\
 
97
        parents = [parent for parent in revisionparents[index] \
70
98
                   if parent!="null:"]
71
 
        
72
 
        revnodecolumn = None
73
 
        
74
 
        #This will hold a list of branchlines whose parent is this rev
75
 
        branchlinesforrev = []
76
 
        
77
 
        children = []
78
 
        
79
 
        #We should maybe should pop None's at the end of branchlines.
80
 
        #I'm not sure what will cost more: resizing the list, or
81
 
        #have this loop ittrate more.
82
 
        
83
 
        #Find lines that end at this rev
84
 
        for (column, branchline) in enumerate(branchlines):
85
 
            if (branchline is not None):
86
 
                (childindex, parentrevid) = branchline
87
 
                if parentrevid == revision.revision_id:
88
 
                    branchlinesforrev.append((childindex, parentrevid, column))
89
 
                    branchlines[column] = None
90
 
                    children.append(linegraph[childindex][0].revision_id)
91
 
                    
92
 
                    #The node column for this rev will be the smallest
93
 
                    #column for the lines that end at this rev
94
 
                    #The smallest column is the first one we get to.
95
 
                    if revnodecolumn is None:
96
 
                        revnodecolumn = column
97
 
        
98
 
        #This will happen for the latest revision
99
 
        if revnodecolumn is None:
100
 
            revnodecolumn = 0
101
 
        
102
 
        colour = None
103
 
        childcolours = []
104
 
        
105
 
        #Try and see if we are the same "branch" as one of our children
106
 
        #If we are, use the childs colour
107
 
        for childrevid in children:
 
99
        for parentrevid in parents:
 
100
            if parentrevid in revindex:
 
101
                revisionchildren[revindex[parentrevid]]\
 
102
                    .append(revision.revision_id)
 
103
        
 
104
        children = revisionchildren[index]
 
105
        linegraph.append([revision, None,
 
106
                          [], parents, children])
 
107
        
 
108
        branchlineid = None
 
109
        #Try and see if we are the same branchline as one of our children
 
110
        #If we are, use the same branchlineid
 
111
        for childrevid in children: 
108
112
            childindex = revindex[childrevid]
109
113
            childsparents = revisionparents[childindex]
110
 
            childcolour = linegraph[childindex][1][1]
111
 
            childcolours.append(childcolour)
 
114
            childbranchlineid = branchlineids[childindex]
112
115
            
113
116
            if len(children) == 1 and len(childsparents) == 1: 
114
 
                # one-one relationship between parent and child, same colour
115
 
                #1st [1] selects the node
116
 
                #2nd [1] selects the colour
117
 
                colour = childcolour
 
117
                # one-one relationship between parent and child
 
118
                branchlineid = childbranchlineid
118
119
                break
119
120
            
120
121
            #Is the current revision the direct parent of the child?
121
122
            if revision.revision_id == \
122
123
                    getdirectparent(childindex, childsparents):
123
 
                colour = childcolour
 
124
                branchlineid = childbranchlineid
124
125
                break
125
126
        
126
 
        if colour is None:
127
 
            # 6 is the len of the colourwheel in graphcell
128
 
            if len(children)<6:
129
 
                while (colour is None or colour in childcolours):
130
 
                    colour = lastcolour = (lastcolour + 1) % 6
 
127
        if branchlineid is None:
 
128
            branchlineid = lastbranchlineid = lastbranchlineid + 1
 
129
        
 
130
        branchlineids.append(branchlineid)
 
131
        
 
132
        (columnindex, column) = find_column_from_branchlineid(branchlineid)
 
133
        
 
134
        if columnindex is None:
 
135
            (columnindex, column) = find_finished_child_column(index, children)
 
136
 
 
137
        
 
138
        if columnindex is None:
 
139
            columnindex = len(columns)
 
140
            column = {"branchlineid": branchlineid,
 
141
                      "nodeindexes": [index],
 
142
                      "lines": [],
 
143
                      "maxindex": index}
 
144
            columns.append(column)
 
145
        else:
 
146
            column["branchlineid"] = branchlineid
 
147
            column["nodeindexes"].append(index)
 
148
        
 
149
        opentillparent = getdirectparent(index, parents)
 
150
        if opentillparent == "":
 
151
            if len(parents)>0:
 
152
                opentillparent = parents[0]
131
153
            else:
132
 
                #If this is getting hit, we should increase the size of the
133
 
                #colourwheel
134
 
                colour = lastcolour = (lastcolour + 1) % 6
 
154
                opentillparent = None
 
155
        
 
156
        if opentillparent is not None and opentillparent in revindex:
 
157
            parentindex = revindex[opentillparent]
 
158
            if parentindex > column["maxindex"]:
 
159
                column["maxindex"] = parentindex
 
160
        
 
161
        for childrevid in children:
 
162
            childindex = revindex[childrevid]
 
163
            childbranchlineid = branchlineids[childindex]
 
164
            (childcolumnindex, childcolumn) = \
 
165
                find_column_from_branchlineid(childbranchlineid)
135
166
            
136
 
        
137
 
        #We now have every thing (except for the lines) so we can add
138
 
        #our tuple to our list.
139
 
        linegraph.append((revision, (revnodecolumn, colour),
140
 
                          [], parents, children))
141
 
        
142
 
        #add all the line bits to the rev that the branchline passes
143
 
        for (childindex, parentrevid, column) in branchlinesforrev:
144
 
            if index>childindex+1:
145
 
                #out from the child to line
146
 
                linegraph[childindex][2].append(
147
 
                    (linegraph[childindex][1][0], #the column of the child
148
 
                     column,                      #the column of the line
149
 
                     colour))
150
 
                
151
 
                #down the line
152
 
                for linepartindex in range(childindex+1, index-1):
153
 
                    linegraph[linepartindex][2].append(
154
 
                        (column,                  #the column of the line
155
 
                         column,                  #the column of the line
156
 
                         colour))
157
 
                
158
 
                #in to the parent
159
 
                linegraph[index-1][2].append(
160
 
                    (column,                      #the column of the line
161
 
                     revnodecolumn,               #the column of the parent
162
 
                     colour))
 
167
            if index-childindex == 1 or childcolumnindex is None:
 
168
                append_line(column,childindex,index)
 
169
            elif childcolumnindex >= columnindex and \
 
170
                    has_no_nodes_between(childcolumn, childindex, index):
 
171
                append_line(childcolumn,childindex,index)
 
172
            elif childcolumnindex > columnindex and \
 
173
                    has_no_nodes_between(column, childindex, index):
 
174
                append_line(column,childindex,index)
 
175
            elif childcolumnindex < columnindex and \
 
176
                    has_no_nodes_between(column, childindex, index):
 
177
                append_line(column,childindex,index)
 
178
            elif childcolumnindex < columnindex and \
 
179
                    has_no_nodes_between(childcolumn, childindex, index):
 
180
                append_line(childcolumn,childindex,index)
163
181
            else:
164
 
                #child to parent
165
 
                linegraph[childindex][2].append(
166
 
                    (linegraph[childindex][1][0], #the column of the child
167
 
                     revnodecolumn,               #the column of the parent
168
 
                     colour))
169
 
                
170
 
        for parentrevid in parents:
171
 
            column = revnodecolumn
172
 
            branchline = (index,parentrevid)
173
 
            while True:
174
 
                if column<len(branchlines):
175
 
                    if branchlines[column] is None:
176
 
                        #An empty column. Put line here
177
 
                        branchlines[column] = branchline
178
 
                        break
 
182
                columns.append({"branchlineid": None,
 
183
                                "nodeindexes": [],
 
184
                                "lines": [(childindex,index)],
 
185
                                "maxindex": index})
 
186
        
 
187
        num_of_unfinished_cols = 0
 
188
        for (columnindex, column) in enumerate(columns):
 
189
            if column is not None and column["maxindex"] > index:
 
190
                num_of_unfinished_cols += 1
 
191
        
 
192
        if num_of_unfinished_cols == 1:
 
193
            for (columnindex, column) in enumerate(columns):
 
194
                if column is not None:
 
195
                    for nodeindex in column["nodeindexes"]:
 
196
                        linegraph[nodeindex][1] = (columnindex,
 
197
                                                   branchlineids[nodeindex])
 
198
 
 
199
            for (columnindex, column) in enumerate(columns):
 
200
                for (childindex, parentindex) in column["lines"]:
 
201
                    childnode = linegraph[childindex][1]
 
202
                    parentnode = linegraph[parentindex][1]
 
203
                    if parentindex>childindex+1:
 
204
                        #out from the child to line
 
205
                        linegraph[childindex][2].append(
 
206
                            (childnode[0],    #the column of the child
 
207
                             columnindex,     #the column of the line
 
208
                             parentnode[1]))
 
209
                        
 
210
                        #down the line
 
211
                        for linepartindex in range(childindex+1, parentindex-1):
 
212
                            linegraph[linepartindex][2].append(
 
213
                                (columnindex, #the column of the line
 
214
                                 columnindex, #the column of the line
 
215
                                 parentnode[1]))
 
216
                        
 
217
                        #in to the parent
 
218
                        linegraph[parentindex-1][2].append(
 
219
                            (columnindex,     #the column of the line
 
220
                             parentnode[0],   #the column of the parent
 
221
                             parentnode[1]))
179
222
                    else:
180
 
                        if branchlines[column][0] == index:
181
 
                            #This column is allready used for a line for
182
 
                            #this rev, Move along.
183
 
                            column += 1
184
 
                        else:
185
 
                            #This column is allready used for a line for another
186
 
                            #rev. Insert her.
187
 
                            
188
 
                            #See if there is a None after us that we could
189
 
                            #move the lines after us into
190
 
                            movetocolumn = None
191
 
                            for i in \
192
 
                                    range(column+1,len(branchlines)):
193
 
                                if branchlines[i] is None:
194
 
                                    movetocolumn = i
195
 
                                    break
196
 
                            
197
 
                            if movetocolumn is None:
198
 
                                #No None was found. Insert line here
199
 
                                branchlines.insert(column, branchline)
200
 
                            else:
201
 
                                #Move the lines after us out to the None
202
 
                                for movecolumn in \
203
 
                                        reversed(range(column,movetocolumn)):
204
 
                                    branchlines[movecolumn+1] = \
205
 
                                        branchlines[movecolumn]
206
 
                                #And put line here
207
 
                                branchlines[column] = branchline
208
 
                            
209
 
                            break
 
223
                        #child to parent
 
224
                        linegraph[childindex][2].append(
 
225
                            (childnode[0],    #the column of the child
 
226
                             parentnode[0],   #the column of the parent
 
227
                             parentnode[1]))
 
228
                
 
229
                if column["maxindex"] <= index:
 
230
                    columns[columnindex] = None
210
231
                else:
211
 
                    #no more columns, so add one to the end
212
 
                    branchlines.append(branchline)
213
 
                    break
 
232
                    columns[columnindex]["nodeindexes"] = []
 
233
                    columns[columnindex]["lines"] = []
 
234
            columns = [column for column in columns if column is not None]            
214
235
 
215
236
    return linegraph
216
237