[thirdparty/gcc.git] / libstdc++-v3 / include / ext / pb_ds / detail / pairing_heap_ / pairing_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 pairing_heap_.hpp
 * Contains an implementation class for a pairing heap.
 */

/*
 * Pairing heap:
 * Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator,
 *    and Robert Endre Tarjan, The Pairing Heap:
 *    A New Form of Self-Adjusting Heap, Algorithmica, 1(1):111-129, 1986.
 */

#include <ext/pb_ds/detail/cond_dealtor.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/null_metadata.hpp>
#include <debug/debug.h>

namespace pb_ds
{
  namespace detail
  {

#define PB_DS_CLASS_T_DEC \
    template<typename Value_Type, class Cmp_Fn, class Allocator>

#define PB_DS_CLASS_C_DEC \
    pairing_heap_<Value_Type, Cmp_Fn, Allocator>

#ifdef _GLIBCXX_DEBUG
#define PB_DS_BASE_C_DEC \
    left_child_next_sibling_heap_<			\
									Value_Type, \
									Cmp_Fn,	\
									null_left_child_next_sibling_heap_node_metadata, \
									Allocator, \
									false>
#else 
#define PB_DS_BASE_C_DEC						\
    left_child_next_sibling_heap_<			\
									Value_Type, \
									Cmp_Fn,	\
									null_left_child_next_sibling_heap_node_metadata, \
									Allocator>
#endif 

    /**
     * class description = "P4ri|\|g h3ap$">
     **/
    template<typename Value_Type, class Cmp_Fn, class Allocator>
    class pairing_heap_ : public PB_DS_BASE_C_DEC
    {

    private:
      typedef PB_DS_BASE_C_DEC base_type;

      typedef typename base_type::node_pointer node_pointer;

    public:

      typedef 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;


      pairing_heap_();

      pairing_heap_(const Cmp_Fn& r_cmp_fn);

      pairing_heap_(const PB_DS_CLASS_C_DEC& other);

      void
      swap(PB_DS_CLASS_C_DEC& other);

      ~pairing_heap_();

      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);

      template<typename Pred>
      size_type
      erase_if(Pred pred);

      template<typename Pred>
      void
      split(Pred pred, PB_DS_CLASS_C_DEC& other);

      void
      join(PB_DS_CLASS_C_DEC& other);

    protected:

      template<typename It>
      void
      copy_from_range(It first_it, It last_it);

#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;
#endif

    private:

      inline void
      push_imp(node_pointer p_nd);

      node_pointer
      join_node_children(node_pointer p_nd);

      node_pointer
      forward_join(node_pointer p_nd, node_pointer p_next);

      node_pointer
      back_join(node_pointer p_nd, node_pointer p_next);

      void
      remove_node(node_pointer p_nd);

    };

#include <ext/pb_ds/detail/pairing_heap_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/pairing_heap_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/pairing_heap_/find_fn_imps.hpp>
#include <ext/pb_ds/detail/pairing_heap_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/pairing_heap_/split_join_fn_imps.hpp>

#undef PB_DS_CLASS_C_DEC
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_BASE_C_DEC

  } // namespace detail
} // namespace pb_ds
Commit	Line	Data
4569a895 AT	1	// -- C++ --
	2
	3	// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
	4	//
	5	// This file is part of the GNU ISO C++ Library. This library is free
	6	// software; you can redistribute it and/or modify it under the terms
	7	// of the GNU General Public License as published by the Free Software
	8	// Foundation; either version 2, or (at your option) any later
	9	// version.
	10
	11	// This library is distributed in the hope that it will be useful, but
	12	// WITHOUT ANY WARRANTY; without even the implied warranty of
	13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
	14	// General Public License for more details.
	15
	16	// You should have received a copy of the GNU General Public License
	17	// along with this library; see the file COPYING. If not, write to
	18	// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
	19	// MA 02111-1307, USA.
	20
	21	// As a special exception, you may use this file as part of a free
	22	// software library without restriction. Specifically, if other files
	23	// instantiate templates or use macros or inline functions from this
	24	// file, or you compile this file and link it with other files to
	25	// produce an executable, this file does not by itself cause the
	26	// resulting executable to be covered by the GNU General Public
	27	// License. This exception does not however invalidate any other
	28	// reasons why the executable file might be covered by the GNU General
	29	// Public License.
	30
	31	// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
	32
	33	// Permission to use, copy, modify, sell, and distribute this software
	34	// is hereby granted without fee, provided that the above copyright
	35	// notice appears in all copies, and that both that copyright notice
	36	// and this permission notice appear in supporting documentation. None
	37	// of the above authors, nor IBM Haifa Research Laboratories, make any
	38	// representation about the suitability of this software for any
	39	// purpose. It is provided "as is" without express or implied
	40	// warranty.
	41
	42	/**
	43	* @file pairing_heap_.hpp
	44	* Contains an implementation class for a pairing heap.
	45	*/
	46
	47	/*
	48	* Pairing heap:
	49	* Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator,
	50	* and Robert Endre Tarjan, The Pairing Heap:
	51	* A New Form of Self-Adjusting Heap, Algorithmica, 1(1):111-129, 1986.
	52	*/
	53
	54	#include <ext/pb_ds/detail/cond_dealtor.hpp>
	55	#include <ext/pb_ds/detail/type_utils.hpp>
	56	#include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp>
	57	#include <ext/pb_ds/detail/left_child_next_sibling_heap_/null_metadata.hpp>
47bea7b8	58	#include <debug/debug.h>
4569a895 AT	59
	60	namespace pb_ds
	61	{
	62	namespace detail
	63	{
	64
47bea7b8	65	#define PB_DS_CLASS_T_DEC \
4569a895 AT	66	template<typename Value_Type, class Cmp_Fn, class Allocator>
4569a895 AT	67
47bea7b8 BK	68	#define PB_DS_CLASS_C_DEC \
47bea7b8 BK	69	pairing_heap_<Value_Type, Cmp_Fn, Allocator>
4569a895	70
47bea7b8 BK	71	#ifdef _GLIBCXX_DEBUG
47bea7b8 BK	72	#define PB_DS_BASE_C_DEC \
4569a895 AT	73	left_child_next_sibling_heap_< \
	74	Value_Type, \
	75	Cmp_Fn, \
	76	null_left_child_next_sibling_heap_node_metadata, \
	77	Allocator, \
	78	false>
47bea7b8	79	#else
4569a895 AT	80	#define PB_DS_BASE_C_DEC \
	81	left_child_next_sibling_heap_< \
	82	Value_Type, \
	83	Cmp_Fn, \
	84	null_left_child_next_sibling_heap_node_metadata, \
	85	Allocator>
47bea7b8	86	#endif
4569a895 AT	87
	88	/**
	89	* class description = "P4ri\|\\|g h3ap$">
	90	**/
	91	template<typename Value_Type, class Cmp_Fn, class Allocator>
	92	class pairing_heap_ : public PB_DS_BASE_C_DEC
	93	{
	94
	95	private:
	96	typedef PB_DS_BASE_C_DEC base_type;
	97
	98	typedef typename base_type::node_pointer node_pointer;
	99
	100	public:
	101
	102	typedef typename Allocator::size_type size_type;
	103
	104	typedef typename Allocator::difference_type difference_type;
	105
	106	typedef Value_Type value_type;
	107
	108	typedef
	109	typename Allocator::template rebind<
	110	value_type>::other::pointer
	111	pointer;
	112
	113	typedef
	114	typename Allocator::template rebind<
	115	value_type>::other::const_pointer
	116	const_pointer;
	117
	118	typedef
	119	typename Allocator::template rebind<
	120	value_type>::other::reference
	121	reference;
	122
	123	typedef
	124	typename Allocator::template rebind<
	125	value_type>::other::const_reference
	126	const_reference;
	127
	128	typedef
	129	typename PB_DS_BASE_C_DEC::const_point_iterator
	130	const_point_iterator;
	131
	132	typedef typename PB_DS_BASE_C_DEC::point_iterator point_iterator;
	133
	134	typedef typename PB_DS_BASE_C_DEC::const_iterator const_iterator;
	135
	136	typedef typename PB_DS_BASE_C_DEC::iterator iterator;
	137
	138	typedef Cmp_Fn cmp_fn;
	139
	140	typedef Allocator allocator;
	141
	142
	143	pairing_heap_();
	144
	145	pairing_heap_(const Cmp_Fn& r_cmp_fn);
	146
	147	pairing_heap_(const PB_DS_CLASS_C_DEC& other);
	148
	149	void
	150	swap(PB_DS_CLASS_C_DEC& other);
151
152	~pairing_heap_();
153
154	inline point_iterator
155	push(const_reference r_val);
156
157	void
158	modify(point_iterator it, const_reference r_new_val);
159
160	inline const_reference
161	top() const;
162
163	void
164	pop();
165
166	void
167	erase(point_iterator it);
168
169	template<typename Pred>
170	size_type
171	erase_if(Pred pred);
172
173	template<typename Pred>
174	void
175	split(Pred pred, PB_DS_CLASS_C_DEC& other);
176
177	void
178	join(PB_DS_CLASS_C_DEC& other);
179
180	protected:
181
182	template<typename It>
183	void
184	copy_from_range(It first_it, It last_it);
185
47bea7b8	186	#ifdef _GLIBCXX_DEBUG
4569a895 AT	187	void
	188	assert_valid() const;
	189	#endif
	190
	191	private:
	192
	193	inline void
	194	push_imp(node_pointer p_nd);
	195
	196	node_pointer
	197	join_node_children(node_pointer p_nd);
	198
	199	node_pointer
	200	forward_join(node_pointer p_nd, node_pointer p_next);
	201
	202	node_pointer
	203	back_join(node_pointer p_nd, node_pointer p_next);
	204
	205	void
	206	remove_node(node_pointer p_nd);
	207
	208	};
	209
	210	#include <ext/pb_ds/detail/pairing_heap_/constructors_destructor_fn_imps.hpp>
	211	#include <ext/pb_ds/detail/pairing_heap_/debug_fn_imps.hpp>
	212	#include <ext/pb_ds/detail/pairing_heap_/find_fn_imps.hpp>
	213	#include <ext/pb_ds/detail/pairing_heap_/insert_fn_imps.hpp>
	214	#include <ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp>
	215	#include <ext/pb_ds/detail/pairing_heap_/split_join_fn_imps.hpp>
	216
	217	#undef PB_DS_CLASS_C_DEC
	218	#undef PB_DS_CLASS_T_DEC
	219	#undef PB_DS_BASE_C_DEC
4569a895 AT	220
	221	} // namespace detail
	222	} // namespace pb_ds