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

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