diff options
Diffstat (limited to 'tests/libcxx/include/__tree')
| -rw-r--r-- | tests/libcxx/include/__tree | 2238 |
1 files changed, 0 insertions, 2238 deletions
diff --git a/tests/libcxx/include/__tree b/tests/libcxx/include/__tree deleted file mode 100644 index b49e9e4d..00000000 --- a/tests/libcxx/include/__tree +++ /dev/null @@ -1,2238 +0,0 @@ -// -*- C++ -*- -//===----------------------------------------------------------------------===// -// -// The LLVM Compiler Infrastructure -// -// This file is dual licensed under the MIT and the University of Illinois Open -// Source Licenses. See LICENSE.TXT for details. -// -//===----------------------------------------------------------------------===// - -#ifndef _LIBCPP___TREE -#define _LIBCPP___TREE - -#include <__config> -#include <iterator> -#include <memory> -#include <stdexcept> -#include <algorithm> - -#pragma GCC system_header - -_LIBCPP_BEGIN_NAMESPACE_STD - -template <class, class, class> class __tree; -template <class, class, class> class _LIBCPP_VISIBLE __tree_iterator; -template <class, class, class> class _LIBCPP_VISIBLE __tree_const_iterator; -template <class, class, class, class> class _LIBCPP_VISIBLE map; -template <class, class, class, class> class _LIBCPP_VISIBLE multimap; -template <class, class, class> class _LIBCPP_VISIBLE set; -template <class, class, class> class _LIBCPP_VISIBLE multiset; - -/* - -_NodePtr algorithms - -The algorithms taking _NodePtr are red black tree algorithms. Those -algorithms taking a parameter named __root should assume that __root -points to a proper red black tree (unless otherwise specified). - -Each algorithm herein assumes that __root->__parent_ points to a non-null -structure which has a member __left_ which points back to __root. No other -member is read or written to at __root->__parent_. - -__root->__parent_ will be referred to below (in comments only) as end_node. -end_node->__left_ is an externably accessible lvalue for __root, and can be -changed by node insertion and removal (without explicit reference to end_node). - -All nodes (with the exception of end_node), even the node referred to as -__root, have a non-null __parent_ field. - -*/ - -// Returns: true if __x is a left child of its parent, else false -// Precondition: __x != nullptr. -template <class _NodePtr> -inline _LIBCPP_INLINE_VISIBILITY -bool -__tree_is_left_child(_NodePtr __x) -{ - return __x == __x->__parent_->__left_; -} - -// Determintes if the subtree rooted at __x is a proper red black subtree. If -// __x is a proper subtree, returns the black height (null counts as 1). If -// __x is an improper subtree, returns 0. -template <class _NodePtr> -unsigned -__tree_sub_invariant(_NodePtr __x) -{ - if (__x == nullptr) - return 1; - // parent consistency checked by caller - // check __x->__left_ consistency - if (__x->__left_ != nullptr && __x->__left_->__parent_ != __x) - return 0; - // check __x->__right_ consistency - if (__x->__right_ != nullptr && __x->__right_->__parent_ != __x) - return 0; - // check __x->__left_ != __x->__right_ unless both are nullptr - if (__x->__left_ == __x->__right_ && __x->__left_ != nullptr) - return 0; - // If this is red, neither child can be red - if (!__x->__is_black_) - { - if (__x->__left_ && !__x->__left_->__is_black_) - return 0; - if (__x->__right_ && !__x->__right_->__is_black_) - return 0; - } - unsigned __h = __tree_sub_invariant(__x->__left_); - if (__h == 0) - return 0; // invalid left subtree - if (__h != __tree_sub_invariant(__x->__right_)) - return 0; // invalid or different height right subtree - return __h + __x->__is_black_; // return black height of this node -} - -// Determintes if the red black tree rooted at __root is a proper red black tree. -// __root == nullptr is a proper tree. Returns true is __root is a proper -// red black tree, else returns false. -template <class _NodePtr> -bool -__tree_invariant(_NodePtr __root) -{ - if (__root == nullptr) - return true; - // check __x->__parent_ consistency - if (__root->__parent_ == nullptr) - return false; - if (!__tree_is_left_child(__root)) - return false; - // root must be black - if (!__root->__is_black_) - return false; - // do normal node checks - return __tree_sub_invariant(__root) != 0; -} - -// Returns: pointer to the left-most node under __x. -// Precondition: __x != nullptr. -template <class _NodePtr> -inline _LIBCPP_INLINE_VISIBILITY -_NodePtr -__tree_min(_NodePtr __x) -{ - while (__x->__left_ != nullptr) - __x = __x->__left_; - return __x; -} - -// Returns: pointer to the right-most node under __x. -// Precondition: __x != nullptr. -template <class _NodePtr> -inline _LIBCPP_INLINE_VISIBILITY -_NodePtr -__tree_max(_NodePtr __x) -{ - while (__x->__right_ != nullptr) - __x = __x->__right_; - return __x; -} - -// Returns: pointer to the next in-order node after __x. -// Precondition: __x != nullptr. -template <class _NodePtr> -_NodePtr -__tree_next(_NodePtr __x) -{ - if (__x->__right_ != nullptr) - return __tree_min(__x->__right_); - while (!__tree_is_left_child(__x)) - __x = __x->__parent_; - return __x->__parent_; -} - -// Returns: pointer to the previous in-order node before __x. -// Precondition: __x != nullptr. -template <class _NodePtr> -_NodePtr -__tree_prev(_NodePtr __x) -{ - if (__x->__left_ != nullptr) - return __tree_max(__x->__left_); - while (__tree_is_left_child(__x)) - __x = __x->__parent_; - return __x->__parent_; -} - -// Returns: pointer to a node which has no children -// Precondition: __x != nullptr. -template <class _NodePtr> -_NodePtr -__tree_leaf(_NodePtr __x) -{ - while (true) - { - if (__x->__left_ != nullptr) - { - __x = __x->__left_; - continue; - } - if (__x->__right_ != nullptr) - { - __x = __x->__right_; - continue; - } - break; - } - return __x; -} - -// Effects: Makes __x->__right_ the subtree root with __x as its left child -// while preserving in-order order. -// Precondition: __x->__right_ != nullptr -template <class _NodePtr> -void -__tree_left_rotate(_NodePtr __x) -{ - _NodePtr __y = __x->__right_; - __x->__right_ = __y->__left_; - if (__x->__right_ != nullptr) - __x->__right_->__parent_ = __x; - __y->__parent_ = __x->__parent_; - if (__tree_is_left_child(__x)) - __x->__parent_->__left_ = __y; - else - __x->__parent_->__right_ = __y; - __y->__left_ = __x; - __x->__parent_ = __y; -} - -// Effects: Makes __x->__left_ the subtree root with __x as its right child -// while preserving in-order order. -// Precondition: __x->__left_ != nullptr -template <class _NodePtr> -void -__tree_right_rotate(_NodePtr __x) -{ - _NodePtr __y = __x->__left_; - __x->__left_ = __y->__right_; - if (__x->__left_ != nullptr) - __x->__left_->__parent_ = __x; - __y->__parent_ = __x->__parent_; - if (__tree_is_left_child(__x)) - __x->__parent_->__left_ = __y; - else - __x->__parent_->__right_ = __y; - __y->__right_ = __x; - __x->__parent_ = __y; -} - -// Effects: Rebalances __root after attaching __x to a leaf. -// Precondition: __root != nulptr && __x != nullptr. -// __x has no children. -// __x == __root or == a direct or indirect child of __root. -// If __x were to be unlinked from __root (setting __root to -// nullptr if __root == __x), __tree_invariant(__root) == true. -// Postcondition: __tree_invariant(end_node->__left_) == true. end_node->__left_ -// may be different than the value passed in as __root. -template <class _NodePtr> -void -__tree_balance_after_insert(_NodePtr __root, _NodePtr __x) -{ - __x->__is_black_ = __x == __root; - while (__x != __root && !__x->__parent_->__is_black_) - { - // __x->__parent_ != __root because __x->__parent_->__is_black == false - if (__tree_is_left_child(__x->__parent_)) - { - _NodePtr __y = __x->__parent_->__parent_->__right_; - if (__y != nullptr && !__y->__is_black_) - { - __x = __x->__parent_; - __x->__is_black_ = true; - __x = __x->__parent_; - __x->__is_black_ = __x == __root; - __y->__is_black_ = true; - } - else - { - if (!__tree_is_left_child(__x)) - { - __x = __x->__parent_; - __tree_left_rotate(__x); - } - __x = __x->__parent_; - __x->__is_black_ = true; - __x = __x->__parent_; - __x->__is_black_ = false; - __tree_right_rotate(__x); - break; - } - } - else - { - _NodePtr __y = __x->__parent_->__parent_->__left_; - if (__y != nullptr && !__y->__is_black_) - { - __x = __x->__parent_; - __x->__is_black_ = true; - __x = __x->__parent_; - __x->__is_black_ = __x == __root; - __y->__is_black_ = true; - } - else - { - if (__tree_is_left_child(__x)) - { - __x = __x->__parent_; - __tree_right_rotate(__x); - } - __x = __x->__parent_; - __x->__is_black_ = true; - __x = __x->__parent_; - __x->__is_black_ = false; - __tree_left_rotate(__x); - break; - } - } - } -} - -// Precondition: __root != nullptr && __z != nullptr. -// __tree_invariant(__root) == true. -// __z == __root or == a direct or indirect child of __root. -// Effects: unlinks __z from the tree rooted at __root, rebalancing as needed. -// Postcondition: __tree_invariant(end_node->__left_) == true && end_node->__left_ -// nor any of its children refer to __z. end_node->__left_ -// may be different than the value passed in as __root. -template <class _NodePtr> -void -__tree_remove(_NodePtr __root, _NodePtr __z) -{ - // __z will be removed from the tree. Client still needs to destruct/deallocate it - // __y is either __z, or if __z has two children, __tree_next(__z). - // __y will have at most one child. - // __y will be the initial hole in the tree (make the hole at a leaf) - _NodePtr __y = (__z->__left_ == nullptr || __z->__right_ == nullptr) ? - __z : __tree_next(__z); - // __x is __y's possibly null single child - _NodePtr __x = __y->__left_ != nullptr ? __y->__left_ : __y->__right_; - // __w is __x's possibly null uncle (will become __x's sibling) - _NodePtr __w = nullptr; - // link __x to __y's parent, and find __w - if (__x != nullptr) - __x->__parent_ = __y->__parent_; - if (__tree_is_left_child(__y)) - { - __y->__parent_->__left_ = __x; - if (__y != __root) - __w = __y->__parent_->__right_; - else - __root = __x; // __w == nullptr - } - else - { - __y->__parent_->__right_ = __x; - // __y can't be root if it is a right child - __w = __y->__parent_->__left_; - } - bool __removed_black = __y->__is_black_; - // If we didn't remove __z, do so now by splicing in __y for __z, - // but copy __z's color. This does not impact __x or __w. - if (__y != __z) - { - // __z->__left_ != nulptr but __z->__right_ might == __x == nullptr - __y->__parent_ = __z->__parent_; - if (__tree_is_left_child(__z)) - __y->__parent_->__left_ = __y; - else - __y->__parent_->__right_ = __y; - __y->__left_ = __z->__left_; - __y->__left_->__parent_ = __y; - __y->__right_ = __z->__right_; - if (__y->__right_ != nullptr) - __y->__right_->__parent_ = __y; - __y->__is_black_ = __z->__is_black_; - if (__root == __z) - __root = __y; - } - // There is no need to rebalance if we removed a red, or if we removed - // the last node. - if (__removed_black && __root != nullptr) - { - // Rebalance: - // __x has an implicit black color (transferred from the removed __y) - // associated with it, no matter what its color is. - // If __x is __root (in which case it can't be null), it is supposed - // to be black anyway, and if it is doubly black, then the double - // can just be ignored. - // If __x is red (in which case it can't be null), then it can absorb - // the implicit black just by setting its color to black. - // Since __y was black and only had one child (which __x points to), __x - // is either red with no children, else null, otherwise __y would have - // different black heights under left and right pointers. - // if (__x == __root || __x != nullptr && !__x->__is_black_) - if (__x != nullptr) - __x->__is_black_ = true; - else - { - // Else __x isn't root, and is "doubly black", even though it may - // be null. __w can not be null here, else the parent would - // see a black height >= 2 on the __x side and a black height - // of 1 on the __w side (__w must be a non-null black or a red - // with a non-null black child). - while (true) - { - if (!__tree_is_left_child(__w)) // if x is left child - { - if (!__w->__is_black_) - { - __w->__is_black_ = true; - __w->__parent_->__is_black_ = false; - __tree_left_rotate(__w->__parent_); - // __x is still valid - // reset __root only if necessary - if (__root == __w->__left_) - __root = __w; - // reset sibling, and it still can't be null - __w = __w->__left_->__right_; - } - // __w->__is_black_ is now true, __w may have null children - if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && - (__w->__right_ == nullptr || __w->__right_->__is_black_)) - { - __w->__is_black_ = false; - __x = __w->__parent_; - // __x can no longer be null - if (__x == __root || !__x->__is_black_) - { - __x->__is_black_ = true; - break; - } - // reset sibling, and it still can't be null - __w = __tree_is_left_child(__x) ? - __x->__parent_->__right_ : - __x->__parent_->__left_; - // continue; - } - else // __w has a red child - { - if (__w->__right_ == nullptr || __w->__right_->__is_black_) - { - // __w left child is non-null and red - __w->__left_->__is_black_ = true; - __w->__is_black_ = false; - __tree_right_rotate(__w); - // __w is known not to be root, so root hasn't changed - // reset sibling, and it still can't be null - __w = __w->__parent_; - } - // __w has a right red child, left child may be null - __w->__is_black_ = __w->__parent_->__is_black_; - __w->__parent_->__is_black_ = true; - __w->__right_->__is_black_ = true; - __tree_left_rotate(__w->__parent_); - break; - } - } - else - { - if (!__w->__is_black_) - { - __w->__is_black_ = true; - __w->__parent_->__is_black_ = false; - __tree_right_rotate(__w->__parent_); - // __x is still valid - // reset __root only if necessary - if (__root == __w->__right_) - __root = __w; - // reset sibling, and it still can't be null - __w = __w->__right_->__left_; - } - // __w->__is_black_ is now true, __w may have null children - if ((__w->__left_ == nullptr || __w->__left_->__is_black_) && - (__w->__right_ == nullptr || __w->__right_->__is_black_)) - { - __w->__is_black_ = false; - __x = __w->__parent_; - // __x can no longer be null - if (!__x->__is_black_ || __x == __root) - { - __x->__is_black_ = true; - break; - } - // reset sibling, and it still can't be null - __w = __tree_is_left_child(__x) ? - __x->__parent_->__right_ : - __x->__parent_->__left_; - // continue; - } - else // __w has a red child - { - if (__w->__left_ == nullptr || __w->__left_->__is_black_) - { - // __w right child is non-null and red - __w->__right_->__is_black_ = true; - __w->__is_black_ = false; - __tree_left_rotate(__w); - // __w is known not to be root, so root hasn't changed - // reset sibling, and it still can't be null - __w = __w->__parent_; - } - // __w has a left red child, right child may be null - __w->__is_black_ = __w->__parent_->__is_black_; - __w->__parent_->__is_black_ = true; - __w->__left_->__is_black_ = true; - __tree_right_rotate(__w->__parent_); - break; - } - } - } - } - } -} - -template <class> class __map_node_destructor; - -template <class _Allocator> -class __tree_node_destructor -{ - typedef _Allocator allocator_type; - typedef allocator_traits<allocator_type> __alloc_traits; - typedef typename __alloc_traits::value_type::value_type value_type; -public: - typedef typename __alloc_traits::pointer pointer; -private: - - allocator_type& __na_; - - __tree_node_destructor& operator=(const __tree_node_destructor&); - -public: - bool __value_constructed; - - _LIBCPP_INLINE_VISIBILITY - explicit __tree_node_destructor(allocator_type& __na) - : __na_(__na), - __value_constructed(false) - {} - - _LIBCPP_INLINE_VISIBILITY - void operator()(pointer __p) - { - if (__value_constructed) - __alloc_traits::destroy(__na_, addressof(__p->__value_)); - if (__p) - __alloc_traits::deallocate(__na_, __p, 1); - } - - template <class> friend class __map_node_destructor; -}; - -// node - -template <class _Pointer> -class __tree_end_node -{ -public: - typedef _Pointer pointer; - pointer __left_; - - _LIBCPP_INLINE_VISIBILITY - __tree_end_node() : __left_() {} -}; - -template <class _VoidPtr> -class __tree_node_base - : public __tree_end_node - < - typename pointer_traits<_VoidPtr>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__tree_node_base<_VoidPtr> > -#else - rebind<__tree_node_base<_VoidPtr> >::other -#endif - > -{ - __tree_node_base(const __tree_node_base&); - __tree_node_base& operator=(const __tree_node_base&); -public: - typedef typename pointer_traits<_VoidPtr>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__tree_node_base> -#else - rebind<__tree_node_base>::other -#endif - pointer; - typedef typename pointer_traits<_VoidPtr>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<const __tree_node_base> -#else - rebind<const __tree_node_base>::other -#endif - const_pointer; - typedef __tree_end_node<pointer> base; - - pointer __right_; - pointer __parent_; - bool __is_black_; - - _LIBCPP_INLINE_VISIBILITY - __tree_node_base() : __right_(), __parent_(), __is_black_(false) {} -}; - -template <class _Tp, class _VoidPtr> -class __tree_node - : public __tree_node_base<_VoidPtr> -{ -public: - typedef __tree_node_base<_VoidPtr> base; - typedef _Tp value_type; - - value_type __value_; - -#if !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) - template <class ..._Args> - _LIBCPP_INLINE_VISIBILITY - explicit __tree_node(_Args&& ...__args) - : __value_(_STD::forward<_Args>(__args)...) {} -#else // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) - _LIBCPP_INLINE_VISIBILITY - explicit __tree_node(const value_type& __v) - : __value_(__v) {} -#endif // !defined(_LIBCPP_HAS_NO_RVALUE_REFERENCES) && !defined(_LIBCPP_HAS_NO_VARIADICS) -}; - -template <class> class __map_iterator; -template <class> class __map_const_iterator; - -template <class _Tp, class _NodePtr, class _DiffType> -class _LIBCPP_VISIBLE __tree_iterator -{ - typedef _NodePtr __node_pointer; - typedef typename pointer_traits<__node_pointer>::element_type __node; - typedef typename __node::base __node_base; - typedef typename __node_base::pointer __node_base_pointer; - - __node_pointer __ptr_; - - typedef pointer_traits<__node_pointer> __pointer_traits; -public: - typedef bidirectional_iterator_tag iterator_category; - typedef _Tp value_type; - typedef _DiffType difference_type; - typedef value_type& reference; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<value_type> -#else - rebind<value_type>::other -#endif - pointer; - - _LIBCPP_INLINE_VISIBILITY __tree_iterator() {} - - _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;} - _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &__ptr_->__value_;} - - _LIBCPP_INLINE_VISIBILITY - __tree_iterator& operator++() - {__ptr_ = static_cast<__node_pointer>(__tree_next(static_cast<__node_base_pointer>(__ptr_))); - return *this;} - _LIBCPP_INLINE_VISIBILITY - __tree_iterator operator++(int) - {__tree_iterator __t(*this); ++(*this); return __t;} - - _LIBCPP_INLINE_VISIBILITY - __tree_iterator& operator--() - {__ptr_ = static_cast<__node_pointer>(__tree_prev(static_cast<__node_base_pointer>(__ptr_))); - return *this;} - _LIBCPP_INLINE_VISIBILITY - __tree_iterator operator--(int) - {__tree_iterator __t(*this); --(*this); return __t;} - - friend _LIBCPP_INLINE_VISIBILITY - bool operator==(const __tree_iterator& __x, const __tree_iterator& __y) - {return __x.__ptr_ == __y.__ptr_;} - friend _LIBCPP_INLINE_VISIBILITY - bool operator!=(const __tree_iterator& __x, const __tree_iterator& __y) - {return !(__x == __y);} - -private: - _LIBCPP_INLINE_VISIBILITY - explicit __tree_iterator(__node_pointer __p) : __ptr_(__p) {} - template <class, class, class> friend class __tree; - template <class, class, class> friend class _LIBCPP_VISIBLE __tree_const_iterator; - template <class> friend class _LIBCPP_VISIBLE __map_iterator; - template <class, class, class, class> friend class _LIBCPP_VISIBLE map; - template <class, class, class, class> friend class _LIBCPP_VISIBLE multimap; - template <class, class, class> friend class _LIBCPP_VISIBLE set; - template <class, class, class> friend class _LIBCPP_VISIBLE multiset; -}; - -template <class _Tp, class _ConstNodePtr, class _DiffType> -class _LIBCPP_VISIBLE __tree_const_iterator -{ - typedef _ConstNodePtr __node_pointer; - typedef typename pointer_traits<__node_pointer>::element_type __node; - typedef const typename __node::base __node_base; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__node_base> -#else - rebind<__node_base>::other -#endif - __node_base_pointer; - - __node_pointer __ptr_; - - typedef pointer_traits<__node_pointer> __pointer_traits; -public: - typedef bidirectional_iterator_tag iterator_category; - typedef _Tp value_type; - typedef _DiffType difference_type; - typedef const value_type& reference; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<const value_type> -#else - rebind<const value_type>::other -#endif - pointer; - - _LIBCPP_INLINE_VISIBILITY __tree_const_iterator() {} -private: - typedef typename remove_const<__node>::type __non_const_node; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__non_const_node> -#else - rebind<__non_const_node>::other -#endif - __non_const_node_pointer; - typedef __tree_iterator<value_type, __non_const_node_pointer, difference_type> - __non_const_iterator; -public: - _LIBCPP_INLINE_VISIBILITY - __tree_const_iterator(__non_const_iterator __p) : __ptr_(__p.__ptr_) {} - - _LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;} - _LIBCPP_INLINE_VISIBILITY pointer operator->() const {return &__ptr_->__value_;} - - _LIBCPP_INLINE_VISIBILITY - __tree_const_iterator& operator++() - {__ptr_ = static_cast<__node_pointer>(__tree_next(static_cast<__node_base_pointer>(__ptr_))); - return *this;} - _LIBCPP_INLINE_VISIBILITY - __tree_const_iterator operator++(int) - {__tree_const_iterator __t(*this); ++(*this); return __t;} - - _LIBCPP_INLINE_VISIBILITY - __tree_const_iterator& operator--() - {__ptr_ = static_cast<__node_pointer>(__tree_prev(static_cast<__node_base_pointer>(__ptr_))); - return *this;} - _LIBCPP_INLINE_VISIBILITY - __tree_const_iterator operator--(int) - {__tree_const_iterator __t(*this); --(*this); return __t;} - - friend _LIBCPP_INLINE_VISIBILITY - bool operator==(const __tree_const_iterator& __x, const __tree_const_iterator& __y) - {return __x.__ptr_ == __y.__ptr_;} - friend _LIBCPP_INLINE_VISIBILITY - bool operator!=(const __tree_const_iterator& __x, const __tree_const_iterator& __y) - {return !(__x == __y);} - -private: - _LIBCPP_INLINE_VISIBILITY - explicit __tree_const_iterator(__node_pointer __p) : __ptr_(__p) {} - template <class, class, class> friend class __tree; - template <class, class, class, class> friend class _LIBCPP_VISIBLE map; - template <class, class, class, class> friend class _LIBCPP_VISIBLE multimap; - template <class, class, class> friend class _LIBCPP_VISIBLE set; - template <class, class, class> friend class _LIBCPP_VISIBLE multiset; - template <class> friend class _LIBCPP_VISIBLE __map_const_iterator; -}; - -template <class _Tp, class _Compare, class _Allocator> -class __tree -{ -public: - typedef _Tp value_type; - typedef _Compare value_compare; - typedef _Allocator allocator_type; - typedef allocator_traits<allocator_type> __alloc_traits; - typedef typename __alloc_traits::pointer pointer; - typedef typename __alloc_traits::const_pointer const_pointer; - typedef typename __alloc_traits::size_type size_type; - typedef typename __alloc_traits::difference_type difference_type; - - typedef __tree_node<value_type, typename __alloc_traits::void_pointer> __node; - typedef typename __alloc_traits::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind_alloc<__node> -#else - rebind_alloc<__node>::other -#endif - __node_allocator; - typedef allocator_traits<__node_allocator> __node_traits; - typedef typename __node_traits::pointer __node_pointer; - typedef typename __node_traits::const_pointer __node_const_pointer; - typedef typename __node::base::pointer __node_base_pointer; - typedef typename __node::base::const_pointer __node_base_const_pointer; -private: - typedef typename __node::base::base __end_node_t; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<__end_node_t> -#else - rebind<__end_node_t>::other -#endif - __end_node_ptr; - typedef typename pointer_traits<__node_pointer>::template -#ifndef _LIBCPP_HAS_NO_TEMPLATE_ALIASES - rebind<const __end_node_t> -#else - rebind<const __end_node_t>::other -#endif - __end_node_const_ptr; - - __node_pointer __begin_node_; - __compressed_pair<__end_node_t, __node_allocator> __pair1_; - __compressed_pair<size_type, value_compare> __pair3_; - -public: - _LIBCPP_INLINE_VISIBILITY - __node_pointer __end_node() - { - return static_cast<__node_pointer> - ( - pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first()) - ); - } - _LIBCPP_INLINE_VISIBILITY - __node_const_pointer __end_node() const - { - return static_cast<__node_const_pointer> - ( - pointer_traits<__end_node_const_ptr>::pointer_to(__pair1_.first()) - ); - } - _LIBCPP_INLINE_VISIBILITY - __node_allocator& __node_alloc() {return __pair1_.second();} -private: - _LIBCPP_INLINE_VISIBILITY - const __node_allocator& __node_alloc() const {return __pair1_.second();} - _LIBCPP_INLINE_VISIBILITY - __node_pointer& __begin_node() {return __begin_node_;} - _LIBCPP_INLINE_VISIBILITY - const __node_pointer& __begin_node() const {return __begin_node_;} -public: - _LIBCPP_INLINE_VISIBILITY - allocator_type __alloc() const {return allocator_type(__node_alloc());} -private: - _LIBCPP_INLINE_VISIBILITY - size_type& size() {return __pair3_.first();} -public: - _LIBCPP_INLINE_VISIBILITY - const size_type& size() const {return __pair3_.first();} - _LIBCPP_INLINE_VISIBILITY - value_compare& value_comp() {return __pair3_.second();} - _LIBCPP_INLINE_VISIBILITY - const value_compare& value_comp() const {return __pair3_.second();} -public: - _LIBCPP_INLINE_VISIBILITY - __node_pointer __root() - {return static_cast<__node_pointer> (__end_node()->__left_);} - _LIBCPP_INLINE_VISIBILITY - __node_const_pointer __root() const - {return static_cast<__node_const_pointer>(__end_node()->__left_);} - - typedef __tree_iterator<value_type, __node_pointer, difference_type> iterator; - typedef __tree_const_iterator<value_type, __node_const_pointer, difference_type> const_iterator; - - explicit __tree(const value_compare& __comp); - explicit __tree(const allocator_type& __a); - __tree(const value_compare& __comp, const allocator_type& __a); - __tree(const __tree& __t); - __tree& operator=(const __tree& __t); - template <class _InputIterator> - void __assign_unique(_InputIterator __first, _InputIterator __last); - template <class _InputIterator> - void __assign_multi(_InputIterator __first, _InputIterator __last); -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES - __tree(__tree&& __t); - __tree(__tree&& __t, const allocator_type& __a); - __tree& operator=(__tree&& __t); -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - - ~__tree(); - - _LIBCPP_INLINE_VISIBILITY - iterator begin() {return iterator(__begin_node());} - _LIBCPP_INLINE_VISIBILITY - const_iterator begin() const {return const_iterator(__begin_node());} - _LIBCPP_INLINE_VISIBILITY - iterator end() {return iterator(__end_node());} - _LIBCPP_INLINE_VISIBILITY - const_iterator end() const {return const_iterator(__end_node());} - - _LIBCPP_INLINE_VISIBILITY - size_type max_size() const {return __node_traits::max_size(__node_alloc());} - - void clear(); - - void swap(__tree& __t); - -#ifndef _LIBCPP_HAS_NO_RVALUE_REFERENCES -#ifndef _LIBCPP_HAS_NO_VARIADICS - template <class... _Args> - pair<iterator, bool> - __emplace_unique(_Args&&... __args); - template <class... _Args> - iterator - __emplace_multi(_Args&&... __args); - - template <class... _Args> - iterator - __emplace_hint_unique(const_iterator __p, _Args&&... __args); - template <class... _Args> - iterator - __emplace_hint_multi(const_iterator __p, _Args&&... __args); -#endif // _LIBCPP_HAS_NO_VARIADICS - - template <class _V> - pair<iterator, bool> __insert_unique(_V&& __v); - template <class _V> - iterator __insert_unique(const_iterator __p, _V&& __v); - template <class _V> - iterator __insert_multi(_V&& __v); - template <class _V> - iterator __insert_multi(const_iterator __p, _V&& __v); -#else // _LIBCPP_HAS_NO_RVALUE_REFERENCES - - pair<iterator, bool> __insert_unique(const value_type& __v); - iterator __insert_unique(const_iterator __p, const value_type& __v); - iterator __insert_multi(const value_type& __v); - iterator __insert_multi(const_iterator __p, const value_type& __v); -#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES - - pair<iterator, bool> __node_insert_unique(__node_pointer __nd); - iterator __node_insert_unique(const_iterator __p, - __node_pointer __nd); - - iterator __node_insert_multi(__node_pointer __nd); - iterator __node_insert_multi(const_iterator __p, __node_pointer __nd); - - iterator erase(const_iterator __p); - iterator erase(const_iterator __f, const_iterator __l); - template <class _Key> - size_type __erase_unique(const _Key& __k); - template <class _Key> - size_type __erase_multi(const _Key& __k); - - void __insert_node_at(__node_base_pointer __parent, - __node_base_pointer& __child, - __node_base_pointer __new_node); - - template <class _Key> - iterator find(const _Key& __v); - template <class _Key> - const_iterator find(const _Key& __v) const; - - template <class _Key> - size_type __count_unique(const _Key& __k) const; - template <class _Key> - size_type __count_multi(const _Key& __k) const; - - template <class _Key> - _LIBCPP_INLINE_VISIBILITY - iterator lower_bound(const _Key& __ |