47 template <
typename elem,
typename sequence = vector< elem >,
typename comparator = Compare< elem > >
76 const sequence& b) : A(a),
B(b),
ses(false) {
82 bool deletesFirst) : A(a),
B(b),
ses(deletesFirst) {
88 const comparator& comp) : A(a),
B(b),
ses(false),
cmp(comp) {
95 const comparator& comp) : A(a),
B(b),
ses(deleteFirst),
cmp(comp) {
110 return lcs.getSequence();
139 this->trivial =
true;
143 this->trivial =
false;
147 this->editDistanceOnly =
true;
168 this->trivial =
true;
172 this->trivial =
false;
176 this->editDistanceOnly =
true;
183 elemList seqLst(seq.begin(), seq.end());
185 sesElemVec_iter vsesIt;
186 elemList_iter lstIt = seqLst.begin();
187 long long inc_dec_total = 0;
193 it->a += inc_dec_total;
194 inc_dec_total += it->inc_dec_count;
195 for (
long long i=0;i<it->a - gap;++i) {
198 gap = it->a + it->b + it->inc_dec_count;
199 vsesIt = shunk.begin();
200 while (vsesIt!=shunk.end()) {
201 switch (vsesIt->second.type) {
203 seqLst.insert(lstIt, vsesIt->first);
206 if (lstIt != seqLst.end()) {
207 lstIt = seqLst.erase(lstIt);
211 if (lstIt != seqLst.end()) {
224 sequence patchedSeq(seqLst.begin(), seqLst.end());
231 sequence
patch (
const sequence& seq)
const {
232 sesElemVec sesSeq =
ses.getSequence();
233 elemList seqLst(seq.begin(), seq.end());
234 elemList_iter lstIt = seqLst.begin();
235 for (sesElemVec_iter sesIt=sesSeq.begin();sesIt!=sesSeq.end();++sesIt) {
236 switch (sesIt->second.type) {
238 seqLst.insert(lstIt, sesIt->first);
241 lstIt = seqLst.erase(lstIt);
251 sequence patchedSeq(seqLst.begin(), seqLst.end());
268 fp =
new long long[
M +
N + 3];
269 fill(&
fp[0], &
fp[
M +
N + 3], -1);
275 for (
long long k=-p;k<=static_cast<long long>(
delta)-1;++k) {
278 for (
long long k=
static_cast<long long>(
delta)+p;k>=
static_cast<long long>(
delta)+1;--k) {
298 epc.push_back(cordinate);
315 template <
typename stream >
317 sesElemVec ses_v =
ses.getSequence();
322 printSES< ostream >(out);
328 template <
typename stream >
335 printSES< ostream >(s, out);
341 template <
typename stream,
template <
typename SEET,
typename STRT >
class PT >
343 sesElemVec ses_v =
ses.getSequence ();
344 for_each (ses_v.begin (), ses_v.end(), PT < sesElem, stream > (out));
350 template <
typename storedData,
template <
typename SEET,
typename STRT >
class ST >
352 sesElemVec ses_v =
ses.getSequence();
353 for_each(ses_v.begin(), ses_v.end(), ST < sesElem, storedData >(sd));
359 template <
typename stream >
365 printUnifiedFormat< ostream >(out);
371 template <
typename stream >
377 printUnifiedFormat< ostream >(hunks, out);
384 sesElemVec common[2];
386 sesElemVec ses_v =
ses.getSequence();
388 long long length = distance(ses_v.begin(), ses_v.end());
389 long long middle = 0;
390 bool isMiddle, isAfter;
392 long long a, b, c, d;
393 long long inc_dec_count = 0;
398 isMiddle = isAfter =
false;
401 for (sesElemVec_iter it=ses_v.begin();it!=ses_v.end();++it, ++l_cnt) {
403 switch (einfo.
type) {
408 if (!isMiddle) isMiddle =
true;
410 if (l_cnt >= length) {
419 deletes.push_back(*it);
420 if (!isMiddle) isMiddle =
true;
422 if (l_cnt >= length) {
430 if (common[1].empty() && adds.empty() && deletes.empty() && change.empty()) {
432 if (a == 0 && c == 0) {
441 common[0].push_back(*it);
443 rotate(common[0].begin(), common[0].begin() + 1, common[0].end());
444 common[0].pop_back();
445 common[0].push_back(*it);
450 if (isMiddle && !isAfter) {
454 change.push_back(*it);
467 if (isAfter && !change.empty()) {
468 sesElemVec_iter cit = it;
481 long long c0size =
static_cast<long long>(common[0].size());
482 rotate(common[0].begin(),
486 common[0].pop_back();
498 hunk.
common[0] = common[0];
500 hunk.
common[1] = common[1];
510 a = b = c = d = middle = inc_dec_count = 0;
518 template <
typename stream>
523 long long x_idx, y_idx;
525 while (getline(st, line)) {
526 elem mark(line.begin(), line.begin() + 1);
527 elem e(line.begin() + 1, line.end());
548 M = distance(A.begin(), A.end());
549 N = distance(
B.begin(),
B.end());
569 long long snake(
const long long& k,
const long long& above,
const long long& below) {
571 long long y = max(above, below);
573 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]))) {
580 p.
x = x;p.
y = y;p.
k = r;
590 sequence_const_iter x(A.begin());
591 sequence_const_iter y(
B.begin());
592 long long x_idx, y_idx;
593 long long px_idx, py_idx;
594 bool complete =
false;
597 for (
size_t i=v.size()-1;!complete;--i) {
598 while(px_idx < v[i].x || py_idx < v[i].y) {
599 if (v[i].y - v[i].x > py_idx - px_idx) {
608 }
else if (v[i].y - v[i].x < py_idx - px_idx) {
633 if (i == 0) complete =
true;
636 if (x_idx >
static_cast<long long>(
M) && y_idx >
static_cast<long long>(
N)) {
652 sequence A_(A.begin() + (
size_t)x_idx - 1, A.end());
653 sequence B_(
B.begin() + (
size_t)y_idx - 1,
B.end());
656 M = distance(A.begin(), A.end());
657 N = distance(
B.begin(),
B.end());
661 fp =
new long long[
M +
N + 3];
662 fill(&
fp[0], &
fp[
M +
N + 3], -1);
676 ses.addSequence(*it, idx, 0, et);
681 ses.addSequence(*it, idx, 0, et);
688 void inline joinSesVec (sesElemVec& s1, sesElemVec& s2)
const {
690 for (sesElemVec_iter vit=s2.begin();vit!=s2.end();++vit) {