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 binomial_heap_base_.hpp * Contains an implementation class for a base of bi! . .."èdefault" .!ô..nomial heaps. */ #ifndef PB_DS_BINOMIAL_HEAP_BASE_HPP #define PB_DS_BINOMIAL_HEAP_BASE_HPP /* * Binomial heap base. * Vuillemin J is the mastah. * Modified from CLRS. */ #include #include #include #include #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ binomial_heap_base_ #ifdef _GLIBCXX_DEBUG #define PB_DS_BASE_C_DEC \ left_child_next_sibling_heap_ #else #define PB_DS_BASE_C_DEC \ left_child_next_sibling_heap_ #endif /** * class description = "8y|\|0|\/|i41 h34p 74813"> **/ template class binomial_heap_base_ : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; protected: typedef typename base_type::node node; typedef typename base_type::node_pointer node_pointer; typedef typename base_type::const_node_pointer const_node_pointer; public: typedef typename Allocator::size_type size_type; typedef typename Allocator::difference_type difference_type; typedef Value_Type value_type; typedef typename Allocator::template rebind< value_type>::other::pointer pointer; typedef typename Allocator::template rebind< value_type>::other::const_pointer const_pointer; typedef typename Allocator::template rebind< value_type>::other::reference reference; typedef typename Allocator::template rebind< value_type>::other::const_reference const_reference; typedef typename PB_DS_BASE_C_DEC::const_point_iterator const_point_iterator; typedef typename PB_DS_BASE_C_DEC::point_iterator point_iterator; typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator; typedef typename PB_DS_BASE_C_DEC::iterator iterator; typedef Cmp_Fn cmp_fn; typedef Allocator allocator; public: inline point_iterator push(const_reference r_val); void modify(point_iterator it, const_reference r_new_val); inline const_reference top() const; void pop(); void erase(point_iterator it); inline void clear(); template size_type erase_if(Pred pred); template void split(Pred pred, PB_DS_CLASS_C_DEC& other); void join(PB_DS_CLASS_C_DEC& other); protected: binomial_heap_base_(); binomial_heap_base_(const Cmp_Fn& r_cmp_fn); binomial_heap_base_(const PB_DS_CLASS_C_DEC& other); void swap(PB_DS_CLASS_C_DEC& other); ~binomial_heap_base_(); template void copy_from_range(It first_it, It last_it); inline void find_max(); #ifdef _GLIBCXX_DEBUG void assert_valid(bool strictly_binomial) const; void assert_max() const; #endif private: inline node_pointer fix(node_pointer p_nd) const; inline void insert_node(node_pointer p_nd); inline void remove_parentless_node(node_pointer p_nd); inline node_pointer join(node_pointer p_lhs, node_pointer p_rhs) const; #ifdef _GLIBCXX_DEBUG void assert_node_consistent(const_node_pointer, bool, bool) const; #endif protected: node_pointer m_p_max; }; #include #include #include #include #include #include #undef PB_DS_CLASS_C_DEC #undef PB_DS_CLASS_T_DEC #undef PB_DS_BASE_C_DEC } // namespace detail } // namespace __gnu_pbds #endif Í .X ..Î,#constructors_destructor_fn_imps.hppÏdebug_fn_imps.hppРbinomial_heap_.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 constructors_destructor_fn_imps.hpp * Contains an implementation for binomial_heap_. */ PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: binomial_heap_() { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: binomial_heap_(const Cmp_Fn& r_cmp_fn) : PB_DS_BASE_C_DEC(r_cmp_fn) { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: binomial_heap_(const PB_DS_CLASS_C_DEC& other) : PB_DS_BASE_C_DEC(other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~binomial_heap_() { } // -*- 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 for binomial_heap_. */ #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid() const { base_type::assert_valid(true); } #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 binomial_heap_.hpp * Contains an implementation class for a binomial heap. */ /* * Binomial heap. * Vuillemin J is the mastah. * Modified from CLRS. */ #include #include #include #include namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ binomial_heap_ #define PB_DS_BASE_C_DEC \ binomial_heap_base_ /** * class description = "8y|\|0|\/|i41 h34p 74813"> **/ template class binomial_heap_ : public PB_DS_BASE_C_DEC { private: typedef PB_DS_BASE_C_DEC base_type; typedef typename base_type::node_pointer node_pointer; typedef typename base_type::const_node_pointer const_node_pointer; public: typedef Value_Type value_type; typedef typename Allocator::size_type size_type; typedef typename Allocator::difference_type difference_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::const_point_iterator const_point_iterator; typedef typename base_type::point_iterator point_iterator; typedef typename base_type::const_iterator const_iterator; typedef typename base_type::iterator iterator; typedef typename base_type::cmp_fn cmp_fn; typedef typename base_type::allocator allocator; binomial_heap_(); binomial_heap_(const Cmp_Fn& r_cmp_fn); binomial_heap_(const PB_DS_CLASS_C_DEC& other); ~binomial_heap_(); protected: #ifdef _GLIBCXX_DEBUG void assert_valid() const; #endif }; #include #include #undef PB_DS_CLASS_C_DEC #undef PB_DS_CLASS_T_DEC #undef PB_DS_BASE_C_DEC } // namespace detail } // namespace __gnu_pbds Ñ .X ..Ò$mod_based_range_hashing.hppÓ,!direct_mask_range_hashing_imp.hppÔ$mask_based_range_hashing.hppÕ sample_range_hashing.hppÖ$sample_ranged_hash_fn.hpp×$sample_ranged_probe_fn.hppØ$quadratic_probe_fn_imp.hppÙsample_probe_fn.hppÚ( direct_mod_range_hashing_imp.hppÛ linear_probe_fn_imp.hppÜprobe_fn_base.hppÝranged_hash_fn.hppÞLranged_probe_fn.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 mod_based_range_hashing.hpp * Contains a range hashing policy base. */ #ifndef PB_DS_MOD_BASED_RANGE_HASHING_HPP #define PB_DS_MOD_BASED_RANGE_HASHING_HPP namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ mod_based_range_hashing< \ Size_Type> template class mod_based_range_hashing { protected: typedef Size_Type size_type; protected: void swap(PB_DS_CLASS_C_DEC& other); void notify_resized(size_type size); inline size_type range_hash(size_type hash) const; private: size_type m_size; }; PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { std::swap(m_size, other.m_size); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_resized(size_type size) { m_size = size; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: range_hash(size_type hash) const { return (hash % m_size); } #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_MOD_BASED_RANGE_HASHING_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 direct_mask_range_hashing_imp.hpp * Contains a range-hashing policy implementation */ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { mask_based_base::swap(other); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_resized(size_type size) { mask_based_base::notify_resized(size); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: operator()(size_type hash) const { return mask_based_base::range_hash(hash); } // -*- 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 mask_based_range_hashing.hpp * Contains a range hashing policy base. */ #ifndef PB_DS_MASK_BASED_RANGE_HASHING_HPP #define PB_DS_MASK_BASED_RANGE_HASHING_HPP namespace __gnu_pbds { namespace detail { #define PB_DS_CLASS_T_DEC template #define PB_DS_CLASS_C_DEC mask_based_range_hashing template class mask_based_range_hashing { protected: typedef Size_Type size_type; void swap(mask_based_range_hashing& other) { std::swap(m_mask, other.m_mask); } void notify_resized(size_type size); inline size_type range_hash(size_type hash) const { return size_type(hash & m_mask); } private: size_type m_mask; const static size_type s_num_bits_in_size_type; const static size_type s_highest_bit_1; }; PB_DS_CLASS_T_DEC const typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC::s_num_bits_in_size_type = sizeof(typename PB_DS_CLASS_C_DEC::size_type) << 3; PB_DS_CLASS_T_DEC const typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC::s_highest_bit_1 = static_cast(1) << (s_num_bits_in_size_type - 1); PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_resized(size_type size) { size_type i = 0; while (size ^ s_highest_bit_1) { size <<= 1; ++i; } m_mask = 1; i += 2; while (i++ < s_num_bits_in_size_type) m_mask = (m_mask << 1) ^ 1; } #undef PB_DS_CLASS_T_DEC #undef PB_DS_CLASS_C_DEC } // namespace detail } // 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 sample_range_hashing.hpp * Contains a range hashing policy. */ #ifndef PB_DS_SAMPLE_RANGE_HASHING_HPP #define PB_DS_SAMPLE_RANGE_HASHING_HPP // A sample range-hashing functor. class sample_range_hashing { public: // Size type. typedef size_t size_type; public: // Default constructor. sample_range_hashing(); // Copy constructor. sample_range_hashing(const sample_range_hashing& other); // Swaps content. inline void swap(sample_range_hashing& other); protected: // Notifies the policy object that the container's __size has changed to size. void notify_resized(size_type size); // Transforms the __hash value hash into a ranged-hash value. inline size_type operator()(size_type hash) const; }; #endif // #ifndef PB_DS_SAMPLE_RANGE_HASHING_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 sample_ranged_hash_fn.hpp * Contains a ranged hash policy. */ #ifndef PB_DS_SAMPLE_RANGED_HASH_FN_HPP #define PB_DS_SAMPLE_RANGED_HASH_FN_HPP // A sample ranged-hash functor. class sample_ranged_hash_fn { public: // Size type. typedef size_t size_type; public: // Default constructor. sample_ranged_hash_fn(); // Copy constructor. sample_ranged_hash_fn(const sample_ranged_hash_fn& other); // Swaps content. inline void swap(sample_ranged_hash_fn& other); protected: // Notifies the policy object that the container's __size has changed to size. void notify_resized(size_type size); // Transforms r_key into a position within the table. inline size_type operator()(const_key_reference r_key) const; }; #endif // #ifndef PB_DS_SAMPLE_RANGED_HASH_FN_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 sample_ranged_probe_fn.hpp * Contains a ranged probe policy. */ #ifndef PB_DS_SAMPLE_RANGED_PROBE_FN_HPP #define PB_DS_SAMPLE_RANGED_PROBE_FN_HPP // A sample ranged-probe functor. class sample_ranged_probe_fn { public: // Size type. typedef size_t size_type; public: // Default constructor. sample_ranged_probe_fn(); // Copy constructor. sample_ranged_probe_fn(const sample_ranged_probe_fn& other); // Swaps content. inline void swap(sample_ranged_probe_fn& other); protected: // Notifies the policy object that the container's __size has changed to size. void notify_resized(size_type size); // Transforms the const key reference r_key into the i-th position within the table. This method is called for each collision within the probe sequence. inline size_type operator()(const_key_reference r_key, size_t hash, size_type i) const; }; #endif // #ifndef PB_DS_SAMPLE_RANGED_PROBE_FN_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 quadratic_probe_fn_imp.hpp * Contains a probe policy implementation */ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: operator()(size_type i) const { return (i* i); } // -*- 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 sample_probe_fn.hpp * Contains a sample probe policy. */ #ifndef PB_DS_SAMPLE_PROBE_FN_HPP #define PB_DS_SAMPLE_PROBE_FN_HPP // A sample probe policy. class sample_probe_fn { public: // Size type. typedef size_t size_type; public: // Default constructor. sample_probe_fn(); // Copy constructor. sample_probe_fn(const sample_probe_fn& other); // Swaps content. inline void swap(sample_probe_fn& other); protected: // Returns the i-th offset from the hash value of some key r_key. inline size_type operator()(const_key_reference r_key, size_type i) const; }; #endif // #ifndef PB_DS_SAMPLE_PROBE_FN_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 direct_mod_range_hashing_imp.hpp * Contains a range-hashing policy implementation */ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { mod_based_base::swap(other); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_resized(size_type n) { mod_based_base::notify_resized(n); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: operator()(size_type hash) const { return mod_based_base::range_hash(hash); } // -*- 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 linear_probe_fn_imp.hpp * Contains a probe policy implementation */ PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: operator()(size_type i) const { return (i); } // -*- 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 probe_fn_base.hpp * Contains a probe policy base. */ #ifndef PB_DS_PROBE_FN_BASE_HPP #define PB_DS_PROBE_FN_BASE_HPP #include namespace __gnu_pbds { namespace detail { template class probe_fn_base { protected: ~probe_fn_base() { } }; } // namespace detail } // 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 ranged_hash_fn.hpp * Contains a unified ranged hash functor, allowing the hash tables * to deal with a single class for ranged hashing. */ #ifndef PB_DS_RANGED_HASH_FN_HPP #define PB_DS_RANGED_HASH_FN_HPP #include #include #include namespace __gnu_pbds { namespace detail { template class ranged_hash_fn; #define PB_DS_CLASS_T_DEC \ template #define PB_DS_CLASS_C_DEC \ ranged_hash_fn /** * Specialization 1 * The client supplies a hash function and a ranged hash function, * and requests that hash values not be stored. **/ template class ranged_hash_fn< Key, Hash_Fn, Allocator, Comb_Hash_Fn, false> : public Hash_Fn, public Comb_Hash_Fn { protected: typedef typename Allocator::size_type size_type; typedef Hash_Fn hash_fn_base; typedef Comb_Hash_Fn comb_hash_fn_base; typedef typename Allocator::template rebind< Key>::other key_allocator; typedef typename key_allocator::const_reference const_key_reference; ranged_hash_fn(size_type); ranged_hash_fn(size_type, const Hash_Fn&); ranged_hash_fn(size_type, const Hash_Fn&, const Comb_Hash_Fn&); void swap(PB_DS_CLASS_C_DEC&); void notify_resized(size_type); inline size_type operator()(const_key_reference) const; }; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size) { Comb_Hash_Fn::notify_resized(size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) : Hash_Fn(r_hash_fn) { Comb_Hash_Fn::notify_resized(size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn) : Hash_Fn(r_hash_fn), Comb_Hash_Fn(r_comb_hash_fn) { comb_hash_fn_base::notify_resized(size); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { comb_hash_fn_base::swap(other); std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_resized(size_type size) { comb_hash_fn_base::notify_resized(size); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: operator()(const_key_reference r_key) const { return (comb_hash_fn_base::operator()(hash_fn_base::operator()(r_key)));} #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 \ ranged_hash_fn /** * Specialization 2 * The client supplies a hash function and a ranged hash function, * and requests that hash values be stored. **/ template class ranged_hash_fn : public Hash_Fn, public Comb_Hash_Fn { protected: typedef typename Allocator::size_type size_type; typedef std::pair comp_hash; typedef Hash_Fn hash_fn_base; typedef Comb_Hash_Fn comb_hash_fn_base; typedef typename Allocator::template rebind::other key_allocator; typedef typename key_allocator::const_reference const_key_reference; ranged_hash_fn(size_type); ranged_hash_fn(size_type, const Hash_Fn&); ranged_hash_fn(size_type, const Hash_Fn&, const Comb_Hash_Fn&); void swap(PB_DS_CLASS_C_DEC&); void notify_resized(size_type); inline comp_hash operator()(const_key_reference) const; inline comp_hash operator()(const_key_reference, size_type) const; }; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size) { Comb_Hash_Fn::notify_resized(size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) : Hash_Fn(r_hash_fn) { Comb_Hash_Fn::notify_resized(size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn, const Comb_Hash_Fn& r_comb_hash_fn) : Hash_Fn(r_hash_fn), Comb_Hash_Fn(r_comb_hash_fn) { comb_hash_fn_base::notify_resized(size); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { comb_hash_fn_base::swap(other); std::swap((Hash_Fn& )(*this), (Hash_Fn& )other); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: notify_resized(size_type size) { comb_hash_fn_base::notify_resized(size); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::comp_hash PB_DS_CLASS_C_DEC:: operator()(const_key_reference r_key) const { const size_type hash = hash_fn_base::operator()(r_key); return std::make_pair(comb_hash_fn_base::operator()(hash), hash); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::comp_hash PB_DS_CLASS_C_DEC:: operator() #ifdef _GLIBCXX_DEBUG (const_key_reference r_key, size_type hash) const #else (const_key_reference /*r_key*/, size_type hash) const #endif { _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key)); return std::make_pair(comb_hash_fn_base::operator()(hash), hash); } #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 \ ranged_hash_fn /** * Specialization 3 * The client does not supply a hash function (by specifying * null_hash_fn as the Hash_Fn param