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()30 test1()
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()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_ = &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()94 int main()
95 {
96     test1();
97     test2();
98 }
99