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 __parent_unsafeNode26 Node* __parent_unsafe() const { return __parent_; } __set_parentNode27 void __set_parent(Node* x) { __parent_ = x;} 28 NodeNode29 Node() : __left_(), __right_(), __parent_() {} 30 }; 31 32 void test1()33test1() 34 { 35 Node root; 36 Node x; 37 Node y; 38 root.__left_ = &x; 39 x.__left_ = 0; 40 x.__right_ = &y; 41 x.__parent_ = &root; 42 y.__left_ = 0; 43 y.__right_ = 0; 44 y.__parent_ = &x; 45 std::__tree_left_rotate(&x); 46 assert(root.__parent_ == 0); 47 assert(root.__left_ == &y); 48 assert(root.__right_ == 0); 49 assert(y.__parent_ == &root); 50 assert(y.__left_ == &x); 51 assert(y.__right_ == 0); 52 assert(x.__parent_ == &y); 53 assert(x.__left_ == 0); 54 assert(x.__right_ == 0); 55 } 56 57 void test2()58test2() 59 { 60 Node root; 61 Node x; 62 Node y; 63 Node a; 64 Node b; 65 Node c; 66 root.__left_ = &x; 67 x.__left_ = &a; 68 x.__right_ = &y; 69 x.__parent_ = &root; 70 y.__left_ = &b; 71 y.__right_ = &c; 72 y.__parent_ = &x; 73 a.__parent_ = &x; 74 b.__parent_ = &y; 75 c.__parent_ = &y; 76 std::__tree_left_rotate(&x); 77 assert(root.__parent_ == 0); 78 assert(root.__left_ == &y); 79 assert(root.__right_ == 0); 80 assert(y.__parent_ == &root); 81 assert(y.__left_ == &x); 82 assert(y.__right_ == &c); 83 assert(x.__parent_ == &y); 84 assert(x.__left_ == &a); 85 assert(x.__right_ == &b); 86 assert(a.__parent_ == &x); 87 assert(a.__left_ == 0); 88 assert(a.__right_ == 0); 89 assert(b.__parent_ == &x); 90 assert(b.__left_ == 0); 91 assert(b.__right_ == 0); 92 assert(c.__parent_ == &y); 93 assert(c.__left_ == 0); 94 assert(c.__right_ == 0); 95 } 96 main()97int main() 98 { 99 test1(); 100 test2(); 101 } 102