code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file constructors_destructor_fn_imps.hpp
 * Contains an implementation class for binary_heap_.
 */

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::entry_allocator
PB_DS_CLASS_C_DEC::s_entry_allocator;

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::value_allocator
PB_DS_CLASS_C_DEC::s_value_allocator;

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::no_throw_copies_t
PB_DS_CLASS_C_DEC::s_no_throw_copies_ind;

PB_DS_CLASS_T_DEC
template<typename It>
void
PB_DS_CLASS_C_DEC::
copy_from_range(It first_it, It last_it)
{
  while (first_it != last_it)
    {
      insert_value(*first_it, s_no_throw_copies_ind);
      ++first_it;
    }

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

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
binary_heap_() :
  m_size(0),
  m_actual_size(resize_policy::min_size),
  m_a_entries(s_entry_allocator.allocate(m_actual_size))
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
binary_heap_(const Cmp_Fn& r_cmp_fn) :
  entry_cmp(r_cmp_fn),
  m_size(0),
  m_actual_size(resize_policy::min_size),
  m_a_entries(s_entry_allocator.allocate(m_actual_size))
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
binary_heap_(const PB_DS_CLASS_C_DEC& other) :
  entry_cmp(other),
  resize_policy(other),
  m_size(0),
  m_actual_size(other.m_actual_size),
  m_a_entries(s_entry_allocator.allocate(m_actual_size))
{
  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
  _GLIBCXX_DEBUG_ASSERT(m_a_entries != other.m_a_entries);

  const_iterator first_it = other.begin();
  const_iterator last_it = other.end();

  try
    {
      while (first_it != last_it)
        {
	  insert_value(*first_it, s_no_throw_copies_ind);
	  ++first_it;
        }
    }
  catch(...)
    {
      for (size_type i = 0; i < m_size; ++i)
	erase_at(m_a_entries, i, s_no_throw_copies_ind);

      s_entry_allocator.deallocate(m_a_entries, m_actual_size);
      __throw_exception_again;
    }
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
  _GLIBCXX_DEBUG_ASSERT(m_a_entries != other.m_a_entries);

  value_swap(other);
  std::swap((entry_cmp& )(*this), (entry_cmp& )other);
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
value_swap(PB_DS_CLASS_C_DEC& other)
{
  std::swap(m_a_entries, other.m_a_entries);
  std::swap(m_size, other.m_size);
  std::swap(m_actual_size, other.m_actual_size);
  static_cast<resize_policy*>(this)->swap(other);
}

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~binary_heap_()
{
  for (size_type i = 0; i < m_size; ++i)
    erase_at(m_a_entries, i, s_no_throw_copies_ind);
  s_entry_allocator.deallocate(m_a_entries, m_actual_size);
}


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file debug_fn_imps.hpp
 * Contains an implementation class for a binary_heap.
 */

#ifdef _GLIBCXX_DEBUG

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid() const
{
#ifdef PB_DS_REGRESSION
  s_entry_allocator.check_allocated(m_a_entries, m_actual_size);
#endif

  resize_policy::assert_valid();
  _GLIBCXX_DEBUG_ASSERT(m_size <= m_actual_size);
  for (size_type i = 0; i < m_size; ++i)
    {
#ifdef PB_DS_REGRESSION
      s_value_allocator.check_allocated(m_a_entries[i], 1);
#endif

      if (left_child(i) < m_size)
	_GLIBCXX_DEBUG_ASSERT(!entry_cmp::operator()(m_a_entries[i], m_a_entries[left_child(i)]));

      _GLIBCXX_DEBUG_ASSERT(parent(left_child(i)) == i);

      if (right_child(i) < m_size)
	_GLIBCXX_DEBUG_ASSERT(!entry_cmp::operator()(m_a_entries[i], m_a_entries[right_child(i)]));

      _GLIBCXX_DEBUG_ASSERT(parent(right_child(i)) == i);
    }
}

#endif

repo_name: veiledmerc/mira

license: mit


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

#ifndef PB_DS_BINARY_HEAP_ENTRY_CMP_HPP
#define PB_DS_BINARY_HEAP_ENTRY_CMP_HPP

namespace pb_ds
{
  namespace detail
  {

    template<typename Value_Type,
	     class Cmp_Fn,
	     bool No_Throw,
	     class Allocator>
    struct entry_cmp
    {
      typedef Cmp_Fn type;
    };

    template<typename Value_Type, class Cmp_Fn, class Allocator>
    struct entry_cmp<
      Value_Type,
      Cmp_Fn,
      false,
      Allocator>
    {
    public:
      typedef
      typename Allocator::template rebind<
      Value_Type>::other::const_pointer
      entry;

      struct type : public Cmp_Fn
      {
      public:
	inline
	type()
	{ }

	inline
	type(const Cmp_Fn& other) : Cmp_Fn(other)
	{ }

	inline bool
	operator()(entry p_lhs,  entry p_rhs) const
	{
	  return Cmp_Fn::operator()(*p_lhs, * p_rhs);
	}
      };
    };

  } // namespace detail
} // namespace pb_ds

#endif // #ifndef PB_DS_BINARY_HEAP_ENTRY_CMP_HPP


code:
// -*- 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 entry_pred.hpp
 * Contains an implementation class for a binary_heap.
 */

#ifndef PB_DS_BINARY_HEAP_ENTRY_PRED_HPP
#define PB_DS_BINARY_HEAP_ENTRY_PRED_HPP

namespace pb_ds
{
  namespace detail
  {

    template<typename Value_Type,
	     class Pred,
	     bool No_Throw,
	     class Allocator>
    struct entry_pred
    {
      typedef Pred type;
    };

    template<typename Value_Type, class Pred, class Allocator>
    struct entry_pred<
      Value_Type,
      Pred,
      false,
      Allocator>
    {
    public:
      typedef
      typename Allocator::template rebind<
      Value_Type>::other::const_pointer
      entry;

      struct type : public Pred
      {
      public:
	inline
	type()
	{ }

	inline
	type(const Pred& other) : Pred(other)
	{ }

	inline bool
	operator()(entry p_v) const
	{
	  return Pred::operator()(*p_v);
	}
      };
    };

  } // namespace detail
} // namespace pb_ds

#endif // #ifndef PB_DS_BINARY_HEAP_ENTRY_PRED_HPP


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file erase_fn_imps.hpp
 * Contains an implementation class for a binary_heap.
 */

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
clear()
{
  for (size_type i = 0; i < m_size; ++i)
    erase_at(m_a_entries, i, s_no_throw_copies_ind);

  try
    {
      const size_type actual_size = resize_policy::get_new_size_for_arbitrary(0);

      entry_pointer a_entries = s_entry_allocator.allocate(actual_size);

      resize_policy::notify_arbitrary(actual_size);

      s_entry_allocator.deallocate(m_a_entries, m_actual_size);

      m_actual_size = actual_size;

      m_a_entries = a_entries;
    }
  catch(...)
    { }

  m_size = 0;

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
erase_at(entry_pointer a_entries, size_type i, false_type)
{
  a_entries[i]->~value_type();

  s_value_allocator.deallocate(a_entries[i], 1);
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
erase_at(entry_pointer, size_type, true_type)
{ }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
pop()
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
    _GLIBCXX_DEBUG_ASSERT(!empty());

  erase_at(m_a_entries, 0, s_no_throw_copies_ind);

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

  resize_for_erase_if_needed();

  _GLIBCXX_DEBUG_ASSERT(m_size > 0);
  --m_size;

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

PB_DS_CLASS_T_DEC
template<typename Pred>
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
erase_if(Pred pred)
{
  _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;

  for (size_type i = left; i < m_size; ++i)
    erase_at(m_a_entries, i, s_no_throw_copies_ind);

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

      entry_pointer a_entries = s_entry_allocator.allocate(actual_size);

      std::copy(m_a_entries, m_a_entries + left, a_entries);

      s_entry_allocator.deallocate(m_a_entries, m_actual_size);

      m_actual_size = actual_size;

      resize_policy::notify_arbitrary(m_actual_size);
    }
  catch(...)
    { };

  m_size = left;

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

  _GLIBCXX_DEBUG_ONLY(assert_valid();)

    return ersd;
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
erase(point_iterator it)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
    _GLIBCXX_DEBUG_ASSERT(!empty());

  const size_type fix_pos = it.m_p_e - m_a_entries;

  std::swap(*it.m_p_e, m_a_entries[m_size - 1]);

  erase_at(m_a_entries, m_size - 1, s_no_throw_copies_ind);

  resize_for_erase_if_needed();

  _GLIBCXX_DEBUG_ASSERT(m_size > 0);
  --m_size;

  _GLIBCXX_DEBUG_ASSERT(fix_pos <= m_size);

  if (fix_pos != m_size)
    fix(m_a_entries + fix_pos);

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
resize_for_erase_if_needed()
{
  if (!resize_policy::resize_needed_for_shrink(m_size))
    return;

  try
    {
      const size_type new_actual_size =
	resize_policy::get_new_size_for_shrink();

      entry_pointer a_new_entries = s_entry_allocator.allocate(new_actual_size);

      resize_policy::notify_shrink_resize();

      _GLIBCXX_DEBUG_ASSERT(m_size > 0);
      std::copy(m_a_entries, m_a_entries + m_size - 1, 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;
    }
  catch(...)
    { }
}

PB_DS_CLASS_T_DEC
template<typename Pred>
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
partition(Pred pred)
{
  size_type left = 0;
  size_type right = m_size - 1;

  while (right + 1 != left)
    {
      _GLIBCXX_DEBUG_ASSERT(left <= m_size);

      if (!pred(m_a_entries[left]))
	++left;
      else if (pred(m_a_entries[right]))
	--right;
      else
        {
	  _GLIBCXX_DEBUG_ASSERT(left < right);

	  std::swap(m_a_entries[left], m_a_entries[right]);

	  ++left;
	  --right;
        }
    }

  return left;
}


code:
// -*- 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 find_fn_imps.hpp
 * Contains an implementation class for a binary_heap.
 */

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_reference
PB_DS_CLASS_C_DEC::
top() const
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
    _GLIBCXX_DEBUG_ASSERT(!empty());

  return top_imp(s_no_throw_copies_ind);
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_reference
PB_DS_CLASS_C_DEC::
top_imp(true_type) const
{
  return* m_a_entries;
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_reference
PB_DS_CLASS_C_DEC::
top_imp(false_type) const
{
  return** m_a_entries;
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
left_child(size_type i)
{
  return i*  2 + 1;
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
right_child(size_type i)
{
  return i*  2 + 2;
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
parent(size_type i)
{
  return (i - 1) / 2;
}


code:
// -*- 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());
}


code:
// -*- 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);
}


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

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::
begin()
{
  return (iterator(m_a_entries));
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_iterator
PB_DS_CLASS_C_DEC::
begin() const
{
  return (const_iterator(m_a_entries));
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::
end()
{
  return (iterator(m_a_entries + m_size));
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_iterator
PB_DS_CLASS_C_DEC::
end() const
{
  return (const_iterator(m_a_entries + m_size));
}


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file policy_access_fn_imps.hpp
 * Contains an implementation class for a binary_heap.
 */

PB_DS_CLASS_T_DEC
Cmp_Fn&
PB_DS_CLASS_C_DEC::
get_cmp_fn()
{
  return (*this);
}

PB_DS_CLASS_T_DEC
const Cmp_Fn&
PB_DS_CLASS_C_DEC::
get_cmp_fn() const
{
  return (*this);
}


code:
// -*- 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 resize_policy.hpp
 * Contains an implementation class for a binary_heap.
 */

#ifndef PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP
#define PB_DS_BINARY_HEAP_RESIZE_POLICY_HPP

#include <debug/debug.h>

namespace pb_ds
{
  namespace detail
  {

#define PB_DS_CLASS_T_DEC template<typename Size_Type>

#define PB_DS_CLASS_C_DEC resize_policy<Size_Type>

    template<typename Size_Type>
    class resize_policy
    {
    public:
      typedef Size_Type size_type;

      enum
	{
	  min_size = 16
	};

    public:
      inline
      resize_policy();

      inline void
      swap(PB_DS_CLASS_C_DEC& other);

      inline bool
      resize_needed_for_grow(size_type size) const;

      inline bool
      resize_needed_for_shrink(size_type size) const;

      inline bool
      grow_needed(size_type size) const;

      inline bool
      shrink_needed(size_type size) const;

      inline size_type
      get_new_size_for_grow() const;

      inline size_type
      get_new_size_for_shrink() const;

      size_type
      get_new_size_for_arbitrary(size_type size) const;

      inline void
      notify_grow_resize();

      inline void
      notify_shrink_resize();

      void
      notify_arbitrary(size_type actual_size);

#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;
#endif

#ifdef PB_DS_BINARY_HEAP_TRACE_
      void
      trace() const;
#endif

    private:
      enum
	{
	  ratio = 8,
	  factor = 2
	};

    private:
      size_type m_next_shrink_size;
      size_type m_next_grow_size;
    };

    PB_DS_CLASS_T_DEC
    inline
    PB_DS_CLASS_C_DEC::
    resize_policy() :
      m_next_shrink_size(0),
      m_next_grow_size(min_size)
    { _GLIBCXX_DEBUG_ONLY(assert_valid();) }

    PB_DS_CLASS_T_DEC
    inline void
    PB_DS_CLASS_C_DEC::
    swap(PB_DS_CLASS_C_DEC& other)
    {
      std::swap(m_next_shrink_size, other.m_next_shrink_size);
      std::swap(m_next_grow_size, other.m_next_grow_size);
    }

    PB_DS_CLASS_T_DEC
    inline bool
    PB_DS_CLASS_C_DEC::
    resize_needed_for_grow(size_type size) const
    {
      _GLIBCXX_DEBUG_ASSERT(size <= m_next_grow_size);
      return size == m_next_grow_size;
    }

    PB_DS_CLASS_T_DEC
    inline bool
    PB_DS_CLASS_C_DEC::
    resize_needed_for_shrink(size_type size) const
    {
      _GLIBCXX_DEBUG_ASSERT(size <= m_next_grow_size);
      return size == m_next_shrink_size;
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    get_new_size_for_grow() const
    { return m_next_grow_size*  factor; }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    get_new_size_for_shrink() const
    {
      const size_type half_size = m_next_grow_size / factor;
      return std::max(static_cast<size_type>(min_size), half_size);
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    get_new_size_for_arbitrary(size_type size) const
    {
      size_type ret = min_size;
      while (ret < size)
	ret *= factor;
      return ret;
    }

    PB_DS_CLASS_T_DEC
    inline void
    PB_DS_CLASS_C_DEC::
    notify_grow_resize()
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size);
      m_next_grow_size *= factor;
      m_next_shrink_size = m_next_grow_size / ratio;
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

    PB_DS_CLASS_T_DEC
    inline void
    PB_DS_CLASS_C_DEC::
    notify_shrink_resize()
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      m_next_shrink_size /= factor;
      if (m_next_shrink_size == 1)
	m_next_shrink_size = 0;

      m_next_grow_size =
	std::max(m_next_grow_size / factor, static_cast<size_type>(min_size));
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

    PB_DS_CLASS_T_DEC
    inline void
    PB_DS_CLASS_C_DEC::
    notify_arbitrary(size_type actual_size)
    {
      m_next_grow_size = actual_size;
      m_next_shrink_size = m_next_grow_size / ratio;
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

#ifdef _GLIBCXX_DEBUG
    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    assert_valid() const
    {
      _GLIBCXX_DEBUG_ASSERT(m_next_shrink_size == 0 ||
		       m_next_shrink_size*  ratio == m_next_grow_size);

      _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= min_size);
    }
#endif

#ifdef PB_DS_BINARY_HEAP_TRACE_
    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    trace() const
    {
      std::cerr << "shrink = " << m_next_shrink_size <<
	" grow = " << m_next_grow_size << std::endl;
    }
#endif

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

} // namespace detail
} // namespace pb_ds

#endif


code:
// -*- 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();)
}


code:
// -*- 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_


code:
// -*- 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 binomial_heap_.hpp
 * Contains an implementation class for a binomial heap.
 */

/*
 * Binomial heap.
 * Vuillemin J is the mastah.
 * Modified from CLRS.
 */

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

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 \
    binomial_heap_<Value_Type, Cmp_Fn, Allocator>

#define PB_DS_BASE_C_DEC \
    binomial_heap_base_<Value_Type, Cmp_Fn, Allocator>

    /**
     * class description = "8y|\|0|\/|i41 h34p 74813">
     **/
    template<typename Value_Type, class Cmp_Fn, class Allocator>
    class binomial_heap_ : public PB_DS_BASE_C_DEC
    {
    private:
      typedef PB_DS_BASE_C_DEC base_type;
      typedef typename base_type::node_pointer node_pointer;
      typedef typename base_type::const_node_pointer const_node_pointer;

    public:
      typedef Value_Type value_type;
      typedef typename Allocator::size_type size_type;
      typedef typename Allocator::difference_type difference_type;
      typedef typename base_type::pointer pointer;
      typedef typename base_type::const_pointer const_pointer;
      typedef typename base_type::reference reference;
      typedef typename base_type::const_reference const_reference;
      typedef typename base_type::const_point_iterator const_point_iterator;
      typedef typename base_type::point_iterator point_iterator;
      typedef typename base_type::const_iterator const_iterator;
      typedef typename base_type::iterator iterator;
      typedef typename base_type::cmp_fn cmp_fn;
      typedef typename base_type::allocator allocator;

      binomial_heap_();

      binomial_heap_(const Cmp_Fn& r_cmp_fn);

      binomial_heap_(const PB_DS_CLASS_C_DEC& other);

      ~binomial_heap_();

    protected:
#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;
#endif
    };

#include <ext/pb_ds/detail/binomial_heap_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/binomial_heap_/debug_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


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file constructors_destructor_fn_imps.hpp
 * Contains an implementation for binomial_heap_.
 */

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
binomial_heap_()
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
binomial_heap_(const Cmp_Fn& r_cmp_fn) :
  PB_DS_BASE_C_DEC(r_cmp_fn)
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
binomial_heap_(const PB_DS_CLASS_C_DEC& other) :
  PB_DS_BASE_C_DEC(other)
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~binomial_heap_() { }


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file debug_fn_imps.hpp
 * Contains an implementation for binomial_heap_.
 */

#ifdef _GLIBCXX_DEBUG

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid() const
{ base_type::assert_valid(true); }

#endif


code:
// -*- 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 binomial_heap_base_.hpp
 * Contains an implementation class for a base of binomial heaps.
 */

#ifndef PB_DS_BINOMIAL_HEAP_BASE_HPP
#define PB_DS_BINOMIAL_HEAP_BASE_HPP

/*
 * Binomial heap base.
 * Vuillemin J is the mastah.
 * Modified from CLRS.
 */

#include <debug/debug.h>
#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>

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 \
    binomial_heap_base_<Value_Type, Cmp_Fn, Allocator>

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

    /**
     * class description = "8y|\|0|\/|i41 h34p 74813">
     **/
    template<typename Value_Type, class Cmp_Fn, class Allocator>
    class binomial_heap_base_ : public PB_DS_BASE_C_DEC
    {

    private:
      typedef PB_DS_BASE_C_DEC base_type;

    protected:
      typedef typename base_type::node node;

      typedef typename base_type::node_pointer node_pointer;

      typedef typename base_type::const_node_pointer const_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;

    public:

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

      inline void
      clear();

      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:

      binomial_heap_base_();

      binomial_heap_base_(const Cmp_Fn& r_cmp_fn);

      binomial_heap_base_(const PB_DS_CLASS_C_DEC& other);

      void
      swap(PB_DS_CLASS_C_DEC& other);

      ~binomial_heap_base_();

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

      inline void
      find_max();

#ifdef _GLIBCXX_DEBUG
      void
      assert_valid(bool strictly_binomial) const;

      void
      assert_max() const;
#endif

    private:

      inline node_pointer
      fix(node_pointer p_nd) const;

      inline void
      insert_node(node_pointer p_nd);

      inline void
      remove_parentless_node(node_pointer p_nd);

      inline node_pointer
      join(node_pointer p_lhs, node_pointer p_rhs) const;

#ifdef _GLIBCXX_DEBUG
      void
      assert_node_consistent(const_node_pointer, bool, bool) const;
#endif

    protected:
      node_pointer m_p_max;
    };

#include <ext/pb_ds/detail/binomial_heap_base_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/binomial_heap_base_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/binomial_heap_base_/find_fn_imps.hpp>
#include <ext/pb_ds/detail/binomial_heap_base_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/binomial_heap_base_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/binomial_heap_base_/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

#endif


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file constructors_destructor_fn_imps.hpp
 * Contains an implementation class for a base of binomial heaps.
 */

PB_DS_CLASS_T_DEC
template<typename It>
void
PB_DS_CLASS_C_DEC::
copy_from_range(It first_it, It last_it)
{
  while (first_it != last_it)
    push(*(first_it++));

  _GLIBCXX_DEBUG_ONLY(assert_valid(false);)
    }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
binomial_heap_base_() :
  m_p_max(NULL)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid(false);)
    }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
binomial_heap_base_(const Cmp_Fn& r_cmp_fn) :
  PB_DS_BASE_C_DEC(r_cmp_fn),
  m_p_max(NULL)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid(false);)
    }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
binomial_heap_base_(const PB_DS_CLASS_C_DEC& other) :
  PB_DS_BASE_C_DEC(other),
  m_p_max(NULL)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid(false);)
    }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid(false);)

    base_type::swap(other);

  std::swap(m_p_max, other.m_p_max);

  _GLIBCXX_DEBUG_ONLY(assert_valid(false);)
    }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~binomial_heap_base_()
{ }


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file debug_fn_imps.hpp
 * Contains an implementation class for a base of binomial heaps.
 */

#ifdef _GLIBCXX_DEBUG

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid(bool strictly_binomial) const
{
  base_type::assert_valid();
  assert_node_consistent(base_type::m_p_root, strictly_binomial, true);
  assert_max();
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_max() const
{
  if (m_p_max == NULL)
    return;
  _GLIBCXX_DEBUG_ASSERT(base_type::parent(m_p_max) == NULL);
  for (const_iterator it = base_type::begin(); it != base_type::end(); ++it)
    _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(m_p_max->m_value, it.m_p_nd->m_value));
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_node_consistent(const_node_pointer p_nd, bool strictly_binomial, bool increasing) const
{
  _GLIBCXX_DEBUG_ASSERT(increasing || strictly_binomial);
  base_type::assert_node_consistent(p_nd, false);
  if (p_nd == NULL)
    return;
  _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == base_type::degree(p_nd));
  _GLIBCXX_DEBUG_ASSERT(base_type::size_under_node(p_nd) ==
		   static_cast<size_type>(1 << p_nd->m_metadata));
  assert_node_consistent(p_nd->m_p_next_sibling, strictly_binomial, increasing);
  assert_node_consistent(p_nd->m_p_l_child, true, false);
  if (p_nd->m_p_next_sibling != NULL)
    if (increasing)
      {
	if (strictly_binomial)
	  _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata < p_nd->m_p_next_sibling->m_metadata);
	else
	  _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata <= p_nd->m_p_next_sibling->m_metadata);
      }
    else
      _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata > p_nd->m_p_next_sibling->m_metadata);
}

#endif


code:
// -*- C++ -*-

// Copyright (C) 2005, 2006 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the terms
// of the GNU General Public License as published by the Free Software
// Foundation; either version 2, or (at your option) any later
// version.

// This library is distributed in the hope that it will be useful, but
// WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
// General Public License for more details.

// You should have received a copy of the GNU General Public License
// along with this library; see the file COPYING.  If not, write to
// the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
// MA 02111-1307, USA.

// As a special exception, you may use this file as part of a free
// software library without restriction.  Specifically, if other files
// instantiate templates or use macros or inline functions from this
// file, or you compile this file and link it with other files to
// produce an executable, this file does not by itself cause the
// resulting executable to be covered by the GNU General Public
// License.  This exception does not however invalidate any other
// reasons why the executable file might be covered by the GNU General
// Public License.

// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.

// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.

/**
 * @file erase_fn_imps.hpp
 * Contains an implementation class for a base of binomial heaps.
 */

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
pop()
{
  _GLIBCXX_DEBUG_ONLY(assert_valid(true);)
    _GLIBCXX_DEBUG_ASSERT(!base_type::empty());

  if (m_p_max == NULL)
    find_max();

  _GLIBCXX_DEBUG_ASSERT(m_p_max != NULL);

  node_pointer p_nd = m_p_max;

  remove_parentless_node(m_p_max);

  base_type::actual_erase_node(p_nd);

  m_p_max = NULL;

  _GLIBCXX_DEBUG_ONLY(assert_valid(true);)
    }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
remove_parentless_node(node_pointer p_nd)
{
  _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
  _GLIBCXX_DEBUG_ASSERT(base_type::parent(p_nd) == NULL);

  node_pointer p_cur_root = p_nd == base_type::m_p_root?
    p_nd->m_p_next_sibling :
    base_type::m_p_root;

  if (p_cur_root != NULL)
    p_cur_root->m_p_prev_or_parent = NULL;

  if (p_nd->m_p_prev_or_parent != NULL)
    p_nd->m_p_prev_or_parent->m_p_next_sibling = p_nd->m_p_next_sibling;

  if (p_nd->m_p_next_sibling != NULL)
    p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd->m_p_prev_or_parent;

  node_pointer p_child = p_nd->m_p_l_child;

  if (p_child != NULL)
    {
      p_child->m_p_prev_or_parent = NULL;

      while (p_child->m_p_next_sibling != NULL)
	p_child = p_child->m_p_next_sibling;
    }

  m_p_max = NULL;

  base_type::m_p_root = join(p_cur_root, p_child);
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
clear()
{
  base_type::clear();

  m_p_max = NULL;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
erase(point_iterator it)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid(true);)
    _GLIBCXX_DEBUG_ASSERT(!base_type::empty());

  base_type::bubble_to_top(it.m_p_nd);

  remove_parentless_node(it.m_p_nd);

  base_type::actual_erase_node(it.m_p_nd);

  m_p_max = NULL;

  _GLIBCXX_DEBUG_ONLY(assert_valid(true);)
    }

PB_DS_CLASS_T_DEC
template<typename Pred>
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
erase_if(Pred pred)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid(true);)

    if (base_type::empty())
      {
        _GLIBCXX_DEBUG_ONLY(assert_valid(true);)

	  return 0;
      }

  base_type::to_linked_list();

  node_pointer p_out = base_type::prune(pred);

  size_type ersd = 0;

  while (p_out != NULL)
    {
      ++ersd;

      node_pointer p_next = p_out->m_p_next_sibling;

      base_type::actual_erase_node(p_out);

      p_out = p_next;
    }

  node_pointer p_cur = base_type::m_p_root;

  base_type::m_p_root = NULL;

  while (p_cur != NULL)
    {
      node_pointer p_next = p_cur->m_p_next_sibling;

      p_cur->m_p_l_child = p_cur->m_p_prev_or_parent = NULL;

      p_cur->m_metadata = 0;

      p_cur->m_p_next_sibling = base_type::m_p_root;

      if (base_type::m_p_root != NULL)
	base_type::m_p_root->m_p_prev_or_parent = p_cur;

      base_type::m_p_root = p_cur;

      base_type::m_p_root = fix(base_type::m_p_root);

      p_cur = p_next;
    }

  m_p_max = NULL;

  _GLIBCXX_DEBUG_ONLY(assert_valid(true);)

    return ersd;
}


code:
// -*- 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 find_fn_imps.hpp
 * Contains an implementation class for a base of binomial heaps.
 */

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_reference
PB_DS_CLASS_C_DEC::
top() const
{
  _GLIBCXX_DEBUG_ONLY(assert_valid(false);)
    _GLIBCXX_DEBUG_ASSERT(!base_type::empty());

  if (m_p_max == NULL)
    const_cast<PB_DS_CLASS_C_DEC* >(this)->find_max();

  _GLIBCXX_DEBUG_ASSERT(m_p_max != NULL);
  return m_p_max->m_value;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
find_max()
{
  node_pointer p_cur = base_type::m_p_root;

  m_p_max = p_cur;

  while (p_cur != NULL)
    {
      if (Cmp_Fn::operator()(m_p_max->m_value, p_cur->m_value))
	m_p_max = p_cur;

      p_cur = p_cur->m_p_next_sibling;
    }
}


code:
// -*- 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 base of binomial heaps.
 */

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

    node_pointer p_nd = base_type::get_new_node_for_insert(r_val);

  insert_node(p_nd);

  m_p_max = NULL;

  _GLIBCXX_DEBUG_ONLY(assert_valid(true);)

    return point_iterator(p_nd);
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
insert_node(node_pointer p_nd)
{
  if (base_type::m_p_root == NULL)
    {
      p_nd->m_p_next_sibling = p_nd->m_p_prev_or_parent =
	p_nd->m_p_l_child = NULL;

      p_nd->m_metadata = 0;

      base_type::m_p_root = p_nd;

      return;
    }

  if (base_type::m_p_root->m_metadata > 0)
    {
      p_nd->m_p_prev_or_parent = p_nd->m_p_l_child = NULL;

      p_nd->m_p_next_sibling = base_type::m_p_root;

      base_type::m_p_root->m_p_prev_or_parent = p_nd;

      base_type::m_p_root = p_nd;

      p_nd->m_metadata = 0;

      return;
    }

  if (Cmp_Fn::operator()(base_type::m_p_root->m_value, p_nd->m_value))
    {
      p_nd->m_p_next_sibling = base_type::m_p_root->m_p_next_sibling;

      p_nd->m_p_prev_or_parent = NULL;

      p_nd->m_metadata = 1;

      p_nd->m_p_l_child = base_type::m_p_root;

      base_type::m_p_root->m_p_prev_or_parent = p_nd;

      base_type::m_p_root->m_p_next_sibling = NULL;

      base_type::m_p_root = p_nd;
    }
  else
    {
      p_nd->m_p_next_sibling = NULL;

      p_nd->m_p_l_child = NULL;

      p_nd->m_p_prev_or_parent = base_type::m_p_root;

      p_nd->m_metadata = 0;

      _GLIBCXX_DEBUG_ASSERT(base_type::m_p_root->m_p_l_child == 0);
      base_type::m_p_root->m_p_l_child = p_nd;

      base_type::m_p_root->m_metadata = 1;
    }

  base_type::m_p_root = fix(base_type::m_p_root);
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
fix(node_pointer p_nd) const
{
  while (p_nd->m_p_next_sibling != NULL&&
	 p_nd->m_metadata == p_nd->m_p_next_sibling->m_metadata)
    {
      node_pointer p_next = p_nd->m_p_next_sibling;

      if (Cmp_Fn::operator()(p_nd->m_value, p_next->m_value))
        {
	  p_next->m_p_prev_or_parent =
	    p_nd->m_p_prev_or_parent;

	  if (p_nd->m_p_prev_or_parent != NULL)
	    p_nd->m_p_prev_or_parent->m_p_next_sibling = p_next;

	  base_type::make_child_of(p_nd, p_next);

	  ++p_next->m_metadata;

	  p_nd = p_next;
        }
      else
        {
	  p_nd->m_p_next_sibling = p_next->m_p_next_sibling;

	  if (p_nd->m_p_next_sibling != NULL)
	    p_next->m_p_next_sibling = NULL;

	  base_type::make_child_of(p_next, p_nd);

	  ++p_nd->m_metadata;
        }
    }

  if (p_nd->m_p_next_sibling != NULL)
    p_nd->m_p_next_sibling->m_p_prev_or_parent = p_nd;

  return p_nd;
}

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(true);)
    node_pointer p_nd = it.m_p_nd;

  _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
  _GLIBCXX_DEBUG_ONLY(base_type::assert_node_consistent(p_nd, false);)

    const bool bubble_up = Cmp_Fn::operator()(p_nd->m_value, r_new_val);

  p_nd->m_value = r_new_val;

  if (bubble_up)
    {
      node_pointer p_parent = base_type::parent(p_nd);

      while (p_parent != NULL&&
	     Cmp_Fn::operator()(p_parent->m_value, p_nd->m_value))
        {
	  base_type::swap_with_parent(p_nd, p_parent);

	  p_parent = base_type::parent(p_nd);
        }

      if (p_nd->m_p_prev_or_parent == NULL)
	base_type::m_p_root = p_nd;

      m_p_max = NULL;

      _GLIBCXX_DEBUG_ONLY(assert_valid(true);)

        return;
    }

  base_type::bubble_to_top(p_nd);

  remove_parentless_node(p_nd);

  insert_node(p_nd);

  m_p_max = NULL;

  _GLIBCXX_DEBUG_ONLY(assert_valid(true);)
    }


code:
// -*- 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 base of binomial heaps.
 */

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(true);)
    _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);)

    other.clear();

  if (base_type::empty())
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid(true);)
        _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);)

        return;
    }

  base_type::to_linked_list();

  node_pointer p_out = base_type::prune(pred);

  while (p_out != NULL)
    {
      _GLIBCXX_DEBUG_ASSERT(base_type::m_size > 0);
      --base_type::m_size;

      ++other.m_size;

      node_pointer p_next = p_out->m_p_next_sibling;

      p_out->m_p_l_child = p_out->m_p_prev_or_parent = NULL;

      p_out->m_metadata = 0;

      p_out->m_p_next_sibling = other.m_p_root;

      if (other.m_p_root != NULL)
	other.m_p_root->m_p_prev_or_parent = p_out;

      other.m_p_root = p_out;

      other.m_p_root = other.fix(other.m_p_root);

      p_out = p_next;
    }

  _GLIBCXX_DEBUG_ONLY(other.assert_valid(true);)

    node_pointer p_cur = base_type::m_p_root;

  base_type::m_p_root = NULL;

  while (p_cur != NULL)
    {
      node_pointer p_next = p_cur->m_p_next_sibling;

      p_cur->m_p_l_child = p_cur->m_p_prev_or_parent = NULL;

      p_cur->m_metadata = 0;

      p_cur->m_p_next_sibling = base_type::m_p_root;

      if (base_type::m_p_root != NULL)
	base_type::m_p_root->m_p_prev_or_parent = p_cur;

      base_type::m_p_root = p_cur;

      base_type::m_p_root = fix(base_type::m_p_root);

      p_cur = p_next;
    }

  m_p_max = NULL;

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

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

    node_pointer p_other = other.m_p_root;

  if (p_other != NULL)
    do
      {
	node_pointer p_next = p_other->m_p_next_sibling;

	std::swap(p_other->m_p_next_sibling, p_other->m_p_prev_or_parent);

	p_other = p_next;
      }
    while (p_other != NULL);

  base_type::m_p_root = join(base_type::m_p_root, other.m_p_root);
  base_type::m_size += other.m_size;
  m_p_max = NULL;

  other.m_p_root = NULL;
  other.m_size = 0;
  other.m_p_max = NULL;

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

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
join(node_pointer p_lhs, node_pointer p_rhs) const
{
  node_pointer p_ret = NULL;

  node_pointer p_cur = NULL;

  while (p_lhs != NULL || p_rhs != NULL)
    {
      if (p_rhs == NULL)
        {
	  if (p_cur == NULL)
	    p_ret = p_cur = p_lhs;
	  else
            {
	      p_cur->m_p_next_sibling = p_lhs;

	      p_lhs->m_p_prev_or_parent = p_cur;
            }

	  p_cur = p_lhs = NULL;
        }
      else if (p_lhs == NULL || p_rhs->m_metadata < p_lhs->m_metadata)
        {
	  if (p_cur == NULL)
            {
	      p_ret = p_cur = p_rhs;

	      p_rhs = p_rhs->m_p_prev_or_parent;
            }
	  else
            {
	      p_cur->m_p_next_sibling = p_rhs;

	      p_rhs = p_rhs->m_p_prev_or_parent;

	      p_cur->m_p_next_sibling->m_p_prev_or_parent = p_cur;

	      p_cur = p_cur->m_p_next_sibling;
            }
        }
      else if (p_lhs->m_metadata < p_rhs->m_metadata)
        {
	  if (p_cur == NULL)
	    p_ret = p_cur = p_lhs;
	  else
            {
	      p_cur->m_p_next_sibling = p_lhs;

	      p_lhs->m_p_prev_or_parent = p_cur;

	      p_cur = p_cur->m_p_next_sibling;
            }

	  p_lhs = p_cur->m_p_next_sibling;
        }
      else
        {
	  node_pointer p_next_rhs = p_rhs->m_p_prev_or_parent;

	  p_rhs->m_p_next_sibling = p_lhs;

	  p_lhs = fix(p_rhs);

	  p_rhs = p_next_rhs;
        }
    }

  if (p_cur != NULL)
    p_cur->m_p_next_sibling = NULL;

  if (p_ret != NULL)
    p_ret->m_p_prev_or_parent = NULL;

  return p_ret;
}