#include "BST.hpp" #include #include #include using namespace std; /** * A simple test driver for the BST class template. * P1 CSE 100 2013 * Author: P. Kube (c) 2013 */ int main() { /* Create an STL vector of some ints */ vector v; v.push_back(3); v.push_back(4); v.push_back(1); v.push_back(100); v.push_back(-33); /* Create an instance of BST holding int */ BST b; /* Insert a few data items. */ vector::iterator vit = v.begin(); vector::iterator ven = v.end(); for(; vit != ven; ++vit) { // all these inserts are unique, so should return a std::pair // with second part true std::pair::iterator,bool> pr = b.insert(*vit); if(! pr.second ) { cout << "Incorrect bool return value when inserting " << *vit << endl; return -1; } if(*(pr.first) != *vit) { cout << "Incorrect iterator return value when inserting " << *vit << endl; return -1; } } /* Test size. */ cout << "Size is: " << b.size() << endl; if(b.size() != v.size()) { cout << "... which is incorrect." << endl; return -1; } /* Test find return value. */ vit = v.begin(); for(; vit != ven; ++vit) { if(*(b.find(*vit)) != *vit) { cout << "Incorrect return value when finding " << *vit << endl; return -1; } } /* Sort the vector, to compare with inorder iteration on the BST */ sort(v.begin(),v.end()); /* Test BST iterator; should iterate inorder */ cout << "traversal using iterator:" << endl; vit = v.begin(); BST::iterator en = b.end(); BST::iterator it = b.begin(); for(; vit != ven; ++vit) { if(! (it != en) ) { cout << *it << "," << *vit << ": Early termination of BST iteration." << endl; return -1; } cout << *it << endl; if(*it != *vit) { cout << *it << "," << *vit << ": Incorrect inorder iteration of BST." << endl; return -1; } ++it; } cout << "OK." << endl; }