1 //===----------------------------------------------------------------------===// 2 // 3 // The LLVM Compiler Infrastructure 4 // 5 // This file is dual licensed under the MIT and the University of Illinois Open 6 // Source Licenses. See LICENSE.TXT for details. 7 // 8 //===----------------------------------------------------------------------===// 9 10 // Not a portable test 11 12 // Precondition: __x->__right_ != nullptr 13 // template <class _NodePtr> 14 // void 15 // __tree_left_rotate(_NodePtr __x); 16 17 #include <__tree> 18 #include <cassert> 19 20 struct Node 21 { 22 Node* __left_; 23 Node* __right_; 24 Node* __parent_; 25 NodeNode26 Node() : __left_(), __right_(), __parent_() {} 27 }; 28 29 void test1()30test1() 31 { 32 Node root; 33 Node x; 34 Node y; 35 root.__left_ = &x; 36 x.__left_ = 0; 37 x.__right_ = &y; 38 x.__parent_ = &root; 39 y.__left_ = 0; 40 y.__right_ = 0; 41 y.__parent_ = &x; 42 std::__tree_left_rotate(&x); 43 assert(root.__parent_ == 0); 44 assert(root.__left_ == &y); 45 assert(root.__right_ == 0); 46 assert(y.__parent_ == &root); 47 assert(y.__left_ == &x); 48 assert(y.__right_ == 0); 49 assert(x.__parent_ == &y); 50 assert(x.__left_ == 0); 51 assert(x.__right_ == 0); 52 } 53 54 void test2()55test2() 56 { 57 Node root; 58 Node x; 59 Node y; 60 Node a; 61 Node b; 62 Node c; 63 root.__left_ = &x; 64 x.__left_ = &a; 65 x.__right_ = &y; 66 x.__parent_ = &root; 67 y.__left_ = &b; 68 y.__right_ = &c; 69 y.__parent_ = &x; 70 a.__parent_ = &x; 71 b.__parent_ = &y; 72 c.__parent_ = &y; 73 std::__tree_left_rotate(&x); 74 assert(root.__parent_ == 0); 75 assert(root.__left_ == &y); 76 assert(root.__right_ == 0); 77 assert(y.__parent_ == &root); 78 assert(y.__left_ == &x); 79 assert(y.__right_ == &c); 80 assert(x.__parent_ == &y); 81 assert(x.__left_ == &a); 82 assert(x.__right_ == &b); 83 assert(a.__parent_ == &x); 84 assert(a.__left_ == 0); 85 assert(a.__right_ == 0); 86 assert(b.__parent_ == &x); 87 assert(b.__left_ == 0); 88 assert(b.__right_ == 0); 89 assert(c.__parent_ == &y); 90 assert(c.__left_ == 0); 91 assert(c.__right_ == 0); 92 } 93 main()94int main() 95 { 96 test1(); 97 test2(); 98 } 99