src/TortoiseProc/RevisionGraph/StandardNodePositioning.cpp

   1 // TortoiseSVN - a Windows shell extension for easy version control\r
   2 \r
   3 // Copyright (C) 2003-2008 - TortoiseSVN\r
   4 \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
   9 \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
  14 \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
  18 //\r
  19 \r
  20 #include "StdAfx.h"\r
  21 #include "StandardNodePositioning.h"\r
  22 #include "StandardLayout.h"\r
  23 \r
  24 #include "VisibleGraph.h"\r
  25 \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
  32 {\r
  33     // the highest position allowed for any branch\r
  34     // (if actually reached, node must be at 0,0)\r
  35 \r
  36     long branchMinY = localColumnEnds[0] + node->requiredSize.cy;\r
  37 \r
  38     // shift subtree downwards until there is no overlap with upper sub-trees\r
  39 \r
  40     long subTreeMinY = 0;\r
  41     if (reduceCrossLines->IsActive())\r
  42     {\r
  43         for (size_t i = 0, count = branchColumnStarts.size(); i < count; ++i)\r
  44         {\r
  45             subTreeMinY = max ( subTreeMinY\r
  46                 , localColumnEnds[i+1] + node->rect.Height() / 2 + 10);\r
  47         }\r
  48     }\r
  49     else\r
  50     {\r
  51         for (size_t i = 0, count = branchColumnStarts.size(); i < count; ++i)\r
  52         {\r
  53             subTreeMinY = max ( subTreeMinY\r
  54                 , localColumnEnds[i+1] - branchColumnStarts[i] + node->rect.Height() / 2 + 10);\r
  55         }\r
  56     }\r
  57 \r
  58     // store how much the sub-tree has to be shifted\r
  59     // (will be applied to .rect in a second pass)\r
  60 \r
  61     node->subTreeShift.cx = node->requiredSize.cx + 50;\r
  62     node->subTreeShift.cy = max (branchMinY, subTreeMinY);\r
  63 \r
  64     // adjust y-coord of the start node\r
  65 \r
  66     long nodeYShift = node->subTreeShift.cy - node->requiredSize.cy;\r
  67     node->rect.top += nodeYShift;\r
  68     node->rect.bottom += nodeYShift;\r
  69 \r
  70     // update column heights\r
  71 \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
  75 \r
  76     for (size_t i = 0, count = branchColumnStarts.size(); i < count; ++i)\r
  77     {\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
  82     }\r
  83 }\r
  84 \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
  91 {\r
  92     // push the new branch as far to the left as possible\r
  93 \r
  94     size_t startsCount = columnStarts.size();\r
  95     size_t localCount = localColumnEnds.size();\r
  96 \r
  97     size_t insertionIndex = startsCount;\r
  98     while (insertionIndex > 0)\r
  99     {\r
 100         bool fits = true;\r
 101         for ( size_t i = 0\r
 102             , count = min (startsCount - insertionIndex+1, localCount)\r
 103             ; i < count\r
 104             ; ++i)\r
 105         {\r
 106             if (columnStarts [i + insertionIndex-1] < localColumnEnds [i] + 4)\r
 107             {\r
 108                 fits = false;\r
 109                 break;\r
 110             }\r
 111         }\r
 112 \r
 113         if (fits == false)\r
 114             break;\r
 115 \r
 116         --insertionIndex;\r
 117     }\r
 118 \r
 119     // move the whole branch to the right\r
 120 \r
 121     start->treeShift.cx = insertionIndex * 250;\r
 122 \r
 123     // update the overlapping part\r
 124 \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
 128 \r
 129     // just append the column y-ranges \r
 130     // (column 0 is for the chain that starts at the "start" node)\r
 131 \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
 138 }\r
 139 \r
 140 void CStandardNodePositioning::PlaceBranch \r
 141     ( CStandardLayoutNodeInfo* start\r
 142     , std::vector<long>& columnStarts\r
 143     , std::vector<long>& columnEnds)\r
 144 {\r
 145     // lower + upper bounds for the start node and all its branche columns\r
 146 \r
 147     std::vector<long> localColumnStarts;\r
 148     std::vector<long> localColumnEnds;\r
 149 \r
 150     // lower + upper bounds for the columns of one sub-branch of the start node\r
 151 \r
 152     std::vector<long> branchColumnStarts;\r
 153     std::vector<long> branchColumnEnds;\r
 154 \r
 155     for ( CStandardLayoutNodeInfo* node = start\r
 156         ; node != NULL\r
 157         ; node = node->nextInBranch)\r
 158     {\r
 159         // collect branches\r
 160 \r
 161         branchColumnStarts.clear();\r
 162         branchColumnEnds.clear();\r
 163 \r
 164         for ( CStandardLayoutNodeInfo* branch = node->firstSubBranch\r
 165             ; branch != NULL\r
 166             ; branch = branch->nextBranch)\r
 167         {\r
 168             PlaceBranch (branch, branchColumnStarts, branchColumnEnds);\r
 169         }\r
 170 \r
 171         // stack them and this node\r
 172 \r
 173         size_t subTreeWidth = branchColumnEnds.size()+1;\r
 174         if (localColumnStarts.size() < subTreeWidth)\r
 175         {\r
 176             localColumnStarts.resize (subTreeWidth, LONG_MAX);\r
 177             localColumnEnds.resize (subTreeWidth, 0);\r
 178         }\r
 179 \r
 180         StackSubTree ( node\r
 181                      , branchColumnStarts, branchColumnEnds\r
 182                      , localColumnStarts, localColumnEnds);\r
 183     }\r
 184 \r
 185     // append node and branches horizontally to sibblings of the start node\r
 186 \r
 187     AppendBranch ( start\r
 188                  , columnStarts, columnEnds\r
 189                  , localColumnStarts, localColumnEnds);\r
 190 }\r
 191 \r
 192 void CStandardNodePositioning::ShiftNodes \r
 193     ( CStandardLayoutNodeInfo* node\r
 194     , CSize delta)\r
 195 {\r
 196     // walk along this branch\r
 197 \r
 198     delta += node->treeShift;\r
 199     for ( ; node != NULL; node = node->nextInBranch)\r
 200     {\r
 201         node->rect += delta;\r
 202         node->subTreeShift += delta;\r
 203 \r
 204         // shift sub-branches\r
 205 \r
 206         for ( CStandardLayoutNodeInfo* branch = node->firstSubBranch\r
 207             ; branch != NULL\r
 208             ; branch = branch->nextBranch)\r
 209         {\r
 210             ShiftNodes (branch, node->subTreeShift);\r
 211         }\r
 212     }\r
 213 }\r
 214 \r
 215 CRect CStandardNodePositioning::BoundingRect \r
 216     (const CStandardLayoutNodeInfo* node)\r
 217 {\r
 218     // walk along this branch\r
 219 \r
 220     CRect result = node->rect;\r
 221     for ( ; node != NULL; node = node->nextInBranch)\r
 222     {\r
 223         result.UnionRect (result, node->rect);\r
 224 \r
 225         // shift sub-branches\r
 226 \r
 227         for ( CStandardLayoutNodeInfo* branch = node->firstSubBranch\r
 228             ; branch != NULL\r
 229             ; branch = branch->nextBranch)\r
 230         {\r
 231             result.UnionRect (result, BoundingRect (branch));\r
 232         }\r
 233     }\r
 234 \r
 235     return result;\r
 236 }\r
 237 \r
 238 // construction\r
 239 \r
 240 CStandardNodePositioning::CStandardNodePositioning \r
 241     ( CRevisionGraphOptionList& list)\r
 242     : CRevisionGraphOptionImpl<ILayoutOption, 200, ID_VIEW_GROUPBRANCHES> (list)\r
 243     , reduceCrossLines (NULL)\r
 244 {\r
 245 }\r
 246 \r
 247 // link to sub-option\r
 248 \r
 249 void CStandardNodePositioning::SetReduceCrossLines \r
 250     (IRevisionGraphOption* reduceCrossLines)\r
 251 {\r
 252     this->reduceCrossLines = reduceCrossLines;\r
 253 }\r
 254 \r
 255 // cast @a layout pointer to the respective modification\r
 256 // interface and write the data.\r
 257 \r
 258 void CStandardNodePositioning::ApplyTo (IRevisionGraphLayout* layout)\r
 259 {\r
 260     // we need access to actual data\r
 261 \r
 262     IStandardLayoutNodeAccess* nodeAccess \r
 263         = dynamic_cast<IStandardLayoutNodeAccess*>(layout);\r
 264     if (nodeAccess == NULL) \r
 265         return;\r
 266 \r
 267     // calculate the displacement for every node (member subTreeShift)\r
 268 \r
 269     CSize treeShift (0,0);\r
 270     for (index_t i = 0, count = nodeAccess->GetNodeCount(); i < count; ++i)\r
 271     {\r
 272         CStandardLayoutNodeInfo* node = nodeAccess->GetNode(i);\r
 273         if (   (node->node->GetPrevious() == NULL)\r
 274             && (node->node->GetCopySource() == NULL))\r
 275         {\r
 276             // we found a root -> place it\r
 277 \r
 278             std::vector<long> columnStarts;\r
 279             std::vector<long> ColumnEnds;\r
 280 \r
 281             PlaceBranch (node, columnStarts, ColumnEnds);\r
 282 \r
 283             // actually move the node rects to thier final position\r
 284 \r
 285             ShiftNodes (node, treeShift);\r
 286             treeShift.cx = BoundingRect (node).right + 50;\r
 287         }\r
 288     }\r
 289 }\r