API tools faq
paste
Guest User

Untitled

a guest
Feb 21st, 2018
65
0
Never
Add comment
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
text 13.29 KB | None | 0 0
raw download clone embed print report
  1.  
  2. #ifndef __PROGTEST__
  3. #define __PROGTEST__
  4.  
  5. #include <cstdlib>
  6. #include <cstring>
  7. #include <ctype.h>
  8. #include <map>
  9. #include <vector>
  10. #include <limits.h>
  11.  
  12. using namespace std;
  13.  
  14. class CValue
  15. {
  16. public:
  17. CValue(){v = -1;}
  18. CValue(const CValue &i){v = i.v;}
  19. CValue(int i){v = i;}
  20. ~CValue(){}
  21. CValue& operator = ( const CValue &i ){v = i.v; return *this;}
  22. bool operator == ( const CValue &i ) const {return v == i.v;}
  23. bool operator != ( const CValue &i ) const{return v != i.v;}
  24. bool operator < ( const CValue &i ) const{return v < i.v;}
  25. bool operator > ( const CValue &i ) const{return v > i.v;}
  26. bool operator >= ( const CValue &i ) const{return v >= i.v;}
  27. bool operator <= ( const CValue &i ) const{return v <= i.v;}
  28. int v;
  29. };
  30.  
  31. class CKey
  32. {
  33. public:
  34. CKey() {k = -1;}
  35. CKey(const CKey &i){k = i.k;}
  36. CKey(int i){k = i;}
  37. ~CKey(){}
  38. CKey& operator = ( const CKey &i ){k = i.k; return *this;}
  39. bool operator == ( const CKey &i ) const{return k == i.k;}
  40. bool operator != ( const CKey &i ) const{return k != i.k;}
  41. bool operator < ( const CKey &i ) const{return k < i.k;}
  42. bool operator > ( const CKey &i ) const{return k > i.k;}
  43. bool operator >= ( const CKey &i ) const{return k >= i.k;}
  44. bool operator <= ( const CKey &i ) const{return k <= i.k;}
  45. int k;
  46. };
  47.  
  48. struct Exc{char name[50];};
  49. struct InvalidIndexException : Exc
  50. {InvalidIndexException()
  51. {strcpy(name,"InvalidIndexException");} };
  52. struct InvalidTreeException : Exc{
  53. InvalidTreeException()
  54. {strcpy(name,"InvalidTreeException");} };
  55.  
  56. //>INCLUDE YOUR B-TREE FILE HERE<
  57. #include "main.cpp"
  58. //>INCLUDE YOUR B-TREE FILE HERE<
  59.  
  60. //these probably compile error (cout for sure, dont use them anyway)
  61. #include <iostream>
  62. #include <string>
  63. #include <sstream>
  64.  
  65.  
  66. //global access-----------------------------------------------------------------
  67. bool g_Verbose;
  68. map<int, int> g_Ref;
  69. vector<CKey> g_Used;
  70. ostream& out = cout;
  71. CNode * g_My;
  72. map<int,int>::iterator
  73. g_Correct;
  74. int g_Level;
  75. int g_LeafLvl;
  76. int g_Count;
  77. int g_Last;
  78. //------------------------------------------------------------------------------
  79.  
  80. void printNode(CNode* n, string path){
  81. out << path << ": ";
  82. int gamma = n->getGamma();
  83. if ( gamma == 0 ) {out << "EMPTY" << endl; return;}
  84.  
  85. for(int i = 1; i <= gamma; i++)try{
  86. out << '|'
  87. << n->getKey(i).k ; //key only
  88. // << n->getKey(i).k << '-' n->getValue(i).v; //key-value
  89. }catch(Exc& e){
  90. out << '|' <<e.name;
  91. }
  92.  
  93. out << "|" << "g(" << gamma <<")" << (n->isLeaf() ? ",L":"") << endl;
  94.  
  95. if (!n->isLeaf())
  96. for (int i = 1; i <= gamma + 1; i++)
  97. {
  98. stringstream str; str.str("");
  99. str << path << "," << i;
  100. try{
  101. printNode(n->getChild(i), str.str());
  102. }catch(Exc& e){
  103. out << str.str() << ": " << e.name << endl;
  104. }
  105. }
  106. }
  107.  
  108. void print(CBTree& t){
  109. try{
  110. CNode * r = t.getRoot();
  111. out << "Tree:" << endl;
  112. printNode(r, "R");
  113. }catch(Exc& e){
  114. out << "Can't print tree: root's missing" << endl;
  115. }
  116. }
  117.  
  118. void generateKVPair( CKey& key, CValue& value, int keyCeiling = RAND_MAX )
  119. {
  120. // key e N+
  121. key = rand( ) % keyCeiling +1;
  122. value = rand( );
  123. }
  124.  
  125. bool checkSearch(CBTree& subject, CKey& key)
  126. {
  127. if (g_Verbose) out << "search()" << endl;
  128. int myIdx;
  129. bool myRet;
  130. try{
  131. myRet = (myIdx = subject.bTreeSearch(key, &g_My)) != -1;
  132. }catch(Exc& e){
  133. out << e.name <<" caught called after calling: search() for key: " << key.k << endl;
  134. return false;
  135. }
  136.  
  137. bool correct = (g_Correct = g_Ref.find(key.k)) != g_Ref.end();
  138.  
  139. if ( myRet != correct ){
  140. out << "Bad result for: search() (isPresent?)" << "key: " << key.k << " response value: " << myRet << ", correct value: " << correct << endl;
  141. return false;
  142. }
  143. if( !myRet )
  144. return true;
  145.  
  146. int k, v;
  147. try{
  148. k = g_My->getKey(myIdx).k;
  149. v = g_My->getValue(myIdx).v;
  150. }catch(Exc& e){
  151. out << "Bad result for: search() (couldn't extract key/value - invalid index)" << "key: " << key.k << " idx: " << myIdx << endl;
  152. return false;
  153. }
  154.  
  155. if (k != key.k){
  156. out << "Bad result for: search() (keys don't match)" << "key: " << key.k << " search returned: " << k << endl;
  157. return false;
  158. }
  159.  
  160. if (v != g_Correct->second){
  161. out << "Bad result for: search() (values don't match)" << "key: " << key.k << " value retured: " << v << ", correct value: " << g_Correct->second << endl;
  162. return false;
  163. }
  164. return true;
  165. }
  166.  
  167. bool checkRemove(CBTree& subject, CKey& key)
  168. {
  169. CNode * dummy;
  170.  
  171. bool correct = g_Ref.erase(key.k) > 0;
  172. if (g_Verbose) out << "remove() (" << (correct ? "present" : "missing") << " key)" << endl;
  173. bool my;
  174. try{
  175. my = subject.bTreeDelete(key);
  176. }catch(Exc& e){
  177. out << e.name <<" caught called after calling: remove() for key: " << key.k << (correct ? " (existing" : " (new") << " key)" << endl;
  178. return false;
  179. }
  180. if(correct != my){
  181. out << "Bad result for: remove()" << "key: " << key.k << " response(wasDeleted?): " << my << ", correct: " << correct << endl;
  182. return false;
  183. }
  184. return true;
  185. }
  186.  
  187. bool checkInsert(CBTree& subject, CKey& key, CValue& val){
  188. bool pres_correct = (g_Correct = g_Ref.find(key.k)) != g_Ref.end();
  189. bool pres_my;
  190. if( g_Verbose ){
  191. out << "insert() (" << (pres_correct ? "existing" : "new") << " key)" << endl;
  192. }
  193.  
  194. try{
  195. pres_my = !subject.bTreeInsert(key, val);
  196. }catch(Exc& e){
  197. out << e.name <<" caught called after calling: insert() for key: " << key.k << (pres_correct ? " (existing" : " (new") << " key)" << endl;
  198. return false;
  199. }
  200. g_Ref.operator [](key.k) = val.v;
  201. if (pres_correct != pres_my){
  202. out << "Bad result for: insert()" << "key: " << key.k << (pres_correct ? " (existing)" : " (new)") << " val: " << val.v
  203. << " response: " << pres_my << ", correct value: " << pres_correct << endl;
  204. return false;
  205. }
  206. return true;
  207. }
  208.  
  209. bool InsertCoherencyTest(CBTree& subject, int cycles, int valRange, string comment)
  210. {
  211. out << "Insert coherency test (" << comment << "):" << endl;
  212. CKey k; CValue v;
  213. for (int i = 0; i < cycles ; i++)
  214. {
  215. generateKVPair(k,v, valRange);
  216. g_Used.push_back(k);
  217. if (g_Verbose) out << "key: " << k.k << " value: " << v.v << " actions: " << endl;
  218. if (!checkInsert(subject, k, v) ||
  219. !checkSearch(subject, k) ) {
  220. out << "FAILED" << endl;
  221. return false;}
  222. }
  223. return true;
  224. }
  225.  
  226. bool RemoveCoherencyTest(CBTree& subject, int stepSize, string comment)
  227. {
  228. out << "Remove coherency test (" << comment << "):" << endl;
  229. for (vector<CKey>::iterator it = g_Used.begin(); it < g_Used.end() ; it+=stepSize)
  230. {
  231. // out << "---------------------------------------------------------" << endl;
  232. CKey k= it->k;
  233. if (g_Verbose) out << "key: " << k.k << " actions: " << endl;
  234. if (!checkRemove(subject, k) ||
  235. !checkSearch(subject, k) ) {
  236. out << "FAILED" << endl;
  237. return false;}
  238. }
  239. return true;
  240. }
  241.  
  242. bool CoherencyTestR2S(CBTree& subject)
  243. {
  244. CKey k;
  245. for(g_Correct = g_Ref.begin(); g_Correct != g_Ref.end(); g_Correct++)
  246. {
  247. k = g_Correct->first;
  248. if (g_Verbose) out << "key: " << k.k << " actions: " << endl;
  249. if (!checkSearch(subject, k)) {
  250. out << "FAILED" << endl;
  251. return false;}
  252. }
  253. return true;
  254. }
  255.  
  256. //inOrder traverse
  257. bool CHTS2RSub(CNode * node, string rep){
  258. stringstream s;
  259. if (!node->isLeaf())
  260. try{
  261. s << rep << ",1";
  262. if ( !CHTS2RSub(node->getChild(1), s.str()) ) return false;
  263. } catch(Exc& e){
  264. out << e.name <<" caught called after calling: getChild(1) on node " << s.str() << endl;
  265. return false;
  266. }
  267. for( int g = 1; g <= node->getGamma(); g++)
  268. {
  269. CKey k; CValue v;
  270. try{
  271. k = node->getKey(g);
  272. v = node->getValue(g);
  273. if ( k.k <= g_Last ){
  274. out << "Bad invariant: keys aren't in ascending order for key: " << k.k << " previous value " << g_Last << endl;
  275. return false;
  276. }
  277. g_Last = k.k;
  278. if ( (g_Correct = g_Ref.find(k.k)) == g_Ref.end() ){
  279. out << "Key: " << k.k << " shouldn't be in the tree" << endl;
  280. return false;
  281. }
  282. if (v.v != g_Correct->second)
  283. {
  284. out << "Values don't match for Key: " << k.k << " response:" << v.v <<", correct: " << g_Correct->second << endl;
  285. return false;
  286. }
  287. ++g_Count;
  288. }catch(Exc& e){
  289. out << e.name <<" caught called after calling: getKey/Val("<< g << ") on node " << rep << endl;
  290. return false;
  291. }
  292. if (!node->isLeaf())
  293. try{
  294. s.str(rep); s << "," << g + 1;
  295. if ( !CHTS2RSub(node->getChild(g + 1), s.str()) ) return false;
  296. }catch(Exc& e){
  297. out << e.name <<" caught called after calling: getChild(" << g+ 1 << ") on node " << s.str() << endl;
  298. return false;
  299. }
  300. }
  301. return true;
  302. }
  303. bool CoherencyTestS2R(CBTree& subject){
  304. g_Count = 0;
  305. g_Level = g_LeafLvl = -1;
  306. g_Last = INT_MIN;
  307. try{
  308. if (subject.getRoot() != NULL)
  309. if ( !CHTS2RSub(subject.getRoot(), "R") ) return false;
  310. }catch(Exc& e){
  311. out << e.name <<" caught called after calling: getRoot()" << endl;
  312. out << "FAILED" << endl;
  313. return false;
  314. }
  315. if ( g_Count != g_Ref.size() ){
  316. out << "Invalid number of elements in tree: " << g_Count << " correct: " << g_Ref.size() << endl;
  317. out << "FAILED" << endl;
  318. return false;
  319. }
  320. return true;
  321. }
  322.  
  323. bool TestSuite(CBTree& subject, int multiplier){
  324.  
  325. g_Ref.clear(); g_Used.clear();
  326. subject.bTreeCreate();
  327. if ( ! InsertCoherencyTest(subject, 20 * multiplier, 40 * multiplier, "KEYS : Wide Range") ||
  328. ! CoherencyTestR2S(subject) ||
  329. ! CoherencyTestS2R(subject)) return false;
  330. print(subject);
  331. //------------------------------------------------------------------------------------
  332. g_Ref.clear(); g_Used.clear();
  333. subject.bTreeCreate();
  334. if ( ! InsertCoherencyTest(subject, 20 * multiplier, 10 * multiplier, "KEYS : Narrow Range") ||
  335. ! CoherencyTestR2S(subject)||
  336. ! CoherencyTestS2R(subject)) return false;
  337. //-----------------------------------------------------------------------------------
  338. g_Ref.clear(); g_Used.clear();
  339. subject.bTreeCreate();
  340. if ( ! InsertCoherencyTest(subject, 20 * multiplier, 20 * multiplier, "General") ||
  341. ! CoherencyTestR2S(subject)||
  342. ! CoherencyTestS2R(subject)) return false;
  343. //------------------------------------------------------------------------------
  344. if ( ! RemoveCoherencyTest(subject, 8, "Present Keys") ||
  345. ! CoherencyTestR2S(subject)||
  346. ! CoherencyTestS2R(subject)) return false;
  347. //------------------------------------------------------------------------------
  348. if ( ! RemoveCoherencyTest(subject, 8, "Missing Keys") ||
  349. ! CoherencyTestR2S(subject)||
  350. ! CoherencyTestS2R(subject)) return false;
  351. //------------------------------------------------------------------------------
  352. if ( ! RemoveCoherencyTest(subject, 6, "Present&Missing Keys") ||
  353. ! CoherencyTestR2S(subject)||
  354. ! CoherencyTestS2R(subject)) return false;
  355. if ( ! InsertCoherencyTest(subject, 10 * multiplier, 10 * multiplier, "Inserting more values") ) return false;
  356. if ( ! RemoveCoherencyTest(subject, 1, "Present&Missing Keys, More Keys") ||
  357. ! CoherencyTestR2S(subject)||
  358. ! CoherencyTestS2R(subject)) return false;
  359. g_Used.clear();
  360. if ( ! RemoveCoherencyTest(subject, 1, "Present&Missing Keys, More Keys") ||
  361. ! CoherencyTestR2S(subject)||
  362. ! CoherencyTestS2R(subject)) return false;
  363. if ( ! InsertCoherencyTest(subject, 30 * multiplier, 30 * multiplier, "Inserting more values") ) return false;
  364. if ( ! RemoveCoherencyTest(subject, 3, "Final") ||
  365. ! CoherencyTestR2S(subject)||
  366. ! CoherencyTestS2R(subject)) return false;
  367. //------------------------------------------------------------------------------
  368. subject.bTreeCreate();g_Ref.clear();
  369. out << "Root Delete Test:" << endl;
  370. CValue v(5); CKey k(1);
  371. if ( !checkInsert(subject, k, v) || !checkRemove(subject,k) ) return false;
  372. out << "DONE" << endl;
  373. return true;
  374. }
  375.  
  376.  
  377. int main( int argc, char** argv )
  378. {
  379. srand( time( 0 ) );
  380.  
  381. //suppress additional info
  382. g_Verbose // = true;
  383. = false;
  384.  
  385. //print(tree) - prints tree structure to out
  386.  
  387. out << ">------------------<" << endl;
  388. out << "SIMPLE TEST ODD (5):" << endl;
  389. out << ">------------------<" << endl;
  390. CBTree o(5);
  391. if (!TestSuite(o, 5) ) { print(o); return 1;};
  392.  
  393. out << ">------------------<" << endl;
  394. out << "SIMPLE TEST EVEN (4):" << endl;
  395. out << ">------------------<" << endl;
  396. CBTree e(4);
  397. if (!TestSuite(e, 5) ) { print(e); return 1;};
  398.  
  399. out << ">--------------------<" << endl;
  400. out << "COMPLEX TEST EVEN/ODD:" << endl;
  401. out << ">--------------------<" << endl;
  402. for(int size = 3; size < 13; size+= 1){
  403. CBTree r(size);
  404. for(int i = 0; i < 3; i++) {
  405. out << "M: " << size << " Test Complexity: " << 20+i*15 << endl;
  406. if ( !TestSuite(r,20+i*15)) {print(r);return 1;}
  407. }
  408. }
  409. return 0;
  410. }
  411.  
  412. #endif
Add Comment
Please, Sign In to add comment
Public Pastes
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy.  OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!