Src/DiffList.cpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //    License (GPLv2+):
   3 //    This program is free software; you can redistribute it and/or modify
   4 //    it under the terms of the GNU General Public License as published by
   5 //    the Free Software Foundation; either version 2 of the License, or (at
   6 //    your option) any later version.
   7 //
   8 //    This program is distributed in the hope that it will be useful, but
   9 //    WITHOUT ANY WARRANTY; without even the implied warranty of
  10 //    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  11 //    GNU General Public License for more details.
  12 //
  13 //    You should have received a copy of the GNU General Public License
  14 //    along with this program; if not, write to the Free Software
  15 //    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
  16 /////////////////////////////////////////////////////////////////////////////
  17 /**
  18  * @file  DiffList.cpp
  19  *
  20  * @brief Implementation file for DiffList class
  21  */
  22
  23 #include "DiffList.h"
  24 #include <cassert>
  25 #include <string>
  26 #include <sstream>
  27 #include <algorithm>
  28
  29 using std::swap;
  30 using std::vector;
  31
  32 /**
  33  * @brief Swap diff sides.
  34  */
  35 void DIFFRANGE::swap_sides(int index1, int index2)
  36 {
  37         swap(begin[index1], begin[index2]);
  38         swap(end[index1], end[index2]);
  39         swap(blank[index1], blank[index2]);
  40 }
  41
  42 /**
  43  * @brief Initialize DiffMap.
  44  * @param [in] nlines Lines to add to the list.
  45  */
  46 void DiffMap::InitDiffMap(int nlines)
  47 {
  48         // sentry value so we can check later that we set them all
  49         m_map.assign(nlines, BAD_MAP_ENTRY);
  50 }
  51
  52
  53 /**
  54  * @brief Default constructor, initialises difflist to 64 items.
  55  */
  56 DiffList::DiffList()
  57 : m_firstSignificant(-1)
  58 , m_lastSignificant(-1)
  59 , m_firstSignificantLeftMiddle(-1)
  60 , m_firstSignificantLeftRight(-1)
  61 , m_firstSignificantMiddleRight(-1)
  62 , m_firstSignificantLeftOnly(-1)
  63 , m_firstSignificantMiddleOnly(-1)
  64 , m_firstSignificantRightOnly(-1)
  65 , m_firstSignificantConflict(-1)
  66 , m_lastSignificantLeftMiddle(-1)
  67 , m_lastSignificantLeftRight(-1)
  68 , m_lastSignificantMiddleRight(-1)
  69 , m_lastSignificantLeftOnly(-1)
  70 , m_lastSignificantMiddleOnly(-1)
  71 , m_lastSignificantRightOnly(-1)
  72 , m_lastSignificantConflict(-1)
  73 {
  74         m_diffs.reserve(64); // Reserve some initial space to avoid allocations.
  75 }
  76
  77 /**
  78  * @brief Removes all diffs from list.
  79  */
  80 void DiffList::Clear()
  81 {
  82         m_diffs.clear();
  83         m_firstSignificant = -1;
  84         m_lastSignificant = -1;
  85         m_firstSignificantLeftMiddle = -1;
  86         m_firstSignificantLeftRight = -1;
  87         m_firstSignificantMiddleRight = -1;
  88         m_firstSignificantLeftOnly = -1;
  89         m_firstSignificantMiddleOnly = -1;
  90         m_firstSignificantRightOnly = -1;
  91         m_firstSignificantConflict = -1;
  92         m_lastSignificantLeftMiddle = -1;
  93         m_lastSignificantLeftRight = -1;
  94         m_lastSignificantMiddleRight = -1;
  95         m_lastSignificantLeftOnly = -1;
  96         m_lastSignificantMiddleOnly = -1;
  97         m_lastSignificantRightOnly = -1;
  98         m_lastSignificantConflict = -1;
  99 }
 100
 101 /**
 102  * @brief Returns count of items in diff list.
 103  * This function returns total amount of items (diffs) in list. So returned
 104  * count includes significant and non-significant diffs.
 105  * @note Use GetSignificantDiffs() to get count of non-ignored diffs.
 106  */
 107 int DiffList::GetSize() const
 108 {
 109         return (int) m_diffs.size();
 110 }
 111
 112 /**
 113  * @brief Returns count of significant diffs in the list.
 114  * This function returns total count of significant diffs in list. So returned
 115  * count doesn't include non-significant diffs.
 116  * @return Count of significant differences.
 117  */
 118 int DiffList::GetSignificantDiffs() const
 119 {
 120         int nSignificants = 0;
 121         const int nDiffCount = (int) m_diffs.size();
 122
 123         for (int i = 0; i < nDiffCount; i++)
 124         {
 125                 const DIFFRANGE * dfi = DiffRangeAt(i);
 126                 if (dfi->op != OP_TRIVIAL)
 127                 {
 128                         ++nSignificants;
 129                 }
 130         }
 131         return nSignificants;
 132 }
 133
 134 /**
 135  * @brief Adds given diff to end of the list.
 136  * Adds given difference to end of the list (append).
 137  * @param [in] di Difference to add.
 138  */
 139 void DiffList::AddDiff(const DIFFRANGE & di)
 140 {
 141         DiffRangeInfo dri(di);
 142
 143         // Allocate memory for new items exponentially
 144         if (m_diffs.size() == m_diffs.capacity())
 145                 m_diffs.reserve(m_diffs.size() * 2);
 146         m_diffs.push_back(dri);
 147 }
 148
 149 /**
 150  * @brief Checks if diff in given list index is significant or not.
 151  * @param [in] nDiff Index of DIFFRANGE to check.
 152  * @return true if diff is significant, false if not.
 153  */
 154 bool DiffList::IsDiffSignificant(int nDiff) const
 155 {
 156         const DIFFRANGE * dfi = DiffRangeAt(nDiff);
 157         if (dfi->op != OP_TRIVIAL)
 158                 return true;
 159         else
 160                 return false;
 161 }
 162
 163 /**
 164  * @brief Get significant difference index of the diff.
 165  * This function returns the index of diff when only significant differences
 166  * are calculated.
 167  * @param [in] nDiff Index of difference to check.
 168  * @return Significant difference index of the diff.
 169  */
 170 int DiffList::GetSignificantIndex(int nDiff) const
 171 {
 172         int significants = -1;
 173
 174         for (int i = 0; i <= nDiff; i++)
 175         {
 176                 const DIFFRANGE * dfi = DiffRangeAt(i);
 177                 if (dfi->op != OP_TRIVIAL)
 178                 {
 179                         ++significants;
 180                 }
 181         }
 182         return significants;
 183 }
 184
 185 /**
 186  * @brief Returns copy of DIFFRANGE from diff-list.
 187  * @param [in] nDiff Index of DIFFRANGE to return.
 188  * @param [out] di DIFFRANGE returned (empty if error)
 189  * @return true if DIFFRANGE found from given index.
 190  */
 191 bool DiffList::GetDiff(int nDiff, DIFFRANGE & di) const
 192 {
 193         const DIFFRANGE * dfi = DiffRangeAt(nDiff);
 194         if (!dfi)
 195         {
 196                 DIFFRANGE empty;
 197                 di = empty;
 198                 return false;
 199         }
 200         di = *dfi;
 201         return true;
 202 }
 203
 204 /**
 205  * @brief Return constant pointer to requested diff.
 206  * This function returns constant pointer to DIFFRANGE at given index.
 207  * @param [in] nDiff Index of DIFFRANGE to return.
 208  * @return Constant pointer to DIFFRANGE.
 209  */
 210 const DIFFRANGE * DiffList::DiffRangeAt(int nDiff) const
 211 {
 212         if (nDiff >= 0 && nDiff < (int) m_diffs.size())
 213         {
 214                 return &m_diffs[nDiff];
 215         }
 216         else
 217         {
 218                 assert(0);
 219                 return NULL;
 220         }
 221 }
 222
 223 /**
 224  * @brief Replaces diff in list in given index with given diff.
 225  * @param [in] nDiff Index (0-based) of diff to be replaced
 226  * @param [in] di Diff to put in list.
 227  * @return true if index was valid and diff put to list.
 228  */
 229 bool DiffList::SetDiff(int nDiff, const DIFFRANGE & di)
 230 {
 231         if (nDiff < (int) m_diffs.size())
 232         {
 233                 m_diffs[nDiff] = DiffRangeInfo(di);
 234                 return true;
 235         }
 236         else
 237                 return false;
 238 }
 239
 240 /**
 241  * @brief Checks if line is before, inside or after diff
 242  * @param [in] nLine Linenumber to text buffer (not "real" number)
 243  * @param [in] nDiff Index to diff table
 244  * @return -1 if line is before diff, 0 if line is in diff and
 245  * 1 if line is after diff.
 246  */
 247 int DiffList::LineRelDiff(int nLine, int nDiff) const
 248 {
 249         const DIFFRANGE * dfi = DiffRangeAt(nDiff);
 250         if (static_cast<int>(nLine) < dfi->dbegin)
 251                 return -1;
 252         else if (static_cast<int>(nLine) > dfi->dend)
 253                 return 1;
 254         else
 255                 return 0;
 256 }
 257
 258 /**
 259  * @brief Checks if line is inside given diff
 260  * @param [in] nLine Linenumber to text buffer (not "real" number)
 261  * @param [in] nDiff Index to diff table
 262  * @return true if line is inside given difference.
 263  */
 264 bool DiffList::LineInDiff(int nLine, int nDiff) const
 265 {
 266         const DIFFRANGE * dfi = DiffRangeAt(nDiff);
 267         if (static_cast<int>(nLine) >= dfi->dbegin && static_cast<int>(nLine) <= dfi->dend)
 268                 return true;
 269         else
 270                 return false;
 271 }
 272
 273 /**
 274  * @brief Returns diff index for given line.
 275  * @param [in] nLine Linenumber, 0-based.
 276  * @return Index to diff table, -1 if line is not inside any diff.
 277  */
 278 int DiffList::LineToDiff(int nLine) const
 279 {
 280         const int nDiffCount = static_cast<int>(m_diffs.size());
 281         if (nDiffCount == 0)
 282                 return -1;
 283
 284         // First check line is not before first or after last diff
 285         if (nLine < DiffRangeAt(0)->dbegin)
 286                 return -1;
 287         if (nLine > DiffRangeAt(nDiffCount-1)->dend)
 288                 return -1;
 289
 290         // Use binary search to search for a diff.
 291         int left = 0; // Left limit
 292         int right = nDiffCount - 1; // Right limit
 293
 294         while (left <= right)
 295         {
 296                 int middle = (left + right) / 2; // Compared item
 297                 int result = LineRelDiff(nLine, middle);
 298                 switch (result)
 299                 {
 300                 case -1: // Line is before diff in file
 301                         right = middle - 1;
 302                         break;
 303                 case 0: // Line is in diff
 304                         return middle;
 305                         break;
 306                 case 1: // Line is after diff in file
 307                         left = middle + 1;
 308                         break;
 309                 default:
 310                         {
 311                         std::stringstream s;
 312                         s << "Invalid return value " << result << " from LineRelDiff(): -1, 0 or 1 expected!";
 313                         throw s.str();
 314                         }
 315                 }
 316         }
 317         return -1;
 318 }
 319
 320 /**
 321  * @brief Return previous diff from given line.
 322  * @param [in] nLine First line searched.
 323  * @param [out] nDiff Index of diff found.
 324  * @return true if line is inside diff, false otherwise.
 325  */
 326 bool DiffList::GetPrevDiff(int nLine, int & nDiff) const
 327 {
 328         bool bInDiff = true;
 329         int numDiff = LineToDiff(nLine);
 330
 331         // Line not inside diff
 332         if (nDiff == -1)
 333         {
 334                 bInDiff = false;
 335                 const int size = (int) m_diffs.size();
 336                 for (int i = (int) size - 1; i >= 0 ; i--)
 337                 {
 338                         if ((int)DiffRangeAt(i)->dend <= nLine)
 339                         {
 340                                 numDiff = i;
 341                                 break;
 342                         }
 343                 }
 344         }
 345         nDiff = numDiff;
 346         return bInDiff;
 347 }
 348
 349 /**
 350  * @brief Return next difference from given line.
 351  * This function finds next difference from given line. If line is inside
 352  * difference, that difference is returned. If next difference is not found
 353  * param @p nDiff is set to -1.
 354  * @param [in] nLine First line searched.
 355  * @param [out] nDiff Index of diff found.
 356  * @return true if line is inside diff, false otherwise.
 357  */
 358 bool DiffList::GetNextDiff(int nLine, int & nDiff) const
 359 {
 360         bool bInDiff = true;
 361         int numDiff = LineToDiff(nLine);
 362
 363         // Line not inside diff
 364         if (numDiff == -1)
 365         {
 366                 bInDiff = false;
 367                 const int nDiffCount = (int) m_diffs.size();
 368                 for (int i = 0; i < nDiffCount; i++)
 369                 {
 370                         if ((int)DiffRangeAt(i)->dbegin >= nLine)
 371                         {
 372                                 numDiff = i;
 373                                 break;
 374                         }
 375                 }
 376         }
 377         nDiff = numDiff;
 378         return bInDiff;
 379 }
 380
 381 /**
 382  * @brief Check if diff-list contains significant diffs.
 383  * @return true if list has significant diffs, false otherwise.
 384  */
 385 bool DiffList::HasSignificantDiffs() const
 386 {
 387         if (m_firstSignificant == -1)
 388                 return false;
 389         return true;
 390 }
 391
 392 /**
 393  * @brief Return previous diff index from given line.
 394  * @param [in] nLine First line searched.
 395  * @return Index for next difference or -1 if no difference is found.
 396  */
 397 int DiffList::PrevSignificantDiffFromLine(int nLine) const
 398 {
 399         int nDiff = -1;
 400         const int size = (int) m_diffs.size();
 401
 402         for (int i = size - 1; i >= 0 ; i--)
 403         {
 404                 const DIFFRANGE * dfi = DiffRangeAt(i);
 405                 if (dfi->op != OP_TRIVIAL && dfi->dend <= static_cast<int>(nLine))
 406                 {
 407                         nDiff = i;
 408                         break;
 409                 }
 410         }
 411         return nDiff;
 412 }
 413
 414 /**
 415  * @brief Return next diff index from given line.
 416  * @param [in] nLine First line searched.
 417  * @return Index for previous difference or -1 if no difference is found.
 418  */
 419 int DiffList::NextSignificantDiffFromLine(int nLine) const
 420 {
 421         int nDiff = -1;
 422         const int nDiffCount = static_cast<int>(m_diffs.size());
 423
 424         for (int i = 0; i < nDiffCount; i++)
 425         {
 426                 const DIFFRANGE * dfi = DiffRangeAt(i);
 427                 if (dfi->op != OP_TRIVIAL && dfi->dbegin >= static_cast<int>(nLine))
 428                 {
 429                         nDiff = i;
 430                         break;
 431                 }
 432         }
 433         return nDiff;
 434 }
 435
 436 /**
 437  * @brief Construct the doubly-linked chain of significant differences
 438  */
 439 void DiffList::ConstructSignificantChain()
 440 {
 441         m_firstSignificant = -1;
 442         m_lastSignificant = -1;
 443         m_firstSignificantLeftMiddle = -1;
 444         m_firstSignificantLeftRight = -1;
 445         m_firstSignificantMiddleRight = -1;
 446         m_firstSignificantConflict = -1;
 447         m_lastSignificantLeftMiddle = -1;
 448         m_lastSignificantLeftRight = -1;
 449         m_lastSignificantMiddleRight = -1;
 450         m_lastSignificantConflict = -1;
 451         ptrdiff_t prev = -1;
 452         const ptrdiff_t size = (int) m_diffs.size();
 453
 454         // must be called after diff list is entirely populated
 455     for (int i = 0; i < size; ++i)
 456         {
 457                 if (m_diffs[i].op == OP_TRIVIAL)
 458                 {
 459                         m_diffs[i].prev = -1;
 460                         m_diffs[i].next = -1;
 461                 }
 462                 else
 463                 {
 464                         m_diffs[i].prev = prev;
 465                         if (prev != -1)
 466                                 m_diffs[prev].next = (size_t) i;
 467                         prev = i;
 468                         if (m_firstSignificant == -1)
 469                                 m_firstSignificant = i;
 470                         m_lastSignificant = i;
 471                         if (m_diffs[i].op != OP_TRIVIAL && m_diffs[i].op != OP_3RDONLY)
 472                         {
 473                                 if (m_firstSignificantLeftMiddle == -1)
 474                                         m_firstSignificantLeftMiddle = i;
 475                                 m_lastSignificantLeftMiddle = i;
 476                         }
 477                         if (m_diffs[i].op != OP_TRIVIAL && m_diffs[i].op != OP_2NDONLY)
 478                         {
 479                                 if (m_firstSignificantLeftRight == -1)
 480                                         m_firstSignificantLeftRight = i;
 481                                 m_lastSignificantLeftRight = i;
 482                         }
 483                         if (m_diffs[i].op != OP_TRIVIAL && m_diffs[i].op != OP_1STONLY)
 484                         {
 485                                 if (m_firstSignificantMiddleRight == -1)
 486                                         m_firstSignificantMiddleRight = i;
 487                                 m_lastSignificantMiddleRight = i;
 488                         }
 489                         if (m_diffs[i].op == OP_1STONLY)
 490                         {
 491                                 if (m_firstSignificantLeftOnly == -1)
 492                                         m_firstSignificantLeftOnly = i;
 493                                 m_lastSignificantLeftOnly = i;
 494                         }
 495                         if (m_diffs[i].op == OP_2NDONLY)
 496                         {
 497                                 if (m_firstSignificantMiddleOnly == -1)
 498                                         m_firstSignificantMiddleOnly = i;
 499                                 m_lastSignificantMiddleOnly = i;
 500                         }
 501                         if (m_diffs[i].op == OP_3RDONLY)
 502                         {
 503                                 if (m_firstSignificantRightOnly == -1)
 504                                         m_firstSignificantRightOnly = i;
 505                                 m_lastSignificantRightOnly = i;
 506                         }
 507                         if (m_diffs[i].op == OP_DIFF)
 508                         {
 509                                 if (m_firstSignificantConflict == -1)
 510                                         m_firstSignificantConflict = i;
 511                                 m_lastSignificantConflict = i;
 512                         }
 513                 }
 514         }
 515 }
 516
 517 /**
 518  * @brief Return index to first significant difference.
 519  * @return Index of first significant difference.
 520  */
 521 int DiffList::FirstSignificantDiff() const
 522 {
 523         return m_firstSignificant;
 524 }
 525
 526 /**
 527  * @brief Return index of next significant diff.
 528  * @param [in] nDiff Index to start looking for next diff.
 529  * @return Index of next significant difference.
 530  */
 531 int DiffList::NextSignificantDiff(int nDiff) const
 532 {
 533         return (int)m_diffs[nDiff].next;
 534 }
 535
 536 /**
 537  * @brief Return index of previous significant diff.
 538  * @param [in] nDiff Index to start looking for previous diff.
 539  * @return Index of previous significant difference.
 540  */
 541 int DiffList::PrevSignificantDiff(int nDiff) const
 542 {
 543         return (int)m_diffs[nDiff].prev;
 544 }
 545
 546 /**
 547  * @brief Return index to last significant diff.
 548  * @return Index of last significant difference.
 549  */
 550 int DiffList::LastSignificantDiff() const
 551 {
 552         return m_lastSignificant;
 553 }
 554
 555 /**
 556  * @brief Return pointer to first significant diff.
 557  * @return Constant pointer to first significant difference.
 558  */
 559 const DIFFRANGE * DiffList::FirstSignificantDiffRange() const
 560 {
 561         if (m_firstSignificant == -1)
 562                 return NULL;
 563         return DiffRangeAt(m_firstSignificant);
 564 }
 565
 566 /**
 567  * @brief Return pointer to last significant diff.
 568  * @return Constant pointer to last significant difference.
 569  */
 570 const DIFFRANGE * DiffList::LastSignificantDiffRange() const
 571 {
 572         if (m_lastSignificant == -1)
 573                 return NULL;
 574         return DiffRangeAt(m_lastSignificant);
 575 }
 576
 577 /**
 578 <<<<<<< .mine
 579  * @brief Return previous diff index from given line.
 580  * @param [in] nLine First line searched.
 581  * @return Index for next difference or -1 if no difference is found.
 582  */
 583 int DiffList::PrevSignificant3wayDiffFromLine(int nLine, int nDiffType) const
 584 {
 585         for (int i = static_cast<int>(m_diffs.size()) - 1; i >= 0 ; i--)
 586         {
 587                 const DIFFRANGE * dfi = DiffRangeAt(i);
 588                 switch (nDiffType)
 589                 {
 590                 case THREEWAYDIFFTYPE_LEFTMIDDLE:
 591                         if (dfi->op != OP_TRIVIAL && dfi->op != OP_3RDONLY && dfi->dend <= static_cast<int>(nLine))
 592                                 return i;
 593                         break;
 594                 case THREEWAYDIFFTYPE_LEFTRIGHT:
 595                         if (dfi->op != OP_TRIVIAL && dfi->op != OP_2NDONLY && dfi->dend <= static_cast<int>(nLine))
 596                                 return i;
 597                         break;
 598                 case THREEWAYDIFFTYPE_MIDDLERIGHT:
 599                         if (dfi->op != OP_TRIVIAL && dfi->op != OP_1STONLY && dfi->dend <= static_cast<int>(nLine))
 600                                 return i;
 601                         break;
 602                 case THREEWAYDIFFTYPE_LEFTONLY:
 603                         if (dfi->op == OP_1STONLY && dfi->dend <= static_cast<int>(nLine))
 604                                 return i;
 605                         break;
 606                 case THREEWAYDIFFTYPE_MIDDLEONLY:
 607                         if (dfi->op == OP_2NDONLY && dfi->dend <= static_cast<int>(nLine))
 608                                 return i;
 609                         break;
 610                 case THREEWAYDIFFTYPE_RIGHTONLY:
 611                         if (dfi->op == OP_3RDONLY && dfi->dend <= static_cast<int>(nLine))
 612                                 return i;
 613                         break;
 614                 case THREEWAYDIFFTYPE_CONFLICT:
 615                         if (dfi->op == OP_DIFF && dfi->dend <= nLine)
 616                                 return i;
 617                         break;
 618                 }
 619         }
 620         return -1;
 621 }
 622
 623 /**
 624  * @brief Return next diff index from given line.
 625  * @param [in] nLine First line searched.
 626  * @return Index for previous difference or -1 if no difference is found.
 627  */
 628 int DiffList::NextSignificant3wayDiffFromLine(int nLine, int nDiffType) const
 629 {
 630         const int nDiffCount = static_cast<int>(m_diffs.size());
 631
 632         for (int i = 0; i < nDiffCount; i++)
 633         {
 634                 const DIFFRANGE * dfi = DiffRangeAt(i);
 635                 switch (nDiffType)
 636                 {
 637                 case THREEWAYDIFFTYPE_LEFTMIDDLE:
 638                         if (dfi->op != OP_TRIVIAL && dfi->op != OP_3RDONLY && dfi->dbegin >= static_cast<int>(nLine))
 639                                 return i;
 640                         break;
 641                 case THREEWAYDIFFTYPE_LEFTRIGHT:
 642                         if (dfi->op != OP_TRIVIAL && dfi->op != OP_2NDONLY && dfi->dbegin >= static_cast<int>(nLine))
 643                                 return i;
 644                         break;
 645                 case THREEWAYDIFFTYPE_MIDDLERIGHT:
 646                         if (dfi->op != OP_TRIVIAL && dfi->op != OP_1STONLY && dfi->dbegin >= static_cast<int>(nLine))
 647                                 return i;
 648                         break;
 649                 case THREEWAYDIFFTYPE_LEFTONLY:
 650                         if (dfi->op == OP_1STONLY && dfi->dbegin >= static_cast<int>(nLine))
 651                                 return i;
 652                         break;
 653                 case THREEWAYDIFFTYPE_MIDDLEONLY:
 654                         if (dfi->op == OP_2NDONLY && dfi->dbegin >= static_cast<int>(nLine))
 655                                 return i;
 656                         break;
 657                 case THREEWAYDIFFTYPE_RIGHTONLY:
 658                         if (dfi->op == OP_3RDONLY && dfi->dbegin >= static_cast<int>(nLine))
 659                                 return i;
 660                         break;
 661                 case THREEWAYDIFFTYPE_CONFLICT:
 662                         if (dfi->op == OP_DIFF && dfi->dbegin >= nLine)
 663                                 return i;
 664                         break;
 665                 }
 666         }
 667         return -1;
 668 }
 669
 670 /**
 671  * @brief Return index to first significant difference.
 672  * @return Index of first significant difference.
 673  */
 674 int DiffList::FirstSignificant3wayDiff(int nDiffType) const
 675 {
 676         switch (nDiffType)
 677         {
 678         case THREEWAYDIFFTYPE_LEFTMIDDLE:
 679                 return m_firstSignificantLeftMiddle;
 680         case THREEWAYDIFFTYPE_LEFTRIGHT:
 681                 return m_firstSignificantLeftRight;
 682         case THREEWAYDIFFTYPE_MIDDLERIGHT:
 683                 return m_firstSignificantMiddleRight;
 684         case THREEWAYDIFFTYPE_LEFTONLY:
 685                 return m_firstSignificantLeftOnly;
 686         case THREEWAYDIFFTYPE_MIDDLEONLY:
 687                 return m_firstSignificantLeftOnly;
 688         case THREEWAYDIFFTYPE_RIGHTONLY:
 689                 return m_firstSignificantRightOnly;
 690         case THREEWAYDIFFTYPE_CONFLICT:
 691                 return m_firstSignificantConflict;
 692         }
 693         return -1;
 694 }
 695
 696 /**
 697  * @brief Return index of next significant diff.
 698  * @param [in] nDiff Index to start looking for next diff.
 699  * @return Index of next significant difference.
 700  */
 701 int DiffList::NextSignificant3wayDiff(int nDiff, int nDiffType) const
 702 {
 703         while (m_diffs[nDiff].next != -1)
 704         {
 705                 nDiff = static_cast<int>(m_diffs[nDiff].next);
 706                 switch (nDiffType)
 707                 {
 708                 case THREEWAYDIFFTYPE_LEFTMIDDLE:
 709                         if (m_diffs[nDiff].op != OP_3RDONLY)
 710                                 return nDiff;
 711                         break;
 712                 case THREEWAYDIFFTYPE_LEFTRIGHT:
 713                         if (m_diffs[nDiff].op != OP_2NDONLY)
 714                                 return nDiff;
 715                         break;
 716                 case THREEWAYDIFFTYPE_MIDDLERIGHT:
 717                         if (m_diffs[nDiff].op != OP_1STONLY)
 718                                 return nDiff;
 719                         break;
 720                 case THREEWAYDIFFTYPE_LEFTONLY:
 721                         if (m_diffs[nDiff].op == OP_1STONLY)
 722                                 return nDiff;
 723                         break;
 724                 case THREEWAYDIFFTYPE_MIDDLEONLY:
 725                         if (m_diffs[nDiff].op == OP_2NDONLY)
 726                                 return nDiff;
 727                         break;
 728                 case THREEWAYDIFFTYPE_RIGHTONLY:
 729                         if (m_diffs[nDiff].op == OP_3RDONLY)
 730                                 return nDiff;
 731                         break;
 732                 case THREEWAYDIFFTYPE_CONFLICT:
 733                         if (m_diffs[nDiff].op == OP_DIFF)
 734                                 return nDiff;
 735                         break;
 736                 }
 737         }
 738         return -1;
 739 }
 740
 741 /**
 742  * @brief Return index of previous significant diff.
 743  * @param [in] nDiff Index to start looking for previous diff.
 744  * @return Index of previous significant difference.
 745  */
 746 int DiffList::PrevSignificant3wayDiff(int nDiff, int nDiffType) const
 747 {
 748         while (m_diffs[nDiff].prev != -1)
 749         {
 750                 nDiff = static_cast<int>(m_diffs[nDiff].prev);
 751                 switch (nDiffType)
 752                 {
 753                 case THREEWAYDIFFTYPE_LEFTMIDDLE:
 754                         if (m_diffs[nDiff].op != OP_3RDONLY)
 755                                 return nDiff;
 756                         break;
 757                 case THREEWAYDIFFTYPE_LEFTRIGHT:
 758                         if (m_diffs[nDiff].op != OP_2NDONLY)
 759                                 return nDiff;
 760                         break;
 761                 case THREEWAYDIFFTYPE_MIDDLERIGHT:
 762                         if (m_diffs[nDiff].op != OP_1STONLY)
 763                                 return nDiff;
 764                         break;
 765                 case THREEWAYDIFFTYPE_LEFTONLY:
 766                         if (m_diffs[nDiff].op == OP_1STONLY)
 767                                 return nDiff;
 768                         break;
 769                 case THREEWAYDIFFTYPE_MIDDLEONLY:
 770                         if (m_diffs[nDiff].op == OP_2NDONLY)
 771                                 return nDiff;
 772                         break;
 773                 case THREEWAYDIFFTYPE_RIGHTONLY:
 774                         if (m_diffs[nDiff].op == OP_3RDONLY)
 775                                 return nDiff;
 776                         break;
 777                 case THREEWAYDIFFTYPE_CONFLICT:
 778                         if (m_diffs[nDiff].op == OP_DIFF)
 779                                 return nDiff;
 780                         break;
 781                 }
 782         }
 783         return -1;
 784 }
 785
 786 /**
 787  * @brief Return index to last significant diff.
 788  * @return Index of last significant difference.
 789  */
 790 int DiffList::LastSignificant3wayDiff(int nDiffType) const
 791 {
 792         switch (nDiffType)
 793         {
 794         case THREEWAYDIFFTYPE_LEFTMIDDLE:
 795                 return m_lastSignificantLeftMiddle;
 796         case THREEWAYDIFFTYPE_LEFTRIGHT:
 797                 return m_lastSignificantLeftRight;
 798         case THREEWAYDIFFTYPE_MIDDLERIGHT:
 799                 return m_lastSignificantMiddleRight;
 800         case THREEWAYDIFFTYPE_LEFTONLY:
 801                 return m_lastSignificantLeftOnly;
 802         case THREEWAYDIFFTYPE_MIDDLEONLY:
 803                 return m_lastSignificantLeftOnly;
 804         case THREEWAYDIFFTYPE_RIGHTONLY:
 805                 return m_lastSignificantRightOnly;
 806         case THREEWAYDIFFTYPE_CONFLICT:
 807                 return m_lastSignificantRightOnly;
 808         }
 809         return -1;
 810 }
 811
 812 /**
 813  * @brief Return pointer to first significant diff.
 814  * @return Constant pointer to first significant difference.
 815  */
 816 const DIFFRANGE * DiffList::FirstSignificant3wayDiffRange(int nDiffType) const
 817 {
 818         switch (nDiffType)
 819         {
 820         case THREEWAYDIFFTYPE_LEFTMIDDLE:
 821                 if (m_firstSignificantLeftMiddle == -1) return NULL;
 822                 return DiffRangeAt(m_firstSignificantLeftMiddle);
 823         case THREEWAYDIFFTYPE_LEFTRIGHT:
 824                 if (m_firstSignificantLeftRight == -1) return NULL;
 825                 return DiffRangeAt(m_firstSignificantLeftRight);
 826         case THREEWAYDIFFTYPE_MIDDLERIGHT:
 827                 if (m_firstSignificantMiddleRight == -1) return NULL;
 828                 return DiffRangeAt(m_firstSignificantMiddleRight);
 829         case THREEWAYDIFFTYPE_LEFTONLY:
 830                 if (m_firstSignificantLeftOnly == -1) return NULL;
 831                 return DiffRangeAt(m_firstSignificantLeftOnly);
 832         case THREEWAYDIFFTYPE_MIDDLEONLY:
 833                 if (m_firstSignificantMiddleOnly == -1) return NULL;
 834                 return DiffRangeAt(m_firstSignificantMiddleOnly);
 835         case THREEWAYDIFFTYPE_RIGHTONLY:
 836                 if (m_firstSignificantRightOnly == -1) return NULL;
 837                 return DiffRangeAt(m_firstSignificantRightOnly);
 838         case THREEWAYDIFFTYPE_CONFLICT:
 839                 if (m_firstSignificantConflict == -1) return NULL;
 840                 return DiffRangeAt(m_firstSignificantConflict);
 841         }
 842         return NULL;
 843 }
 844
 845 /**
 846  * @brief Return pointer to last significant diff.
 847  * @return Constant pointer to last significant difference.
 848  */
 849 const DIFFRANGE * DiffList::LastSignificant3wayDiffRange(int nDiffType) const
 850 {
 851         switch (nDiffType)
 852         {
 853         case THREEWAYDIFFTYPE_LEFTMIDDLE:
 854                 if (m_lastSignificantLeftMiddle == -1) return NULL;
 855                 return DiffRangeAt(m_lastSignificantLeftMiddle);
 856         case THREEWAYDIFFTYPE_LEFTRIGHT:
 857                 if (m_lastSignificantLeftRight == -1) return NULL;
 858                 return DiffRangeAt(m_lastSignificantLeftRight);
 859         case THREEWAYDIFFTYPE_MIDDLERIGHT:
 860                 if (m_lastSignificantMiddleRight == -1) return NULL;
 861                 return DiffRangeAt(m_lastSignificantMiddleRight);
 862         case THREEWAYDIFFTYPE_LEFTONLY:
 863                 if (m_lastSignificantLeftOnly == -1) return NULL;
 864                 return DiffRangeAt(m_lastSignificantLeftOnly);
 865         case THREEWAYDIFFTYPE_MIDDLEONLY:
 866                 if (m_lastSignificantMiddleOnly == -1) return NULL;
 867                 return DiffRangeAt(m_lastSignificantMiddleOnly);
 868         case THREEWAYDIFFTYPE_RIGHTONLY:
 869                 if (m_lastSignificantRightOnly == -1) return NULL;
 870                 return DiffRangeAt(m_lastSignificantRightOnly);
 871         case THREEWAYDIFFTYPE_CONFLICT:
 872                 if (m_lastSignificantConflict == -1) return NULL;
 873                 return DiffRangeAt(m_lastSignificantConflict);
 874         }
 875         return NULL;
 876 }
 877
 878 /**
 879  * @brief Swap sides of diffrange
 880  */
 881 void DiffList::Swap(int index1, int index2)
 882 {
 883         vector<DiffRangeInfo>::iterator iter = m_diffs.begin();
 884         vector<DiffRangeInfo>::const_iterator iterEnd = m_diffs.end();
 885         while (iter != iterEnd)
 886         {
 887                 (*iter).swap_sides(index1, index2);
 888                 ++iter;
 889         }
 890 }
 891
 892 /**
 893  * @brief Count number of lines to add to sides (because of synch).
 894  * @param [out] nLeftLines Number of lines to add to left side.
 895  * @param [out] nRightLines Number of lines to add to right side.
 896  */
 897 void DiffList::GetExtraLinesCounts(int nFiles, int extras[3])
 898 {
 899         extras[0]=0;
 900         extras[1]=0;
 901         extras[2]=0;
 902         const int nDiffCount = GetSize();
 903
 904         for (int nDiff = 0; nDiff < nDiffCount; ++nDiff)
 905         {
 906                 DIFFRANGE curDiff;
 907                 GetDiff(nDiff, curDiff);
 908
 909                 // this guarantees that all the diffs are synchronized
 910                 assert(curDiff.begin[0]+extras[0] == curDiff.begin[1]+extras[1]);
 911                 assert(nFiles<3 || curDiff.begin[0]+extras[0] == curDiff.begin[2]+extras[2]);
 912                 int nline[3] = { 0,0,0 };
 913                 int nmaxline = 0;
 914                 int file;
 915                 for (file = 0; file < nFiles; file++)
 916                 {
 917                         nline[file] = curDiff.end[file]-curDiff.begin[file]+1;
 918                         nmaxline = std::max(nmaxline, nline[file]);
 919                 }
 920                 for (file = 0; file < nFiles; file++)
 921                         extras[file] += nmaxline - nline[file];
 922         }
 923 }
 924
 925 void DiffList::AppendDiffList(const DiffList& list, int offset[], int doffset)
 926 {
 927         for (std::vector<DiffRangeInfo>::const_iterator it = list.m_diffs.begin(); it != list.m_diffs.end(); ++it)
 928         {
 929                 DIFFRANGE dr = *it;
 930                 for (int file = 0; file < 3; ++file)
 931                 {
 932                         if (offset)
 933                         {
 934                                 dr.begin[file] += offset[file];
 935                                 dr.end[file] += offset[file];
 936                         }
 937                         if (doffset)
 938                                 dr.blank[file] += doffset;
 939                 }
 940                 if (doffset)
 941                 {
 942                         dr.dbegin += doffset;
 943                         dr.dend += doffset;
 944                 }
 945                 AddDiff(dr);
 946         }
 947 }
 948
 949 int DiffList::GetMergeableSrcIndex(int nDiff, int nDestIndex) const
 950 {
 951         const DIFFRANGE *pdr = DiffRangeAt(nDiff);
 952         switch (nDestIndex)
 953         {
 954         case 0:
 955         case 2:
 956                 if (pdr->op == OP_2NDONLY)
 957                         return 1;
 958                 return -1;
 959         case 1:
 960                 if (pdr->op == OP_1STONLY || pdr->op == OP_2NDONLY)
 961                         return 0;
 962                 else if (pdr->op == OP_3RDONLY)
 963                         return 2;
 964                 return -1;
 965         default:
 966                 return -1;
 967         }
 968 }