URL https://opencores.org/ocsvn/scarts/scarts/trunk

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [libstdc++-v3/] [include/] [ext/] [pb_assoc/] [detail/] [tree_policy/] [order_statistics_imp.hpp] - Blame information for rev 17

Details | Compare with Previous | View Log


// -*- C++ -*-
 
// Copyright (C) 2005 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.
 
// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
 
// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// USA.
 
// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice and
// this permission notice appear in supporting documentation. None of
// the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied warranty.
 
/*
 * @file order_statistics_imp.hpp
 * Contains forward declarations for order_statistics_key
 */
 
#ifndef ORDER_STATISTICS_IMP_HPP
#define ORDER_STATISTICS_IMP_HPP
 
#define PB_ASSOC_CLASS_T_DEC \
        template<class Key, class Allocator>
 
#define PB_ASSOC_CLASS_C_DEC \
        order_statistics_key< \
                Key, \
                Allocator>
 
PB_ASSOC_CLASS_T_DEC
inline
PB_ASSOC_CLASS_C_DEC::
order_statistics_key(const_key_reference r_key) :
  m_key(r_key),
  m_rank(1)
{ }
 
PB_ASSOC_CLASS_T_DEC
inline
PB_ASSOC_CLASS_C_DEC::
operator typename PB_ASSOC_CLASS_C_DEC::key_reference()
{
  return (m_key);
}
 
PB_ASSOC_CLASS_T_DEC
inline
PB_ASSOC_CLASS_C_DEC::
operator typename PB_ASSOC_CLASS_C_DEC::key_type() const
{
  return (m_key);
}
 
#undef PB_ASSOC_CLASS_T_DEC
 
#undef PB_ASSOC_CLASS_C_DEC
 
#define PB_ASSOC_CLASS_T_DEC \
        template<class Cmp_Fn, class Allocator>
 
#define PB_ASSOC_CLASS_C_DEC \
        order_statistics_key_cmp< \
                Cmp_Fn, \
                Allocator>
 
PB_ASSOC_CLASS_T_DEC
inline
PB_ASSOC_CLASS_C_DEC::
order_statistics_key_cmp()
{ }
 
PB_ASSOC_CLASS_T_DEC
inline
PB_ASSOC_CLASS_C_DEC::
order_statistics_key_cmp(const Cmp_Fn& r_cmp_fn) :
  Cmp_Fn(r_cmp_fn)
{ }
 
PB_ASSOC_CLASS_T_DEC
inline bool
PB_ASSOC_CLASS_C_DEC::
operator()(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const
{
  return Cmp_Fn::operator()((key_type)r_lhs_key, (key_type)r_rhs_key);
}
 
PB_ASSOC_CLASS_T_DEC
inline typename PB_ASSOC_CLASS_C_DEC::cmp_fn&
PB_ASSOC_CLASS_C_DEC::
get_cmp_fn()
{
  return (*this);
}
 
PB_ASSOC_CLASS_T_DEC
inline const typename PB_ASSOC_CLASS_C_DEC::cmp_fn&
PB_ASSOC_CLASS_C_DEC::
get_cmp_fn() const
{
  return (*this);
}
 
#undef PB_ASSOC_CLASS_T_DEC
 
#undef PB_ASSOC_CLASS_C_DEC
 
#define PB_ASSOC_CLASS_T_DEC \
        template<class Key, class Allocator>
 
#define PB_ASSOC_CLASS_C_DEC \
        order_statistics_node_updator< \
                Key, \
                Allocator>
 
PB_ASSOC_CLASS_T_DEC
inline void
PB_ASSOC_CLASS_C_DEC::
operator()(const_key_pointer p_key, const_key_pointer p_l_child_key, const_key_pointer p_r_child_key)
{
  /*
   * The left rank is 0 if there is no left child,
   *    or the rank of the left child, otherwise.
   */
  const size_type l_rank =(p_l_child_key == NULL)? 0 : p_l_child_key->m_rank;
 
  /*
   * The right rank is 0 if there is no right child,
   *    or the rank of the right child, otherwise.
   */
  const size_type r_rank =(p_r_child_key == NULL)? 0 : p_r_child_key->m_rank;
 
  /*
   * The rand of the entry is the sumb of the ranks of its
   *    children + 1 (for itself).
   */
  p_key->m_rank = 1 + l_rank + r_rank;
}
 
PB_ASSOC_CLASS_T_DEC
inline void
PB_ASSOC_CLASS_C_DEC::
swap(PB_ASSOC_CLASS_C_DEC& /*r_other*/)
{ }
 
#undef PB_ASSOC_CLASS_T_DEC
 
#undef PB_ASSOC_CLASS_C_DEC
 
#define PB_ASSOC_CLASS_T_DEC \
        template<class Cntnr>
 
#define PB_ASSOC_CLASS_C_DEC \
        find_by_order< \
                Cntnr>
 
PB_ASSOC_CLASS_T_DEC
inline typename PB_ASSOC_CLASS_C_DEC::iterator
PB_ASSOC_CLASS_C_DEC::
operator()(Cntnr& r_c, size_type order) const
{
  return find(r_c, order);
}
 
PB_ASSOC_CLASS_T_DEC
inline typename PB_ASSOC_CLASS_C_DEC::const_iterator
PB_ASSOC_CLASS_C_DEC::
operator()(const Cntnr& r_c, size_type order) const
{
  return find(r_c, order);
}
 
PB_ASSOC_CLASS_T_DEC
inline typename PB_ASSOC_CLASS_C_DEC::const_iterator
PB_ASSOC_CLASS_C_DEC::
find(const Cntnr& r_c, size_type order)
{
  if (order > r_c.size())
    return (r_c.end());
 
  /*
   * Start at the top of the tree.
   */
  typename Cntnr::const_node_iterator it = r_c.node_begin();
 
  /*
   * Loop up to a leaf.
   */
  while (it != r_c.node_end())
    {
      typename Cntnr::const_node_iterator l_it = it.l_child();
 
      /*
       * The order of the element, o, is the rank of the left
       *        child (for the entry itself).
       */
      const size_type o = (l_it == r_c.node_end())?
 
 
      /*
       * If the current order, o, is the order requested,
       *        the key has been found.
       */
      if (order == o)
        return (*it);
      /*
       * If the current order, o, is larger than the order requested,
       *        we should move to the left subtree.
       */
      else if (order < o)
        it = l_it;
      /*
       * Otherwise adujst the requested order and move to the right subtree.
       */
      else
        {
          order -= o + 1;
 
          it = it.r_child();
        }
    }
 
  return (r_c.end());
}
 
PB_ASSOC_CLASS_T_DEC
inline typename PB_ASSOC_CLASS_C_DEC::iterator
PB_ASSOC_CLASS_C_DEC::
find(Cntnr& r_c, size_type order)
{
  if (order > r_c.size())
    return (r_c.end());
 
  /*
   * Start at the top of the tree.
   */
  typename Cntnr::node_iterator it = r_c.node_begin();
 
  /*
   * Loop up to a leaf.
   */
  while (it != r_c.node_end())
    {
      typename Cntnr::node_iterator l_it = it.l_child();
 
      /*
       * The order of the element, o, is the rank of the left
       *        child (for the entry itself).
       */
      const size_type o = (l_it == r_c.node_end())?
 
        r_c.extract_key(*(*l_it)).m_rank;
 
      /*
       * If the current order, o, is the order requested,
       *        the key has been found.
       */
      if (order == o)
        return (*it);
      /*
       * If the current order, o, is larger than the order requested,
       *        we should move to the left subtree.
       */
      else if (order < o)
        it = l_it;
      /*
       * Otherwise adujst the requested order and move to the right subtree.
       */
      else
        {
          order -= o + 1;
 
          it = it.r_child();
        }
    }
 
  return (r_c.end());
}
 
#undef PB_ASSOC_CLASS_T_DEC
 
#undef PB_ASSOC_CLASS_C_DEC
 
#define PB_ASSOC_CLASS_T_DEC \
        template<class Cntnr>
 
#define PB_ASSOC_CLASS_C_DEC \
        order_by_key< \
                Cntnr>
 
PB_ASSOC_CLASS_T_DEC
inline typename PB_ASSOC_CLASS_C_DEC::size_type
PB_ASSOC_CLASS_C_DEC::
operator()(const Cntnr& r_c, const underlying_key_type& r_key) const
{
  /*
   * The logic here is similar to that in order_by_key.
   */
 
  typename Cntnr::const_node_iterator it = r_c.node_begin();
 
  size_type ord = 0;
 
  while (it != r_c.node_end())
    {
      typename Cntnr::const_node_iterator l_it = it.l_child();
 
      if (r_c.get_cmp_fn().get_cmp_fn()(
                                        r_key,
                                        r_c.extract_key(*(*it)).m_key))
        it = l_it;
      else if (r_c.get_cmp_fn().get_cmp_fn()(
                                             r_c.extract_key(*(*it)).m_key,
                                             r_key))
        {
 
          ord += (l_it == r_c.node_end())?
            1 :
            1 + r_c.extract_key(*(*l_it)).m_rank;
 
          it = it.r_child();
        }
      else
        {
          ord += (l_it == r_c.node_end())?
 
            r_c.extract_key(*(*l_it)).m_rank;
 
          it = r_c.node_end();
        }
    }
 
  return (ord);
}
 
#undef PB_ASSOC_CLASS_T_DEC
 
#undef PB_ASSOC_CLASS_C_DEC
 
#define PB_ASSOC_CLASS_T_DEC \
        template<class Cntnr, class Allocator>
 
#define PB_ASSOC_CLASS_C_DEC \
        order_statistics_key_verifier< \
                Cntnr, \
                Allocator>
 
template<class Cntnr, class Allocator = std::allocator<char> >
class order_statistics_key_verifier
{
public:
  typedef Cntnr map;
 
  typedef Allocator allocator;
 
  typedef typename allocator::size_type size_type;
 
  typedef
  typename allocator::template rebind<map>::other::const_reference
  const_map_reference;
 
public:
  bool
  operator()(const Cntnr& r_c) const;
 
private:
  typedef typename Cntnr::const_node_iterator const_node_iterator;
 
  typedef typename Cntnr::const_iterator cntnr_const_it;
 
  typedef std::pair<bool, size_type> stat;
 
private:
  static stat
  verify_imp(const_node_iterator it, const_node_iterator end_it)
  {
    if (it == end_it)
      return (std::make_pair(true, 0));
 
    const stat l_ret =
      verify_imp(it.l_child(), end_it);
 
    const stat r_ret =
      verify_imp(it.r_child(), end_it);
 
    if (!l_ret.first || !r_ret.first)
      return (std::make_pair(false, 0));
 
    if ((*it)->m_rank != 1 + l_ret.second + r_ret.second)
      return (std::make_pair(false, 0));
 
    return (std::make_pair(true, (*it)->m_rank));
  }
};
 
PB_ASSOC_CLASS_T_DEC
bool
PB_ASSOC_CLASS_C_DEC::
operator()(const Cntnr& r_c) const
{
  const stat top_stat =
    verify_imp(r_c.node_begin(), r_c.node_end());
 
  return (top_stat.first);
}
 
#undef PB_ASSOC_CLASS_T_DEC
 
#undef PB_ASSOC_CLASS_C_DEC
 
#endif // #ifndef ORDER_STATISTICS_IMP_HPP

Browse

Tools

Subversion Repositories scarts

[/] [scarts/] [trunk/] [toolchain/] [scarts-gcc/] [gcc-4.1.1/] [libstdc++-v3/] [include/] [ext/] [pb_assoc/] [detail/] [tree_policy/] [order_statistics_imp.hpp] - Blame information for rev 17

Line No.	Rev	Author	Line
1	17	jlechner	`// -- 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 order_statistics_imp.hpp`
42			`* Contains forward declarations for order_statistics_key`
43			`*/`
44
45			`#ifndef ORDER_STATISTICS_IMP_HPP`
46			`#define ORDER_STATISTICS_IMP_HPP`
47
48			`#define PB_ASSOC_CLASS_T_DEC \`
49			`template<class Key, class Allocator>`
50
51			`#define PB_ASSOC_CLASS_C_DEC \`
52			`order_statistics_key< \`
53			`Key, \`
54			`Allocator>`
55
56			`PB_ASSOC_CLASS_T_DEC`
57			`inline`
58			`PB_ASSOC_CLASS_C_DEC::`
59			`order_statistics_key(const_key_reference r_key) :`
60			`m_key(r_key),`
61			`m_rank(1)`
62			`{ }`
63
64			`PB_ASSOC_CLASS_T_DEC`
65			`inline`
66			`PB_ASSOC_CLASS_C_DEC::`
67			`operator typename PB_ASSOC_CLASS_C_DEC::key_reference()`
68			`{`
69			`return (m_key);`
70			`}`
71
72			`PB_ASSOC_CLASS_T_DEC`
73			`inline`
74			`PB_ASSOC_CLASS_C_DEC::`
75			`operator typename PB_ASSOC_CLASS_C_DEC::key_type() const`
76			`{`
77			`return (m_key);`
78			`}`
79
80			`#undef PB_ASSOC_CLASS_T_DEC`
81
82			`#undef PB_ASSOC_CLASS_C_DEC`
83
84			`#define PB_ASSOC_CLASS_T_DEC \`
85			`template<class Cmp_Fn, class Allocator>`
86
87			`#define PB_ASSOC_CLASS_C_DEC \`
88			`order_statistics_key_cmp< \`
89			`Cmp_Fn, \`
90			`Allocator>`
91
92			`PB_ASSOC_CLASS_T_DEC`
93			`inline`
94			`PB_ASSOC_CLASS_C_DEC::`
95			`order_statistics_key_cmp()`
96			`{ }`
97
98			`PB_ASSOC_CLASS_T_DEC`
99			`inline`
100			`PB_ASSOC_CLASS_C_DEC::`
101			`order_statistics_key_cmp(const Cmp_Fn& r_cmp_fn) :`
102			`Cmp_Fn(r_cmp_fn)`
103			`{ }`
104
105			`PB_ASSOC_CLASS_T_DEC`
106			`inline bool`
107			`PB_ASSOC_CLASS_C_DEC::`
108			`operator()(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const`
109			`{`
110			`return Cmp_Fn::operator()((key_type)r_lhs_key, (key_type)r_rhs_key);`
111			`}`
112
113			`PB_ASSOC_CLASS_T_DEC`
114			`inline typename PB_ASSOC_CLASS_C_DEC::cmp_fn&`
115			`PB_ASSOC_CLASS_C_DEC::`
116			`get_cmp_fn()`
117			`{`
118			`return (*this);`
119			`}`
120
121			`PB_ASSOC_CLASS_T_DEC`
122			`inline const typename PB_ASSOC_CLASS_C_DEC::cmp_fn&`
123			`PB_ASSOC_CLASS_C_DEC::`
124			`get_cmp_fn() const`
125			`{`
126			`return (*this);`
127			`}`
128
129			`#undef PB_ASSOC_CLASS_T_DEC`
130
131			`#undef PB_ASSOC_CLASS_C_DEC`
132
133			`#define PB_ASSOC_CLASS_T_DEC \`
134			`template<class Key, class Allocator>`
135
136			`#define PB_ASSOC_CLASS_C_DEC \`
137			`order_statistics_node_updator< \`
138			`Key, \`
139			`Allocator>`
140
141			`PB_ASSOC_CLASS_T_DEC`
142			`inline void`
143			`PB_ASSOC_CLASS_C_DEC::`
144			`operator()(const_key_pointer p_key, const_key_pointer p_l_child_key, const_key_pointer p_r_child_key)`
145			`{`
146			`/*`
147			`* The left rank is 0 if there is no left child,`
148			`* or the rank of the left child, otherwise.`
149			`*/`
150			`const size_type l_rank =(p_l_child_key == NULL)? 0 : p_l_child_key->m_rank;`
151
152			`/*`
153			`* The right rank is 0 if there is no right child,`
154			`* or the rank of the right child, otherwise.`
155			`*/`
156			`const size_type r_rank =(p_r_child_key == NULL)? 0 : p_r_child_key->m_rank;`
157
158			`/*`
159			`* The rand of the entry is the sumb of the ranks of its`
160			`* children + 1 (for itself).`
161			`*/`
162			`p_key->m_rank = 1 + l_rank + r_rank;`
163			`}`
164
165			`PB_ASSOC_CLASS_T_DEC`
166			`inline void`
167			`PB_ASSOC_CLASS_C_DEC::`
168			`swap(PB_ASSOC_CLASS_C_DEC& /r_other/)`
169			`{ }`
170
171			`#undef PB_ASSOC_CLASS_T_DEC`
172
173			`#undef PB_ASSOC_CLASS_C_DEC`
174
175			`#define PB_ASSOC_CLASS_T_DEC \`
176			`template<class Cntnr>`
177
178			`#define PB_ASSOC_CLASS_C_DEC \`
179			`find_by_order< \`
180			`Cntnr>`
181
182			`PB_ASSOC_CLASS_T_DEC`
183			`inline typename PB_ASSOC_CLASS_C_DEC::iterator`
184			`PB_ASSOC_CLASS_C_DEC::`
185			`operator()(Cntnr& r_c, size_type order) const`
186			`{`
187			`return find(r_c, order);`
188			`}`
189
190			`PB_ASSOC_CLASS_T_DEC`
191			`inline typename PB_ASSOC_CLASS_C_DEC::const_iterator`
192			`PB_ASSOC_CLASS_C_DEC::`
193			`operator()(const Cntnr& r_c, size_type order) const`
194			`{`
195			`return find(r_c, order);`
196			`}`
197
198			`PB_ASSOC_CLASS_T_DEC`
199			`inline typename PB_ASSOC_CLASS_C_DEC::const_iterator`
200			`PB_ASSOC_CLASS_C_DEC::`
201			`find(const Cntnr& r_c, size_type order)`
202			`{`
203			`if (order > r_c.size())`
204			`return (r_c.end());`
205
206			`/*`
207			`* Start at the top of the tree.`
208			`*/`
209			`typename Cntnr::const_node_iterator it = r_c.node_begin();`
210
211			`/*`
212			`* Loop up to a leaf.`
213			`*/`
214			`while (it != r_c.node_end())`
215			`{`
216			`typename Cntnr::const_node_iterator l_it = it.l_child();`
217
218			`/*`
219			`* The order of the element, o, is the rank of the left`
220			`* child (for the entry itself).`
221			`*/`
222			`const size_type o = (l_it == r_c.node_end())?`
223
224
225			`/*`
226			`* If the current order, o, is the order requested,`
227			`* the key has been found.`
228			`*/`
229			`if (order == o)`
230			`return (*it);`
231			`/*`
232			`* If the current order, o, is larger than the order requested,`
233			`* we should move to the left subtree.`
234			`*/`
235			`else if (order < o)`
236			`it = l_it;`
237			`/*`
238			`* Otherwise adujst the requested order and move to the right subtree.`
239			`*/`
240			`else`
241			`{`
242			`order -= o + 1;`
243
244			`it = it.r_child();`
245			`}`
246			`}`
247
248			`return (r_c.end());`
249			`}`
250
251			`PB_ASSOC_CLASS_T_DEC`
252			`inline typename PB_ASSOC_CLASS_C_DEC::iterator`
253			`PB_ASSOC_CLASS_C_DEC::`
254			`find(Cntnr& r_c, size_type order)`
255			`{`
256			`if (order > r_c.size())`
257			`return (r_c.end());`
258
259			`/*`
260			`* Start at the top of the tree.`
261			`*/`
262			`typename Cntnr::node_iterator it = r_c.node_begin();`
263
264			`/*`
265			`* Loop up to a leaf.`
266			`*/`
267			`while (it != r_c.node_end())`
268			`{`
269			`typename Cntnr::node_iterator l_it = it.l_child();`
270
271			`/*`
272			`* The order of the element, o, is the rank of the left`
273			`* child (for the entry itself).`
274			`*/`
275			`const size_type o = (l_it == r_c.node_end())?`
276
277			`r_c.extract_key((l_it)).m_rank;`
278
279			`/*`
280			`* If the current order, o, is the order requested,`
281			`* the key has been found.`
282			`*/`
283			`if (order == o)`
284			`return (*it);`
285			`/*`
286			`* If the current order, o, is larger than the order requested,`
287			`* we should move to the left subtree.`
288			`*/`
289			`else if (order < o)`
290			`it = l_it;`
291			`/*`
292			`* Otherwise adujst the requested order and move to the right subtree.`
293			`*/`
294			`else`
295			`{`
296			`order -= o + 1;`
297
298			`it = it.r_child();`
299			`}`
300			`}`
301
302			`return (r_c.end());`
303			`}`
304
305			`#undef PB_ASSOC_CLASS_T_DEC`
306
307			`#undef PB_ASSOC_CLASS_C_DEC`
308
309			`#define PB_ASSOC_CLASS_T_DEC \`
310			`template<class Cntnr>`
311
312			`#define PB_ASSOC_CLASS_C_DEC \`
313			`order_by_key< \`
314			`Cntnr>`
315
316			`PB_ASSOC_CLASS_T_DEC`
317			`inline typename PB_ASSOC_CLASS_C_DEC::size_type`
318			`PB_ASSOC_CLASS_C_DEC::`
319			`operator()(const Cntnr& r_c, const underlying_key_type& r_key) const`
320			`{`
321			`/*`
322			`* The logic here is similar to that in order_by_key.`
323			`*/`
324
325			`typename Cntnr::const_node_iterator it = r_c.node_begin();`
326
327			`size_type ord = 0;`
328
329			`while (it != r_c.node_end())`
330			`{`
331			`typename Cntnr::const_node_iterator l_it = it.l_child();`
332
333			`if (r_c.get_cmp_fn().get_cmp_fn()(`
334			`r_key,`
335			`r_c.extract_key((it)).m_key))`
336			`it = l_it;`
337			`else if (r_c.get_cmp_fn().get_cmp_fn()(`
338			`r_c.extract_key((it)).m_key,`
339			`r_key))`
340			`{`
341
342			`ord += (l_it == r_c.node_end())?`
343			`1 :`
344			`1 + r_c.extract_key((l_it)).m_rank;`
345
346			`it = it.r_child();`
347			`}`
348			`else`
349			`{`
350			`ord += (l_it == r_c.node_end())?`
351
352			`r_c.extract_key((l_it)).m_rank;`
353
354			`it = r_c.node_end();`
355			`}`
356			`}`
357
358			`return (ord);`
359			`}`
360
361			`#undef PB_ASSOC_CLASS_T_DEC`
362
363			`#undef PB_ASSOC_CLASS_C_DEC`
364
365			`#define PB_ASSOC_CLASS_T_DEC \`
366			`template<class Cntnr, class Allocator>`
367
368			`#define PB_ASSOC_CLASS_C_DEC \`
369			`order_statistics_key_verifier< \`
370			`Cntnr, \`
371			`Allocator>`
372
373			`template<class Cntnr, class Allocator = std::allocator<char> >`
374			`class order_statistics_key_verifier`
375			`{`
376			`public:`
377			`typedef Cntnr map;`
378
379			`typedef Allocator allocator;`
380
381			`typedef typename allocator::size_type size_type;`
382
383			`typedef`
384			`typename allocator::template rebind<map>::other::const_reference`
385			`const_map_reference;`
386
387			`public:`
388			`bool`
389			`operator()(const Cntnr& r_c) const;`
390
391			`private:`
392			`typedef typename Cntnr::const_node_iterator const_node_iterator;`
393
394			`typedef typename Cntnr::const_iterator cntnr_const_it;`
395
396			`typedef std::pair<bool, size_type> stat;`
397
398			`private:`
399			`static stat`
400			`verify_imp(const_node_iterator it, const_node_iterator end_it)`
401			`{`
402			`if (it == end_it)`
403			`return (std::make_pair(true, 0));`
404
405			`const stat l_ret =`
406			`verify_imp(it.l_child(), end_it);`
407
408			`const stat r_ret =`
409			`verify_imp(it.r_child(), end_it);`
410
411			`if (!l_ret.first \|\| !r_ret.first)`
412			`return (std::make_pair(false, 0));`
413
414			`if ((*it)->m_rank != 1 + l_ret.second + r_ret.second)`
415			`return (std::make_pair(false, 0));`
416
417			`return (std::make_pair(true, (*it)->m_rank));`
418			`}`
419			`};`
420
421			`PB_ASSOC_CLASS_T_DEC`
422			`bool`
423			`PB_ASSOC_CLASS_C_DEC::`
424			`operator()(const Cntnr& r_c) const`
425			`{`
426			`const stat top_stat =`
427			`verify_imp(r_c.node_begin(), r_c.node_end());`
428
429			`return (top_stat.first);`
430			`}`
431
432			`#undef PB_ASSOC_CLASS_T_DEC`
433
434			`#undef PB_ASSOC_CLASS_C_DEC`
435
436			`#endif // #ifndef ORDER_STATISTICS_IMP_HPP`