// -*- 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>

#if !defined(_LIBCPP_HAS_NO_PRAGMA_SYSTEM_HEADER)

#pragma GCC system_header

#endif

_LIBCPP_BEGIN_NAMESPACE_STD

template <class _Tp, class _Compare, class _Allocator> class __tree;

template <class _Tp, class _NodePtr, class _DiffType>

class _LIBCPP_TYPE_VIS_ONLY __tree_iterator;

template <class _Tp, class _ConstNodePtr, class _DiffType>

class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;

template <class _Key, class _Tp, class _Compare, class _Allocator>

class _LIBCPP_TYPE_VIS_ONLY map;

template <class _Key, class _Tp, class _Compare, class _Allocator>

class _LIBCPP_TYPE_VIS_ONLY multimap;

template <class _Key, class _Compare, class _Allocator>

class _LIBCPP_TYPE_VIS_ONLY set;

template <class _Key, class _Compare, class _Allocator>

class _LIBCPP_TYPE_VIS_ONLY 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) _NOEXCEPT

{

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) _NOEXCEPT

{

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) _NOEXCEPT

{

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) _NOEXCEPT

{

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) _NOEXCEPT

{

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) _NOEXCEPT

{

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) _NOEXCEPT

{

_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) _NOEXCEPT

{

_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) _NOEXCEPT

{

__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) _NOEXCEPT

{

// __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 _Allocator> 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) _NOEXCEPT

: __na_(__na),

__value_constructed(false)

{}

_LIBCPP_INLINE_VISIBILITY

void operator()(pointer __p) _NOEXCEPT

{

if (__value_constructed)

__alloc_traits::destroy(__na_, _VSTD::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() _NOEXCEPT : __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() _NOEXCEPT

: __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_(_VSTD::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 _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_iterator;

template <class _TreeIterator> class _LIBCPP_TYPE_VIS_ONLY __map_const_iterator;

template <class _Tp, class _NodePtr, class _DiffType>

class _LIBCPP_TYPE_VIS_ONLY __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() _NOEXCEPT

#if _LIBCPP_STD_VER > 11

: __ptr_(nullptr)

#endif

{}

_LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}

_LIBCPP_INLINE_VISIBILITY pointer operator->() const

{return pointer_traits<pointer>::pointer_to(__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) _NOEXCEPT : __ptr_(__p) {}

template <class, class, class> friend class __tree;

template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator;

template <class> friend class _LIBCPP_TYPE_VIS_ONLY __map_iterator;

template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;

template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;

template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set;

template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset;

};

template <class _Tp, class _ConstNodePtr, class _DiffType>

class _LIBCPP_TYPE_VIS_ONLY __tree_const_iterator

{

typedef _ConstNodePtr __node_pointer;

typedef typename pointer_traits<__node_pointer>::element_type __node;

typedef 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() _NOEXCEPT

#if _LIBCPP_STD_VER > 11

: __ptr_(nullptr)

#endif

{}

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) _NOEXCEPT

: __ptr_(__p.__ptr_) {}

_LIBCPP_INLINE_VISIBILITY reference operator*() const {return __ptr_->__value_;}

_LIBCPP_INLINE_VISIBILITY pointer operator->() const

{return pointer_traits<pointer>::pointer_to(__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) _NOEXCEPT

: __ptr_(__p) {}

template <class, class, class> friend class __tree;

template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY map;

template <class, class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multimap;

template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY set;

template <class, class, class> friend class _LIBCPP_TYPE_VIS_ONLY multiset;

template <class> friend class _LIBCPP_TYPE_VIS_ONLY __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 typename __alloc_traits::void_pointer __void_pointer;

typedef __tree_node<value_type, __void_pointer> __node;

typedef __tree_node_base<__void_pointer> __node_base;

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::pointer __node_const_pointer;

typedef typename __node_base::pointer __node_base_pointer;

typedef typename __node_base::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<__end_node_t>

#else

rebind<__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() _NOEXCEPT

{

return static_cast<__node_pointer>

(

pointer_traits<__end_node_ptr>::pointer_to(__pair1_.first())

);

}

_LIBCPP_INLINE_VISIBILITY

__node_const_pointer __end_node() const _NOEXCEPT

{

return static_cast<__node_const_pointer>

(

pointer_traits<__end_node_const_ptr>::pointer_to(const_cast<__end_node_t&>(__pair1_.first()))

);

}

_LIBCPP_INLINE_VISIBILITY

__node_allocator& __node_alloc() _NOEXCEPT {return __pair1_.second();}

private:

_LIBCPP_INLINE_VISIBILITY

const __node_allocator& __node_alloc() const _NOEXCEPT

{return __pair1_.second();}

_LIBCPP_INLINE_VISIBILITY

__node_pointer& __begin_node() _NOEXCEPT {return __begin_node_;}

_LIBCPP_INLINE_VISIBILITY

const __node_pointer& __begin_node() const _NOEXCEPT {return __begin_node_;}

public:

_LIBCPP_INLINE_VISIBILITY

allocator_type __alloc() const _NOEXCEPT

{return allocator_type(__node_alloc());}

private:

_LIBCPP_INLINE_VISIBILITY

size_type& size() _NOEXCEPT {return __pair3_.first();}

public:

_LIBCPP_INLINE_VISIBILITY

const size_type& size() const _NOEXCEPT {return __pair3_.first();}

_LIBCPP_INLINE_VISIBILITY

value_compare& value_comp() _NOEXCEPT {return __pair3_.second();}

_LIBCPP_INLINE_VISIBILITY

const value_compare& value_comp() const _NOEXCEPT

{return __pair3_.second();}

public:

_LIBCPP_INLINE_VISIBILITY

__node_pointer __root() _NOEXCEPT

{return static_cast<__node_pointer> (__end_node()->__left_);}

_LIBCPP_INLINE_VISIBILITY

__node_const_pointer __root() const _NOEXCEPT

{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_pointer, difference_type> const_iterator;

explicit __tree(const value_compare& __comp)

_NOEXCEPT_(

is_nothrow_default_constructible<__node_allocator>::value &&

is_nothrow_copy_constructible<value_compare>::value);

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)

_NOEXCEPT_(

is_nothrow_move_constructible<__node_allocator>::value &&

is_nothrow_move_constructible<value_compare>::value);

__tree(__tree&& __t, const allocator_type& __a);

__tree& operator=(__tree&& __t)

_NOEXCEPT_(

__node_traits::propagate_on_container_move_assignment::value &&

is_nothrow_move_assignable<value_compare>::value &&

is_nothrow_move_assignable<__node_allocator>::value);

#endif // _LIBCPP_HAS_NO_RVALUE_REFERENCES

~__tree();

_LIBCPP_INLINE_VISIBILITY

iterator begin() _NOEXCEPT {return iterator(__begin_node());}

_LIBCPP_INLINE_VISIBILITY

const_iterator begin() const _NOEXCEPT {return const_iterator(__begin_node());}

_LIBCPP_INLINE_VISIBILITY

iterator end() _NOEXCEPT {return iterator(__end_node());}

_LIBCPP_INLINE_VISIBILITY

const_iterator end() const _NOEXCEPT {return const_iterator(__end_node());}

_LIBCPP_INLINE_VISIBILITY

size_type max_size() const _NOEXCEPT

{return __node_traits::max_size(__node_alloc());}

void clear() _NOEXCEPT;

void swap(__tree& __t)

_NOEXCEPT_(

__is_nothrow_swappable<value_compare>::value &&

(!__node_traits::propagate_on_container_swap::value ||

__is_nothrow_swappable<__node_allocator>::value));

#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 _Vp>

pair<iterator, bool> __insert_unique(_Vp&& __v);

template <class _Vp>

iterator __insert_unique(const_iterator __p, _Vp&& __v);

template <class _Vp>

iterator __insert_multi(_Vp&& __v);

template <class _Vp>

iterator __insert_multi(const_iterator __p, _Vp&& __v);

#endif // _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);

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>

_LIBCPP_INLINE_VISIBILITY