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 pat_trie_/pat_trie_.hpp 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Contains an implementation class for a patricia tree. 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <iterator> 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <utility> 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <algorithm> 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <functional> 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <assert.h> 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <list> 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/exception.hpp> 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/tag_and_trait.hpp> 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/tree_policy.hpp> 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/cond_dealtor.hpp> 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/type_utils.hpp> 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/types_traits.hpp> 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp> 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp> 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/debug_map_base.hpp> 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <debug/debug.h> 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __gnu_pbds 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert namespace detail 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_TRUE_INDICATOR 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_PAT_TRIE_NAME pat_trie_map 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_FALSE_INDICATOR 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_PAT_TRIE_NAME pat_trie_set 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_CLASS_T_DEC \ 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Key, typename Mapped, typename Node_And_It_Traits, \ 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Alloc> 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_CLASS_C_DEC \ 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_PAT_TRIE_NAME<Key, Mapped, Node_And_It_Traits, _Alloc> 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_PAT_TRIE_TRAITS_BASE \ 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert types_traits<Key, Mapped, _Alloc, false> 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_DEBUG_MAP_BASE_C_DEC \ 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert debug_map_base<Key, eq_by_less<Key, std::less<Key> >, \ 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Alloc::template rebind<Key>::other::const_reference> 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /** 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @brief PATRICIA trie. 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * @ingroup branch-detail 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This implementation loosely borrows ideas from: 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 1) Fast Mergeable Integer Maps, Okasaki, Gill 1998 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 2) Ptset: Sets of integers implemented as Patricia trees, 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Jean-Christophe Filliatr, 2000 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Key, typename Mapped, typename Node_And_It_Traits, 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename _Alloc> 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class PB_DS_PAT_TRIE_NAME : 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public PB_DS_DEBUG_MAP_BASE_C_DEC, 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public Node_And_It_Traits::synth_access_traits, 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public Node_And_It_Traits::node_update, 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public PB_DS_PAT_TRIE_TRAITS_BASE, 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public pat_trie_base 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef pat_trie_base base_type; 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef PB_DS_PAT_TRIE_TRAITS_BASE traits_base; 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef Node_And_It_Traits traits_type; 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::synth_access_traits synth_access_traits; 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename synth_access_traits::const_iterator a_const_iterator; 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::node node; 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::template rebind<node> __rebind_n; 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename __rebind_n::other::const_pointer node_const_pointer; 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename __rebind_n::other::pointer node_pointer; 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::head head; 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::template rebind<head> __rebind_h; 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename __rebind_h::other head_allocator; 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename head_allocator::pointer head_pointer; 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::leaf leaf; 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::template rebind<leaf> __rebind_l; 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename __rebind_l::other leaf_allocator; 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename leaf_allocator::pointer leaf_pointer; 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename leaf_allocator::const_pointer leaf_const_pointer; 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::inode inode; 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename inode::iterator inode_iterator; 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::template rebind<inode> __rebind_in; 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename __rebind_in::other __rebind_ina; 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename __rebind_in::other inode_allocator; 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename __rebind_ina::pointer inode_pointer; 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename __rebind_ina::const_pointer inode_const_pointer; 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Conditional deallocator. 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class cond_dealtor 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert protected: 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert leaf_pointer m_p_nd; 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool m_no_action_dtor; 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool m_call_destructor; 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert cond_dealtor(leaf_pointer p_nd) 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : m_p_nd(p_nd), m_no_action_dtor(false), m_call_destructor(false) 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { } 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set_no_action_dtor() 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { m_no_action_dtor = true; } 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert set_call_destructor() 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { m_call_destructor = true; } 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~cond_dealtor() 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (m_no_action_dtor) 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (m_call_destructor) 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert m_p_nd->~leaf(); 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert s_leaf_allocator.deallocate(m_p_nd, 1); 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Branch bag, for split-join. 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class branch_bag 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef inode_pointer __inp; 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::template rebind<__inp>::other __rebind_inp; 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef std::_GLIBCXX_STD_C::list<__inp, __rebind_inp> bag_type; 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef std::list<__inp, __rebind_inp> bag_type; 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bag_type m_bag; 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert add_branch() 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inode_pointer p_nd = s_inode_allocator.allocate(1); 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert m_bag.push_back(p_nd); 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert s_inode_allocator.deallocate(p_nd, 1); 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inode_pointer 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert get_branch() 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_DEBUG_ASSERT(!m_bag.empty()); 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inode_pointer p_nd = *m_bag.begin(); 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert m_bag.pop_front(); 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return p_nd; 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~branch_bag() 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (!m_bag.empty()) 21911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 22011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inode_pointer p_nd = *m_bag.begin(); 22111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert s_inode_allocator.deallocate(p_nd, 1); 22211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert m_bag.pop_front(); 22311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 22411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 22511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 22611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline bool 22711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert empty() const 22811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return m_bag.empty(); } 22911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 23011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 23211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; 23311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 23411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::null_node_update_pointer null_node_update_pointer; 23611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 23711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 23811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef pat_trie_tag container_category; 23911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef _Alloc allocator_type; 24011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::size_type size_type; 24111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Alloc::difference_type difference_type; 24211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 24311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_type key_type; 24411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_pointer key_pointer; 24511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_const_pointer key_const_pointer; 24611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_reference key_reference; 24711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::key_const_reference key_const_reference; 24811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_type mapped_type; 24911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_pointer mapped_pointer; 25011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_const_pointer mapped_const_pointer; 25111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_reference mapped_reference; 25211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::mapped_const_reference mapped_const_reference; 25311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::value_type value_type; 25411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::pointer pointer; 25511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::const_pointer const_pointer; 25611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::reference reference; 25711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_base::const_reference const_reference; 25811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::access_traits access_traits; 26011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::const_iterator point_const_iterator; 26111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::iterator point_iterator; 26211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef point_const_iterator const_iterator; 26311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef point_iterator iterator; 26411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 26511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::reverse_iterator reverse_iterator; 26611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::const_reverse_iterator const_reverse_iterator; 26711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::node_const_iterator node_const_iterator; 26811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::node_iterator node_iterator; 26911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename traits_type::node_update node_update; 27011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_PAT_TRIE_NAME(); 27211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_PAT_TRIE_NAME(const access_traits&); 27411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_PAT_TRIE_NAME(const PB_DS_CLASS_C_DEC&); 27611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 27811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert swap(PB_DS_CLASS_C_DEC&); 27911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~PB_DS_PAT_TRIE_NAME(); 28111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline bool 28311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert empty() const; 28411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline size_type 28611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size() const; 28711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 28811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline size_type 28911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert max_size() const; 29011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert access_traits& 29211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert get_access_traits(); 29311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const access_traits& 29511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert get_access_traits() const; 29611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_update& 29811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert get_node_update(); 29911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const node_update& 30111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert get_node_update() const; 30211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline std::pair<point_iterator, bool> 30411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert(const_reference); 30511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline mapped_reference 30711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator[](key_const_reference r_key) 30811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 30911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_TRUE_INDICATOR 31011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return insert(std::make_pair(r_key, mapped_type())).first->second; 31111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 31211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert(r_key); 31311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return traits_base::s_null_type; 31411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 31511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 31611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_iterator 31811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(key_const_reference); 31911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_const_iterator 32111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(key_const_reference) const; 32211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_iterator 32411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert lower_bound(key_const_reference); 32511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_const_iterator 32711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert lower_bound(key_const_reference) const; 32811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_iterator 33011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert upper_bound(key_const_reference); 33111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline point_const_iterator 33311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert upper_bound(key_const_reference) const; 33411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 33611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert clear(); 33711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline bool 33911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(key_const_reference); 34011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 34111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const_iterator 34211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(const_iterator); 34311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 34411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_TRUE_INDICATOR 34511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline iterator 34611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(iterator); 34711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 34811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 34911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const_reverse_iterator 35011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(const_reverse_iterator); 35111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_DATA_TRUE_INDICATOR 35311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline reverse_iterator 35411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase(reverse_iterator); 35511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 35611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Pred> 35811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline size_type 35911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase_if(Pred); 36011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 36211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert join(PB_DS_CLASS_C_DEC&); 36311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 36511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert split(key_const_reference, PB_DS_CLASS_C_DEC&); 36611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline iterator 36811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert begin(); 36911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const_iterator 37111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert begin() const; 37211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline iterator 37411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert end(); 37511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const_iterator 37711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert end() const; 37811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 37911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline reverse_iterator 38011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rbegin(); 38111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const_reverse_iterator 38311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rbegin() const; 38411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline reverse_iterator 38611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rend(); 38711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 38811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline const_reverse_iterator 38911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rend() const; 39011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Returns a const node_iterator corresponding to the node at the 39211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// root of the tree. 39311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_const_iterator 39411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_begin() const; 39511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 39611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Returns a node_iterator corresponding to the node at the 39711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// root of the tree. 39811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_iterator 39911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_begin(); 40011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Returns a const node_iterator corresponding to a node just 40211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// after a leaf of the tree. 40311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_const_iterator 40411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_end() const; 40511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 40611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// Returns a node_iterator corresponding to a node just 40711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /// after a leaf of the tree. 40811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_iterator 40911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_end(); 41011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_PAT_TRIE_TRACE_ 41211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 41311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert trace() const; 41411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 41511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert protected: 41711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename It> 41811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 41911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert copy_from_range(It, It); 42011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 42111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 42211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert value_swap(PB_DS_CLASS_C_DEC&); 42311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 42411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_pointer 42511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert recursive_copy_node(node_const_pointer); 42611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 42711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 42811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 42911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert initialize(); 43011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 43111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 43211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert apply_update(node_pointer, null_node_update_pointer); 43311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 43411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Node_Update_> 43511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 43611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert apply_update(node_pointer, Node_Update_*); 43711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 43811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 43911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert join_prep(PB_DS_CLASS_C_DEC&, branch_bag&); 44011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 44111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 44211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rec_join_prep(node_const_pointer, node_const_pointer, branch_bag&); 44311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 44411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 44511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rec_join_prep(leaf_const_pointer, leaf_const_pointer, branch_bag&); 44611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 44711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 44811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rec_join_prep(leaf_const_pointer, inode_const_pointer, branch_bag&); 44911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 45011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 45111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rec_join_prep(inode_const_pointer, leaf_const_pointer, branch_bag&); 45211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 45311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 45411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rec_join_prep(inode_const_pointer, inode_const_pointer, branch_bag&); 45511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 45611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_pointer 45711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rec_join(node_pointer, node_pointer, size_type, branch_bag&); 45811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 45911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_pointer 46011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rec_join(leaf_pointer, leaf_pointer, branch_bag&); 46111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 46211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_pointer 46311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rec_join(leaf_pointer, inode_pointer, size_type, branch_bag&); 46411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 46511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_pointer 46611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rec_join(inode_pointer, leaf_pointer, size_type, branch_bag&); 46711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 46811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_pointer 46911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rec_join(inode_pointer, inode_pointer, branch_bag&); 47011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 47111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type 47211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert keys_diff_ind(typename access_traits::const_iterator, 47311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename access_traits::const_iterator, 47411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename access_traits::const_iterator, 47511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename access_traits::const_iterator); 47611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 47711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inode_pointer 47811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert insert_branch(node_pointer, node_pointer, branch_bag&); 47911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 48011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 48111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert update_min_max_for_inserted_leaf(leaf_pointer); 48211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 48311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 48411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase_leaf(leaf_pointer); 48511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 48611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 48711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert actual_erase_leaf(leaf_pointer); 48811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 48911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 49011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert clear_imp(node_pointer); 49111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 49211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 49311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert erase_fixup(inode_pointer); 49411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 49511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 49611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert update_min_max_for_erased_leaf(leaf_pointer); 49711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 49811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static inline a_const_iterator 49911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pref_begin(node_const_pointer); 50011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 50111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static inline a_const_iterator 50211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert pref_end(node_const_pointer); 50311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 50411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_pointer 50511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find_imp(key_const_reference); 50611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 50711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_pointer 50811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert lower_bound_imp(key_const_reference); 50911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 51011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline node_pointer 51111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert upper_bound_imp(key_const_reference); 51211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 51311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline static leaf_const_pointer 51411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert leftmost_descendant(node_const_pointer); 51511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 51611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline static leaf_pointer 51711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert leftmost_descendant(node_pointer); 51811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 51911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline static leaf_const_pointer 52011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rightmost_descendant(node_const_pointer); 52111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 52211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline static leaf_pointer 52311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rightmost_descendant(node_pointer); 52411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 52511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef _GLIBCXX_DEBUG 52611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 52711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_valid(const char*, int) const; 52811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 52911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 53011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_iterators(const char*, int) const; 53111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 53211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 53311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert assert_reverse_iterators(const char*, int) const; 53411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 53511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static size_type 53611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert recursive_count_leafs(node_const_pointer, const char*, int); 53711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 53811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 53911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef PB_DS_PAT_TRIE_TRACE_ 54011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static void 54111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert trace_node(node_const_pointer, size_type); 54211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 54311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<typename Metadata_> 54411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static void 54511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert trace_node_metadata(node_const_pointer, type_to_type<Metadata_>); 54611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 54711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static void 54811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert trace_node_metadata(node_const_pointer, type_to_type<null_type>); 54911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 55011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 55111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert leaf_pointer 55211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert split_prep(key_const_reference, PB_DS_CLASS_C_DEC&, branch_bag&); 55311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 55411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert node_pointer 55511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rec_split(node_pointer, a_const_iterator, a_const_iterator, 55611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert PB_DS_CLASS_C_DEC&, branch_bag&); 55711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 55811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 55911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert split_insert_branch(size_type, a_const_iterator, inode_iterator, 56011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type, branch_bag&); 56111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 56211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static head_allocator s_head_allocator; 56311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static inode_allocator s_inode_allocator; 56411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert static leaf_allocator s_leaf_allocator; 56511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 56611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert head_pointer m_p_head; 56711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type m_size; 56811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 56911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 57011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_ASSERT_NODE_VALID(X) \ 57111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);) 57211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 57311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#define PB_DS_RECURSIVE_COUNT_LEAFS(X) \ 57411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert recursive_count_leafs(X, __FILE__, __LINE__) 57511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 57611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp> 57711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp> 57811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp> 57911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp> 58011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp> 58111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp> 58211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp> 58311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp> 58411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp> 58511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp> 58611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp> 58711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 58811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_RECURSIVE_COUNT_LEAFS 58911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_ASSERT_NODE_VALID 59011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_CLASS_C_DEC 59111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_CLASS_T_DEC 59211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_PAT_TRIE_NAME 59311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_PAT_TRIE_TRAITS_BASE 59411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#undef PB_DS_DEBUG_MAP_BASE_C_DEC 59511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } // namespace detail 59611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // namespace __gnu_pbds 597