diff options
Diffstat (limited to 'tests/RB_Tree_Test.cpp')
-rw-r--r-- | tests/RB_Tree_Test.cpp | 237 |
1 files changed, 0 insertions, 237 deletions
diff --git a/tests/RB_Tree_Test.cpp b/tests/RB_Tree_Test.cpp deleted file mode 100644 index 32245ca19d7..00000000000 --- a/tests/RB_Tree_Test.cpp +++ /dev/null @@ -1,237 +0,0 @@ -// $Id$ - -// ============================================================================ -// -// = LIBRARY -// tests -// -// = FILENAME -// RB_Tree_Test.cpp -// -// = DESCRIPTION -// This is a test to verify and illustrate the use of the ACE_RB_Tree -// and ACE_RB_Tree_Iterator classes. Two different key and item types are -// used in order to demonstrate specialization of the ACE_Less_Than -// comparison function object template: int (for which the native < -// operator is sufficient), and char * (for which < operator semantics must -// be replaced by strcmp semantics). An RB tree for each of the four -// possible type parameter permutations over int and char * is constructed -// and filled in, and the resulting order is checked via an iterator over -// each. -// -// = AUTHOR -// Chris Gill <cdgill@cs.wustl.edu> -// -// ============================================================================ - -#include "test_config.h" /* Include first to enable ACE_ASSERT. */ -#include "ace/RB_Tree.h" - -ACE_RCSID(tests, RB_Tree_Test, "$Id$") - -#if defined(__BORLANDC__) && __BORLANDC__ >= 0x0530 -USELIB("..\ace\aced.lib"); -//--------------------------------------------------------------------------- -#endif /* defined(__BORLANDC__) && __BORLANDC__ >= 0x0530 */ - - - -// These arrays of numbers as ints and character strings -// are used to instantiate key and item nodes in the tree. -static char *number_strings [] = {"10", "20", "30", "40", - "50", "60", "70", "80"}; - -static int number_integers [] = {10, 20, 30, 40, - 50, 60, 70, 80}; - -// These arrays of ints are used to shuffle the order of insertion -// of keys and items for the various trees. -static int int_int_index [] = {0, 1, 2, 3, 4, 5, 6, 7}; // LR inorder -static int int_str_index [] = {7, 6, 5, 4, 3, 2, 1, 0}; // RL inorder -static int str_int_index [] = {4, 6, 2, 7, 5, 3, 1, 0}; // RL BFS -static int str_str_index [] = {4, 2, 1, 0, 3, 6, 5, 7}; // LR preorder - -// Number of entries placed in each tree. -static int RB_TREE_TEST_ENTRIES = 8; - -int -main (int, ASYS_TCHAR *[]) -{ - ACE_START_TEST (ASYS_TEXT ("RB_Tree_Test")); - - // Local variables used to index arrays. - int i, k; - - // Construct four RB_Trees. Specialization of the ACE_Less_Than template - // for character strings performs strcmp style string comparisons rather - // than < operator comparison of the pointers themselves. - ACE_RB_Tree<int, int, ACE_Less_Than<int>, ACE_Null_Mutex> int_int_tree; - ACE_RB_Tree<int, char *, ACE_Less_Than<int>, ACE_Null_Mutex> int_str_tree; - ACE_RB_Tree<char *, int, ACE_Less_Than<char *>, ACE_Null_Mutex> str_int_tree; - ACE_RB_Tree<char *, char *, ACE_Less_Than<char *>, ACE_Null_Mutex> str_str_tree; - - // Fill in each tree with the key and item from the appropriate arrays, - // using the shuffle indexes to create different insertion orders. - for (i = 0; i < RB_TREE_TEST_ENTRIES; ++i) - { - k = int_int_index [i]; - ACE_ASSERT ((k >= 0) && (k < RB_TREE_TEST_ENTRIES)); - int_int_tree.insert (number_integers [k], number_integers [k]); - ACE_ASSERT ((int_int_tree.find (number_integers [k]) != 0) && - (*int_int_tree.find (number_integers [k]) == - number_integers [k])); - - k = int_str_index [i]; - ACE_ASSERT ((k >= 0) && (k < RB_TREE_TEST_ENTRIES)); - int_str_tree.insert (number_integers [k], number_strings [k]); - ACE_ASSERT ((int_str_tree.find (number_integers [k]) != 0) && - (*int_str_tree.find (number_integers [k]) == - number_strings [k])); - - k = str_int_index [i]; - ACE_ASSERT ((k >= 0) && (k < RB_TREE_TEST_ENTRIES)); - str_int_tree.insert (number_strings [k], number_integers [k]); - ACE_ASSERT ((str_int_tree.find (number_strings [k]) != 0) && - (*str_int_tree.find (number_strings [k]) == - number_integers [k])); - - k = str_str_index [i]; - ACE_ASSERT ((k >= 0) && (k < RB_TREE_TEST_ENTRIES)); - str_str_tree.insert (number_strings [k], number_strings [k]); - ACE_ASSERT ((str_str_tree.find (number_strings [k]) != 0) && - (*str_str_tree.find (number_strings [k]) == - number_strings [k])); - } - - // Construct an iterator for each of the trees. - ACE_RB_Tree_Iterator<int, int, ACE_Less_Than<int>, ACE_Null_Mutex> int_int_iter (int_int_tree); - ACE_RB_Tree_Iterator<int, char *, ACE_Less_Than<int>, ACE_Null_Mutex> int_str_iter (int_str_tree); - ACE_RB_Tree_Iterator<char *, int, ACE_Less_Than<char *>, ACE_Null_Mutex> str_int_iter (str_int_tree); - ACE_RB_Tree_Iterator<char *, char *, ACE_Less_Than<char *>, ACE_Null_Mutex> str_str_iter (str_str_tree); - - // Iterate over each of the trees, making sure their entries - // are in the same relative order (i.e., the integers and strings - // represent the same values at each respective position in the tree). - for (i = 0; i < RB_TREE_TEST_ENTRIES; ++i) - { - char **str_item; - int *int_item; - - int_item = int_int_iter.item (); - ACE_ASSERT (int_item != 0); - ACE_ASSERT (*int_item == number_integers [i]); - - int_item = str_int_iter.item (); - ACE_ASSERT (int_item != 0); - ACE_ASSERT (*int_item == number_integers [i]); - - str_item = int_str_iter.item (); - ACE_ASSERT (str_item != 0); - ACE_ASSERT (*str_item == number_strings [i]); - - str_item = str_str_iter.item (); - ACE_ASSERT (str_item != 0); - ACE_ASSERT (*str_item == number_strings [i]); - - // Advance each iterator. - int_int_iter.next (); - int_str_iter.next (); - str_int_iter.next (); - str_str_iter.next (); - } - - // Make sure each item in each tree has been visited - ACE_ASSERT (int_int_iter.is_done () == 1); - ACE_ASSERT (int_str_iter.is_done () == 1); - ACE_ASSERT (str_int_iter.is_done () == 1); - ACE_ASSERT (str_str_iter.is_done () == 1); - - // Remove the even numbered entries from each of the trees. - for (i = 0; i < RB_TREE_TEST_ENTRIES; i += 2) - { - ACE_ASSERT (int_int_tree.remove (number_integers [i]) == 1); - ACE_ASSERT (int_str_tree.remove (number_integers [i]) == 1); - ACE_ASSERT (str_int_tree.remove (number_strings [i]) == 1); - ACE_ASSERT (str_str_tree.remove (number_strings [i]) == 1); - } - - // Reset iterators - int_int_iter.first (); - int_str_iter.first (); - str_int_iter.first (); - str_str_iter.first (); - - // Iterate over each of the trees, making sure their entries are - // still in the same relative order (i.e., the integers and strings - // represent the same values at each respective position in the tree). - for (i = 1; i < RB_TREE_TEST_ENTRIES; i += 2) - { - char **str_item; - int *int_item; - - int_item = int_int_iter.item (); - ACE_ASSERT (int_item != 0); - ACE_ASSERT (*int_item == number_integers [i]); - - int_item = str_int_iter.item (); - ACE_ASSERT (int_item != 0); - ACE_ASSERT (*int_item == number_integers [i]); - - str_item = int_str_iter.item (); - ACE_ASSERT (str_item != 0); - ACE_ASSERT (*str_item == number_strings [i]); - - str_item = str_str_iter.item (); - ACE_ASSERT (str_item != 0); - ACE_ASSERT (*str_item == number_strings [i]); - - // Advance each iterator. - int_int_iter.next (); - int_str_iter.next (); - str_int_iter.next (); - str_str_iter.next (); - } - - // Make sure each item in each tree has been visited a second time. - ACE_ASSERT (int_int_iter.is_done () == 1); - ACE_ASSERT (int_str_iter.is_done () == 1); - ACE_ASSERT (str_int_iter.is_done () == 1); - ACE_ASSERT (str_str_iter.is_done () == 1); - - ACE_END_TEST; - return 0; -} - -#if defined (ACE_HAS_EXPLICIT_TEMPLATE_INSTANTIATION) -template class ACE_RB_Tree<int, int, ACE_Less_Than<int>, ACE_Null_Mutex>; -template class ACE_RB_Tree_Node<int, int>; -template class ACE_RB_Tree_Iterator<int, int, ACE_Less_Than<int>, ACE_Null_Mutex>; -template class ACE_RB_Tree<int, char *, ACE_Less_Than<int>, ACE_Null_Mutex>; -template class ACE_RB_Tree_Node<int, char *>; -template class ACE_RB_Tree_Iterator<int, char *, ACE_Less_Than<int>, ACE_Null_Mutex>; -template class ACE_RB_Tree<char *, int, ACE_Less_Than<char *>, ACE_Null_Mutex>; -template class ACE_RB_Tree_Node<char *, int>; -template class ACE_RB_Tree_Iterator<char *, int, ACE_Less_Than<char *>, ACE_Null_Mutex>; -template class ACE_RB_Tree<char *, char *, ACE_Less_Than<char *>, ACE_Null_Mutex>; -template class ACE_RB_Tree_Node<char *, char *>; -template class ACE_RB_Tree_Iterator<char *, char *, ACE_Less_Than<char *>, ACE_Null_Mutex>; -template class ACE_Less_Than<int>; - -#elif defined (ACE_HAS_TEMPLATE_INSTANTIATION_PRAGMA) - -#pragma instantiate ACE_RB_Tree<int, int, ACE_Less_Than<int>, ACE_Null_Mutex> -#pragma instantiate ACE_RB_Tree_Node<int, int> -#pragma instantiate ACE_RB_Tree_Iterator<int, int, ACE_Less_Than<int>, ACE_Null_Mutex> -#pragma instantiate ACE_RB_Tree<int, char *, ACE_Less_Than<int>, ACE_Null_Mutex> -#pragma instantiate ACE_RB_Tree_Node<int, char *> -#pragma instantiate ACE_RB_Tree_Iterator<int, char *, ACE_Less_Than<int>, ACE_Null_Mutex> -#pragma instantiate ACE_RB_Tree<char *, int, ACE_Less_Than<char *>, ACE_Null_Mutex> -#pragma instantiate ACE_RB_Tree_Node<char *, int> -#pragma instantiate ACE_RB_Tree_Iterator<char *, int, ACE_Less_Than<char *>, ACE_Null_Mutex> -#pragma instantiate ACE_RB_Tree<char *, char *, ACE_Less_Than<char *>, ACE_Null_Mutex> -#pragma instantiate ACE_RB_Tree_Node<char *, char *> -#pragma instantiate ACE_RB_Tree_Iterator<char *, char *, ACE_Less_Than<char *>, ACE_Null_Mutex> -#pragma instantiate ACE_Less_Than<int> - -#endif /* ACE_HAS_EXPLICIT_TEMPLATE_INSTANTIATION */ - |