3 // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
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
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.
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.
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/>.
25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
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
37 * @file point_iterators.hpp
38 * Contains an implementation class for bin_search_tree_.
41 #ifndef PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
42 #define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP
44 #include <debug/debug.h>
51 #define PB_DS_CONST_IT_C_DEC \
58 Is_Forward_Iterator, \
61 #define PB_DS_CONST_ODIR_IT_C_DEC \
68 !Is_Forward_Iterator, \
71 #define PB_DS_IT_C_DEC \
78 Is_Forward_Iterator, \
81 #define PB_DS_ODIR_IT_C_DEC \
88 !Is_Forward_Iterator, \
93 template<typename Type_Traits
,
98 bool Is_Forward_Iterator
,
100 class pat_trie_const_it_
105 typename
Allocator::template rebind
<
106 Node
>::other::pointer
110 typename
Allocator::template rebind
<
111 Leaf
>::other::const_pointer
115 typename
Allocator::template rebind
<
116 Leaf
>::other::pointer
120 typename
Allocator::template rebind
<
121 Head
>::other::pointer
125 typename
Allocator::template rebind
<
126 Internal_Node
>::other::pointer
127 internal_node_pointer
;
131 typedef std::bidirectional_iterator_tag iterator_category
;
133 typedef typename
Allocator::difference_type difference_type
;
135 typedef typename
Type_Traits::value_type value_type
;
137 typedef typename
Type_Traits::pointer pointer
;
139 typedef typename
Type_Traits::const_pointer const_pointer
;
141 typedef typename
Type_Traits::reference reference
;
143 typedef typename
Type_Traits::const_reference const_reference
;
148 pat_trie_const_it_(node_pointer p_nd
= 0) : m_p_nd(p_nd
)
152 pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC
& other
)
153 : m_p_nd(other
.m_p_nd
)
157 PB_DS_CONST_IT_C_DEC
&
158 operator=(const PB_DS_CONST_IT_C_DEC
& other
)
160 m_p_nd
= other
.m_p_nd
;
165 PB_DS_CONST_IT_C_DEC
&
166 operator=(const PB_DS_CONST_ODIR_IT_C_DEC
& other
)
168 m_p_nd
= other
.m_p_nd
;
175 _GLIBCXX_DEBUG_ASSERT(m_p_nd
->m_type
== pat_trie_leaf_node_type
);
176 return &static_cast<leaf_pointer
>(m_p_nd
)->value();
179 inline const_reference
182 _GLIBCXX_DEBUG_ASSERT(m_p_nd
->m_type
== pat_trie_leaf_node_type
);
183 return static_cast<leaf_pointer
>(m_p_nd
)->value();
187 operator==(const PB_DS_CONST_IT_C_DEC
& other
) const
188 { return (m_p_nd
== other
.m_p_nd
); }
191 operator==(const PB_DS_CONST_ODIR_IT_C_DEC
& other
) const
192 { return (m_p_nd
== other
.m_p_nd
); }
195 operator!=(const PB_DS_CONST_IT_C_DEC
& other
) const
196 { return (m_p_nd
!= other
.m_p_nd
); }
199 operator!=(const PB_DS_CONST_ODIR_IT_C_DEC
& other
) const
200 { return (m_p_nd
!= other
.m_p_nd
); }
202 inline PB_DS_CONST_IT_C_DEC
&
205 inc(integral_constant
<int,Is_Forward_Iterator
>());
209 inline PB_DS_CONST_IT_C_DEC
212 PB_DS_CONST_IT_C_DEC
ret_it(m_p_nd
);
217 inline PB_DS_CONST_IT_C_DEC
&
220 dec(integral_constant
<int,Is_Forward_Iterator
>());
224 inline PB_DS_CONST_IT_C_DEC
227 PB_DS_CONST_IT_C_DEC
ret_it(m_p_nd
);
235 { dec(true_type()); }
240 if (m_p_nd
->m_type
== pat_trie_head_node_type
)
242 m_p_nd
= static_cast<head_pointer
>(m_p_nd
)->m_p_min
;
246 node_pointer p_y
= m_p_nd
->m_p_parent
;
247 while (p_y
->m_type
!= pat_trie_head_node_type
&&
248 get_larger_sibling(m_p_nd
) == 0)
251 p_y
= p_y
->m_p_parent
;
254 if (p_y
->m_type
== pat_trie_head_node_type
)
259 m_p_nd
= leftmost_descendant(get_larger_sibling(m_p_nd
));
264 { inc(true_type()); }
269 if (m_p_nd
->m_type
== pat_trie_head_node_type
)
271 m_p_nd
= static_cast<head_pointer
>(m_p_nd
)->m_p_max
;
275 node_pointer p_y
= m_p_nd
->m_p_parent
;
276 while (p_y
->m_type
!= pat_trie_head_node_type
&&
277 get_smaller_sibling(m_p_nd
) == 0)
280 p_y
= p_y
->m_p_parent
;
283 if (p_y
->m_type
== pat_trie_head_node_type
)
288 m_p_nd
= rightmost_descendant(get_smaller_sibling(m_p_nd
));
291 inline static node_pointer
292 get_larger_sibling(node_pointer p_nd
)
294 internal_node_pointer p_parent
=
295 static_cast<internal_node_pointer
>(p_nd
->m_p_parent
);
297 typename
Internal_Node::iterator it
= p_parent
->begin();
301 typename
Internal_Node::iterator next_it
= it
;
303 return ((next_it
== p_parent
->end())? 0 :* next_it
);
306 inline static node_pointer
307 get_smaller_sibling(node_pointer p_nd
)
309 internal_node_pointer p_parent
=
310 static_cast<internal_node_pointer
>(p_nd
->m_p_parent
);
312 typename
Internal_Node::iterator it
= p_parent
->begin();
316 typename
Internal_Node::iterator prev_it
;
326 _GLIBCXX_DEBUG_ASSERT(false);
330 inline static leaf_pointer
331 leftmost_descendant(node_pointer p_nd
)
333 if (p_nd
->m_type
== pat_trie_leaf_node_type
)
334 return static_cast<leaf_pointer
>(p_nd
);
335 return static_cast<internal_node_pointer
>(p_nd
)->leftmost_descendant();
338 inline static leaf_pointer
339 rightmost_descendant(node_pointer p_nd
)
341 if (p_nd
->m_type
== pat_trie_leaf_node_type
)
342 return static_cast<leaf_pointer
>(p_nd
);
343 return static_cast<internal_node_pointer
>(p_nd
)->rightmost_descendant();
351 template<typename Type_Traits
,
356 bool Is_Forward_Iterator
,
359 public PB_DS_CONST_IT_C_DEC
364 typename
Allocator::template rebind
<
365 Node
>::other::pointer
369 typename
Allocator::template rebind
<
370 Leaf
>::other::const_pointer
374 typename
Allocator::template rebind
<
375 Leaf
>::other::pointer
379 typename
Allocator::template rebind
<
380 Head
>::other::pointer
384 typename
Allocator::template rebind
<
385 Internal_Node
>::other::pointer
386 internal_node_pointer
;
389 typedef typename
Type_Traits::value_type value_type
;
391 typedef typename
Type_Traits::const_pointer const_pointer
;
393 typedef typename
Type_Traits::pointer pointer
;
395 typedef typename
Type_Traits::const_reference const_reference
;
397 typedef typename
Type_Traits::reference reference
;
400 pat_trie_it_(node_pointer p_nd
= 0) : PB_DS_CONST_IT_C_DEC((node_pointer
)p_nd
)
404 pat_trie_it_(const PB_DS_ODIR_IT_C_DEC
& other
) : PB_DS_CONST_IT_C_DEC(other
.m_p_nd
)
409 operator=(const PB_DS_IT_C_DEC
& other
)
411 base_it_type::m_p_nd
= other
.m_p_nd
;
417 operator=(const PB_DS_ODIR_IT_C_DEC
& other
)
419 base_it_type::m_p_nd
= other
.m_p_nd
;
426 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd
->m_type
== pat_trie_leaf_node_type
);
428 return &static_cast<leaf_pointer
>(base_it_type::m_p_nd
)->value();
434 _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd
->m_type
== pat_trie_leaf_node_type
);
435 return static_cast<leaf_pointer
>(base_it_type::m_p_nd
)->value();
438 inline PB_DS_IT_C_DEC
&
441 PB_DS_CONST_IT_C_DEC::
446 inline PB_DS_IT_C_DEC
449 PB_DS_IT_C_DEC
ret_it(base_it_type::m_p_nd
);
454 inline PB_DS_IT_C_DEC
&
457 PB_DS_CONST_IT_C_DEC::operator--();
461 inline PB_DS_IT_C_DEC
464 PB_DS_IT_C_DEC
ret_it(base_it_type::m_p_nd
);
470 typedef PB_DS_CONST_IT_C_DEC base_it_type
;
472 friend class PB_DS_CLASS_C_DEC
;
475 #undef PB_DS_CONST_IT_C_DEC
476 #undef PB_DS_CONST_ODIR_IT_C_DEC
477 #undef PB_DS_IT_C_DEC
478 #undef PB_DS_ODIR_IT_C_DEC
480 } // namespace detail
481 } // namespace __gnu_pbds