libstdc++-v3/include/ext/pb_assoc/detail/bin_search_tree_/split_join_fn_imps.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005 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
   7 // terms of the GNU General Public License as published by the
   8 // Free Software Foundation; either version 2, or (at your option)
   9 // any later version.
  10
  11 // This library is distributed in the hope that it will be useful,
  12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  14 // GNU General Public License for more details.
  15
  16 // You should have received a copy of the GNU General Public License along
  17 // with this library; see the file COPYING.  If not, write to the Free
  18 // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
  19 // USA.
  20
  21 // As a special exception, you may use this file as part of a free software
  22 // library without restriction.  Specifically, if other files instantiate
  23 // templates or use macros or inline functions from this file, or you compile
  24 // this file and link it with other files to produce an executable, this
  25 // file does not by itself cause the resulting executable to be covered by
  26 // the GNU General Public License.  This exception does not however
  27 // invalidate any other reasons why the executable file might be covered by
  28 // the GNU General Public License.
  29
  30 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  31
  32 // Permission to use, copy, modify, sell, and distribute this software
  33 // is hereby granted without fee, provided that the above copyright
  34 // notice appears in all copies, and that both that copyright notice and
  35 // this permission notice appear in supporting documentation. None of
  36 // the above authors, nor IBM Haifa Research Laboratories, make any
  37 // representation about the suitability of this software for any
  38 // purpose. It is provided "as is" without express or implied warranty.
  39
  40 /**
  41  * @file split_join_fn_imps.hpp
  42  * Contains an implementation class for bin_search_tree_.
  43  */
  44
  45 PB_ASSOC_CLASS_T_DEC
  46 bool
  47 PB_ASSOC_CLASS_C_DEC::
  48 join_prep(PB_ASSOC_CLASS_C_DEC& r_other)
  49 {
  50   PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
  51     PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
  52
  53     if (r_other.m_size == 0)
  54       return (false);
  55
  56   if (m_size == 0)
  57     {
  58       swap(r_other);
  59
  60       return (false);
  61     }
  62
  63   const bool greater = Cmp_Fn::operator()(
  64                                           PB_ASSOC_V2F(m_p_head->m_p_right->m_value),
  65                                           PB_ASSOC_V2F(r_other.m_p_head->m_p_left->m_value));
  66
  67   const bool lesser = Cmp_Fn::operator()(
  68                                          PB_ASSOC_V2F(r_other.m_p_head->m_p_right->m_value),
  69                                          PB_ASSOC_V2F(m_p_head->m_p_left->m_value));
  70
  71   if (!greater&&  !lesser)
  72     throw cannot_join();
  73
  74   if (lesser)
  75     swap(r_other);
  76
  77   m_size += r_other.m_size;
  78
  79 #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
  80   for (const_iterator other_it = r_other.begin(); other_it != r_other.end();
  81        ++other_it)
  82     {
  83       my_map_debug_base::insert_new(PB_ASSOC_V2F(*other_it));
  84       r_other.my_map_debug_base::erase_existing(PB_ASSOC_V2F(*other_it));
  85     }
  86 #endif // PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
  87
  88   return (true);
  89 }
  90
  91 PB_ASSOC_CLASS_T_DEC
  92 void
  93 PB_ASSOC_CLASS_C_DEC::
  94 join_finish(PB_ASSOC_CLASS_C_DEC& r_other)
  95 {
  96   initialize_min_max();
  97
  98   r_other.initialize();
  99 }
 100
 101 PB_ASSOC_CLASS_T_DEC
 102 bool
 103 PB_ASSOC_CLASS_C_DEC::
 104 split_prep(const_key_reference r_key, PB_ASSOC_CLASS_C_DEC& r_other)
 105 {
 106   PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
 107     PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
 108
 109     r_other.clear();
 110
 111   if (m_size == 0)
 112     {
 113       PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
 114         PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
 115
 116         return (false);
 117     }
 118
 119   if (Cmp_Fn::operator()(r_key, PB_ASSOC_V2F(m_p_head->m_p_left->m_value)))
 120     {
 121       swap(r_other);
 122
 123       PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
 124         PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
 125
 126         return (false);
 127     }
 128
 129   if (!Cmp_Fn::operator()(
 130                           r_key,
 131                           PB_ASSOC_V2F(m_p_head->m_p_right->m_value)))
 132     {
 133       PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
 134         PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
 135
 136         return (false);
 137     }
 138
 139   if (m_size == 1)
 140     {
 141       swap(r_other);
 142
 143       PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
 144         PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
 145
 146         return (false);
 147     }
 148
 149 #ifdef PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
 150   for (const_iterator it = begin(); it != end(); ++it)
 151     if (Cmp_Fn::operator()(
 152                            r_key,
 153                            PB_ASSOC_V2F(*it)))
 154       {
 155         my_map_debug_base::erase_existing(PB_ASSOC_V2F(*it));
 156         r_other.my_map_debug_base::insert_new(PB_ASSOC_V2F(*it));
 157       }
 158 #endif // PB_ASSOC_BIN_SEARCH_TREE_DEBUG_
 159
 160   return (true);
 161 }
 162
 163 PB_ASSOC_CLASS_T_DEC
 164 void
 165 PB_ASSOC_CLASS_C_DEC::
 166 split_finish(PB_ASSOC_CLASS_C_DEC& r_other)
 167 {
 168   r_other.m_size = r_other.recursive_count(r_other.m_p_head->m_p_parent);
 169
 170   r_other.initialize_min_max();
 171
 172   m_size -= r_other.m_size;
 173
 174   initialize_min_max();
 175
 176   PB_ASSOC_DBG_ONLY(assert_valid(true, true);)
 177     PB_ASSOC_DBG_ONLY(r_other.assert_valid(true, true);)
 178     }
 179
 180 PB_ASSOC_CLASS_T_DEC
 181 typename PB_ASSOC_CLASS_C_DEC::size_type
 182 PB_ASSOC_CLASS_C_DEC::
 183 recursive_count(node_pointer p_nd) const
 184 {
 185   if (p_nd == NULL)
 186     return (0);
 187
 188   return (1 +
 189           recursive_count(p_nd->m_p_left) +
 190           recursive_count(p_nd->m_p_right));
 191 }
 192