src/TortoiseProc/RevisionGraph/StrictOrderNodePositioning.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 "StrictOrderNodePositioning.h"\r
  22 #include "StandardLayout.h"\r
  23 \r
  24 #include "VisibleGraph.h"\r
  25 \r
  26 inline bool CompareNodes \r
  27     ( const std::pair<revision_t, CStandardLayoutNodeInfo*>& lhs\r
  28     , const std::pair<revision_t, CStandardLayoutNodeInfo*>& rhs)\r
  29 {\r
  30     return lhs.first > rhs.first;\r
  31 }\r
  32 \r
  33 void CStrictOrderNodePositioning::SortRevisions \r
  34     ( IStandardLayoutNodeAccess* nodeAccess\r
  35     , std::vector<std::pair<revision_t, CStandardLayoutNodeInfo*> >& nodes)\r
  36 {\r
  37     // fill vector\r
  38 \r
  39     index_t count = nodeAccess->GetNodeCount();\r
  40     nodes.reserve (count);\r
  41     for (index_t i = 0; i < count; ++i)\r
  42     {\r
  43         CStandardLayoutNodeInfo* node = nodeAccess->GetNode(i);\r
  44         nodes.push_back (std::make_pair (node->node->GetRevision(), node));\r
  45     }\r
  46 \r
  47     // sort it\r
  48 \r
  49     std::sort (nodes.begin(), nodes.end()/*, CompareNodes*/);\r
  50 }\r
  51 \r
  52 void CStrictOrderNodePositioning::AssignColumns \r
  53     ( CStandardLayoutNodeInfo* start\r
  54     , size_t column\r
  55     , std::vector<revision_t>& startRevisions\r
  56     , std::vector<revision_t>& endRevisions\r
  57     , std::vector<int>& maxWidths)\r
  58 {\r
  59     // there should be no gaps between the branches / trees\r
  60 \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
  65 \r
  66     // this range must not be used by the column:\r
  67 \r
  68     revision_t firstRevision = start->node->GetRevision();\r
  69     revision_t lastRevision = start->lastInBranch->node->GetRevision();\r
  70 \r
  71     // find a suitable column\r
  72 \r
  73     for (; column < columCount; ++column)\r
  74         if (   (firstRevision > endRevisions[column]) \r
  75             || (lastRevision < startRevisions[column]))\r
  76         {\r
  77             break;\r
  78         }\r
  79 \r
  80     // mark this branches range as used\r
  81 \r
  82     if (columCount > column)\r
  83     {\r
  84         startRevisions[column] = min (firstRevision, startRevisions[column]);\r
  85         endRevisions[column] = max (lastRevision, endRevisions[column]);\r
  86     }\r
  87     else\r
  88     {\r
  89         startRevisions.push_back (firstRevision);\r
  90         endRevisions.push_back (lastRevision);\r
  91         maxWidths.push_back (0);\r
  92     }\r
  93 \r
  94     // prevent crossing lines / nodes\r
  95 \r
  96     if (reduceCrossLines->IsActive() && (start->parentBranch != NULL))\r
  97     {\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
 101         {\r
 102             startRevisions[i] = min (connectionFirstRevision, startRevisions[i]);\r
 103             endRevisions[i] = max (connectionLastRevision, endRevisions[i]);\r
 104         }\r
 105     }\r
 106 \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
 109 \r
 110     int maxWidth = 0;\r
 111     for ( CStandardLayoutNodeInfo* node = start->lastInBranch\r
 112         ; node != NULL\r
 113         ; node = node->previousInBranch)\r
 114     {\r
 115         node->treeShift.cx = static_cast<int>(column);\r
 116         if (node->rect.Width() > maxWidth)\r
 117             maxWidth = node->rect.Width();\r
 118 \r
 119         // add sub-branches\r
 120 \r
 121         for ( CStandardLayoutNodeInfo* branch = node->firstSubBranch\r
 122             ; branch != NULL\r
 123             ; branch = branch->nextBranch)\r
 124         {\r
 125             AssignColumns ( branch\r
 126                           , column+1\r
 127                           , startRevisions\r
 128                           , endRevisions\r
 129                           , maxWidths);\r
 130         }\r
 131     }\r
 132 \r
 133     // update column width\r
 134 \r
 135     maxWidths[column] = max (maxWidth, maxWidths[column]);\r
 136 }\r
 137 \r
 138 void CStrictOrderNodePositioning::AssignColumns \r
 139     ( std::vector<std::pair<revision_t, CStandardLayoutNodeInfo*> >& nodes\r
 140     , std::vector<int>& maxWidths)\r
 141 {\r
 142     std::vector<revision_t> startRevisions;\r
 143     std::vector<revision_t> endRevisions;\r
 144 \r
 145     startRevisions.reserve (nodes.size());\r
 146     endRevisions.reserve (nodes.size());\r
 147     maxWidths.reserve (nodes.size());\r
 148 \r
 149     for (size_t i = 0, count = nodes.size(); i < count; ++i)\r
 150     {\r
 151         CStandardLayoutNodeInfo* node = nodes[i].second;\r
 152         if (   (node->node->GetPrevious() == NULL)\r
 153             && (node->node->GetCopySource() == NULL))\r
 154         {\r
 155             AssignColumns ( node\r
 156                           , startRevisions.size()\r
 157                           , startRevisions\r
 158                           , endRevisions\r
 159                           , maxWidths);\r
 160         }\r
 161     }\r
 162 }\r
 163 \r
 164 void CStrictOrderNodePositioning::AssignRows\r
 165     (std::vector<std::pair<revision_t, CStandardLayoutNodeInfo*> >& nodes)\r
 166 {\r
 167     // keep track of every columns' top position\r
 168     // (probably fewer columns than nodes)\r
 169 \r
 170     std::vector<int> columnTops;\r
 171     columnTops.insert (columnTops.begin(), nodes.size(), 0);\r
 172 \r
 173     // next row start\r
 174 \r
 175     int rowStart = 0;\r
 176 \r
 177     // process all nodes, group by revision\r
 178     // (assign the same row to all nodes of the same revision)\r
 179 \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
 184     {\r
 185         // find the first entry that hasn't the same revision\r
 186 \r
 187         revision_t revision = nodes[rangeStart].first;\r
 188         while ((++rangeEnd < count) && (nodes[rangeEnd].first == revision));\r
 189 \r
 190         // shift row upward until all nodes match\r
 191 \r
 192         for (size_t i = rangeStart; i < rangeEnd; ++i)\r
 193         {\r
 194             // row must be larger than the top of any column changed \r
 195             // in that revision\r
 196 \r
 197             const CStandardLayoutNodeInfo* node = nodes[i].second;\r
 198             int column = node->treeShift.cx;\r
 199             rowStart = max (rowStart, columnTops[column]);\r
 200 \r
 201             // copy targets must be pushed down even further\r
 202 \r
 203             const CStandardLayoutNodeInfo* parent = node->parentBranch;\r
 204             if ((parent != NULL) && (node->previousInBranch == NULL))\r
 205             {\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
 209             }\r
 210 \r
 211             // copy sources as well\r
 212 \r
 213             if (reduceCrossLines->IsActive())\r
 214             {\r
 215                 int maxTargetColumn = column;\r
 216                 for ( const CStandardLayoutNodeInfo* subBranch = node->firstSubBranch\r
 217                     ; subBranch != NULL\r
 218                     ; subBranch = subBranch->nextBranch)\r
 219                 {\r
 220                     maxTargetColumn = max (maxTargetColumn, subBranch->treeShift.cx);\r
 221                 }\r
 222 \r
 223                 int halfHeight = node->rect.Height() / 2;\r
 224                 for (int i = column+1; i <= maxTargetColumn; ++i)\r
 225                 {\r
 226                     rowStart = max (rowStart, columnTops[i] - halfHeight + 6);\r
 227                 }\r
 228             }\r
 229         }\r
 230 \r
 231         // assign rowStarts\r
 232 \r
 233         for (size_t i = rangeStart; i < rangeEnd; ++i)\r
 234         {\r
 235             CStandardLayoutNodeInfo* node = nodes[i].second;\r
 236             int column = node->treeShift.cx;\r
 237             int height = node->rect.Height();\r
 238 \r
 239             columnTops[column] = rowStart + height;\r
 240             node->treeShift.cy = rowStart;\r
 241         }\r
 242 \r
 243         // minimum shift between consequtive revisions on different branches\r
 244 \r
 245         rowStart += 10;\r
 246     }\r
 247 }\r
 248 \r
 249 void CStrictOrderNodePositioning::ShiftNodes \r
 250     ( std::vector<std::pair<revision_t, CStandardLayoutNodeInfo*> >& nodes\r
 251     , std::vector<int>& columWidths)\r
 252 {\r
 253     // calculate column positions\r
 254 \r
 255     std::vector<int> columnPositions;\r
 256     columnPositions.reserve (columnPositions.size());\r
 257 \r
 258     int columnStart = 0;\r
 259     for (size_t i = 0, count = columWidths.size(); i < count; ++i)\r
 260     {\r
 261         columnPositions.push_back (columnStart);\r
 262         columnStart += 50 + columWidths[i];\r
 263     }\r
 264 \r
 265     // move nodes\r
 266 \r
 267     for (size_t i = 0, count = nodes.size(); i < count; ++i)\r
 268     {\r
 269         CStandardLayoutNodeInfo* node = nodes[i].second;\r
 270         CSize shift (columnPositions [node->treeShift.cx], node->treeShift.cy);\r
 271         node->rect += shift;\r
 272     }\r
 273 }\r
 274 \r
 275 // construction\r
 276 \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
 284 {\r
 285 }\r
 286 \r
 287 // implement IRevisionGraphOption: Active if standard layout is disabled.\r
 288 \r
 289 bool CStrictOrderNodePositioning::IsActive() const\r
 290 {\r
 291     return !standardNodePositioning->IsSelected();\r
 292 }\r
 293 \r
 294 // cast @a layout pointer to the respective modification\r
 295 // interface and write the data.\r
 296 \r
 297 void CStrictOrderNodePositioning::ApplyTo (IRevisionGraphLayout* layout)\r
 298 {\r
 299     // we need access to actual data\r
 300 \r
 301     IStandardLayoutNodeAccess* nodeAccess \r
 302         = dynamic_cast<IStandardLayoutNodeAccess*>(layout);\r
 303     if (nodeAccess == NULL) \r
 304         return;\r
 305 \r
 306     // assign columns and rows\r
 307 \r
 308     std::vector<std::pair<revision_t, CStandardLayoutNodeInfo*> > nodes;\r
 309     SortRevisions (nodeAccess, nodes);\r
 310 \r
 311     std::vector<int> columnWidths;\r
 312     AssignColumns (nodes, columnWidths);\r
 313     AssignRows (nodes);\r
 314 \r
 315     // post-processing\r
 316 \r
 317     ShiftNodes (nodes, columnWidths);\r
 318 }\r