suwako / ShaderPlayground

master
ブランチ master
ShaderPlayground / deps / imgui / ImGuiColorTextEdit / dtl.h
42.4 KB、1284行 生 Blame 履歴
1/**
2 dtl -- Diff Template Library
3
4 In short, Diff Template Library is distributed under so called "BSD license",
5
6 Copyright (c) 2015 Tatsuhiko Kubo <cubicdaiya@gmail.com>
7 All rights reserved.
8
9 Redistribution and use in source and binary forms, with or without modification,
10 are permitted provided that the following conditions are met:
11
12 * Redistributions of source code must retain the above copyright notice,
13 this list of conditions and the following disclaimer.
14
15 * Redistributions in binary form must reproduce the above copyright notice,
16 this list of conditions and the following disclaimer in the documentation
17 and/or other materials provided with the distribution.
18
19 * Neither the name of the authors nor the names of its contributors
20 may be used to endorse or promote products derived from this software
21 without specific prior written permission.
22
23 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
24 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
25 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
26 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
27 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
28 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
29 TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
30 PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
31 LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
32 NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
33 SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
34*/
35
36#ifndef DTL_H
37#define DTL_H
38
39
40#ifndef DTL_VARIABLES_H
41#define DTL_VARIABLES_H
42
43#include <vector>
44#include <list>
45#include <string>
46#include <algorithm>
47#include <iostream>
48
49namespace dtl {
50
51 using std::vector;
52 using std::string;
53 using std::pair;
54 using std::ostream;
55 using std::list;
56 using std::for_each;
57 using std::distance;
58 using std::fill;
59 using std::cout;
60 using std::endl;
61 using std::rotate;
62 using std::swap;
63 using std::max;
64
65 /**
66 * version string
67 */
68 const string version = "1.21";
69
70 /**
71 * type of edit for SES
72 */
73 typedef int edit_t;
74 const edit_t SES_DELETE = -1;
75 const edit_t SES_COMMON = 0;
76 const edit_t SES_ADD = 1;
77
78 /**
79 * mark of SES
80 */
81#define SES_MARK_DELETE "-"
82#define SES_MARK_COMMON " "
83#define SES_MARK_ADD "+"
84
85 /**
86 * info for Unified Format
87 */
88 typedef struct eleminfo {
89 long long beforeIdx; // index of prev sequence
90 long long afterIdx; // index of after sequence
91 edit_t type; // type of edit(Add, Delete, Common)
92 bool operator==(const eleminfo& other) const{
93 return (this->beforeIdx == other.beforeIdx && this->afterIdx == other.afterIdx && this->type == other.type);
94 }
95 } elemInfo;
96
97 const long long DTL_SEPARATE_SIZE = 3;
98 const long long DTL_CONTEXT_SIZE = 3;
99
100 /**
101 * cordinate for registering route
102 */
103 typedef struct Point {
104 long long x; // x cordinate
105 long long y; // y cordinate
106 long long k; // vertex
107 } P;
108
109 /**
110 * limit of cordinate size
111 */
112 const unsigned long long MAX_CORDINATES_SIZE = 2000000;
113
114 typedef vector< long long > editPath;
115 typedef vector< P > editPathCordinates;
116
117 /**
118 * Structure of Unified Format Hunk
119 */
120 template <typename sesElem>
121 struct uniHunk {
122 long long a, b, c, d; // @@ -a,b +c,d @@
123 vector< sesElem > common[2]; // anteroposterior commons on changes
124 vector< sesElem > change; // changes
125 long long inc_dec_count; // count of increace and decrease
126 };
127
128#define dtl_typedefs(elem, sequence) \
129 typedef pair< elem, elemInfo > sesElem; \
130 typedef vector< sesElem > sesElemVec; \
131 typedef vector< uniHunk< sesElem > > uniHunkVec; \
132 typedef list< elem > elemList; \
133 typedef vector< elem > elemVec; \
134 typedef typename uniHunkVec::iterator uniHunkVec_iter; \
135 typedef typename sesElemVec::iterator sesElemVec_iter; \
136 typedef typename elemList::iterator elemList_iter; \
137 typedef typename sequence::iterator sequence_iter; \
138 typedef typename sequence::const_iterator sequence_const_iter; \
139 typedef typename elemVec::iterator elemVec_iter;
140
141
142}
143
144#endif // DTL_VARIABLES_H
145
146#ifndef DTL_FUNCTORS_H
147#define DTL_FUNCTORS_H
148
149namespace dtl {
150
151 /**
152 * printer class template
153 */
154 template <typename sesElem, typename stream = ostream >
155 class Printer
156 {
157 public :
158 Printer () : out_(cout) {}
159 Printer (stream& out) : out_(out) {}
160 virtual ~Printer () {}
161 virtual void operator() (const sesElem& se) const = 0;
162 protected :
163 stream& out_;
164 };
165
166 /**
167 * common element printer class template
168 */
169 template <typename sesElem, typename stream = ostream >
170 class CommonPrinter : public Printer < sesElem, stream >
171 {
172 public :
173 CommonPrinter () : Printer < sesElem, stream > () {}
174 CommonPrinter (stream& out) : Printer < sesElem, stream > (out) {}
175 ~CommonPrinter () {}
176 void operator() (const sesElem& se) const {
177 this->out_ << SES_MARK_COMMON << se.first << endl;
178 }
179 };
180
181 /**
182 * ses element printer class template
183 */
184 template <typename sesElem, typename stream = ostream >
185 class ChangePrinter : public Printer < sesElem, stream >
186 {
187 public :
188 ChangePrinter () : Printer < sesElem, stream > () {}
189 ChangePrinter (stream& out) : Printer < sesElem, stream > (out) {}
190 ~ChangePrinter () {}
191 void operator() (const sesElem& se) const {
192 switch (se.second.type) {
193 case SES_ADD:
194 this->out_ << SES_MARK_ADD << se.first << endl;
195 break;
196 case SES_DELETE:
197 this->out_ << SES_MARK_DELETE << se.first << endl;
198 break;
199 case SES_COMMON:
200 this->out_ << SES_MARK_COMMON << se.first << endl;
201 break;
202 }
203 }
204 };
205
206 /**
207 * unified format element printer class template
208 */
209 template <typename sesElem, typename stream = ostream >
210 class UniHunkPrinter
211 {
212 public :
213 UniHunkPrinter () : out_(cout) {}
214 UniHunkPrinter (stream& out) : out_(out) {}
215 ~UniHunkPrinter () {}
216 void operator() (const uniHunk< sesElem >& hunk) const {
217 out_ << "@@"
218 << " -" << hunk.a << "," << hunk.b
219 << " +" << hunk.c << "," << hunk.d
220 << " @@" << endl;
221
222 for_each(hunk.common[0].begin(), hunk.common[0].end(), CommonPrinter< sesElem, stream >(out_));
223 for_each(hunk.change.begin(), hunk.change.end(), ChangePrinter< sesElem, stream >(out_));
224 for_each(hunk.common[1].begin(), hunk.common[1].end(), CommonPrinter< sesElem, stream >(out_));
225 }
226 private :
227 stream& out_;
228 };
229
230 /**
231 * storage class template
232 */
233 template <typename sesElem, typename storedData >
234 class Storage
235 {
236 public:
237 Storage(storedData& sd) : storedData_(sd) {}
238 virtual ~Storage() {}
239 virtual void operator() (const sesElem& se) const = 0;
240 protected:
241 storedData& storedData_;
242 };
243
244 /**
245 * compare class template
246 */
247 template <typename elem>
248 class Compare
249 {
250 public :
251 Compare () {}
252 virtual ~Compare () {}
253 virtual inline bool impl (const elem& e1, const elem& e2) const {
254 return e1 == e2;
255 }
256 };
257}
258
259#endif // DTL_FUNCTORS_H
260
261#ifndef DTL_SEQUENCE_H
262#define DTL_SEQUENCE_H
263
264namespace dtl {
265
266 /**
267 * sequence class template
268 */
269 template <typename elem>
270 class Sequence
271 {
272 public :
273 typedef vector< elem > elemVec;
274 Sequence () {}
275 virtual ~Sequence () {}
276
277 elemVec getSequence () const {
278 return sequence;
279 }
280 void addSequence (elem e) {
281 sequence.push_back(e);
282 }
283 protected :
284 elemVec sequence;
285 };
286}
287
288#endif // DTL_SEQUENCE_H
289
290#ifndef DTL_LCS_H
291#define DTL_LCS_H
292
293namespace dtl {
294
295 /**
296 * Longest Common Subsequence template class
297 */
298 template <typename elem>
299 class Lcs : public Sequence< elem >
300 {
301 public :
302 Lcs () {}
303 ~Lcs () {}
304 };
305}
306
307#endif // DTL_LCS_H
308
309#ifndef DTL_SES_H
310#define DTL_SES_H
311
312namespace dtl {
313
314 /**
315 * Shortest Edit Script template class
316 */
317 template <typename elem>
318 class Ses : public Sequence< elem >
319 {
320 private :
321 typedef pair< elem, elemInfo > sesElem;
322 typedef vector< sesElem > sesElemVec;
323 public :
324
325 Ses () : onlyAdd(true), onlyDelete(true), onlyCopy(true), deletesFirst(false) {
326 nextDeleteIdx = 0;
327 }
328 Ses (bool moveDel) : onlyAdd(true), onlyDelete(true), onlyCopy(true), deletesFirst(moveDel) {
329 nextDeleteIdx = 0;
330 }
331 ~Ses () {}
332
333 bool isOnlyAdd () const {
334 return onlyAdd;
335 }
336
337 bool isOnlyDelete () const {
338 return onlyDelete;
339 }
340
341 bool isOnlyCopy () const {
342 return onlyCopy;
343 }
344
345 bool isOnlyOneOperation () const {
346 return isOnlyAdd() || isOnlyDelete() || isOnlyCopy();
347 }
348
349 bool isChange () const {
350 return !onlyCopy;
351 }
352
353 using Sequence< elem >::addSequence;
354 void addSequence (elem e, long long beforeIdx, long long afterIdx, const edit_t type) {
355 elemInfo info;
356 info.beforeIdx = beforeIdx;
357 info.afterIdx = afterIdx;
358 info.type = type;
359 sesElem pe(e, info);
360 if (!deletesFirst) {
361 sequence.push_back(pe);
362 }
363 switch (type) {
364 case SES_DELETE:
365 onlyCopy = false;
366 onlyAdd = false;
367 if (deletesFirst) {
368 sequence.insert(sequence.begin() + nextDeleteIdx, pe);
369 nextDeleteIdx++;
370 }
371 break;
372 case SES_COMMON:
373 onlyAdd = false;
374 onlyDelete = false;
375 if (deletesFirst) {
376 sequence.push_back(pe);
377 nextDeleteIdx = sequence.size();
378 }
379 break;
380 case SES_ADD:
381 onlyDelete = false;
382 onlyCopy = false;
383 if (deletesFirst) {
384 sequence.push_back(pe);
385 }
386 break;
387 }
388 }
389
390 sesElemVec getSequence () const {
391 return sequence;
392 }
393 private :
394 sesElemVec sequence;
395 bool onlyAdd;
396 bool onlyDelete;
397 bool onlyCopy;
398 bool deletesFirst;
399 size_t nextDeleteIdx;
400 };
401}
402
403#endif // DTL_SES_H
404
405#ifndef DTL_DIFF_H
406#define DTL_DIFF_H
407
408namespace dtl {
409
410 /**
411 * diff class template
412 * sequence must support random_access_iterator.
413 */
414 template <typename elem, typename sequence = vector< elem >, typename comparator = Compare< elem > >
415 class Diff
416 {
417 private :
418 dtl_typedefs(elem, sequence)
419 sequence A;
420 sequence B;
421 size_t M;
422 size_t N;
423 size_t delta;
424 size_t offset;
425 long long *fp;
426 long long editDistance;
427 Lcs< elem > lcs;
428 Ses< elem > ses;
429 editPath path;
430 editPathCordinates pathCordinates;
431 bool swapped;
432 bool huge;
433 bool trivial;
434 bool editDistanceOnly;
435 uniHunkVec uniHunks;
436 comparator cmp;
437 long long ox;
438 long long oy;
439 public :
440 Diff () {}
441
442 Diff (const sequence& a,
443 const sequence& b) : A(a), B(b), ses(false) {
444 init();
445 }
446
447 Diff (const sequence& a,
448 const sequence& b,
449 bool deletesFirst) : A(a), B(b), ses(deletesFirst) {
450 init();
451 }
452
453 Diff (const sequence& a,
454 const sequence& b,
455 const comparator& comp) : A(a), B(b), ses(false), cmp(comp) {
456 init();
457 }
458
459 Diff (const sequence& a,
460 const sequence& b,
461 bool deleteFirst,
462 const comparator& comp) : A(a), B(b), ses(deleteFirst), cmp(comp) {
463 init();
464 }
465
466 ~Diff() {}
467
468 long long getEditDistance () const {
469 return editDistance;
470 }
471
472 Lcs< elem > getLcs () const {
473 return lcs;
474 }
475
476 elemVec getLcsVec () const {
477 return lcs.getSequence();
478 }
479
480 Ses< elem > getSes () const {
481 return ses;
482 }
483
484 uniHunkVec getUniHunks () const {
485 return uniHunks;
486 }
487
488 /* These should be deprecated */
489 bool isHuge () const {
490 return huge;
491 }
492
493 void onHuge () {
494 this->huge = true;
495 }
496
497 void offHuge () {
498 this->huge = false;
499 }
500
501 bool isUnserious () const {
502 return trivial;
503 }
504
505 void onUnserious () {
506 this->trivial = true;
507 }
508
509 void offUnserious () {
510 this->trivial = false;
511 }
512
513 void onOnlyEditDistance () {
514 this->editDistanceOnly = true;
515 }
516
517 /* These are the replacements for the above */
518 bool hugeEnabled () const {
519 return huge;
520 }
521
522 void enableHuge () {
523 this->huge = true;
524 }
525
526 void disableHuge () {
527 this->huge = false;
528 }
529
530 bool trivialEnabled () const {
531 return trivial;
532 }
533
534 void enableTrivial () {
535 this->trivial = true;
536 }
537
538 void disableTrivial () {
539 this->trivial = false;
540 }
541
542 void editDistanceOnlyEnabled () {
543 this->editDistanceOnly = true;
544 }
545
546 /**
547 * patching with Unified Format Hunks
548 */
549 sequence uniPatch (const sequence& seq) {
550 elemList seqLst(seq.begin(), seq.end());
551 sesElemVec shunk;
552 sesElemVec_iter vsesIt;
553 elemList_iter lstIt = seqLst.begin();
554 long long inc_dec_total = 0;
555 long long gap = 1;
556 for (uniHunkVec_iter it=uniHunks.begin();it!=uniHunks.end();++it) {
557 joinSesVec(shunk, it->common[0]);
558 joinSesVec(shunk, it->change);
559 joinSesVec(shunk, it->common[1]);
560 it->a += inc_dec_total;
561 inc_dec_total += it->inc_dec_count;
562 for (long long i=0;i<it->a - gap;++i) {
563 ++lstIt;
564 }
565 gap = it->a + it->b + it->inc_dec_count;
566 vsesIt = shunk.begin();
567 while (vsesIt!=shunk.end()) {
568 switch (vsesIt->second.type) {
569 case SES_ADD :
570 seqLst.insert(lstIt, vsesIt->first);
571 break;
572 case SES_DELETE :
573 if (lstIt != seqLst.end()) {
574 lstIt = seqLst.erase(lstIt);
575 }
576 break;
577 case SES_COMMON :
578 if (lstIt != seqLst.end()) {
579 ++lstIt;
580 }
581 break;
582 default :
583 // no fall-through
584 break;
585 }
586 ++vsesIt;
587 }
588 shunk.clear();
589 }
590
591 sequence patchedSeq(seqLst.begin(), seqLst.end());
592 return patchedSeq;
593 }
594
595 /**
596 * patching with Shortest Edit Script (SES)
597 */
598 sequence patch (const sequence& seq) const {
599 sesElemVec sesSeq = ses.getSequence();
600 elemList seqLst(seq.begin(), seq.end());
601 elemList_iter lstIt = seqLst.begin();
602 for (sesElemVec_iter sesIt=sesSeq.begin();sesIt!=sesSeq.end();++sesIt) {
603 switch (sesIt->second.type) {
604 case SES_ADD :
605 seqLst.insert(lstIt, sesIt->first);
606 break;
607 case SES_DELETE :
608 lstIt = seqLst.erase(lstIt);
609 break;
610 case SES_COMMON :
611 ++lstIt;
612 break;
613 default :
614 // no through
615 break;
616 }
617 }
618 sequence patchedSeq(seqLst.begin(), seqLst.end());
619 return patchedSeq;
620 }
621
622 /**
623 * compose Longest Common Subsequence and Shortest Edit Script.
624 * The algorithm implemented here is based on "An O(NP) Sequence Comparison Algorithm"
625 * described by Sun Wu, Udi Manber and Gene Myers
626 */
627 void compose() {
628
629 if (isHuge()) {
630 pathCordinates.reserve(MAX_CORDINATES_SIZE);
631 }
632 ox = 0;
633 oy = 0;
634 long long p = -1;
635 fp = new long long[M + N + 3];
636 fill(&fp[0], &fp[M + N + 3], -1);
637 path = editPath(M + N + 3);
638 fill(path.begin(), path.end(), -1);
639 ONP:
640 do {
641 ++p;
642 for (long long k=-p;k<=static_cast<long long>(delta)-1;++k) {
643 fp[k+offset] = snake(k, fp[k-1+offset]+1, fp[k+1+offset]);
644 }
645 for (long long k=static_cast<long long>(delta)+p;k>=static_cast<long long>(delta)+1;--k) {
646 fp[k+offset] = snake(k, fp[k-1+offset]+1, fp[k+1+offset]);
647 }
648 fp[delta+offset] = snake(static_cast<long long>(delta), fp[delta-1+offset]+1, fp[delta+1+offset]);
649 } while (fp[delta+offset] != static_cast<long long>(N) && pathCordinates.size() < MAX_CORDINATES_SIZE);
650
651 editDistance += static_cast<long long>(delta) + 2 * p;
652 long long r = path[delta+offset];
653 P cordinate;
654 editPathCordinates epc(0);
655
656 // recording edit distance only
657 if (editDistanceOnly) {
658 delete[] this->fp;
659 return;
660 }
661
662 while(r != -1) {
663 cordinate.x = pathCordinates[(size_t)r].x;
664 cordinate.y = pathCordinates[(size_t)r].y;
665 epc.push_back(cordinate);
666 r = pathCordinates[(size_t)r].k;
667 }
668
669 // record Longest Common Subsequence & Shortest Edit Script
670 if (!recordSequence(epc)) {
671 pathCordinates.resize(0);
672 epc.resize(0);
673 p = -1;
674 goto ONP;
675 }
676 delete[] this->fp;
677 }
678
679 /**
680 * print difference between A and B as an SES
681 */
682 template < typename stream >
683 void printSES (stream& out) const {
684 sesElemVec ses_v = ses.getSequence();
685 for_each(ses_v.begin(), ses_v.end(), ChangePrinter< sesElem, stream >(out));
686 }
687
688 void printSES (ostream& out = cout) const {
689 printSES< ostream >(out);
690 }
691
692 /**
693 * print differences given an SES
694 */
695 template < typename stream >
696 static void printSES (const Ses< elem >& s, stream& out) {
697 sesElemVec ses_v = s.getSequence();
698 for_each(ses_v.begin(), ses_v.end(), ChangePrinter< sesElem, stream >(out));
699 }
700
701 static void printSES (const Ses< elem >& s, ostream& out = cout) {
702 printSES< ostream >(s, out);
703 }
704
705 /**
706 * print difference between A and B as an SES with custom printer
707 */
708 template < typename stream, template < typename SEET, typename STRT > class PT >
709 void printSES (stream& out) const {
710 sesElemVec ses_v = ses.getSequence ();
711 for_each (ses_v.begin (), ses_v.end(), PT < sesElem, stream > (out));
712 }
713
714 /**
715 * store difference between A and B as an SES with custom storage
716 */
717 template < typename storedData, template < typename SEET, typename STRT > class ST >
718 void storeSES(storedData& sd) const {
719 sesElemVec ses_v = ses.getSequence();
720 for_each(ses_v.begin(), ses_v.end(), ST < sesElem, storedData >(sd));
721 }
722
723 /**
724 * print difference between A and B in the Unified Format
725 */
726 template < typename stream >
727 void printUnifiedFormat (stream& out) const {
728 for_each(uniHunks.begin(), uniHunks.end(), UniHunkPrinter< sesElem, stream >(out));
729 }
730
731 void printUnifiedFormat (ostream& out = cout) const {
732 printUnifiedFormat< ostream >(out);
733 }
734
735 /**
736 * print unified format difference with given unified format hunks
737 */
738 template < typename stream >
739 static void printUnifiedFormat (const uniHunkVec& hunks, stream& out) {
740 for_each(hunks.begin(), hunks.end(), UniHunkPrinter< sesElem >(out));
741 }
742
743 static void printUnifiedFormat (const uniHunkVec& hunks, ostream& out = cout) {
744 printUnifiedFormat< ostream >(hunks, out);
745 }
746
747 /**
748 * compose Unified Format Hunks from Shortest Edit Script
749 */
750 void composeUnifiedHunks () {
751 sesElemVec common[2];
752 sesElemVec change;
753 sesElemVec ses_v = ses.getSequence();
754 long long l_cnt = 1;
755 long long length = distance(ses_v.begin(), ses_v.end());
756 long long middle = 0;
757 bool isMiddle, isAfter;
758 elemInfo einfo;
759 long long a, b, c, d; // @@ -a,b +c,d @@
760 long long inc_dec_count = 0;
761 uniHunk< sesElem > hunk;
762 sesElemVec adds;
763 sesElemVec deletes;
764
765 isMiddle = isAfter = false;
766 a = b = c = d = 0;
767
768 for (sesElemVec_iter it=ses_v.begin();it!=ses_v.end();++it, ++l_cnt) {
769 einfo = it->second;
770 switch (einfo.type) {
771 case SES_ADD :
772 middle = 0;
773 ++inc_dec_count;
774 adds.push_back(*it);
775 if (!isMiddle) isMiddle = true;
776 if (isMiddle) ++d;
777 if (l_cnt >= length) {
778 joinSesVec(change, deletes);
779 joinSesVec(change, adds);
780 isAfter = true;
781 }
782 break;
783 case SES_DELETE :
784 middle = 0;
785 --inc_dec_count;
786 deletes.push_back(*it);
787 if (!isMiddle) isMiddle = true;
788 if (isMiddle) ++b;
789 if (l_cnt >= length) {
790 joinSesVec(change, deletes);
791 joinSesVec(change, adds);
792 isAfter = true;
793 }
794 break;
795 case SES_COMMON :
796 ++b;++d;
797 if (common[1].empty() && adds.empty() && deletes.empty() && change.empty()) {
798 if (static_cast<long long>(common[0].size()) < DTL_CONTEXT_SIZE) {
799 if (a == 0 && c == 0) {
800 if (!wasSwapped()) {
801 a = einfo.beforeIdx;
802 c = einfo.afterIdx;
803 } else {
804 a = einfo.afterIdx;
805 c = einfo.beforeIdx;
806 }
807 }
808 common[0].push_back(*it);
809 } else {
810 rotate(common[0].begin(), common[0].begin() + 1, common[0].end());
811 common[0].pop_back();
812 common[0].push_back(*it);
813 ++a;++c;
814 --b;--d;
815 }
816 }
817 if (isMiddle && !isAfter) {
818 ++middle;
819 joinSesVec(change, deletes);
820 joinSesVec(change, adds);
821 change.push_back(*it);
822 if (middle >= DTL_SEPARATE_SIZE || l_cnt >= length) {
823 isAfter = true;
824 }
825 adds.clear();
826 deletes.clear();
827 }
828 break;
829 default :
830 // no through
831 break;
832 }
833 // compose unified format hunk
834 if (isAfter && !change.empty()) {
835 sesElemVec_iter cit = it;
836 long long cnt = 0;
837 for (long long i=0;i<DTL_SEPARATE_SIZE && (cit != ses_v.end());++i, ++cit) {
838 if (cit->second.type == SES_COMMON) {
839 ++cnt;
840 }
841 }
842 if (cnt < DTL_SEPARATE_SIZE && l_cnt < length) {
843 middle = 0;
844 isAfter = false;
845 continue;
846 }
847 if (static_cast<long long>(common[0].size()) >= DTL_SEPARATE_SIZE) {
848 long long c0size = static_cast<long long>(common[0].size());
849 rotate(common[0].begin(),
850 common[0].begin() + (size_t)c0size - DTL_SEPARATE_SIZE,
851 common[0].end());
852 for (long long i=0;i<c0size - DTL_SEPARATE_SIZE;++i) {
853 common[0].pop_back();
854 }
855 a += c0size - DTL_SEPARATE_SIZE;
856 c += c0size - DTL_SEPARATE_SIZE;
857 }
858 if (a == 0) ++a;
859 if (c == 0) ++c;
860 if (wasSwapped()) swap(a, c);
861 hunk.a = a;
862 hunk.b = b;
863 hunk.c = c;
864 hunk.d = d;
865 hunk.common[0] = common[0];
866 hunk.change = change;
867 hunk.common[1] = common[1];
868 hunk.inc_dec_count = inc_dec_count;
869 uniHunks.push_back(hunk);
870 isMiddle = false;
871 isAfter = false;
872 common[0].clear();
873 common[1].clear();
874 adds.clear();
875 deletes.clear();
876 change.clear();
877 a = b = c = d = middle = inc_dec_count = 0;
878 }
879 }
880 }
881
882 /**
883 * compose ses from stream
884 */
885 template <typename stream>
886 static Ses< elem > composeSesFromStream (stream& st)
887 {
888 elem line;
889 Ses< elem > ret;
890 long long x_idx, y_idx;
891 x_idx = y_idx = 1;
892 while (getline(st, line)) {
893 elem mark(line.begin(), line.begin() + 1);
894 elem e(line.begin() + 1, line.end());
895 if (mark == SES_MARK_DELETE) {
896 ret.addSequence(e, x_idx, 0, SES_DELETE);
897 ++x_idx;
898 } else if (mark == SES_MARK_ADD) {
899 ret.addSequence(e, y_idx, 0, SES_ADD);
900 ++y_idx;
901 } else if (mark == SES_MARK_COMMON) {
902 ret.addSequence(e, x_idx, y_idx, SES_COMMON);
903 ++x_idx;
904 ++y_idx;
905 }
906 }
907 return ret;
908 }
909
910 private :
911 /**
912 * initialize
913 */
914 void init () {
915 M = distance(A.begin(), A.end());
916 N = distance(B.begin(), B.end());
917 if (M < N) {
918 swapped = false;
919 } else {
920 swap(A, B);
921 swap(M, N);
922 swapped = true;
923 }
924 editDistance = 0;
925 delta = N - M;
926 offset = M + 1;
927 huge = false;
928 trivial = false;
929 editDistanceOnly = false;
930 fp = NULL;
931 }
932
933 /**
934 * search shortest path and record the path
935 */
936 long long snake(const long long& k, const long long& above, const long long& below) {
937 long long r = above > below ? path[(size_t)k-1+offset] : path[(size_t)k+1+offset];
938 long long y = max(above, below);
939 long long x = y - k;
940 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]))) {
941 ++x;++y;
942 }
943
944 path[(size_t)k+offset] = static_cast<long long>(pathCordinates.size());
945 if (!editDistanceOnly) {
946 P p;
947 p.x = x;p.y = y;p.k = r;
948 pathCordinates.push_back(p);
949 }
950 return y;
951 }
952
953 /**
954 * record SES and LCS
955 */
956 bool recordSequence (const editPathCordinates& v) {
957 sequence_const_iter x(A.begin());
958 sequence_const_iter y(B.begin());
959 long long x_idx, y_idx; // line number for Unified Format
960 long long px_idx, py_idx; // cordinates
961 bool complete = false;
962 x_idx = y_idx = 1;
963 px_idx = py_idx = 0;
964 for (size_t i=v.size()-1;!complete;--i) {
965 while(px_idx < v[i].x || py_idx < v[i].y) {
966 if (v[i].y - v[i].x > py_idx - px_idx) {
967 if (!wasSwapped()) {
968 ses.addSequence(*y, 0, y_idx + oy, SES_ADD);
969 } else {
970 ses.addSequence(*y, y_idx + oy, 0, SES_DELETE);
971 }
972 ++y;
973 ++y_idx;
974 ++py_idx;
975 } else if (v[i].y - v[i].x < py_idx - px_idx) {
976 if (!wasSwapped()) {
977 ses.addSequence(*x, x_idx + ox, 0, SES_DELETE);
978 } else {
979 ses.addSequence(*x, 0, x_idx + ox, SES_ADD);
980 }
981 ++x;
982 ++x_idx;
983 ++px_idx;
984 } else {
985 if (!wasSwapped()) {
986 lcs.addSequence(*x);
987 ses.addSequence(*x, x_idx + ox, y_idx + oy, SES_COMMON);
988 } else {
989 lcs.addSequence(*y);
990 ses.addSequence(*y, y_idx + oy, x_idx + ox, SES_COMMON);
991 }
992 ++x;
993 ++y;
994 ++x_idx;
995 ++y_idx;
996 ++px_idx;
997 ++py_idx;
998 }
999 }
1000 if (i == 0) complete = true;
1001 }
1002
1003 if (x_idx > static_cast<long long>(M) && y_idx > static_cast<long long>(N)) {
1004 // all recording succeeded
1005 } else {
1006 // trivial difference
1007 if (trivialEnabled()) {
1008 if (!wasSwapped()) {
1009 recordOddSequence(x_idx, M, x, SES_DELETE);
1010 recordOddSequence(y_idx, N, y, SES_ADD);
1011 } else {
1012 recordOddSequence(x_idx, M, x, SES_ADD);
1013 recordOddSequence(y_idx, N, y, SES_DELETE);
1014 }
1015 return true;
1016 }
1017
1018 // nontrivial difference
1019 sequence A_(A.begin() + (size_t)x_idx - 1, A.end());
1020 sequence B_(B.begin() + (size_t)y_idx - 1, B.end());
1021 A = A_;
1022 B = B_;
1023 M = distance(A.begin(), A.end());
1024 N = distance(B.begin(), B.end());
1025 delta = N - M;
1026 offset = M + 1;
1027 delete[] fp;
1028 fp = new long long[M + N + 3];
1029 fill(&fp[0], &fp[M + N + 3], -1);
1030 fill(path.begin(), path.end(), -1);
1031 ox = x_idx - 1;
1032 oy = y_idx - 1;
1033 return false;
1034 }
1035 return true;
1036 }
1037
1038 /**
1039 * record odd sequence in SES
1040 */
1041 void inline recordOddSequence (long long idx, long long length, sequence_const_iter it, const edit_t et) {
1042 while(idx < length){
1043 ses.addSequence(*it, idx, 0, et);
1044 ++it;
1045 ++idx;
1046 ++editDistance;
1047 }
1048 ses.addSequence(*it, idx, 0, et);
1049 ++editDistance;
1050 }
1051
1052 /**
1053 * join SES vectors
1054 */
1055 void inline joinSesVec (sesElemVec& s1, sesElemVec& s2) const {
1056 if (!s2.empty()) {
1057 for (sesElemVec_iter vit=s2.begin();vit!=s2.end();++vit) {
1058 s1.push_back(*vit);
1059 }
1060 }
1061 }
1062
1063 /**
1064 * check if the sequences have been swapped
1065 */
1066 bool inline wasSwapped () const {
1067 return swapped;
1068 }
1069
1070 };
1071}
1072
1073#endif // DTL_DIFF_H
1074
1075#ifndef DTL_DIFF3_H
1076#define DTL_DIFF3_H
1077
1078namespace dtl {
1079
1080 /**
1081 * diff3 class template
1082 * sequence must support random_access_iterator.
1083 */
1084 template <typename elem, typename sequence = vector< elem >, typename comparator = Compare< elem > >
1085 class Diff3
1086 {
1087 private:
1088 dtl_typedefs(elem, sequence)
1089 sequence A;
1090 sequence B;
1091 sequence C;
1092 sequence S;
1093 Diff< elem, sequence, comparator > diff_ba;
1094 Diff< elem, sequence, comparator > diff_bc;
1095 bool conflict;
1096 elem csepabegin;
1097 elem csepa;
1098 elem csepaend;
1099 public :
1100 Diff3 () {}
1101 Diff3 (const sequence& a,
1102 const sequence& b,
1103 const sequence& c) : A(a), B(b), C(c),
1104 diff_ba(b, a), diff_bc(b, c),
1105 conflict(false) {}
1106
1107 ~Diff3 () {}
1108
1109 bool isConflict () const {
1110 return conflict;
1111 }
1112
1113 sequence getMergedSequence () const {
1114 return S;
1115 }
1116
1117 /**
1118 * merge changes B and C into A
1119 */
1120 bool merge () {
1121 if (diff_ba.getEditDistance() == 0) { // A == B
1122 if (diff_bc.getEditDistance() == 0) { // A == B == C
1123 S = B;
1124 return true;
1125 }
1126 S = C;
1127 return true;
1128 } else { // A != B
1129 if (diff_bc.getEditDistance() == 0) { // A != B == C
1130 S = A;
1131 return true;
1132 } else { // A != B != C
1133 S = merge_();
1134 if (isConflict()) { // conflict occured
1135 return false;
1136 }
1137 }
1138 }
1139 return true;
1140 }
1141
1142 /**
1143 * compose differences
1144 */
1145 void compose () {
1146 diff_ba.compose();
1147 diff_bc.compose();
1148 }
1149
1150 private :
1151 /**
1152 * merge implementation
1153 */
1154 sequence merge_ () {
1155 elemVec seq;
1156 Ses< elem > ses_ba = diff_ba.getSes();
1157 Ses< elem > ses_bc = diff_bc.getSes();
1158 sesElemVec ses_ba_v = ses_ba.getSequence();
1159 sesElemVec ses_bc_v = ses_bc.getSequence();
1160 sesElemVec_iter ba_it = ses_ba_v.begin();
1161 sesElemVec_iter bc_it = ses_bc_v.begin();
1162 sesElemVec_iter ba_end = ses_ba_v.end();
1163 sesElemVec_iter bc_end = ses_bc_v.end();
1164
1165 while (!isEnd(ba_end, ba_it) || !isEnd(bc_end, bc_it)) {
1166 while (true) {
1167 if (!isEnd(ba_end, ba_it) &&
1168 !isEnd(bc_end, bc_it) &&
1169 ba_it->first == bc_it->first &&
1170 ba_it->second.type == SES_COMMON &&
1171 bc_it->second.type == SES_COMMON) {
1172 // do nothing
1173 } else {
1174 break;
1175 }
1176 if (!isEnd(ba_end, ba_it)) seq.push_back(ba_it->first);
1177 else if (!isEnd(bc_end, bc_it)) seq.push_back(bc_it->first);
1178 forwardUntilEnd(ba_end, ba_it);
1179 forwardUntilEnd(bc_end, bc_it);
1180 }
1181 if (isEnd(ba_end, ba_it) || isEnd(bc_end, bc_it)) break;
1182 if ( ba_it->second.type == SES_COMMON
1183 && bc_it->second.type == SES_DELETE) {
1184 forwardUntilEnd(ba_end, ba_it);
1185 forwardUntilEnd(bc_end, bc_it);
1186 } else if (ba_it->second.type == SES_COMMON &&
1187 bc_it->second.type == SES_ADD) {
1188 seq.push_back(bc_it->first);
1189 forwardUntilEnd(bc_end, bc_it);
1190 } else if (ba_it->second.type == SES_DELETE &&
1191 bc_it->second.type == SES_COMMON) {
1192 forwardUntilEnd(ba_end, ba_it);
1193 forwardUntilEnd(bc_end, bc_it);
1194 } else if (ba_it->second.type == SES_DELETE &&
1195 bc_it->second.type == SES_DELETE) {
1196 if (ba_it->first == bc_it->first) {
1197 forwardUntilEnd(ba_end, ba_it);
1198 forwardUntilEnd(bc_end, bc_it);
1199 } else {
1200 // conflict
1201 conflict = true;
1202 return B;
1203 }
1204 } else if (ba_it->second.type == SES_DELETE &&
1205 bc_it->second.type == SES_ADD) {
1206 // conflict
1207 conflict = true;
1208 return B;
1209 } else if (ba_it->second.type == SES_ADD &&
1210 bc_it->second.type == SES_COMMON) {
1211 seq.push_back(ba_it->first);
1212 forwardUntilEnd(ba_end, ba_it);
1213 } else if (ba_it->second.type == SES_ADD &&
1214 bc_it->second.type == SES_DELETE) {
1215 // conflict
1216 conflict = true;
1217 return B;
1218 } else if (ba_it->second.type == SES_ADD &&
1219 bc_it->second.type == SES_ADD) {
1220 if (ba_it->first == bc_it->first) {
1221 seq.push_back(ba_it->first);
1222 forwardUntilEnd(ba_end, ba_it);
1223 forwardUntilEnd(bc_end, bc_it);
1224 } else {
1225 // conflict
1226 conflict = true;
1227 return B;
1228 }
1229 }
1230 }
1231
1232 if (isEnd(ba_end, ba_it)) {
1233 addDecentSequence(bc_end, bc_it, seq);
1234 } else if (isEnd(bc_end, bc_it)) {
1235 addDecentSequence(ba_end, ba_it, seq);
1236 }
1237
1238 sequence mergedSeq(seq.begin(), seq.end());
1239 return mergedSeq;
1240 }
1241
1242 /**
1243 * join elem vectors
1244 */
1245 void inline joinElemVec (elemVec& s1, elemVec& s2) const {
1246 if (!s2.empty()) {
1247 for (elemVec_iter vit=s2.begin();vit!=s2.end();++vit) {
1248 s1.push_back(*vit);
1249 }
1250 }
1251 }
1252
1253 /**
1254 * check if sequence is at end
1255 */
1256 template <typename T_iter>
1257 bool inline isEnd (const T_iter& end, const T_iter& it) const {
1258 return it == end ? true : false;
1259 }
1260
1261 /**
1262 * increment iterator until iterator is at end
1263 */
1264 template <typename T_iter>
1265 void inline forwardUntilEnd (const T_iter& end, T_iter& it) const {
1266 if (!isEnd(end, it)) ++it;
1267 }
1268
1269 /**
1270 * add elements whose SES's type is ADD
1271 */
1272 void inline addDecentSequence (const sesElemVec_iter& end, sesElemVec_iter& it, elemVec& seq) const {
1273 while (!isEnd(end, it)) {
1274 if (it->second.type == SES_ADD) seq.push_back(it->first);
1275 ++it;
1276 }
1277 }
1278
1279 };
1280}
1281
1282#endif // DTL_DIFF3_H
1283
1284#endif // DTL_H