libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26
  27 // Permission to use, copy, modify, sell, and distribute this software
  28 // is hereby granted without fee, provided that the above copyright
  29 // notice appears in all copies, and that both that copyright notice
  30 // and this permission notice appear in supporting documentation. None
  31 // of the above authors, nor IBM Haifa Research Laboratories, make any
  32 // representation about the suitability of this software for any
  33 // purpose. It is provided "as is" without express or implied
  34 // warranty.
  35
  36 /**
  37  * @file node_iterators.hpp
  38  * Contains an implementation class for pat_trie_.
  39  */
  40
  41 #ifndef PB_DS_PAT_TRIE_NODE_ITERATORS_HPP
  42 #define PB_DS_PAT_TRIE_NODE_ITERATORS_HPP
  43
  44 #include <debug/debug.h>
  45
  46 namespace __gnu_pbds
  47 {
  48   namespace detail
  49   {
  50
  51 #define PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC                        \
  52     pat_trie_const_node_it_<                                            \
  53                                                         Node,           \
  54                                                         Leaf,           \
  55                                                         Head,           \
  56                                                         Internal_Node,  \
  57                                                         Const_Iterator, \
  58                                                         Iterator,       \
  59                                                         E_Access_Traits, \
  60                                                         Allocator>
  61
  62 #define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC                      \
  63     pat_trie_node_it_<                                          \
  64                                         Node,                   \
  65                                         Leaf,                   \
  66                                         Head,                   \
  67                                         Internal_Node,          \
  68                                         Const_Iterator,         \
  69                                         Iterator,               \
  70                                         E_Access_Traits,        \
  71                                         Allocator>
  72
  73     // Const node iterator.
  74     template<typename Node,
  75              class Leaf,
  76              class Head,
  77              class Internal_Node,
  78              class Const_Iterator,
  79              class Iterator,
  80              class E_Access_Traits,
  81              class Allocator>
  82     class pat_trie_const_node_it_
  83     {
  84     protected:
  85       typedef
  86       typename Allocator::template rebind<
  87       Node>::other::pointer
  88       node_pointer;
  89
  90       typedef
  91       typename Allocator::template rebind<
  92         Leaf>::other::const_pointer
  93       const_leaf_pointer;
  94
  95       typedef
  96       typename Allocator::template rebind<
  97         Leaf>::other::pointer
  98       leaf_pointer;
  99
 100       typedef
 101       typename Allocator::template rebind<
 102         Internal_Node>::other::pointer
 103       internal_node_pointer;
 104
 105       typedef
 106       typename Allocator::template rebind<
 107         Internal_Node>::other::const_pointer
 108       const_internal_node_pointer;
 109
 110       typedef
 111       typename Allocator::template rebind<
 112         E_Access_Traits>::other::const_pointer
 113       const_e_access_traits_pointer;
 114
 115     private:
 116       inline typename E_Access_Traits::const_iterator
 117       pref_begin() const
 118       {
 119         if (m_p_nd->m_type == pat_trie_leaf_node_type)
 120           return (m_p_traits->begin(
 121                                     m_p_traits->extract_key(
 122                                                             static_cast<const_leaf_pointer>(m_p_nd)->value())));
 123
 124         _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
 125
 126         return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_b_it());
 127       }
 128
 129       inline typename E_Access_Traits::const_iterator
 130       pref_end() const
 131       {
 132         if (m_p_nd->m_type == pat_trie_leaf_node_type)
 133           return (m_p_traits->end(
 134                                   m_p_traits->extract_key(
 135                                                           static_cast<const_leaf_pointer>(m_p_nd)->value())));
 136
 137         _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
 138
 139         return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_e_it());
 140       }
 141
 142     public:
 143
 144       // Size type.
 145       typedef typename Allocator::size_type size_type;
 146
 147       // Category.
 148       typedef trivial_iterator_tag iterator_category;
 149
 150       // Difference type.
 151       typedef trivial_iterator_difference_type difference_type;
 152
 153       // __Iterator's value type.
 154       typedef Const_Iterator value_type;
 155
 156       // __Iterator's reference type.
 157       typedef value_type reference;
 158
 159       // __Iterator's __const reference type.
 160       typedef value_type const_reference;
 161
 162       // Element access traits.
 163       typedef E_Access_Traits e_access_traits;
 164
 165       // A key's element __const iterator.
 166       typedef typename e_access_traits::const_iterator const_e_iterator;
 167
 168       // Metadata type.
 169       typedef typename Node::metadata_type metadata_type;
 170
 171       // Const metadata reference type.
 172       typedef
 173       typename Allocator::template rebind<
 174         metadata_type>::other::const_reference
 175       const_metadata_reference;
 176
 177       // Default constructor.
 178       /*
 179         inline
 180         pat_trie_const_node_it_()
 181       */
 182       inline
 183       pat_trie_const_node_it_(node_pointer p_nd = 0,
 184                               const_e_access_traits_pointer p_traits = 0)
 185       : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits)
 186       { }
 187
 188       // Subtree valid prefix.
 189       inline std::pair<const_e_iterator, const_e_iterator>
 190       valid_prefix() const
 191       { return std::make_pair(pref_begin(), pref_end()); }
 192
 193       // Const access; returns the __const iterator* associated with
 194       // the current leaf.
 195       inline const_reference
 196       operator*() const
 197       {
 198         _GLIBCXX_DEBUG_ASSERT(num_children() == 0);
 199         return Const_Iterator(m_p_nd);
 200       }
 201
 202       // Metadata access.
 203       inline const_metadata_reference
 204       get_metadata() const
 205       { return m_p_nd->get_metadata(); }
 206
 207       // Returns the number of children in the corresponding node.
 208       inline size_type
 209       num_children() const
 210       {
 211         if (m_p_nd->m_type == pat_trie_leaf_node_type)
 212           return 0;
 213         _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
 214         return std::distance(static_cast<internal_node_pointer>(m_p_nd)->begin(),  static_cast<internal_node_pointer>(m_p_nd)->end());
 215       }
 216
 217       // Returns a __const node __iterator to the corresponding node's
 218       // i-th child.
 219       PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
 220       get_child(size_type i) const
 221       {
 222         _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
 223         typename Internal_Node::iterator it =
 224           static_cast<internal_node_pointer>(m_p_nd)->begin();
 225
 226         std::advance(it, i);
 227         return PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC(*it, m_p_traits);
 228       }
 229
 230       // Compares content to a different iterator object.
 231       inline bool
 232       operator==(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const
 233       { return (m_p_nd == other.m_p_nd); }
 234
 235       // Compares content (negatively) to a different iterator object.
 236       inline bool
 237       operator!=(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const
 238       { return m_p_nd != other.m_p_nd; }
 239
 240     private:
 241
 242       friend class PB_DS_CLASS_C_DEC;
 243
 244     public:
 245       node_pointer m_p_nd;
 246
 247       const_e_access_traits_pointer m_p_traits;
 248     };
 249
 250     // Node iterator.
 251     template<typename Node,
 252              class Leaf,
 253              class Head,
 254              class Internal_Node,
 255              class Const_Iterator,
 256              class Iterator,
 257              class E_Access_Traits,
 258              class Allocator>
 259     class pat_trie_node_it_ :
 260       public PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
 261
 262     {
 263     private:
 264       typedef
 265       typename Allocator::template rebind<
 266       Node>::other::pointer
 267       node_pointer;
 268
 269       typedef Iterator iterator;
 270
 271       typedef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC base_type;
 272
 273       typedef
 274       typename base_type::const_e_access_traits_pointer
 275       const_e_access_traits_pointer;
 276
 277       typedef typename base_type::internal_node_pointer internal_node_pointer;
 278
 279     public:
 280
 281       // Size type.
 282       typedef
 283       typename PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC::size_type
 284       size_type;
 285
 286       // __Iterator's value type.
 287       typedef Iterator value_type;
 288
 289       // __Iterator's reference type.
 290       typedef value_type reference;
 291
 292       // __Iterator's __const reference type.
 293       typedef value_type const_reference;
 294
 295       // Default constructor.
 296       /*
 297         inline
 298         pat_trie_node_it_() ;
 299       */
 300
 301       inline
 302       pat_trie_node_it_(node_pointer p_nd = 0,  const_e_access_traits_pointer p_traits = 0) : base_type(p_nd, p_traits)
 303       { }
 304
 305       // Access; returns the iterator*  associated with the current leaf.
 306       inline reference
 307       operator*() const
 308       {
 309         _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0);
 310         return Iterator(base_type::m_p_nd);
 311
 312       }
 313
 314       // Returns a node __iterator to the corresponding node's i-th child.
 315       PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC
 316       get_child(size_type i) const
 317       {
 318         _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == pat_trie_internal_node_type);
 319
 320         typename Internal_Node::iterator it =
 321           static_cast<internal_node_pointer>(base_type::m_p_nd)->begin();
 322
 323         std::advance(it, i);
 324         return PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC(*it, base_type::m_p_traits);
 325       }
 326
 327     private:
 328       friend class PB_DS_CLASS_C_DEC;
 329     };
 330
 331 #undef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
 332 #undef PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC
 333
 334   } // namespace detail
 335 } // namespace __gnu_pbds
 336
 337 #endif
 338