src/TortoiseProc/lanes.cpp

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