diff options
Diffstat (limited to 'gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy')
7 files changed, 0 insertions, 849 deletions
diff --git a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp b/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp deleted file mode 100644 index 67dfde25e..000000000 --- a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/node_metadata_selector.hpp +++ /dev/null @@ -1,103 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005-2013 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 3, 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. - -// Under Section 7 of GPL version 3, you are granted additional -// permissions described in the GCC Runtime Library Exception, version -// 3.1, as published by the Free Software Foundation. - -// You should have received a copy of the GNU General Public License and -// a copy of the GCC Runtime Library Exception along with this program; -// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -// <http://www.gnu.org/licenses/>. - -// 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 trie_policy/node_metadata_selector.hpp - * Contains an implementation class for tries. - */ - -#ifndef PB_DS_TRIE_NODE_METADATA_DISPATCH_HPP -#define PB_DS_TRIE_NODE_METADATA_DISPATCH_HPP - -#include <ext/pb_ds/detail/branch_policy/null_node_metadata.hpp> -#include <ext/pb_ds/detail/types_traits.hpp> - -namespace __gnu_pbds -{ - namespace detail - { - /** - * @addtogroup traits Traits - * @{ - */ - - /// Trie metadata helper. - template<typename Node_Update, bool _BTp> - struct trie_metadata_helper; - - /// Specialization, false. - template<typename Node_Update> - struct trie_metadata_helper<Node_Update, false> - { - typedef typename Node_Update::metadata_type type; - }; - - /// Specialization, true. - template<typename Node_Update> - struct trie_metadata_helper<Node_Update, true> - { - typedef null_type type; - }; - - /// Trie node metadata dispatch. - template<typename Key, - typename Data, - typename Cmp_Fn, - template<typename Node_CItr, - typename Const_Iterator, - typename Cmp_Fn_, - typename _Alloc_> - class Node_Update, - typename _Alloc> - struct trie_node_metadata_dispatch - { - private: - typedef dumnode_const_iterator<Key, Data, _Alloc> __it_type; - typedef Node_Update<__it_type, __it_type, Cmp_Fn, _Alloc> __node_u; - typedef null_node_update<__it_type, __it_type, Cmp_Fn, _Alloc> __nnode_u; - - enum - { - null_update = is_same<__node_u, __nnode_u>::value - }; - - public: - typedef typename trie_metadata_helper<__node_u, null_update>::type type; - }; - //@} - } // namespace detail -} // namespace __gnu_pbds - -#endif // #ifndef PB_DS_TRIE_NODE_METADATA_DISPATCH_HPP diff --git a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp b/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp deleted file mode 100644 index 82b6acc5c..000000000 --- a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp +++ /dev/null @@ -1,160 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005-2013 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 3, 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. - -// Under Section 7 of GPL version 3, you are granted additional -// permissions described in the GCC Runtime Library Exception, version -// 3.1, as published by the Free Software Foundation. - -// You should have received a copy of the GNU General Public License and -// a copy of the GCC Runtime Library Exception along with this program; -// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -// <http://www.gnu.org/licenses/>. - -// 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 trie_policy/order_statistics_imp.hpp - * Contains forward declarations for order_statistics_key - */ - -PB_DS_CLASS_T_DEC -inline typename PB_DS_CLASS_C_DEC::iterator -PB_DS_CLASS_C_DEC:: -find_by_order(size_type order) -{ - if (empty()) - return end(); - - ++order; - node_iterator nd_it = node_begin(); - - while (true) - { - if (order > nd_it.get_metadata()) - return ++base_type::rightmost_it(nd_it); - - const size_type num_children = nd_it.num_children(); - if (num_children == 0) - return *nd_it; - - for (size_type i = 0; i < num_children; ++i) - { - node_iterator child_nd_it = nd_it.get_child(i); - if (order <= child_nd_it.get_metadata()) - { - i = num_children; - nd_it = child_nd_it; - } - else - order -= child_nd_it.get_metadata(); - } - } -} - -PB_DS_CLASS_T_DEC -inline typename PB_DS_CLASS_C_DEC::const_iterator -PB_DS_CLASS_C_DEC:: -find_by_order(size_type order) const -{ return const_cast<PB_DS_CLASS_C_DEC*>(this)->find_by_order(order); } - -PB_DS_CLASS_T_DEC -inline typename PB_DS_CLASS_C_DEC::size_type -PB_DS_CLASS_C_DEC:: -order_of_key(key_const_reference r_key) const -{ - const _ATraits& r_traits = - const_cast<PB_DS_CLASS_C_DEC* >(this)->get_access_traits(); - - return order_of_prefix(r_traits.begin(r_key), r_traits.end(r_key)); -} - -PB_DS_CLASS_T_DEC -inline typename PB_DS_CLASS_C_DEC::size_type -PB_DS_CLASS_C_DEC:: -order_of_prefix(typename access_traits::const_iterator b, - typename access_traits::const_iterator e) const -{ - if (empty()) - return 0; - - const _ATraits& r_traits = - const_cast<PB_DS_CLASS_C_DEC*>(this)->get_access_traits(); - - node_const_iterator nd_it = node_begin(); - node_const_iterator end_nd_it = node_end(); - size_type ord = 0; - - while (true) - { - const size_type num_children = nd_it.num_children(); - if (num_children == 0) - { - key_const_reference r_key = base_type::extract_key(*(*nd_it)); - typename access_traits::const_iterator key_b = - r_traits.begin(r_key); - - typename access_traits::const_iterator key_e = - r_traits.end(r_key); - - return (base_type::less(key_b, key_e, b, e, r_traits)) ? - ord + 1 : ord; - } - - node_const_iterator next_nd_it = end_nd_it; - size_type i = num_children - 1; - - do - { - node_const_iterator child_nd_it = nd_it.get_child(i); - - if (next_nd_it != end_nd_it) - ord += child_nd_it.get_metadata(); - else if (!base_type::less(b, e, - child_nd_it.valid_prefix().first, - child_nd_it.valid_prefix().second, - r_traits)) - next_nd_it = child_nd_it; - } - while (i-- > 0); - - if (next_nd_it == end_nd_it) - return ord; - - nd_it = next_nd_it; - } -} - -PB_DS_CLASS_T_DEC -inline void -PB_DS_CLASS_C_DEC:: -operator()(node_iterator nd_it, node_const_iterator /*end_nd_it*/) const -{ - const size_type num_children = nd_it.num_children(); - size_type children_rank = 0; - for (size_type i = 0; i < num_children; ++i) - children_rank += nd_it.get_child(i).get_metadata(); - - const size_type res = (num_children == 0) ? 1 : children_rank; - const_cast<size_type&>(nd_it.get_metadata()) = res; -} diff --git a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp b/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp deleted file mode 100644 index 8e961134e..000000000 --- a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp +++ /dev/null @@ -1,139 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005-2013 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 3, 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. - -// Under Section 7 of GPL version 3, you are granted additional -// permissions described in the GCC Runtime Library Exception, version -// 3.1, as published by the Free Software Foundation. - -// You should have received a copy of the GNU General Public License and -// a copy of the GCC Runtime Library Exception along with this program; -// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -// <http://www.gnu.org/licenses/>. - -// 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 trie_policy/prefix_search_node_update_imp.hpp - * Contains an implementation of prefix_search_node_update. - */ - -PB_DS_CLASS_T_DEC -std::pair< - typename PB_DS_CLASS_C_DEC::const_iterator, - typename PB_DS_CLASS_C_DEC::const_iterator> -PB_DS_CLASS_C_DEC:: -prefix_range(key_const_reference r_key) const -{ - const access_traits& r_traits = get_access_traits(); - return (prefix_range(r_traits.begin(r_key), r_traits.end(r_key))); -} - -PB_DS_CLASS_T_DEC -std::pair< - typename PB_DS_CLASS_C_DEC::iterator, - typename PB_DS_CLASS_C_DEC::iterator> -PB_DS_CLASS_C_DEC:: -prefix_range(key_const_reference r_key) -{ - return (prefix_range(get_access_traits().begin(r_key), - get_access_traits().end(r_key))); -} - -PB_DS_CLASS_T_DEC -std::pair< - typename PB_DS_CLASS_C_DEC::const_iterator, - typename PB_DS_CLASS_C_DEC::const_iterator> -PB_DS_CLASS_C_DEC:: -prefix_range(typename access_traits::const_iterator b, - typename access_traits::const_iterator e) const -{ - const std::pair<iterator, iterator> non_const_ret = - const_cast<PB_DS_CLASS_C_DEC* >(this)->prefix_range(b, e); - - return (std::make_pair(const_iterator(non_const_ret.first), - const_iterator(non_const_ret.second))); -} - -PB_DS_CLASS_T_DEC -std::pair< - typename PB_DS_CLASS_C_DEC::iterator, - typename PB_DS_CLASS_C_DEC::iterator> -PB_DS_CLASS_C_DEC:: -prefix_range(typename access_traits::const_iterator b, - typename access_traits::const_iterator e) -{ - Node_Itr nd_it = node_begin(); - Node_Itr end_nd_it = node_end(); - - const access_traits& r_traits = get_access_traits(); - const size_type given_range_length = std::distance(b, e); - - while (true) - { - if (nd_it == end_nd_it) - return (std::make_pair(end(), end())); - - const size_type common_range_length = - base_type::common_prefix_len(nd_it, b, e, r_traits); - - if (common_range_length >= given_range_length) - { - iterator ret_b = this->leftmost_it(nd_it); - iterator ret_e = this->rightmost_it(nd_it); - return (std::make_pair(ret_b, ++ret_e)); - } - nd_it = next_child(nd_it, b, e, end_nd_it, r_traits); - } -} - -PB_DS_CLASS_T_DEC -typename PB_DS_CLASS_C_DEC::node_iterator -PB_DS_CLASS_C_DEC:: -next_child(node_iterator nd_it, typename access_traits::const_iterator b, - typename access_traits::const_iterator e, node_iterator end_nd_it, - const access_traits& r_traits) -{ - const size_type num_children = nd_it.num_children(); - node_iterator ret = end_nd_it; - size_type max_length = 0; - for (size_type i = 0; i < num_children; ++i) - { - node_iterator pot = nd_it.get_child(i); - const size_type common_range_length = - base_type::common_prefix_len(pot, b, e, r_traits); - - if (common_range_length > max_length) - { - ret = pot; - max_length = common_range_length; - } - } - return (ret); -} - -PB_DS_CLASS_T_DEC -inline void -PB_DS_CLASS_C_DEC:: -operator()(node_iterator /*nd_it*/, node_const_iterator /*end_nd_it*/) const -{ } diff --git a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp b/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp deleted file mode 100644 index 79ef2c6d8..000000000 --- a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_access_traits.hpp +++ /dev/null @@ -1,77 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005-2013 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 3, 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. - -// Under Section 7 of GPL version 3, you are granted additional -// permissions described in the GCC Runtime Library Exception, version -// 3.1, as published by the Free Software Foundation. - -// You should have received a copy of the GNU General Public License and -// a copy of the GCC Runtime Library Exception along with this program; -// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -// <http://www.gnu.org/licenses/>. - -// 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 trie_policy/sample_trie_access_traits.hpp - * Contains a sample probe policy. - */ - -#ifndef PB_DS_SAMPLE_TRIE_E_ACCESS_TRAITS_HPP -#define PB_DS_SAMPLE_TRIE_E_ACCESS_TRAITS_HPP - -namespace __gnu_pbds -{ - /// A sample trie element access traits. - struct sample_trie_access_traits - { - typedef std::size_t size_type; - typedef std::string key_type; - - typedef typename _Alloc::template rebind<key_type> __rebind_k; - typedef typename __rebind_k::other::const_reference key_const_reference; - typedef std::string::const_iterator const_iterator; - - /// Element type. - typedef char e_type; - - enum - { - max_size = 4 - }; - - /// Returns a const_iterator to the first element of r_key. - inline static const_iterator - begin(key_const_reference); - - /// Returns a const_iterator to the after-last element of r_key. - inline static const_iterator - end(key_const_reference); - - /// Maps an element to a position. - inline static size_type - e_pos(e_type); - }; -} -#endif // #ifndef PB_DS_SAMPLE_TRIE_E_ACCESS_TRAITS_HPP diff --git a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_node_update.hpp b/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_node_update.hpp deleted file mode 100644 index c2d487e37..000000000 --- a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/sample_trie_node_update.hpp +++ /dev/null @@ -1,64 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005-2013 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 3, 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. - -// Under Section 7 of GPL version 3, you are granted additional -// permissions described in the GCC Runtime Library Exception, version -// 3.1, as published by the Free Software Foundation. - -// You should have received a copy of the GNU General Public License and -// a copy of the GCC Runtime Library Exception along with this program; -// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -// <http://www.gnu.org/licenses/>. - -// 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 trie_policy/sample_trie_node_update.hpp - * Contains a samle node update functor. - */ - -#ifndef PB_DS_SAMPLE_TRIE_NODE_UPDATOR_HPP -#define PB_DS_SAMPLE_TRIE_NODE_UPDATOR_HPP - -namespace __gnu_pbds -{ - /// A sample node updator. - template<typename Node_CItr, typename Node_Itr, - typename _ATraits, typename _Alloc> - class sample_trie_node_update - { - public: - typedef std::size_t metadata_type; - - protected: - /// Default constructor. - sample_trie_node_update(); - - /// Updates the rank of a node through a node_iterator node_it; - /// end_nd_it is the end node iterator. - inline void - operator()(node_iterator, node_const_iterator) const; - }; -} -#endif // #ifndef PB_DS_SAMPLE_TRIE_NODE_UPDATOR_HPP diff --git a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp b/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp deleted file mode 100644 index 7b1c4a9e7..000000000 --- a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_policy_base.hpp +++ /dev/null @@ -1,207 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005-2013 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 3, 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. - -// Under Section 7 of GPL version 3, you are granted additional -// permissions described in the GCC Runtime Library Exception, version -// 3.1, as published by the Free Software Foundation. - -// You should have received a copy of the GNU General Public License and -// a copy of the GCC Runtime Library Exception along with this program; -// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -// <http://www.gnu.org/licenses/>. - -// 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 trie_policy/trie_policy_base.hpp - * Contains an implementation of trie_policy_base. - */ - -#ifndef PB_DS_TRIE_POLICY_BASE_HPP -#define PB_DS_TRIE_POLICY_BASE_HPP - -#include <ext/pb_ds/detail/branch_policy/branch_policy.hpp> - -namespace __gnu_pbds -{ - namespace detail - { - /// Base class for trie policies. - template<typename Node_CItr, typename Node_Itr, - typename _ATraits, typename _Alloc> - class trie_policy_base - : public branch_policy<Node_CItr, Node_Itr, _Alloc> - { - typedef branch_policy<Node_CItr, Node_Itr, _Alloc> base_type; - - public: - typedef _ATraits access_traits; - typedef _Alloc allocator_type; - typedef typename allocator_type::size_type size_type; - typedef null_type metadata_type; - typedef Node_CItr node_const_iterator; - typedef Node_Itr node_iterator; - typedef typename node_const_iterator::value_type const_iterator; - typedef typename node_iterator::value_type iterator; - typedef typename base_type::key_type key_type; - typedef typename base_type::key_const_reference key_const_reference; - - protected: - virtual const_iterator - end() const = 0; - - virtual iterator - end() = 0; - - virtual node_const_iterator - node_begin() const = 0; - - virtual node_iterator - node_begin() = 0; - - virtual node_const_iterator - node_end() const = 0; - - virtual node_iterator - node_end() = 0; - - virtual const access_traits& - get_access_traits() const = 0; - - private: - typedef typename access_traits::const_iterator e_const_iterator; - typedef std::pair<e_const_iterator, e_const_iterator> prefix_range_t; - - protected: - static size_type - common_prefix_len(node_iterator, e_const_iterator, - e_const_iterator, const access_traits&); - - static iterator - leftmost_it(node_iterator); - - static iterator - rightmost_it(node_iterator); - - static bool - less(e_const_iterator, e_const_iterator, e_const_iterator, - e_const_iterator, const access_traits&); - }; - - -#define PB_DS_CLASS_T_DEC \ - template<typename Node_CItr, typename Node_Itr, \ - typename _ATraits, typename _Alloc> - -#define PB_DS_CLASS_C_DEC \ - trie_policy_base<Node_CItr, Node_Itr, _ATraits, _Alloc> - - PB_DS_CLASS_T_DEC - typename PB_DS_CLASS_C_DEC::size_type - PB_DS_CLASS_C_DEC:: - common_prefix_len(node_iterator nd_it, e_const_iterator b_r, - e_const_iterator e_r, const access_traits& r_traits) - { - prefix_range_t pref_range = nd_it.valid_prefix(); - - e_const_iterator b_l = pref_range.first; - e_const_iterator e_l = pref_range.second; - - const size_type range_length_l = std::distance(b_l, e_l); - const size_type range_length_r = std::distance(b_r, e_r); - - if (range_length_r < range_length_l) - { - std::swap(b_l, b_r); - std::swap(e_l, e_r); - } - - size_type ret = 0; - while (b_l != e_l) - { - if (r_traits.e_pos(*b_l) != r_traits.e_pos(*b_r)) - return ret; - - ++ret; - ++b_l; - ++b_r; - } - - return ret; - } - - PB_DS_CLASS_T_DEC - typename PB_DS_CLASS_C_DEC::iterator - PB_DS_CLASS_C_DEC:: - leftmost_it(node_iterator nd_it) - { - if (nd_it.num_children() == 0) - return *nd_it; - - return leftmost_it(nd_it.get_child(0)); - } - - PB_DS_CLASS_T_DEC - typename PB_DS_CLASS_C_DEC::iterator - PB_DS_CLASS_C_DEC:: - rightmost_it(node_iterator nd_it) - { - const size_type num_children = nd_it.num_children(); - - if (num_children == 0) - return *nd_it; - - return rightmost_it(nd_it.get_child(num_children - 1)); - } - - PB_DS_CLASS_T_DEC - bool - PB_DS_CLASS_C_DEC:: - less(e_const_iterator b_l, e_const_iterator e_l, - e_const_iterator b_r, e_const_iterator e_r, - const access_traits& r_traits) - { - while (b_l != e_l) - { - if (b_r == e_r) - return false; - - size_type l_pos = r_traits.e_pos(*b_l); - size_type r_pos = r_traits.e_pos(*b_r); - if (l_pos != r_pos) - return (l_pos < r_pos); - - ++b_l; - ++b_r; - } - return b_r != e_r; - } - -#undef PB_DS_CLASS_T_DEC -#undef PB_DS_CLASS_C_DEC - - } // namespace detail -} // namespace __gnu_pbds - -#endif // #ifndef PB_DS_TRIE_POLICY_BASE_HPP diff --git a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_string_access_traits_imp.hpp b/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_string_access_traits_imp.hpp deleted file mode 100644 index 4662dc3a9..000000000 --- a/gcc-4.8.1/libstdc++-v3/include/ext/pb_ds/detail/trie_policy/trie_string_access_traits_imp.hpp +++ /dev/null @@ -1,99 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005-2013 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 3, 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. - -// Under Section 7 of GPL version 3, you are granted additional -// permissions described in the GCC Runtime Library Exception, version -// 3.1, as published by the Free Software Foundation. - -// You should have received a copy of the GNU General Public License and -// a copy of the GCC Runtime Library Exception along with this program; -// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see -// <http://www.gnu.org/licenses/>. - -// 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 trie_policy/trie_string_access_traits_imp.hpp - * Contains a policy for extracting character positions from - * a string for a vector-based PATRICIA tree - */ - -PB_DS_CLASS_T_DEC -detail::integral_constant<int, Reverse> PB_DS_CLASS_C_DEC::s_rev_ind; - -PB_DS_CLASS_T_DEC -inline typename PB_DS_CLASS_C_DEC::size_type -PB_DS_CLASS_C_DEC:: -e_pos(e_type e) -{ - return (static_cast<size_type>(e - min_e_val)); -} - -PB_DS_CLASS_T_DEC -inline typename PB_DS_CLASS_C_DEC::const_iterator -PB_DS_CLASS_C_DEC:: -begin(key_const_reference r_key) -{ - return (begin_imp(r_key, s_rev_ind)); -} - -PB_DS_CLASS_T_DEC -inline typename PB_DS_CLASS_C_DEC::const_iterator -PB_DS_CLASS_C_DEC:: -end(key_const_reference r_key) -{ - return (end_imp(r_key, s_rev_ind)); -} - -PB_DS_CLASS_T_DEC -inline typename PB_DS_CLASS_C_DEC::const_iterator -PB_DS_CLASS_C_DEC:: -begin_imp(key_const_reference r_key, detail::false_type) -{ - return (r_key.begin()); -} - -PB_DS_CLASS_T_DEC -inline typename PB_DS_CLASS_C_DEC::const_iterator -PB_DS_CLASS_C_DEC:: -begin_imp(key_const_reference r_key, detail::true_type) -{ - return (r_key.rbegin()); -} - -PB_DS_CLASS_T_DEC -inline typename PB_DS_CLASS_C_DEC::const_iterator -PB_DS_CLASS_C_DEC:: -end_imp(key_const_reference r_key, detail::false_type) -{ - return (r_key.end()); -} - -PB_DS_CLASS_T_DEC -inline typename PB_DS_CLASS_C_DEC::const_iterator -PB_DS_CLASS_C_DEC:: -end_imp(key_const_reference r_key, detail::true_type) -{ - return (r_key.rend()); -} |