1169691Skan// -*- C++ -*- 2169691Skan 3169691Skan// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 4169691Skan// 5169691Skan// This file is part of the GNU ISO C++ Library. This library is free 6169691Skan// software; you can redistribute it and/or modify it under the terms 7169691Skan// of the GNU General Public License as published by the Free Software 8169691Skan// Foundation; either version 2, or (at your option) any later 9169691Skan// version. 10169691Skan 11169691Skan// This library is distributed in the hope that it will be useful, but 12169691Skan// WITHOUT ANY WARRANTY; without even the implied warranty of 13169691Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 14169691Skan// General Public License for more details. 15169691Skan 16169691Skan// You should have received a copy of the GNU General Public License 17169691Skan// along with this library; see the file COPYING. If not, write to 18169691Skan// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 19169691Skan// MA 02111-1307, USA. 20169691Skan 21169691Skan// As a special exception, you may use this file as part of a free 22169691Skan// software library without restriction. Specifically, if other files 23169691Skan// instantiate templates or use macros or inline functions from this 24169691Skan// file, or you compile this file and link it with other files to 25169691Skan// produce an executable, this file does not by itself cause the 26169691Skan// resulting executable to be covered by the GNU General Public 27169691Skan// License. This exception does not however invalidate any other 28169691Skan// reasons why the executable file might be covered by the GNU General 29169691Skan// Public License. 30169691Skan 31169691Skan// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 32169691Skan 33169691Skan// Permission to use, copy, modify, sell, and distribute this software 34169691Skan// is hereby granted without fee, provided that the above copyright 35169691Skan// notice appears in all copies, and that both that copyright notice 36169691Skan// and this permission notice appear in supporting documentation. None 37169691Skan// of the above authors, nor IBM Haifa Research Laboratories, make any 38169691Skan// representation about the suitability of this software for any 39169691Skan// purpose. It is provided "as is" without express or implied 40169691Skan// warranty. 41169691Skan 42169691Skan/** 43169691Skan * @file node_iterators.hpp 44169691Skan * Contains an implementation class for pat_trie_. 45169691Skan */ 46169691Skan 47169691Skan#ifndef PB_DS_PAT_TRIE_NODE_ITERATORS_HPP 48169691Skan#define PB_DS_PAT_TRIE_NODE_ITERATORS_HPP 49169691Skan 50169691Skan#include <debug/debug.h> 51169691Skan 52169691Skannamespace pb_ds 53169691Skan{ 54169691Skan namespace detail 55169691Skan { 56169691Skan 57169691Skan#define PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC \ 58169691Skan pat_trie_const_node_it_< \ 59169691Skan Node, \ 60169691Skan Leaf, \ 61169691Skan Head, \ 62169691Skan Internal_Node, \ 63169691Skan Const_Iterator, \ 64169691Skan Iterator, \ 65169691Skan E_Access_Traits, \ 66169691Skan Allocator> 67169691Skan 68169691Skan#define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \ 69169691Skan pat_trie_node_it_< \ 70169691Skan Node, \ 71169691Skan Leaf, \ 72169691Skan Head, \ 73169691Skan Internal_Node, \ 74169691Skan Const_Iterator, \ 75169691Skan Iterator, \ 76169691Skan E_Access_Traits, \ 77169691Skan Allocator> 78169691Skan 79169691Skan // Const node iterator. 80169691Skan template<typename Node, 81169691Skan class Leaf, 82169691Skan class Head, 83169691Skan class Internal_Node, 84169691Skan class Const_Iterator, 85169691Skan class Iterator, 86169691Skan class E_Access_Traits, 87169691Skan class Allocator> 88169691Skan class pat_trie_const_node_it_ 89169691Skan { 90169691Skan protected: 91169691Skan typedef 92169691Skan typename Allocator::template rebind< 93169691Skan Node>::other::pointer 94169691Skan node_pointer; 95169691Skan 96169691Skan typedef 97169691Skan typename Allocator::template rebind< 98169691Skan Leaf>::other::const_pointer 99169691Skan const_leaf_pointer; 100169691Skan 101169691Skan typedef 102169691Skan typename Allocator::template rebind< 103169691Skan Leaf>::other::pointer 104169691Skan leaf_pointer; 105169691Skan 106169691Skan typedef 107169691Skan typename Allocator::template rebind< 108169691Skan Internal_Node>::other::pointer 109169691Skan internal_node_pointer; 110169691Skan 111169691Skan typedef 112169691Skan typename Allocator::template rebind< 113169691Skan Internal_Node>::other::const_pointer 114169691Skan const_internal_node_pointer; 115169691Skan 116169691Skan typedef 117169691Skan typename Allocator::template rebind< 118169691Skan E_Access_Traits>::other::const_pointer 119169691Skan const_e_access_traits_pointer; 120169691Skan 121169691Skan private: 122169691Skan inline typename E_Access_Traits::const_iterator 123169691Skan pref_begin() const 124169691Skan { 125169691Skan if (m_p_nd->m_type == pat_trie_leaf_node_type) 126169691Skan return (m_p_traits->begin( 127169691Skan m_p_traits->extract_key( 128169691Skan static_cast<const_leaf_pointer>(m_p_nd)->value()))); 129169691Skan 130169691Skan _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); 131169691Skan 132169691Skan return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_b_it()); 133169691Skan } 134169691Skan 135169691Skan inline typename E_Access_Traits::const_iterator 136169691Skan pref_end() const 137169691Skan { 138169691Skan if (m_p_nd->m_type == pat_trie_leaf_node_type) 139169691Skan return (m_p_traits->end( 140169691Skan m_p_traits->extract_key( 141169691Skan static_cast<const_leaf_pointer>(m_p_nd)->value()))); 142169691Skan 143169691Skan _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); 144169691Skan 145169691Skan return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_e_it()); 146169691Skan } 147169691Skan 148169691Skan public: 149169691Skan 150169691Skan // Size type. 151169691Skan typedef typename Allocator::size_type size_type; 152169691Skan 153169691Skan // Category. 154169691Skan typedef trivial_iterator_tag iterator_category; 155169691Skan 156169691Skan // Difference type. 157169691Skan typedef trivial_iterator_difference_type difference_type; 158169691Skan 159169691Skan // __Iterator's value type. 160169691Skan typedef Const_Iterator value_type; 161169691Skan 162169691Skan // __Iterator's reference type. 163169691Skan typedef value_type reference; 164169691Skan 165169691Skan // __Iterator's __const reference type. 166169691Skan typedef value_type const_reference; 167169691Skan 168169691Skan // Element access traits. 169169691Skan typedef E_Access_Traits e_access_traits; 170169691Skan 171169691Skan // A key's element __const iterator. 172169691Skan typedef typename e_access_traits::const_iterator const_e_iterator; 173169691Skan 174169691Skan // Metadata type. 175169691Skan typedef typename Node::metadata_type metadata_type; 176169691Skan 177169691Skan // Const metadata reference type. 178169691Skan typedef 179169691Skan typename Allocator::template rebind< 180169691Skan metadata_type>::other::const_reference 181169691Skan const_metadata_reference; 182169691Skan 183169691Skan // Default constructor. 184169691Skan /* 185169691Skan inline 186169691Skan pat_trie_const_node_it_() 187169691Skan */ 188169691Skan inline 189169691Skan pat_trie_const_node_it_(node_pointer p_nd = NULL, 190169691Skan const_e_access_traits_pointer p_traits = NULL) 191169691Skan : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits) 192169691Skan { } 193169691Skan 194169691Skan // Subtree valid prefix. 195169691Skan inline std::pair<const_e_iterator, const_e_iterator> 196169691Skan valid_prefix() const 197169691Skan { return std::make_pair(pref_begin(), pref_end()); } 198169691Skan 199169691Skan // Const access; returns the __const iterator* associated with 200169691Skan // the current leaf. 201169691Skan inline const_reference 202169691Skan operator*() const 203169691Skan { 204169691Skan _GLIBCXX_DEBUG_ASSERT(num_children() == 0); 205169691Skan return Const_Iterator(m_p_nd); 206169691Skan } 207169691Skan 208169691Skan // Metadata access. 209169691Skan inline const_metadata_reference 210169691Skan get_metadata() const 211169691Skan { return m_p_nd->get_metadata(); } 212169691Skan 213169691Skan // Returns the number of children in the corresponding node. 214169691Skan inline size_type 215169691Skan num_children() const 216169691Skan { 217169691Skan if (m_p_nd->m_type == pat_trie_leaf_node_type) 218169691Skan return 0; 219169691Skan _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); 220169691Skan return std::distance(static_cast<internal_node_pointer>(m_p_nd)->begin(), static_cast<internal_node_pointer>(m_p_nd)->end()); 221169691Skan } 222169691Skan 223169691Skan // Returns a __const node __iterator to the corresponding node's 224169691Skan // i-th child. 225169691Skan PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC 226169691Skan get_child(size_type i) const 227169691Skan { 228169691Skan _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); 229169691Skan typename Internal_Node::iterator it = 230169691Skan static_cast<internal_node_pointer>(m_p_nd)->begin(); 231169691Skan 232169691Skan std::advance(it, i); 233169691Skan return PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC(*it, m_p_traits); 234169691Skan } 235169691Skan 236169691Skan // Compares content to a different iterator object. 237169691Skan inline bool 238169691Skan operator==(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const 239169691Skan { return (m_p_nd == other.m_p_nd); } 240169691Skan 241169691Skan // Compares content (negatively) to a different iterator object. 242169691Skan inline bool 243169691Skan operator!=(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const 244169691Skan { return m_p_nd != other.m_p_nd; } 245169691Skan 246169691Skan private: 247169691Skan 248169691Skan friend class PB_DS_CLASS_C_DEC; 249169691Skan 250169691Skan public: 251169691Skan node_pointer m_p_nd; 252169691Skan 253169691Skan const_e_access_traits_pointer m_p_traits; 254169691Skan }; 255169691Skan 256169691Skan // Node iterator. 257169691Skan template<typename Node, 258169691Skan class Leaf, 259169691Skan class Head, 260169691Skan class Internal_Node, 261169691Skan class Const_Iterator, 262169691Skan class Iterator, 263169691Skan class E_Access_Traits, 264169691Skan class Allocator> 265169691Skan class pat_trie_node_it_ : 266169691Skan public PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC 267169691Skan 268169691Skan { 269169691Skan private: 270169691Skan typedef 271169691Skan typename Allocator::template rebind< 272169691Skan Node>::other::pointer 273169691Skan node_pointer; 274169691Skan 275169691Skan typedef Iterator iterator; 276169691Skan 277169691Skan typedef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC base_type; 278169691Skan 279169691Skan typedef 280169691Skan typename base_type::const_e_access_traits_pointer 281169691Skan const_e_access_traits_pointer; 282169691Skan 283169691Skan typedef typename base_type::internal_node_pointer internal_node_pointer; 284169691Skan 285169691Skan public: 286169691Skan 287169691Skan // Size type. 288169691Skan typedef 289169691Skan typename PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC::size_type 290169691Skan size_type; 291169691Skan 292169691Skan // __Iterator's value type. 293169691Skan typedef Iterator value_type; 294169691Skan 295169691Skan // __Iterator's reference type. 296169691Skan typedef value_type reference; 297169691Skan 298169691Skan // __Iterator's __const reference type. 299169691Skan typedef value_type const_reference; 300169691Skan 301169691Skan // Default constructor. 302169691Skan /* 303169691Skan inline 304169691Skan pat_trie_node_it_() ; 305169691Skan */ 306169691Skan 307169691Skan inline 308169691Skan pat_trie_node_it_(node_pointer p_nd = NULL, const_e_access_traits_pointer p_traits = NULL) : base_type(p_nd, p_traits) 309169691Skan { } 310169691Skan 311169691Skan // Access; returns the iterator* associated with the current leaf. 312169691Skan inline reference 313169691Skan operator*() const 314169691Skan { 315169691Skan _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0); 316169691Skan return Iterator(base_type::m_p_nd); 317169691Skan 318169691Skan } 319169691Skan 320169691Skan // Returns a node __iterator to the corresponding node's i-th child. 321169691Skan PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC 322169691Skan get_child(size_type i) const 323169691Skan { 324169691Skan _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == pat_trie_internal_node_type); 325169691Skan 326169691Skan typename Internal_Node::iterator it = 327169691Skan static_cast<internal_node_pointer>(base_type::m_p_nd)->begin(); 328169691Skan 329169691Skan std::advance(it, i); 330169691Skan return PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC(*it, base_type::m_p_traits); 331169691Skan } 332169691Skan 333169691Skan private: 334169691Skan friend class PB_DS_CLASS_C_DEC; 335169691Skan }; 336169691Skan 337169691Skan#undef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC 338169691Skan#undef PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC 339169691Skan 340169691Skan } // namespace detail 341169691Skan} // namespace pb_ds 342169691Skan 343169691Skan#endif 344169691Skan 345