1 // ported from Algorithm::Diff, which is Copyright (c) 2000-2002 Ned
2 // Konz.
3
4 #ifndef lcs_hh
5 #define lcs_hh
6
7 #include <vector>
8 #include "lcsimpl.hh"
9
10 // Uses std::less and std::equals_to to compare instances of TItem -
11 // specialize the comparators for types which cannot be compared with
12 // < and == .
13 template<typename TItem, typename TSequence = std::vector<TItem> >
14 class LCS
15 {
16 public:
~LCS()17 virtual ~LCS() { }
18
19 void traverse_balanced(const TSequence &a, const TSequence &b);
20
21 private:
22 virtual void on_match() = 0;
23 virtual void on_insert(TItem n) = 0;
24 virtual void on_delete(TItem m) = 0;
25
26 void discard_a(const TSequence &a, int i);
27 void discard_b(const TSequence &b, int j);
28 };
29
30 template<typename TItem, typename TSequence>
discard_a(const TSequence & a,int i)31 inline void LCS<TItem, TSequence>::discard_a(const TSequence &a, int i)
32 {
33 on_delete(a[i]);
34 }
35
36 template<typename TItem, typename TSequence>
discard_b(const TSequence & b,int j)37 inline void LCS<TItem, TSequence>::discard_b(const TSequence &b, int j)
38 {
39 on_insert(b[j]);
40 }
41
42 template<typename TItem, typename TSequence>
traverse_balanced(const TSequence & a,const TSequence & b)43 void LCS<TItem, TSequence>::traverse_balanced(const TSequence &a,
44 const TSequence &b)
45 {
46 lcsimpl::TSparseVector matchvector =
47 lcsimpl::longest_common_subsequence<TItem, TSequence>(a, b);
48
49 int lasta = a.size() - 1;
50 int lastb = b.size() - 1;
51 int ai = 0;
52 int bi = 0;
53 int ma = -1;
54 int mb;
55
56 int sentinel = 0;
57 if (!matchvector.empty()) {
58 sentinel = matchvector.rbegin()->first;
59 }
60
61 while (true) {
62 do {
63 ma++;
64 } while ((ma <= sentinel) &&
65 (matchvector.find(ma) == matchvector.end()));
66
67 if (ma > sentinel) {
68 goto second;
69 }
70
71 mb = matchvector[ma];
72
73 while ((ai < ma) || (bi < mb)) {
74 if ((ai < ma) && (bi < mb)) {
75 discard_a(a, ai++);
76 discard_b(b, bi++);
77 } else if (ai < ma) {
78 discard_a(a, ai++);
79 } else {
80 discard_b(b, bi++);
81 }
82 }
83
84 on_match();
85 ++ai; ++bi;
86 }
87
88 second:
89 while ((ai <= lasta) || (bi <= lastb)) {
90 if ((ai <= lasta) && (bi <= lastb)) {
91 discard_a(a, ai++);
92 discard_b(b, bi++);
93 } else if (ai <= lasta) {
94 discard_a(a, ai++);
95 } else {
96 discard_b(b, bi++);
97 }
98 }
99 }
100
101 #endif
102
103