• R/O
  • SSH
  • HTTPS

eirrepo: Commit


Commit MetaInfo

Revision99 (tree)
Time2018-05-13 21:46:01
Authorquiret

Log Message

- fixed a nasty bug that I overlooked in AVLTree.h
- added another unittest

Change Summary

Incremental Difference

--- common/sdk/AVLTree.h (revision 98)
+++ common/sdk/AVLTree.h (revision 99)
@@ -27,9 +27,6 @@
2727 // Useful to fetch an actual struct if AVLNode is a struct-member.
2828 #define AVL_GETITEM( type, nodePtr, nodeMemb ) ( (type*)( (char*)nodePtr - offsetof(type, nodeMemb) ) )
2929
30-// TODO: we actually HAVE TO be able to store SAME VALUES inside of our AVL tree implementation.
31-// this should be managed by stacking nodes if they happen to be the same.
32-
3330 // Has to be less-than comparable, in a total order.
3431 struct AVLNode
3532 {
@@ -548,9 +545,18 @@
548545 // Remove the closest node.
549546 // We know that the node has no right child, because it is the maximum in its subtree.
550547 {
551- *closestReplacementPtr = closestReplacement->left;
548+ AVLNode *leftChildForReplacing = closestReplacement->left;
552549
553- update_invalidated_tree_height( closestReplacement->parent );
550+ *closestReplacementPtr = leftChildForReplacing;
551+
552+ AVLNode *closestReplacementParent = closestReplacement->parent;
553+
554+ if ( leftChildForReplacing != nullptr )
555+ {
556+ leftChildForReplacing->parent = closestReplacementParent;
557+ }
558+
559+ update_invalidated_tree_height( closestReplacementParent );
554560 }
555561
556562 // We need to update members because they could be out-of-date.
--- unittests/src/avltree.cpp (revision 98)
+++ unittests/src/avltree.cpp (revision 99)
@@ -17,7 +17,7 @@
1717 }
1818 };
1919
20-static void check_avl_sort( AVLTree <IntegerItem>& tree )
20+static void check_avl_sort( AVLTree <IntegerItem>& tree, bool hasSameNumbers = false )
2121 {
2222 bool hadLastValue = false;
2323 int last_int;
@@ -33,7 +33,14 @@
3333 }
3434 else
3535 {
36- assert( last_int < curItem->my_number );
36+ if ( hasSameNumbers )
37+ {
38+ assert( last_int <= curItem->my_number );
39+ }
40+ else
41+ {
42+ assert( last_int < curItem->my_number );
43+ }
3744
3845 last_int = curItem->my_number;
3946 }
@@ -79,6 +86,41 @@
7986 }
8087 printf( "ok.\n" );
8188
89+ printf( "testing non-trivial AVL tree sort using same numbers..." );
90+ {
91+ AVLTree <IntegerItem> tree;
92+
93+ static const int my_nums[] = { 43, 42, 12, 74, 4235, 0, 7856, 1232, 44, 623, 754, 4, 1, 7, 42, 482, 111, 321, 0, 88, 1, 3 };
94+
95+ constexpr size_t num_ints = countof(my_nums);
96+
97+ IntegerItem int_items[ num_ints ];
98+
99+ for ( size_t n = 0; n < num_ints; n++ )
100+ {
101+ IntegerItem& curItem = int_items[n];
102+
103+ curItem.my_number = my_nums[n];
104+
105+ tree.Insert( &curItem.node );
106+ tree.Validate();
107+ }
108+
109+ // Check that items are sorted
110+ check_avl_sort( tree, true );
111+
112+ // Remove all items again.
113+ for ( IntegerItem& curItem : int_items )
114+ {
115+ tree.RemoveByNodeFast( &curItem.node );
116+
117+ check_avl_sort( tree, true );
118+
119+ tree.Validate();
120+ }
121+ }
122+ printf( "ok.\n" );
123+
82124 printf( "testing massive AVL tree insert..." );
83125 {
84126 AVLTree <IntegerItem> tree;
@@ -140,8 +182,12 @@
140182
141183 tree.Validate();
142184
185+ assert( tree.GetTreeHeight() == 1 );
186+
143187 tree.RemoveByNodeFast( &first.node );
144188 tree.RemoveByNodeFast( &second.node );
189+
190+ assert( tree.GetTreeHeight() == 0 );
145191 }
146192 printf( "ok.\n" );
147193
Show on old repository browser