other); _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: initialize() { base_type::m_p_head->m_special = true; } // -*- C++ -*- // Copyright (C) 2005, 2006 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 debug_fn_imps.hpp * Contains an implementation class for splay_tree_. */ #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid() const { base_type::assert_valid(); const node_pointer p_head = base_type::m_p_head; assert_special_imp(p_head); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_special_imp(const node_pointer p_nd) const { if (p_nd == NULL) return; if (p_nd == base_type::m_p_head) { _GLIBCXX_DEBUG_ASSERT(p_nd->m_special); assert_special_imp(p_nd->m_p_parent); return; } _GLIBCXX_DEBUG_ASSERT(!p_nd->m_special); assert_special_imp(p_nd->m_p_left); assert_special_imp(p_nd->m_p_right); } #endif // -*- C++ -*- // Copyright (C) 2005, 2006 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 erase_fn_imps.hpp * Contains an implementation class for splay_tree_. */ PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: erase(const_key_reference r_key) { point_iterator it = find(r_key); if (it == base_type::end()) return false; erase(it); return true; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::iterator PB_DS_CLASS_C_DEC:: erase(iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid()); if (it == base_type::end()) return it; iterator ret_it = it; ++ret_it; erase_node(it.m_p_nd); _GLIBCXX_DEBUG_ONLY(assert_valid()); return ret_it; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::reverse_iterator PB_DS_CLASS_C_DEC:: erase(reverse_iterator it) { _GLIBCXX_DEBUG_ONLY(assert_valid()); if (it.m_p_nd == base_type::m_p_head) return (it); reverse_iterator ret_it = it; ++ret_it; erase_node(it.m_p_nd); _GLIBCXX_DEBUG_ONLY(assert_valid()); return ret_it; } PB_DS_CLASS_T_DEC template inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: erase_if(Pred pred) { _GLIBCXX_DEBUG_ONLY(assert_valid();) size_type num_ersd = 0; iterator it = base_type::begin(); while (it != base_type::end()) { if (pred(*it)) { ++num_ersd; it = erase(it); } else ++it; } _GLIBCXX_DEBUG_ONLY(assert_valid();) return num_ersd; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: erase_node(node_pointer p_nd) { _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); splay(p_nd); _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ASSERT(p_nd == this->m_p_head->m_p_parent); node_pointer p_l = p_nd->m_p_left; node_pointer p_r = p_nd->m_p_right; base_type::update_min_max_for_erased_node(p_nd); base_type::actual_erase_node(p_nd); if (p_r == NULL) { base_type::m_p_head->m_p_parent = p_l; if (p_l != NULL) p_l->m_p_parent = base_type::m_p_head; _GLIBCXX_DEBUG_ONLY(assert_valid();) return; } node_pointer p_target_r = leftmost(p_r); _GLIBCXX_DEBUG_ASSERT(p_target_r != NULL); p_r->m_p_parent = base_type::m_p_head; base_type::m_p_head->m_p_parent = p_r; splay(p_target_r); _GLIBCXX_DEBUG_ONLY(p_target_r->m_p_left = NULL); _GLIBCXX_DEBUG_ASSERT(p_target_r->m_p_parent == this->m_p_head); _GLIBCXX_DEBUG_ASSERT(this->m_p_head->m_p_parent == p_target_r); p_target_r->m_p_left = p_l; if (p_l != NULL) p_l->m_p_parent = p_target_r; _GLIBCXX_DEBUG_ONLY(assert_valid();) apply_update(p_target_r, (node_update* )this); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: leftmost(node_pointer p_nd) { _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); while (p_nd->m_p_left != NULL) p_nd = p_nd->m_p_left; return p_nd; } // -*- C++ -*- // Copyright (C) 2005, 2006 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 traits.hpp * Contains an implementation for splay_tree_. */ #ifndef PB_DS_SPLAY_TREE_NODE_AND_IT_TRAITS_HPP #define PB_DS_SPLAY_TREE_NODE_AND_IT_TRAITS_HPP #include namespace __gnu_pbds { namespace detail { template class Node_Update, class Allocator> struct tree_traits< Key, Mapped, Cmp_Fn, Node_Update, splay_tree_tag, Allocator> : public bin_search_tree_traits< Key, Mapped, Cmp_Fn, Node_Update, splay_tree_node_< typename types_traits< Key, Mapped, Allocator, false>::value_type, typename tree_node_metadata_selector< Key, Mapped, Cmp_Fn, Node_Update, Allocator>::type, Allocator>, Allocator> { }; template class Node_Update, class Allocator> struct tree_traits : public bin_search_tree_traits::value_type, typename tree_node_metadata_selector< Key, null_mapped_type, Cmp_Fn, Node_Update, Allocator>::type, Allocator>, Allocator> { }; } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_SPLAY_TREE_NODE_AND_IT_TRAITS_HPP // -*- C++ -*- // Copyright (C) 2005, 2006 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 splay_tree_.hpp * Contains an implementation class for splay_tree_. */ /* * This implementation uses an idea from the SGI STL (using a "header" node * which is needed for efficient iteration). Following is the SGI STL * copyright. * * Copyright (c) 1996,1997 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * */ #ifdef PB_DS_DATA_TRUE_INDICATOR #ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR #define PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR #include #endif #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR #define PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR #include #endif #endif #include #include #include #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_CLASS_NAME splay_tree_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_CLASS_NAME splay_tree_no_data_ #endif #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_BASE_CLASS_NAME bin_search_tree_data_ #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_BASE_CLASS_NAME bin_search_tree_no_data_ #endif #define PB_DS_CLASS_C_DEC \ PB_DS_CLASS_NAME #define PB_DS_BASE_C_DEC \ PB_DS_BASE_CLASS_NAME #ifdef PB_DS_DATA_TRUE_INDICATOR #define PB_DS_V2F(X) (X).first #define PB_DS_V2S(X) (X).second #define PB_DS_EP2VP(X)& ((X)->m_value) #endif #ifdef PB_DS_DATA_FALSE_INDICATOR #define PB_DS_V2F(X) (X) #define PB_DS_V2S(X) Mapped_Data() #define PB_DS_EP2VP(X)& ((X)->m_value.first) #endif // $p14y 7r33 7481. template class PB_DS_CLASS_NAME : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; typedef typename base_type::node_pointer node_pointer; public: typedef Allocator allocator; typedef typename Allocator::size_type size_type; typedef typename Allocator::difference_type difference_type; typedef Cmp_Fn cmp_fn; typedef typename base_type::key_type key_type; typedef typename base_type::key_pointer key_pointer; typedef typename base_type::const_key_pointer const_key_pointer; typedef typename base_type::key_reference key_reference; typedef typename base_type::const_key_reference const_key_reference; typedef typename base_type::mapped_type mapped_type; typedef typename base_type::mapped_pointer mapped_pointer; typedef typename base_type::const_mapped_pointer const_mapped_pointer; typedef typename base_type::mapped_reference mapped_reference; typedef typename base_type::const_mapped_reference const_mapped_reference; typedef typename base_type::value_type value_type; typedef typename base_type::pointer pointer; typedef typename base_type::const_pointer const_pointer; typedef typename base_type::reference reference; typedef typename base_type::const_reference const_reference; typedef typename base_type::point_iterator point_iterator; typedef typename base_type::const_iterator const_point_iterator; typedef typename base_type::iterator iterator; typedef typename base_type::const_iterator const_iterator; typedef typename base_type::reverse_iterator reverse_iterator; typedef typename base_type::const_reverse_iterator const_reverse_iterator; typedef typename base_type::node_update node_update; PB_DS_CLASS_NAME(); PB_DS_CLASS_NAME(const Cmp_Fn&); PB_DS_CLASS_NAME(const Cmp_Fn&, const node_update&); PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); void swap(PB_DS_CLASS_C_DEC&); template void copy_from_range(It, It); void initialize(); inline std::pair insert(const_reference r_value); inline mapped_reference operator[](const_key_reference r_key) { #ifdef PB_DS_DATA_TRUE_INDICATOR _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) std::pair ins_pair = insert_leaf_imp(value_type(r_key, mapped_type())); ins_pair.first.m_p_nd->m_special = false; _GLIBCXX_DEBUG_ONLY(base_type::assert_valid()); splay(ins_pair.first.m_p_nd); _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) return ins_pair.first.m_p_nd->m_value.second; #else insert(r_key); return base_type::s_null_mapped; #endif } inline point_iterator find(const_key_reference); inline const_point_iterator find(const_key_reference) const; inline bool erase(const_key_reference); inline iterator erase(iterator it); inline reverse_iterator erase(reverse_iterator); template inline size_type erase_if(Pred); void join(PB_DS_CLASS_C_DEC&); void split(const_key_reference, PB_DS_CLASS_C_DEC&); private: inline std::pair insert_leaf_imp(const_reference); inline node_pointer find_imp(const_key_reference); inline const node_pointer find_imp(const_key_reference) const; #ifdef _GLIBCXX_DEBUG void assert_valid() const; void assert_special_imp(const node_pointer) const; #endif void splay(node_pointer); inline void splay_zig_zag_left(node_pointer, node_pointer, node_pointer); inline void splay_zig_zag_right(node_pointer, node_pointer, node_pointer); inline void splay_zig_zig_left(node_pointer, node_pointer, node_pointer); inline void splay_zig_zig_right(node_pointer, node_pointer, node_pointer); inline void splay_zz_start(node_pointer, node_pointer, node_pointer); inline void splay_zz_end(node_pointer, node_pointer, node_pointer); inline node_pointer leftmost(node_pointer); void erase_node(node_pointer); }; #include #include #include #include #include #include #include #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #undef PB_DS_CLASS_NAME #undef PB_DS_BASE_CLASS_NAME #undef PB_DS_BASE_C_DEC #undef PB_DS_V2F #undef PB_DS_EP2VP #undef PB_DS_V2S } // namespace detail } // namespace __gnu_pbds // -*- C++ -*- // Copyright (C) 2005, 2006, 2007 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 list_update_policy.hpp * Contains policies for list update containers. */ #ifndef PB_DS_LU_POLICY_HPP #define PB_DS_LU_POLICY_HPP #include #include namespace __gnu_pbds { // A null type that means that each link in a list-based container // does not actually need metadata. struct null_lu_metadata { }; #define PB_DS_CLASS_T_DEC template #define PB_DS_CLASS_C_DEC move_to_front_lu_policy // A list-update policy that unconditionally moves elements to the // front of the list. template > class move_to_front_lu_policy { public: typedef Allocator allocator; // Metadata on which this functor operates. typedef null_lu_metadata metadata_type; // Reference to metadata on which this functor operates. typedef typename allocator::template rebind::other metadata_rebind; typedef typename metadata_rebind::reference metadata_reference; // Creates a metadata object. metadata_type operator()() const; // Decides whether a metadata object should be moved to the front // of the list. inline bool operator()(metadata_reference r_metadata) const; private: static null_lu_metadata s_metadata; }; #include #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #define PB_DS_CLASS_T_DEC template #define PB_DS_CLASS_C_DEC counter_lu_policy // A list-update policy that moves elements to the front of the list // based on the counter algorithm. template > class counter_lu_policy : private detail::counter_lu_policy_base { public: typedef Allocator allocator; enum { max_count = Max_Count }; typedef typename allocator::size_type size_type; // Metadata on which this functor operates. typedef detail::counter_lu_metadata metadata_type; // Reference to metadata on which this functor operates. typedef typename Allocator::template rebind::other metadata_rebind; typedef typename metadata_rebind::reference metadata_reference; // Creates a metadata object. metadata_type operator()() const; // Decides whether a metadata object should be moved to the front // of the list. bool operator()(metadata_reference r_metadata) const; private: typedef detail::counter_lu_policy_base base_type; }; #include #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC } // namespace __gnu_pbds #endif // -*- C++ -*- // Copyright (C) 2005, 2006, 2007, 2008 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 exception.hpp * Contains exception classes. */ #ifndef PB_DS_EXCEPTION_HPP #define PB_DS_EXCEPTION_HPP #include #include namespace __gnu_pbds { // Base class for exceptions. struct container_error : public std::logic_error { container_error() : std::logic_error(__N("__gnu_pbds::container_error")) { } }; // An entry cannot be inserted into a container object for logical // reasons (not, e.g., if memory is unabvailable, in which case // the allocator's exception will be thrown). struct insert_error : public container_error { }; // A join cannot be performed logical reasons (i.e., the ranges of // the two container objects being joined overlaps. struct join_error : public container_error { }; // A container cannot be resized. struct resize_error : public container_error { }; #if __EXCEPTIONS inline void __throw_container_error(void) { throw container_error(); } inline void __throw_insert_error(void) { throw insert_error(); } inline void __throw_join_error(void) { throw join_error(); } inline void __throw_resize_error(void) { throw resize_error(); } #else inline void __throw_container_error(void) { std::abort(); } inline void __throw_insert_error(void) { std::abort(); } inline void __throw_join_error(void) { std::abort(); } inline void __throw_resize_error(void) { std::abort(); } #endif } // namespace __gnu_pbds #endif // -*- C++ -*- // Copyright (C) 2005, 2006 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 tree_policy.hpp * Contains tree-related policies. */ #ifndef PB_DS_TREE_POLICY_HPP #define PB_DS_TREE_POLICY_HPP #include #include #include namespace __gnu_pbds { // A null node updator, indicating that no node updates are required. template struct null_tree_node_update { }; #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ tree_order_statistics_node_update #define PB_DS_BASE_C_DEC \ detail::basic_tree_policy_base // Functor updating ranks of entrees. template class tree_order_statistics_node_update : private PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; public: typedef Cmp_Fn cmp_fn; typedef Allocator allocator; typedef typename allocator::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 order) 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 order); // 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 r_key) const; private: // Const reference to the container's value-type. typedef typename base_type::const_reference const_reference; // Const pointer to the container's value-type. typedef typename base_type::const_pointer const_pointer; typedef typename allocator::template rebind::other metadata_rebind; // Const metadata reference. typedef typename metadata_rebind::const_reference const_metadata_reference; // Metadata reference. typedef typename metadata_rebind::reference metadata_reference; // Returns the const_node_iterator associated with the tree's root node. virtual const_node_iterator node_begin() const = 0; // Returns the node_iterator associated with the tree'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 cmp_fn& get_cmp_fn() = 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 node_it, const_node_iterator end_nd_it) const; virtual ~tree_order_statistics_node_update(); }; #include #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC #undef PB_DS_BASE_C_DEC } // namespace __gnu_pbds #endif // -*- C++ -*- // Copyright (C) 2005, 2006 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 tag_and_trait.hpp * Contains tags and traits, e.g., ones describing underlying * data structures. */ #ifndef PB_DS_TAG_AND_TRAIT_HPP #define PB_DS_TAG_AND_TRAIT_HPP #include /** * @namespace __gnu_pbds * @brief GNU extensions for policy-based data structures for public use. */ namespace __gnu_pbds { // A trivial iterator tag. Signifies that the iterators has none of // the STL's movement abilities. struct trivial_iterator_tag { }; // Prohibit moving trivial iterators. typedef void trivial_iterator_difference_type; // Signifies a basic invalidation guarantee that any iterator, // pointer, or reference to a container object's mapped value type // is valid as long as the container is not modified. struct basic_invalidation_guarantee { }; // Signifies an invalidation guarantee that includes all those of // its base, and additionally, that any point-type iterator, // pointer, or reference to a container object's mapped value type // is valid as long as its corresponding entry has not be erased, // regardless of modifications to the container object. struct point_invalidation_guarantee : public basic_invalidation_guarantee { }; // Signifies an invalidation guarantee that includes all those of // its base, and additionally, that any range-type iterator // (including the returns of begin() and end()) is in the correct // relative positions to other range-type iterators as long as its // corresponding entry has not be erased, regardless of // modifications to the container object. struct range_invalidation_guarantee : public point_invalidation_guarantee { }; // A mapped-policy indicating that an associative container is a set. // XXX should this be a trait of the form is_set ?? struct null_mapped_type { }; // Base data structure tag. struct container_tag { }; // Basic associative-container. struct associative_container_tag : public container_tag { }; // Basic hash. struct basic_hash_tag : public associative_container_tag { }; // Collision-chaining hash. struct cc_hash_tag : public basic_hash_tag { }; // General-probing hash. struct gp_hash_tag : public basic_hash_tag { }; // Basic tree. struct basic_tree_tag : public associative_container_tag { }; // tree. struct tree_tag : public basic_tree_tag { }; // Red-black tree. struct rb_tree_tag : public tree_tag { }; // Splay tree. struct splay_tree_tag : public tree_tag { }; // Ordered-vector tree. struct ov_tree_tag : public tree_tag { }; // trie. struct trie_tag : public basic_tree_tag { }; // PATRICIA trie. struct pat_trie_tag : public trie_tag { }; // List-update. struct list_update_tag : public associative_container_tag { }; // Basic priority-queue. struct priority_queue_tag : public container_tag { }; // Pairing-heap. struct pairing_heap_tag : public priority_queue_tag { }; // Binomial-heap. struct binomial_heap_tag : public priority_queue_tag { }; // Redundant-counter binomial-heap. struct rc_binomial_heap_tag : public priority_queue_tag { }; // Binary-heap (array-based). struct binary_heap_tag : public priority_queue_tag { }; // Thin heap. struct thin_heap_tag : public priority_queue_tag { }; template struct container_traits_base; template<> struct container_traits_base { typedef cc_hash_tag container_category; typedef point_invalidation_guarantee invalidation_guarantee; enum { order_preserving = false, erase_can_throw = false, split_join_can_throw = false, reverse_iteration = false }; }; template<> struct container_traits_base { typedef gp_hash_tag container_category; typedef basic_invalidation_guarantee invalidation_guarantee; enum { order_preserving = false, erase_can_throw = false, split_join_can_throw = false, reverse_iteration = false }; }; template<> struct container_traits_base { typedef rb_tree_tag container_category; typedef range_invalidation_guarantee invalidation_guarantee; enum { order_preserving = true, erase_can_throw = false, split_join_can_throw = false, reverse_iteration = true }; }; template<> struct container_traits_base { typedef splay_tree_tag container_category; typedef range_invalidation_guarantee invalidation_guarantee; enum { order_preserving = true, erase_can_throw = false, split_join_can_throw = false, reverse_iteration = true }; }; template<> struct container_traits_base { typedef ov_tree_tag container_category; typedef basic_invalidation_guarantee invalidation_guarantee; enum { order_preserving = true, erase_can_throw = true, split_join_can_throw = true, reverse_iteration = false }; }; template<> struct container_traits_base { typedef pat_trie_tag container_category; typedef range_invalidation_guarantee invalidation_guarantee; enum { order_preserving = true, erase_can_throw = false, split_join_can_throw = true, reverse_iteration = true }; }; template<> struct container_traits_base { typedef list_update_tag container_category; typedef point_invalidation_guarantee invalidation_guarantee; enum { order_preserving = false, erase_can_throw = false, split_join_can_throw = false, reverse_iteration = false }; }; template<> struct container_traits_base { typedef pairing_heap_tag container_category; typedef point_invalidation_guarantee invalidation_guarantee; enum { order_preserving = false, erase_can_throw = false, split_join_can_throw = false, reverse_iteration = false }; }; template<> struct container_traits_base { typedef thin_heap_tag container_category; typedef point_invalidation_guarantee invalidation_guarantee; enum { order_preserving = false, erase_can_throw = false, split_join_can_throw = false, reverse_iteration = false }; }; template<> struct container_traits_base { typedef binomial_heap_tag container_category; typedef point_invalidation_guarantee invalidation_guarantee; enum { order_preserving = false, erase_can_throw = false, split_join_can_throw = false, reverse_iteration = false }; }; template<> struct container_traits_base { typedef rc_binomial_heap_tag container_category; typedef point_invalidation_guarantee invalidation_guarantee; enum { order_preserving = false, erase_can_throw = false, split_join_can_throw = false, reverse_iteration = false }; }; template<> struct container_traits_base { typedef binary_heap_tag container_category; typedef basic_invalidation_guarantee invalidation_guarantee; enum { order_preserving = false, erase_can_throw = false, split_join_can_throw = true, reverse_iteration = false }; }; // See Matt Austern for the name, S. Meyers MEFC++ #2, others. template struct container_traits : public container_traits_base { typedef Cntnr container_type; typedef typename Cntnr::container_category container_category; typedef container_traits_base base_type; typedef typename base_type::invalidation_guarantee invalidation_guarantee; enum { order_preserving = base_type::order_preserving, erase_can_throw = base_type::erase_can_throw, split_join_can_throw = base_type::split_join_can_throw, reverse_iteration = base_type::reverse_iteration }; }; } // namespace __gnu_pbds #endif // Hashing set implementation -*- C++ -*- // Copyright (C) 2001, 2002, 2004, 2005, 2006 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) 1996 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Silicon Graphics makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * * * Copyright (c) 1994 * Hewlett-Packard Company * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation. Hewlett-Packard Company makes no * representations about the suitability of this software for any * purpose. It is provided "as is" without express or implied warranty. * */ /** @file backward/hash_set * This file is a GNU extension to the Standard C++ Library (possibly * containing extensions from the HP/SGI STL subset). */ #ifndef _HASH_SET #define _HASH_SET 1 #include "backward_warning.h" #include #include #include _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) using std::equal_to; using std::allocator; using std::pair; using std::_Identity; /** * This is an SGI extension. * @ingroup SGIextensions * @doctodo */ template, class _EqualKey = equal_to<_Value>, class _Alloc = allocator<_Value> > class hash_set { // concept requirements __glibcxx_class_requires(_Value, _SGIAssignableConcept) __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) private: typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, _EqualKey, _Alloc> _Ht; _Ht _M_ht; public: typedef typename _Ht::key_type key_type; typedef typename _Ht::value_type value_type; typedef typename _Ht::hasher hasher; typedef typename _Ht::key_equal key_equal; typedef typename _Ht::size_type size_type; typedef typename _Ht::difference_type difference_type; typedef typename _Alloc::pointer pointer; typedef typename _Alloc::const_pointer const_pointer; typedef typename _Alloc::reference reference; typedef typename _Alloc::const_reference const_reference; typedef typename _Ht::const_iterator iterator; typedef typename _Ht::const_iterator const_iterator; typedef typename _Ht::allocator_type allocator_type; hasher hash_funct() const { return _M_ht.hash_funct(); } key_equal key_eq() const { return _M_ht.key_eq(); } allocator_type get_allocator() const { return _M_ht.get_allocator(); } hash_set() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} explicit hash_set(size_type __n) : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} hash_set(size_type __n, const hasher& __hf) : _M_ht(__n, __hf, key_equal(), allocator_type()) {} hash_set(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a = allocator_type()) : _M_ht(__n, __hf, __eql, __a) {} template hash_set(_InputIterator __f, _InputIterator __l) : _M_ht(100, hasher(), key_equal(), allocator_type()) { _M_ht.insert_unique(__f, __l); } template hash_set(_InputIterator __f, _InputIterator __l, size_type __n) : _M_ht(__n, hasher(), key_equal(), allocator_type()) { _M_ht.insert_unique(__f, __l); } template hash_set(_InputIterator __f, _InputIterator __l, size_type __n, const hasher& __hf) : _M_ht(__n, __hf, key_equal(), allocator_type()) { _M_ht.insert_unique(__f, __l); } template hash_set(_InputIterator __f, _InputIterator __l, size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a = allocator_type()) : _M_ht(__n, __hf, __eql, __a) { _M_ht.insert_unique(__f, __l); } size_type size() const { return _M_ht.size(); } size_type max_size() const { return _M_ht.max_size(); } bool empty() const { return _M_ht.empty(); } void swap(hash_set& __hs) { _M_ht.swap(__hs._M_ht); } template friend bool operator==(const hash_set<_Val, _HF, _EqK, _Al>&, const hash_set<_Val, _HF, _EqK, _Al>&); iterator begin() const { return _M_ht.begin(); } iterator end() const { return _M_ht.end(); } pair insert(const value_type& __obj) { pair __p = _M_ht.insert_unique(__obj); return pair(__p.first, __p.second); } template void insert(_InputIterator __f, _InputIterator __l) { _M_ht.insert_unique(__f, __l); } pair insert_noresize(const value_type& __obj) { pair __p = _M_ht.insert_unique_noresize(__obj); return pair(__p.first, __p.second); } iterator find(const key_type& __key) const { return _M_ht.find(__key); } size_type count(const key_type& __key) const { return _M_ht.count(__key); } pair equal_range(const key_type& __key) const { return _M_ht.equal_range(__key); } size_type erase(const key_type& __key) {return _M_ht.erase(__key); } void erase(iterator __it) { _M_ht.erase(__it); } void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } void clear() { _M_ht.clear(); } void resize(size_type __hint) { _M_ht.resize(__hint); } size_type bucket_count() const { return _M_ht.bucket_count(); } size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } size_type elems_in_bucket(size_type __n) const { return _M_ht.elems_in_bucket(__n); } }; template inline bool operator==(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) { return __hs1._M_ht == __hs2._M_ht; } template inline bool operator!=(const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs1, const hash_set<_Value, _HashFcn, _EqualKey, _Alloc>& __hs2) { return !(__hs1 == __hs2); } template inline void swap(hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, hash_set<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) { __hs1.swap(__hs2); } /** * This is an SGI extension. * @ingroup SGIextensions * @doctodo */ template, class _EqualKey = equal_to<_Value>, class _Alloc = allocator<_Value> > class hash_multiset { // concept requirements __glibcxx_class_requires(_Value, _SGIAssignableConcept) __glibcxx_class_requires3(_HashFcn, size_t, _Value, _UnaryFunctionConcept) __glibcxx_class_requires3(_EqualKey, _Value, _Value, _BinaryPredicateConcept) private: typedef hashtable<_Value, _Value, _HashFcn, _Identity<_Value>, _EqualKey, _Alloc> _Ht; _Ht _M_ht; public: typedef typename _Ht::key_type key_type; typedef typename _Ht::value_type value_type; typedef typename _Ht::hasher hasher; typedef typename _Ht::key_equal key_equal; typedef typename _Ht::size_type size_type; typedef typename _Ht::difference_type difference_type; typedef typename _Alloc::pointer pointer; typedef typename _Alloc::const_pointer const_pointer; typedef typename _Alloc::reference reference; typedef typename _Alloc::const_reference const_reference; typedef typename _Ht::const_iterator iterator; typedef typename _Ht::const_iterator const_iterator; typedef typename _Ht::allocator_type allocator_type; hasher hash_funct() const { return _M_ht.hash_funct(); } key_equal key_eq() const { return _M_ht.key_eq(); } allocator_type get_allocator() const { return _M_ht.get_allocator(); } hash_multiset() : _M_ht(100, hasher(), key_equal(), allocator_type()) {} explicit hash_multiset(size_type __n) : _M_ht(__n, hasher(), key_equal(), allocator_type()) {} hash_multiset(size_type __n, const hasher& __hf) : _M_ht(__n, __hf, key_equal(), allocator_type()) {} hash_multiset(size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a = allocator_type()) : _M_ht(__n, __hf, __eql, __a) {} template hash_multiset(_InputIterator __f, _InputIterator __l) : _M_ht(100, hasher(), key_equal(), allocator_type()) { _M_ht.insert_equal(__f, __l); } template hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n) : _M_ht(__n, hasher(), key_equal(), allocator_type()) { _M_ht.insert_equal(__f, __l); } template hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, const hasher& __hf) : _M_ht(__n, __hf, key_equal(), allocator_type()) { _M_ht.insert_equal(__f, __l); } template hash_multiset(_InputIterator __f, _InputIterator __l, size_type __n, const hasher& __hf, const key_equal& __eql, const allocator_type& __a = allocator_type()) : _M_ht(__n, __hf, __eql, __a) { _M_ht.insert_equal(__f, __l); } size_type size() const { return _M_ht.size(); } size_type max_size() const { return _M_ht.max_size(); } bool empty() const { return _M_ht.empty(); } void swap(hash_multiset& hs) { _M_ht.swap(hs._M_ht); } templ>7?7@7A7B7ate friend bool operator==(const hash_multiset<_Val, _HF, _EqK, _Al>&, const hash_multiset<_Val, _HF, _EqK, _Al>&); iterator begin() const { return _M_ht.begin(); } iterator end() const { return _M_ht.end(); } iterator insert(const value_type& __obj) { return _M_ht.insert_equal(__obj); } template void insert(_InputIterator __f, _InputIterator __l) { _M_ht.insert_equal(__f,__l); } iterator insert_noresize(const value_type& __obj) { return _M_ht.insert_equal_noresize(__obj); } iterator find(const key_type& __key) const { return _M_ht.find(__key); } size_type count(const key_type& __key) const { return _M_ht.count(__key); } pair equal_range(const key_type& __key) const { return _M_ht.equal_range(__key); } size_type erase(const key_type& __key) { return _M_ht.erase(__key); } void erase(iterator __it) { _M_ht.erase(__it); } void erase(iterator __f, iterator __l) { _M_ht.erase(__f, __l); } void clear() { _M_ht.clear(); } void resize(size_type __hint) { _M_ht.resize(__hint); } size_type bucket_count() const { return _M_ht.bucket_count(); } size_type max_bucket_count() const { return _M_ht.max_bucket_count(); } size_type elems_in_bucket(size_type __n) const { return _M_ht.elems_in_bucket(__n); } }; template inline bool operator==(const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs1, const hash_multiset<_Val, _HashFcn, _EqualKey, _Alloc>& __hs2) { return __hs1._M_ht == __hs2._M_ht; } template inline bool operator!=(const hash