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