// -*- 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 left_child_next_sibling_heap_.hpp
 * Contains an implementation class for a basic heap.
 */

#ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_HPP
#define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_HPP

/*
 * Based on CLRS.
 */

#include <iterator>
#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_/node.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/const_point_iterator.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/const_iterator.hpp>
#ifdef PB_DS_LC_NS_HEAP_TRACE_
#include <iostream>
#endif 
#include <debug/debug.h>

namespace __gnu_pbds
{
  namespace detail
  {

#ifdef _GLIBCXX_DEBUG
#define PB_DS_CLASS_T_DEC						\
    template<								\
						typename Value_Type,	\
						class Cmp_Fn,		\
						typename Node_Metadata,	\
						class Allocator,	\
						bool Single_Link_Roots>
#else 
#define PB_DS_CLASS_T_DEC						\
    template<								\
						typename Value_Type,	\
						class Cmp_Fn,		\
						typename Node_Metadata,	\
						class Allocator>
#endif 

#ifdef _GLIBCXX_DEBUG
#define PB_DS_CLASS_C_DEC						\
    left_child_next_sibling_heap_<					\
							Value_Type,	\
							Cmp_Fn,		\
							Node_Metadata,	\
							Allocator,	\
							Single_Link_Roots>
#else 
#define PB_DS_CLASS_C_DEC						\
    left_child_next_sibling_heap_<					\
							Value_Type,	\
							Cmp_Fn,		\
							Node_Metadata,	\
							Allocator>
#endif 

    /**
     * class description = "Base class for some types of h3ap$">
     **/
#ifdef _GLIBCXX_DEBUG
    template<typename Value_Type,
	     class Cmp_Fn,
	     typename Node_Metadata,
	     class Allocator,
	     bool Single_Link_Roots>
#else 
    template<typename Value_Type,
	     class Cmp_Fn,
	     typename Node_Metadata,
	     class Allocator>
#endif 
    class left_child_next_sibling_heap_ : public Cmp_Fn
    {

    protected:
      typedef
      typename Allocator::template rebind<
      left_child_next_sibling_heap_node_<
      Value_Type,
      Node_Metadata,
      Allocator> >::other
      node_allocator;

      typedef typename node_allocator::value_type node;

      typedef typename node_allocator::pointer node_pointer;

      typedef typename node_allocator::const_pointer const_node_pointer;

      typedef Node_Metadata node_metadata;

      typedef std::pair< node_pointer, node_pointer> node_pointer_pair;

    private:
      typedef cond_dealtor< node, Allocator> cond_dealtor_t;

      enum
	{
	  simple_value = is_simple<Value_Type>::value
	};

      typedef integral_constant<int, simple_value> no_throw_copies_t;

    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
      left_child_next_sibling_heap_node_const_point_iterator_<
	node,
	Allocator>
      const_point_iterator;

      typedef const_point_iterator point_iterator;

      typedef
      left_child_next_sibling_heap_const_iterator_<
	node,
	Allocator>
      const_iterator;

      typedef const_iterator iterator;

      typedef Cmp_Fn cmp_fn;

      typedef Allocator allocator;

    public:

      left_child_next_sibling_heap_();

      left_child_next_sibling_heap_(const Cmp_Fn& r_cmp_fn);

      left_child_next_sibling_heap_(const PB_DS_CLASS_C_DEC& other);

      void
      swap(PB_DS_CLASS_C_DEC& other);

      ~left_child_next_sibling_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 iterator
      begin();

      inline const_iterator
      begin() const;

      inline iterator
      end();

      inline const_iterator
      end() const;

      void
      clear();

#ifdef PB_DS_LC_NS_HEAP_TRACE_
      void
      trace() const;
#endif 

    protected:

      inline node_pointer
      get_new_node_for_insert(const_reference r_val);

      inline static void
      make_child_of(node_pointer p_nd, node_pointer p_new_parent);

      void
      value_swap(PB_DS_CLASS_C_DEC& other);

      inline static node_pointer
      parent(node_pointer p_nd);

      inline void
      swap_with_parent(node_pointer p_nd, node_pointer p_parent);

      void
      bubble_to_top(node_pointer p_nd);

      inline void
      actual_erase_node(node_pointer p_nd);

      void
      clear_imp(node_pointer p_nd);

      void
      to_linked_list();

      template<typename Pred>
      node_pointer
      prune(Pred pred);

#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;

      void
      assert_node_consistent(const_node_pointer p_nd, bool single_link) const;

      static size_type
      size_under_node(const_node_pointer p_nd);

      static size_type
      degree(const_node_pointer p_nd);
#endif 

#ifdef PB_DS_LC_NS_HEAP_TRACE_
      static void
      trace_node(const_node_pointer, size_type level);
#endif 

    protected:
      node_pointer m_p_root;

      size_type m_size;

    private:
#ifdef _GLIBCXX_DEBUG
      void
      assert_iterators() const;

      void
      assert_size() const;

      static size_type
      size_from_node(const_node_pointer p_nd);
#endif 

      node_pointer
      recursive_copy_node(const_node_pointer p_nd);

      inline node_pointer
      get_new_node_for_insert(const_reference r_val, false_type);

      inline node_pointer
      get_new_node_for_insert(const_reference r_val, true_type);

#ifdef PB_DS_LC_NS_HEAP_TRACE_
      template<typename Metadata_>
      static void
      trace_node_metadata(const_node_pointer p_nd, type_to_type<Metadata_>);

      static void
      trace_node_metadata(const_node_pointer, type_to_type<null_left_child_next_sibling_heap_node_metadata>);
#endif 

    private:
      static node_allocator s_node_allocator;

      static no_throw_copies_t s_no_throw_copies_ind;
    };

#include <ext/pb_ds/detail/left_child_next_sibling_heap_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/iterators_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/trace_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/info_fn_imps.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/policy_access_fn_imps.hpp>

#undef PB_DS_CLASS_C_DEC
#undef PB_DS_CLASS_T_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 iterators_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::iterator
PB_DS_CLASS_C_DEC::
begin()
{
  node_pointer p_nd = m_p_root;

  if (p_nd == NULL)
    return (iterator(NULL));

  while (p_nd->m_p_l_child != NULL)
    p_nd = p_nd->m_p_l_child;

  return (iterator(p_nd));
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_iterator
PB_DS_CLASS_C_DEC::
begin() const
{
  node_pointer p_nd = m_p_root;

  if (p_nd == NULL)
    return (const_iterator(NULL));

  while (p_nd->m_p_l_child != NULL)
    p_nd = p_nd->m_p_l_child;

  return (const_iterator(p_nd));
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::
end()
{
  return (iterator(NULL));
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_iterator
PB_DS_CLASS_C_DEC::
end() const
{
  return (const_iterator(NULL));
}

// -*- 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 table's const find and insert
 *     methods.
 */

#ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_CONST_FIND_ITERATOR_HPP
#define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_CONST_FIND_ITERATOR_HPP

#include <ext/pb_ds/tag_and_trait.hpp>
#include <debug/debug.h>

namespace __gnu_pbds
{
  namespace detail
  {

#define PB_DS_CLASS_T_DEC			\
    template<typename Node, class Allocator>

#define PB_DS_CLASS_C_DEC \
    left_child_next_sibling_heap_node_const_point_iterator_<Node, Allocator>

    // Const point-type iterator.
    template<typename Node, class Allocator>
    class left_child_next_sibling_heap_node_const_point_iterator_
    {

    protected:
      typedef typename Allocator::template rebind<Node>::other::pointer node_pointer;

    public:

      // Category.
      typedef trivial_iterator_tag iterator_category;

      // Difference type.
      typedef trivial_iterator_difference_type difference_type;

      // Iterator's value type.
      typedef typename Node::value_type value_type;

      // Iterator's pointer type.
      typedef
      typename Allocator::template rebind<
	value_type>::other::pointer
      pointer;

      // Iterator's const pointer type.
      typedef
      typename Allocator::template rebind<
	value_type>::other::const_pointer
      const_pointer;

      // Iterator's reference type.
      typedef
      typename Allocator::template rebind<
	value_type>::other::reference
      reference;

      // Iterator's const reference type.
      typedef
      typename Allocator::template rebind<
	value_type>::other::const_reference
      const_reference;

    public:

      inline
      left_child_next_sibling_heap_node_const_point_iterator_(node_pointer p_nd) : m_p_nd(p_nd)
      { }

      // Default constructor.
      inline
      left_child_next_sibling_heap_node_const_point_iterator_() : m_p_nd(NULL)
      { }

      // Copy constructor.
      inline
      left_child_next_sibling_heap_node_const_point_iterator_(const PB_DS_CLASS_C_DEC& other) : m_p_nd(other.m_p_nd)
      { }

      // Access.
      inline const_pointer
      operator->() const
      {
	_GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL);
	return &m_p_nd->m_value;
      }

      // Access.
      inline const_reference
      operator*() const
      {
	_GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL);
	return m_p_nd->m_value;
      }

      // Compares content to a different iterator object.
      inline bool
      operator==(const PB_DS_CLASS_C_DEC& other) const
      { return m_p_nd == other.m_p_nd; }

      // Compares content (negatively) to a different iterator object.
      inline bool
      operator!=(const PB_DS_CLASS_C_DEC& other) const
      { return m_p_nd != other.m_p_nd; }

    public:
      node_pointer m_p_nd;
    };

#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 const_iterator.hpp
 * Contains an iterator class returned by the table's const find and insert
 *     methods.
 */

#ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_CONST_ITERATOR_HPP
#define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_CONST_ITERATOR_HPP

#include <ext/pb_ds/detail/left_child_next_sibling_heap_/const_point_iterator.hpp>
#include <debug/debug.h>

namespace __gnu_pbds
{
  namespace detail
  {

#define PB_DS_CLASS_C_DEC						\
    left_child_next_sibling_heap_const_iterator_<Node, Allocator>

#define PB_DS_BASE_C_DEC						\
    left_child_next_sibling_heap_node_const_point_iterator_<Node, Allocator>

    // Const point-type iterator.
    template<typename Node, class Allocator>
    class left_child_next_sibling_heap_const_iterator_ : public PB_DS_BASE_C_DEC
    {

    private:
      typedef typename PB_DS_BASE_C_DEC::node_pointer node_pointer;

      typedef PB_DS_BASE_C_DEC base_type;

    public:

      // Category.
      typedef std::forward_iterator_tag iterator_category;

      // Difference type.
      typedef typename Allocator::difference_type difference_type;

      // Iterator's value type.
      typedef typename base_type::value_type value_type;

      // Iterator's pointer type.
      typedef typename base_type::pointer pointer;

      // Iterator's const pointer type.
      typedef typename base_type::const_pointer const_pointer;

      // Iterator's reference type.
      typedef typename base_type::reference reference;

      // Iterator's const reference type.
      typedef typename base_type::const_reference const_reference;

    public:

      inline
      left_child_next_sibling_heap_const_iterator_(node_pointer p_nd) : base_type(p_nd)
      { }

      // Default constructor.
      inline
      left_child_next_sibling_heap_const_iterator_()
      { }

      // Copy constructor.
      inline
      left_child_next_sibling_heap_const_iterator_(const PB_DS_CLASS_C_DEC& other) : base_type(other)
      { }

      // Compares content to a different iterator object.
      inline bool
      operator==(const PB_DS_CLASS_C_DEC& other) const
      { return (base_type::m_p_nd == other.m_p_nd); }

      // Compares content (negatively) to a different iterator object.
      inline bool
      operator!=(const PB_DS_CLASS_C_DEC& other) const
      { return (base_type::m_p_nd != other.m_p_nd); }

      inline PB_DS_CLASS_C_DEC& 
      operator++()
      {
	_GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd != NULL);
	inc();
	return (*this);
      }

      inline PB_DS_CLASS_C_DEC
      operator++(int)
      {
	PB_DS_CLASS_C_DEC ret_it(base_type::m_p_nd);
	operator++();
	return (ret_it);
      }

    private:
      void
      inc()
      {
	if (base_type::m_p_nd->m_p_next_sibling != NULL)
	  {
	    base_type::m_p_nd = base_type::m_p_nd->m_p_next_sibling;
	    while (base_type::m_p_nd->m_p_l_child != NULL)
	      base_type::m_p_nd = base_type::m_p_nd->m_p_l_child;
	    return;
	  }

	while (true)
	  {
	    node_pointer p_next = base_type::m_p_nd;
	    base_type::m_p_nd = base_type::m_p_nd->m_p_prev_or_parent;
	    if (base_type::m_p_nd == NULL || base_type::m_p_nd->m_p_l_child == p_next)
	      return;
	  }
      }
    };

#undef PB_DS_CLASS_C_DEC
#undef PB_DS_BASE_C_DEC

  } // namespace detail
} // namespace __gnu_pbds

#endif 
// -*- C++ -*-

// Copyright (C) 2005, 2006, 2008 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_metadata.hpp
 * Contains an implementation struct for this type of heap's node.
 */

#ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NULL_METADATA_HPP
#define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NULL_METADATA_HPP

namespace __gnu_pbds
{
  namespace detail
  {

    struct null_left_child_next_sibling_heap_node_metadata
    { };

  } // namespace detail
} // namespace __gnu_pbds

#endif // #ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NULL_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 container_base_dispatch.hpp
 * Contains an associative container dispatching base.
 */

#ifndef PB_DS_ASSOC_CNTNR_BASE_DS_DISPATCHER_HPP
#define PB_DS_ASSOC_CNTNR_BASE_DS_DISPATCHER_HPP

#include <ext/typelist.h>

#define PB_DS_DATA_TRUE_INDICATOR
#include <ext/pb_ds/detail/list_update_map_/lu_map_.hpp>
#undef PB_DS_DATA_TRUE_INDICATOR

#define PB_DS_DATA_FALSE_INDICATOR
#include <ext/pb_ds/detail/list_update_map_/lu_map_.hpp>
#undef PB_DS_DATA_FALSE_INDICATOR

#define PB_DS_DATA_TRUE_INDICATOR
#include <ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp>
#undef PB_DS_DATA_TRUE_INDICATOR

#define PB_DS_DATA_FALSE_INDICATOR
#include <ext/pb_ds/detail/rb_tree_map_/rb_tree_.hpp>
#undef PB_DS_DATA_FALSE_INDICATOR

#define PB_DS_DATA_TRUE_INDICATOR
#include <ext/pb_ds/detail/splay_tree_/splay_tree_.hpp>
#undef PB_DS_DATA_TRUE_INDICATOR

#define PB_DS_DATA_FALSE_INDICATOR
#include <ext/pb_ds/detail/splay_tree_/splay_tree_.hpp>
#undef PB_DS_DATA_FALSE_INDICATOR

#define PB_DS_DATA_TRUE_INDICATOR
#include <ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp>
#undef PB_DS_DATA_TRUE_INDICATOR

#define PB_DS_DATA_FALSE_INDICATOR
#include <ext/pb_ds/detail/ov_tree_map_/ov_tree_map_.hpp>
#undef PB_DS_DATA_FALSE_INDICATOR

#define PB_DS_DATA_TRUE_INDICATOR
#include <ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp>
#undef PB_DS_DATA_TRUE_INDICATOR

#define PB_DS_DATA_FALSE_INDICATOR
#include <ext/pb_ds/detail/cc_hash_table_map_/cc_ht_map_.hpp>
#undef PB_DS_DATA_FALSE_INDICATOR

#define PB_DS_DATA_TRUE_INDICATOR
#include <ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp>
#undef PB_DS_DATA_TRUE_INDICATOR

#define PB_DS_DATA_FALSE_INDICATOR
#include <ext/pb_ds/detail/gp_hash_table_map_/gp_ht_map_.hpp>
#undef PB_DS_DATA_FALSE_INDICATOR

#define PB_DS_DATA_TRUE_INDICATOR
#include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp>
#undef PB_DS_DATA_TRUE_INDICATOR

#define PB_DS_DATA_FALSE_INDICATOR
#include <ext/pb_ds/detail/pat_trie_/pat_trie_.hpp>
#undef PB_DS_DATA_FALSE_INDICATOR

namespace __gnu_pbds
{
namespace detail
{
  // Primary template.
  template<typename Key, typename Mapped, typename Data_Structure_Taq,
	   typename Policy_Tl, typename Alloc>
    struct container_base_dispatch;

  template<typename Key, typename Mapped, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, Mapped, list_update_tag, 
				   Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>	at0;
      typedef typename at0::type			    	at0t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;
      
    public:
      typedef lu_map_data_<Key, Mapped, at0t, Alloc, at1t>	type;
    };

  template<typename Key, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, null_mapped_type, list_update_tag,
				   Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>	at0;
      typedef typename at0::type			    	at0t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;

    public:
      typedef lu_map_no_data_<Key, null_mapped_type, at0t, Alloc, at1t> type;
    };

  template<typename Key, typename Mapped, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, Mapped, pat_trie_tag, Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;

    public:
      typedef pat_trie_data_<Key, Mapped, at1t, Alloc> 		type;
    };

  template<typename Key, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, null_mapped_type, pat_trie_tag,
				   Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;

    public:
      typedef pat_trie_no_data_<Key, null_mapped_type, at1t, Alloc> type;
    };

  template<typename Key, typename Mapped, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, Mapped, rb_tree_tag, Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>	at0;
      typedef typename at0::type			    	at0t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;

    public:
      typedef rb_tree_data_<Key, Mapped, at0t, at1t, Alloc> 	type;
    };

  template<typename Key, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, null_mapped_type, rb_tree_tag,
				   Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>	at0;
      typedef typename at0::type			    	at0t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;

    public:
      typedef rb_tree_no_data_<Key, null_mapped_type, at0t, at1t, Alloc> type;
    };

  template<typename Key, typename Mapped, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, Mapped, splay_tree_tag, 
				   Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>	at0;
      typedef typename at0::type			    	at0t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;

    public:
      typedef splay_tree_data_<Key, Mapped, at0t, at1t, Alloc> 	type;
    };

  template<typename Key, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, null_mapped_type, splay_tree_tag,
				   Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>	at0;
      typedef typename at0::type			    	at0t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;

    public:
      typedef splay_tree_no_data_<Key, null_mapped_type, at0t, at1t, Alloc> type;
  };

  template<typename Key, typename Mapped, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, Mapped, ov_tree_tag, Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>	at0;
      typedef typename at0::type			    	at0t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;

    public:
      typedef ov_tree_data_<Key, Mapped, at0t, at1t, Alloc> 	type;
  };

  template<typename Key, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, null_mapped_type, ov_tree_tag,
				   Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>	at0;
      typedef typename at0::type			    	at0t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;

    public:
      typedef ov_tree_no_data_<Key, null_mapped_type, at0t, at1t, Alloc> type;
  };

  template<typename Key, typename Mapped, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, Mapped, cc_hash_tag, Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>	at0;
      typedef typename at0::type			    	at0t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2>	at2;
      typedef typename at2::type			    	at2t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3>	at3;
      typedef typename at3::type				at3t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> 	at4;
      typedef typename at4::type			    	at4t;

    public:
      typedef cc_ht_map_data_<Key, Mapped, at0t, at1t, Alloc, at3t::value, 
			      at4t, at2t> 			type;
  };

  template<typename Key, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, null_mapped_type, cc_hash_tag, 
				   Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>	at0;
      typedef typename at0::type			    	at0t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2>	at2;
      typedef typename at2::type			    	at2t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3>	at3;
      typedef typename at3::type				at3t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> 	at4;
      typedef typename at4::type			    	at4t;

    public:
      typedef cc_ht_map_no_data_<Key, null_mapped_type, at0t, at1t, Alloc, 
				 at3t::value, at4t, at2t>    	type;
  };

  template<typename Key, typename Mapped, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, Mapped, gp_hash_tag, Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>	at0;
      typedef typename at0::type			    	at0t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2>	at2;
      typedef typename at2::type			    	at2t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3>	at3;
      typedef typename at3::type				at3t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> 	at4;
      typedef typename at4::type			    	at4t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 5> 	at5;
      typedef typename at5::type			    	at5t;

    public:
      typedef gp_ht_map_data_<Key, Mapped, at0t, at1t, Alloc, at3t::value, 
			      at4t, at5t, at2t> 		type;
  };

  template<typename Key, typename Policy_Tl, typename Alloc>
    struct container_base_dispatch<Key, null_mapped_type, gp_hash_tag,
				   Policy_Tl, Alloc>
    {
    private:
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 0>	at0;
      typedef typename at0::type			    	at0t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 1> 	at1;
      typedef typename at1::type			    	at1t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 2>	at2;
      typedef typename at2::type			    	at2t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 3>	at3;
      typedef typename at3::type				at3t;
      typedef __gnu_cxx::typelist::at_index<Policy_Tl, 4> 	at4;
      typedef typename at4::type			    	at4t;
      typedef __gnu_cxx::typelist::at_index<Po'3licy_Tl, 5> 	at5;
      typedef typename at5::type			    	at5t;

    public:
      typedef gp_ht_map_no_data_<Key, null_mapped_type, at0t, at1t, Alloc,
				 at3t::value, at4t, at5t, at2t>	type;
  };
} // namespace detail
} // namespace __gnu_pbds

#endif 
š

.X
..›
 
split_join_fn_imps.hppœ

insert_fn_imps.hpp�

info_fn_imps.hppž

trace_fn_imps.hppŸ

binary_heap_.hpp 

resize_policy.hpp¡
$
policy_access_fn_imps.hpp¢

find_fn_imps.hpp£
,#
constructors_destructor_fn_imps.hpp¤

debug_fn_imps.hpp¥

erase_fn_imps.hpp¦
 
iterators_fn_imps.hpp§
 
const_point_iterator.hpp¨

const_iterator.hpp©

entry_pred.hppª
0

entry_cmp.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 split_join_fn_imps.hpp
 * Contains an implementation class for a binary_heap.
 */

PB_DS_CLASS_T_DEC
template<typename Pred>
void
PB_DS_CLASS_C_DEC::
split(Pred pred, PB_DS_CLASS_C_DEC& other)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)

    typedef
    typename entry_pred<
    value_type,
    Pred,
    simple_value,
    Allocator>::type
    pred_t;

  const size_type left = partition(pred_t(pred));

  _GLIBCXX_DEBUG_ASSERT(m_size >= left);

  const size_type ersd = m_size - left;

  _GLIBCXX_DEBUG_ASSERT(m_size >= ersd);

  const size_type actual_size =
    resize_policy::get_new_size_for_arbitrary(left);

  const size_type other_actual_size =
    other.get_new_size_for_arbitrary(ersd);

  entry_pointer a_entries = NULL;
  entry_pointer a_other_entries = NULL;

  try
    {
      a_entries = s_entry_allocator.allocate(actual_size);

      a_other_entries = s_entry_allocator.allocate(other_actual_size);
    }
  catch(...)
    {
      if (a_entries != NULL)
	s_entry_allocator.deallocate(a_entries, actual_size);

      if (a_other_entries != NULL)
	s_entry_allocator.deallocate(a_other_entries, other_actual_size);

      __throw_exception_again;
    };

  for (size_type i = 0; i < other.m_size; ++i)
    erase_at(other.m_a_entries, i, s_no_throw_copies_ind);

  _GLIBCXX_DEBUG_ASSERT(actual_size >= left);
  std::copy(m_a_entries, m_a_entries + left, a_entries);
  std::copy(m_a_entries + left, m_a_entries + m_size, a_other_entries);

  s_entry_allocator.deallocate(m_a_entries, m_actual_size);
  s_entry_allocator.deallocate(other.m_a_entries, other.m_actual_size);

  m_actual_size = actual_size;
  other.m_actual_size = other_actual_size;

  m_size = left;
  other.m_size = ersd;

  m_a_entries = a_entries;
  other.m_a_entries = a_other_entries;

  std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this));
  std::make_heap(other.m_a_entries, other.m_a_entries + other.m_size, static_cast<entry_cmp& >(other));

  resize_policy::notify_arbitrary(m_actual_size);
  other.notify_arbitrary(other.m_actual_size);

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
    _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
    }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
join(PB_DS_CLASS_C_DEC& other)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)

  const size_type len = m_size + other.m_size;
  const size_type actual_size = resize_policy::get_new_size_for_arbitrary(len);

  entry_pointer a_entries = NULL;
  entry_pointer a_other_entries = NULL;

  try
    {
      a_entries = s_entry_allocator.allocate(actual_size);
      a_other_entries = s_entry_allocator.allocate(resize_policy::min_size);
    }
  catch(...)
    {
      if (a_entries != NULL)
	s_entry_allocator.deallocate(a_entries, actual_size);

      if (a_other_entries != NULL)
	s_entry_allocator.deallocate(a_other_entries, resize_policy::min_size);

      __throw_exception_again;
    }

  std::copy(m_a_entries, m_a_entries + m_size, a_entries);
  std::copy(other.m_a_entries, other.m_a_entries + other.m_size, a_entries + m_size);

  s_entry_allocator.deallocate(m_a_entries, m_actual_size);
  m_a_entries = a_entries;
  m_size = len;
  m_actual_size = actual_size;

  resize_policy::notify_arbitrary(actual_size);

  std::make_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this));

  s_entry_allocator.deallocate(other.m_a_entries, other.m_actual_size);
  other.m_a_entries = a_other_entries;
  other.m_size = 0;
  other.m_actual_size = resize_policy::min_size;

  other.notify_arbitrary(resize_policy::min_size);

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}

// -*- 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 a binary_heap.
 */

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::point_iterator
PB_DS_CLASS_C_DEC::
push(const_reference r_val)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)

    insert_value(r_val, s_no_throw_copies_ind);

  std::push_heap(m_a_entries, m_a_entries + m_size, static_cast<entry_cmp& >(*this));

  _GLIBCXX_DEBUG_ONLY(assert_valid();)

    return point_iterator(m_a_entries);
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
insert_value(value_type val, true_type)
{
  resize_for_insert_if_needed();

  m_a_entries[m_size++] = val;
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
insert_value(const_reference r_val, false_type)
{
  resize_for_insert_if_needed();

  pointer p_new = s_value_allocator.allocate(1);

  cond_dealtor_t cond(p_new);

  new (p_new) value_type(r_val);

  cond.set_no_action();

  m_a_entries[m_size++] = p_new;
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
insert_entry(entry e)
{
  resize_for_insert_if_needed();

  m_a_entries[m_size++] = e;
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
resize_for_insert_if_needed()
{
  if (!resize_policy::resize_needed_for_grow(m_size))
    {
      _GLIBCXX_DEBUG_ASSERT(m_size < m_actual_size);

      return;
    }

  const size_type new_actual_size =
    resize_policy::get_new_size_for_grow();

  entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size);

  resize_policy::notify_grow_resize();

  std::copy(m_a_entries, m_a_entries + m_size, a_new_entries);

  s_entry_allocator.deallocate(m_a_entries, m_actual_size);

  m_actual_size = new_actual_size;

  m_a_entries = a_new_entries;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
modify(point_iterator it, const_reference r_new_val)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)

    swap_value_imp(it.m_p_e, r_new_val, s_no_throw_copies_ind);

  fix(it.m_p_e);

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
fix(entry_pointer p_e)
{
  size_type i = p_e - m_a_entries;

  if (i > 0&&  entry_cmp::operator()(m_a_entries[parent(i)], m_a_entries[i]))
    {
      size_type parent_i = parent(i);

      while (i > 0&&  entry_cmp::operator()(m_a_entries[parent_i], m_a_entries[i]))
        {
	  std::swap(m_a_entries[i], m_a_entries[parent_i]);

	  i = parent_i;

	  parent_i = parent(i);
        }

      _GLIBCXX_DEBUG_ONLY(assert_valid();)

        return;
    }

  while (i < m_size)
    {
      const size_type left_child_i = left_child(i);
      const size_type right_child_i = right_child(i);

      _GLIBCXX_DEBUG_ASSERT(right_child_i > left_child_i);

      const bool smaller_than_left_child =
	left_child_i < m_size&& 
	entry_cmp::operator()(m_a_entries[i], m_a_entries[left_child_i]);

      const bool smaller_than_right_child =
	right_child_i < m_size&& 
	entry_cmp::operator()(m_a_entries[i], m_a_entries[right_child_i]);

      const bool swap_with_r_child = smaller_than_right_child&& (!smaller_than_left_child ||
								 entry_cmp::operator()(m_a_entries[left_child_i], m_a_entries[right_child_i]));

      const bool swap_with_l_child = !swap_with_r_child&&  smaller_than_left_child;

      if (swap_with_l_child)
        {
	  std::swap(m_a_entries[i], m_a_entries[left_child_i]);

	  i = left_child_i;
        }
      else if (swap_with_r_child)
        {
	  std::swap(m_a_entries[i], m_a_entries[right_child_i]);

	  i = right_child_i;
        }
      else
	i = m_size;
    }
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
swap_value_imp(entry_pointer p_e, value_type new_val, true_type)
{
  * p_e = new_val;
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
swap_value_imp(entry_pointer p_e, const_reference r_new_val, false_type)
{
  value_type tmp(r_new_val);
  (*p_e)->swap(tmp);
}
// -*- 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 a binary_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_entry_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 a binary_heap.
 */

#ifdef PB_DS_BINARY_HEAP_TRACE_

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
trace() const
{
  std::cerr << this << std::endl;

  std::cerr << m_a_entries << std::endl;

  for (size_type i = 0; i < m_size; ++i)
    trace_entry(m_a_entries[i], s_no_throw_copies_ind);

  std::cerr << std::endl;

  std::cerr << "size = " << m_size << " " << "actual_size = " << m_actual_size << std::endl;

  resize_policy::trace();
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
trace_entry(const entry& r_e, false_type) const
{
  std::cout << r_e << " " <<* r_e << std::endl;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
trace_entry(const entry& r_e, true_type) const
{
  std::cout << r_e << std::endl;
}

#endif // #ifdef PB_DS_BINARY_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 binary_heap_.hpp
 * Contains an implementation class for a binary heap.
 */

#ifndef PB_DS_BINARY_HEAP_HPP
#define PB_DS_BINARY_HEAP_HPP

/*
 * Based on CLRS.
 */

#include <queue>
#include <algorithm>
#include <ext/pb_ds/detail/cond_dealtor.hpp>
#include <ext/pb_ds/detail/cond_dealtor.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/detail/binary_heap_/entry_cmp.hpp>
#include <ext/pb_ds/detail/binary_heap_/entry_pred.hpp>
#include <ext/pb_ds/detail/binary_heap_/resize_policy.hpp>
#include <ext/pb_ds/detail/binary_heap_/const_point_iterator.hpp>
#include <ext/pb_ds/detail/binary_heap_/const_iterator.hpp>
#ifdef PB_DS_BINARY_HEAP_TRACE_
#include <iostream>
#endif
#include <ext/pb_ds/detail/type_utils.hpp>
#include <debug/debug.h>

namespace __gnu_pbds
{
  namespace detail
  {
#define PB_DS_CLASS_T_DEC \
    template<typename Value_Type, class Cmp_Fn, class Allocator>

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

#define PB_DS_ENTRY_CMP_DEC \
    entry_cmp<Value_Type, Cmp_Fn, is_simple<Value_Type>::value, Allocator>::type

#define PB_DS_RESIZE_POLICY_DEC	\
    __gnu_pbds::detail::resize_policy<typename Allocator::size_type>

    /**
     * class description = "Base class for some types of h3ap$">
     **/
    template<typename Value_Type, class Cmp_Fn, class Allocator>
    class binary_heap_ : public PB_DS_ENTRY_CMP_DEC,
			 public PB_DS_RESIZE_POLICY_DEC
    {

    private:
      enum
	{
	  simple_value = is_simple<Value_Type>::value
	};

      typedef integral_constant<int, simple_value> no_throw_copies_t;

      typedef
      typename Allocator::template rebind<
	Value_Type>::other
      value_allocator;

      typedef
      typename __conditional_type<
	simple_value,
	Value_Type,
	typename value_allocator::pointer>::__type
      entry;

      typedef
      typename Allocator::template rebind<
	entry>::other
      entry_allocator;

      typedef typename entry_allocator::pointer entry_pointer;

      typedef typename PB_DS_ENTRY_CMP_DEC entry_cmp;

      typedef PB_DS_RESIZE_POLICY_DEC resize_policy;

      typedef
      cond_dealtor<
	Value_Type,
	Allocator>
      cond_dealtor_t;

    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
      binary_heap_const_point_iterator_<
	value_type,
	entry,
	simple_value,
	Allocator>
      const_point_iterator;

      typedef const_point_iterator point_iterator;

      typedef
      binary_heap_const_iterator_<
	value_type,
	entry,
	simple_value,
	Allocator>
      const_iterator;

      typedef const_iterator iterator;

      typedef Cmp_