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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file node_iterators.hpp
  44  * Contains an implementation class for pat_trie_.
  45  */
  46
  47 #ifndef PB_DS_PAT_TRIE_NODE_ITERATORS_HPP
  48 #define PB_DS_PAT_TRIE_NODE_ITERATORS_HPP
  49
  50 namespace pb_ds
  51 {
  52   namespace detail
  53   {
  54
  55 #ifdef PB_DS_PAT_TRIE_DEBUG_
  56 #define PB_DS_DBG_ASSERT(X) assert(X)
  57 #define PB_DS_DBG_VERIFY(X) assert(X)
  58 #define PB_DS_DBG_ONLY(X) X
  59 #else // #ifdef PB_DS_PAT_TRIE_DEBUG_
  60 #define PB_DS_DBG_ASSERT(X)
  61 #define PB_DS_DBG_VERIFY(X) {if((X)==0);}
  62 #define PB_DS_DBG_ONLY(X) ;
  63 #endif // #ifdef PB_DS_PAT_TRIE_DEBUG_
  64
  65 #define PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC                        \
  66     pat_trie_const_node_it_<                                            \
  67                                                         Node,           \
  68                                                         Leaf,           \
  69                                                         Head,           \
  70                                                         Internal_Node,  \
  71                                                         Const_Iterator, \
  72                                                         Iterator,       \
  73                                                         E_Access_Traits, \
  74                                                         Allocator>
  75
  76 #define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC                      \
  77     pat_trie_node_it_<                                          \
  78                                         Node,                   \
  79                                         Leaf,                   \
  80                                         Head,                   \
  81                                         Internal_Node,          \
  82                                         Const_Iterator,         \
  83                                         Iterator,               \
  84                                         E_Access_Traits,        \
  85                                         Allocator>
  86
  87     // Const node iterator.
  88     template<typename Node,
  89              class Leaf,
  90              class Head,
  91              class Internal_Node,
  92              class Const_Iterator,
  93              class Iterator,
  94              class E_Access_Traits,
  95              class Allocator>
  96     class pat_trie_const_node_it_
  97     {
  98
  99     protected:
 100       typedef
 101       typename Allocator::template rebind<
 102       Node>::other::pointer
 103       node_pointer;
 104
 105       typedef
 106       typename Allocator::template rebind<
 107         Leaf>::other::const_pointer
 108       const_leaf_pointer;
 109
 110       typedef
 111       typename Allocator::template rebind<
 112         Leaf>::other::pointer
 113       leaf_pointer;
 114
 115       typedef
 116       typename Allocator::template rebind<
 117         Internal_Node>::other::pointer
 118       internal_node_pointer;
 119
 120       typedef
 121       typename Allocator::template rebind<
 122         Internal_Node>::other::const_pointer
 123       const_internal_node_pointer;
 124
 125       typedef
 126       typename Allocator::template rebind<
 127         E_Access_Traits>::other::const_pointer
 128       const_e_access_traits_pointer;
 129
 130     private:
 131       inline typename E_Access_Traits::const_iterator
 132       pref_begin() const
 133       {
 134         if (m_p_nd->m_type == pat_trie_leaf_node_type)
 135           return (m_p_traits->begin(
 136                                     m_p_traits->extract_key(
 137                                                             static_cast<const_leaf_pointer>(m_p_nd)->value())));
 138
 139         PB_DS_DBG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
 140
 141         return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_b_it());
 142       }
 143
 144       inline typename E_Access_Traits::const_iterator
 145       pref_end() const
 146       {
 147         if (m_p_nd->m_type == pat_trie_leaf_node_type)
 148           return (m_p_traits->end(
 149                                   m_p_traits->extract_key(
 150                                                           static_cast<const_leaf_pointer>(m_p_nd)->value())));
 151
 152         PB_DS_DBG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
 153
 154         return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_e_it());
 155       }
 156
 157     public:
 158
 159       // Size type.
 160       typedef typename Allocator::size_type size_type;
 161
 162       // Category.
 163       typedef trivial_iterator_tag iterator_category;
 164
 165       // Difference type.
 166       typedef trivial_iterator_difference_type difference_type;
 167
 168       // __Iterator's value type.
 169       typedef Const_Iterator value_type;
 170
 171       // __Iterator's reference type.
 172       typedef value_type reference;
 173
 174       // __Iterator's __const reference type.
 175       typedef value_type const_reference;
 176
 177       // Element access traits.
 178       typedef E_Access_Traits e_access_traits;
 179
 180       // A key's element __const iterator.
 181       typedef typename e_access_traits::const_iterator const_e_iterator;
 182
 183       // Metadata type.
 184       typedef typename Node::metadata_type metadata_type;
 185
 186       // Const metadata reference type.
 187       typedef
 188       typename Allocator::template rebind<
 189         metadata_type>::other::const_reference
 190       const_metadata_reference;
 191
 192     public:
 193
 194       // Default constructor.
 195       /*
 196         inline
 197         pat_trie_const_node_it_()
 198       */
 199
 200       inline
 201       pat_trie_const_node_it_(node_pointer p_nd = NULL,  const_e_access_traits_pointer p_traits = NULL) : m_p_nd(const_cast<node_pointer>(p_nd)),
 202                                                                                                           m_p_traits(p_traits)
 203       { }
 204
 205       // Subtree valid prefix.
 206       inline std::pair<
 207         const_e_iterator,
 208         const_e_iterator>
 209       valid_prefix() const
 210       {
 211         return (std::make_pair(
 212                                pref_begin(),
 213                                pref_end()));
 214       }
 215
 216       // Const access; returns the __const iterator*  associated with the current leaf.
 217       inline const_reference
 218       operator*() const
 219       {
 220         PB_DS_DBG_ASSERT(num_children() == 0);
 221
 222         return (Const_Iterator(m_p_nd));
 223       }
 224
 225       // Metadata access.
 226       inline const_metadata_reference
 227       get_metadata() const
 228       {
 229         return (m_p_nd->get_metadata());
 230       }
 231
 232       // Returns the number of children in the corresponding node.
 233       inline size_type
 234       num_children() const
 235       {
 236         if (m_p_nd->m_type == pat_trie_leaf_node_type)
 237           return (0);
 238
 239         PB_DS_DBG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
 240
 241         return (std::distance(
 242                               static_cast<internal_node_pointer>(m_p_nd)->begin(),
 243                               static_cast<internal_node_pointer>(m_p_nd)->end()));
 244       }
 245
 246       // Returns a __const node __iterator to the corresponding node's i-th child.
 247       PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
 248       get_child(size_type i) const
 249       {
 250         PB_DS_DBG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
 251
 252         typename Internal_Node::iterator it =
 253           static_cast<internal_node_pointer>(m_p_nd)->begin();
 254
 255         std::advance(it, i);
 256
 257         return (PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC(*it, m_p_traits));
 258       }
 259
 260       // Compares content to a different iterator object.
 261       inline bool
 262       operator==(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const
 263       {
 264         return (m_p_nd == other.m_p_nd);
 265       }
 266
 267       // Compares content (negatively) to a different iterator object.
 268       inline bool
 269       operator!=(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const
 270       {
 271         return (m_p_nd != other.m_p_nd);
 272       }
 273
 274     private:
 275
 276       friend class PB_DS_CLASS_C_DEC;
 277
 278     public:
 279       node_pointer m_p_nd;
 280
 281       const_e_access_traits_pointer m_p_traits;
 282     };
 283
 284     // Node iterator.
 285     template<typename Node,
 286              class Leaf,
 287              class Head,
 288              class Internal_Node,
 289              class Const_Iterator,
 290              class Iterator,
 291              class E_Access_Traits,
 292              class Allocator>
 293     class pat_trie_node_it_ :
 294       public PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
 295
 296     {
 297
 298     private:
 299       typedef
 300       typename Allocator::template rebind<
 301       Node>::other::pointer
 302       node_pointer;
 303
 304       typedef Iterator iterator;
 305
 306       typedef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC base_type;
 307
 308       typedef
 309       typename base_type::const_e_access_traits_pointer
 310       const_e_access_traits_pointer;
 311
 312       typedef typename base_type::internal_node_pointer internal_node_pointer;
 313
 314     public:
 315
 316       // Size type.
 317       typedef
 318       typename PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC::size_type
 319       size_type;
 320
 321       // __Iterator's value type.
 322       typedef Iterator value_type;
 323
 324       // __Iterator's reference type.
 325       typedef value_type reference;
 326
 327       // __Iterator's __const reference type.
 328       typedef value_type const_reference;
 329
 330     public:
 331
 332       // Default constructor.
 333       /*
 334         inline
 335         pat_trie_node_it_() ;
 336       */
 337
 338       inline
 339       pat_trie_node_it_(node_pointer p_nd = NULL,  const_e_access_traits_pointer p_traits = NULL) : base_type(p_nd, p_traits)
 340       { }
 341
 342       // Access; returns the iterator*  associated with the current leaf.
 343       inline reference
 344       operator*() const
 345       {
 346         PB_DS_DBG_ASSERT(base_type::num_children() == 0);
 347
 348         return (Iterator(base_type::m_p_nd));
 349
 350       }
 351
 352       // Returns a node __iterator to the corresponding node's i-th child.
 353       PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC
 354       get_child(size_type i) const
 355       {
 356         PB_DS_DBG_ASSERT(base_type::m_p_nd->m_type ==
 357                          pat_trie_internal_node_type);
 358
 359         typename Internal_Node::iterator it =
 360           static_cast<internal_node_pointer>(base_type::m_p_nd)->begin();
 361
 362         std::advance(it, i);
 363
 364         return (PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC(*it, base_type::m_p_traits));
 365       }
 366
 367     private:
 368       friend class PB_DS_CLASS_C_DEC;
 369     };
 370
 371 #undef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
 372
 373 #undef PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC
 374
 375 #undef PB_DS_DBG_ASSERT
 376 #undef PB_DS_DBG_VERIFY
 377 #undef PB_DS_DBG_ONLY
 378
 379   } // namespace detail
 380 } // namespace pb_ds
 381
 382 #endif // #ifndef PB_DS_PAT_TRIE_NODE_ITERATORS_HPP
 383