libstdc++
insert_join_fn_imps.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc.
00004 //
00005 // This file is part of the GNU ISO C++ Library.  This library is free
00006 // software; you can redistribute it and/or modify it under the terms
00007 // of the GNU General Public License as published by the Free Software
00008 // Foundation; either version 3, or (at your option) any later
00009 // version.
00010 
00011 // This library is distributed in the hope that it will be useful, but
00012 // WITHOUT ANY WARRANTY; without even the implied warranty of
00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00014 // General Public License for more details.
00015 
00016 // Under Section 7 of GPL version 3, you are granted additional
00017 // permissions described in the GCC Runtime Library Exception, version
00018 // 3.1, as published by the Free Software Foundation.
00019 
00020 // You should have received a copy of the GNU General Public License and
00021 // a copy of the GCC Runtime Library Exception along with this program;
00022 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00023 // <http://www.gnu.org/licenses/>.
00024 
00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00026 
00027 // Permission to use, copy, modify, sell, and distribute this software
00028 // is hereby granted without fee, provided that the above copyright
00029 // notice appears in all copies, and that both that copyright notice
00030 // and this permission notice appear in supporting documentation. None
00031 // of the above authors, nor IBM Haifa Research Laboratories, make any
00032 // representation about the suitability of this software for any
00033 // purpose. It is provided "as is" without express or implied
00034 // warranty.
00035 
00036 /**
00037  * @file pat_trie_/insert_join_fn_imps.hpp
00038  * Contains an implementation class for pat_trie.
00039  */
00040 
00041 PB_DS_CLASS_T_DEC
00042 void
00043 PB_DS_CLASS_C_DEC::
00044 join(PB_DS_CLASS_C_DEC& other)
00045 {
00046   PB_DS_ASSERT_VALID((*this))
00047   PB_DS_ASSERT_VALID(other)
00048   branch_bag bag;
00049   if (!join_prep(other, bag))
00050     {
00051       PB_DS_ASSERT_VALID((*this))
00052       PB_DS_ASSERT_VALID(other)
00053       return;
00054     }
00055 
00056   m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent,
00057                   other.m_p_head->m_p_parent, 0, bag);
00058 
00059   m_p_head->m_p_parent->m_p_parent = m_p_head;
00060   m_size += other.m_size;
00061   other.initialize();
00062   PB_DS_ASSERT_VALID(other)
00063   m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent);
00064   m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent);
00065   PB_DS_ASSERT_VALID((*this))
00066 }
00067 
00068 PB_DS_CLASS_T_DEC
00069 bool
00070 PB_DS_CLASS_C_DEC::
00071 join_prep(PB_DS_CLASS_C_DEC& other, branch_bag& r_bag)
00072 {
00073   PB_DS_ASSERT_VALID((*this))
00074   PB_DS_ASSERT_VALID(other)
00075   if (other.m_size == 0)
00076     return false;
00077 
00078   if (m_size == 0)
00079     {
00080       value_swap(other);
00081       return false;
00082     }
00083 
00084   const bool greater =
00085     synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value()),
00086                     PB_DS_V2F(static_cast<leaf_const_pointer>(other.m_p_head->m_p_min)->value()));
00087 
00088   const bool lesser =
00089     synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(other.m_p_head->m_p_max)->value()),
00090                     PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value()));
00091 
00092   if (!greater && !lesser)
00093     __throw_join_error();
00094 
00095   rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag);
00096   _GLIBCXX_DEBUG_ONLY(debug_base::join(other, false);)
00097   return true;
00098 }
00099 
00100 PB_DS_CLASS_T_DEC
00101 void
00102 PB_DS_CLASS_C_DEC::
00103 rec_join_prep(node_const_pointer p_l, node_const_pointer p_r, 
00104           branch_bag& r_bag)
00105 {
00106   if (p_l->m_type == leaf_node)
00107     {
00108       if (p_r->m_type == leaf_node)
00109     {
00110       rec_join_prep(static_cast<leaf_const_pointer>(p_l),
00111             static_cast<leaf_const_pointer>(p_r), r_bag);
00112       return;
00113     }
00114 
00115       _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node);
00116       rec_join_prep(static_cast<leaf_const_pointer>(p_l),
00117             static_cast<inode_const_pointer>(p_r), r_bag);
00118       return;
00119     }
00120 
00121   _GLIBCXX_DEBUG_ASSERT(p_l->m_type == i_node);
00122   if (p_r->m_type == leaf_node)
00123     {
00124       rec_join_prep(static_cast<inode_const_pointer>(p_l),
00125             static_cast<leaf_const_pointer>(p_r), r_bag);
00126       return;
00127     }
00128 
00129   _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node);
00130 
00131   rec_join_prep(static_cast<inode_const_pointer>(p_l),
00132         static_cast<inode_const_pointer>(p_r), r_bag);
00133 }
00134 
00135 PB_DS_CLASS_T_DEC
00136 void
00137 PB_DS_CLASS_C_DEC::
00138 rec_join_prep(leaf_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/,
00139           branch_bag& r_bag)
00140 { r_bag.add_branch(); }
00141 
00142 PB_DS_CLASS_T_DEC
00143 void
00144 PB_DS_CLASS_C_DEC::
00145 rec_join_prep(leaf_const_pointer /*p_l*/, inode_const_pointer /*p_r*/,
00146           branch_bag& r_bag)
00147 { r_bag.add_branch(); }
00148 
00149 PB_DS_CLASS_T_DEC
00150 void
00151 PB_DS_CLASS_C_DEC::
00152 rec_join_prep(inode_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/,
00153           branch_bag& r_bag)
00154 { r_bag.add_branch(); }
00155 
00156 PB_DS_CLASS_T_DEC
00157 void
00158 PB_DS_CLASS_C_DEC::
00159 rec_join_prep(inode_const_pointer p_l, inode_const_pointer p_r,
00160           branch_bag& r_bag)
00161 {
00162   if (p_l->get_e_ind() == p_r->get_e_ind() &&
00163       synth_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(),
00164                         p_r->pref_b_it(), p_r->pref_e_it()))
00165     {
00166       for (typename inode::const_iterator it = p_r->begin();
00167        it != p_r->end(); ++ it)
00168     {
00169       node_const_pointer p_l_join_child = p_l->get_join_child(*it, this);
00170       if (p_l_join_child != 0)
00171         rec_join_prep(p_l_join_child, * it, r_bag);
00172     }
00173       return;
00174     }
00175 
00176   if (p_r->get_e_ind() < p_l->get_e_ind() &&
00177       p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
00178     {
00179       node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this);
00180       if (p_r_join_child != 0)
00181     rec_join_prep(p_r_join_child, p_l, r_bag);
00182       return;
00183     }
00184 
00185   if (p_r->get_e_ind() < p_l->get_e_ind() &&
00186       p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
00187     {
00188       node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this);
00189       if (p_r_join_child != 0)
00190     rec_join_prep(p_r_join_child, p_l, r_bag);
00191       return;
00192     }
00193   r_bag.add_branch();
00194 }
00195 
00196 PB_DS_CLASS_T_DEC
00197 typename PB_DS_CLASS_C_DEC::node_pointer
00198 PB_DS_CLASS_C_DEC::
00199 rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, 
00200      branch_bag& r_bag)
00201 {
00202   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
00203   if (p_l == 0)
00204     {
00205       apply_update(p_r, (node_update*)this);
00206       return (p_r);
00207     }
00208 
00209   if (p_l->m_type == leaf_node)
00210     {
00211       if (p_r->m_type == leaf_node)
00212     {
00213       node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l),
00214                     static_cast<leaf_pointer>(p_r), r_bag);
00215       apply_update(p_ret, (node_update*)this);
00216       return p_ret;
00217     }
00218 
00219       _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node);
00220       node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l),
00221                     static_cast<inode_pointer>(p_r),
00222                     checked_ind, r_bag);
00223       apply_update(p_ret, (node_update*)this);
00224       return p_ret;
00225     }
00226 
00227   _GLIBCXX_DEBUG_ASSERT(p_l->m_type == i_node);
00228   if (p_r->m_type == leaf_node)
00229     {
00230       node_pointer p_ret = rec_join(static_cast<inode_pointer>(p_l),
00231                     static_cast<leaf_pointer>(p_r),
00232                     checked_ind, r_bag);
00233       apply_update(p_ret, (node_update*)this);
00234       return p_ret;
00235     }
00236 
00237   _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node);
00238   node_pointer p_ret = rec_join(static_cast<inode_pointer>(p_l),
00239                 static_cast<inode_pointer>(p_r),
00240                 r_bag);
00241 
00242   apply_update(p_ret, (node_update*)this);
00243   return p_ret;
00244 }
00245 
00246 PB_DS_CLASS_T_DEC
00247 typename PB_DS_CLASS_C_DEC::node_pointer
00248 PB_DS_CLASS_C_DEC::
00249 rec_join(leaf_pointer p_l, leaf_pointer p_r, branch_bag& r_bag)
00250 {
00251   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
00252   if (p_l == 0)
00253     return (p_r);
00254   node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
00255   _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == 2);
00256   return p_ret;
00257 }
00258 
00259 PB_DS_CLASS_T_DEC
00260 typename PB_DS_CLASS_C_DEC::node_pointer
00261 PB_DS_CLASS_C_DEC::
00262 rec_join(leaf_pointer p_l, inode_pointer p_r, size_type checked_ind,
00263      branch_bag& r_bag)
00264 {
00265 #ifdef _GLIBCXX_DEBUG
00266   const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l);
00267   const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r);
00268 #endif
00269 
00270   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
00271   node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag);
00272   _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == lhs_leafs + rhs_leafs);
00273   return p_ret;
00274 }
00275 
00276 PB_DS_CLASS_T_DEC
00277 typename PB_DS_CLASS_C_DEC::node_pointer
00278 PB_DS_CLASS_C_DEC::
00279 rec_join(inode_pointer p_l, leaf_pointer p_r, size_type checked_ind, branch_bag& r_bag)
00280 {
00281   _GLIBCXX_DEBUG_ASSERT(p_l != 0);
00282   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
00283 
00284 #ifdef _GLIBCXX_DEBUG
00285   const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l);
00286   const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r);
00287 #endif
00288 
00289   if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this))
00290     {
00291       node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
00292       PB_DS_ASSERT_NODE_VALID(p_ret)
00293       _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) ==
00294                     lhs_leafs + rhs_leafs);
00295       return p_ret;
00296     }
00297 
00298   node_pointer p_pot_child = p_l->add_child(p_r, pref_begin(p_r),
00299                         pref_end(p_r), this);
00300   if (p_pot_child != p_r)
00301     {
00302       node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(),
00303                       r_bag);
00304 
00305       p_l->replace_child(p_new_child, pref_begin(p_new_child),
00306              pref_end(p_new_child), this);
00307     }
00308 
00309   PB_DS_ASSERT_NODE_VALID(p_l)
00310   _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_l) == lhs_leafs + rhs_leafs);
00311   return p_l;
00312 }
00313 
00314 PB_DS_CLASS_T_DEC
00315 typename PB_DS_CLASS_C_DEC::node_pointer
00316 PB_DS_CLASS_C_DEC::
00317 rec_join(inode_pointer p_l, inode_pointer p_r, 
00318      branch_bag& r_bag)
00319 {
00320   _GLIBCXX_DEBUG_ASSERT(p_l != 0);
00321   _GLIBCXX_DEBUG_ASSERT(p_r != 0);
00322 
00323 #ifdef _GLIBCXX_DEBUG
00324   const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l);
00325   const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r);
00326 #endif
00327 
00328   if (p_l->get_e_ind() == p_r->get_e_ind() &&
00329       synth_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(),
00330                         p_r->pref_b_it(), p_r->pref_e_it()))
00331     {
00332       for (typename inode::iterator it = p_r->begin();
00333        it != p_r->end(); ++ it)
00334     {
00335       node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this),
00336                           * it, 0, r_bag);
00337       p_l->replace_child(p_new_child, pref_begin(p_new_child),
00338                  pref_end(p_new_child), this);
00339     }
00340 
00341       p_r->~inode();
00342       s_inode_allocator.deallocate(p_r, 1);
00343       PB_DS_ASSERT_NODE_VALID(p_l)
00344       _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_l) == lhs_leafs + rhs_leafs);
00345       return p_l;
00346     }
00347 
00348   if (p_l->get_e_ind() < p_r->get_e_ind() &&
00349       p_l->should_be_mine(p_r->pref_b_it(), p_r->pref_e_it(), 0, this))
00350     {
00351       node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this),
00352                       p_r, 0, r_bag);
00353       p_l->replace_child(p_new_child, pref_begin(p_new_child),
00354              pref_end(p_new_child), this);
00355       PB_DS_ASSERT_NODE_VALID(p_l)
00356       return p_l;
00357     }
00358 
00359   if (p_r->get_e_ind() < p_l->get_e_ind() &&
00360       p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
00361     {
00362       node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l,
00363                       0, r_bag);
00364 
00365       p_r->replace_child(p_new_child, pref_begin(p_new_child),
00366              pref_end(p_new_child), this);
00367 
00368       PB_DS_ASSERT_NODE_VALID(p_r)
00369       _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_r) == lhs_leafs + rhs_leafs);
00370       return p_r;
00371     }
00372 
00373   node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
00374   PB_DS_ASSERT_NODE_VALID(p_ret)
00375   _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_ret) == lhs_leafs + rhs_leafs);
00376   return p_ret;
00377 }
00378 
00379 PB_DS_CLASS_T_DEC
00380 inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool>
00381 PB_DS_CLASS_C_DEC::
00382 insert(const_reference r_val)
00383 {
00384   node_pointer p_lf = find_imp(PB_DS_V2F(r_val));
00385   if (p_lf != 0 && p_lf->m_type == leaf_node &&
00386       synth_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()), PB_DS_V2F(r_val)))
00387     {
00388       PB_DS_CHECK_KEY_EXISTS(PB_DS_V2F(r_val))
00389       PB_DS_ASSERT_VALID((*this))
00390       return std::make_pair(iterator(p_lf), false);
00391     }
00392 
00393   PB_DS_CHECK_KEY_DOES_NOT_EXIST(PB_DS_V2F(r_val))
00394 
00395   leaf_pointer p_new_lf = s_leaf_allocator.allocate(1);
00396   cond_dealtor cond(p_new_lf);
00397 
00398   new (p_new_lf) leaf(r_val);
00399   apply_update(p_new_lf, (node_update*)this);
00400   cond.set_call_destructor();
00401   branch_bag bag;
00402   bag.add_branch();
00403   m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag);
00404   m_p_head->m_p_parent->m_p_parent = m_p_head;
00405   cond.set_no_action_dtor();
00406   ++m_size;
00407   update_min_max_for_inserted_leaf(p_new_lf);
00408   _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));)
00409   PB_DS_ASSERT_VALID((*this))
00410   return std::make_pair(point_iterator(p_new_lf), true);
00411 }
00412 
00413 PB_DS_CLASS_T_DEC
00414 typename PB_DS_CLASS_C_DEC::size_type
00415 PB_DS_CLASS_C_DEC::
00416 keys_diff_ind(typename access_traits::const_iterator b_l,
00417           typename access_traits::const_iterator e_l,
00418           typename access_traits::const_iterator b_r,
00419           typename access_traits::const_iterator e_r)
00420 {
00421   size_type diff_pos = 0;
00422   while (b_l != e_l)
00423     {
00424       if (b_r == e_r)
00425     return (diff_pos);
00426       if (access_traits::e_pos(*b_l) != access_traits::e_pos(*b_r))
00427     return (diff_pos);
00428       ++b_l;
00429       ++b_r;
00430       ++diff_pos;
00431     }
00432   _GLIBCXX_DEBUG_ASSERT(b_r != e_r);
00433   return diff_pos;
00434 }
00435 
00436 PB_DS_CLASS_T_DEC
00437 typename PB_DS_CLASS_C_DEC::inode_pointer
00438 PB_DS_CLASS_C_DEC::
00439 insert_branch(node_pointer p_l, node_pointer p_r, branch_bag& r_bag)
00440 {
00441   typename synth_access_traits::const_iterator left_b_it = pref_begin(p_l);
00442   typename synth_access_traits::const_iterator left_e_it = pref_end(p_l);
00443   typename synth_access_traits::const_iterator right_b_it = pref_begin(p_r);
00444   typename synth_access_traits::const_iterator right_e_it = pref_end(p_r);
00445 
00446   const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it,
00447                        right_b_it, right_e_it);
00448 
00449   inode_pointer p_new_nd = r_bag.get_branch();
00450   new (p_new_nd) inode(diff_ind, left_b_it);
00451   p_new_nd->add_child(p_l, left_b_it, left_e_it, this);
00452   p_new_nd->add_child(p_r, right_b_it, right_e_it, this);
00453   p_l->m_p_parent = p_new_nd;
00454   p_r->m_p_parent = p_new_nd;
00455   PB_DS_ASSERT_NODE_VALID(p_new_nd)
00456   return (p_new_nd);
00457 }
00458 
00459 PB_DS_CLASS_T_DEC
00460 void
00461 PB_DS_CLASS_C_DEC::
00462 update_min_max_for_inserted_leaf(leaf_pointer p_new_lf)
00463 {
00464   if (m_p_head->m_p_min == m_p_head ||
00465       synth_access_traits::cmp_keys(PB_DS_V2F(p_new_lf->value()),
00466                       PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value())))
00467     m_p_head->m_p_min = p_new_lf;
00468 
00469   if (m_p_head->m_p_max == m_p_head ||
00470       synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value()), PB_DS_V2F(p_new_lf->value())))
00471     m_p_head->m_p_max = p_new_lf;
00472 }