OpenCores
URL https://opencores.org/ocsvn/altor32/altor32/trunk

Subversion Repositories altor32

[/] [altor32/] [trunk/] [gcc-x64/] [or1knd-elf/] [or1knd-elf/] [include/] [c++/] [4.8.0/] [ext/] [pb_ds/] [detail/] [bin_search_tree_/] [point_iterators.hpp] - Blame information for rev 35

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 35 ultra_embe
// -*- C++ -*-
2
 
3
// Copyright (C) 2005, 2006, 2009, 2010 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 bin_search_tree_/point_iterators.hpp
38
 * Contains an implementation class for bin_search_tree_.
39
 */
40
 
41
#ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
42
#define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
43
 
44
#include <ext/pb_ds/tag_and_trait.hpp>
45
#include <debug/debug.h>
46
 
47
namespace __gnu_pbds
48
{
49
  namespace detail
50
  {
51
 
52
#define PB_DS_TREE_CONST_IT_C_DEC                                       \
53
    bin_search_tree_const_it_<                                          \
54
                                                Node_Pointer,           \
55
                                                Value_Type,             \
56
                                                Pointer,                \
57
                                                Const_Pointer,          \
58
                                                Reference,              \
59
                                                Const_Reference,        \
60
                                                Is_Forward_Iterator,    \
61
                                                _Alloc>
62
 
63
#define PB_DS_TREE_CONST_ODIR_IT_C_DEC                                  \
64
    bin_search_tree_const_it_<                                          \
65
                                                Node_Pointer,           \
66
                                                Value_Type,             \
67
                                                Pointer,                \
68
                                                Const_Pointer,          \
69
                                                Reference,              \
70
                                                Const_Reference,        \
71
                                                !Is_Forward_Iterator,   \
72
                                                _Alloc>
73
 
74
#define PB_DS_TREE_IT_C_DEC                                             \
75
    bin_search_tree_it_<                                                \
76
                                                Node_Pointer,           \
77
                                                Value_Type,             \
78
                                                Pointer,                \
79
                                                Const_Pointer,          \
80
                                                Reference,              \
81
                                                Const_Reference,        \
82
                                                Is_Forward_Iterator,    \
83
                                                _Alloc>
84
 
85
#define PB_DS_TREE_ODIR_IT_C_DEC                                        \
86
    bin_search_tree_it_<                                                \
87
                                                        Node_Pointer,   \
88
                                                        Value_Type,     \
89
                                                        Pointer,        \
90
                                                        Const_Pointer,  \
91
                                                        Reference,      \
92
                                                        Const_Reference, \
93
                                                        !Is_Forward_Iterator, \
94
                                                        _Alloc>
95
 
96
    /// Const iterator.
97
    template<typename Node_Pointer,
98
             typename Value_Type,
99
             typename Pointer,
100
             typename Const_Pointer,
101
             typename Reference,
102
             typename Const_Reference,
103
             bool Is_Forward_Iterator,
104
             typename _Alloc>
105
    class bin_search_tree_const_it_
106
    {
107
    public:
108
      typedef std::bidirectional_iterator_tag           iterator_category;
109
      typedef typename _Alloc::difference_type  difference_type;
110
      typedef Value_Type                                value_type;
111
      typedef Pointer                                   pointer;
112
      typedef Const_Pointer                             const_pointer;
113
      typedef Reference                                 reference;
114
      typedef Const_Reference                           const_reference;
115
 
116
      inline
117
      bin_search_tree_const_it_(const Node_Pointer p_nd = 0)
118
      : m_p_nd(const_cast<Node_Pointer>(p_nd))
119
      { }
120
 
121
      inline
122
      bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other)
123
      : m_p_nd(other.m_p_nd)
124
      { }
125
 
126
      inline
127
      PB_DS_TREE_CONST_IT_C_DEC&
128
      operator=(const PB_DS_TREE_CONST_IT_C_DEC& other)
129
      {
130
        m_p_nd = other.m_p_nd;
131
        return *this;
132
      }
133
 
134
      inline
135
      PB_DS_TREE_CONST_IT_C_DEC&
136
      operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other)
137
      {
138
        m_p_nd = other.m_p_nd;
139
        return *this;
140
      }
141
 
142
      inline const_pointer
143
      operator->() const
144
      {
145
        _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
146
        return &m_p_nd->m_value;
147
      }
148
 
149
      inline const_reference
150
      operator*() const
151
      {
152
        _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
153
        return m_p_nd->m_value;
154
      }
155
 
156
      inline bool
157
      operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const
158
      { return m_p_nd == other.m_p_nd; }
159
 
160
      inline bool
161
      operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const
162
      { return m_p_nd == other.m_p_nd; }
163
 
164
      inline bool
165
      operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const
166
      { return m_p_nd != other.m_p_nd; }
167
 
168
      inline bool
169
      operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const
170
      { return m_p_nd != other.m_p_nd; }
171
 
172
      inline PB_DS_TREE_CONST_IT_C_DEC&
173
      operator++()
174
      {
175
        _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
176
        inc(integral_constant<int,Is_Forward_Iterator>());
177
        return *this;
178
      }
179
 
180
      inline PB_DS_TREE_CONST_IT_C_DEC
181
      operator++(int)
182
      {
183
        PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
184
        operator++();
185
        return ret_it;
186
      }
187
 
188
      inline PB_DS_TREE_CONST_IT_C_DEC&
189
      operator--()
190
      {
191
        dec(integral_constant<int,Is_Forward_Iterator>());
192
        return *this;
193
      }
194
 
195
      inline PB_DS_TREE_CONST_IT_C_DEC
196
      operator--(int)
197
      {
198
        PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
199
        operator--();
200
        return ret_it;
201
      }
202
 
203
    protected:
204
      inline void
205
      inc(false_type)
206
      { dec(true_type()); }
207
 
208
      void
209
      inc(true_type)
210
      {
211
        if (m_p_nd->special()&&
212
            m_p_nd->m_p_parent->m_p_parent == m_p_nd)
213
          {
214
            m_p_nd = m_p_nd->m_p_left;
215
            return;
216
          }
217
 
218
        if (m_p_nd->m_p_right != 0)
219
          {
220
            m_p_nd = m_p_nd->m_p_right;
221
            while (m_p_nd->m_p_left != 0)
222
              m_p_nd = m_p_nd->m_p_left;
223
            return;
224
          }
225
 
226
        Node_Pointer p_y = m_p_nd->m_p_parent;
227
        while (m_p_nd == p_y->m_p_right)
228
          {
229
            m_p_nd = p_y;
230
            p_y = p_y->m_p_parent;
231
          }
232
 
233
        if (m_p_nd->m_p_right != p_y)
234
          m_p_nd = p_y;
235
      }
236
 
237
      inline void
238
      dec(false_type)
239
      { inc(true_type()); }
240
 
241
      void
242
      dec(true_type)
243
      {
244
        if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd)
245
          {
246
            m_p_nd = m_p_nd->m_p_right;
247
            return;
248
          }
249
 
250
        if (m_p_nd->m_p_left != 0)
251
          {
252
            Node_Pointer p_y = m_p_nd->m_p_left;
253
            while (p_y->m_p_right != 0)
254
              p_y = p_y->m_p_right;
255
            m_p_nd = p_y;
256
            return;
257
          }
258
 
259
        Node_Pointer p_y = m_p_nd->m_p_parent;
260
        while (m_p_nd == p_y->m_p_left)
261
          {
262
            m_p_nd = p_y;
263
            p_y = p_y->m_p_parent;
264
          }
265
        if (m_p_nd->m_p_left != p_y)
266
          m_p_nd = p_y;
267
      }
268
 
269
    public:
270
      Node_Pointer m_p_nd;
271
    };
272
 
273
    /// Iterator.
274
    template<typename Node_Pointer,
275
             typename Value_Type,
276
             typename Pointer,
277
             typename Const_Pointer,
278
             typename Reference,
279
             typename Const_Reference,
280
             bool Is_Forward_Iterator,
281
             typename _Alloc>
282
    class bin_search_tree_it_ : public PB_DS_TREE_CONST_IT_C_DEC
283
    {
284
    public:
285
      inline
286
      bin_search_tree_it_(const Node_Pointer p_nd = 0)
287
      : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd)
288
      { }
289
 
290
      inline
291
      bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other)
292
      : PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd)
293
      { }
294
 
295
      inline
296
      PB_DS_TREE_IT_C_DEC&
297
      operator=(const PB_DS_TREE_IT_C_DEC& other)
298
      {
299
        base_it_type::m_p_nd = other.m_p_nd;
300
        return *this;
301
      }
302
 
303
      inline
304
      PB_DS_TREE_IT_C_DEC&
305
      operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other)
306
      {
307
        base_it_type::m_p_nd = other.m_p_nd;
308
        return *this;
309
      }
310
 
311
      inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer
312
      operator->() const
313
      {
314
        _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0);
315
        return &base_it_type::m_p_nd->m_value;
316
      }
317
 
318
      inline typename PB_DS_TREE_CONST_IT_C_DEC::reference
319
      operator*() const
320
      {
321
        _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0);
322
        return base_it_type::m_p_nd->m_value;
323
      }
324
 
325
      inline PB_DS_TREE_IT_C_DEC&
326
      operator++()
327
      {
328
        PB_DS_TREE_CONST_IT_C_DEC:: operator++();
329
        return *this;
330
      }
331
 
332
      inline PB_DS_TREE_IT_C_DEC
333
      operator++(int)
334
      {
335
        PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
336
        operator++();
337
        return ret_it;
338
      }
339
 
340
      inline PB_DS_TREE_IT_C_DEC&
341
      operator--()
342
      {
343
        PB_DS_TREE_CONST_IT_C_DEC:: operator--();
344
        return *this;
345
      }
346
 
347
      inline PB_DS_TREE_IT_C_DEC
348
      operator--(int)
349
      {
350
        PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
351
        operator--();
352
        return ret_it;
353
      }
354
 
355
    protected:
356
      typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type;
357
    };
358
 
359
#undef PB_DS_TREE_CONST_IT_C_DEC
360
#undef PB_DS_TREE_CONST_ODIR_IT_C_DEC
361
#undef PB_DS_TREE_IT_C_DEC
362
#undef PB_DS_TREE_ODIR_IT_C_DEC
363
 
364
  } // namespace detail
365
} // namespace __gnu_pbds
366
 
367
#endif 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.