1 // TortoiseSVN - a Windows shell extension for easy version control
\r
3 // Copyright (C) 2003-2008 - TortoiseSVN
\r
5 // This program is free software; you can redistribute it and/or
\r
6 // modify it under the terms of the GNU General Public License
\r
7 // as published by the Free Software Foundation; either version 2
\r
8 // of the License, or (at your option) any later version.
\r
10 // This program is distributed in the hope that it will be useful,
\r
11 // but WITHOUT ANY WARRANTY; without even the implied warranty of
\r
12 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
\r
13 // GNU General Public License for more details.
\r
15 // You should have received a copy of the GNU General Public License
\r
16 // along with this program; if not, write to the Free Software Foundation,
\r
17 // 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA.
\r
21 #include "StrictOrderNodePositioning.h"
\r
22 #include "StandardLayout.h"
\r
24 #include "VisibleGraph.h"
\r
26 inline bool CompareNodes
\r
27 ( const std::pair<revision_t, CStandardLayoutNodeInfo*>& lhs
\r
28 , const std::pair<revision_t, CStandardLayoutNodeInfo*>& rhs)
\r
30 return lhs.first > rhs.first;
\r
33 void CStrictOrderNodePositioning::SortRevisions
\r
34 ( IStandardLayoutNodeAccess* nodeAccess
\r
35 , std::vector<std::pair<revision_t, CStandardLayoutNodeInfo*> >& nodes)
\r
39 index_t count = nodeAccess->GetNodeCount();
\r
40 nodes.reserve (count);
\r
41 for (index_t i = 0; i < count; ++i)
\r
43 CStandardLayoutNodeInfo* node = nodeAccess->GetNode(i);
\r
44 nodes.push_back (std::make_pair (node->node->GetRevision(), node));
\r
49 std::sort (nodes.begin(), nodes.end()/*, CompareNodes*/);
\r
52 void CStrictOrderNodePositioning::AssignColumns
\r
53 ( CStandardLayoutNodeInfo* start
\r
55 , std::vector<revision_t>& startRevisions
\r
56 , std::vector<revision_t>& endRevisions
\r
57 , std::vector<int>& maxWidths)
\r
59 // there should be no gaps between the branches / trees
\r
61 size_t columCount = endRevisions.size();
\r
62 assert (columCount >= column);
\r
63 assert (columCount == startRevisions.size());
\r
64 assert (columCount == maxWidths.size());
\r
66 // this range must not be used by the column:
\r
68 revision_t firstRevision = start->node->GetRevision();
\r
69 revision_t lastRevision = start->lastInBranch->node->GetRevision();
\r
71 // find a suitable column
\r
73 for (; column < columCount; ++column)
\r
74 if ( (firstRevision > endRevisions[column])
\r
75 || (lastRevision < startRevisions[column]))
\r
80 // mark this branches range as used
\r
82 if (columCount > column)
\r
84 startRevisions[column] = min (firstRevision, startRevisions[column]);
\r
85 endRevisions[column] = max (lastRevision, endRevisions[column]);
\r
89 startRevisions.push_back (firstRevision);
\r
90 endRevisions.push_back (lastRevision);
\r
91 maxWidths.push_back (0);
\r
94 // prevent crossing lines / nodes
\r
96 if (reduceCrossLines->IsActive() && (start->parentBranch != NULL))
\r
98 revision_t connectionFirstRevision = start->parentBranch->node->GetRevision();
\r
99 revision_t connectionLastRevision = firstRevision-1;
\r
100 for (revision_t i = start->parentBranch->treeShift.cx+1; i <= column; ++i)
\r
102 startRevisions[i] = min (connectionFirstRevision, startRevisions[i]);
\r
103 endRevisions[i] = max (connectionLastRevision, endRevisions[i]);
\r
107 // assign colum to this branch and proceed with sub-branches
\r
108 // (as X coordinates, actual coordinates to be assigned in a second run)
\r
111 for ( CStandardLayoutNodeInfo* node = start->lastInBranch
\r
113 ; node = node->previousInBranch)
\r
115 node->treeShift.cx = static_cast<int>(column);
\r
116 if (node->rect.Width() > maxWidth)
\r
117 maxWidth = node->rect.Width();
\r
119 // add sub-branches
\r
121 for ( CStandardLayoutNodeInfo* branch = node->firstSubBranch
\r
123 ; branch = branch->nextBranch)
\r
125 AssignColumns ( branch
\r
133 // update column width
\r
135 maxWidths[column] = max (maxWidth, maxWidths[column]);
\r
138 void CStrictOrderNodePositioning::AssignColumns
\r
139 ( std::vector<std::pair<revision_t, CStandardLayoutNodeInfo*> >& nodes
\r
140 , std::vector<int>& maxWidths)
\r
142 std::vector<revision_t> startRevisions;
\r
143 std::vector<revision_t> endRevisions;
\r
145 startRevisions.reserve (nodes.size());
\r
146 endRevisions.reserve (nodes.size());
\r
147 maxWidths.reserve (nodes.size());
\r
149 for (size_t i = 0, count = nodes.size(); i < count; ++i)
\r
151 CStandardLayoutNodeInfo* node = nodes[i].second;
\r
152 if ( (node->node->GetPrevious() == NULL)
\r
153 && (node->node->GetCopySource() == NULL))
\r
155 AssignColumns ( node
\r
156 , startRevisions.size()
\r
164 void CStrictOrderNodePositioning::AssignRows
\r
165 (std::vector<std::pair<revision_t, CStandardLayoutNodeInfo*> >& nodes)
\r
167 // keep track of every columns' top position
\r
168 // (probably fewer columns than nodes)
\r
170 std::vector<int> columnTops;
\r
171 columnTops.insert (columnTops.begin(), nodes.size(), 0);
\r
177 // process all nodes, group by revision
\r
178 // (assign the same row to all nodes of the same revision)
\r
180 size_t rangeEnd = 0;
\r
181 for ( size_t rangeStart = rangeEnd, count = nodes.size()
\r
182 ; rangeStart < count
\r
183 ; rangeStart = rangeEnd)
\r
185 // find the first entry that hasn't the same revision
\r
187 revision_t revision = nodes[rangeStart].first;
\r
188 while ((++rangeEnd < count) && (nodes[rangeEnd].first == revision));
\r
190 // shift row upward until all nodes match
\r
192 for (size_t i = rangeStart; i < rangeEnd; ++i)
\r
194 // row must be larger than the top of any column changed
\r
195 // in that revision
\r
197 const CStandardLayoutNodeInfo* node = nodes[i].second;
\r
198 int column = node->treeShift.cx;
\r
199 rowStart = max (rowStart, columnTops[column]);
\r
201 // copy targets must be pushed down even further
\r
203 const CStandardLayoutNodeInfo* parent = node->parentBranch;
\r
204 if ((parent != NULL) && (node->previousInBranch == NULL))
\r
206 int sourceBottom = parent->rect.bottom + parent->treeShift.cy;
\r
207 rowStart = max (rowStart, sourceBottom);
\r
208 rowStart = max (rowStart, columnTops[column] + 6);
\r
211 // copy sources as well
\r
213 if (reduceCrossLines->IsActive())
\r
215 int maxTargetColumn = column;
\r
216 for ( const CStandardLayoutNodeInfo* subBranch = node->firstSubBranch
\r
217 ; subBranch != NULL
\r
218 ; subBranch = subBranch->nextBranch)
\r
220 maxTargetColumn = max (maxTargetColumn, subBranch->treeShift.cx);
\r
223 int halfHeight = node->rect.Height() / 2;
\r
224 for (int i = column+1; i <= maxTargetColumn; ++i)
\r
226 rowStart = max (rowStart, columnTops[i] - halfHeight + 6);
\r
231 // assign rowStarts
\r
233 for (size_t i = rangeStart; i < rangeEnd; ++i)
\r
235 CStandardLayoutNodeInfo* node = nodes[i].second;
\r
236 int column = node->treeShift.cx;
\r
237 int height = node->rect.Height();
\r
239 columnTops[column] = rowStart + height;
\r
240 node->treeShift.cy = rowStart;
\r
243 // minimum shift between consequtive revisions on different branches
\r
249 void CStrictOrderNodePositioning::ShiftNodes
\r
250 ( std::vector<std::pair<revision_t, CStandardLayoutNodeInfo*> >& nodes
\r
251 , std::vector<int>& columWidths)
\r
253 // calculate column positions
\r
255 std::vector<int> columnPositions;
\r
256 columnPositions.reserve (columnPositions.size());
\r
258 int columnStart = 0;
\r
259 for (size_t i = 0, count = columWidths.size(); i < count; ++i)
\r
261 columnPositions.push_back (columnStart);
\r
262 columnStart += 50 + columWidths[i];
\r
267 for (size_t i = 0, count = nodes.size(); i < count; ++i)
\r
269 CStandardLayoutNodeInfo* node = nodes[i].second;
\r
270 CSize shift (columnPositions [node->treeShift.cx], node->treeShift.cy);
\r
271 node->rect += shift;
\r
277 CStrictOrderNodePositioning::CStrictOrderNodePositioning
\r
278 ( CRevisionGraphOptionList& list
\r
279 , IRevisionGraphOption* standardNodePositioning
\r
280 , IRevisionGraphOption* reduceCrossLines)
\r
281 : CRevisionGraphOptionImpl<ILayoutOption, 200, 0> (list)
\r
282 , standardNodePositioning (standardNodePositioning)
\r
283 , reduceCrossLines (reduceCrossLines)
\r
287 // implement IRevisionGraphOption: Active if standard layout is disabled.
\r
289 bool CStrictOrderNodePositioning::IsActive() const
\r
291 return !standardNodePositioning->IsSelected();
\r
294 // cast @a layout pointer to the respective modification
\r
295 // interface and write the data.
\r
297 void CStrictOrderNodePositioning::ApplyTo (IRevisionGraphLayout* layout)
\r
299 // we need access to actual data
\r
301 IStandardLayoutNodeAccess* nodeAccess
\r
302 = dynamic_cast<IStandardLayoutNodeAccess*>(layout);
\r
303 if (nodeAccess == NULL)
\r
306 // assign columns and rows
\r
308 std::vector<std::pair<revision_t, CStandardLayoutNodeInfo*> > nodes;
\r
309 SortRevisions (nodeAccess, nodes);
\r
311 std::vector<int> columnWidths;
\r
312 AssignColumns (nodes, columnWidths);
\r
313 AssignRows (nodes);
\r
317 ShiftNodes (nodes, columnWidths);
\r