diff_match_patch.h

/*
 * Copyright 2008 Google Inc. All Rights Reserved.
 * Author: fraser@google.com (Neil Fraser)
 * Author: mikeslemmer@gmail.com (Mike Slemmer)
 *
 * Licensed under the Apache License, Version 2.0 (the "License");
 * you may not use this file except in compliance with the License.
 * You may obtain a copy of the License at
 *
 *   http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing, software
 * distributed under the License is distributed on an "AS IS" BASIS,
 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
 * See the License for the specific language governing permissions and
 * limitations under the License.
 *
 * Diff Match and Patch
 * http://code.google.com/p/google-diff-match-patch/
 */

#ifndef DIFF_MATCH_PATCH_H
#define DIFF_MATCH_PATCH_H

/*
 * Functions for diff, match and patch.
 * Computes the difference between two texts to create a patch.
 * Applies the patch onto another text, allowing for errors.
 *
 * @author fraser@google.com (Neil Fraser)
 *
 * Qt/C++ port by mikeslemmer@gmail.com (Mike Slemmer):
 *
 * Code known to compile and run with Qt 4.3 through Qt 4.7.
 *
 * Here is a trivial sample program which works properly when linked with this
 * library:
 *

 #include <QtCore>
 #include <QString>
 #include <QList>
 #include <QMap>
 #include <QVariant>
 #include "diff_match_patch.h"
 int main(int argc, char **argv) {
   diff_match_patch dmp;
   QString str1 = QString("First string in diff");
   QString str2 = QString("Second string in diff");

   QString strPatch = dmp.patch_toText(dmp.patch_make(str1, str2));
   QPair<QString, QVector<bool> > out
       = dmp.patch_apply(dmp.patch_fromText(strPatch), str1);
   QString strResult = out.first;

   // here, strResult will equal str2 above.
   return 0;
 }

 */


enum Operation {
  DELETE, INSERT, EQUAL
};


class Diff {
 public:
  Operation operation;
  // One of: INSERT, DELETE or EQUAL.
  QString text;
  // The text associated with this diff operation.

  Diff(Operation _operation, const QString &_text);
  Diff();
  inline bool isNull() const;
  QString toString() const;
  bool operator==(const Diff &d) const;
  bool operator!=(const Diff &d) const;

  static QString strOperation(Operation op);
};


class Patch {
 public:
  QList<Diff> diffs;
  int start1;
  int start2;
  int length1;
  int length2;

  Patch();
  bool isNull() const;
  QString toString();
};


class diff_match_patch {

  friend class diff_match_patch_test;

 public:
  // Defaults.
  // Set these on your diff_match_patch instance to override the defaults.

  // Number of seconds to map a diff before giving up (0 for infinity).
  float Diff_Timeout;
  // Cost of an empty edit operation in terms of edit characters.
  short Diff_EditCost;
  // At what point is no match declared (0.0 = perfection, 1.0 = very loose).
  float Match_Threshold;
  // How far to search for a match (0 = exact location, 1000+ = broad match).
  // A match this many characters away from the expected location will add
  // 1.0 to the score (0.0 is a perfect match).
  int Match_Distance;
  // When deleting a large block of text (over ~64 characters), how close does
  // the contents have to match the expected contents. (0.0 = perfection,
  // 1.0 = very loose).  Note that Match_Threshold controls how closely the
  // end points of a delete need to match.
  float Patch_DeleteThreshold;
  // Chunk size for context length.
  short Patch_Margin;

  // The number of bits in an int.
  short Match_MaxBits;

 private:
  // Define some regex patterns for matching boundaries.
  static QRegExp BLANKLINEEND;
  static QRegExp BLANKLINESTART;


 public:

  diff_match_patch();

  //  DIFF FUNCTIONS


  QList<Diff> diff_main(const QString &text1, const QString &text2);

  QList<Diff> diff_main(const QString &text1, const QString &text2, bool checklines);

 private:
  QList<Diff> diff_main(const QString &text1, const QString &text2, bool checklines, clock_t deadline);

 private:
  QList<Diff> diff_compute(QString text1, QString text2, bool checklines, clock_t deadline);

 private:
  QList<Diff> diff_lineMode(QString text1, QString text2, clock_t deadline);

 protected:
  QList<Diff> diff_bisect(const QString &text1, const QString &text2, clock_t deadline);

 private:
  QList<Diff> diff_bisectSplit(const QString &text1, const QString &text2, int x, int y, clock_t deadline);

 protected:
  QList<QVariant> diff_linesToChars(const QString &text1, const QString &text2); // return elems 0 and 1 are QString, elem 2 is QStringList

 private:
  QString diff_linesToCharsMunge(const QString &text, QStringList &lineArray,
                                 QMap<QString, int> &lineHash);

 private:
  void diff_charsToLines(QList<Diff> &diffs, const QStringList &lineArray);

 public:
  int diff_commonPrefix(const QString &text1, const QString &text2);

 public:
  int diff_commonSuffix(const QString &text1, const QString &text2);

 protected:
  int diff_commonOverlap(const QString &text1, const QString &text2);

 protected:
  QStringList diff_halfMatch(const QString &text1, const QString &text2);

 private:
  QStringList diff_halfMatchI(const QString &longtext, const QString &shorttext, int i);

 public:
  void diff_cleanupSemantic(QList<Diff> &diffs);

 public:
  void diff_cleanupSemanticLossless(QList<Diff> &diffs);

 private:
  int diff_cleanupSemanticScore(const QString &one, const QString &two);

 public:
  void diff_cleanupEfficiency(QList<Diff> &diffs);

 public:
  void diff_cleanupMerge(QList<Diff> &diffs);

 public:
  int diff_xIndex(const QList<Diff> &diffs, int loc);

 public:
  QString diff_prettyHtml(const QList<Diff> &diffs);

 public:
  QString diff_text1(const QList<Diff> &diffs);

 public:
  QString diff_text2(const QList<Diff> &diffs);

 public:
  int diff_levenshtein(const QList<Diff> &diffs);

 public:
  QString diff_toDelta(const QList<Diff> &diffs);

 public:
  QList<Diff> diff_fromDelta(const QString &text1, const QString &delta);


  //  MATCH FUNCTIONS


 public:
  int match_main(const QString &text, const QString &pattern, int loc);

 protected:
  int match_bitap(const QString &text, const QString &pattern, int loc);

 private:
  double match_bitapScore(int e, int x, int loc, const QString &pattern);

 protected:
  QMap<QChar, int> match_alphabet(const QString &pattern);


 //  PATCH FUNCTIONS


 protected:
  void patch_addContext(Patch &patch, const QString &text);

 public:
  QList<Patch> patch_make(const QString &text1, const QString &text2);

 public:
  QList<Patch> patch_make(const QList<Diff> &diffs);

 public:
  QList<Patch> patch_make(const QString &text1, const QString &text2, const QList<Diff> &diffs);

 public:
  QList<Patch> patch_make(const QString &text1, const QList<Diff> &diffs);

 public:
  QList<Patch> patch_deepCopy(QList<Patch> &patches);

 public:
  QPair<QString,QVector<bool> > patch_apply(QList<Patch> &patches, const QString &text);

 public:
  QString patch_addPadding(QList<Patch> &patches);

 public:
  void patch_splitMax(QList<Patch> &patches);

 public:
  QString patch_toText(const QList<Patch> &patches);

 public:
  QList<Patch> patch_fromText(const QString &textline);

 private:
  static inline QString safeMid(const QString &str, int pos) {
    return (pos == str.length()) ? QString("") : str.mid(pos);
  }

 private:
  static inline QString safeMid(const QString &str, int pos, int len) {
    return (pos == str.length()) ? QString("") : str.mid(pos, len);
  }
};

#endif // DIFF_MATCH_PATCH_H