49 template <
typename elem,
typename sequence = vector< elem >,
typename comparator = Compare< elem > >
78 const sequence& b) : A(a),
B(b),
ses(false) {
84 bool deletesFirst) : A(a),
B(b),
ses(deletesFirst) {
90 const comparator& comp) : A(a),
B(b),
ses(false),
cmp(comp) {
97 const comparator& comp) : A(a),
B(b),
ses(deleteFirst),
cmp(comp) {
112 return lcs.getSequence();
141 this->trivial =
true;
145 this->trivial =
false;
149 this->editDistanceOnly =
true;
170 this->trivial =
true;
174 this->trivial =
false;
178 this->editDistanceOnly =
true;
185 elemList seqLst(seq.begin(), seq.end());
187 sesElemVec_iter vsesIt;
188 elemList_iter lstIt = seqLst.begin();
189 long long inc_dec_total = 0;
195 it->a += inc_dec_total;
196 inc_dec_total += it->inc_dec_count;
197 for (
long long i=0;i<it->a - gap;++i) {
200 gap = it->a + it->b + it->inc_dec_count;
201 vsesIt = shunk.begin();
202 while (vsesIt!=shunk.end()) {
203 switch (vsesIt->second.type) {
205 seqLst.insert(lstIt, vsesIt->first);
208 if (lstIt != seqLst.end()) {
209 lstIt = seqLst.erase(lstIt);
213 if (lstIt != seqLst.end()) {
226 sequence patchedSeq(seqLst.begin(), seqLst.end());
233 sequence
patch (
const sequence& seq)
const {
234 sesElemVec sesSeq =
ses.getSequence();
235 elemList seqLst(seq.begin(), seq.end());
236 elemList_iter lstIt = seqLst.begin();
237 for (sesElemVec_iter sesIt=sesSeq.begin();sesIt!=sesSeq.end();++sesIt) {
238 switch (sesIt->second.type) {
240 seqLst.insert(lstIt, sesIt->first);
243 lstIt = seqLst.erase(lstIt);
253 sequence patchedSeq(seqLst.begin(), seqLst.end());
270 fp =
new long long[
M +
N + 3];
271 fill(&
fp[0], &
fp[
M +
N + 3], -1);
277 for (
long long k=-p;k<=static_cast<long long>(
delta)-1;++k) {
280 for (
long long k=
static_cast<long long>(
delta)+p;k>=
static_cast<long long>(
delta)+1;--k) {
300 epc.push_back(cordinate);
317 template <
typename stream >
319 sesElemVec ses_v =
ses.getSequence();
324 printSES< ostream >(out);
330 template <
typename stream >
337 printSES< ostream >(s, out);
343 template <
typename stream,
template <
typename SEET,
typename STRT >
class PT >
345 sesElemVec ses_v =
ses.getSequence ();
346 for_each (ses_v.begin (), ses_v.end(), PT < sesElem, stream > (out));
352 template <
typename storedData,
template <
typename SEET,
typename STRT >
class ST >
354 sesElemVec ses_v =
ses.getSequence();
355 for_each(ses_v.begin(), ses_v.end(), ST < sesElem, storedData >(sd));
361 template <
typename stream >
367 printUnifiedFormat< ostream >(out);
373 template <
typename stream >
379 printUnifiedFormat< ostream >(hunks, out);
386 sesElemVec common[2];
388 sesElemVec ses_v =
ses.getSequence();
390 long long length = distance(ses_v.begin(), ses_v.end());
391 long long middle = 0;
392 bool isMiddle, isAfter;
394 long long a, b, c, d;
395 long long inc_dec_count = 0;
400 isMiddle = isAfter =
false;
403 for (sesElemVec_iter it=ses_v.begin();it!=ses_v.end();++it, ++l_cnt) {
405 switch (einfo.
type) {
410 if (!isMiddle) isMiddle =
true;
412 if (l_cnt >= length) {
421 deletes.push_back(*it);
422 if (!isMiddle) isMiddle =
true;
424 if (l_cnt >= length) {
432 if (common[1].empty() && adds.empty() && deletes.empty() && change.empty()) {
434 if (a == 0 && c == 0) {
443 common[0].push_back(*it);
445 rotate(common[0].begin(), common[0].begin() + 1, common[0].end());
446 common[0].pop_back();
447 common[0].push_back(*it);
452 if (isMiddle && !isAfter) {
456 change.push_back(*it);
469 if (isAfter && !change.empty()) {
470 sesElemVec_iter cit = it;
483 long long c0size =
static_cast<long long>(common[0].size());
484 rotate(common[0].begin(),
488 common[0].pop_back();
500 hunk.
common[0] = common[0];
502 hunk.
common[1] = common[1];
512 a = b = c = d = middle = inc_dec_count = 0;
520 template <
typename stream>
525 long long x_idx, y_idx;
527 while (getline(st, line)) {
528 elem mark(line.begin(), line.begin() + 1);
529 elem e(line.begin() + 1, line.end());
550 M = distance(A.begin(), A.end());
551 N = distance(
B.begin(),
B.end());
571 long long snake(
const long long& k,
const long long& above,
const long long& below) {
573 long long y = max(above, below);
575 while ((
size_t)x <
M && (
size_t)y <
N && (
swapped ?
cmp.impl(
B[(
size_t)y], A[(
size_t)x]) :
cmp.impl(A[(
size_t)x],
B[(
size_t)y]))) {
582 p.
x = x;p.
y = y;p.
k = r;
592 sequence_const_iter x(A.begin());
593 sequence_const_iter y(
B.begin());
594 long long x_idx, y_idx;
595 long long px_idx, py_idx;
596 bool complete =
false;
599 for (
size_t i=v.size()-1;!complete;--i) {
600 while(px_idx < v[i].x || py_idx < v[i].y) {
601 if (v[i].y - v[i].x > py_idx - px_idx) {
610 }
else if (v[i].y - v[i].x < py_idx - px_idx) {
635 if (i == 0) complete =
true;
638 if (x_idx >
static_cast<long long>(
M) && y_idx >
static_cast<long long>(
N)) {
654 sequence A_(A.begin() + (
size_t)x_idx - 1, A.end());
655 sequence B_(
B.begin() + (
size_t)y_idx - 1,
B.end());
658 M = distance(A.begin(), A.end());
659 N = distance(
B.begin(),
B.end());
663 fp =
new long long[
M +
N + 3];
664 fill(&
fp[0], &
fp[
M +
N + 3], -1);
678 ses.addSequence(*it, idx, 0, et);
683 ses.addSequence(*it, idx, 0, et);
690 void inline joinSesVec (sesElemVec& s1, sesElemVec& s2)
const {
692 for (sesElemVec_iter vit=s2.begin();vit!=s2.end();++vit) {
Definition: functors.hpp:78
static Ses< elem > composeSesFromStream(stream &st)
Definition: Diff.hpp:521
void printUnifiedFormat(stream &out) const
Definition: Diff.hpp:362
bool hugeEnabled() const
Definition: Diff.hpp:153
dtl_typedefs(elem, sequence) sequence A
void disableHuge()
Definition: Diff.hpp:161
comparator cmp
Definition: Diff.hpp:71
editPath path
Definition: Diff.hpp:64
bool isHuge() const
Definition: Diff.hpp:124
void onUnserious()
Definition: Diff.hpp:140
size_t N
Definition: Diff.hpp:57
Diff(const sequence &a, const sequence &b, const comparator &comp)
Definition: Diff.hpp:88
bool editDistanceOnly
Definition: Diff.hpp:69
void printSES(ostream &out=cout) const
Definition: Diff.hpp:323
size_t delta
Definition: Diff.hpp:58
Diff(const sequence &a, const sequence &b, bool deletesFirst)
Definition: Diff.hpp:82
static void printUnifiedFormat(const uniHunkVec &hunks, stream &out)
Definition: Diff.hpp:374
void editDistanceOnlyEnabled()
Definition: Diff.hpp:177
Diff()
Definition: Diff.hpp:75
size_t offset
Definition: Diff.hpp:59
void recordOddSequence(long long idx, long long length, sequence_const_iter it, const edit_t et)
Definition: Diff.hpp:676
void composeUnifiedHunks()
Definition: Diff.hpp:385
long long * fp
Definition: Diff.hpp:60
void disableTrivial()
Definition: Diff.hpp:173
long long ox
Definition: Diff.hpp:72
bool huge
Definition: Diff.hpp:67
sequence patch(const sequence &seq) const
Definition: Diff.hpp:233
void compose()
Definition: Diff.hpp:262
long long getEditDistance() const
Definition: Diff.hpp:103
void init()
Definition: Diff.hpp:549
void offUnserious()
Definition: Diff.hpp:144
size_t M
Definition: Diff.hpp:56
bool wasSwapped() const
Definition: Diff.hpp:701
Ses< elem > ses
Definition: Diff.hpp:63
static void printSES(const Ses< elem > &s, stream &out)
Definition: Diff.hpp:331
sequence B
Definition: Diff.hpp:55
elemVec getLcsVec() const
Definition: Diff.hpp:111
Diff(const sequence &a, const sequence &b, bool deleteFirst, const comparator &comp)
Definition: Diff.hpp:94
void storeSES(storedData &sd) const
Definition: Diff.hpp:353
Lcs< elem > lcs
Definition: Diff.hpp:62
sequence uniPatch(const sequence &seq)
Definition: Diff.hpp:184
editPathCordinates pathCordinates
Definition: Diff.hpp:65
long long oy
Definition: Diff.hpp:73
bool trivial
Definition: Diff.hpp:68
void printSES(stream &out) const
Definition: Diff.hpp:318
void printSES(stream &out) const
Definition: Diff.hpp:344
Lcs< elem > getLcs() const
Definition: Diff.hpp:107
Diff(const sequence &a, const sequence &b)
Definition: Diff.hpp:77
void offHuge()
Definition: Diff.hpp:132
void printUnifiedFormat(ostream &out=cout) const
Definition: Diff.hpp:366
~Diff()
Definition: Diff.hpp:101
bool recordSequence(const editPathCordinates &v)
Definition: Diff.hpp:591
uniHunkVec getUniHunks() const
Definition: Diff.hpp:119
bool trivialEnabled() const
Definition: Diff.hpp:165
void enableTrivial()
Definition: Diff.hpp:169
Ses< elem > getSes() const
Definition: Diff.hpp:115
bool isUnserious() const
Definition: Diff.hpp:136
bool swapped
Definition: Diff.hpp:66
long long snake(const long long &k, const long long &above, const long long &below)
Definition: Diff.hpp:571
static void printUnifiedFormat(const uniHunkVec &hunks, ostream &out=cout)
Definition: Diff.hpp:378
long long editDistance
Definition: Diff.hpp:61
void joinSesVec(sesElemVec &s1, sesElemVec &s2) const
Definition: Diff.hpp:690
uniHunkVec uniHunks
Definition: Diff.hpp:70
static void printSES(const Ses< elem > &s, ostream &out=cout)
Definition: Diff.hpp:336
void enableHuge()
Definition: Diff.hpp:157
void onHuge()
Definition: Diff.hpp:128
void onOnlyEditDistance()
Definition: Diff.hpp:148
sesElemVec getSequence() const
Definition: Ses.hpp:119
void addSequence(elem e, long long beforeIdx, long long afterIdx, const edit_t type)
Definition: Ses.hpp:83
Definition: functors.hpp:103
int edit_t
Definition: variables.hpp:71
const edit_t SES_ADD
Definition: variables.hpp:74
const long long DTL_CONTEXT_SIZE
Definition: variables.hpp:96
const unsigned long long MAX_CORDINATES_SIZE
Definition: variables.hpp:110
const long long DTL_SEPARATE_SIZE
Definition: variables.hpp:95
const edit_t SES_COMMON
Definition: variables.hpp:73
const edit_t SES_DELETE
Definition: variables.hpp:72
vector< long long > editPath
Definition: variables.hpp:112
vector< P > editPathCordinates
Definition: variables.hpp:113
Definition: variables.hpp:101
long long x
Definition: variables.hpp:102
long long k
Definition: variables.hpp:104
long long y
Definition: variables.hpp:103
Definition: variables.hpp:86
long long afterIdx
Definition: variables.hpp:88
long long beforeIdx
Definition: variables.hpp:87
edit_t type
Definition: variables.hpp:89
Definition: variables.hpp:119
vector< sesElem > change
Definition: variables.hpp:122
long long b
Definition: variables.hpp:120
long long d
Definition: variables.hpp:120
long long inc_dec_count
Definition: variables.hpp:123
long long c
Definition: variables.hpp:120
long long a
Definition: variables.hpp:120
vector< sesElem > common[2]
Definition: variables.hpp:121
#define SES_MARK_DELETE
Definition: variables.hpp:79
#define SES_MARK_ADD
Definition: variables.hpp:81
#define SES_MARK_COMMON
Definition: variables.hpp:80