1*e4b17023SJohn Marino // -*- C++ -*-
2*e4b17023SJohn Marino
3*e4b17023SJohn Marino // Copyright (C) 2005, 2006, 2009, 2010, 2011 Free Software Foundation, Inc.
4*e4b17023SJohn Marino //
5*e4b17023SJohn Marino // This file is part of the GNU ISO C++ Library. This library is free
6*e4b17023SJohn Marino // software; you can redistribute it and/or modify it under the terms
7*e4b17023SJohn Marino // of the GNU General Public License as published by the Free Software
8*e4b17023SJohn Marino // Foundation; either version 3, or (at your option) any later
9*e4b17023SJohn Marino // version.
10*e4b17023SJohn Marino
11*e4b17023SJohn Marino // This library is distributed in the hope that it will be useful, but
12*e4b17023SJohn Marino // WITHOUT ANY WARRANTY; without even the implied warranty of
13*e4b17023SJohn Marino // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14*e4b17023SJohn Marino // General Public License for more details.
15*e4b17023SJohn Marino
16*e4b17023SJohn Marino // Under Section 7 of GPL version 3, you are granted additional
17*e4b17023SJohn Marino // permissions described in the GCC Runtime Library Exception, version
18*e4b17023SJohn Marino // 3.1, as published by the Free Software Foundation.
19*e4b17023SJohn Marino
20*e4b17023SJohn Marino // You should have received a copy of the GNU General Public License and
21*e4b17023SJohn Marino // a copy of the GCC Runtime Library Exception along with this program;
22*e4b17023SJohn Marino // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
23*e4b17023SJohn Marino // <http://www.gnu.org/licenses/>.
24*e4b17023SJohn Marino
25*e4b17023SJohn Marino // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26*e4b17023SJohn Marino
27*e4b17023SJohn Marino // Permission to use, copy, modify, sell, and distribute this software
28*e4b17023SJohn Marino // is hereby granted without fee, provided that the above copyright
29*e4b17023SJohn Marino // notice appears in all copies, and that both that copyright notice
30*e4b17023SJohn Marino // and this permission notice appear in supporting documentation. None
31*e4b17023SJohn Marino // of the above authors, nor IBM Haifa Research Laboratories, make any
32*e4b17023SJohn Marino // representation about the suitability of this software for any
33*e4b17023SJohn Marino // purpose. It is provided "as is" without express or implied
34*e4b17023SJohn Marino // warranty.
35*e4b17023SJohn Marino
36*e4b17023SJohn Marino /**
37*e4b17023SJohn Marino * @file bin_search_tree_/split_join_fn_imps.hpp
38*e4b17023SJohn Marino * Contains an implementation class for bin_search_tree_.
39*e4b17023SJohn Marino */
40*e4b17023SJohn Marino
41*e4b17023SJohn Marino PB_DS_CLASS_T_DEC
42*e4b17023SJohn Marino bool
43*e4b17023SJohn Marino PB_DS_CLASS_C_DEC::
join_prep(PB_DS_CLASS_C_DEC & other)44*e4b17023SJohn Marino join_prep(PB_DS_CLASS_C_DEC& other)
45*e4b17023SJohn Marino {
46*e4b17023SJohn Marino PB_DS_ASSERT_VALID((*this))
47*e4b17023SJohn Marino PB_DS_ASSERT_VALID(other)
48*e4b17023SJohn Marino if (other.m_size == 0)
49*e4b17023SJohn Marino return false;
50*e4b17023SJohn Marino
51*e4b17023SJohn Marino if (m_size == 0)
52*e4b17023SJohn Marino {
53*e4b17023SJohn Marino value_swap(other);
54*e4b17023SJohn Marino return false;
55*e4b17023SJohn Marino }
56*e4b17023SJohn Marino
57*e4b17023SJohn Marino const bool greater =
58*e4b17023SJohn Marino Cmp_Fn::operator()(PB_DS_V2F(m_p_head->m_p_right->m_value),
59*e4b17023SJohn Marino PB_DS_V2F(other.m_p_head->m_p_left->m_value));
60*e4b17023SJohn Marino
61*e4b17023SJohn Marino const bool lesser =
62*e4b17023SJohn Marino Cmp_Fn::operator()(PB_DS_V2F(other.m_p_head->m_p_right->m_value),
63*e4b17023SJohn Marino PB_DS_V2F(m_p_head->m_p_left->m_value));
64*e4b17023SJohn Marino
65*e4b17023SJohn Marino if (!greater && !lesser)
66*e4b17023SJohn Marino __throw_join_error();
67*e4b17023SJohn Marino
68*e4b17023SJohn Marino if (lesser)
69*e4b17023SJohn Marino value_swap(other);
70*e4b17023SJohn Marino
71*e4b17023SJohn Marino m_size += other.m_size;
72*e4b17023SJohn Marino _GLIBCXX_DEBUG_ONLY(debug_base::join(other);)
73*e4b17023SJohn Marino return true;
74*e4b17023SJohn Marino }
75*e4b17023SJohn Marino
76*e4b17023SJohn Marino PB_DS_CLASS_T_DEC
77*e4b17023SJohn Marino void
78*e4b17023SJohn Marino PB_DS_CLASS_C_DEC::
join_finish(PB_DS_CLASS_C_DEC & other)79*e4b17023SJohn Marino join_finish(PB_DS_CLASS_C_DEC& other)
80*e4b17023SJohn Marino {
81*e4b17023SJohn Marino initialize_min_max();
82*e4b17023SJohn Marino other.initialize();
83*e4b17023SJohn Marino }
84*e4b17023SJohn Marino
85*e4b17023SJohn Marino PB_DS_CLASS_T_DEC
86*e4b17023SJohn Marino bool
87*e4b17023SJohn Marino PB_DS_CLASS_C_DEC::
split_prep(key_const_reference r_key,PB_DS_CLASS_C_DEC & other)88*e4b17023SJohn Marino split_prep(key_const_reference r_key, PB_DS_CLASS_C_DEC& other)
89*e4b17023SJohn Marino {
90*e4b17023SJohn Marino PB_DS_ASSERT_VALID((*this))
91*e4b17023SJohn Marino PB_DS_ASSERT_VALID(other)
92*e4b17023SJohn Marino other.clear();
93*e4b17023SJohn Marino
94*e4b17023SJohn Marino if (m_size == 0)
95*e4b17023SJohn Marino {
96*e4b17023SJohn Marino PB_DS_ASSERT_VALID((*this))
97*e4b17023SJohn Marino PB_DS_ASSERT_VALID(other)
98*e4b17023SJohn Marino return false;
99*e4b17023SJohn Marino }
100*e4b17023SJohn Marino
101*e4b17023SJohn Marino if (Cmp_Fn::operator()(r_key, PB_DS_V2F(m_p_head->m_p_left->m_value)))
102*e4b17023SJohn Marino {
103*e4b17023SJohn Marino value_swap(other);
104*e4b17023SJohn Marino PB_DS_ASSERT_VALID((*this))
105*e4b17023SJohn Marino PB_DS_ASSERT_VALID(other)
106*e4b17023SJohn Marino return false;
107*e4b17023SJohn Marino }
108*e4b17023SJohn Marino
109*e4b17023SJohn Marino if (!Cmp_Fn::operator()(r_key, PB_DS_V2F(m_p_head->m_p_right->m_value)))
110*e4b17023SJohn Marino {
111*e4b17023SJohn Marino PB_DS_ASSERT_VALID((*this))
112*e4b17023SJohn Marino PB_DS_ASSERT_VALID(other)
113*e4b17023SJohn Marino return false;
114*e4b17023SJohn Marino }
115*e4b17023SJohn Marino
116*e4b17023SJohn Marino if (m_size == 1)
117*e4b17023SJohn Marino {
118*e4b17023SJohn Marino value_swap(other);
119*e4b17023SJohn Marino PB_DS_ASSERT_VALID((*this))
120*e4b17023SJohn Marino PB_DS_ASSERT_VALID(other)
121*e4b17023SJohn Marino return false;
122*e4b17023SJohn Marino }
123*e4b17023SJohn Marino
124*e4b17023SJohn Marino _GLIBCXX_DEBUG_ONLY(debug_base::split(r_key,(Cmp_Fn& )(*this), other);)
125*e4b17023SJohn Marino return true;
126*e4b17023SJohn Marino }
127*e4b17023SJohn Marino
128*e4b17023SJohn Marino PB_DS_CLASS_T_DEC
129*e4b17023SJohn Marino void
130*e4b17023SJohn Marino PB_DS_CLASS_C_DEC::
split_finish(PB_DS_CLASS_C_DEC & other)131*e4b17023SJohn Marino split_finish(PB_DS_CLASS_C_DEC& other)
132*e4b17023SJohn Marino {
133*e4b17023SJohn Marino other.initialize_min_max();
134*e4b17023SJohn Marino other.m_size = std::distance(other.begin(), other.end());
135*e4b17023SJohn Marino m_size -= other.m_size;
136*e4b17023SJohn Marino initialize_min_max();
137*e4b17023SJohn Marino PB_DS_ASSERT_VALID((*this))
138*e4b17023SJohn Marino PB_DS_ASSERT_VALID(other)
139*e4b17023SJohn Marino }
140*e4b17023SJohn Marino
141*e4b17023SJohn Marino PB_DS_CLASS_T_DEC
142*e4b17023SJohn Marino typename PB_DS_CLASS_C_DEC::size_type
143*e4b17023SJohn Marino PB_DS_CLASS_C_DEC::
recursive_count(node_pointer p) const144*e4b17023SJohn Marino recursive_count(node_pointer p) const
145*e4b17023SJohn Marino {
146*e4b17023SJohn Marino if (p == 0)
147*e4b17023SJohn Marino return 0;
148*e4b17023SJohn Marino return 1 + recursive_count(p->m_p_left) + recursive_count(p->m_p_right);
149*e4b17023SJohn Marino }
150*e4b17023SJohn Marino
151