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

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [libstdc++-v3/] [include/] [ext/] [pb_assoc/] [detail/] [bin_search_tree_/] [find_iterators.hpp] - Blame information for rev 17

Details | Compare with Previous | View Log

Line No. Rev Author Line
1 17 jlechner 
// -*- C++ -*-
2 
 
3 
// Copyright (C) 2005 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
7 
// terms of the GNU General Public License as published by the
8 
// Free Software Foundation; either version 2, or (at your option)
9 
// any later version.
10 
 
11 
// This library is distributed in the hope that it will be useful,
12 
// but WITHOUT ANY WARRANTY; without even the implied warranty of
13 
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 
// GNU General Public License for more details.
15 
 
16 
// You should have received a copy of the GNU General Public License along
17 
// with this library; see the file COPYING.  If not, write to the Free
18 
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
19 
// USA.
20 
 
21 
// As a special exception, you may use this file as part of a free software
22 
// library without restriction.  Specifically, if other files instantiate
23 
// templates or use macros or inline functions from this file, or you compile
24 
// this file and link it with other files to produce an executable, this
25 
// file does not by itself cause the resulting executable to be covered by
26 
// the GNU General Public License.  This exception does not however
27 
// invalidate any other reasons why the executable file might be covered by
28 
// the GNU General Public License.
29 
 
30 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
31 
 
32 
// Permission to use, copy, modify, sell, and distribute this software
33 
// is hereby granted without fee, provided that the above copyright
34 
// notice appears in all copies, and that both that copyright notice and
35 
// this permission notice appear in supporting documentation. None of
36 
// the above authors, nor IBM Haifa Research Laboratories, make any
37 
// representation about the suitability of this software for any
38 
// purpose. It is provided "as is" without express or implied warranty.
39 
 
40 
/**
41 
 * @file find_iterators.hpp
42 
 * Contains an implementation class for bin_search_tree_.
43 
 */
44 
 
45 
#define PB_ASSOC_CONST_IT_C_DEC \
46 
        const_it_< \
47 
                Is_Forward_Iterator>
48 
 
49 
#define PB_ASSOC_CONST_ODIR_IT_C_DEC \
50 
        const_it_< \
51 
                !Is_Forward_Iterator>
52 
 
53 
#define PB_ASSOC_IT_C_DEC \
54 
        it_< \
55 
                Is_Forward_Iterator>
56 
 
57 
#define PB_ASSOC_ODIR_IT_C_DEC \
58 
        it_< \
59 
                !Is_Forward_Iterator>
60 
 
61 
template<bool Is_Forward_Iterator>
62 
class const_it_
63 
{
64 
 
65 
public:
66 
 
67 
  typedef std::bidirectional_iterator_tag iterator_category;
68 
 
69 
  typedef typename Allocator::difference_type difference_type;
70 
 
71 
  typedef mapped_value_type value_type;
72 
 
73 
  typedef mapped_pointer pointer;
74 
 
75 
  typedef const_mapped_pointer const_pointer;
76 
 
77 
  typedef mapped_reference reference;
78 
 
79 
  typedef const_mapped_reference const_reference;
80 
 
81 
public:
82 
 
83 
  inline
84 
  const_it_(const node_pointer p_nd = NULL) : m_p_nd(const_cast<node_pointer>(p_nd))
85 
  { }
86 
 
87 
  inline
88 
  const_it_(const PB_ASSOC_CONST_ODIR_IT_C_DEC&
89 
            r_other)
90 
 
91 
    : m_p_nd(r_other.m_p_nd)
92 
  { }
93 
 
94 
  inline
95 
  PB_ASSOC_CONST_IT_C_DEC&
96 
  operator=(const PB_ASSOC_CONST_IT_C_DEC&
97 
            r_other)
98 
  {
99 
    m_p_nd = r_other.m_p_nd;
100 
 
101 
    return (*this);
102 
  }
103 
 
104 
  inline
105 
  PB_ASSOC_CONST_IT_C_DEC&
106 
  operator=(const PB_ASSOC_CONST_ODIR_IT_C_DEC&
107 
            r_other)
108 
  {
109 
    m_p_nd = r_other.m_p_nd;
110 
 
111 
    return (*this);
112 
  }
113 
 
114 
  inline const_pointer
115 
  operator->() const
116 
  {
117 
    PB_ASSOC_DBG_ASSERT(m_p_nd != NULL);
118 
 
119 
    return (&m_p_nd->m_value);
120 
  }
121 
 
122 
  inline const_reference
123 
  operator*() const
124 
  {
125 
    PB_ASSOC_DBG_ASSERT(m_p_nd != NULL);
126 
 
127 
    return (m_p_nd->m_value);
128 
  }
129 
 
130 
  inline bool
131 
  operator==(const PB_ASSOC_CONST_IT_C_DEC
132 
             &r_other) const
133 
  {
134 
    return (m_p_nd == r_other.m_p_nd);
135 
  }
136 
 
137 
  inline bool
138 
  operator==(const PB_ASSOC_CONST_ODIR_IT_C_DEC
139 
             &r_other) const
140 
  {
141 
    return (m_p_nd == r_other.m_p_nd);
142 
  }
143 
 
144 
  inline bool
145 
  operator!=(const PB_ASSOC_CONST_IT_C_DEC&
146 
             r_other) const
147 
  {
148 
    return (m_p_nd != r_other.m_p_nd);
149 
  }
150 
 
151 
  inline bool
152 
  operator!=(const PB_ASSOC_CONST_ODIR_IT_C_DEC&
153 
             r_other) const
154 
  {
155 
    return (m_p_nd != r_other.m_p_nd);
156 
  }
157 
 
158 
  inline PB_ASSOC_CONST_IT_C_DEC&
159 
  operator++()
160 
  {
161 
    PB_ASSOC_DBG_ASSERT(m_p_nd != NULL);
162 
 
163 
    inc(int_to_type<Is_Forward_Iterator>());
164 
 
165 
    return (*this);
166 
  }
167 
 
168 
  inline PB_ASSOC_CONST_IT_C_DEC
169 
  operator++(int)
170 
  {
171 
    PB_ASSOC_CONST_IT_C_DEC
172 
      ret_it(m_p_nd);
173 
 
174 
    operator++();
175 
 
176 
    return (ret_it);
177 
  }
178 
 
179 
  inline PB_ASSOC_CONST_IT_C_DEC&
180 
  operator--()
181 
  {
182 
    dec(int_to_type<Is_Forward_Iterator>());
183 
 
184 
    return (*this);
185 
  }
186 
 
187 
  inline PB_ASSOC_CONST_IT_C_DEC
188 
  operator--(int)
189 
  {
190 
    PB_ASSOC_CONST_IT_C_DEC
191 
      ret_it(m_p_nd);
192 
 
193 
    operator--();
194 
 
195 
    return (ret_it);
196 
  }
197 
 
198 
protected:
199 
  inline void
200 
  inc(int_to_type<false>)
201 
  {
202 
    dec(int_to_type<true>());
203 
  }
204 
 
205 
  void
206 
  inc(int_to_type<true>)
207 
  {
208 
    if (m_p_nd->m_p_right != NULL)
209 
      {
210 
        m_p_nd = m_p_nd->m_p_right;
211 
 
212 
        while (m_p_nd->m_p_left != NULL)
213 
          m_p_nd = m_p_nd->m_p_left;
214 
 
215 
        return;
216 
      }
217 
 
218 
    node_pointer p_y = m_p_nd->m_p_parent;
219 
 
220 
    while (m_p_nd == p_y->m_p_right)
221 
      {
222 
        m_p_nd = p_y;
223 
 
224 
        p_y = p_y->m_p_parent;
225 
      }
226 
 
227 
    if (m_p_nd->m_p_right != p_y)
228 
      m_p_nd = p_y;
229 
  }
230 
 
231 
  inline void
232 
  dec(int_to_type<false>)
233 
  {
234 
    inc(int_to_type<true>());
235 
  }
236 
 
237 
  void
238 
  dec(int_to_type<true>)
239 
  {
240 
    if (m_p_nd->special_dec_check()&&
241 
        m_p_nd->m_p_parent->m_p_parent == m_p_nd)
242 
      {
243 
        m_p_nd = m_p_nd->m_p_right;
244 
 
245 
        return;
246 
      }
247 
 
248 
    if (m_p_nd->m_p_left != NULL)
249 
      {
250 
        node_pointer p_y = m_p_nd->m_p_left;
251 
 
252 
        while (p_y->m_p_right != NULL)
253 
          p_y = p_y->m_p_right;
254 
 
255 
        m_p_nd = p_y;
256 
 
257 
        return;
258 
      }
259 
 
260 
    node_pointer p_y = m_p_nd->m_p_parent;
261 
 
262 
    while (m_p_nd == p_y->m_p_left)
263 
      {
264 
        m_p_nd = p_y;
265 
 
266 
        p_y = p_y->m_p_parent;
267 
      }
268 
 
269 
    /*
270 
     * This seems to correct an apparent bug in the SGI STL
271 
     * implementation. */
272 
    if (m_p_nd->m_p_left != p_y)
273 
      m_p_nd = p_y;
274 
  }
275 
 
276 
  friend class PB_ASSOC_CLASS_C_DEC;
277 
 
278 
public:
279 
  node_pointer m_p_nd;
280 
};
281 
 
282 
template<bool Is_Forward_Iterator>
283 
class it_ :
284 
  public PB_ASSOC_CONST_IT_C_DEC
285 
 
286 
{
287 
 
288 
public:
289 
 
290 
  inline
291 
  it_(const node_pointer p_nd = NULL) : PB_ASSOC_CONST_IT_C_DEC((node_pointer)p_nd)
292 
  { }
293 
 
294 
  inline
295 
  it_(const PB_ASSOC_ODIR_IT_C_DEC&
296 
      r_other)
297 
 
298 
    : PB_ASSOC_CONST_IT_C_DEC(
299 
                              r_other.m_p_nd)
300 
  { }
301 
 
302 
  inline
303 
  PB_ASSOC_IT_C_DEC&
304 
  operator=(const PB_ASSOC_IT_C_DEC&
305 
            r_other)
306 
  {
307 
    my_base_it::m_p_nd = r_other.m_p_nd;
308 
 
309 
    return (*this);
310 
  }
311 
 
312 
  inline
313 
  PB_ASSOC_IT_C_DEC&
314 
  operator=(const PB_ASSOC_ODIR_IT_C_DEC&
315 
            r_other)
316 
  {
317 
    my_base_it::m_p_nd = r_other.m_p_nd;
318 
 
319 
    return (*this);
320 
  }
321 
 
322 
  inline pointer
323 
  operator->()
324 
  {
325 
    PB_ASSOC_DBG_ASSERT(my_base_it::m_p_nd != NULL);
326 
 
327 
    return (&my_base_it::m_p_nd->m_value);
328 
  }
329 
 
330 
  inline reference
331 
  operator*()
332 
  {
333 
    PB_ASSOC_DBG_ASSERT(my_base_it::m_p_nd != NULL);
334 
 
335 
    return (my_base_it::m_p_nd->m_value);
336 
  }
337 
 
338 
  inline PB_ASSOC_IT_C_DEC&
339 
  operator++()
340 
  {
341 
    PB_ASSOC_CONST_IT_C_DEC::
342 
      operator++();
343 
 
344 
    return (*this);
345 
  }
346 
 
347 
  inline PB_ASSOC_IT_C_DEC
348 
  operator++(int)
349 
  {
350 
    PB_ASSOC_IT_C_DEC
351 
      ret_it(my_base_it::m_p_nd);
352 
 
353 
    operator++();
354 
 
355 
    return (ret_it);
356 
  }
357 
 
358 
  inline PB_ASSOC_IT_C_DEC&
359 
  operator--()
360 
  {
361 
    PB_ASSOC_CONST_IT_C_DEC::
362 
      operator--();
363 
 
364 
    return (*this);
365 
  }
366 
 
367 
  inline PB_ASSOC_IT_C_DEC
368 
  operator--(int)
369 
  {
370 
    PB_ASSOC_IT_C_DEC
371 
      ret_it(my_base_it::m_p_nd);
372 
 
373 
    operator--();
374 
 
375 
    return (ret_it);
376 
  }
377 
 
378 
protected:
379 
  typedef PB_ASSOC_CONST_IT_C_DEC my_base_it;
380 
 
381 
  friend class PB_ASSOC_CLASS_C_DEC;
382 
};
383 
 
384 
#undef PB_ASSOC_CONST_IT_C_DEC
385 
 
386 
#undef PB_ASSOC_CONST_ODIR_IT_C_DEC
387 
 
388 
#undef PB_ASSOC_IT_C_DEC
389 
 
390 
#undef PB_ASSOC_ODIR_IT_C_DEC
391 
 

powered by: WebSVN 2.1.0

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