Advanced Search

LCS header file

/ Published in: C++
Save to your folder(s)

Expand | Embed | Plain Text

Copy this code and paste it in your HTML 
  1. /*
  2.  * =====================================================================================
  3.  *
  4.  *       Filename:  lcs.hpp
  5.  *
  6.  *    Description:  A class of longest common subsequence (lcs) by dynamic programming
  7.  *
  8.  *        Version:  1.2
  9.  *        Created:  2011å¹´01月03æ—¥ 20時15分32秒
  10.  *       Revision:  none
  11.  *       Compiler:  gcc
  12.  *
  13.  *         Author:  Dirk Chang (), [email protected]
  14.  *        Company:  lc.asiahope.net
  15.  *
  16.  * =====================================================================================
  17.  */
  18. #ifndef LCS_HPP_
  19. #define LCS_HPP_
  20.  
  21. #include <vector>
  22. #include <iostream>
  23. #include <iomanip>
  24. #include <cstring>
  25. #include <iterator>
  26. #include <algorithm>
  27.  
  28. struct Default_LCS_Comparison {
  29. 	template <typename T>
  30. 	static bool equal(T const &x, T const &y) {
  31. 		return x == y; // use operator == as the default comparison funtion
  32. 	}
  33. };
  34.  
  35. template <typename COMP = Default_LCS_Comparison>
  36. class LCS {
  37. private:
  38. 	enum Direction { NIL = 0, LEFT, UPLEFT, UP };
  39. 	typedef size_t IndexType;
  40. 	typedef IndexType* Row;
  41. 	typedef std::vector<Row> Table;
  42. 	typedef std::vector<Direction*> AnsTable;
  43.  
  44. public:
  45. 	LCS(size_t const & reserved = 32) : _length(0), _m(0), _n(0), _reserved(reserved+1) {
  46. 		construct_table();
  47. 	}
  48. 	~LCS() {
  49. 		destory_table();
  50. 	}
  51. 	LCS(LCS const &l) : _length(l._length), _reserved(l._reserved) {
  52. 		construct_table();
  53. 		for(size_t i = 0; i < _reserved; ++i) {
  54. 			std::memcpy(_compute_table[i], l._compute_table[i], sizeof(IndexType)*_reserved);
  55. 			std::memcpy(_answer_table[i], l._answer_table[i], sizeof(Direction)*_reserved);
  56. 		}
  57. 	}
  58. 	LCS const &operator=(LCS const &l) {
  59. 		_length = l._length;
  60. 		_reserved = l._reserved;
  61. 		destory_table();
  62. 		construct_table();
  63. 		for(size_t i = 0; i < _reserved; ++i) {
  64. 			std::memcpy(_compute_table[i], l._compute_table[i], sizeof(IndexType)*_reserved);
  65. 			std::memcpy(_answer_table[i], l._answer_table[i], sizeof(Direction)*_reserved);
  66. 		}
  67. 	}
  68.  
  69. 	template<typename const_iterator>
  70. 	inline IndexType Compute(const_iterator x_begin, const_iterator x_end, size_t const x_size, const_iterator y_begin, const_iterator y_end, size_t const y_size) {
  71. 		_length = 0;
  72. 		_m = x_size;
  73. 		_n = y_size;
  74.  
  75. 		size_t tmp_max = y_size;
  76. 		if(tmp_max < x_size) tmp_max = x_size;
  77. 		if(tmp_max >= _reserved) {
  78. 			_reserved = tmp_max + 1;
  79. 			destory_table();
  80. 			construct_table();
  81. 		}
  82.  
  83. 		const_iterator xi, yj;
  84. 		xi = x_begin;
  85. 		size_t i(1), j(1);
  86. 		for(i = 1; i <= x_size; ++i) {
  87. 			yj = y_begin;
  88. 			for(j = 1; j <= y_size; ++j) {
  89. 				if(COMP::equal(*xi,*yj)) {
  90. 					_compute_table[i][j] = _compute_table[i - 1][j - 1] + 1;
  91. 					_answer_table[i][j] = UPLEFT;
  92. 				}
  93. 				else if(_compute_table[i - 1][j] >= _compute_table[i][j - 1]) {
  94. 					_compute_table[i][j] = _compute_table[i - 1][j];
  95. 					_answer_table[i][j] = UP;
  96. 				}
  97. 				else {
  98. 					_compute_table[i][j] = _compute_table[i][j - 1];
  99. 					_answer_table[i][j] = LEFT;
  100. 				}
  101. 				++yj;
  102. 			}
  103. 			++xi;
  104. 		}
  105. 		_length = _compute_table[x_size][y_size];
  106. 		return _length;
  107. 	}
  108.  
  109. 	inline IndexType Length() {
  110. 		return _length;
  111. 	}
  112.  
  113. 	template<typename SEQ, typename ANS>
  114. 	int Answer(const SEQ &x, ANS &answer) {
  115. 		construct_answer(x, _m, _n, answer);
  116. 		return 0;
  117. 	}
  118.  
  119. 	void PrintComputeTable(std::ostream &out, int const tab = 2);
  120. 	void PrintAnswerTable(std::ostream &out, int const tab = 2);
  121.  
  122. private:
  123. 	template<typename SEQ, typename ANS>
  124. 	void construct_answer(const SEQ &x, int const i, int const j, ANS &answer) {
  125. 		if(i == 0 || j == 0) return;
  126. 		if(_answer_table[i][j] == UPLEFT) {
  127. 			construct_answer(x, i - 1, j - 1, answer);
  128. 			answer.push_back(x[i - 1]);
  129. 		}
  130. 		else if(_answer_table[i][j] == UP) {
  131. 			construct_answer(x, i - 1, j, answer);
  132. 		}
  133. 		else construct_answer(x, i, j - 1, answer);
  134. 	}
  135.  
  136. 	void construct_table() {
  137. 		_compute_table.resize(_reserved, 0);
  138. 		_answer_table.resize(_reserved, 0);
  139. 		for(size_t i = 0; i < _reserved; ++i) {
  140. 			_compute_table[i] = new IndexType [_reserved];
  141. 			_answer_table[i] = new Direction [_reserved];
  142. 			_compute_table[i][0] = 0;
  143. 			_answer_table[i][0] = NIL;
  144. 		}
  145. 		for(size_t i = 0; i < _reserved; ++i) {
  146. 			_compute_table[0][i] = 0;
  147. 			_answer_table[0][i] = NIL;
  148. 		}
  149. 	}
  150. 	void destory_table() {
  151. 		for(size_t i = 0; i < _reserved; ++i) {
  152. 			delete [] _compute_table[i];
  153. 			delete [] _answer_table[i];
  154. 		}
  155. 	}
  156.  
  157. private:
  158. 	Table _compute_table;
  159. 	AnsTable _answer_table;
  160. 	IndexType _length, _m, _n;
  161. 	size_t _reserved;
  162. };
  163.  
  164. template <typename COMP>
  165. void LCS<COMP>::PrintAnswerTable(std::ostream &out, int const tab) {
  166. 	int i, j;
  167. 	out << std::setw(tab) << ' ' << std::setw(tab) << 'j';
  168. 	for(i = 0; i < _n; ++i) {
  169. 		out << std::setw(tab) << i;
  170. 	}
  171. 	out << '\n';
  172.  
  173. 	out << std::setw(tab) << 'i' << std::setw(tab) << ' ' << std::setw(tab) << 'y' << '\n';
  174. 	out << std::setw(tab) << '0' << std::setw(tab) << 'x';
  175. 	for(i = 0; i< _n; ++i) {
  176. 		out << std::setw(tab) << '0';
  177. 	}
  178. 	out << '\n';
  179.  
  180. 	for(i = 1; i < _m; ++i) {
  181. 		out << std::setw(tab) << i << std::setw(tab) << ' ';
  182. 		for(j = 0; j < _n; ++j) {
  183. 			out << std::setw(tab) << _answer_table[i][j];
  184. 		}
  185. 		out << '\n';
  186. 	}
  187. 	out << '\n';
  188. }
  189.  
  190.  
  191. template <typename COMP>
  192. void LCS<COMP>::PrintComputeTable(std::ostream &out, int const tab) {
  193. 	int i, j;
  194. 	out << std::setw(tab) << ' ' << std::setw(tab) << 'j';
  195. 	for(i = 0; i < _n; ++i) {
  196. 		out << std::setw(tab) << i;
  197. 	}
  198. 	out << '\n';
  199.  
  200. 	out << std::setw(tab) << 'i' << std::setw(tab) << ' ' << std::setw(tab) << 'y' << '\n';
  201. 	out << std::setw(tab) << '0' << std::setw(tab) << 'x';
  202. 	for(i = 0; i< _n; ++i) {
  203. 		out << std::setw(tab) << '0';
  204. 	}
  205. 	out << '\n';
  206.  
  207. 	for(i = 1; i < _m; ++i) {
  208. 		out << std::setw(tab) << i << std::setw(tab) << ' ';
  209. 		for(j = 0; j < _n; ++j) {
  210. 			out << std::setw(tab) << _compute_table[i][j];
  211. 		}
  212. 		out << '\n';
  213. 	}
  214. 	out << '\n';
  215. }
  216.  
  217. template <typename COMP = Default_LCS_Comparison>
  218. class LCS_NOANS {
  219. private:
  220. 	typedef size_t IndexType;
  221. 	typedef IndexType* Row;
  222. 	typedef std::vector<Row> Table;
  223.  
  224. public:
  225. 	LCS_NOANS(size_t const & reserved = 32) : _length(-1), _reserved(reserved+1) {
  226. 		_compute_table.resize(2, 0);
  227. 		_compute_table[0] = new IndexType [_reserved];
  228. 		_compute_table[1] = new IndexType [_reserved];
  229. 	}
  230. 	~LCS_NOANS() {
  231. 		delete [] _compute_table[0];
  232. 		delete [] _compute_table[1];
  233. 	}
  234. 	LCS_NOANS(LCS_NOANS const &l) : _length(l._length), _reserved(l._reserved) {
  235. 		_compute_table[0] = new IndexType [_reserved];
  236. 		_compute_table[1] = new IndexType [_reserved];
  237. 		std::memcpy(_compute_table[0], l._compute_table[0], sizeof(IndexType)*_reserved);
  238. 		std::memcpy(_compute_table[1], l._compute_table[1], sizeof(IndexType)*_reserved);
  239. 	}
  240. 	LCS_NOANS const &operator=(LCS_NOANS const &l) {
  241. 		_length = l._length;
  242. 		_reserved = l._reserved;
  243. 		delete [] _compute_table[0];
  244. 		delete [] _compute_table[1];
  245. 		_compute_table[0] = new IndexType [_reserved];
  246. 		_compute_table[1] = new IndexType [_reserved];
  247. 		std::memcpy(_compute_table[0], l._compute_table[0], sizeof(IndexType)*_reserved);
  248. 		std::memcpy(_compute_table[1], l._compute_table[1], sizeof(IndexType)*_reserved);
  249. 	}
  250.  
  251. 	template<typename const_iterator>
  252. 	inline IndexType Compute(const_iterator x_begin, const_iterator x_end, size_t const x_size, const_iterator y_begin, const_iterator y_end, size_t const y_size) {
  253. 		_length = 0;
  254.  
  255. 		size_t tmp_max = y_size;
  256. 		if(tmp_max < x_size) tmp_max = x_size;
  257. 		if(tmp_max >= _reserved) {
  258. 			_reserved = tmp_max + 1;
  259. 			delete [] _compute_table[0];
  260. 			delete [] _compute_table[1];
  261. 			_compute_table[0] = new IndexType [_reserved];
  262. 			_compute_table[1] = new IndexType [_reserved];
  263. 		}
  264. 		std::memset(_compute_table[0], 0, sizeof(IndexType)*_reserved);
  265. 		_compute_table[1][0] = 0;
  266.  
  267. 		const_iterator xi, yj;
  268. 		xi = x_begin;
  269. 		size_t i(1), j(1);
  270. 		for(i = 1; i <= x_size; ++i) {
  271. 			yj = y_begin;
  272. 			_compute_table[i%2][0] = 0;
  273. 			for(j = 1; j <= y_size; ++j) {
  274. 				if(i%2) {
  275. 					if(COMP::equal(*xi,*yj)) {
  276. 						//std::cout << "(" << *xi << "," << *yj << ")";
  277. 						_compute_table[1][j] = _compute_table[0][j - 1] + 1;
  278. 					}
  279. 					else if(_compute_table[0][j] >= _compute_table[1][j - 1]) {
  280. 						_compute_table[1][j] = _compute_table[0][j];
  281. 					}
  282. 					else {
  283. 						_compute_table[1][j] = _compute_table[1][j - 1];
  284. 					}
  285. 				}
  286. 				else {
  287. 					if(COMP::equal(*xi,*yj)) {
  288. 						_compute_table[0][j] = _compute_table[1][j - 1] + 1;
  289. 					}
  290. 					else if(_compute_table[1][j] >= _compute_table[0][j - 1]) {
  291. 						_compute_table[0][j] = _compute_table[1][j];
  292. 					}
  293. 					else {
  294. 						_compute_table[0][j] = _compute_table[0][j - 1];
  295. 					}
  296. 				}
  297. 				++yj;
  298. 			}
  299. 			++xi;
  300. 		}
  301. 		_length = _compute_table[x_size%2][y_size];
  302. 		return _length;
  303. 	}
  304. 	inline IndexType Length() {
  305. 		return _length;
  306. 	}
  307.  
  308. private:
  309. 	Table _compute_table;//, _answer_table;
  310. 	IndexType _length;
  311. 	size_t _reserved;
  312. };
  313.  
  314. #endif /* LCS_HPP_ */

Report this snippet


Comments

RSS Icon Subscribe to comments

You need to login to post a comment.