src/TortoiseProc/lanes.cpp

   1 /*\r
   2         Description: history graph computation\r
   3 \r
   4         Author: Marco Costalba (C) 2005-2007\r
   5 \r
   6         Copyright: See COPYING file that comes with this distribution\r
   7 \r
   8 */\r
   9 #include "stdafx.h"\r
  10 #include "lanes.h"\r
  11 \r
  12 #define IS_NODE(x) (x == NODE || x == NODE_R || x == NODE_L)\r
  13 \r
  14 \r
  15 void Lanes::init(const QString& expectedSha) {\r
  16 \r
  17         clear();\r
  18         activeLane = 0;\r
  19         setBoundary(false);\r
  20         add(BRANCH, expectedSha, activeLane);\r
  21 }\r
  22 \r
  23 void Lanes::clear() {\r
  24 \r
  25         typeVec.clear();\r
  26         nextShaVec.clear();\r
  27 }\r
  28 \r
  29 void Lanes::setBoundary(bool b) {\r
  30 // changes the state so must be called as first one\r
  31 \r
  32         NODE   = b ? BOUNDARY_C : MERGE_FORK;\r
  33         NODE_R = b ? BOUNDARY_R : MERGE_FORK_R;\r
  34         NODE_L = b ? BOUNDARY_L : MERGE_FORK_L;\r
  35         boundary = b;\r
  36 \r
  37         if (boundary)\r
  38                 typeVec[activeLane] = BOUNDARY;\r
  39 }\r
  40 \r
  41 bool Lanes::isFork(const QString& sha, bool& isDiscontinuity) {\r
  42 \r
  43         int pos = findNextSha(sha, 0);\r
  44         isDiscontinuity = (activeLane != pos);\r
  45         if (pos == -1) // new branch case\r
  46                 return false;\r
  47 \r
  48         return (findNextSha(sha, pos + 1) != -1);\r
  49 /*\r
  50         int cnt = 0;\r
  51         while (pos != -1) {\r
  52                 cnt++;\r
  53                 pos = findNextSha(sha, pos + 1);\r
  54 //              if (isDiscontinuity)\r
  55 //                      isDiscontinuity = (activeLane != pos);\r
  56         }\r
  57         return (cnt > 1);\r
  58 */\r
  59 }\r
  60 \r
  61 void Lanes::setFork(const QString& sha) {\r
  62 \r
  63         int rangeStart, rangeEnd, idx;\r
  64         rangeStart = rangeEnd = idx = findNextSha(sha, 0);\r
  65 \r
  66         while (idx != -1) {\r
  67                 rangeEnd = idx;\r
  68                 typeVec[idx] = TAIL;\r
  69                 idx = findNextSha(sha, idx + 1);\r
  70         }\r
  71         typeVec[activeLane] = NODE;\r
  72 \r
  73         int& startT = typeVec[rangeStart];\r
  74         int& endT = typeVec[rangeEnd];\r
  75 \r
  76         if (startT == NODE)\r
  77                 startT = NODE_L;\r
  78 \r
  79         if (endT == NODE)\r
  80                 endT = NODE_R;\r
  81 \r
  82         if (startT == TAIL)\r
  83                 startT = TAIL_L;\r
  84 \r
  85         if (endT == TAIL)\r
  86                 endT = TAIL_R;\r
  87 \r
  88         for (int i = rangeStart + 1; i < rangeEnd; i++) {\r
  89 \r
  90                 int& t = typeVec[i];\r
  91 \r
  92                 if (t == NOT_ACTIVE)\r
  93                         t = CROSS;\r
  94 \r
  95                 else if (t == EMPTY)\r
  96                         t = CROSS_EMPTY;\r
  97         }\r
  98 }\r
  99 \r
 100 void Lanes::setMerge(const QStringList& parents) {\r
 101 // setFork() must be called before setMerge()\r
 102 \r
 103         if (boundary)\r
 104                 return; // handle as a simple active line\r
 105 \r
 106         int& t = typeVec[activeLane];\r
 107         bool wasFork   = (t == NODE);\r
 108         bool wasFork_L = (t == NODE_L);\r
 109         bool wasFork_R = (t == NODE_R);\r
 110         bool startJoinWasACross = false, endJoinWasACross = false;\r
 111 \r
 112         t = NODE;\r
 113 \r
 114         int rangeStart = activeLane, rangeEnd = activeLane;\r
 115         QStringList::const_iterator it(parents.begin());\r
 116         for (++it; it != parents.end(); ++it) { // skip first parent\r
 117 \r
 118                 int idx = findNextSha(*it, 0);\r
 119                 if (idx != -1) {\r
 120 \r
 121                         if (idx > rangeEnd) {\r
 122 \r
 123                                 rangeEnd = idx;\r
 124                                 endJoinWasACross = typeVec[idx] == CROSS;\r
 125                         }\r
 126 \r
 127                         if (idx < rangeStart) {\r
 128 \r
 129                                 rangeStart = idx;\r
 130                                 startJoinWasACross = typeVec[idx] == CROSS;\r
 131                         }\r
 132 \r
 133                         typeVec[idx] = JOIN;\r
 134                 } else\r
 135                         rangeEnd = add(HEAD, *it, rangeEnd + 1);\r
 136         }\r
 137         int& startT = typeVec[rangeStart];\r
 138         int& endT = typeVec[rangeEnd];\r
 139 \r
 140         if (startT == NODE && !wasFork && !wasFork_R)\r
 141                 startT = NODE_L;\r
 142 \r
 143         if (endT == NODE && !wasFork && !wasFork_L)\r
 144                 endT = NODE_R;\r
 145 \r
 146         if (startT == JOIN && !startJoinWasACross)\r
 147                 startT = JOIN_L;\r
 148 \r
 149         if (endT == JOIN && !endJoinWasACross)\r
 150                 endT = JOIN_R;\r
 151 \r
 152         if (startT == HEAD)\r
 153                 startT = HEAD_L;\r
 154 \r
 155         if (endT == HEAD)\r
 156                 endT = HEAD_R;\r
 157 \r
 158         for (int i = rangeStart + 1; i < rangeEnd; i++) {\r
 159 \r
 160                 int& t = typeVec[i];\r
 161 \r
 162                 if (t == NOT_ACTIVE)\r
 163                         t = CROSS;\r
 164 \r
 165                 else if (t == EMPTY)\r
 166                         t = CROSS_EMPTY;\r
 167 \r
 168                 else if (t == TAIL_R || t == TAIL_L)\r
 169                         t = TAIL;\r
 170         }\r
 171 }\r
 172 \r
 173 void Lanes::setInitial() {\r
 174 \r
 175         int& t = typeVec[activeLane];\r
 176         if (!IS_NODE(t) && t != APPLIED)\r
 177                 t = (boundary ? BOUNDARY : INITIAL);\r
 178 }\r
 179 \r
 180 void Lanes::setApplied() {\r
 181 \r
 182         // applied patches are not merges, nor forks\r
 183         typeVec[activeLane] = APPLIED; // TODO test with boundaries\r
 184 }\r
 185 \r
 186 void Lanes::changeActiveLane(const QString& sha) {\r
 187 \r
 188         int& t = typeVec[activeLane];\r
 189         if (t == INITIAL || isBoundary(t))\r
 190                 t = EMPTY;\r
 191         else\r
 192                 t = NOT_ACTIVE;\r
 193 \r
 194         int idx = findNextSha(sha, 0); // find first sha\r
 195         if (idx != -1)\r
 196                 typeVec[idx] = ACTIVE; // called before setBoundary()\r
 197         else\r
 198                 idx = add(BRANCH, sha, activeLane); // new branch\r
 199 \r
 200         activeLane = idx;\r
 201 }\r
 202 \r
 203 void Lanes::afterMerge() {\r
 204 \r
 205         if (boundary)\r
 206                 return; // will be reset by changeActiveLane()\r
 207 \r
 208         for (unsigned int i = 0; i < typeVec.size(); i++) {\r
 209 \r
 210                 int& t = typeVec[i];\r
 211 \r
 212                 if (isHead(t) || isJoin(t) || t == CROSS)\r
 213                         t = NOT_ACTIVE;\r
 214 \r
 215                 else if (t == CROSS_EMPTY)\r
 216                         t = EMPTY;\r
 217 \r
 218                 else if (IS_NODE(t))\r
 219                         t = ACTIVE;\r
 220         }\r
 221 }\r
 222 \r
 223 void Lanes::afterFork() {\r
 224 \r
 225         for (unsigned int i = 0; i < typeVec.size(); i++) {\r
 226 \r
 227                 int& t = typeVec[i];\r
 228 \r
 229                 if (t == CROSS)\r
 230                         t = NOT_ACTIVE;\r
 231 \r
 232                 else if (isTail(t) || t == CROSS_EMPTY)\r
 233                         t = EMPTY;\r
 234 \r
 235                 if (!boundary && IS_NODE(t))\r
 236                         t = ACTIVE; // boundary will be reset by changeActiveLane()\r
 237         }\r
 238         while (typeVec.back() == EMPTY) {\r
 239                 typeVec.pop_back();\r
 240                 nextShaVec.pop_back();\r
 241         }\r
 242 }\r
 243 \r
 244 bool Lanes::isBranch() {\r
 245 \r
 246         return (typeVec[activeLane] == BRANCH);\r
 247 }\r
 248 \r
 249 void Lanes::afterBranch() {\r
 250 \r
 251         typeVec[activeLane] = ACTIVE; // TODO test with boundaries\r
 252 }\r
 253 \r
 254 void Lanes::afterApplied() {\r
 255 \r
 256         typeVec[activeLane] = ACTIVE; // TODO test with boundaries\r
 257 }\r
 258 \r
 259 void Lanes::nextParent(const QString& sha) {\r
 260 \r
 261         nextShaVec[activeLane] = (boundary ? QString(_T("")) : sha);\r
 262 }\r
 263 \r
 264 int Lanes::findNextSha(const QString& next, int pos) {\r
 265 \r
 266         for (unsigned int i = pos; i < nextShaVec.size(); i++)\r
 267                 if (nextShaVec[i] == next)\r
 268                         return i;\r
 269         return -1;\r
 270 }\r
 271 \r
 272 int Lanes::findType(int type, int pos) {\r
 273 \r
 274         for (unsigned int i = pos; i < typeVec.size(); i++)\r
 275                 if (typeVec[i] == type)\r
 276                         return i;\r
 277         return -1;\r
 278 }\r
 279 \r
 280 int Lanes::add(int type, const QString& next, int pos) {\r
 281 \r
 282         // first check empty lanes starting from pos\r
 283         if (pos < (int)typeVec.size()) {\r
 284                 pos = findType(EMPTY, pos);\r
 285                 if (pos != -1) {\r
 286                         typeVec[pos] = type;\r
 287                         nextShaVec[pos] = next;\r
 288                         return pos;\r
 289                 }\r
 290         }\r
 291         // if all lanes are occupied add a new lane\r
 292         typeVec.push_back(type);\r
 293         nextShaVec.push_back(next);\r
 294         return typeVec.size() - 1;\r
 295 }\r