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 20struct Node 21{ 22 Node* __left_; 23 Node* __right_; 24 Node* __parent_; 25 26 Node() : __left_(), __right_(), __parent_() {} 27}; 28 29void 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 54void 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 94int main() 95{ 96 test1(); 97 test2(); 98} 99