]>
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 insert_join_fn_imps.hpp | |
38 | * Contains an implementation class for bin_search_tree_. | |
39 | */ | |
40 | ||
41 | PB_DS_CLASS_T_DEC | |
42 | void | |
43 | PB_DS_CLASS_C_DEC:: | |
44 | join(PB_DS_CLASS_C_DEC& other) | |
45 | { | |
47bea7b8 BK |
46 | _GLIBCXX_DEBUG_ONLY(assert_valid();); |
47 | _GLIBCXX_DEBUG_ONLY(other.assert_valid();); | |
4569a895 | 48 | split_join_branch_bag bag; |
4569a895 AT |
49 | if (!join_prep(other, bag)) |
50 | { | |
47bea7b8 BK |
51 | _GLIBCXX_DEBUG_ONLY(assert_valid();); |
52 | _GLIBCXX_DEBUG_ONLY(other.assert_valid();); | |
4569a895 AT |
53 | return; |
54 | } | |
55 | ||
47bea7b8 BK |
56 | m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, |
57 | other.m_p_head->m_p_parent, 0, bag); | |
4569a895 AT |
58 | |
59 | m_p_head->m_p_parent->m_p_parent = m_p_head; | |
4569a895 | 60 | m_size += other.m_size; |
4569a895 | 61 | other.initialize(); |
47bea7b8 | 62 | _GLIBCXX_DEBUG_ONLY(other.assert_valid();); |
4569a895 AT |
63 | m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent); |
64 | m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); | |
47bea7b8 | 65 | _GLIBCXX_DEBUG_ONLY(assert_valid();); |
4569a895 AT |
66 | } |
67 | ||
68 | PB_DS_CLASS_T_DEC | |
69 | bool | |
70 | PB_DS_CLASS_C_DEC:: | |
71 | join_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag) | |
72 | { | |
47bea7b8 BK |
73 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
74 | _GLIBCXX_DEBUG_ONLY(other.assert_valid();) | |
75 | if (other.m_size == 0) | |
76 | return false; | |
4569a895 AT |
77 | |
78 | if (m_size == 0) | |
79 | { | |
80 | value_swap(other); | |
47bea7b8 | 81 | return false; |
4569a895 AT |
82 | } |
83 | ||
47bea7b8 BK |
84 | const bool greater = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>( |
85 | m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast<const_leaf_pointer>( | |
4569a895 AT |
86 | other.m_p_head->m_p_min)->value())); |
87 | ||
47bea7b8 BK |
88 | const bool lesser = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>( |
89 | other.m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value())); | |
4569a895 | 90 | |
47bea7b8 | 91 | if (!greater && !lesser) |
8fafc2d3 | 92 | __throw_join_error(); |
4569a895 AT |
93 | |
94 | rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag); | |
551fe1a2 | 95 | _GLIBCXX_DEBUG_ONLY(debug_base::join(other);) |
47bea7b8 | 96 | return true; |
4569a895 AT |
97 | } |
98 | ||
99 | PB_DS_CLASS_T_DEC | |
100 | void | |
101 | PB_DS_CLASS_C_DEC:: | |
102 | rec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag) | |
103 | { | |
104 | if (p_l->m_type == pat_trie_leaf_node_type) | |
105 | { | |
106 | if (p_r->m_type == pat_trie_leaf_node_type) | |
107 | { | |
47bea7b8 BK |
108 | rec_join_prep(static_cast<const_leaf_pointer>(p_l), |
109 | static_cast<const_leaf_pointer>(p_r), r_bag); | |
4569a895 AT |
110 | return; |
111 | } | |
112 | ||
47bea7b8 BK |
113 | _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); |
114 | rec_join_prep(static_cast<const_leaf_pointer>(p_l), | |
115 | static_cast<const_internal_node_pointer>(p_r), r_bag); | |
4569a895 AT |
116 | return; |
117 | } | |
118 | ||
47bea7b8 | 119 | _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type); |
4569a895 AT |
120 | if (p_r->m_type == pat_trie_leaf_node_type) |
121 | { | |
47bea7b8 BK |
122 | rec_join_prep(static_cast<const_internal_node_pointer>(p_l), |
123 | static_cast<const_leaf_pointer>(p_r), r_bag); | |
4569a895 AT |
124 | return; |
125 | } | |
126 | ||
47bea7b8 | 127 | _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); |
4569a895 | 128 | |
47bea7b8 BK |
129 | rec_join_prep(static_cast<const_internal_node_pointer>(p_l), |
130 | static_cast<const_internal_node_pointer>(p_r), r_bag); | |
4569a895 AT |
131 | } |
132 | ||
133 | PB_DS_CLASS_T_DEC | |
134 | void | |
135 | PB_DS_CLASS_C_DEC:: | |
47bea7b8 BK |
136 | rec_join_prep(const_leaf_pointer /*p_l*/, const_leaf_pointer /*p_r*/, |
137 | split_join_branch_bag& r_bag) | |
138 | { r_bag.add_branch(); } | |
4569a895 AT |
139 | |
140 | PB_DS_CLASS_T_DEC | |
141 | void | |
142 | PB_DS_CLASS_C_DEC:: | |
47bea7b8 BK |
143 | rec_join_prep(const_leaf_pointer /*p_l*/, const_internal_node_pointer /*p_r*/, |
144 | split_join_branch_bag& r_bag) | |
145 | { r_bag.add_branch(); } | |
4569a895 AT |
146 | |
147 | PB_DS_CLASS_T_DEC | |
148 | void | |
149 | PB_DS_CLASS_C_DEC:: | |
47bea7b8 BK |
150 | rec_join_prep(const_internal_node_pointer /*p_l*/, const_leaf_pointer /*p_r*/, |
151 | split_join_branch_bag& r_bag) | |
152 | { r_bag.add_branch(); } | |
4569a895 AT |
153 | |
154 | PB_DS_CLASS_T_DEC | |
155 | void | |
156 | PB_DS_CLASS_C_DEC:: | |
47bea7b8 BK |
157 | rec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r, |
158 | split_join_branch_bag& r_bag) | |
4569a895 | 159 | { |
47bea7b8 BK |
160 | if (p_l->get_e_ind() == p_r->get_e_ind() && |
161 | synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(), | |
162 | p_r->pref_b_it(), p_r->pref_e_it())) | |
4569a895 AT |
163 | { |
164 | for (typename internal_node::const_iterator it = p_r->begin(); | |
165 | it != p_r->end(); ++ it) | |
166 | { | |
47bea7b8 | 167 | const_node_pointer p_l_join_child = p_l->get_join_child(*it, this); |
8fc81078 | 168 | if (p_l_join_child != 0) |
4569a895 AT |
169 | rec_join_prep(p_l_join_child, * it, r_bag); |
170 | } | |
4569a895 AT |
171 | return; |
172 | } | |
173 | ||
47bea7b8 BK |
174 | if (p_r->get_e_ind() < p_l->get_e_ind() && |
175 | p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) | |
4569a895 | 176 | { |
47bea7b8 | 177 | const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this); |
8fc81078 | 178 | if (p_r_join_child != 0) |
4569a895 | 179 | rec_join_prep(p_r_join_child, p_l, r_bag); |
4569a895 AT |
180 | return; |
181 | } | |
182 | ||
47bea7b8 BK |
183 | if (p_r->get_e_ind() < p_l->get_e_ind() && |
184 | p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) | |
4569a895 | 185 | { |
47bea7b8 | 186 | const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this); |
8fc81078 | 187 | if (p_r_join_child != 0) |
4569a895 | 188 | rec_join_prep(p_r_join_child, p_l, r_bag); |
4569a895 AT |
189 | return; |
190 | } | |
4569a895 AT |
191 | r_bag.add_branch(); |
192 | } | |
193 | ||
194 | PB_DS_CLASS_T_DEC | |
195 | typename PB_DS_CLASS_C_DEC::node_pointer | |
196 | PB_DS_CLASS_C_DEC:: | |
197 | rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) | |
198 | { | |
8fc81078 PC |
199 | _GLIBCXX_DEBUG_ASSERT(p_r != 0); |
200 | if (p_l == 0) | |
4569a895 AT |
201 | { |
202 | apply_update(p_r, (node_update* )this); | |
4569a895 AT |
203 | return (p_r); |
204 | } | |
205 | ||
206 | if (p_l->m_type == pat_trie_leaf_node_type) | |
207 | { | |
208 | if (p_r->m_type == pat_trie_leaf_node_type) | |
209 | { | |
47bea7b8 BK |
210 | node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), |
211 | static_cast<leaf_pointer>(p_r), r_bag); | |
4569a895 | 212 | apply_update(p_ret, (node_update* )this); |
47bea7b8 | 213 | return p_ret; |
4569a895 AT |
214 | } |
215 | ||
47bea7b8 BK |
216 | _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); |
217 | node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), | |
4569a895 | 218 | static_cast<internal_node_pointer>(p_r), |
47bea7b8 | 219 | checked_ind, r_bag); |
4569a895 | 220 | apply_update(p_ret, (node_update* )this); |
47bea7b8 | 221 | return p_ret; |
4569a895 AT |
222 | } |
223 | ||
47bea7b8 | 224 | _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type); |
4569a895 AT |
225 | if (p_r->m_type == pat_trie_leaf_node_type) |
226 | { | |
47bea7b8 | 227 | node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l), |
4569a895 | 228 | static_cast<leaf_pointer>(p_r), |
47bea7b8 | 229 | checked_ind, r_bag); |
4569a895 | 230 | apply_update(p_ret, (node_update* )this); |
47bea7b8 | 231 | return p_ret; |
4569a895 AT |
232 | } |
233 | ||
47bea7b8 BK |
234 | _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); |
235 | node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l), | |
236 | static_cast<internal_node_pointer>(p_r), | |
4569a895 AT |
237 | r_bag); |
238 | ||
239 | apply_update(p_ret, (node_update* )this); | |
47bea7b8 | 240 | return p_ret; |
4569a895 AT |
241 | } |
242 | ||
243 | PB_DS_CLASS_T_DEC | |
244 | typename PB_DS_CLASS_C_DEC::node_pointer | |
245 | PB_DS_CLASS_C_DEC:: | |
246 | rec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag) | |
247 | { | |
8fc81078 PC |
248 | _GLIBCXX_DEBUG_ASSERT(p_r != 0); |
249 | if (p_l == 0) | |
4569a895 | 250 | return (p_r); |
4569a895 | 251 | node_pointer p_ret = insert_branch(p_l, p_r, r_bag); |
47bea7b8 BK |
252 | _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == 2); |
253 | return p_ret; | |
4569a895 AT |
254 | } |
255 | ||
256 | PB_DS_CLASS_T_DEC | |
257 | typename PB_DS_CLASS_C_DEC::node_pointer | |
258 | PB_DS_CLASS_C_DEC:: | |
47bea7b8 BK |
259 | rec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind, |
260 | split_join_branch_bag& r_bag) | |
4569a895 | 261 | { |
47bea7b8 | 262 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 263 | const size_type lhs_leafs = recursive_count_leafs(p_l); |
4569a895 | 264 | const size_type rhs_leafs = recursive_count_leafs(p_r); |
47bea7b8 | 265 | #endif |
4569a895 | 266 | |
8fc81078 | 267 | _GLIBCXX_DEBUG_ASSERT(p_r != 0); |
4569a895 | 268 | node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag); |
47bea7b8 BK |
269 | _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs); |
270 | return p_ret; | |
4569a895 AT |
271 | } |
272 | ||
273 | PB_DS_CLASS_T_DEC | |
274 | typename PB_DS_CLASS_C_DEC::node_pointer | |
275 | PB_DS_CLASS_C_DEC:: | |
276 | rec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) | |
277 | { | |
8fc81078 PC |
278 | _GLIBCXX_DEBUG_ASSERT(p_l != 0); |
279 | _GLIBCXX_DEBUG_ASSERT(p_r != 0); | |
4569a895 | 280 | |
47bea7b8 | 281 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 282 | const size_type lhs_leafs = recursive_count_leafs(p_l); |
4569a895 | 283 | const size_type rhs_leafs = recursive_count_leafs(p_r); |
47bea7b8 | 284 | #endif |
4569a895 | 285 | |
47bea7b8 | 286 | if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this)) |
4569a895 AT |
287 | { |
288 | node_pointer p_ret = insert_branch(p_l, p_r, r_bag); | |
47bea7b8 BK |
289 | _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);) |
290 | _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == | |
291 | lhs_leafs + rhs_leafs); | |
292 | return p_ret; | |
4569a895 AT |
293 | } |
294 | ||
47bea7b8 BK |
295 | node_pointer p_pot_child = p_l->add_child(p_r, pref_begin(p_r), |
296 | pref_end(p_r), this); | |
4569a895 AT |
297 | if (p_pot_child != p_r) |
298 | { | |
47bea7b8 | 299 | node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(), |
4569a895 AT |
300 | r_bag); |
301 | ||
47bea7b8 BK |
302 | p_l->replace_child(p_new_child, pref_begin(p_new_child), |
303 | pref_end(p_new_child), this); | |
4569a895 AT |
304 | } |
305 | ||
47bea7b8 BK |
306 | _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this)); |
307 | _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs); | |
308 | return p_l; | |
4569a895 AT |
309 | } |
310 | ||
311 | PB_DS_CLASS_T_DEC | |
312 | typename PB_DS_CLASS_C_DEC::node_pointer | |
313 | PB_DS_CLASS_C_DEC:: | |
314 | rec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag) | |
315 | { | |
8fc81078 PC |
316 | _GLIBCXX_DEBUG_ASSERT(p_l != 0); |
317 | _GLIBCXX_DEBUG_ASSERT(p_r != 0); | |
4569a895 | 318 | |
47bea7b8 | 319 | #ifdef _GLIBCXX_DEBUG |
4569a895 | 320 | const size_type lhs_leafs = recursive_count_leafs(p_l); |
4569a895 | 321 | const size_type rhs_leafs = recursive_count_leafs(p_r); |
47bea7b8 BK |
322 | #endif |
323 | ||
324 | if (p_l->get_e_ind() == p_r->get_e_ind() && | |
325 | synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(), | |
326 | p_r->pref_b_it(), p_r->pref_e_it())) | |
4569a895 AT |
327 | { |
328 | for (typename internal_node::iterator it = p_r->begin(); | |
329 | it != p_r->end(); ++ it) | |
330 | { | |
47bea7b8 BK |
331 | node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this), |
332 | * it, 0, r_bag); | |
333 | p_l->replace_child(p_new_child, pref_begin(p_new_child), | |
334 | pref_end(p_new_child), this); | |
4569a895 AT |
335 | } |
336 | ||
337 | p_r->~internal_node(); | |
4569a895 | 338 | s_internal_node_allocator.deallocate(p_r, 1); |
47bea7b8 BK |
339 | _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);) |
340 | _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs); | |
341 | return p_l; | |
4569a895 AT |
342 | } |
343 | ||
47bea7b8 BK |
344 | if (p_l->get_e_ind() < p_r->get_e_ind() && |
345 | p_l->should_be_mine(p_r->pref_b_it(), p_r->pref_e_it(), 0, this)) | |
4569a895 | 346 | { |
47bea7b8 BK |
347 | node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this), |
348 | p_r, 0, r_bag); | |
349 | p_l->replace_child(p_new_child, pref_begin(p_new_child), | |
350 | pref_end(p_new_child), this); | |
351 | _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);) | |
352 | return p_l; | |
4569a895 AT |
353 | } |
354 | ||
47bea7b8 BK |
355 | if (p_r->get_e_ind() < p_l->get_e_ind() && |
356 | p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) | |
4569a895 | 357 | { |
47bea7b8 BK |
358 | node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l, |
359 | 0, r_bag); | |
4569a895 | 360 | |
47bea7b8 BK |
361 | p_r->replace_child(p_new_child, pref_begin(p_new_child), |
362 | pref_end(p_new_child), this); | |
4569a895 | 363 | |
47bea7b8 BK |
364 | _GLIBCXX_DEBUG_ONLY(p_r->assert_valid(this);) |
365 | _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_r) == lhs_leafs + rhs_leafs); | |
366 | return p_r; | |
4569a895 AT |
367 | } |
368 | ||
369 | node_pointer p_ret = insert_branch(p_l, p_r, r_bag); | |
47bea7b8 BK |
370 | _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);) |
371 | _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs); | |
372 | return p_ret; | |
4569a895 AT |
373 | } |
374 | ||
375 | PB_DS_CLASS_T_DEC | |
47bea7b8 | 376 | inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool> |
4569a895 AT |
377 | PB_DS_CLASS_C_DEC:: |
378 | insert(const_reference r_val) | |
379 | { | |
380 | node_pointer p_lf = find_imp(PB_DS_V2F(r_val)); | |
8fc81078 | 381 | if (p_lf != 0 && p_lf->m_type == pat_trie_leaf_node_type && |
47bea7b8 | 382 | synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()), PB_DS_V2F(r_val))) |
4569a895 | 383 | { |
551fe1a2 | 384 | _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(PB_DS_V2F(r_val))); |
47bea7b8 BK |
385 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
386 | return std::make_pair(iterator(p_lf), false); | |
4569a895 AT |
387 | } |
388 | ||
551fe1a2 | 389 | _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(PB_DS_V2F(r_val))); |
4569a895 AT |
390 | |
391 | leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); | |
4569a895 AT |
392 | cond_dealtor cond(p_new_lf); |
393 | ||
394 | new (p_new_lf) leaf(r_val); | |
4569a895 | 395 | apply_update(p_new_lf, (node_update* )this); |
4569a895 | 396 | cond.set_call_destructor(); |
4569a895 | 397 | split_join_branch_bag bag; |
4569a895 | 398 | bag.add_branch(); |
47bea7b8 | 399 | m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag); |
4569a895 | 400 | m_p_head->m_p_parent->m_p_parent = m_p_head; |
4569a895 | 401 | cond.set_no_action_dtor(); |
4569a895 | 402 | ++m_size; |
4569a895 | 403 | update_min_max_for_inserted_leaf(p_new_lf); |
551fe1a2 | 404 | _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) |
47bea7b8 BK |
405 | _GLIBCXX_DEBUG_ONLY(assert_valid();) |
406 | return std::make_pair(point_iterator(p_new_lf), true); | |
4569a895 AT |
407 | } |
408 | ||
409 | PB_DS_CLASS_T_DEC | |
410 | typename PB_DS_CLASS_C_DEC::size_type | |
411 | PB_DS_CLASS_C_DEC:: | |
412 | keys_diff_ind(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r) | |
413 | { | |
414 | size_type diff_pos = 0; | |
4569a895 AT |
415 | while (b_l != e_l) |
416 | { | |
417 | if (b_r == e_r) | |
418 | return (diff_pos); | |
4569a895 AT |
419 | if (e_access_traits::e_pos(*b_l) != e_access_traits::e_pos(*b_r)) |
420 | return (diff_pos); | |
4569a895 AT |
421 | ++b_l; |
422 | ++b_r; | |
4569a895 AT |
423 | ++diff_pos; |
424 | } | |
47bea7b8 BK |
425 | _GLIBCXX_DEBUG_ASSERT(b_r != e_r); |
426 | return diff_pos; | |
4569a895 AT |
427 | } |
428 | ||
429 | PB_DS_CLASS_T_DEC | |
430 | typename PB_DS_CLASS_C_DEC::internal_node_pointer | |
431 | PB_DS_CLASS_C_DEC:: | |
432 | insert_branch(node_pointer p_l, node_pointer p_r, split_join_branch_bag& r_bag) | |
433 | { | |
47bea7b8 BK |
434 | typename synth_e_access_traits::const_iterator left_b_it = pref_begin(p_l); |
435 | typename synth_e_access_traits::const_iterator left_e_it = pref_end(p_l); | |
436 | typename synth_e_access_traits::const_iterator right_b_it = pref_begin(p_r); | |
437 | typename synth_e_access_traits::const_iterator right_e_it = pref_end(p_r); | |
4569a895 | 438 | |
47bea7b8 BK |
439 | const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it, |
440 | right_b_it, right_e_it); | |
4569a895 AT |
441 | |
442 | internal_node_pointer p_new_nd = r_bag.get_branch(); | |
4569a895 | 443 | new (p_new_nd) internal_node(diff_ind, left_b_it); |
47bea7b8 BK |
444 | p_new_nd->add_child(p_l, left_b_it, left_e_it, this); |
445 | p_new_nd->add_child(p_r, right_b_it, right_e_it, this); | |
4569a895 AT |
446 | p_l->m_p_parent = p_new_nd; |
447 | p_r->m_p_parent = p_new_nd; | |
47bea7b8 BK |
448 | _GLIBCXX_DEBUG_ONLY(p_new_nd->assert_valid(this);) |
449 | return (p_new_nd); | |
4569a895 AT |
450 | } |
451 | ||
452 | PB_DS_CLASS_T_DEC | |
453 | void | |
454 | PB_DS_CLASS_C_DEC:: | |
455 | update_min_max_for_inserted_leaf(leaf_pointer p_new_lf) | |
456 | { | |
457 | if (m_p_head->m_p_min == m_p_head || | |
47bea7b8 | 458 | synth_e_access_traits::cmp_keys(PB_DS_V2F(p_new_lf->value()), |
4569a895 AT |
459 | PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value()))) |
460 | m_p_head->m_p_min = p_new_lf; | |
461 | ||
462 | if (m_p_head->m_p_max == m_p_head || | |
47bea7b8 | 463 | synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_max)->value()), PB_DS_V2F(p_new_lf->value()))) |
4569a895 AT |
464 | m_p_head->m_p_max = p_new_lf; |
465 | } |