//----------------------------------------------------------- // TOOLS // C++ Templates & Tools, 2nd Edition //----------------------------------------------------------- // // TestTree.cpp // // Procedures for testing binary tree classes. // //----------------------------------------------------------- // Copyright 1996 by Scott Robert Ladd. All rights reserved. //----------------------------------------------------------- #include "strstrea.h" #include "iomanip.h" #include "limits.h" #include "ToolsThread.h" #include "RandDev.h" #include "BinaryTree.h" #include "RedBlackTree.h" using namespace Coyote; //------------------ // Test binary trees //------------------ void TestTrees ( void * args ) { // retrieve parameters for simpler syntax ToolsThreadData * ttd = (ToolsThreadData *)args; HINSTANCE inst = ttd->inst; HWND wdw = ttd->mainWdw; ostrstream & buffer = *(ttd->ostrm); // change main window heading SetWindowText(wdw,"Binary tree tests"); // display a headline buffer << "Binary Tree Test\r\n" "----------------\r\n"; const size_t TEST_SIZE = 101; unsigned int values[TEST_SIZE]; size_t n; RandDev gen1; BinaryTree tree2; for (n = 0; n < TEST_SIZE; ++n) { values[n] = gen1(UINT_MAX); buffer << "values[" << setw(3) << n << "] = " << setw(5) << values[n] << "\r\n"; tree2.Insert(values[n]); } tree2.Delete(values[17]); tree2.Delete(values[0]); tree2.Delete(values[23]); tree2.Delete(values[TEST_SIZE - 1]); buffer << "\r\n"; BinaryTreeIterator iter2(tree2); try { n = 0; while (1) { ++n; buffer << setw(3) << n << " : " << setw(5) << *iter2 << "\r\n"; ++iter2; } } catch (TreeEx & ex) { if (ex.WhatsWrong() == BTX_NOTFOUND) buffer << "End of list!\r\n"; else throw; } buffer << "\r\n"; iter2.Largest(); try { n = 0; while (1) { ++n; buffer << setw(3) << n << " : " << setw(5) << *iter2 << "\r\n"; --iter2; } } catch (TreeEx & ex) { if (ex.WhatsWrong() == BTX_NOTFOUND) buffer << "End of list!\r\n"; else throw; } // change main window heading SetWindowText(wdw,"Red-black tree tests"); buffer << "RedBlack Tree Test\r\n" "------------------\r\n"; unsigned int min = UINT_MAX, max = 0; RedBlackTree rbtree; for (n = 0; n < TEST_SIZE; ++n) { values[n] = gen1(UINT_MAX); buffer << "values[" << setw(3) << n << "] = " << setw(5) << values[n] << "\r\n"; rbtree.Insert(values[n]); if (values[n] < min) min = values[n]; if (values[n] > max) max = values[n]; } rbtree.Delete(values[17]); rbtree.Delete(values[0]); rbtree.Delete(values[23]); rbtree.Delete(values[TEST_SIZE - 1]); rbtree.Delete(min); rbtree.Delete(max); buffer << "\r\n"; RBTreeIterator rbiter(rbtree); try { n = 0; while (1) { ++n; buffer << setw(3) << n << " : " << setw(5) << *rbiter << "\r\n"; ++rbiter; } } catch (TreeEx & ex) { if (ex.WhatsWrong() == BTX_NOTFOUND) buffer << "End of list!\r\n"; else throw; } buffer << "\r\n"; rbiter.Largest(); try { n = 0; while (1) { ++n; buffer << setw(3) << n << " : " << setw(5) << *rbiter << "\r\n"; --rbiter; } } catch (TreeEx & ex) { if (ex.WhatsWrong() == BTX_NOTFOUND) buffer << "End of list!\r\n"; else throw; } // Done TerminateTest(wdw); }