]>
Commit | Line | Data |
---|---|---|
4569a895 AT |
1 | // -*- C++ -*- |
2 | ||
748086b7 | 3 | // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. |
4569a895 AT |
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 | |
748086b7 | 8 | // Foundation; either version 3, or (at your option) any later |
4569a895 AT |
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 | ||
748086b7 JJ |
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. | |
4569a895 | 19 | |
748086b7 JJ |
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/>. | |
4569a895 AT |
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 find_fn_imps.hpp | |
38 | * Contains an implementation class for bin_search_tree_. | |
39 | */ | |
40 | ||
41 | PB_DS_CLASS_T_DEC | |
42 | inline typename PB_DS_CLASS_C_DEC::point_iterator | |
43 | PB_DS_CLASS_C_DEC:: | |
44 | find(const_key_reference r_key) | |
45 | { | |
47bea7b8 | 46 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
1b24692f | 47 | node_pointer p_nd = find_imp(r_key); |
4569a895 AT |
48 | |
49 | if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) | |
50 | { | |
551fe1a2 | 51 | _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) |
1b24692f | 52 | return end(); |
4569a895 AT |
53 | } |
54 | ||
1b24692f | 55 | if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_nd)->value()), r_key)) |
4569a895 | 56 | { |
551fe1a2 | 57 | _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); |
1b24692f | 58 | return iterator(p_nd); |
4569a895 AT |
59 | } |
60 | ||
551fe1a2 | 61 | _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) |
1b24692f | 62 | return end(); |
4569a895 AT |
63 | } |
64 | ||
65 | PB_DS_CLASS_T_DEC | |
66 | inline typename PB_DS_CLASS_C_DEC::const_point_iterator | |
67 | PB_DS_CLASS_C_DEC:: | |
68 | find(const_key_reference r_key) const | |
69 | { | |
47bea7b8 | 70 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
4569a895 | 71 | |
1b24692f | 72 | const_node_pointer p_nd = const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(r_key); |
4569a895 AT |
73 | |
74 | if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) | |
75 | { | |
551fe1a2 | 76 | _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) |
1b24692f | 77 | return end(); |
4569a895 AT |
78 | } |
79 | ||
1b24692f | 80 | if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key)) |
4569a895 | 81 | { |
551fe1a2 | 82 | _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); |
1b24692f | 83 | return const_iterator(const_cast<node_pointer>(p_nd)); |
4569a895 AT |
84 | } |
85 | ||
551fe1a2 | 86 | _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) |
1b24692f | 87 | return end(); |
4569a895 AT |
88 | } |
89 | ||
90 | PB_DS_CLASS_T_DEC | |
91 | inline typename PB_DS_CLASS_C_DEC::node_pointer | |
92 | PB_DS_CLASS_C_DEC:: | |
93 | find_imp(const_key_reference r_key) | |
94 | { | |
95 | if (empty()) | |
96 | return (NULL); | |
97 | ||
98 | typename synth_e_access_traits::const_iterator b_it = | |
99 | synth_e_access_traits::begin(r_key); | |
100 | typename synth_e_access_traits::const_iterator e_it = | |
101 | synth_e_access_traits::end(r_key); | |
102 | ||
103 | node_pointer p_nd = m_p_head->m_p_parent; | |
47bea7b8 | 104 | _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); |
4569a895 AT |
105 | |
106 | while (p_nd->m_type != pat_trie_leaf_node_type) | |
107 | { | |
47bea7b8 | 108 | _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); |
1b24692f | 109 | node_pointer p_next_nd = static_cast<internal_node_pointer>(p_nd)->get_child_node(b_it, e_it, this); |
4569a895 AT |
110 | |
111 | if (p_next_nd == NULL) | |
1b24692f | 112 | return p_nd; |
4569a895 AT |
113 | p_nd = p_next_nd; |
114 | } | |
1b24692f | 115 | return p_nd; |
4569a895 AT |
116 | } |
117 | ||
118 | PB_DS_CLASS_T_DEC | |
119 | inline typename PB_DS_CLASS_C_DEC::node_pointer | |
120 | PB_DS_CLASS_C_DEC:: | |
121 | lower_bound_imp(const_key_reference r_key) | |
122 | { | |
123 | if (empty()) | |
124 | return (m_p_head); | |
125 | ||
126 | node_pointer p_nd = m_p_head->m_p_parent; | |
47bea7b8 | 127 | _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); |
4569a895 AT |
128 | |
129 | typename PB_DS_CLASS_C_DEC::const_e_iterator b_it = | |
130 | synth_e_access_traits::begin(r_key); | |
131 | ||
132 | typename PB_DS_CLASS_C_DEC::const_e_iterator e_it = | |
133 | synth_e_access_traits::end(r_key); | |
134 | ||
135 | size_type checked_ind = 0; | |
4569a895 AT |
136 | while (true) |
137 | { | |
138 | if (p_nd->m_type == pat_trie_leaf_node_type) | |
139 | { | |
1b24692f BK |
140 | if (!synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key)) |
141 | return p_nd; | |
4569a895 | 142 | iterator it(p_nd); |
4569a895 | 143 | ++it; |
1b24692f | 144 | return it.m_p_nd; |
4569a895 AT |
145 | } |
146 | ||
47bea7b8 | 147 | _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); |
4569a895 AT |
148 | const size_type new_checked_ind = |
149 | static_cast<internal_node_pointer>(p_nd)->get_e_ind(); | |
150 | ||
151 | p_nd = | |
152 | static_cast<internal_node_pointer>(p_nd)->get_lower_bound_child_node( b_it, e_it, checked_ind, this); | |
4569a895 AT |
153 | checked_ind = new_checked_ind; |
154 | } | |
155 | } | |
156 | ||
157 | PB_DS_CLASS_T_DEC | |
158 | inline typename PB_DS_CLASS_C_DEC::point_iterator | |
159 | PB_DS_CLASS_C_DEC:: | |
160 | lower_bound(const_key_reference r_key) | |
1b24692f | 161 | { return point_iterator(lower_bound_imp(r_key)); } |
4569a895 AT |
162 | |
163 | PB_DS_CLASS_T_DEC | |
164 | inline typename PB_DS_CLASS_C_DEC::const_point_iterator | |
165 | PB_DS_CLASS_C_DEC:: | |
166 | lower_bound(const_key_reference r_key) const | |
167 | { | |
1b24692f | 168 | return const_point_iterator(const_cast<PB_DS_CLASS_C_DEC* >(this)->lower_bound_imp(r_key)); |
4569a895 AT |
169 | } |
170 | ||
171 | PB_DS_CLASS_T_DEC | |
172 | inline typename PB_DS_CLASS_C_DEC::point_iterator | |
173 | PB_DS_CLASS_C_DEC:: | |
174 | upper_bound(const_key_reference r_key) | |
175 | { | |
176 | point_iterator l_bound_it = lower_bound(r_key); | |
177 | ||
47bea7b8 | 178 | _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || |
1b24692f | 179 | !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), |
4569a895 AT |
180 | r_key)); |
181 | ||
182 | if (l_bound_it == end() || | |
1b24692f BK |
183 | synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) |
184 | return l_bound_it; | |
4569a895 | 185 | |
1b24692f | 186 | return ++l_bound_it; |
4569a895 AT |
187 | } |
188 | ||
189 | PB_DS_CLASS_T_DEC | |
190 | inline typename PB_DS_CLASS_C_DEC::const_point_iterator | |
191 | PB_DS_CLASS_C_DEC:: | |
192 | upper_bound(const_key_reference r_key) const | |
193 | { | |
194 | const_point_iterator l_bound_it = lower_bound(r_key); | |
195 | ||
47bea7b8 | 196 | _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || |
1b24692f | 197 | !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), |
4569a895 AT |
198 | r_key)); |
199 | ||
200 | if (l_bound_it == end() || | |
1b24692f BK |
201 | synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) |
202 | return l_bound_it; | |
203 | return ++l_bound_it; | |
4569a895 AT |
204 | } |
205 | ||
206 | PB_DS_CLASS_T_DEC | |
207 | inline typename PB_DS_CLASS_C_DEC::const_e_iterator | |
208 | PB_DS_CLASS_C_DEC:: | |
209 | pref_begin(const_node_pointer p_nd) | |
210 | { | |
211 | if (p_nd->m_type == pat_trie_leaf_node_type) | |
1b24692f | 212 | return (synth_e_access_traits::begin(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); |
4569a895 | 213 | |
47bea7b8 | 214 | _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); |
1b24692f | 215 | return static_cast<const_internal_node_pointer>(p_nd)->pref_b_it(); |
4569a895 AT |
216 | } |
217 | ||
218 | PB_DS_CLASS_T_DEC | |
219 | inline typename PB_DS_CLASS_C_DEC::const_e_iterator | |
220 | PB_DS_CLASS_C_DEC:: | |
221 | pref_end(const_node_pointer p_nd) | |
222 | { | |
223 | if (p_nd->m_type == pat_trie_leaf_node_type) | |
1b24692f | 224 | return (synth_e_access_traits::end(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); |
4569a895 | 225 | |
47bea7b8 | 226 | _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); |
1b24692f | 227 | return static_cast<const_internal_node_pointer>(p_nd)->pref_e_it(); |
4569a895 AT |
228 | } |
229 | ||
230 | PB_DS_CLASS_T_DEC | |
231 | inline typename PB_DS_CLASS_C_DEC::const_leaf_pointer | |
232 | PB_DS_CLASS_C_DEC:: | |
233 | leftmost_descendant(const_node_pointer p_nd) | |
234 | { | |
235 | if (p_nd->m_type == pat_trie_leaf_node_type) | |
1b24692f BK |
236 | return static_cast<const_leaf_pointer>(p_nd); |
237 | return static_cast<const_internal_node_pointer>(p_nd)->leftmost_descendant(); | |
4569a895 AT |
238 | } |
239 | ||
240 | PB_DS_CLASS_T_DEC | |
241 | inline typename PB_DS_CLASS_C_DEC::leaf_pointer | |
242 | PB_DS_CLASS_C_DEC:: | |
243 | leftmost_descendant(node_pointer p_nd) | |
244 | { | |
245 | if (p_nd->m_type == pat_trie_leaf_node_type) | |
1b24692f BK |
246 | return static_cast<leaf_pointer>(p_nd); |
247 | return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant(); | |
4569a895 AT |
248 | } |
249 | ||
250 | PB_DS_CLASS_T_DEC | |
251 | inline typename PB_DS_CLASS_C_DEC::const_leaf_pointer | |
252 | PB_DS_CLASS_C_DEC:: | |
253 | rightmost_descendant(const_node_pointer p_nd) | |
254 | { | |
255 | if (p_nd->m_type == pat_trie_leaf_node_type) | |
1b24692f BK |
256 | return static_cast<const_leaf_pointer>(p_nd); |
257 | return static_cast<const_internal_node_pointer>(p_nd)->rightmost_descendant(); | |
4569a895 AT |
258 | } |
259 | ||
260 | PB_DS_CLASS_T_DEC | |
261 | inline typename PB_DS_CLASS_C_DEC::leaf_pointer | |
262 | PB_DS_CLASS_C_DEC:: | |
263 | rightmost_descendant(node_pointer p_nd) | |
264 | { | |
265 | if (p_nd->m_type == pat_trie_leaf_node_type) | |
1b24692f BK |
266 | return static_cast<leaf_pointer>(p_nd); |
267 | return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant(); | |
4569a895 AT |
268 | } |
269 |