split_join_fn_imps.hpp revision 296373
190075Sobrien// -*- C++ -*- 290075Sobrien 390075Sobrien// Copyright (C) 2005, 2006 Free Software Foundation, Inc. 490075Sobrien// 590075Sobrien// This file is part of the GNU ISO C++ Library. This library is free 690075Sobrien// software; you can redistribute it and/or modify it under the terms 790075Sobrien// of the GNU General Public License as published by the Free Software 890075Sobrien// Foundation; either version 2, or (at your option) any later 990075Sobrien// version. 1090075Sobrien 1190075Sobrien// This library is distributed in the hope that it will be useful, but 1290075Sobrien// WITHOUT ANY WARRANTY; without even the implied warranty of 1390075Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 1490075Sobrien// General Public License for more details. 1590075Sobrien 1690075Sobrien// You should have received a copy of the GNU General Public License 1790075Sobrien// along with this library; see the file COPYING. If not, write to 1890075Sobrien// the Free Software Foundation, 59 Temple Place - Suite 330, Boston, 1990075Sobrien// MA 02111-1307, USA. 2090075Sobrien 2190075Sobrien// As a special exception, you may use this file as part of a free 2290075Sobrien// software library without restriction. Specifically, if other files 2390075Sobrien// instantiate templates or use macros or inline functions from this 2490075Sobrien// file, or you compile this file and link it with other files to 2590075Sobrien// produce an executable, this file does not by itself cause the 26169689Skan// resulting executable to be covered by the GNU General Public 27169689Skan// License. This exception does not however invalidate any other 2890075Sobrien// reasons why the executable file might be covered by the GNU General 2990075Sobrien// Public License. 3090075Sobrien 3190075Sobrien// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 3290075Sobrien 3390075Sobrien// Permission to use, copy, modify, sell, and distribute this software 3490075Sobrien// is hereby granted without fee, provided that the above copyright 3590075Sobrien// notice appears in all copies, and that both that copyright notice 3690075Sobrien// and this permission notice appear in supporting documentation. None 3790075Sobrien// of the above authors, nor IBM Haifa Research Laboratories, make any 3890075Sobrien// representation about the suitability of this software for any 3990075Sobrien// purpose. It is provided "as is" without express or implied 4090075Sobrien// warranty. 4190075Sobrien 42132718Skan/** 4390075Sobrien * @file split_join_fn_imps.hpp 4490075Sobrien * Contains an implementation class for bin_search_tree_. 4590075Sobrien */ 4690075Sobrien 47169689SkanPB_DS_CLASS_T_DEC 4890075Sobrienbool 4990075SobrienPB_DS_CLASS_C_DEC:: 5090075Sobrienjoin_prep(PB_DS_CLASS_C_DEC& other) 5190075Sobrien{ 5290075Sobrien _GLIBCXX_DEBUG_ONLY(assert_valid();) 5390075Sobrien _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 5490075Sobrien if (other.m_size == 0) 5590075Sobrien return false; 5690075Sobrien 5790075Sobrien if (m_size == 0) 5890075Sobrien { 5990075Sobrien value_swap(other); 6090075Sobrien return false; 6190075Sobrien } 6290075Sobrien 6390075Sobrien const bool greater = Cmp_Fn::operator()(PB_DS_V2F(m_p_head->m_p_right->m_value), PB_DS_V2F(other.m_p_head->m_p_left->m_value)); 6490075Sobrien 6590075Sobrien const bool lesser = Cmp_Fn::operator()(PB_DS_V2F(other.m_p_head->m_p_right->m_value), PB_DS_V2F(m_p_head->m_p_left->m_value)); 6690075Sobrien 6790075Sobrien if (!greater && !lesser) 6890075Sobrien __throw_join_error(); 6990075Sobrien 70169689Skan if (lesser) 7190075Sobrien value_swap(other); 7290075Sobrien 7390075Sobrien m_size += other.m_size; 7490075Sobrien _GLIBCXX_DEBUG_ONLY(map_debug_base::join(other);) 7590075Sobrien return true; 7690075Sobrien} 7790075Sobrien 7890075SobrienPB_DS_CLASS_T_DEC 7990075Sobrienvoid 8090075SobrienPB_DS_CLASS_C_DEC:: 8190075Sobrienjoin_finish(PB_DS_CLASS_C_DEC& other) 8290075Sobrien{ 8390075Sobrien initialize_min_max(); 8490075Sobrien other.initialize(); 8590075Sobrien} 8690075Sobrien 8790075SobrienPB_DS_CLASS_T_DEC 8890075Sobrienbool 8990075SobrienPB_DS_CLASS_C_DEC:: 9090075Sobriensplit_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) 9190075Sobrien{ 9290075Sobrien _GLIBCXX_DEBUG_ONLY(assert_valid();) 9390075Sobrien _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 9490075Sobrien other.clear(); 9590075Sobrien 9690075Sobrien if (m_size == 0) 9790075Sobrien { 9890075Sobrien _GLIBCXX_DEBUG_ONLY(assert_valid();) 9990075Sobrien _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 10090075Sobrien return false; 10190075Sobrien } 10290075Sobrien 10390075Sobrien if (Cmp_Fn::operator()(r_key, PB_DS_V2F(m_p_head->m_p_left->m_value))) 10490075Sobrien { 10590075Sobrien value_swap(other); 10690075Sobrien _GLIBCXX_DEBUG_ONLY(assert_valid();) 10790075Sobrien _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 108169689Skan return false; 109169689Skan } 110169689Skan 111169689Skan if (!Cmp_Fn::operator()(r_key, PB_DS_V2F(m_p_head->m_p_right->m_value))) 112169689Skan { 113169689Skan _GLIBCXX_DEBUG_ONLY(assert_valid();) 11490075Sobrien _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 11590075Sobrien return false; 11690075Sobrien } 117132718Skan 118 if (m_size == 1) 119 { 120 value_swap(other); 121 _GLIBCXX_DEBUG_ONLY(assert_valid();) 122 _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 123 return false; 124 } 125 126 _GLIBCXX_DEBUG_ONLY(map_debug_base::split(r_key,(Cmp_Fn& )(*this), other);) 127 return true; 128} 129 130PB_DS_CLASS_T_DEC 131void 132PB_DS_CLASS_C_DEC:: 133split_finish(PB_DS_CLASS_C_DEC& other) 134{ 135 other.initialize_min_max(); 136 other.m_size = std::distance(other.begin(), other.end()); 137 m_size -= other.m_size; 138 initialize_min_max(); 139 _GLIBCXX_DEBUG_ONLY(assert_valid();) 140 _GLIBCXX_DEBUG_ONLY(other.assert_valid();) 141} 142 143PB_DS_CLASS_T_DEC 144typename PB_DS_CLASS_C_DEC::size_type 145PB_DS_CLASS_C_DEC:: 146recursive_count(node_pointer p) const 147{ 148 if (p == NULL) 149 return 0; 150 return 1 + recursive_count(p->m_p_left) + recursive_count(p->m_p_right); 151} 152 153