diff options
Diffstat (limited to 'tests/libcxx/include/__tree')
| -rw-r--r-- | tests/libcxx/include/__tree | 2238 |
1 files changed, 2238 insertions, 0 deletions
diff --git a/tests/libcxx/include/__tree b/tests/libcxx/include/__tree new file mode 100644 index 00000000..b49e9e4d --- /dev/null +++ b/tests/libcxx/include/__tree @@ -0,0 +1,2238 @@ +// -*- 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& __v) + {return __lower_bound(__v, __root(), __end_node());} + template <class _Key> + iterator __lower_bound(const _Key& __v, + __node_pointer __root, + __node_pointer __result); + template <class _Key> < |