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

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