point_iterators.hpp revision 169691 
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 point_iterators.hpp
44 * Contains an implementation class for bin_search_tree_.
45 */
46
47#ifndef PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
48#define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
49
50#include <debug/debug.h>
51
52namespace pb_ds
53{
54  namespace detail
55  {
56
57#define PB_DS_CONST_IT_C_DEC					\
58    pat_trie_const_it_<						\
59					Type_Traits,		\
60					Node,			\
61					Leaf,			\
62					Head,			\
63					Internal_Node,		\
64					Is_Forward_Iterator,	\
65					Allocator>
66
67#define PB_DS_CONST_ODIR_IT_C_DEC				\
68    pat_trie_const_it_<						\
69					Type_Traits,		\
70					Node,			\
71					Leaf,			\
72					Head,			\
73					Internal_Node,		\
74					!Is_Forward_Iterator,	\
75					Allocator>
76
77#define PB_DS_IT_C_DEC							\
78    pat_trie_it_<							\
79						Type_Traits,		\
80						Node,			\
81						Leaf,			\
82						Head,			\
83						Internal_Node,		\
84						Is_Forward_Iterator,	\
85						Allocator>
86
87#define PB_DS_ODIR_IT_C_DEC						\
88    pat_trie_it_<							\
89						Type_Traits,		\
90						Node,			\
91						Leaf,			\
92						Head,			\
93						Internal_Node,		\
94						!Is_Forward_Iterator,	\
95						Allocator>
96
97
98    // Const iterator.
99    template<typename Type_Traits,
100	     class Node,
101	     class Leaf,
102	     class Head,
103	     class Internal_Node,
104	     bool Is_Forward_Iterator,
105	     class Allocator>
106    class pat_trie_const_it_
107    {
108
109    private:
110      typedef
111      typename Allocator::template rebind<
112      Node>::other::pointer
113      node_pointer;
114
115      typedef
116      typename Allocator::template rebind<
117	Leaf>::other::const_pointer
118      const_leaf_pointer;
119
120      typedef
121      typename Allocator::template rebind<
122	Leaf>::other::pointer
123      leaf_pointer;
124
125      typedef
126      typename Allocator::template rebind<
127	Head>::other::pointer
128      head_pointer;
129
130      typedef
131      typename Allocator::template rebind<
132	Internal_Node>::other::pointer
133      internal_node_pointer;
134
135    public:
136
137      typedef std::bidirectional_iterator_tag iterator_category;
138
139      typedef typename Allocator::difference_type difference_type;
140
141      typedef typename Type_Traits::value_type value_type;
142
143      typedef typename Type_Traits::pointer pointer;
144
145      typedef typename Type_Traits::const_pointer const_pointer;
146
147      typedef typename Type_Traits::reference reference;
148
149      typedef typename Type_Traits::const_reference const_reference;
150
151    public:
152
153      inline
154      pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd)
155      { }
156
157      inline
158      pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC& other)
159      : m_p_nd(other.m_p_nd)
160      { }
161
162      inline
163      PB_DS_CONST_IT_C_DEC&
164      operator=(const PB_DS_CONST_IT_C_DEC& other)
165      {
166	m_p_nd = other.m_p_nd;
167	return *this;
168      }
169
170      inline
171      PB_DS_CONST_IT_C_DEC&
172      operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other)
173      {
174	m_p_nd = other.m_p_nd;
175	return *this;
176      }
177
178      inline const_pointer
179      operator->() const
180      {
181	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
182	return &static_cast<leaf_pointer>(m_p_nd)->value();
183      }
184
185      inline const_reference
186      operator*() const
187      {
188	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type);
189	return static_cast<leaf_pointer>(m_p_nd)->value();
190      }
191
192      inline bool
193      operator==(const PB_DS_CONST_IT_C_DEC& other) const
194      { return (m_p_nd == other.m_p_nd); }
195
196      inline bool
197      operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
198      { return (m_p_nd == other.m_p_nd); }
199
200      inline bool
201      operator!=(const PB_DS_CONST_IT_C_DEC& other) const
202      { return (m_p_nd != other.m_p_nd); }
203
204      inline bool
205      operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const
206      { return (m_p_nd != other.m_p_nd); }
207
208      inline PB_DS_CONST_IT_C_DEC&
209      operator++()
210      {
211	inc(integral_constant<int,Is_Forward_Iterator>());
212	return *this;
213      }
214
215      inline PB_DS_CONST_IT_C_DEC
216      operator++(int)
217      {
218	PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
219	operator++();
220	return ret_it;
221      }
222
223      inline PB_DS_CONST_IT_C_DEC&
224      operator--()
225      {
226	dec(integral_constant<int,Is_Forward_Iterator>());
227	return *this;
228      }
229
230      inline PB_DS_CONST_IT_C_DEC
231      operator--(int)
232      {
233	PB_DS_CONST_IT_C_DEC ret_it(m_p_nd);
234	operator--();
235	return ret_it;
236      }
237
238    protected:
239      inline void
240      inc(false_type)
241      { dec(true_type()); }
242
243      void
244      inc(true_type)
245      {
246	if (m_p_nd->m_type == pat_trie_head_node_type)
247	  {
248	    m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min;
249	    return;
250	  }
251
252	node_pointer p_y = m_p_nd->m_p_parent;
253	while (p_y->m_type != pat_trie_head_node_type &&
254	       get_larger_sibling(m_p_nd) == NULL)
255	  {
256	    m_p_nd = p_y;
257	    p_y = p_y->m_p_parent;
258	  }
259
260	if (p_y->m_type == pat_trie_head_node_type)
261	  {
262	    m_p_nd = p_y;
263	    return;
264	  }
265	m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd));
266      }
267
268      inline void
269      dec(false_type)
270      { inc(true_type()); }
271
272      void
273      dec(true_type)
274      {
275	if (m_p_nd->m_type == pat_trie_head_node_type)
276	  {
277	    m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max;
278	    return;
279	  }
280
281	node_pointer p_y = m_p_nd->m_p_parent;
282	while (p_y->m_type != pat_trie_head_node_type &&
283	       get_smaller_sibling(m_p_nd) == NULL)
284	  {
285	    m_p_nd = p_y;
286	    p_y = p_y->m_p_parent;
287	  }
288
289	if (p_y->m_type == pat_trie_head_node_type)
290	  {
291	    m_p_nd = p_y;
292	    return;
293	  }
294	m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd));
295      }
296
297      inline static node_pointer
298      get_larger_sibling(node_pointer p_nd)
299      {
300	internal_node_pointer p_parent =
301	  static_cast<internal_node_pointer>(p_nd->m_p_parent);
302
303	typename Internal_Node::iterator it = p_parent->begin();
304	while (*it != p_nd)
305	  ++it;
306
307	typename Internal_Node::iterator next_it = it;
308	++next_it;
309	return ((next_it == p_parent->end())? NULL :* next_it);
310      }
311
312      inline static node_pointer
313      get_smaller_sibling(node_pointer p_nd)
314      {
315	internal_node_pointer p_parent =
316	  static_cast<internal_node_pointer>(p_nd->m_p_parent);
317
318	typename Internal_Node::iterator it = p_parent->begin();
319
320	if (*it == p_nd)
321	  return (NULL);
322	typename Internal_Node::iterator prev_it;
323	do
324	  {
325	    prev_it = it;
326	    ++it;
327	    if (*it == p_nd)
328	      return (*prev_it);
329	  }
330	while (true);
331
332	_GLIBCXX_DEBUG_ASSERT(false);
333	return (NULL);
334      }
335
336      inline static leaf_pointer
337      leftmost_descendant(node_pointer p_nd)
338      {
339	if (p_nd->m_type == pat_trie_leaf_node_type)
340	  return static_cast<leaf_pointer>(p_nd);
341	return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant();
342      }
343
344      inline static leaf_pointer
345      rightmost_descendant(node_pointer p_nd)
346      {
347	if (p_nd->m_type == pat_trie_leaf_node_type)
348	  return static_cast<leaf_pointer>(p_nd);
349	return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant();
350      }
351
352    public:
353      node_pointer m_p_nd;
354    };
355
356    // Iterator.
357    template<typename Type_Traits,
358	     class Node,
359	     class Leaf,
360	     class Head,
361	     class Internal_Node,
362	     bool Is_Forward_Iterator,
363	     class Allocator>
364    class pat_trie_it_ :
365      public PB_DS_CONST_IT_C_DEC
366
367    {
368    private:
369      typedef
370      typename Allocator::template rebind<
371      Node>::other::pointer
372      node_pointer;
373
374      typedef
375      typename Allocator::template rebind<
376	Leaf>::other::const_pointer
377      const_leaf_pointer;
378
379      typedef
380      typename Allocator::template rebind<
381	Leaf>::other::pointer
382      leaf_pointer;
383
384      typedef
385      typename Allocator::template rebind<
386	Head>::other::pointer
387      head_pointer;
388
389      typedef
390      typename Allocator::template rebind<
391	Internal_Node>::other::pointer
392      internal_node_pointer;
393
394    public:
395      typedef typename Type_Traits::value_type value_type;
396
397      typedef typename Type_Traits::const_pointer const_pointer;
398
399      typedef typename Type_Traits::pointer pointer;
400
401      typedef typename Type_Traits::const_reference const_reference;
402
403      typedef typename Type_Traits::reference reference;
404
405      inline
406      pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd)
407      { }
408
409      inline
410      pat_trie_it_(const PB_DS_ODIR_IT_C_DEC& other) : PB_DS_CONST_IT_C_DEC(other.m_p_nd)
411      { }
412
413      inline
414      PB_DS_IT_C_DEC&
415      operator=(const PB_DS_IT_C_DEC& other)
416      {
417	base_it_type::m_p_nd = other.m_p_nd;
418	return *this;
419      }
420
421      inline
422      PB_DS_IT_C_DEC&
423      operator=(const PB_DS_ODIR_IT_C_DEC& other)
424      {
425	base_it_type::m_p_nd = other.m_p_nd;
426	return *this;
427      }
428
429      inline pointer
430      operator->() const
431      {
432	_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
433
434	return &static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
435      }
436
437      inline reference
438      operator*() const
439      {
440	_GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type);
441	return static_cast<leaf_pointer>(base_it_type::m_p_nd)->value();
442      }
443
444      inline PB_DS_IT_C_DEC&
445      operator++()
446      {
447	PB_DS_CONST_IT_C_DEC::
448	  operator++();
449	return *this;
450      }
451
452      inline PB_DS_IT_C_DEC
453      operator++(int)
454      {
455	PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
456	operator++();
457	return ret_it;
458      }
459
460      inline PB_DS_IT_C_DEC&
461      operator--()
462      {
463	PB_DS_CONST_IT_C_DEC::operator--();
464	return *this;
465      }
466
467      inline PB_DS_IT_C_DEC
468      operator--(int)
469      {
470	PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd);
471	operator--();
472	return ret_it;
473      }
474
475    protected:
476      typedef PB_DS_CONST_IT_C_DEC base_it_type;
477
478      friend class PB_DS_CLASS_C_DEC;
479    };
480
481#undef PB_DS_CONST_IT_C_DEC
482#undef PB_DS_CONST_ODIR_IT_C_DEC
483#undef PB_DS_IT_C_DEC
484#undef PB_DS_ODIR_IT_C_DEC
485
486  } // namespace detail
487} // namespace pb_ds
488
489#endif
490
491