1275072Semaste// -*- C++ -*-
2275072Semaste
3275072Semaste// Copyright (C) 2005-2015 Free Software Foundation, Inc.
4275072Semaste//
5275072Semaste// This file is part of the GNU ISO C++ Library.  This library is free
6275072Semaste// software; you can redistribute it and/or modify it under the terms
7275072Semaste// of the GNU General Public License as published by the Free Software
8275072Semaste// Foundation; either version 3, or (at your option) any later
9275072Semaste// version.
10275072Semaste
11275072Semaste// This library is distributed in the hope that it will be useful, but
12275072Semaste// WITHOUT ANY WARRANTY; without even the implied warranty of
13275072Semaste// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14275072Semaste// General Public License for more details.
15275072Semaste
16275072Semaste// Under Section 7 of GPL version 3, you are granted additional
17288943Sdim// permissions described in the GCC Runtime Library Exception, version
18275072Semaste// 3.1, as published by the Free Software Foundation.
19296417Sdim
20296417Sdim// You should have received a copy of the GNU General Public License and
21275072Semaste// a copy of the GCC Runtime Library Exception along with this program;
22296417Sdim// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23296417Sdim// <http://www.gnu.org/licenses/>.
24280031Sdim
25275072Semaste// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26275072Semaste
27275072Semaste// Permission to use, copy, modify, sell, and distribute this software
28275072Semaste// is hereby granted without fee, provided that the above copyright
29275072Semaste// notice appears in all copies, and that both that copyright notice
30275072Semaste// and this permission notice appear in supporting documentation. None
31275072Semaste// of the above authors, nor IBM Haifa Research Laboratories, make any
32275072Semaste// representation about the suitability of this software for any
33296417Sdim// purpose. It is provided "as is" without express or implied
34296417Sdim// warranty.
35296417Sdim
36296417Sdim/**
37296417Sdim * @file bin_search_tree_/find_fn_imps.hpp
38296417Sdim * Contains an implementation class for bin_search_tree_.
39296417Sdim */
40296417Sdim
41296417SdimPB_DS_CLASS_T_DEC
42296417Sdiminline typename PB_DS_CLASS_C_DEC::point_const_iterator
43296417SdimPB_DS_CLASS_C_DEC::
44296417Sdimlower_bound(key_const_reference r_key) const
45296417Sdim{
46296417Sdim  node_pointer p_pot = m_p_head;
47296417Sdim  node_pointer p_nd = m_p_head->m_p_parent;
48296417Sdim
49296417Sdim  while (p_nd != 0)
50275072Semaste    if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
51275072Semaste      p_nd = p_nd->m_p_right;
52275072Semaste    else
53275072Semaste      {
54275072Semaste	p_pot = p_nd;
55275072Semaste	p_nd = p_nd->m_p_left;
56275072Semaste      }
57275072Semaste  return iterator(p_pot);
58275072Semaste}
59275072Semaste
60275072SemastePB_DS_CLASS_T_DEC
61275072Semasteinline typename PB_DS_CLASS_C_DEC::point_iterator
62275072SemastePB_DS_CLASS_C_DEC::
63280031Sdimlower_bound(key_const_reference r_key)
64280031Sdim{
65288943Sdim  node_pointer p_pot = m_p_head;
66288943Sdim  node_pointer p_nd = m_p_head->m_p_parent;
67288943Sdim
68288943Sdim  while (p_nd != 0)
69288943Sdim    if (Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
70288943Sdim      p_nd = p_nd->m_p_right;
71288943Sdim    else
72288943Sdim      {
73288943Sdim	p_pot = p_nd;
74288943Sdim	p_nd = p_nd->m_p_left;
75288943Sdim      }
76275072Semaste  return iterator(p_pot);
77275072Semaste}
78275072Semaste
79275072SemastePB_DS_CLASS_T_DEC
80275072Semasteinline typename PB_DS_CLASS_C_DEC::point_const_iterator
81275072SemastePB_DS_CLASS_C_DEC::
82275072Semasteupper_bound(key_const_reference r_key) const
83275072Semaste{
84275072Semaste  node_pointer p_pot = m_p_head;
85275072Semaste  node_pointer p_nd = m_p_head->m_p_parent;
86275072Semaste
87275072Semaste  while (p_nd != 0)
88275072Semaste    if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
89296417Sdim      {
90275072Semaste	p_pot = p_nd;
91296417Sdim	p_nd = p_nd->m_p_left;
92275072Semaste      }
93296417Sdim    else
94296417Sdim      p_nd = p_nd->m_p_right;
95275072Semaste  return const_iterator(p_pot);
96296417Sdim}
97296417Sdim
98296417SdimPB_DS_CLASS_T_DEC
99296417Sdiminline typename PB_DS_CLASS_C_DEC::point_iterator
100296417SdimPB_DS_CLASS_C_DEC::
101296417Sdimupper_bound(key_const_reference r_key)
102296417Sdim{
103296417Sdim  node_pointer p_pot = m_p_head;
104296417Sdim  node_pointer p_nd = m_p_head->m_p_parent;
105296417Sdim
106296417Sdim  while (p_nd != 0)
107296417Sdim    if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
108296417Sdim      {
109296417Sdim	p_pot = p_nd;
110296417Sdim	p_nd = p_nd->m_p_left;
111296417Sdim      }
112296417Sdim    else
113296417Sdim      p_nd = p_nd->m_p_right;
114296417Sdim  return point_iterator(p_pot);
115296417Sdim}
116275072Semaste
117275072SemastePB_DS_CLASS_T_DEC
118296417Sdiminline typename PB_DS_CLASS_C_DEC::point_iterator
119296417SdimPB_DS_CLASS_C_DEC::
120275072Semastefind(key_const_reference r_key)
121296417Sdim{
122296417Sdim  PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
123275072Semaste  node_pointer p_pot = m_p_head;
124296417Sdim  node_pointer p_nd = m_p_head->m_p_parent;
125296417Sdim
126296417Sdim  while (p_nd != 0)
127296417Sdim    if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
128296417Sdim      {
129275072Semaste	p_pot = p_nd;
130296417Sdim	p_nd = p_nd->m_p_left;
131296417Sdim      }
132296417Sdim    else
133296417Sdim      p_nd = p_nd->m_p_right;
134275072Semaste
135296417Sdim  node_pointer ret = p_pot;
136296417Sdim  if (p_pot != m_p_head)
137296417Sdim    {
138275072Semaste      const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value));
139275072Semaste      if (__cmp)
140275072Semaste	ret = m_p_head;
141275072Semaste    }
142296417Sdim  return point_iterator(ret);
143296417Sdim}
144296417Sdim
145296417SdimPB_DS_CLASS_T_DEC
146296417Sdiminline typename PB_DS_CLASS_C_DEC::point_const_iterator
147296417SdimPB_DS_CLASS_C_DEC::
148275072Semastefind(key_const_reference r_key) const
149275072Semaste{
150275072Semaste  PB_DS_STRUCT_ONLY_ASSERT_VALID((*this))
151296417Sdim  node_pointer p_pot = m_p_head;
152275072Semaste  node_pointer p_nd = m_p_head->m_p_parent;
153296417Sdim
154275072Semaste  while (p_nd != 0)
155275072Semaste    if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
156275072Semaste      {
157275072Semaste	p_pot = p_nd;
158275072Semaste	p_nd = p_nd->m_p_left;
159275072Semaste      }
160296417Sdim    else
161296417Sdim      p_nd = p_nd->m_p_right;
162296417Sdim
163296417Sdim  node_pointer ret = p_pot;
164296417Sdim  if (p_pot != m_p_head)
165296417Sdim    {
166275072Semaste      const bool __cmp = Cmp_Fn::operator()(r_key, PB_DS_V2F(p_pot->m_value));
167275072Semaste      if (__cmp)
168275072Semaste	ret = m_p_head;
169275072Semaste    }
170275072Semaste  return point_const_iterator(ret);
171275072Semaste}
172288943Sdim