Hide
Stay up to dateembedded code automagically updates, each snippet and article has a feed Join Siafoo Now or Learn More

LCS C++ template classes Atom Feed 1

# 's
  1/**
2 Author: Michael Case
3 Date Started: ~ 4/13/2011
4
5 Modification notes:
6 2011-04-26:
7 lcs1.1 : cleaned up a bit.
8 lcs5 : removed clear() requirement;
9 lcs5 : implemented char* specialization for *.
10 requires a null-terminated string still... or crashes.
11 lcs6 : allow L_ not to be square.
12 lcs7 : printDiff()
13 **/
14// T must have copy constructor
15// T must have a default constructor
16// T must have operator[ ] accessesible by int
17// T must have a size or the asize() and bsize() methods should be specialized.
18
19template <class T>
20class LCS : public std::binary_function<T, T, bool>{
21
22public:
23 LCS(); ~LCS();
24 // LCS(const T& a, const T& b);
25 bool operator() (const T& a, const T& b);
26 const std::vector<std::vector<int> >& result ();
27 void dumpDataL();
28 void printDiff();
29
30private:
31 T a_, b_;
32 std::vector<std::vector<int> > L_;
33 int lcsLength();
34 int subProblem(int i, int j);
35 size_t asize() { return a_.size(); };
36 size_t bsize() { return b_.size(); };
37 void printDiff( int i, int j );
38};
39
40template <class T>
41LCS<T>::LCS() : a_(), b_() { };
42
43template <class T>
44LCS<T>::~LCS() { }
45
46// template <class T>
47// LCS<T>::LCS(const T& a, const T& b) : a_(a), b_(b) {
48// }
49
50// template <class T>
51// const std::vector<std::vector<int> >& operator() ( const T& a, const T& b ) {
52
53template <class T>
54bool LCS<T>::operator() ( const T& a, const T& b) {
55 // main work here... and there...
56 a_=a;
57 b_=b;
58 lcsLength();
59};
60
61template <class T>
62const std::vector<std::vector<int> >& LCS<T>::result() {
63 if ( L_.size() == 0 ) std::cout << "UNUSED FUNCTOR THEREFORE EMPTY RESULTS" << std::endl;
64 return L_;
65}
66
67template <class T>
68int LCS<T>::lcsLength() {
69 L_.clear();
70 std::vector<int> tv;
71 for (int i = 0; i <= asize(); i++){
72 tv.clear();
73 for (int j = 0; j <= bsize(); j++)
74 tv.push_back(-1);
75 L_.push_back(tv);
76 }
77 return subProblem(0,0);
78}
79
80template <class T>
81int LCS<T>::subProblem(int i, int j) {
82 if (L_[i][j] < 0) {
83 if ( i == asize() || j == bsize() ) {
84 L_[i][j] = 0;
85 } else if (a_[i] == b_[j]) {
86 L_[i][j] = 1 + subProblem(i+1, j+1);
87 // std::cout << " matched at " << i << " " << j << " value " << a_[i] << std::endl;
88 } else {
89 L_[i][j] = std::max(subProblem(i+1, j), subProblem(i, j+1));
90 }
91 }
92 return L_[i][j];
93}
94
95template <class T>
96void LCS<T>::dumpDataL() {
97 for ( size_t i = 0; i < asize(); ++i ) {
98 for ( size_t j = 0; j < bsize(); ++j ) {
99 std::cout << L_[i][j] << "\t"; //printf ("%i\t", L_[i][j]);
100 }
101 std::cout << std::endl; //printf("\n");
102 }
103}
104
105// template <class T>
106// size_t LCS<T>::asize() {
107// return asize();
108// }
109
110// template <class T>
111// size_t LCS<T>::bsize() {
112// return bsize();
113// }
114
115template <class T>
116void LCS<T>::printDiff() {
117 // printDiff(asize()-1, bsize()-1);
118 printDiff(0,0);
119}
120
121template <class T>
122 void LCS<T>::printDiff( int i, int j ) {
123 if ( i < asize() && j < bsize() && a_[i] == b_[j] ) {
124 std::cout << " " << a_[i] << " " << b_[j] << std::endl;
125 printDiff ( i+1, j+1 );
126 } else {
127 if ( j < bsize() && ( i == asize() || L_[i][j+1] >= L_[i+1][j] ) ) {
128 std::cout << " + " << b_[j] << std::endl;
129 printDiff( i, j+1);
130 } else if ( i < asize() && ( j == bsize() || L_[i][j+1] < L_[i+1][j] ) ) {
131 std::cout << "- " << a_[i] << std::endl;
132 printDiff( i+1, j );
133 } else {
134 std::cout << "" << std::endl;
135 }
136 }
137}