:other::reference reference; typedef typename Allocator::template rebind< typename remove_const< value_type>::type>::other::const_pointer const_pointer; static inline const_key_reference extract_key(const_reference r_val) { return (r_val.first); } virtual it_type end() = 0; it_type end_iterator() const { return (const_cast(this)->end()); } virtual ~basic_tree_policy_base() { } }; template struct basic_tree_policy_base< Const_Node_Iterator, Const_Node_Iterator, Allocator> { protected: typedef typename Const_Node_Iterator::value_type it_type; typedef typename std::iterator_traits< it_type>::value_type value_type; typedef value_type key_type; typedef typename Allocator::template rebind< typename remove_const< key_type>::type>::other::const_reference const_key_reference; typedef typename Allocator::template rebind< typename remove_const< value_type>::type>::other::const_reference const_reference; typedef typename Allocator::template rebind< typename remove_const< value_type>::type>::other::reference reference; typedef typename Allocator::template rebind< typename remove_const< value_type>::type>::other::const_pointer const_pointer; static inline const_key_reference extract_key(const_reference r_val) { return (r_val); } virtual it_type end() const = 0; it_type end_iterator() const { return (end()); } virtual ~basic_tree_policy_base() { } }; #undef PB_DS_CLASS_C_DEC } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_TREE_LIKE_POLICY_BASE_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 traits.hpp * Contains an implementation class for tree-like classes. */ #ifndef PB_DS_NODE_AND_IT_TRAITS_HPP #define PB_DS_NODE_AND_IT_TRAITS_HPP #include #include #include #include namespace __gnu_pbds { namespace detail { template class Node_Update, class Tag, class Allocator> struct tree_traits; template class Node_Update, class Tag, class Allocator> struct trie_traits; } // namespace detail } // namespace __gnu_pbds #include #include #include #include #endif // #ifndef PB_DS_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 null_node_metadata.hpp * Contains an implementation class for tree-like classes. */ #ifndef PB_DS_NULL_NODE_METADATA_HPP #define PB_DS_NULL_NODE_METADATA_HPP #include namespace __gnu_pbds { namespace detail { template struct dumconst_node_iterator { private: typedef typename types_traits::pointer const_iterator; public: typedef const_iterator value_type; typedef const_iterator const_reference; typedef const_reference reference; }; struct null_node_metadata { }; } // namespace detail } // namespace __gnu_pbds #endif † .X ..‡point_iterator.hppˆ iterator.hpp‰ const_point_iterator.hppŠ˜const_iterator.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 point_iterator.hpp * Contains an iterator class returned by the tables' find and insert * methods. */ // Find type iterator. class point_iterator_ { public: // Category. typedef trivial_iterator_tag iterator_category; // Difference type. typedef trivial_iterator_difference_type difference_type; // Iterator's value type. typedef value_type_ value_type; // Iterator's pointer type. typedef pointer_ pointer; // Iterator's const pointer type. typedef const_pointer_ const_pointer; // Iterator's reference type. typedef reference_ reference; // Iterator's const reference type. typedef const_reference_ const_reference; public: // Default constructor. inline point_iterator_() : m_p_value(NULL) { } // Copy constructor. inline point_iterator_(const point_iterator_& other) : m_p_value(other.m_p_value) { } // Access. inline pointer operator->() const { _GLIBCXX_DEBUG_ASSERT(m_p_value != NULL); return (m_p_value); } // Access. inline reference operator*() const { _GLIBCXX_DEBUG_ASSERT(m_p_value != NULL); return (*m_p_value); } // Compares content to a different iterator object. inline bool operator==(const point_iterator_& other) const { return (m_p_value == other.m_p_value); } // Compares content to a different iterator object. inline bool operator==(const const_point_iterator_& other) const { return (m_p_value == other.m_p_value); } // Compares content to a different iterator object. inline bool operator!=(const point_iterator_& other) const { return (m_p_value != other.m_p_value); } // Compares content (negatively) to a different iterator object. inline bool operator!=(const const_point_iterator_& other) const { return (m_p_value != other.m_p_value); } inline point_iterator_(pointer p_value) : m_p_value(p_value) { } protected: friend class const_point_iterator_; friend class PB_DS_CLASS_C_DEC; protected: pointer m_p_value; }; // -*- 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 iterator.hpp * Contains an iterator_ class used for ranging over the elements of the * table. */ // Range-type iterator. class iterator_ : public const_iterator_ { public: // Category. typedef std::forward_iterator_tag iterator_category; // Difference type. typedef typename Allocator::difference_type difference_type; // Iterator's value type. typedef value_type_ value_type; // Iterator's pointer type. typedef pointer_ pointer; // Iterator's const pointer type. typedef const_pointer_ const_pointer; // Iterator's reference type. typedef reference_ reference; // Iterator's const reference type. typedef const_reference_ const_reference; public: // Default constructor. inline iterator_() : const_iterator_(NULL, PB_DS_GEN_POS(), NULL) { } // Conversion to a point-type iterator. inline operator point_iterator_() { return (point_iterator_( const_cast(const_iterator_::m_p_value))); } // Conversion to a point-type iterator. inline operator const point_iterator_() const { return (point_iterator_( const_cast(const_iterator_::m_p_value))); } // Access. inline pointer operator->() const { _GLIBCXX_DEBUG_ASSERT(base_type::m_p_value != NULL); return (const_cast(base_type::m_p_value)); } // Access. inline reference operator*() const { _GLIBCXX_DEBUG_ASSERT(base_type::m_p_value != NULL); return (const_cast(*base_type::m_p_value)); } // Increments. inline iterator_& operator++() { base_type::m_p_tbl->inc_it_state(base_type::m_p_value, base_type::m_pos); return (*this); } // Increments. inline iterator_ operator++(int) { iterator_ ret =* this; base_type::m_p_tbl->inc_it_state(base_type::m_p_value, base_type::m_pos); return (ret); } protected: typedef const_iterator_ base_type; protected: /** * Constructor used by the table to initiate the generalized * pointer and position (e.g., this is called from within a find() * of a table. * */ inline iterator_(pointer p_value, PB_DS_GEN_POS pos, PB_DS_CLASS_C_DEC* p_tbl) : const_iterator_(p_value, pos, p_tbl) { } friend class PB_DS_CLASS_C_DEC; }; // -*- 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 const_point_iterator.hpp * Contains an iterator class returned by the tables' const find and insert * methods. */ class point_iterator_; // Const point-type iterator. class const_point_iterator_ { public: // Category. typedef trivial_iterator_tag iterator_category; // Difference type. typedef trivial_iterator_difference_type difference_type; // Iterator's value type. typedef value_type_ value_type; // Iterator's pointer type. typedef pointer_ pointer; // Iterator's const pointer type. typedef const_pointer_ const_pointer; // Iterator's reference type. typedef reference_ reference; // Iterator's const reference type. typedef const_reference_ const_reference; public: inline const_point_iterator_(const_pointer p_value) : m_p_value(p_value) { } // Default constructor. inline const_point_iterator_() : m_p_value(NULL) { } // Copy constructor. inline const_point_iterator_(const const_point_iterator_& other) : m_p_value(other.m_p_value) { } // Copy constructor. inline const_point_iterator_(const point_iterator_& other) : m_p_value(other.m_p_value) { } // Access. inline const_pointer operator->() const { _GLIBCXX_DEBUG_ASSERT(m_p_value != NULL); return (m_p_value); } // Access. inline const_reference operator*() const { _GLIBCXX_DEBUG_ASSERT(m_p_value != NULL); return (*m_p_value); } // Compares content to a different iterator object. inline bool operator==(const point_iterator_& other) const { return (m_p_value == other.m_p_value); } // Compares content to a different iterator object. inline bool operator==(const const_point_iterator_& other) const { return (m_p_value == other.m_p_value); } // Compares content (negatively) to a different iterator object. inline bool operator!=(const point_iterator_& other) const { return (m_p_value != other.m_p_value); } // Compares content (negatively) to a different iterator object. inline bool operator!=(const const_point_iterator_& other) const { return (m_p_value != other.m_p_value); } protected: const_pointer m_p_value; friend class point_iterator_; friend class PB_DS_CLASS_C_DEC; }; // -*- 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 const_iterator.hpp * Contains an iterator class used for const ranging over the elements of the * table. */ // Const range-type iterator. class const_iterator_ : public const_point_iterator_ { public: // Category. typedef std::forward_iterator_tag iterator_category; // Difference type. typedef typename Allocator::difference_type difference_type; // Iterator's value type. typedef value_type_ value_type; // Iterator's pointer type. typedef pointer_ pointer; // Iterator's const pointer type. typedef const_pointer_ const_pointer; // Iterator's reference type. typedef reference_ reference; // Iterator's const reference type. typedef const_reference_ const_reference; public: // Default constructor. inline const_iterator_() : m_p_tbl(NULL) { } // Increments. inline const_iterator_& operator++() { m_p_tbl->inc_it_state(base_type::m_p_value, m_pos); return (*this); } // Increments. inline const_iterator_ operator++(int) { const_iterator_ ret =* this; m_p_tbl->inc_it_state(base_type::m_p_value, m_pos); return (ret); } protected: typedef const_point_iterator_ base_type; protected: /** * Constructor used by the table to initiate the generalized * pointer and position (e.g., this is called from within a find() * of a table. * */ inline const_iterator_(const_pointer_ p_value, PB_DS_GEN_POS pos, const PB_DS_CLASS_C_DEC* p_tbl) : const_point_iterator_(p_value), m_p_tbl(p_tbl), m_pos(pos) { } protected: /** * Pointer to the table object which created the iterator (used for * incrementing its position. * */ const PB_DS_CLASS_C_DEC* m_p_tbl; PB_DS_GEN_POS m_pos; friend class PB_DS_CLASS_C_DEC; }; ‹ .X ..Œinsert_fn_imps.hppinfo_fn_imps.hppŽtrace_fn_imps.hpp$policy_access_fn_imps.hppnode.hpp‘,#constructors_destructor_fn_imps.hpp’debug_fn_imps.hpp“erase_fn_imps.hpp”,!left_child_next_sibling_heap_.hpp• iterators_fn_imps.hpp– const_point_iterator.hpp—const_iterator.hpp˜xnull_metadata.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 insert_fn_imps.hpp * Contains an implementation class for left_child_next_sibling_heap_. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: get_new_node_for_insert(const_reference r_val) { return get_new_node_for_insert(r_val, s_no_throw_copies_ind); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: get_new_node_for_insert(const_reference r_val, false_type) { node_pointer p_new_nd = s_node_allocator.allocate(1); cond_dealtor_t cond(p_new_nd); new (const_cast( static_cast(&p_new_nd->m_value))) typename node::value_type(r_val); cond.set_no_action(); ++m_size; return (p_new_nd); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: get_new_node_for_insert(const_reference r_val, true_type) { node_pointer p_new_nd = s_node_allocator.allocate(1); new (const_cast( static_cast(&p_new_nd->m_value))) typename node::value_type(r_val); ++m_size; return (p_new_nd); } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: make_child_of(node_pointer p_nd, node_pointer p_new_parent) { _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); _GLIBCXX_DEBUG_ASSERT(p_new_parent != NULL); p_nd->m_p_next_sibling = p_new_parent->m_p_l_child; if (p_new_parent->m_p_l_child != NULL) p_new_parent->m_p_l_child->m_p_prev_or_parent = p_nd; p_nd->m_p_prev_or_parent = p_new_parent; p_new_parent->m_p_l_child = p_nd; } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: parent(node_pointer p_nd) { while (true) { node_pointer p_pot = p_nd->m_p_prev_or_parent; if (p_pot == NULL || p_pot->m_p_l_child == p_nd) return p_pot; p_nd = p_pot; } } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: swap_with_parent(node_pointer p_nd, node_pointer p_parent) { if (p_parent == m_p_root) m_p_root = p_nd; _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); _GLIBCXX_DEBUG_ASSERT(p_parent != NULL); _GLIBCXX_DEBUG_ASSERT(parent(p_nd) == p_parent); const bool nd_direct_child = p_parent->m_p_l_child == p_nd; const bool parent_root = p_parent->m_p_prev_or_parent == NULL; const bool parent_direct_child = !parent_root&& p_parent->m_p_prev_or_parent->m_p_l_child == p_parent; std::swap(p_parent->m_p_prev_or_parent, p_nd->m_p_prev_or_parent); std::swap(p_parent->m_p_next_sibling, p_nd->m_p_next_sibling); std::swap(p_parent->m_p_l_child, p_nd->m_p_l_child); std::swap(p_parent->m_metadata, p_nd->m_metadata); _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_l_child != NULL); _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_prev_or_parent != NULL); if (p_nd->m_p_next_sibling != NULL) p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd; if (p_parent->m_p_next_sibling != NULL) p_parent->m_p_next_sibling->m_p_prev_or_parent = p_parent; if (p_parent->m_p_l_child != NULL) p_parent->m_p_l_child->m_p_prev_or_parent = p_parent; if (parent_direct_child) p_nd->m_p_prev_or_parent->m_p_l_child = p_nd; else if (!parent_root) p_nd->m_p_prev_or_parent->m_p_next_sibling = p_nd; if (!nd_direct_child) { p_nd->m_p_l_child->m_p_prev_or_parent = p_nd; p_parent->m_p_prev_or_parent->m_p_next_sibling = p_parent; } else { _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_l_child == p_nd); _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_prev_or_parent == p_parent); p_nd->m_p_l_child = p_parent; p_parent->m_p_prev_or_parent = p_nd; } _GLIBCXX_DEBUG_ASSERT(parent(p_parent) == 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 info_fn_imps.hpp * Contains an implementation class for left_child_next_sibling_heap_. */ PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: empty() const { return (m_size == 0); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: size() const { return (m_size); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: max_size() const { return (s_node_allocator.max_size()); } // -*- 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 trace_fn_imps.hpp * Contains an implementation class for left_child_next_sibling_heap_. */ #ifdef PB_DS_LC_NS_HEAP_TRACE_ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: trace() const { std::cerr << std::endl; trace_node(m_p_root, 0); std::cerr << std::endl; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: trace_node(const_node_pointer p_nd, size_type level) { while (p_nd != NULL) { for (size_type i = 0; i < level; ++i) std::cerr << ' '; std::cerr << p_nd << " prev = " << p_nd->m_p_prev_or_parent << " next " << p_nd->m_p_next_sibling << " left = " << p_nd->m_p_l_child << " "; trace_node_metadata(p_nd, type_to_type()); std::cerr << p_nd->m_value << std::endl; trace_node(p_nd->m_p_l_child, level + 1); p_nd = p_nd->m_p_next_sibling; } } PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: trace_node_metadata(const_node_pointer p_nd, type_to_type) { std::cerr << "(" << p_nd->m_metadata << ") "; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: trace_node_metadata(const_node_pointer, type_to_type) { } #endif // #ifdef PB_DS_LC_NS_HEAP_TRACE_ // -*- 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 policy_access_fn_imps.hpp * Contains an implementation class for left_child_next_sibling_heap_. */ PB_DS_CLASS_T_DEC Cmp_Fn& PB_DS_CLASS_C_DEC:: get_cmp_fn() { return (*this); } PB_DS_CLASS_T_DEC const Cmp_Fn& PB_DS_CLASS_C_DEC:: get_cmp_fn() const { return (*this); } // -*- 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 node.hpp * Contains an implementation struct for this type of heap's node. */ #ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NODE_HPP #define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NODE_HPP #include namespace __gnu_pbds { namespace detail { template struct left_child_next_sibling_heap_node_ { private: typedef left_child_next_sibling_heap_node_< Value_Type, Metadata_Type, Allocator> this_type; public: typedef typename Allocator::size_type size_type; typedef typename Allocator::template rebind< this_type>::other::pointer node_pointer; typedef Value_Type value_type; typedef Metadata_Type metadata_type; public: value_type m_value; metadata_type m_metadata; node_pointer m_p_l_child; node_pointer m_p_next_sibling; node_pointer m_p_prev_or_parent; }; template struct left_child_next_sibling_heap_node_< Value_Type, null_left_child_next_sibling_heap_node_metadata, Allocator> { private: typedef left_child_next_sibling_heap_node_< Value_Type, null_left_child_next_sibling_heap_node_metadata, Allocator> this_type; public: typedef typename Allocator::size_type size_type; typedef typename Allocator::template rebind< this_type>::other::pointer node_pointer; typedef Value_Type value_type; public: value_type m_value; node_pointer m_p_l_child; node_pointer m_p_next_sibling; node_pointer m_p_prev_or_parent; }; } // namespace detail } // namespace __gnu_pbds #endif // #ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NODE_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 class for left_child_next_sibling_heap_. */ PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_allocator PB_DS_CLASS_C_DEC::s_node_allocator; PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::no_throw_copies_t PB_DS_CLASS_C_DEC::s_no_throw_copies_ind; PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: left_child_next_sibling_heap_() : m_p_root(NULL), m_size(0) { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: left_child_next_sibling_heap_(const Cmp_Fn& r_cmp_fn) : Cmp_Fn(r_cmp_fn), m_p_root(NULL), m_size(0) { _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: left_child_next_sibling_heap_(const PB_DS_CLASS_C_DEC& other) : Cmp_Fn(other), m_p_root(NULL), m_size(0) { m_size = other.m_size; _GLIBCXX_DEBUG_ONLY(other.assert_valid();) m_p_root = recursive_copy_node(other.m_p_root); m_size = other.m_size; _GLIBCXX_DEBUG_ONLY(assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) value_swap(other); std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )other); _GLIBCXX_DEBUG_ONLY(assert_valid();) _GLIBCXX_DEBUG_ONLY(other.assert_valid();) } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: value_swap(PB_DS_CLASS_C_DEC& other) { std::swap(m_p_root, other.m_p_root); std::swap(m_size, other.m_size); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~left_child_next_sibling_heap_() { clear(); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: recursive_copy_node(const_node_pointer p_nd) { if (p_nd == NULL) return (NULL); node_pointer p_ret = s_node_allocator.allocate(1); try { new (p_ret) node(*p_nd); } catch(...) { s_node_allocator.deallocate(p_ret, 1); __throw_exception_again; } p_ret->m_p_l_child = p_ret->m_p_next_sibling = p_ret->m_p_prev_or_parent = NULL; try { p_ret->m_p_l_child = recursive_copy_node(p_nd->m_p_l_child); p_ret->m_p_next_sibling = recursive_copy_node(p_nd->m_p_next_sibling); } catch(...) { clear_imp(p_ret); __throw_exception_again; } if (p_ret->m_p_l_child != NULL) p_ret->m_p_l_child->m_p_prev_or_parent = p_ret; if (p_ret->m_p_next_sibling != NULL) p_ret->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_next_sibling->m_p_prev_or_parent == p_nd ? p_ret : NULL; return p_ret; } // -*- 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 left_child_next_sibling_heap_. */ #ifdef _GLIBCXX_DEBUG PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_valid() const { _GLIBCXX_DEBUG_ASSERT(m_p_root == NULL || m_p_root->m_p_prev_or_parent == NULL); if (m_p_root != NULL) assert_node_consistent(m_p_root, Single_Link_Roots); assert_size(); assert_iterators(); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_node_consistent(const_node_pointer p_nd, bool single_link) const { if (p_nd == NULL) return; assert_node_consistent(p_nd->m_p_l_child, false); assert_node_consistent(p_nd->m_p_next_sibling, single_link); if (single_link) _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_prev_or_parent == NULL); else if (p_nd->m_p_next_sibling != NULL) _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_next_sibling->m_p_prev_or_parent == p_nd); if (p_nd->m_p_l_child == NULL) return; const_node_pointer p_child = p_nd->m_p_l_child; while (p_child != NULL) { const_node_pointer p_next_child = p_child->m_p_next_sibling; _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(p_nd->m_value, p_child->m_value)); p_child = p_next_child; } _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_l_child->m_p_prev_or_parent == p_nd); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_iterators() const { const size_type calc_size = std::distance(begin(), end()); if (calc_size == size()) return; _GLIBCXX_DEBUG_ASSERT(0); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: assert_size() const { if (size_from_node(m_p_root) == m_size) return; _GLIBCXX_DEBUG_ASSERT(0); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: size_under_node(const_node_pointer p_nd) { return 1 + size_from_node(p_nd->m_p_l_child); } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: size_from_node(const_node_pointer p_nd) { size_type ret = 0; while (p_nd != NULL) { ret += 1 + size_from_node(p_nd->m_p_l_child); p_nd = p_nd->m_p_next_sibling; } return ret; } PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: degree(const_node_pointer p_nd) { size_type ret = 0; const_node_pointer p_child = p_nd->m_p_l_child; while (p_child != NULL) { ++ret; p_child = p_child->m_p_next_sibling; } return ret; } #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 left_child_next_sibling_heap_. */ PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear() { clear_imp(m_p_root); _GLIBCXX_DEBUG_ASSERT(m_size == 0); m_p_root = NULL; } PB_DS_CLASS_T_DEC inline void PB_DS_CLASS_C_DEC:: actual_erase_node(node_pointer p_nd) { _GLIBCXX_DEBUG_ASSERT(m_size > 0); --m_size; p_nd->~node(); s_node_allocator.deallocate(p_nd, 1); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: clear_imp(node_pointer p_nd) { while (p_nd != NULL) { clear_imp(p_nd->m_p_l_child); node_pointer p_next = p_nd->m_p_next_sibling; actual_erase_node(p_nd); p_nd = p_next; } } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: to_linked_list() { _GLIBCXX_DEBUG_ONLY(assert_valid();) node_pointer p_cur = m_p_root; while (p_cur != NULL) if (p_cur->m_p_l_child != NULL) { node_pointer p_child_next = p_cur->m_p_l_child->m_p_next_sibling; p_cur->m_p_l_child->m_p_next_sibling = p_cur->m_p_next_sibling; p_cur->m_p_next_sibling = p_cur->m_p_l_child; p_cur->m_p_l_child = p_child_next; } else p_cur = p_cur->m_p_next_sibling; #ifdef _GLIBCXX_DEBUG const_node_pointer p_counter = m_p_root; size_type count = 0; while (p_counter != NULL) { ++count; _GLIBCXX_DEBUG_ASSERT(p_counter->m_p_l_child == NULL); p_counter = p_counter->m_p_next_sibling; } _GLIBCXX_DEBUG_ASSERT(count == m_size); #endif } PB_DS_CLASS_T_DEC template typename PB_DS_CLASS_C_DEC::node_pointer PB_DS_CLASS_C_DEC:: prune(Pred pred) { node_pointer p_cur = m_p_root; m_p_root = NULL; node_pointer p_out = NULL; while (p_cur != NULL) { node_pointer p_next = p_cur->m_p_next_sibling; if (pred(p_cur->m_value)) { p_cur->m_p_next_sibling = p_out; if (p_out != NULL) p_out->m_p_prev_or_parent = p_cur; p_out = p_cur; } else { p_cur->m_p_next_sibling = m_p_root; if (m_p_root != NULL) m_p_root->m_p_prev_or_parent = p_cur; m_p_root = p_cur; } p_cur = p_next; } return p_out; } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: bubble_to_top(node_pointer p_nd) { node_pointer p_parent = parent(p_nd); while (p_parent != NULL) { swap_with_parent(p_nd, p_parent); p_parent = parent(p_nd); } }