99 lines · cpp
1//===----------------------------------------------------------------------===//2//3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.4// See https://llvm.org/LICENSE.txt for license information.5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception6//7//===----------------------------------------------------------------------===//8 9// Not a portable test10 11// Precondition: __x->__right_ != nullptr12// template <class _NodePtr>13// void14// __tree_left_rotate(_NodePtr __x);15 16#include <__cxx03/__tree>17#include <cassert>18 19#include "test_macros.h"20 21struct Node {22 Node* __left_;23 Node* __right_;24 Node* __parent_;25 26 Node* __parent_unsafe() const { return __parent_; }27 void __set_parent(Node* x) { __parent_ = x; }28 29 Node() : __left_(), __right_(), __parent_() {}30};31 32void test1() {33 Node root;34 Node x;35 Node y;36 root.__left_ = &x;37 x.__left_ = 0;38 x.__right_ = &y;39 x.__parent_ = &root;40 y.__left_ = 0;41 y.__right_ = 0;42 y.__parent_ = &x;43 std::__tree_left_rotate(&x);44 assert(root.__parent_ == 0);45 assert(root.__left_ == &y);46 assert(root.__right_ == 0);47 assert(y.__parent_ == &root);48 assert(y.__left_ == &x);49 assert(y.__right_ == 0);50 assert(x.__parent_ == &y);51 assert(x.__left_ == 0);52 assert(x.__right_ == 0);53}54 55void test2() {56 Node root;57 Node x;58 Node y;59 Node a;60 Node b;61 Node c;62 root.__left_ = &x;63 x.__left_ = &a;64 x.__right_ = &y;65 x.__parent_ = &root;66 y.__left_ = &b;67 y.__right_ = &c;68 y.__parent_ = &x;69 a.__parent_ = &x;70 b.__parent_ = &y;71 c.__parent_ = &y;72 std::__tree_left_rotate(&x);73 assert(root.__parent_ == 0);74 assert(root.__left_ == &y);75 assert(root.__right_ == 0);76 assert(y.__parent_ == &root);77 assert(y.__left_ == &x);78 assert(y.__right_ == &c);79 assert(x.__parent_ == &y);80 assert(x.__left_ == &a);81 assert(x.__right_ == &b);82 assert(a.__parent_ == &x);83 assert(a.__left_ == 0);84 assert(a.__right_ == 0);85 assert(b.__parent_ == &x);86 assert(b.__left_ == 0);87 assert(b.__right_ == 0);88 assert(c.__parent_ == &y);89 assert(c.__left_ == 0);90 assert(c.__right_ == 0);91}92 93int main(int, char**) {94 test1();95 test2();96 97 return 0;98}99