diff options
Diffstat (limited to 'libstdc++-v3/include/ext/pb_assoc/detail/order_statistics_imp.hpp')
| -rw-r--r-- | libstdc++-v3/include/ext/pb_assoc/detail/order_statistics_imp.hpp | 436 |
1 files changed, 436 insertions, 0 deletions
diff --git a/libstdc++-v3/include/ext/pb_assoc/detail/order_statistics_imp.hpp b/libstdc++-v3/include/ext/pb_assoc/detail/order_statistics_imp.hpp new file mode 100644 index 00000000000..d4031583c9c --- /dev/null +++ b/libstdc++-v3/include/ext/pb_assoc/detail/order_statistics_imp.hpp @@ -0,0 +1,436 @@ +// -*- 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, +// 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 |