| Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 1 | //===----------------------------------------------------------------------===// |
| 2 | // |
| Howard Hinnant | f5256e1 | 2010-05-11 21:36:01 +0000 | [diff] [blame] | 3 | // The LLVM Compiler Infrastructure |
| Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 4 | // |
| Howard Hinnant | b64f8b0 | 2010-11-16 22:09:02 +0000 | [diff] [blame] | 5 | // This file is dual licensed under the MIT and the University of Illinois Open |
| 6 | // Source Licenses. See LICENSE.TXT for details. |
| Howard Hinnant | bc8d3f9 | 2010-05-11 19:42:16 +0000 | [diff] [blame] | 7 | // |
| 8 | //===----------------------------------------------------------------------===// |
| 9 | |
| 10 | // Not a portable test |
| 11 | |
| 12 | // Precondition: __x->__left_ != nullptr |
| 13 | // template <class _NodePtr> |
| 14 | // void |
| 15 | // __tree_right_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 | |
| 26 | Node() : __left_(), __right_(), __parent_() {} |
| 27 | }; |
| 28 | |
| 29 | void |
| 30 | test1() |
| 31 | { |
| 32 | Node root; |
| 33 | Node x; |
| 34 | Node y; |
| 35 | root.__left_ = &x; |
| 36 | x.__left_ = &y; |
| 37 | x.__right_ = 0; |
| 38 | x.__parent_ = &root; |
| 39 | y.__left_ = 0; |
| 40 | y.__right_ = 0; |
| 41 | y.__parent_ = &x; |
| 42 | std::__tree_right_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_ == 0); |
| 48 | assert(y.__right_ == &x); |
| 49 | assert(x.__parent_ == &y); |
| 50 | assert(x.__left_ == 0); |
| 51 | assert(x.__right_ == 0); |
| 52 | } |
| 53 | |
| 54 | void |
| 55 | test2() |
| 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_ = &y; |
| 65 | x.__right_ = &c; |
| 66 | x.__parent_ = &root; |
| 67 | y.__left_ = &a; |
| 68 | y.__right_ = &b; |
| 69 | y.__parent_ = &x; |
| 70 | a.__parent_ = &y; |
| 71 | b.__parent_ = &y; |
| 72 | c.__parent_ = &x; |
| 73 | std::__tree_right_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_ == &a); |
| 79 | assert(y.__right_ == &x); |
| 80 | assert(x.__parent_ == &y); |
| 81 | assert(x.__left_ == &b); |
| 82 | assert(x.__right_ == &c); |
| 83 | assert(a.__parent_ == &y); |
| 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_ == &x); |
| 90 | assert(c.__left_ == 0); |
| 91 | assert(c.__right_ == 0); |
| 92 | } |
| 93 | |
| 94 | int main() |
| 95 | { |
| 96 | test1(); |
| 97 | test2(); |
| 98 | } |