17b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// -*- C++ -*- 27b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 37b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// Copyright (C) 2005-2014 Free Software Foundation, Inc. 47b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// 57b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// This file is part of the GNU ISO C++ Library. This library is free 67b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// software; you can redistribute it and/or modify it under the terms 77b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// of the GNU General Public License as published by the Free Software 87b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// Foundation; either version 3, or (at your option) any later 97b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// version. 107b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 117b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// This library is distributed in the hope that it will be useful, but 127b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// WITHOUT ANY WARRANTY; without even the implied warranty of 137b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 147b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// General Public License for more details. 157b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 167b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// Under Section 7 of GPL version 3, you are granted additional 177b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// permissions described in the GCC Runtime Library Exception, version 187b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// 3.1, as published by the Free Software Foundation. 197b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 207b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// You should have received a copy of the GNU General Public License and 217b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// a copy of the GCC Runtime Library Exception along with this program; 227b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 237b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// <http://www.gnu.org/licenses/>. 247b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 257b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 267b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 277b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// Permission to use, copy, modify, sell, and distribute this software 287b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// is hereby granted without fee, provided that the above copyright 297b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// notice appears in all copies, and that both that copyright notice 307b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// and this permission notice appear in supporting documentation. None 317b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// of the above authors, nor IBM Haifa Research Laboratories, make any 327b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// representation about the suitability of this software for any 337b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// purpose. It is provided "as is" without express or implied 347b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh// warranty. 357b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 367b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh/** 377b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * @file pairing_heap_/pairing_heap_.hpp 387b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * Contains an implementation class for a pairing heap. 397b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh */ 407b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 417b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh/* 427b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * Pairing heap: 437b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * Michael L. Fredman, Robert Sedgewick, Daniel Dominic Sleator, 447b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * and Robert Endre Tarjan, The Pairing Heap: 457b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * A New Form of Self-Adjusting Heap, Algorithmica, 1(1):111-129, 1986. 467b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh */ 477b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 487b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#include <ext/pb_ds/detail/cond_dealtor.hpp> 497b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#include <ext/pb_ds/detail/type_utils.hpp> 507b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#include <ext/pb_ds/detail/left_child_next_sibling_heap_/left_child_next_sibling_heap_.hpp> 517b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#include <debug/debug.h> 527b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 537b9b0e19b31944fce201a273083eaca38e477580Andrew Hsiehnamespace __gnu_pbds 547b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh{ 557b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh namespace detail 567b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh { 577b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#define PB_DS_CLASS_T_DEC \ 587b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh template<typename Value_Type, typename Cmp_Fn, typename _Alloc> 597b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 607b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#define PB_DS_CLASS_C_DEC \ 617b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh pairing_heap<Value_Type, Cmp_Fn, _Alloc> 627b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 637b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#ifdef _GLIBCXX_DEBUG 647b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#define PB_DS_P_HEAP_BASE \ 657b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh left_child_next_sibling_heap<Value_Type, Cmp_Fn, null_type, _Alloc, false> 667b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#else 677b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#define PB_DS_P_HEAP_BASE \ 687b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh left_child_next_sibling_heap<Value_Type, Cmp_Fn, null_type, _Alloc> 697b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#endif 707b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 717b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh /** 727b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * Pairing heap. 737b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * 747b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh * @ingroup heap-detail 757b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh */ 767b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh template<typename Value_Type, typename Cmp_Fn, typename _Alloc> 777b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh class pairing_heap : public PB_DS_P_HEAP_BASE 787b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh { 797b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh private: 807b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef PB_DS_P_HEAP_BASE base_type; 817b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename base_type::node_pointer node_pointer; 827b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 837b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename _Alloc::template rebind<Value_Type>::other __rebind_a; 847b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 857b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh public: 867b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef Value_Type value_type; 877b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef Cmp_Fn cmp_fn; 887b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef _Alloc allocator_type; 897b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename _Alloc::size_type size_type; 907b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename _Alloc::difference_type difference_type; 917b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 927b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename __rebind_a::pointer pointer; 937b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename __rebind_a::const_pointer const_pointer; 947b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename __rebind_a::reference reference; 957b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename __rebind_a::const_reference const_reference; 967b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 977b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename base_type::point_const_iterator point_const_iterator; 987b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename base_type::point_iterator point_iterator; 997b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename base_type::const_iterator const_iterator; 1007b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh typedef typename base_type::iterator iterator; 1017b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1027b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh pairing_heap(); 1037b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1047b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh pairing_heap(const Cmp_Fn&); 1057b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1067b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh pairing_heap(const pairing_heap&); 1077b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1087b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh void 1097b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh swap(pairing_heap&); 1107b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1117b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh ~pairing_heap(); 1127b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1137b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh inline point_iterator 1147b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh push(const_reference); 1157b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1167b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh void 1177b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh modify(point_iterator, const_reference); 1187b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1197b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh inline const_reference 1207b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh top() const; 1217b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1227b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh void 1237b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh pop(); 1247b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1257b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh void 1267b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh erase(point_iterator); 1277b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1287b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh template<typename Pred> 1297b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh size_type 1307b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh erase_if(Pred); 1317b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1327b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh template<typename Pred> 1337b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh void 1347b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh split(Pred, pairing_heap&); 1357b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1367b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh void 1377b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh join(pairing_heap&); 1387b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1397b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh protected: 1407b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1417b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh template<typename It> 1427b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh void 1437b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh copy_from_range(It, It); 1447b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1457b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#ifdef _GLIBCXX_DEBUG 1467b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh void 1477b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh assert_valid(const char*, int) const; 1487b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#endif 1497b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1507b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh private: 1517b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1527b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh inline void 1537b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh push_imp(node_pointer); 1547b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1557b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh node_pointer 1567b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh join_node_children(node_pointer); 1577b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1587b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh node_pointer 1597b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh forward_join(node_pointer, node_pointer); 1607b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1617b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh node_pointer 1627b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh back_join(node_pointer, node_pointer); 1637b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1647b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh void 1657b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh remove_node(node_pointer); 1667b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh }; 1677b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1687b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#define PB_DS_ASSERT_NODE_CONSISTENT(_Node, _Bool) \ 1697b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(_Node, _Bool, \ 1707b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh __FILE__, __LINE__);) 1717b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1727b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#include <ext/pb_ds/detail/pairing_heap_/constructors_destructor_fn_imps.hpp> 1737b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#include <ext/pb_ds/detail/pairing_heap_/debug_fn_imps.hpp> 1747b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#include <ext/pb_ds/detail/pairing_heap_/find_fn_imps.hpp> 1757b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#include <ext/pb_ds/detail/pairing_heap_/insert_fn_imps.hpp> 1767b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#include <ext/pb_ds/detail/pairing_heap_/erase_fn_imps.hpp> 1777b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#include <ext/pb_ds/detail/pairing_heap_/split_join_fn_imps.hpp> 1787b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1797b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#undef PB_DS_ASSERT_NODE_CONSISTENT 1807b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#undef PB_DS_CLASS_C_DEC 1817b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#undef PB_DS_CLASS_T_DEC 1827b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh#undef PB_DS_P_HEAP_BASE 1837b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh 1847b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh } // namespace detail 1857b9b0e19b31944fce201a273083eaca38e477580Andrew Hsieh} // namespace __gnu_pbds 186