libstdc++-v3/include/ext/pb_ds/detail/ov_tree_map_/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 ov_tree_.
  45  */
  46
  47 #ifndef PB_DS_OV_TREE_NODE_ITERATORS_HPP
  48 #define PB_DS_OV_TREE_NODE_ITERATORS_HPP
  49
  50 #include <ext/pb_ds/tag_and_trait.hpp>
  51 #include <ext/pb_ds/detail/type_utils.hpp>
  52 #include <debug/debug.h>
  53
  54 namespace pb_ds
  55 {
  56   namespace detail
  57   {
  58
  59 #define PB_DS_STATIC_ASSERT(UNIQUE, E)                                  \
  60     typedef                                                             \
  61     static_assert_dumclass<sizeof(static_assert<(bool)(E)>)> \
  62     UNIQUE##static_assert_type
  63
  64 #define PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC                 \
  65     ov_tree_node_const_it_<Value_Type, Metadata_Type, Allocator>
  66
  67     // Const node reference.
  68     template<typename Value_Type, typename Metadata_Type, class Allocator>
  69     class ov_tree_node_const_it_
  70     {
  71
  72     protected:
  73       typedef
  74       typename Allocator::template rebind<
  75       Value_Type>::other::pointer
  76       pointer;
  77
  78       typedef
  79       typename Allocator::template rebind<
  80         Value_Type>::other::const_pointer
  81       const_pointer;
  82
  83       typedef
  84       typename Allocator::template rebind<
  85         Metadata_Type>::other::const_pointer
  86       const_metadata_pointer;
  87
  88       typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC this_type;
  89
  90     protected:
  91
  92       template<typename Ptr>
  93       inline static Ptr
  94       mid_pointer(Ptr p_begin, Ptr p_end)
  95       {
  96         _GLIBCXX_DEBUG_ASSERT(p_end >= p_begin);
  97         return (p_begin + (p_end - p_begin) / 2);
  98       }
  99
 100     public:
 101
 102       typedef trivial_iterator_tag iterator_category;
 103
 104       typedef trivial_iterator_difference_type difference_type;
 105
 106       typedef
 107       typename Allocator::template rebind<
 108         Value_Type>::other::const_pointer
 109       value_type;
 110
 111       typedef
 112       typename Allocator::template rebind<
 113         typename remove_const<
 114         Value_Type>::type>::other::const_pointer
 115       reference;
 116
 117       typedef
 118       typename Allocator::template rebind<
 119         typename remove_const<
 120         Value_Type>::type>::other::const_pointer
 121       const_reference;
 122
 123       typedef Metadata_Type metadata_type;
 124
 125       typedef
 126       typename Allocator::template rebind<
 127         metadata_type>::other::const_reference
 128       const_metadata_reference;
 129
 130     public:
 131       inline
 132       ov_tree_node_const_it_(const_pointer p_nd = NULL,  const_pointer p_begin_nd = NULL,  const_pointer p_end_nd = NULL,  const_metadata_pointer p_metadata = NULL) : m_p_value(const_cast<pointer>(p_nd)), m_p_begin_value(const_cast<pointer>(p_begin_nd)), m_p_end_value(const_cast<pointer>(p_end_nd)), m_p_metadata(p_metadata)
 133       { }
 134
 135       inline const_reference
 136       operator*() const
 137       { return m_p_value; }
 138
 139       inline const_metadata_reference
 140       get_metadata() const
 141       {
 142         enum
 143           {
 144             has_metadata = !is_same<Metadata_Type, null_node_metadata>::value
 145           };
 146
 147         PB_DS_STATIC_ASSERT(should_have_metadata, has_metadata);
 148         _GLIBCXX_DEBUG_ASSERT(m_p_metadata != NULL);
 149         return *m_p_metadata;
 150       }
 151
 152       inline this_type
 153       get_l_child() const
 154       {
 155         if (m_p_begin_value == m_p_value)
 156           return (this_type(m_p_begin_value, m_p_begin_value, m_p_begin_value));
 157
 158         const_metadata_pointer p_begin_metadata =
 159           m_p_metadata - (m_p_value - m_p_begin_value);
 160
 161         return (this_type(mid_pointer(m_p_begin_value, m_p_value),
 162                           m_p_begin_value,
 163                           m_p_value,
 164                           mid_pointer(p_begin_metadata, m_p_metadata)));
 165       }
 166
 167       inline this_type
 168       get_r_child() const
 169       {
 170         if (m_p_value == m_p_end_value)
 171           return (this_type(m_p_end_value,  m_p_end_value,  m_p_end_value));
 172
 173         const_metadata_pointer p_end_metadata =
 174           m_p_metadata + (m_p_end_value - m_p_value);
 175
 176         return (this_type(mid_pointer(m_p_value + 1, m_p_end_value),
 177                           m_p_value + 1,
 178                           m_p_end_value,(m_p_metadata == NULL) ?
 179                           NULL : mid_pointer(m_p_metadata + 1, p_end_metadata)));
 180       }
 181
 182       inline bool
 183       operator==(const this_type& other) const
 184       {
 185         const bool is_end = m_p_begin_value == m_p_end_value;
 186         const bool is_other_end = other.m_p_begin_value == other.m_p_end_value;
 187
 188         if (is_end)
 189           return (is_other_end);
 190
 191         if (is_other_end)
 192           return (is_end);
 193
 194         return m_p_value == other.m_p_value;
 195       }
 196
 197       inline bool
 198       operator!=(const this_type& other) const
 199       { return !operator==(other); }
 200
 201     public:
 202       pointer m_p_value;
 203       pointer m_p_begin_value;
 204       pointer m_p_end_value;
 205
 206       const_metadata_pointer m_p_metadata;
 207     };
 208
 209 #define PB_DS_OV_TREE_NODE_ITERATOR_C_DEC                       \
 210     ov_tree_node_it_<Value_Type, Metadata_Type, Allocator>
 211
 212     // Node reference.
 213     template<typename Value_Type, typename Metadata_Type, class Allocator>
 214     class ov_tree_node_it_ : public PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC
 215     {
 216
 217     private:
 218       typedef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC this_type;
 219
 220       typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC base_type;
 221
 222       typedef typename base_type::pointer pointer;
 223
 224       typedef typename base_type::const_pointer const_pointer;
 225
 226       typedef
 227       typename base_type::const_metadata_pointer
 228       const_metadata_pointer;
 229
 230     public:
 231
 232       typedef trivial_iterator_tag iterator_category;
 233
 234       typedef trivial_iterator_difference_type difference_type;
 235
 236       typedef
 237       typename Allocator::template rebind<
 238         Value_Type>::other::pointer
 239       value_type;
 240
 241       typedef
 242       typename Allocator::template rebind<
 243         typename remove_const<
 244         Value_Type>::type>::other::pointer
 245       reference;
 246
 247       typedef
 248       typename Allocator::template rebind<
 249         typename remove_const<
 250         Value_Type>::type>::other::pointer
 251       const_reference;
 252
 253     public:
 254       inline
 255       ov_tree_node_it_(const_pointer p_nd = NULL,  const_pointer p_begin_nd = NULL,  const_pointer p_end_nd = NULL,  const_metadata_pointer p_metadata = NULL) : base_type(                p_nd,  p_begin_nd,  p_end_nd,  p_metadata)
 256       { }
 257
 258       // Access.
 259       inline reference
 260       operator*() const
 261       { return reference(base_type::m_p_value); }
 262
 263       // Returns the node reference associated with the left node.
 264       inline ov_tree_node_it_
 265       get_l_child() const
 266       {
 267         if (base_type::m_p_begin_value == base_type::m_p_value)
 268           return (this_type(base_type::m_p_begin_value,  base_type::m_p_begin_value,  base_type::m_p_begin_value));
 269
 270         const_metadata_pointer p_begin_metadata =
 271           base_type::m_p_metadata - (base_type::m_p_value - base_type::m_p_begin_value);
 272
 273         return (this_type(base_type::mid_pointer(base_type::m_p_begin_value, base_type::m_p_value),
 274                           base_type::m_p_begin_value,
 275                           base_type::m_p_value,
 276                           base_type::mid_pointer(p_begin_metadata, base_type::m_p_metadata)));
 277       }
 278
 279       // Returns the node reference associated with the right node.
 280       inline ov_tree_node_it_
 281       get_r_child() const
 282       {
 283         if (base_type::m_p_value == base_type::m_p_end_value)
 284           return (this_type(base_type::m_p_end_value,  base_type::m_p_end_value,  base_type::m_p_end_value));
 285
 286         const_metadata_pointer p_end_metadata =
 287           base_type::m_p_metadata + (base_type::m_p_end_value - base_type::m_p_value);
 288
 289         return (this_type(base_type::mid_pointer(base_type::m_p_value + 1, base_type::m_p_end_value),
 290                           base_type::m_p_value + 1,
 291                           base_type::m_p_end_value,(base_type::m_p_metadata == NULL)?
 292                           NULL : base_type::mid_pointer(base_type::m_p_metadata + 1, p_end_metadata)));
 293       }
 294
 295     };
 296
 297 #undef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC
 298 #undef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC
 299 #undef PB_DS_STATIC_ASSERT
 300
 301 } // namespace detail
 302 } // namespace pb_ds
 303
 304 #endif