src/TortoiseProc/RevisionGraph/StandardLayout.cpp

   1 // TortoiseSVN - a Windows shell extension for easy version control\r
   2 \r
   3 // Copyright (C) 2003-2009 - 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 #include "StdAfx.h"\r
  20 #include "StandardLayout.h"\r
  21 \r
  22 #include "VisibleGraph.h"\r
  23 \r
  24 #include "StandardLayoutRectList.h"\r
  25 #include "StandardLayoutNodeList.h"\r
  26 #include "StandardLayoutConnectionList.h"\r
  27 #include "StandardLayoutTextList.h"\r
  28 \r
  29 // initialization\r
  30 \r
  31 CStandardLayoutNodeInfo::CStandardLayoutNodeInfo()\r
  32     : node (NULL)\r
  33     , firstSubBranch (NULL)\r
  34     , nextInBranch (NULL)\r
  35     , previousInBranch (NULL)\r
  36     , lastInBranch (NULL)\r
  37     , nextBranch (NULL)\r
  38     , previousBranch (NULL)\r
  39     , lastBranch (NULL)\r
  40     , rootID ((index_t)NO_INDEX)\r
  41     , subTreeWidth (1)\r
  42     , subTreeHeight (1)\r
  43     , subTreeWeight (1)\r
  44     , branchLength (1)\r
  45     , requiresRevision (true)\r
  46     , requiresPath (true)\r
  47     , requiresGap (true)\r
  48     , skipStartPathElements (0)\r
  49     , skipTailPathElements (0)\r
  50     , requiredSize (0, 0)\r
  51     , subTreeShift (0, 0)\r
  52     , treeShift (0, 0)\r
  53     , rect (0, 0, 0, 0)\r
  54         , parentBranch(NULL)\r
  55 {\r
  56 }\r
  57 \r
  58 // sort nodes: make "heaviest" branch the first one\r
  59 \r
  60 void CStandardLayout::SortNodes()\r
  61 {\r
  62     for (size_t i = 0, count = nodes.size(); i < count; ++i)\r
  63         if (nodes[i].firstSubBranch != NULL)\r
  64         {\r
  65             // find first deepest sub-branch\r
  66 \r
  67             CStandardLayoutNodeInfo* firstBranch = nodes[i].firstSubBranch;\r
  68             CStandardLayoutNodeInfo* heaviestBranch = firstBranch;\r
  69             index_t maxWeight = heaviestBranch->subTreeWeight;\r
  70 \r
  71             for ( CStandardLayoutNodeInfo* node = heaviestBranch->nextBranch\r
  72                 ; node != NULL\r
  73                 ; node = node->nextBranch)\r
  74             {\r
  75                 if (node->subTreeWeight > maxWeight)\r
  76                 {\r
  77                     maxWeight = node->subTreeWeight;\r
  78                     heaviestBranch = node;\r
  79                 }\r
  80             }\r
  81 \r
  82             // already the first one?\r
  83 \r
  84             if (firstBranch == heaviestBranch)\r
  85                 continue;\r
  86 \r
  87             // update "last" pointers, if necessary\r
  88 \r
  89             CStandardLayoutNodeInfo* nextBranch = heaviestBranch->nextBranch;\r
  90             if (nextBranch == NULL)\r
  91             {\r
  92                 CStandardLayoutNodeInfo* newLast = heaviestBranch->previousBranch;\r
  93                 for ( CStandardLayoutNodeInfo* node = firstBranch\r
  94                     ; node != NULL\r
  95                     ; node = node->nextBranch)\r
  96                 {\r
  97                     node->lastBranch = newLast;\r
  98                 }\r
  99             }\r
 100 \r
 101             // mode branch to front\r
 102 \r
 103             heaviestBranch->previousBranch->nextBranch = nextBranch;\r
 104             if (nextBranch != NULL)\r
 105                 nextBranch->previousBranch = heaviestBranch->previousBranch;\r
 106 \r
 107             heaviestBranch->previousBranch = NULL;\r
 108             heaviestBranch->nextBranch = firstBranch;\r
 109             firstBranch->previousBranch = heaviestBranch;\r
 110 \r
 111             nodes[i].firstSubBranch = heaviestBranch;\r
 112         }\r
 113 }\r
 114 \r
 115 // layout creation: \r
 116 // * create a node info object for every node\r
 117 // * calculate branch and tree sizes (in nodes)\r
 118 \r
 119 void CStandardLayout::InitializeNodes ( const CVisibleGraphNode* start\r
 120                                       , CStandardLayoutNodeInfo* parentBranch)\r
 121 {\r
 122     CStandardLayoutNodeInfo* previousInBranch = NULL;\r
 123     CStandardLayoutNodeInfo* lastInBranch = NULL;\r
 124 \r
 125     // copy this info to all sub-nodes:\r
 126 \r
 127     index_t rootID = nodes[start->GetIndex()].rootID;\r
 128 \r
 129     // measure subtree size, calculate branch length and back-link it\r
 130 \r
 131     index_t branchLength = 0;\r
 132     for ( const CVisibleGraphNode* node = start \r
 133         ; node != NULL\r
 134         ; node = node->GetNext())\r
 135     {\r
 136         // get the node, initialize it and update pointers\r
 137 \r
 138         CStandardLayoutNodeInfo& nodeInfo = nodes[node->GetIndex()];\r
 139         ++branchLength;\r
 140 \r
 141         assert (nodeInfo.node == NULL);\r
 142         nodeInfo.node = node;\r
 143         nodeInfo.rootID = rootID;\r
 144         nodeInfo.previousInBranch = previousInBranch;\r
 145         nodeInfo.parentBranch = parentBranch;\r
 146         if (previousInBranch != NULL)\r
 147             previousInBranch->nextInBranch = &nodeInfo;\r
 148         \r
 149         previousInBranch = &nodeInfo;\r
 150         lastInBranch = &nodeInfo;\r
 151 \r
 152         if (node->GetFirstCopyTarget())\r
 153         {\r
 154             CStandardLayoutNodeInfo* previousBranch = NULL;\r
 155             CStandardLayoutNodeInfo* lastBranch = NULL;\r
 156 \r
 157             // measure sub-branches and back-link them \r
 158 \r
 159             for ( const CVisibleGraphNode::CCopyTarget* \r
 160                     target = node->GetFirstCopyTarget()\r
 161                 ; target != NULL\r
 162                 ; target = target->next())\r
 163             {\r
 164                 // get sub-branch node, initialize it and update pointers\r
 165 \r
 166                 const CVisibleGraphNode* subNode = target->value();\r
 167                 CStandardLayoutNodeInfo& subNodeInfo = nodes[subNode->GetIndex()];\r
 168                 subNodeInfo.rootID = rootID;\r
 169 \r
 170                 if (previousBranch != NULL)\r
 171                 {\r
 172                     previousBranch->nextBranch = &subNodeInfo;\r
 173                     subNodeInfo.previousBranch = previousBranch;\r
 174                 }\r
 175                 else\r
 176                 {\r
 177                     // mark the first branch\r
 178 \r
 179                     nodeInfo.firstSubBranch = &subNodeInfo;\r
 180                 }\r
 181 \r
 182                 previousBranch = &subNodeInfo;\r
 183                 lastBranch = &subNodeInfo;\r
 184 \r
 185                 // add branch\r
 186 \r
 187                 InitializeNodes (subNode, &nodeInfo);\r
 188 \r
 189                 // accumulate branch into sub-tree\r
 190 \r
 191                 nodeInfo.subTreeWidth += subNodeInfo.subTreeWidth;\r
 192                 nodeInfo.subTreeWeight += subNodeInfo.subTreeWeight;\r
 193                 if (nodeInfo.subTreeHeight <= subNodeInfo.subTreeHeight)\r
 194                     nodeInfo.subTreeHeight = subNodeInfo.subTreeHeight+1;\r
 195             }\r
 196 \r
 197             // link sub-branches forward\r
 198 \r
 199             for ( const CVisibleGraphNode::CCopyTarget* \r
 200                     target = node->GetFirstCopyTarget()\r
 201                 ; target != NULL\r
 202                 ; target = target->next())\r
 203             {\r
 204                 nodes[target->value()->GetIndex()].lastBranch = lastBranch;\r
 205             }\r
 206         }\r
 207     }\r
 208 \r
 209     // write branch lengths, adjust sub-tree heights and link forward\r
 210 \r
 211     for ( const CVisibleGraphNode* node = start \r
 212         ; node != NULL\r
 213         ; node = node->GetNext())\r
 214     {\r
 215         CStandardLayoutNodeInfo& nodeInfo = nodes[node->GetIndex()];\r
 216         nodeInfo.branchLength = branchLength;\r
 217         nodeInfo.lastInBranch = lastInBranch;\r
 218 \r
 219         if (nodeInfo.subTreeHeight < branchLength)\r
 220             nodeInfo.subTreeHeight = branchLength;\r
 221     }\r
 222 }\r
 223 \r
 224 void CStandardLayout::InitializeNodes()\r
 225 {\r
 226     nodes.resize (graph->GetNodeCount());\r
 227 \r
 228     for (size_t i = 0, count = graph->GetRootCount(); i < count; ++i)\r
 229     {\r
 230         const CVisibleGraphNode* root = graph->GetRoot(i);\r
 231         nodes[root->GetIndex()].rootID = static_cast<index_t>(i);\r
 232 \r
 233         InitializeNodes (root, NULL);\r
 234     }\r
 235 \r
 236     // every node info must actually refer to a node\r
 237 \r
 238     for (size_t i = 0, count = nodes.size(); i < count; ++i)\r
 239         assert (nodes[i].node != NULL);\r
 240 \r
 241     // adjust sub-tree weights\r
 242 \r
 243     for (size_t i = nodes.size(); i > 0; --i)\r
 244     {\r
 245         CStandardLayoutNodeInfo& node = nodes[i-1];\r
 246 \r
 247         index_t weight = node.nextInBranch != NULL \r
 248                        ? node.nextInBranch->subTreeWeight+1\r
 249                        : 1;\r
 250 \r
 251         for ( CStandardLayoutNodeInfo* branch = node.firstSubBranch\r
 252             ; branch != NULL\r
 253             ; branch = branch->nextBranch)\r
 254             weight += branch->subTreeWeight;\r
 255 \r
 256         node.subTreeWeight = weight;\r
 257     }\r
 258 \r
 259     // prevent degenerated branches from growing too far to the right\r
 260 \r
 261     SortNodes();\r
 262 }\r
 263 \r
 264 // scan tree for connections between non-overlapping nodes\r
 265 \r
 266 void CStandardLayout::CreateConnections()\r
 267 {\r
 268     // there can't be more connections than nodes\r
 269 \r
 270     connections.reserve (nodes.size());\r
 271     for (index_t i = 0, count = (index_t)nodes.size(); i < count; ++i)\r
 272     {\r
 273         const CVisibleGraphNode* node = nodes[i].node;\r
 274         const CVisibleGraphNode* previousNode = node->GetSource();\r
 275 \r
 276         // skip roots\r
 277 \r
 278         if (previousNode == NULL)\r
 279             continue;\r
 280 \r
 281         // source rect\r
 282 \r
 283         const CRect& previousRect = nodes[previousNode->GetIndex()].rect;\r
 284         CRect rect = nodes[i].rect;\r
 285 \r
 286         // no line because nodes touch or overlap?\r
 287 \r
 288         rect.InflateRect (1, 1, 1, 1);\r
 289         if (TRUE == CRect().IntersectRect (rect, previousRect))\r
 290             continue;\r
 291 \r
 292         // an actual connection\r
 293 \r
 294         connections.push_back (std::make_pair (previousNode->GetIndex(), i));\r
 295     }\r
 296 }\r
 297 \r
 298 // scan tree for connections longer than 0\r
 299 \r
 300 void CStandardLayout::CreateTexts()\r
 301 {\r
 302     // there can be at most two texts per node\r
 303 \r
 304     texts.reserve (2*nodes.size());\r
 305 \r
 306     // cover all node rects \r
 307     // (connections and texts will lie within these bounds)\r
 308 \r
 309     for (index_t i = 0, count = (index_t)nodes.size(); i < count; ++i)\r
 310     {\r
 311         const CStandardLayoutNodeInfo& info = nodes[i];\r
 312 \r
 313         if (info.requiresRevision)\r
 314             texts.push_back (STextInfo (i, 0));\r
 315 \r
 316         if (info.requiresPath)\r
 317         {\r
 318             size_t visibleElementCount = info.node->GetPath().GetDepth() \r
 319                                        - info.skipStartPathElements\r
 320                                        - info.skipTailPathElements;\r
 321             for (index_t k = visibleElementCount; k > 0; --k)\r
 322                 texts.push_back (STextInfo (i, k));\r
 323         }\r
 324     }\r
 325 }\r
 326 \r
 327 // just iterate over all nodes\r
 328 \r
 329 inline bool SortRectByLeft (const CRect& lhs, const CRect& rhs)\r
 330 {\r
 331     return lhs.left < rhs.left;\r
 332 };\r
 333 \r
 334 void CStandardLayout::CloseTreeBoundingRectGaps()\r
 335 {\r
 336     std::sort (trees.begin(), trees.end(), &SortRectByLeft);\r
 337 \r
 338     for (size_t i = 1, count = trees.size(); i < count; ++i)\r
 339     {\r
 340         LONG diff = (trees[i].left - trees[i-1].right + 1) / 2;\r
 341         trees[i-1].right += diff;\r
 342         trees[i].left -= diff;\r
 343     }\r
 344 }\r
 345 \r
 346 void CStandardLayout::CalculateTreeBoundingRects()\r
 347 {\r
 348     // initialize with empty rect\r
 349 \r
 350     trees.resize (graph->GetRootCount());\r
 351     for (size_t i = 0, count = graph->GetRootCount(); i < count; ++i)\r
 352         trees[i] = CRect (0, 0, 0, 0);\r
 353 \r
 354     for (size_t i = 0, count = nodes.size(); i < count; ++i)\r
 355     {\r
 356         const CStandardLayoutNodeInfo& nodeInfo = nodes[i];\r
 357         const CSize& size = nodeInfo.requiredSize;\r
 358 \r
 359         CRect rect = nodeInfo.rect;\r
 360         rect.right = max (rect.left + size.cx, rect.right);\r
 361         rect.bottom = max (rect.top + size.cy, rect.bottom);\r
 362 \r
 363         CRect& bounds = trees[nodeInfo.rootID];\r
 364         if (bounds.Width() == 0)\r
 365             bounds = rect;\r
 366         else\r
 367             bounds |= rect;\r
 368     }\r
 369 }\r
 370 \r
 371 // just iterate over all nodes\r
 372 \r
 373 void CStandardLayout::CalculateBoundingRect()\r
 374 {\r
 375     // special case: empty graph\r
 376 \r
 377     if (nodes.empty())\r
 378     {\r
 379         boundingRect = CRect();\r
 380         return;\r
 381     }\r
 382 \r
 383     // cover all node rects \r
 384     // (connections and texts will lie within these bounds)\r
 385 \r
 386     boundingRect = trees[0];\r
 387     for (size_t i = 1, count = trees.size(); i < count; ++i)\r
 388         boundingRect |= trees[i];\r
 389 }\r
 390 \r
 391 // construction / destruction\r
 392 \r
 393 CStandardLayout::CStandardLayout ( const CCachedLogInfo* cache\r
 394                                  , const CVisibleGraph* graph)\r
 395     : cache (cache)\r
 396     , graph (graph)\r
 397 {\r
 398     InitializeNodes();\r
 399 }\r
 400 \r
 401 CStandardLayout::~CStandardLayout(void)\r
 402 {\r
 403 }\r
 404 \r
 405 // call this after executing the format options\r
 406 \r
 407 void CStandardLayout::Finalize()\r
 408 {\r
 409     CreateConnections();\r
 410     CreateTexts();\r
 411 \r
 412     CalculateTreeBoundingRects();\r
 413     CloseTreeBoundingRectGaps();\r
 414     CalculateBoundingRect();\r
 415 }\r
 416 \r
 417 /// implement IRevisionGraphLayout\r
 418 \r
 419 CRect CStandardLayout::GetRect() const\r
 420 {\r
 421     return boundingRect;\r
 422 }\r
 423 \r
 424 const ILayoutRectList* CStandardLayout::GetTrees() const\r
 425 {\r
 426     return new CStandardLayoutRectList (trees);\r
 427 }\r
 428 \r
 429 const ILayoutNodeList* CStandardLayout::GetNodes() const\r
 430 {\r
 431     return new CStandardLayoutNodeList (nodes, cache);\r
 432 }\r
 433 \r
 434 const ILayoutConnectionList* CStandardLayout::GetConnections() const\r
 435 {\r
 436     return new CStandardLayoutConnectionList (nodes, connections);\r
 437 }\r
 438 \r
 439 const ILayoutTextList* CStandardLayout::GetTexts() const\r
 440 {\r
 441     return new CStandardLayoutTextList (nodes, texts);\r
 442 }\r
 443 \r
 444 /// implement IStandardLayoutNodeAccess\r
 445 \r
 446 index_t CStandardLayout::GetNodeCount() const\r
 447 {\r
 448     return static_cast<index_t>(nodes.size());\r
 449 }\r
 450 \r
 451 CStandardLayoutNodeInfo* CStandardLayout::GetNode (index_t index)\r
 452 {\r
 453     return &nodes[index];\r
 454 }\r
 455 \r