111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert//===----------------------------------------------------------------------===// 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// The LLVM Compiler Infrastructure 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is dual licensed under the MIT and the University of Illinois Open 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Source Licenses. See LICENSE.TXT for details. 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert//===----------------------------------------------------------------------===// 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Not a portable test 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Precondition: __x->__left_ != nullptr 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// template <class _NodePtr> 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// void 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// __tree_right_rotate(_NodePtr __x); 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <__tree> 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <cassert> 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albertstruct Node 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node* __left_; 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node* __right_; 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node* __parent_; 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node() : __left_(), __right_(), __parent_() {} 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert}; 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albertvoid 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttest1() 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node root; 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node x; 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node y; 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert root.__left_ = &x; 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert x.__left_ = &y; 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert x.__right_ = 0; 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert x.__parent_ = &root; 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert y.__left_ = 0; 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert y.__right_ = 0; 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert y.__parent_ = &x; 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::__tree_right_rotate(&x); 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(root.__parent_ == 0); 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(root.__left_ == &y); 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(root.__right_ == 0); 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(y.__parent_ == &root); 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(y.__left_ == 0); 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(y.__right_ == &x); 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(x.__parent_ == &y); 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(x.__left_ == 0); 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(x.__right_ == 0); 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albertvoid 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Alberttest2() 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node root; 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node x; 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node y; 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node a; 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node b; 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Node c; 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert root.__left_ = &x; 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert x.__left_ = &y; 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert x.__right_ = &c; 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert x.__parent_ = &root; 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert y.__left_ = &a; 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert y.__right_ = &b; 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert y.__parent_ = &x; 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert a.__parent_ = &y; 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert b.__parent_ = &y; 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert c.__parent_ = &x; 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert std::__tree_right_rotate(&x); 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(root.__parent_ == 0); 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(root.__left_ == &y); 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(root.__right_ == 0); 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(y.__parent_ == &root); 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(y.__left_ == &a); 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(y.__right_ == &x); 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(x.__parent_ == &y); 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(x.__left_ == &b); 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(x.__right_ == &c); 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(a.__parent_ == &y); 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(a.__left_ == 0); 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(a.__right_ == 0); 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(b.__parent_ == &x); 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(b.__left_ == 0); 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(b.__right_ == 0); 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(c.__parent_ == &x); 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(c.__left_ == 0); 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert(c.__right_ == 0); 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albertint main() 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert test1(); 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert test2(); 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} 99