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 "StandardNodePositioning.h"
\r
22 #include "StandardLayout.h"
\r
24 #include "VisibleGraph.h"
\r
26 void CStandardNodePositioning::StackSubTree
\r
27 ( CStandardLayoutNodeInfo* node
\r
28 , std::vector<long>& branchColumnStarts
\r
29 , std::vector<long>& branchColumnEnds
\r
30 , std::vector<long>& localColumnStarts
\r
31 , std::vector<long>& localColumnEnds)
\r
33 // the highest position allowed for any branch
\r
34 // (if actually reached, node must be at 0,0)
\r
36 long branchMinY = localColumnEnds[0] + node->requiredSize.cy;
\r
38 // shift subtree downwards until there is no overlap with upper sub-trees
\r
40 long subTreeMinY = 0;
\r
41 if (reduceCrossLines->IsActive())
\r
43 for (size_t i = 0, count = branchColumnStarts.size(); i < count; ++i)
\r
45 subTreeMinY = max ( subTreeMinY
\r
46 , localColumnEnds[i+1] + node->rect.Height() / 2 + 10);
\r
51 for (size_t i = 0, count = branchColumnStarts.size(); i < count; ++i)
\r
53 subTreeMinY = max ( subTreeMinY
\r
54 , localColumnEnds[i+1] - branchColumnStarts[i] + node->rect.Height() / 2 + 10);
\r
58 // store how much the sub-tree has to be shifted
\r
59 // (will be applied to .rect in a second pass)
\r
61 node->subTreeShift.cx = node->requiredSize.cx + 50;
\r
62 node->subTreeShift.cy = max (branchMinY, subTreeMinY);
\r
64 // adjust y-coord of the start node
\r
66 long nodeYShift = node->subTreeShift.cy - node->requiredSize.cy;
\r
67 node->rect.top += nodeYShift;
\r
68 node->rect.bottom += nodeYShift;
\r
70 // update column heights
\r
72 long subTreeYShift = node->subTreeShift.cy;
\r
73 localColumnStarts[0] = min (localColumnStarts[0], node->rect.top);
\r
74 localColumnEnds[0] = max (localColumnEnds[0], node->rect.top + node->requiredSize.cy);
\r
76 for (size_t i = 0, count = branchColumnStarts.size(); i < count; ++i)
\r
78 localColumnStarts[i+1] = min ( localColumnStarts[i+1]
\r
79 , subTreeYShift + branchColumnStarts[i]);
\r
80 localColumnEnds[i+1] = max ( localColumnEnds[i+1]
\r
81 , subTreeYShift + branchColumnEnds[i]);
\r
85 void CStandardNodePositioning::AppendBranch
\r
86 ( CStandardLayoutNodeInfo* start
\r
87 , std::vector<long>& columnStarts
\r
88 , std::vector<long>& columnEnds
\r
89 , std::vector<long>& localColumnStarts
\r
90 , std::vector<long>& localColumnEnds)
\r
92 // push the new branch as far to the left as possible
\r
94 size_t startsCount = columnStarts.size();
\r
95 size_t localCount = localColumnEnds.size();
\r
97 size_t insertionIndex = startsCount;
\r
98 while (insertionIndex > 0)
\r
102 , count = min (startsCount - insertionIndex+1, localCount)
\r
106 if (columnStarts [i + insertionIndex-1] < localColumnEnds [i] + 4)
\r
119 // move the whole branch to the right
\r
121 start->treeShift.cx = insertionIndex * 250;
\r
123 // update the overlapping part
\r
125 size_t offset = min (localCount, startsCount - insertionIndex);
\r
126 for (size_t i = 0; i < offset; ++i)
\r
127 columnStarts [i + insertionIndex] = localColumnStarts[i];
\r
129 // just append the column y-ranges
\r
130 // (column 0 is for the chain that starts at the "start" node)
\r
132 columnStarts.insert ( columnStarts.end()
\r
133 , localColumnStarts.begin() + offset
\r
134 , localColumnStarts.end());
\r
135 columnEnds.insert ( columnEnds.end()
\r
136 , localColumnEnds.begin() + offset
\r
137 , localColumnEnds.end());
\r
140 void CStandardNodePositioning::PlaceBranch
\r
141 ( CStandardLayoutNodeInfo* start
\r
142 , std::vector<long>& columnStarts
\r
143 , std::vector<long>& columnEnds)
\r
145 // lower + upper bounds for the start node and all its branche columns
\r
147 std::vector<long> localColumnStarts;
\r
148 std::vector<long> localColumnEnds;
\r
150 // lower + upper bounds for the columns of one sub-branch of the start node
\r
152 std::vector<long> branchColumnStarts;
\r
153 std::vector<long> branchColumnEnds;
\r
155 for ( CStandardLayoutNodeInfo* node = start
\r
157 ; node = node->nextInBranch)
\r
159 // collect branches
\r
161 branchColumnStarts.clear();
\r
162 branchColumnEnds.clear();
\r
164 for ( CStandardLayoutNodeInfo* branch = node->firstSubBranch
\r
166 ; branch = branch->nextBranch)
\r
168 PlaceBranch (branch, branchColumnStarts, branchColumnEnds);
\r
171 // stack them and this node
\r
173 size_t subTreeWidth = branchColumnEnds.size()+1;
\r
174 if (localColumnStarts.size() < subTreeWidth)
\r
176 localColumnStarts.resize (subTreeWidth, LONG_MAX);
\r
177 localColumnEnds.resize (subTreeWidth, 0);
\r
180 StackSubTree ( node
\r
181 , branchColumnStarts, branchColumnEnds
\r
182 , localColumnStarts, localColumnEnds);
\r
185 // append node and branches horizontally to sibblings of the start node
\r
187 AppendBranch ( start
\r
188 , columnStarts, columnEnds
\r
189 , localColumnStarts, localColumnEnds);
\r
192 void CStandardNodePositioning::ShiftNodes
\r
193 ( CStandardLayoutNodeInfo* node
\r
196 // walk along this branch
\r
198 delta += node->treeShift;
\r
199 for ( ; node != NULL; node = node->nextInBranch)
\r
201 node->rect += delta;
\r
202 node->subTreeShift += delta;
\r
204 // shift sub-branches
\r
206 for ( CStandardLayoutNodeInfo* branch = node->firstSubBranch
\r
208 ; branch = branch->nextBranch)
\r
210 ShiftNodes (branch, node->subTreeShift);
\r
215 CRect CStandardNodePositioning::BoundingRect
\r
216 (const CStandardLayoutNodeInfo* node)
\r
218 // walk along this branch
\r
220 CRect result = node->rect;
\r
221 for ( ; node != NULL; node = node->nextInBranch)
\r
223 result.UnionRect (result, node->rect);
\r
225 // shift sub-branches
\r
227 for ( CStandardLayoutNodeInfo* branch = node->firstSubBranch
\r
229 ; branch = branch->nextBranch)
\r
231 result.UnionRect (result, BoundingRect (branch));
\r
240 CStandardNodePositioning::CStandardNodePositioning
\r
241 ( CRevisionGraphOptionList& list)
\r
242 : CRevisionGraphOptionImpl<ILayoutOption, 200, ID_VIEW_GROUPBRANCHES> (list)
\r
243 , reduceCrossLines (NULL)
\r
247 // link to sub-option
\r
249 void CStandardNodePositioning::SetReduceCrossLines
\r
250 (IRevisionGraphOption* reduceCrossLines)
\r
252 this->reduceCrossLines = reduceCrossLines;
\r
255 // cast @a layout pointer to the respective modification
\r
256 // interface and write the data.
\r
258 void CStandardNodePositioning::ApplyTo (IRevisionGraphLayout* layout)
\r
260 // we need access to actual data
\r
262 IStandardLayoutNodeAccess* nodeAccess
\r
263 = dynamic_cast<IStandardLayoutNodeAccess*>(layout);
\r
264 if (nodeAccess == NULL)
\r
267 // calculate the displacement for every node (member subTreeShift)
\r
269 CSize treeShift (0,0);
\r
270 for (index_t i = 0, count = nodeAccess->GetNodeCount(); i < count; ++i)
\r
272 CStandardLayoutNodeInfo* node = nodeAccess->GetNode(i);
\r
273 if ( (node->node->GetPrevious() == NULL)
\r
274 && (node->node->GetCopySource() == NULL))
\r
276 // we found a root -> place it
\r
278 std::vector<long> columnStarts;
\r
279 std::vector<long> ColumnEnds;
\r
281 PlaceBranch (node, columnStarts, ColumnEnds);
\r
283 // actually move the node rects to thier final position
\r
285 ShiftNodes (node, treeShift);
\r
286 treeShift.cx = BoundingRect (node).right + 50;
\r