find_fn_imps.hpp revision 1.1.1.1 
1// -*- C++ -*-
2
3// Copyright (C) 2005, 2006, 2009 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 terms
7// of the GNU General Public License as published by the Free Software
8// Foundation; either version 3, or (at your option) any later
9// version.
10
11// This library is distributed in the hope that it will be useful, but
12// WITHOUT ANY WARRANTY; without even the implied warranty of
13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
14// General Public License for more details.
15
16// Under Section 7 of GPL version 3, you are granted additional
17// permissions described in the GCC Runtime Library Exception, version
18// 3.1, as published by the Free Software Foundation.
19
20// You should have received a copy of the GNU General Public License and
21// a copy of the GCC Runtime Library Exception along with this program;
22// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23// <http://www.gnu.org/licenses/>.
24
25// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
26
27// Permission to use, copy, modify, sell, and distribute this software
28// is hereby granted without fee, provided that the above copyright
29// notice appears in all copies, and that both that copyright notice
30// and this permission notice appear in supporting documentation. None
31// of the above authors, nor IBM Haifa Research Laboratories, make any
32// representation about the suitability of this software for any
33// purpose. It is provided "as is" without express or implied
34// warranty.
35
36/**
37 * @file find_fn_imps.hpp
38 * Contains an implementation class for bin_search_tree_.
39 */
40
41PB_DS_CLASS_T_DEC
42inline typename PB_DS_CLASS_C_DEC::const_point_iterator
43PB_DS_CLASS_C_DEC::
44lower_bound(const_key_reference r_key) const
45{
46  node_pointer p_pot = m_p_head;
47  node_pointer p_nd = m_p_head->m_p_parent;
48
49  while (p_nd != NULL)
50    if (Cmp_Fn::operator()(
51			   PB_DS_V2F(p_nd->m_value),
52			   r_key))
53      p_nd = p_nd->m_p_right;
54    else
55      {
56	p_pot = p_nd;
57
58	p_nd = p_nd->m_p_left;
59      }
60
61  return (iterator(p_pot));
62}
63
64PB_DS_CLASS_T_DEC
65inline typename PB_DS_CLASS_C_DEC::point_iterator
66PB_DS_CLASS_C_DEC::
67lower_bound(const_key_reference r_key)
68{
69  node_pointer p_pot = m_p_head;
70  node_pointer p_nd = m_p_head->m_p_parent;
71
72  while (p_nd != NULL)
73    if (Cmp_Fn::operator()(
74			   PB_DS_V2F(p_nd->m_value),
75			   r_key))
76      p_nd = p_nd->m_p_right;
77    else
78      {
79	p_pot = p_nd;
80
81	p_nd = p_nd->m_p_left;
82      }
83
84  return (iterator(p_pot));
85}
86
87PB_DS_CLASS_T_DEC
88inline typename PB_DS_CLASS_C_DEC::const_point_iterator
89PB_DS_CLASS_C_DEC::
90upper_bound(const_key_reference r_key) const
91{
92  node_pointer p_pot = m_p_head;
93  node_pointer p_nd = m_p_head->m_p_parent;
94
95  while (p_nd != NULL)
96    if (Cmp_Fn::operator()(r_key,
97			   PB_DS_V2F(p_nd->m_value)))
98      {
99	p_pot = p_nd,
100
101	  p_nd = p_nd->m_p_left;
102      }
103    else
104      p_nd = p_nd->m_p_right;
105
106  return (const_iterator(p_pot));
107}
108
109PB_DS_CLASS_T_DEC
110inline typename PB_DS_CLASS_C_DEC::point_iterator
111PB_DS_CLASS_C_DEC::
112upper_bound(const_key_reference r_key)
113{
114  node_pointer p_pot = m_p_head;
115  node_pointer p_nd = m_p_head->m_p_parent;
116
117  while (p_nd != NULL)
118    if (Cmp_Fn::operator()(r_key,
119			   PB_DS_V2F(p_nd->m_value)))
120      {
121	p_pot = p_nd,
122
123	  p_nd = p_nd->m_p_left;
124      }
125    else
126      p_nd = p_nd->m_p_right;
127
128  return (point_iterator(p_pot));
129}
130
131PB_DS_CLASS_T_DEC
132inline typename PB_DS_CLASS_C_DEC::point_iterator
133PB_DS_CLASS_C_DEC::
134find(const_key_reference r_key)
135{
136  _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
137
138    node_pointer p_pot = m_p_head;
139  node_pointer p_nd = m_p_head->m_p_parent;
140
141  while (p_nd != NULL)
142    if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
143      {
144	p_pot = p_nd;
145
146	p_nd = p_nd->m_p_left;
147      }
148    else
149      p_nd = p_nd->m_p_right;
150
151  return point_iterator((p_pot != m_p_head&&  Cmp_Fn::operator()(
152								 r_key,
153								 PB_DS_V2F(p_pot->m_value)))?
154			m_p_head : p_pot);
155}
156
157PB_DS_CLASS_T_DEC
158inline typename PB_DS_CLASS_C_DEC::const_point_iterator
159PB_DS_CLASS_C_DEC::
160find(const_key_reference r_key) const
161{
162  _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();)
163
164    node_pointer p_pot = m_p_head;
165  node_pointer p_nd = m_p_head->m_p_parent;
166
167  while (p_nd != NULL)
168    if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key))
169      {
170	p_pot = p_nd;
171
172	p_nd = p_nd->m_p_left;
173      }
174    else
175      p_nd = p_nd->m_p_right;
176
177  return const_point_iterator((p_pot != m_p_head&&  Cmp_Fn::operator()(
178								       r_key,
179								       PB_DS_V2F(p_pot->m_value)))?
180			      m_p_head : p_pot);
181}
182
183