diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp')
-rw-r--r-- | gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp | 355 |
1 files changed, 0 insertions, 355 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp deleted file mode 100644 index c10591bb7..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/trie_policy.hpp +++ /dev/null @@ -1,355 +0,0 @@ -// -*- C++ -*- - -// Copyright (C) 2005, 2006, 2007, 2009 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.hpp - * Contains trie-related policies. - */ - -#ifndef PB_DS_TRIE_POLICY_HPP -#define PB_DS_TRIE_POLICY_HPP - -#include <string> -#include <ext/pb_ds/detail/type_utils.hpp> -#include <ext/pb_ds/detail/trie_policy/trie_policy_base.hpp> - -namespace __gnu_pbds -{ - // A null node updator, indicating that no node updates are required. - template<typename Const_Node_Iterator, - typename Node_Iterator, - typename E_Access_Traits, - typename Allocator> - struct null_trie_node_update - { }; - -#define PB_DS_CLASS_T_DEC \ - template<typename String, typename String::value_type Min_E_Val, typename String::value_type Max_E_Val, bool Reverse, typename Allocator> - -#define PB_DS_CLASS_C_DEC \ - string_trie_e_access_traits<String, Min_E_Val,Max_E_Val,Reverse,Allocator> - - // Element access traits for string types. - template<typename String = std::string, - typename String::value_type Min_E_Val = detail::__numeric_traits<typename String::value_type>::__min, - typename String::value_type Max_E_Val = detail::__numeric_traits<typename String::value_type>::__max, - bool Reverse = false, - typename Allocator = std::allocator<char> > - struct string_trie_e_access_traits - { - public: - typedef typename Allocator::size_type size_type; - typedef String key_type; - typedef typename Allocator::template rebind<key_type>::other key_rebind; - typedef typename key_rebind::const_reference const_key_reference; - - enum - { - reverse = Reverse - }; - - // Element const iterator type. - typedef typename detail::__conditional_type<Reverse, typename String::const_reverse_iterator, typename String::const_iterator>::__type const_iterator; - - // Element type. - typedef typename std::iterator_traits<const_iterator>::value_type e_type; - - enum - { - min_e_val = Min_E_Val, - max_e_val = Max_E_Val, - max_size = max_e_val - min_e_val + 1 - }; - PB_DS_STATIC_ASSERT(min_max_size, max_size >= 2); - - // Returns a const_iterator to the first element of - // const_key_reference agumnet. - inline static const_iterator - begin(const_key_reference); - - // Returns a const_iterator to the after-last element of - // const_key_reference argument. - inline static const_iterator - end(const_key_reference); - - // Maps an element to a position. - inline static size_type - e_pos(e_type e); - - private: - - inline static const_iterator - begin_imp(const_key_reference, detail::false_type); - - inline static const_iterator - begin_imp(const_key_reference, detail::true_type); - - inline static const_iterator - end_imp(const_key_reference, detail::false_type); - - inline static const_iterator - end_imp(const_key_reference, detail::true_type); - - static detail::integral_constant<int, Reverse> s_rev_ind; - }; - -#include <ext/pb_ds/detail/trie_policy/string_trie_e_access_traits_imp.hpp> - -#undef PB_DS_CLASS_T_DEC -#undef PB_DS_CLASS_C_DEC - -#define PB_DS_CLASS_T_DEC \ - template<typename Const_Node_Iterator,typename Node_Iterator,class E_Access_Traits, typename Allocator> - -#define PB_DS_CLASS_C_DEC \ - trie_prefix_search_node_update<Const_Node_Iterator, Node_Iterator, E_Access_Traits,Allocator> - -#define PB_DS_BASE_C_DEC \ - detail::trie_policy_base<Const_Node_Iterator,Node_Iterator,E_Access_Traits, Allocator> - - // A node updator that allows tries to be searched for the range of - // values that match a certain prefix. - template<typename Const_Node_Iterator, - typename Node_Iterator, - typename E_Access_Traits, - typename Allocator> - class trie_prefix_search_node_update : private PB_DS_BASE_C_DEC - { - private: - typedef PB_DS_BASE_C_DEC base_type; - - public: - typedef typename base_type::key_type key_type; - typedef typename base_type::const_key_reference const_key_reference; - - // Element access traits. - typedef E_Access_Traits e_access_traits; - - // Const element iterator. - typedef typename e_access_traits::const_iterator const_e_iterator; - - // Allocator type. - typedef Allocator allocator_type; - - // Size type. - typedef typename allocator_type::size_type size_type; - typedef detail::null_node_metadata metadata_type; - typedef Const_Node_Iterator const_node_iterator; - typedef Node_Iterator node_iterator; - typedef typename const_node_iterator::value_type const_iterator; - typedef typename node_iterator::value_type iterator; - - // Finds the const iterator range corresponding to all values - // whose prefixes match r_key. - std::pair<const_iterator, const_iterator> - prefix_range(const_key_reference) const; - - // Finds the iterator range corresponding to all values whose - // prefixes match r_key. - std::pair<iterator, iterator> - prefix_range(const_key_reference); - - // Finds the const iterator range corresponding to all values - // whose prefixes match [b, e). - std::pair<const_iterator, const_iterator> - prefix_range(const_e_iterator, const_e_iterator) const; - - // Finds the iterator range corresponding to all values whose - // prefixes match [b, e). - std::pair<iterator, iterator> - prefix_range(const_e_iterator, const_e_iterator); - - protected: - // Called to update a node's metadata. - inline void - operator()(node_iterator node_it, const_node_iterator end_nd_it) const; - - private: - // Returns the const iterator associated with the just-after last element. - virtual const_iterator - end() const = 0; - - // Returns the iterator associated with the just-after last element. - virtual iterator - end() = 0; - - // Returns the const_node_iterator associated with the trie's root node. - virtual const_node_iterator - node_begin() const = 0; - - // Returns the node_iterator associated with the trie's root node. - virtual node_iterator - node_begin() = 0; - - // Returns the const_node_iterator associated with a just-after leaf node. - virtual const_node_iterator - node_end() const = 0; - - // Returns the node_iterator associated with a just-after leaf node. - virtual node_iterator - node_end() = 0; - - // Access to the cmp_fn object. - virtual const e_access_traits& - get_e_access_traits() const = 0; - - node_iterator - next_child(node_iterator, const_e_iterator, const_e_iterator, - node_iterator, const e_access_traits&); - }; - -#include <ext/pb_ds/detail/trie_policy/prefix_search_node_update_imp.hpp> - -#undef PB_DS_CLASS_C_DEC - -#define PB_DS_CLASS_C_DEC \ - trie_order_statistics_node_update<Const_Node_Iterator, Node_Iterator,E_Access_Traits, Allocator> - - // Functor updating ranks of entrees. - template<typename Const_Node_Iterator, - typename Node_Iterator, - typename E_Access_Traits, - typename Allocator> - class trie_order_statistics_node_update : private PB_DS_BASE_C_DEC - { - private: - typedef PB_DS_BASE_C_DEC base_type; - - public: - typedef E_Access_Traits e_access_traits; - typedef typename e_access_traits::const_iterator const_e_iterator; - typedef Allocator allocator_type; - typedef typename allocator_type::size_type size_type; - typedef typename base_type::key_type key_type; - typedef typename base_type::const_key_reference const_key_reference; - - typedef size_type metadata_type; - typedef Const_Node_Iterator const_node_iterator; - typedef Node_Iterator node_iterator; - typedef typename const_node_iterator::value_type const_iterator; - typedef typename node_iterator::value_type iterator; - - // Finds an entry by __order. Returns a const_iterator to the - // entry with the __order order, or a const_iterator to the - // container object's end if order is at least the size of the - // container object. - inline const_iterator - find_by_order(size_type) const; - - // Finds an entry by __order. Returns an iterator to the entry - // with the __order order, or an iterator to the container - // object's end if order is at least the size of the container - // object. - inline iterator - find_by_order(size_type); - - // Returns the order of a key within a sequence. For exapmle, if - // r_key is the smallest key, this method will return 0; if r_key - // is a key between the smallest and next key, this method will - // return 1; if r_key is a key larger than the largest key, this - // method will return the size of r_c. - inline size_type - order_of_key(const_key_reference) const; - - // Returns the order of a prefix within a sequence. For exapmle, - // if [b, e] is the smallest prefix, this method will return 0; if - // r_key is a key between the smallest and next key, this method - // will return 1; if r_key is a key larger than the largest key, - // this method will return the size of r_c. - inline size_type - order_of_prefix(const_e_iterator, const_e_iterator) const; - - private: - typedef typename base_type::const_reference const_reference; - typedef typename base_type::const_pointer const_pointer; - - typedef typename Allocator::template rebind<metadata_type>::other metadata_rebind; - typedef typename metadata_rebind::const_reference const_metadata_reference; - typedef typename metadata_rebind::reference metadata_reference; - - // Returns true if the container is empty. - virtual bool - empty() const = 0; - - // Returns the iterator associated with the trie's first element. - virtual iterator - begin() = 0; - - // Returns the iterator associated with the trie's - // just-after-last element. - virtual iterator - end() = 0; - - // Returns the const_node_iterator associated with the trie's root node. - virtual const_node_iterator - node_begin() const = 0; - - // Returns the node_iterator associated with the trie's root node. - virtual node_iterator - node_begin() = 0; - - // Returns the const_node_iterator associated with a just-after - // leaf node. - virtual const_node_iterator - node_end() const = 0; - - // Returns the node_iterator associated with a just-after leaf node. - virtual node_iterator - node_end() = 0; - - // Access to the cmp_fn object. - virtual e_access_traits& - get_e_access_traits() = 0; - - protected: - // 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, const_node_iterator) const; - - // Destructor. - virtual - ~trie_order_statistics_node_update(); - }; - -#include <ext/pb_ds/detail/trie_policy/order_statistics_imp.hpp> - -#undef PB_DS_CLASS_T_DEC -#undef PB_DS_CLASS_C_DEC -#undef PB_DS_BASE_C_DEC - -} // namespace __gnu_pbds - -#endif |