diff options
Diffstat (limited to 'libstdc++-v3/include/ext/pb_assoc/detail/tree_policy/order_statistics_imp.hpp')
| -rw-r--r-- | libstdc++-v3/include/ext/pb_assoc/detail/tree_policy/order_statistics_imp.hpp | 436 |
1 files changed, 0 insertions, 436 deletions
diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/tree_policy/order_statistics_imp.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/tree_policy/order_statistics_imp.hpp deleted file mode 100644 index 7e3550188d6..00000000000 --- a/libstdc++-v3/include/ext/pb_assoc/detail/tree_policy/order_statistics_imp.hpp +++ /dev/null @@ -1,436 +0,0 @@ -// -*- 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())? - 0 :(*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()); -} - -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())? - 0 : - 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())? - 0 : - 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 |