X-Git-Url: http://wagnertech.de/git?a=blobdiff_plain;ds=sidebyside;f=i686-linux-gnu-4.7%2Fusr%2Finclude%2Fc%2B%2B%2F4.7%2Fext%2Fpb_ds%2Fdetail%2Fbinary_heap_%2Fbinary_heap_.hpp;fp=i686-linux-gnu-4.7%2Fusr%2Finclude%2Fc%2B%2B%2F4.7%2Fext%2Fpb_ds%2Fdetail%2Fbinary_heap_%2Fbinary_heap_.hpp;h=8d91c4ca0b62ddecc860e3ba4e76a3a19f163c04;hb=94df942c2c7bd3457276fe5b7367623cbb8c1302;hp=0000000000000000000000000000000000000000;hpb=4dd7d9155a920895ff7b1cb6b9c9c676aa62000a;p=cross.git
diff --git a/i686-linux-gnu-4.7/usr/include/c++/4.7/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp b/i686-linux-gnu-4.7/usr/include/c++/4.7/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
new file mode 100644
index 0000000..8d91c4c
--- /dev/null
+++ b/i686-linux-gnu-4.7/usr/include/c++/4.7/ext/pb_ds/detail/binary_heap_/binary_heap_.hpp
@@ -0,0 +1,352 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009, 2011 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 3, 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.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
+// .
+
+// 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 binary_heap_/binary_heap_.hpp
+ * Contains an implementation class for a binary heap.
+ */
+
+#ifndef PB_DS_BINARY_HEAP_HPP
+#define PB_DS_BINARY_HEAP_HPP
+
+#include
+#include
+#include
+#include
+#include
+#include
+#include
+#include
+#include
+#include
+#ifdef PB_DS_BINARY_HEAP_TRACE_
+#include
+#endif
+#include
+#include
+
+namespace __gnu_pbds
+{
+ namespace detail
+ {
+#define PB_DS_CLASS_T_DEC \
+ template
+
+#define PB_DS_CLASS_C_DEC \
+ binary_heap
+
+#define PB_DS_ENTRY_CMP_DEC \
+ entry_cmp::value>::type
+
+#define PB_DS_RESIZE_POLICY_DEC \
+ __gnu_pbds::detail::resize_policy
+
+ /**
+ * Binary heaps composed of resize and compare policies.
+ *
+ * @ingroup heap-detail
+ *
+ * Based on CLRS.
+ */
+ template
+ class binary_heap
+ : public PB_DS_ENTRY_CMP_DEC, public PB_DS_RESIZE_POLICY_DEC
+ {
+ public:
+ typedef Value_Type value_type;
+ typedef Cmp_Fn cmp_fn;
+ typedef _Alloc allocator_type;
+ typedef typename _Alloc::size_type size_type;
+ typedef typename _Alloc::difference_type difference_type;
+ typedef typename PB_DS_ENTRY_CMP_DEC entry_cmp;
+ typedef PB_DS_RESIZE_POLICY_DEC resize_policy;
+ typedef cond_dealtor cond_dealtor_t;
+
+ private:
+ enum
+ {
+ simple_value = is_simple::value
+ };
+
+ typedef integral_constant no_throw_copies_t;
+
+ typedef typename _Alloc::template rebind __rebind_v;
+ typedef typename __rebind_v::other value_allocator;
+
+ public:
+ typedef typename value_allocator::pointer pointer;
+ typedef typename value_allocator::const_pointer const_pointer;
+ typedef typename value_allocator::reference reference;
+ typedef typename value_allocator::const_reference const_reference;
+
+ typedef typename __conditional_type::__type
+ entry;
+
+ typedef typename _Alloc::template rebind::other
+ entry_allocator;
+
+ typedef typename entry_allocator::pointer entry_pointer;
+
+ typedef binary_heap_point_const_iterator_
+ point_const_iterator;
+
+ typedef point_const_iterator point_iterator;
+
+ typedef binary_heap_const_iterator_
+ const_iterator;
+
+ typedef const_iterator iterator;
+
+
+ binary_heap();
+
+ binary_heap(const cmp_fn&);
+
+ binary_heap(const binary_heap&);
+
+ void
+ swap(binary_heap&);
+
+ ~binary_heap();
+
+ inline bool
+ empty() const;
+
+ inline size_type
+ size() const;
+
+ inline size_type
+ max_size() const;
+
+ Cmp_Fn&
+ get_cmp_fn();
+
+ const Cmp_Fn&
+ get_cmp_fn() const;
+
+ inline point_iterator
+ push(const_reference);
+
+ void
+ modify(point_iterator, const_reference);
+
+ inline const_reference
+ top() const;
+
+ inline void
+ pop();
+
+ inline void
+ erase(point_iterator);
+
+ template
+ size_type
+ erase_if(Pred);
+
+ inline void
+ erase_at(entry_pointer, size_type, false_type);
+
+ inline void
+ erase_at(entry_pointer, size_type, true_type);
+
+ inline iterator
+ begin();
+
+ inline const_iterator
+ begin() const;
+
+ inline iterator
+ end();
+
+ inline const_iterator
+ end() const;
+
+ void
+ clear();
+
+ template
+ void
+ split(Pred, binary_heap&);
+
+ void
+ join(binary_heap&);
+
+#ifdef PB_DS_BINARY_HEAP_TRACE_
+ void
+ trace() const;
+#endif
+
+ protected:
+ template
+ void
+ copy_from_range(It, It);
+
+ private:
+ void
+ value_swap(binary_heap&);
+
+ inline void
+ insert_value(const_reference, false_type);
+
+ inline void
+ insert_value(value_type, true_type);
+
+ inline void
+ resize_for_insert_if_needed();
+
+ inline void
+ swap_value_imp(entry_pointer, value_type, true_type);
+
+ inline void
+ swap_value_imp(entry_pointer, const_reference, false_type);
+
+ void
+ fix(entry_pointer);
+
+ inline const_reference
+ top_imp(true_type) const;
+
+ inline const_reference
+ top_imp(false_type) const;
+
+ inline static size_type
+ left_child(size_type);
+
+ inline static size_type
+ right_child(size_type);
+
+ inline static size_type
+ parent(size_type);
+
+ inline void
+ resize_for_erase_if_needed();
+
+ template
+ size_type
+ partition(Pred);
+
+ void
+ make_heap()
+ {
+ const entry_cmp& m_cmp = static_cast(*this);
+ entry_pointer end = m_a_entries + m_size;
+ std::make_heap(m_a_entries, end, m_cmp);
+ _GLIBCXX_DEBUG_ASSERT(is_heap());
+ }
+
+ void
+ push_heap()
+ {
+ if (!is_heap())
+ make_heap();
+ else
+ {
+ const entry_cmp& m_cmp = static_cast(*this);
+ entry_pointer end = m_a_entries + m_size;
+ std::push_heap(m_a_entries, end, m_cmp);
+ }
+ }
+
+ void
+ pop_heap()
+ {
+ const entry_cmp& m_cmp = static_cast(*this);
+ entry_pointer end = m_a_entries + m_size;
+ std::pop_heap(m_a_entries, end, m_cmp);
+ }
+
+ bool
+ is_heap()
+ {
+ const entry_cmp& m_cmp = static_cast(*this);
+ entry_pointer end = m_a_entries + m_size;
+ bool p = std::__is_heap(m_a_entries, end, m_cmp);
+ return p;
+ }
+
+#ifdef _GLIBCXX_DEBUG
+ void
+ assert_valid(const char*, int) const;
+#endif
+
+#ifdef PB_DS_BINARY_HEAP_TRACE_
+ void
+ trace_entry(const entry&, false_type) const;
+
+ void
+ trace_entry(const entry&, true_type) const;
+#endif
+
+ static entry_allocator s_entry_allocator;
+ static value_allocator s_value_allocator;
+ static no_throw_copies_t s_no_throw_copies_ind;
+
+ size_type m_size;
+ size_type m_actual_size;
+ entry_pointer m_a_entries;
+ };
+
+#define PB_DS_ASSERT_VALID(X) \
+ _GLIBCXX_DEBUG_ONLY(X.assert_valid(__FILE__, __LINE__);)
+
+#define PB_DS_DEBUG_VERIFY(_Cond) \
+ _GLIBCXX_DEBUG_VERIFY_AT(_Cond, \
+ _M_message(#_Cond" assertion from %1;:%2;") \
+ ._M_string(__FILE__)._M_integer(__LINE__) \
+ ,__file,__line)
+
+#include
+#include
+#include
+#include
+#include
+#include
+#include
+#include
+#include
+#include
+
+#undef PB_DS_CLASS_C_DEC
+#undef PB_DS_CLASS_T_DEC
+#undef PB_DS_ENTRY_CMP_DEC
+#undef PB_DS_RESIZE_POLICY_DEC
+
+ } // namespace detail
+} // namespace __gnu_pbds
+
+#endif