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