111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2005-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the terms 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the GNU General Public License as published by the Free Software 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Foundation; either version 3, or (at your option) any later 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, but 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License and 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// a copy of the GCC Runtime Library Exception along with this program; 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Permission to use, copy, modify, sell, and distribute this software 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// is hereby granted without fee, provided that the above copyright 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// notice appears in all copies, and that both that copyright notice 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// and this permission notice appear in supporting documentation. None 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// of the above authors, nor IBM Haifa Research Laboratories, make any 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// representation about the suitability of this software for any 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// purpose. It is provided "as is" without express or implied 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// warranty. 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @file bin_search_tree_/bin_search_tree_.hpp 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Contains an implementation class for binary search tree. 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/exception.hpp> 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/tree_policy.hpp> 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/types_traits.hpp> 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/cond_dealtor.hpp> 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/type_utils.hpp> 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/tree_trace_base.hpp> 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/debug_map_base.hpp> 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <utility> 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <functional> 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <debug/debug.h> 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __gnu_pbds 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert namespace detail 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_TRUE_INDICATOR 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_BIN_TREE_NAME bin_search_tree_map 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_FALSE_INDICATOR 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_BIN_TREE_NAME bin_search_tree_set 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_CLASS_T_DEC \ 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Key, typename Mapped, typename Cmp_Fn, \ 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename Node_And_It_Traits, typename _Alloc> 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_CLASS_C_DEC \ 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_BIN_TREE_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, _Alloc> 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_BIN_TREE_TRAITS_BASE \ 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert types_traits<Key, Mapped, _Alloc, false> 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_DEBUG_MAP_BASE_C_DEC \ 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \ 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Alloc::template rebind<Key>::other::const_reference> 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_TREE_TRACE 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_TREE_TRACE_BASE_C_DEC \ 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert tree_trace_base<typename Node_And_It_Traits::node_const_iterator, \ 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename Node_And_It_Traits::node_iterator, \ 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Cmp_Fn, true, _Alloc> 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief Binary search tree (BST). 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This implementation uses an idea from the SGI STL (using a @a 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * header node which is needed for efficient iteration). 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Key, typename Mapped, typename Cmp_Fn, 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename Node_And_It_Traits, typename _Alloc> 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class PB_DS_BIN_TREE_NAME : 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public PB_DS_DEBUG_MAP_BASE_C_DEC, 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_TREE_TRACE 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public PB_DS_TREE_TRACE_BASE_C_DEC, 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public Cmp_Fn, 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public PB_DS_BIN_TREE_TRAITS_BASE, 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public Node_And_It_Traits::node_update 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef Node_And_It_Traits traits_type; 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert protected: 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef PB_DS_BIN_TREE_TRAITS_BASE traits_base; 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Alloc::template rebind<typename traits_type::node>::other 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_allocator; 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename node_allocator::value_type node; 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename node_allocator::pointer node_pointer; 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::null_node_update_pointer 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert null_node_update_pointer; 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef cond_dealtor<node, _Alloc> cond_dealtor_t; 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::size_type size_type; 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::difference_type difference_type; 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_type key_type; 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_pointer key_pointer; 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_const_pointer key_const_pointer; 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_reference key_reference; 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_const_reference key_const_reference; 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_TRUE_INDICATOR 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_type mapped_type; 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_pointer mapped_pointer; 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_reference mapped_reference; 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_const_reference mapped_const_reference; 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::value_type value_type; 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::pointer pointer; 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::const_pointer const_pointer; 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::reference reference; 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::const_reference const_reference; 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::point_const_iterator point_const_iterator; 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef point_const_iterator const_iterator; 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::point_iterator point_iterator; 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef point_iterator iterator; 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::const_reverse_iterator const_reverse_iterator; 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::reverse_iterator reverse_iterator; 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::node_const_iterator node_const_iterator; 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::node_iterator node_iterator; 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::node_update node_update; 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef Cmp_Fn cmp_fn; 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Alloc allocator_type; 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_BIN_TREE_NAME(); 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_BIN_TREE_NAME(const Cmp_Fn&); 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_BIN_TREE_NAME(const Cmp_Fn&, const node_update&); 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_BIN_TREE_NAME(const PB_DS_CLASS_C_DEC&); 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert swap(PB_DS_CLASS_C_DEC&); 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~PB_DS_BIN_TREE_NAME(); 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline bool 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert empty() const; 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline size_type 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size() const; 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline size_type 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert max_size() const; 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert Cmp_Fn& 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert get_cmp_fn(); 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const Cmp_Fn& 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert get_cmp_fn() const; 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_iterator 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert lower_bound(key_const_reference); 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_const_iterator 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert lower_bound(key_const_reference) const; 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_iterator 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert upper_bound(key_const_reference); 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_const_iterator 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert upper_bound(key_const_reference) const; 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_iterator 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(key_const_reference); 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_const_iterator 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(key_const_reference) const; 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline iterator 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert begin(); 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const_iterator 22011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert begin() const; 22111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline iterator 22311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert end(); 22411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const_iterator 22611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert end() const; 22711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline reverse_iterator 22911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rbegin(); 23011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const_reverse_iterator 23211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rbegin() const; 23311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline reverse_iterator 23511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rend(); 23611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const_reverse_iterator 23811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rend() const; 23911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Returns a const node_iterator corresponding to the node at the 24111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// root of the tree. 24211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_const_iterator 24311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_begin() const; 24411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Returns a node_iterator corresponding to the node at the 24611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// root of the tree. 24711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_iterator 24811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_begin(); 24911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Returns a const node_iterator corresponding to a node just 25111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// after a leaf of the tree. 25211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_const_iterator 25311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_end() const; 25411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Returns a node_iterator corresponding to a node just 25611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// after a leaf of the tree. 25711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_iterator 25811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_end(); 25911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 26111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert clear(); 26211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert protected: 26411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 26511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_swap(PB_DS_CLASS_C_DEC&); 26611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 26811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert initialize_min_max(); 26911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline iterator 27111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert_imp_empty(const_reference); 27211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline iterator 27411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert_leaf_new(const_reference, node_pointer, bool); 27511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_pointer 27711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert get_new_node_for_leaf_insert(const_reference, false_type); 27811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_pointer 28011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert get_new_node_for_leaf_insert(const_reference, true_type); 28111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 28311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert actual_erase_node(node_pointer); 28411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline std::pair<node_pointer, bool> 28611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(node_pointer); 28711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 28911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert update_min_max_for_erased_node(node_pointer); 29011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static void 29211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert clear_imp(node_pointer); 29311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline std::pair<point_iterator, bool> 29511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert_leaf(const_reference); 29611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 29811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rotate_left(node_pointer); 29911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 30111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rotate_right(node_pointer); 30211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 30411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rotate_parent(node_pointer); 30511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 30711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert apply_update(node_pointer, null_node_update_pointer); 30811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Node_Update_> 31011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 31111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert apply_update(node_pointer, Node_Update_*); 31211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 31411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert update_to_top(node_pointer, null_node_update_pointer); 31511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Node_Update_> 31711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 31811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert update_to_top(node_pointer, Node_Update_*); 31911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 32111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert join_prep(PB_DS_CLASS_C_DEC&); 32211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 32411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert join_finish(PB_DS_CLASS_C_DEC&); 32511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 32711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert split_prep(key_const_reference, PB_DS_CLASS_C_DEC&); 32811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 33011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert split_finish(PB_DS_CLASS_C_DEC&); 33111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type 33311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert recursive_count(node_pointer) const; 33411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 33611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 33711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_valid(const char*, int) const; 33811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 34011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert structure_only_assert_valid(const char*, int) const; 34111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 34211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 34311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_node_consistent(const node_pointer, const char*, int) const; 34411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 34511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 34611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 34711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 34811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 34911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_iterators(const char*, int) const; 35011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 35211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_consistent_with_debug_base(const char*, int) const; 35311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 35511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_node_consistent_with_left(const node_pointer, 35611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const char*, int) const; 35711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 35911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_node_consistent_with_right(const node_pointer, 36011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const char*, int) const; 36111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 36311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_consistent_with_debug_base(const node_pointer, 36411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const char*, int) const; 36511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 36711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_min(const char*, int) const; 36811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 37011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_min_imp(const node_pointer, const char*, int) const; 37111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 37311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_max(const char*, int) const; 37411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 37611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_max_imp(const node_pointer, const char*, int) const; 37711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 37911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_size(const char*, int) const; 38011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef std::pair<const_pointer, const_pointer> node_consistent_t; 38211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_consistent_t 38411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_node_consistent_(const node_pointer, const char*, int) const; 38511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 38611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 38811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert initialize(); 38911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_pointer 39111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert recursive_copy_node(const node_pointer); 39211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert protected: 39411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_pointer m_p_head; 39511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type m_size; 39611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static node_allocator s_node_allocator; 39711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 39811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_STRUCT_ONLY_ASSERT_VALID(X) \ 40011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_DEBUG_ONLY(X.structure_only_assert_valid(__FILE__, __LINE__);) 40111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_ASSERT_NODE_CONSISTENT(_Node) \ 40311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_DEBUG_ONLY(assert_node_consistent(_Node, __FILE__, __LINE__);) 40411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp> 40611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp> 40711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp> 40811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp> 40911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp> 41011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp> 41111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp> 41211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp> 41311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp> 41411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp> 41511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_ASSERT_NODE_CONSISTENT 41711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_STRUCT_ONLY_ASSERT_VALID 41811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_CLASS_C_DEC 41911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_CLASS_T_DEC 42011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_BIN_TREE_NAME 42111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_BIN_TREE_TRAITS_BASE 42211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_DEBUG_MAP_BASE_C_DEC 42311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 42411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_TREE_TRACE 42511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_TREE_TRACE_BASE_C_DEC 42611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 42711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } // namespace detail 42811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // namespace __gnu_pbds 429