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 node.hpp
 * Contains an implementation for rb_tree_.
 */

#ifndef PB_DS_RB_TREE_NODE_HPP
#define PB_DS_RB_TREE_NODE_HPP

#include <ext/pb_ds/detail/basic_tree_policy/null_node_metadata.hpp>

namespace pb_ds
{
  namespace detail
  {
    template<typename Value_Type, class Metadata, class Allocator>
    struct rb_tree_node_
    {
    public:
      typedef Value_Type value_type;
      typedef Metadata metadata_type;

      typedef
      typename Allocator::template rebind<
      rb_tree_node_<
      Value_Type,
      Metadata,
      Allocator> >::other::pointer
      node_pointer;

      typedef
      typename Allocator::template rebind<
	metadata_type>::other::reference
      metadata_reference;

      typedef
      typename Allocator::template rebind<
	metadata_type>::other::const_reference
      const_metadata_reference;

      inline bool
      special() const
      { return m_red; }

      inline const_metadata_reference
      get_metadata() const
      { return m_metadata; }

      inline metadata_reference
      get_metadata()
      { return m_metadata; }

#ifdef PB_DS_BIN_SEARCH_TREE_TRACE_
      void
      trace() const
      {
	std::cout << PB_DS_V2F(m_value) <<(m_red? " <r> " : " <b> ")
		  << "(" << m_metadata << ")";
      }
#endif

      node_pointer m_p_left;
      node_pointer m_p_right;
      node_pointer m_p_parent;
      value_type m_value;
      bool m_red;
      metadata_type m_metadata;
    };

    template<typename Value_Type, class Allocator>
    struct rb_tree_node_<Value_Type, null_node_metadata, Allocator>
    {
    public:
      typedef Value_Type value_type;
      typedef null_node_metadata metadata_type;

      typedef
      typename Allocator::template rebind<
      rb_tree_node_<
      Value_Type,
      null_node_metadata,
      Allocator> >::other::pointer
      node_pointer;

      inline bool
      special() const
      { return m_red; }

#ifdef PB_DS_BIN_SEARCH_TREE_TRACE_
      void
      trace() const
      { std::cout << PB_DS_V2F(m_value) <<(m_red? " <r> " : " <b> "); }
#endif

      node_pointer m_p_left;
      node_pointer m_p_right;
      node_pointer m_p_parent;
      value_type m_value;
      bool m_red;
    };
  } // 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 rb_tree_.hpp
 * Contains an implementation for rb_tree_.
 */
/*
 * This implementation uses an idea from the SGI STL (using a "header" node
 *    which is needed for efficient iteration).
 */

#ifdef PB_DS_DATA_TRUE_INDICATOR
#ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
#define PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
#endif
#endif

#ifdef PB_DS_DATA_FALSE_INDICATOR
#ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
#define PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
#endif
#endif

#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/detail/basic_types.hpp>
#include <utility>
#include <vector>
#include <assert.h>
#include <debug/debug.h>

namespace pb_ds
{
  namespace detail
  {
#define PB_DS_CLASS_T_DEC \
    template<typename Key, typename Mapped, typename Cmp_Fn, \
	     typename Node_And_It_Traits, typename Allocator>

#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_CLASS_NAME rb_tree_data_
#endif

#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_BASE_CLASS_NAME bin_search_tree_data_
#endif

#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_CLASS_NAME rb_tree_no_data_
#endif

#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_BASE_CLASS_NAME bin_search_tree_no_data_
#endif

#define PB_DS_CLASS_C_DEC \
    PB_DS_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator>

#define PB_DS_BASE_C_DEC \
    PB_DS_BASE_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator>

#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_V2F(X) (X).first
#define PB_DS_V2S(X) (X).second
#define PB_DS_EP2VP(X)& ((X)->m_value)
#endif

#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_V2F(X) (X)
#define PB_DS_V2S(X) Mapped_Data()
#define PB_DS_EP2VP(X)& ((X)->m_value.first)
#endif

    template<typename Key,
	     typename Mapped,
	     typename Cmp_Fn,
	     typename Node_And_It_Traits,
	     typename Allocator>
    class PB_DS_CLASS_NAME : public PB_DS_BASE_C_DEC
    {
    private:
      typedef PB_DS_BASE_C_DEC base_type;
      typedef typename base_type::node_pointer node_pointer;

    public:
      typedef Cmp_Fn cmp_fn;
      typedef Allocator allocator;
      typedef typename Allocator::size_type size_type;
      typedef typename Allocator::difference_type difference_type;
      typedef typename base_type::key_type key_type;
      typedef typename base_type::key_pointer key_pointer;
      typedef typename base_type::const_key_pointer const_key_pointer;
      typedef typename base_type::key_reference key_reference;
      typedef typename base_type::const_key_reference const_key_reference;
      typedef typename base_type::mapped_type mapped_type;
      typedef typename base_type::mapped_pointer mapped_pointer;
      typedef typename base_type::const_mapped_pointer const_mapped_pointer;
      typedef typename base_type::mapped_reference mapped_reference;
      typedef typename base_type::const_mapped_reference const_mapped_reference;
      typedef typename base_type::value_type value_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::point_iterator point_iterator;
      typedef typename base_type::const_iterator const_point_iterator;
      typedef typename base_type::iterator iterator;
      typedef typename base_type::const_iterator const_iterator;
      typedef typename base_type::reverse_iterator reverse_iterator;
      typedef typename base_type::const_reverse_iterator const_reverse_iterator;
      typedef typename base_type::node_update node_update;

      PB_DS_CLASS_NAME();

      PB_DS_CLASS_NAME(const Cmp_Fn&);

      PB_DS_CLASS_NAME(const Cmp_Fn&, const node_update&);

      PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);

      void
      swap(PB_DS_CLASS_C_DEC&);

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

      inline std::pair<point_iterator, bool>
      insert(const_reference);

      inline mapped_reference
      operator[](const_key_reference r_key)
      {
#ifdef PB_DS_DATA_TRUE_INDICATOR
	_GLIBCXX_DEBUG_ONLY(assert_valid();)
	std::pair<point_iterator, bool> ins_pair =
	base_type::insert_leaf(value_type(r_key, mapped_type()));

	if (ins_pair.second == true)
	  {
	    ins_pair.first.m_p_nd->m_red = true;
	    _GLIBCXX_DEBUG_ONLY(this->structure_only_assert_valid();)
	    insert_fixup(ins_pair.first.m_p_nd);
	  }
	_GLIBCXX_DEBUG_ONLY(assert_valid();)
	return ins_pair.first.m_p_nd->m_value.second;
#else
	insert(r_key);
	return base_type::s_null_mapped;
#endif
      }

      inline bool
      erase(const_key_reference);

      inline iterator
      erase(iterator);

      inline reverse_iterator
      erase(reverse_iterator);

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

      void
      join(PB_DS_CLASS_C_DEC&);

      void
      split(const_key_reference, PB_DS_CLASS_C_DEC&);

    protected:

    private:

#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;

      size_type
      assert_node_consistent(const node_pointer) const;
#endif

      inline static bool
      is_effectively_black(const node_pointer);

      void
      initialize();

      void
      insert_fixup(node_pointer);

      void
      erase_node(node_pointer);

      void
      remove_node(node_pointer);

      void
      remove_fixup(node_pointer, node_pointer);

      void
      split_imp(node_pointer, PB_DS_CLASS_C_DEC&);

      inline node_pointer
      split_min();

      std::pair<node_pointer, node_pointer>
      split_min_imp();

      void
      join_imp(node_pointer, node_pointer);

      std::pair<node_pointer, node_pointer>
      find_join_pos_right(node_pointer, size_type, size_type);

      std::pair<node_pointer, node_pointer>
      find_join_pos_left(node_pointer, size_type, size_type);

      inline size_type
      black_height(node_pointer);

      void
      split_at_node(node_pointer, PB_DS_CLASS_C_DEC&);
    };

#include <ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp>
#include <ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_CLASS_NAME
#undef PB_DS_BASE_CLASS_NAME
#undef PB_DS_BASE_C_DEC
#undef PB_DS_V2F
#undef PB_DS_EP2VP
#undef PB_DS_V2S

  } // namespace detail
} // namespace pb_ds

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 split_join_fn_imps.hpp
 * Contains an implementation for rb_tree_.
 */

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();)
  _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();)
  if (base_type::join_prep(other) == false)
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
      return;
    }

  const node_pointer p_x = other.split_min();
  join_imp(p_x, other.m_p_head->m_p_parent);
  base_type::join_finish(other);
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();)
  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
  _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();)
 }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
join_imp(node_pointer p_x, node_pointer p_r)
{
  _GLIBCXX_DEBUG_ASSERT(p_x != NULL);
  if (p_r != NULL)
    p_r->m_red = false;

  const size_type h = black_height(base_type::m_p_head->m_p_parent);
  const size_type other_h = black_height(p_r);
  node_pointer p_x_l;
  node_pointer p_x_r;
  std::pair<node_pointer, node_pointer> join_pos;
  const bool right_join = h >= other_h;
  if (right_join)
    {
      join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent,
				     h, other_h);
      p_x_l = join_pos.first;
      p_x_r = p_r;
    }
  else
    {
      p_x_l = base_type::m_p_head->m_p_parent;
      base_type::m_p_head->m_p_parent = p_r;
      if (p_r != NULL)
	p_r->m_p_parent = base_type::m_p_head;

      join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent,
				    h, other_h);
      p_x_r = join_pos.first;
    }

  node_pointer p_parent = join_pos.second;
  if (p_parent == base_type::m_p_head)
    {
      base_type::m_p_head->m_p_parent = p_x;
      p_x->m_p_parent = base_type::m_p_head;
    }
  else
    {
      p_x->m_p_parent = p_parent;
      if (right_join)
	p_x->m_p_parent->m_p_right = p_x;
      else
	p_x->m_p_parent->m_p_left = p_x;
    }

  p_x->m_p_left = p_x_l;
  if (p_x_l != NULL)
    p_x_l->m_p_parent = p_x;

  p_x->m_p_right = p_x_r;
  if (p_x_r != NULL)
    p_x_r->m_p_parent = p_x;

  p_x->m_red = true;

  base_type::initialize_min_max();
  _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
  base_type::update_to_top(p_x, (node_update* )this);
  insert_fixup(p_x);
  _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid());
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
split_min()
{
  node_pointer p_min = base_type::m_p_head->m_p_left;

#ifdef _GLIBCXX_DEBUG
  const node_pointer p_head = base_type::m_p_head;
  _GLIBCXX_DEBUG_ASSERT(p_min != p_head);
#endif

  remove_node(p_min);
  return p_min;
}

PB_DS_CLASS_T_DEC
std::pair<
  typename PB_DS_CLASS_C_DEC::node_pointer,
  typename PB_DS_CLASS_C_DEC::node_pointer>
PB_DS_CLASS_C_DEC::
find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r)
{
  _GLIBCXX_DEBUG_ASSERT(h_l >= h_r);

  if (base_type::m_p_head->m_p_parent == NULL)
    return (std::make_pair((node_pointer)NULL, base_type::m_p_head));

  node_pointer p_l_parent = base_type::m_p_head;
  while (h_l > h_r)
    {
      if (p_l->m_red == false)
        {
	  _GLIBCXX_DEBUG_ASSERT(h_l > 0);
	  --h_l;
        }

      p_l_parent = p_l;
      p_l = p_l->m_p_right;
    }

  if (!is_effectively_black(p_l))
    {
      p_l_parent = p_l;
      p_l = p_l->m_p_right;
    }

  _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_l));
  _GLIBCXX_DEBUG_ASSERT(black_height(p_l) == h_r);
  _GLIBCXX_DEBUG_ASSERT(p_l == NULL || p_l->m_p_parent == p_l_parent);
  return std::make_pair(p_l, p_l_parent);
}

PB_DS_CLASS_T_DEC
std::pair<
  typename PB_DS_CLASS_C_DEC::node_pointer,
  typename PB_DS_CLASS_C_DEC::node_pointer>
PB_DS_CLASS_C_DEC::
find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r)
{
  _GLIBCXX_DEBUG_ASSERT(h_r > h_l);
  if (base_type::m_p_head->m_p_parent == NULL)
    return (std::make_pair((node_pointer)NULL,
			   base_type::m_p_head));
  node_pointer p_r_parent = base_type::m_p_head;
  while (h_r > h_l)
    {
      if (p_r->m_red == false)
        {
	  _GLIBCXX_DEBUG_ASSERT(h_r > 0);
	  --h_r;
        }

      p_r_parent = p_r;
      p_r = p_r->m_p_left;
    }

  if (!is_effectively_black(p_r))
    {
      p_r_parent = p_r;
      p_r = p_r->m_p_left;
    }

  _GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_r));
  _GLIBCXX_DEBUG_ASSERT(black_height(p_r) == h_l);
  _GLIBCXX_DEBUG_ASSERT(p_r == NULL || p_r->m_p_parent == p_r_parent);
  return std::make_pair(p_r, p_r_parent);
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
black_height(node_pointer p_nd)
{
  size_type h = 1;
  while (p_nd != NULL)
    {
      if (p_nd->m_red == false)
	++h;
      p_nd = p_nd->m_p_left;
    }
  return h;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid());
  _GLIBCXX_DEBUG_ONLY(base_type::assert_valid();)

    _GLIBCXX_DEBUG_ONLY(other.assert_valid());
  _GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();)

    if (base_type::split_prep(r_key, other) == false)
      {
        _GLIBCXX_DEBUG_ONLY(assert_valid());
        _GLIBCXX_DEBUG_ONLY(other.assert_valid());
        return;
      }

  _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
  _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();)
  node_pointer p_nd = upper_bound(r_key).m_p_nd;
  do
    {
      node_pointer p_next_nd = p_nd->m_p_parent;
      if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
	split_at_node(p_nd, other);

      _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
      _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();)
      p_nd = p_next_nd;
    }
  while (p_nd != base_type::m_p_head);

  base_type::split_finish(other);
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other)
{
  _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);

  node_pointer p_l = p_nd->m_p_left;
  node_pointer p_r = p_nd->m_p_right;
  node_pointer p_parent = p_nd->m_p_parent;
  if (p_parent == base_type::m_p_head)
    {
      base_type::m_p_head->m_p_parent = p_l;
      if (p_l != NULL)
        {
	  p_l->m_p_parent = base_type::m_p_head;
	  p_l->m_red = false;
        }
    }
  else
    {
      if (p_parent->m_p_left == p_nd)
	p_parent->m_p_left = p_l;
      else
	p_parent->m_p_right = p_l;

      if (p_l != NULL)
	p_l->m_p_parent = p_parent;

      update_to_top(p_parent, (node_update* )this);

      if (!p_nd->m_red)
	remove_fixup(p_l, p_parent);
    }

  base_type::initialize_min_max();
  other.join_imp(p_nd, p_r);
  _GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid());
  _GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_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 traits.hpp
 * Contains an implementation for rb_tree_.
 */

#ifndef PB_DS_RB_TREE_NODE_AND_IT_TRAITS_HPP
#define PB_DS_RB_TREE_NODE_AND_IT_TRAITS_HPP

#include <ext/pb_ds/detail/rb_tree_map_/node.hpp>

namespace pb_ds
{
  namespace detail
  {
    template<typename Key,
	     typename Mapped,
	     typename Cmp_Fn,
	     template<typename Const_Node_Iterator,
		      class Node_Iterator,
		      class Cmp_Fn_,
		      class Allocator_>
    class Node_Update,
	     typename Allocator>
    struct tree_traits<
      Key,
      Mapped,
      Cmp_Fn,
      Node_Update,
      rb_tree_tag,
      Allocator> : public bin_search_tree_traits<
      Key,
      Mapped,
      Cmp_Fn,
      Node_Update,
      rb_tree_node_<
      typename types_traits<
      Key,
      Mapped,
      Allocator,
      false>::value_type,
      typename tree_node_metadata_selector<
      Key,
      Mapped,
      Cmp_Fn,
      Node_Update,
      Allocator>::type,
      Allocator>,
      Allocator>
    { };

    template<typename Key,
	     class Cmp_Fn,
	     template<typename Const_Node_Iterator,
		      class Node_Iterator,
		      class Cmp_Fn_,
		      class Allocator_>
    class Node_Update,
	     class Allocator>
    struct tree_traits<
      Key,
      null_mapped_type,
      Cmp_Fn,
      Node_Update,
      rb_tree_tag,
      Allocator> : public bin_search_tree_traits<
      Key,
      null_mapped_type,
      Cmp_Fn,
      Node_Update,
      rb_tree_node_<
      typename types_traits<
      Key,
      null_mapped_type,
      Allocator,
      false>::value_type,
      typename tree_node_metadata_selector<
      Key,
      null_mapped_type,
      Cmp_Fn,
      Node_Update,
      Allocator>::type,
      Allocator>,
      Allocator>
    { };

  } // 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 for rc_binomial_heap_.
 */

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

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
rc_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::
rc_binomial_heap_(const PB_DS_CLASS_C_DEC& other) :
  PB_DS_BASE_C_DEC(other)
{
  make_binomial_heap();

  base_type::find_max();

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~rc_binomial_heap_()
{ }

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

    base_type::swap(other);

  m_rc.swap(other.m_rc);

  _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 debug_fn_imps.hpp
 * Contains an implementation for rc_binomial_heap_.
 */

#ifdef _GLIBCXX_DEBUG

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid() const
{
  base_type::assert_valid(false);
  if (!base_type::empty())
    {
      _GLIBCXX_DEBUG_ASSERT(base_type::m_p_max != NULL);
      base_type::assert_max();
    }

  m_rc.assert_valid();

  if (m_rc.empty())
    {
      base_type::assert_valid(true);
      _GLIBCXX_DEBUG_ASSERT(next_2_pointer(base_type::m_p_root) == NULL);
      return;
    }

  const_node_pointer p_nd = next_2_pointer(base_type::m_p_root);
  typename rc_t::const_iterator it = m_rc.end();
  --it;

  while (p_nd != NULL)
    {
      _GLIBCXX_DEBUG_ASSERT(*it == p_nd);
      const_node_pointer p_next = p_nd->m_p_next_sibling;
      _GLIBCXX_DEBUG_ASSERT(p_next != NULL);
      _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_next->m_metadata);
      _GLIBCXX_DEBUG_ASSERT(p_next->m_p_next_sibling == NULL ||
		       p_next->m_metadata < p_next->m_p_next_sibling->m_metadata);

      --it;
      p_nd = next_2_pointer(next_after_0_pointer(p_nd));
    }
  _GLIBCXX_DEBUG_ASSERT(it + 1 == m_rc.begin());
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::const_node_pointer
PB_DS_CLASS_C_DEC::
next_2_pointer(const_node_pointer p_nd)
{
  if (p_nd == NULL)
    return NULL;

  node_pointer p_next = p_nd->m_p_next_sibling;

  if (p_next == NULL)
    return NULL;

  if (p_nd->m_metadata == p_next->m_metadata)
    return p_nd;

  return next_2_pointer(p_next);
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::const_node_pointer
PB_DS_CLASS_C_DEC::
next_after_0_pointer(const_node_pointer p_nd)
{
  if (p_nd == NULL)
    return NULL;

  node_pointer p_next = p_nd->m_p_next_sibling;

  if (p_next == NULL)
    return NULL;

  if (p_nd->m_metadata < p_next->m_metadata)
    return p_next;

  return next_after_0_pointer(p_next);
}

#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 for rc_binomial_heap_.
 */

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
pop()
{
  make_binomial_heap();
  _GLIBCXX_DEBUG_ASSERT(!base_type::empty());
  base_type::pop();
  base_type::find_max();
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
clear()
{
  base_type::clear();
  m_rc.clear();
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
make_binomial_heap()
{
  node_pointer p_nd = base_type::m_p_root;
  while (p_nd != NULL)
    {
      node_pointer p_next = p_nd->m_p_next_sibling;
      if (p_next == NULL)
	p_nd = p_next;
      else if (p_nd->m_metadata == p_next->m_metadata)
	p_nd = link_with_next_sibling(p_nd);
      else if (p_nd->m_metadata < p_next->m_metadata)
	p_nd = p_next;
#ifdef _GLIBCXX_DEBUG
      else
	_GLIBCXX_DEBUG_ASSERT(0);
#endif
    }

  m_rc.clear();
}

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)
{
  make_binomial_heap();
  const size_type ersd = base_type::erase_if(pred);
  base_type::find_max();
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  return ersd;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
erase(point_iterator it)
{
  make_binomial_heap();
  base_type::erase(it);
  base_type::find_max();
}


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 for rc_binomial_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();)

    make_0_exposed();

  _GLIBCXX_DEBUG_ONLY(assert_valid();)

    node_pointer p_nd = base_type::get_new_node_for_insert(r_val);

  p_nd->m_p_l_child = p_nd->m_p_prev_or_parent = NULL;
  p_nd->m_metadata = 0;

  if (base_type::m_p_max == NULL || Cmp_Fn::operator()(base_type::m_p_max->m_value, r_val))
    base_type::m_p_max = p_nd;

  p_nd->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_nd;

  base_type::m_p_root = p_nd;

  if (p_nd->m_p_next_sibling != NULL&&  p_nd->m_p_next_sibling->m_metadata == 0)
    m_rc.push(p_nd);

  _GLIBCXX_DEBUG_ONLY(assert_valid();)

    return point_iterator(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();)

    make_binomial_heap();

  base_type::modify(it, r_new_val);

  base_type::find_max();

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
link_with_next_sibling(node_pointer p_nd)
{
  node_pointer p_next = p_nd->m_p_next_sibling;

  _GLIBCXX_DEBUG_ASSERT(p_next != NULL);
  _GLIBCXX_DEBUG_ASSERT(p_next->m_p_prev_or_parent == p_nd);

  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_next->m_p_prev_or_parent == NULL)
	base_type::m_p_root = p_next;
      else
	p_next->m_p_prev_or_parent->m_p_next_sibling = p_next;

      if (base_type::m_p_max == p_nd)
	base_type::m_p_max = p_next;

      base_type::make_child_of(p_nd, p_next);

      ++p_next->m_metadata;

      return p_next;
    }

  p_nd->m_p_next_sibling = p_next->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;

  if (base_type::m_p_max == p_next)
    base_type::m_p_max = p_nd;

  base_type::make_child_of(p_next, p_nd);

  ++p_nd->m_metadata;

  return p_nd;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
make_0_exposed()
{
  if (m_rc.empty())
    return;

  node_pointer p_nd = m_rc.top();

  m_rc.pop();

  _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_next_sibling != NULL);
  _GLIBCXX_DEBUG_ASSERT(p_nd->m_metadata == p_nd->m_p_next_sibling->m_metadata);

  node_pointer p_res = link_with_next_sibling(p_nd);

  if (p_res->m_p_next_sibling != NULL&&  p_res->m_metadata == p_res->m_p_next_sibling->m_metadata)
    m_rc.push(p_res);
}


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 rc.hpp
 * Contains a redundant (binary counter).
 */

#ifndef PB_DS_RC_HPP
#define PB_DS_RC_HPP

namespace pb_ds
{
  namespace detail
  {

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

#define PB_DS_CLASS_C_DEC \
    rc<Node, Allocator>

    template<typename Node, class Allocator>
    class rc
    {
    private:
      typedef Allocator allocator;

      typedef typename allocator::size_type size_type;

      typedef Node node;

      typedef
      typename allocator::template rebind<
	node>::other::pointer
      node_pointer;

      typedef
      typename allocator::template rebind<
	node_pointer>::other::pointer
      entry_pointer;

      typedef
      typename allocator::template rebind<
	node_pointer>::other::const_pointer
      const_entry_pointer;

      enum
	{
	  max_entries = sizeof(size_type) << 3
	};

    public:
      typedef node_pointer entry;

      typedef const_entry_pointer const_iterator;

    public:
      rc();

      rc(const PB_DS_CLASS_C_DEC& other);

      inline void
      swap(PB_DS_CLASS_C_DEC& other);

      inline void
      push(entry p_nd);

      inline node_pointer
      top() const;

      inline void
      pop();

      inline bool
      empty() const;

      inline size_type
      size() const;

      void
      clear();

      const const_iterator
      begin() const;

      const const_iterator
      end() const;

#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;
#endif

#ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_
      void
      trace() const;
#endif

    private:
      node_pointer m_a_entries[max_entries];

      size_type m_over_top;
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    rc() : m_over_top(0)
    { _GLIBCXX_DEBUG_ONLY(assert_valid();) }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    rc(const PB_DS_CLASS_C_DEC& other) : m_over_top(0)
    { _GLIBCXX_DEBUG_ONLY(assert_valid();) }

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

      const size_type over_top = std::max(m_over_top, other.m_over_top);

      for (size_type i = 0; i < over_top; ++i)
	std::swap(m_a_entries[i], other.m_a_entries[i]);

      std::swap(m_over_top, other.m_over_top);
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
     }

    PB_DS_CLASS_T_DEC
    inline void
    PB_DS_CLASS_C_DEC::
    push(entry p_nd)
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      _GLIBCXX_DEBUG_ASSERT(m_over_top < max_entries);
      m_a_entries[m_over_top++] = p_nd;
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

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

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::node_pointer
    PB_DS_CLASS_C_DEC::
    top() const
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      _GLIBCXX_DEBUG_ASSERT(!empty());
      return *(m_a_entries + m_over_top - 1);
    }

    PB_DS_CLASS_T_DEC
    inline bool
    PB_DS_CLASS_C_DEC::
    empty() const
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      return m_over_top == 0;
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    size() const
    { return m_over_top; }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    clear()
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      m_over_top = 0;
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

    PB_DS_CLASS_T_DEC
    const typename PB_DS_CLASS_C_DEC::const_iterator
    PB_DS_CLASS_C_DEC::
    begin() const
    { return& m_a_entries[0]; }

    PB_DS_CLASS_T_DEC
    const typename PB_DS_CLASS_C_DEC::const_iterator
    PB_DS_CLASS_C_DEC::
    end() const
    { return& m_a_entries[m_over_top]; }

#ifdef _GLIBCXX_DEBUG
    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    assert_valid() const
    { _GLIBCXX_DEBUG_ASSERT(m_over_top < max_entries); }
#endif

#ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_
    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    trace() const
    {
      std::cout << "rc" << std::endl;
      for (size_type i = 0; i < m_over_top; ++i)
	std::cerr << m_a_entries[i] << std::endl;
      std::cout << 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 rc_binomial_heap_.hpp
 * Contains an implementation for rc_binomial_heap_.
 */

/*
 * Redundant-counter binomial heap.
 */

#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>
#include <ext/pb_ds/detail/rc_binomial_heap_/rc.hpp>
#include <debug/debug.h>

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

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

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

#define PB_DS_RC_C_DEC \
    rc<typename PB_DS_BASE_C_DEC::node, Allocator>

    /**
     * class description = "8y|\|0|\/|i41 h34p 74813">
     **/
    template<typename Value_Type, class Cmp_Fn, class Allocator>
    class rc_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;

      typedef PB_DS_RC_C_DEC rc_t;

    public:

      typedef typename Allocator::size_type size_type;

      typedef typename Allocator::difference_type difference_type;

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

    public:

      rc_binomial_heap_();

      rc_binomial_heap_(const Cmp_Fn& r_cmp_fn);

      rc_binomial_heap_(const PB_DS_CLASS_C_DEC& other);

      ~rc_binomial_heap_();

      void
      swap(PB_DS_CLASS_C_DEC& other);

      inline point_iterator
      push(const_reference r_val);

      void
      modify(point_iterator it, const_reference r_new_val);

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

#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;
#endif

#ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_
      void
      trace() const;
#endif

    private:

      inline node_pointer
      link_with_next_sibling(node_pointer p_nd);

      void
      make_0_exposed();

      void
      make_binomial_heap();

#ifdef _GLIBCXX_DEBUG
      static const_node_pointer
      next_2_pointer(const_node_pointer p_nd);

      static const_node_pointer
      next_after_0_pointer(const_node_pointer p_nd);
#endif

    private:
      rc_t m_rc;
    };

#include <ext/pb_ds/detail/rc_binomial_heap_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/rc_binomial_heap_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/rc_binomial_heap_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/rc_binomial_heap_/trace_fn_imps.hpp>
#include <ext/pb_ds/detail/rc_binomial_heap_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/rc_binomial_heap_/split_join_fn_imps.hpp>

#undef PB_DS_CLASS_C_DEC

#undef PB_DS_CLASS_T_DEC

#undef PB_DS_BASE_C_DEC

#undef PB_DS_RC_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 split_join_fn_imps.hpp
 * Contains an implementation for rc_binomial_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();)
    _GLIBCXX_DEBUG_ONLY(other.assert_valid();)

    make_binomial_heap();
  other.make_binomial_heap();

  base_type::split(pred, other);

  base_type::find_max();
  other.find_max();

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

    make_binomial_heap();
  other.make_binomial_heap();

  base_type::join(other);

  base_type::find_max();
  other.find_max();

  _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 for rc_binomial_heap_.
 */

#ifdef PB_DS_RC_BINOMIAL_HEAP_TRACE_

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
trace() const
{
  base_type::trace();

  m_rc.trace();
}

#endif // #ifdef PB_DS_RC_BINOMIAL_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 cc_hash_max_collision_check_resize_trigger_imp.hpp
 * Contains a resize trigger implementation.
 */

#define PB_DS_STATIC_ASSERT(UNIQUE, E) \
  typedef detail::static_assert_dumclass<sizeof(detail::static_assert<(bool)(E)>)> UNIQUE##static_assert_type

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
cc_hash_max_collision_check_resize_trigger(float load) :
  m_load(load),
  m_size(0),
  m_num_col(0),
  m_max_col(0),
  m_resize_needed(false)
{ }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_find_search_start()
{ }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_find_search_collision()
{ }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_find_search_end()
{ }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_insert_search_start()
{ m_num_col = 0; }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_insert_search_collision()
{ ++m_num_col; }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_insert_search_end()
{ calc_resize_needed(); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_erase_search_start()
{ }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_erase_search_collision()
{ }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_erase_search_end()
{ }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_inserted(size_type)
{ }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_erased(size_type)
{ m_resize_needed = true; }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_cleared()
{ m_resize_needed = false; }

PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
is_resize_needed() const
{ return m_resize_needed; }

PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
is_grow_needed(size_type /*size*/, size_type /*num_used_e*/) const
{ return m_num_col >= m_max_col; }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_resized(size_type new_size)
{
  m_size = new_size;

#ifdef PB_DS_HT_MAP_RESIZE_TRACE_
  std::cerr << "chmccrt::notify_resized "
	    << static_cast<unsigned long>(new_size) << std::endl;
#endif

  calc_max_num_coll();
  calc_resize_needed();
  m_num_col = 0;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
calc_max_num_coll()
{
  // max_col <-- \sqrt{2 load \ln( 2 m \ln( m ) ) }
  const double ln_arg = 2 * m_size * ::log(double(m_size));
  m_max_col = size_type(::ceil(::sqrt(2 * m_load * ::log(ln_arg))));

#ifdef PB_DS_HT_MAP_RESIZE_TRACE_
  std::cerr << "chmccrt::calc_max_num_coll "
	    << static_cast<unsigned long>(m_size) <<    "    "
	    << static_cast<unsigned long>(m_max_col) << std::endl;
#endif
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_externally_resized(size_type new_size)
{ notify_resized(new_size); }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
  std::swap(m_load, other.m_load);
  std::swap(m_size, other.m_size);
  std::swap(m_num_col, other.m_num_col);
  std::swap(m_max_col, other.m_max_col);
  std::swap(m_resize_needed, other.m_resize_needed);
}

PB_DS_CLASS_T_DEC
inline float
PB_DS_CLASS_C_DEC::
get_load() const
{
  PB_DS_STATIC_ASSERT(access, external_load_access);
  return m_load;
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
calc_resize_needed()
{ m_resize_needed = m_resize_needed || m_num_col >= m_max_col; }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
set_load(float load)
{
  PB_DS_STATIC_ASSERT(access, external_load_access);
  m_load = load;
  calc_max_num_coll();
  calc_resize_needed();
}

#undef PB_DS_STATIC_ASSERT


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 hash_exponential_size_policy_imp.hpp
 * Contains a resize size policy implementation.
 */

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
hash_exponential_size_policy(size_type start_size, size_type grow_factor) :
  m_start_size(start_size),
  m_grow_factor(grow_factor)
{ }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
  std::swap(m_start_size, other.m_start_size);
  std::swap(m_grow_factor, other.m_grow_factor);
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
get_nearest_larger_size(size_type size) const
{
  size_type ret = m_start_size;
  while (ret <= size)
    {
      const size_type next_ret = ret*  m_grow_factor;
      if (next_ret < ret)
	__throw_insert_error();
      ret = next_ret;
    }
  return ret;
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
get_nearest_smaller_size(size_type size) const
{
  size_type ret = m_start_size;
  while (true)
    {
      const size_type next_ret = ret*  m_grow_factor;
      if (next_ret < ret)
	__throw_resize_error();
      if (next_ret >= size)
	return (ret);
      ret = next_ret;
    }
  return ret;
}


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 hash_load_check_resize_trigger_imp.hpp
 * Contains a resize trigger implementation.
 */

#define PB_DS_STATIC_ASSERT(UNIQUE, E)  \
  typedef detail::static_assert_dumclass<sizeof(detail::static_assert<bool(E)>)> UNIQUE##static_assert_type

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
hash_load_check_resize_trigger(float load_min, float load_max)
: m_load_min(load_min), m_load_max(load_max), m_next_shrink_size(0),
  m_next_grow_size(0), m_resize_needed(false)
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_find_search_start()
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_find_search_collision()
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_find_search_end()
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_insert_search_start()
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_insert_search_collision()
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_insert_search_end()
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_erase_search_start()
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_erase_search_collision()
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_erase_search_end()
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_inserted(size_type num_entries)
{
  m_resize_needed = (num_entries >= m_next_grow_size);
  size_base::set_size(num_entries);
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_erased(size_type num_entries)
{
  size_base::set_size(num_entries);
  m_resize_needed = num_entries <= m_next_shrink_size;
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
is_resize_needed() const
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  return m_resize_needed;
}

PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
is_grow_needed(size_type /*size*/, size_type num_entries) const
{
  _GLIBCXX_DEBUG_ASSERT(m_resize_needed);
  return num_entries >= m_next_grow_size;
}

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~hash_load_check_resize_trigger() { }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_resized(size_type new_size)
{
  m_resize_needed = false;
  m_next_grow_size = size_type(m_load_max * new_size - 1);
  m_next_shrink_size = size_type(m_load_min * new_size);

#ifdef PB_DS_HT_MAP_RESIZE_TRACE_
  std::cerr << "hlcrt::notify_resized " <<
    static_cast<unsigned long>(new_size) << "    " <<
    static_cast<unsigned long>(m_load_min) << "    " <<
    static_cast<unsigned long>(m_load_max) << "    " <<
    static_cast<unsigned long>(m_next_shrink_size) << " " <<
    static_cast<unsigned long>(m_next_grow_size) << "    " << std::endl;
#endif

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_externally_resized(size_type new_size)
{
  m_resize_needed = false;
  size_type new_grow_size = size_type(m_load_max * new_size - 1);
  size_type new_shrink_size = size_type(m_load_min * new_size );
  if (new_grow_size >= m_next_grow_size)
    {
      _GLIBCXX_DEBUG_ASSERT(new_shrink_size > m_next_shrink_size);
      m_next_grow_size = new_grow_size;
      _GLIBCXX_DEBUG_ONLY(assert_valid();)

#ifdef PB_DS_HT_MAP_RESIZE_TRACE_
	std::cerr << "hlcrt::notify_externally_resized1 " <<
        static_cast<unsigned long>(new_size) << "    " <<
        static_cast<unsigned long>(m_load_min) << "    " <<
        static_cast<unsigned long>(m_load_max) << "    " <<
        static_cast<unsigned long>(m_next_shrink_size) << " " <<
        static_cast<unsigned long>(m_next_grow_size) << "    " << std::endl;
#endif
      return;
    }

  _GLIBCXX_DEBUG_ASSERT(new_shrink_size <= m_next_shrink_size);
  m_next_shrink_size = new_shrink_size;

#ifdef PB_DS_HT_MAP_RESIZE_TRACE_
  std::cerr << "hlcrt::notify_externally_resized2 " <<
    static_cast<unsigned long>(new_size) << "    " <<
    static_cast<unsigned long>(m_load_min) << "    " <<
    static_cast<unsigned long>(m_load_max) << "    " <<
    static_cast<unsigned long>(m_next_shrink_size) << " " <<
    static_cast<unsigned long>(m_next_grow_size) << "    " << std::endl;
#endif

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_cleared()
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  size_base::set_size(0);
  m_resize_needed = (0 < m_next_shrink_size);
  _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();)

  size_base::swap(other);
  std::swap(m_load_min, other.m_load_min);
  std::swap(m_load_max, other.m_load_max);
  std::swap(m_resize_needed, other.m_resize_needed);
  std::swap(m_next_grow_size, other.m_next_grow_size);
  std::swap(m_next_shrink_size, other.m_next_shrink_size);

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

PB_DS_CLASS_T_DEC
inline std::pair<float, float>
PB_DS_CLASS_C_DEC::
get_loads() const
{
  PB_DS_STATIC_ASSERT(access, external_load_access);
  return std::make_pair(m_load_min, m_load_max);
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
set_loads(std::pair<float, float> load_pair)
{
  PB_DS_STATIC_ASSERT(access, external_load_access);
  const float old_load_min = m_load_min;
  const float old_load_max = m_load_max;
  const size_type old_next_shrink_size = m_next_shrink_size;
  const size_type old_next_grow_size = m_next_grow_size;
  const bool old_resize_needed = m_resize_needed;

  try
    {
      m_load_min = load_pair.first;
      m_load_max = load_pair.second;
      do_resize(static_cast<size_type>(size_base::get_size() / ((m_load_min + m_load_max) / 2)));
    }
  catch (...)
    {
      m_load_min = old_load_min;
      m_load_max = old_load_max;
      m_next_shrink_size = old_next_shrink_size;
      m_next_grow_size = old_next_grow_size;
      m_resize_needed = old_resize_needed;
      __throw_exception_again;
    }
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
do_resize(size_type)
{ abort(); }

#ifdef _GLIBCXX_DEBUG
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid() const
{
  _GLIBCXX_DEBUG_ASSERT(m_load_max > m_load_min);
  _GLIBCXX_DEBUG_ASSERT(m_next_grow_size >= m_next_shrink_size);
}
#endif

#undef PB_DS_STATIC_ASSERT


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 hash_load_check_resize_trigger_size_base.hpp
 * Contains an base holding size for some resize policies.
 */

#ifndef PB_DS_HASH_LOAD_CHECK_RESIZE_TRIGGER_SIZE_BASE_HPP
#define PB_DS_HASH_LOAD_CHECK_RESIZE_TRIGGER_SIZE_BASE_HPP

namespace pb_ds
{
  namespace detail
  {
    // Primary template.
    template<typename Size_Type, bool Hold_Size>
    class hash_load_check_resize_trigger_size_base;

    // Specializations.
    template<typename Size_Type>
    class hash_load_check_resize_trigger_size_base<Size_Type, true>
    {
    protected:
      typedef Size_Type size_type;

      hash_load_check_resize_trigger_size_base(): m_size(0)
      { }

      inline void
      swap(hash_load_check_resize_trigger_size_base& other)
      { std::swap(m_size, other.m_size); }

      inline void
      set_size(size_type size)
      { m_size = size; }

      inline size_type
      get_size() const
      { return m_size; }

    private:
      size_type m_size;
    };

    template<typename Size_Type>
    class hash_load_check_resize_trigger_size_base<Size_Type, false>
    {
    protected:
      typedef Size_Type size_type;

    protected:
      inline void
      swap(hash_load_check_resize_trigger_size_base& other) { }

      inline void
      set_size(size_type size) { }
    };
  } // 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, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301,
// 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 hash_prime_size_policy_imp.hpp
 * Contains a resize size policy implementation.
 */

namespace detail
{
  enum
    {
      num_distinct_sizes_32_bit = 30,
      num_distinct_sizes_64_bit = 62,
      num_distinct_sizes = sizeof(std::size_t) != 8 ?
            num_distinct_sizes_32_bit : num_distinct_sizes_64_bit,
    };

  // Originally taken from the SGI implementation; acknowledged in the docs.
  // Further modified (for 64 bits) from tr1's hashtable.
  static const std::size_t g_a_sizes[num_distinct_sizes_64_bit] =
    {
      /* 0     */              5ul,
      /* 1     */              11ul,
      /* 2     */              23ul,
      /* 3     */              47ul,
      /* 4     */              97ul,
      /* 5     */              199ul,
      /* 6     */              409ul,
      /* 7     */              823ul,
      /* 8     */              1741ul,
      /* 9     */              3469ul,
      /* 10    */              6949ul,
      /* 11    */              14033ul,
      /* 12    */              28411ul,
      /* 13    */              57557ul,
      /* 14    */              116731ul,
      /* 15    */              236897ul,
      /* 16    */              480881ul,
      /* 17    */              976369ul,
      /* 18    */              1982627ul,
      /* 19    */              4026031ul,
      /* 20    */              8175383ul,
      /* 21    */              16601593ul,
      /* 22    */              33712729ul,
      /* 23    */              68460391ul,
      /* 24    */              139022417ul,
      /* 25    */              282312799ul,
      /* 26    */              573292817ul,
      /* 27    */              1164186217ul,
      /* 28    */              2364114217ul,
      /* 29    */              4294967291ul,
      /* 30    */ (std::size_t)8589934583ull,
      /* 31    */ (std::size_t)17179869143ull,
      /* 32    */ (std::size_t)34359738337ull,
      /* 33    */ (std::size_t)68719476731ull,
      /* 34    */ (std::size_t)137438953447ull,
      /* 35    */ (std::size_t)274877906899ull,
      /* 36    */ (std::size_t)549755813881ull,
      /* 37    */ (std::size_t)1099511627689ull,
      /* 38    */ (std::size_t)2199023255531ull,
      /* 39    */ (std::size_t)4398046511093ull,
      /* 40    */ (std::size_t)8796093022151ull,
      /* 41    */ (std::size_t)17592186044399ull,
      /* 42    */ (std::size_t)35184372088777ull,
      /* 43    */ (std::size_t)70368744177643ull,
      /* 44    */ (std::size_t)140737488355213ull,
      /* 45    */ (std::size_t)281474976710597ull,
      /* 46    */ (std::size_t)562949953421231ull,
      /* 47    */ (std::size_t)1125899906842597ull,
      /* 48    */ (std::size_t)2251799813685119ull,
      /* 49    */ (std::size_t)4503599627370449ull,
      /* 50    */ (std::size_t)9007199254740881ull,
      /* 51    */ (std::size_t)18014398509481951ull,
      /* 52    */ (std::size_t)36028797018963913ull,
      /* 53    */ (std::size_t)72057594037927931ull,
      /* 54    */ (std::size_t)144115188075855859ull,
      /* 55    */ (std::size_t)288230376151711717ull,
      /* 56    */ (std::size_t)576460752303423433ull,
      /* 57    */ (std::size_t)1152921504606846883ull,
      /* 58    */ (std::size_t)2305843009213693951ull,
      /* 59    */ (std::size_t)4611686018427387847ull,
      /* 60    */ (std::size_t)9223372036854775783ull,
      /* 61    */ (std::size_t)18446744073709551557ull,
    };

} // namespace detail

PB_DS_CLASS_T_DEC
inline
PB_DS_CLASS_C_DEC::
hash_prime_size_policy(size_type n) : m_start_size(n)
{ m_start_size = get_nearest_larger_size(n); }

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

PB_DS_CLASS_T_DEC
inline PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
get_nearest_larger_size(size_type n) const
{
  const std::size_t* const p_upper = std::upper_bound(detail::g_a_sizes,
		     detail::g_a_sizes + detail::num_distinct_sizes, n);

  if (p_upper == detail::g_a_sizes + detail::num_distinct_sizes)
    __throw_resize_error();
  return *p_upper;
}

PB_DS_CLASS_T_DEC
inline PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
get_nearest_smaller_size(size_type n) const
{
  const size_t* p_lower = std::lower_bound(detail::g_a_sizes,
		       detail::g_a_sizes + detail::num_distinct_sizes, n);

  if (*p_lower >= n &&  p_lower != detail::g_a_sizes)
    --p_lower;
  if (*p_lower < m_start_size)
    return m_start_size;
  return *p_lower;
}


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 hash_standard_resize_policy_imp.hpp
 * Contains a resize policy implementation.
 */

#define PB_DS_STATIC_ASSERT(UNIQUE, E) \
  typedef detail::static_assert_dumclass<sizeof(detail::static_assert<(bool)(E)>)> UNIQUE##static_assert_type

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
hash_standard_resize_policy()
: m_size(Size_Policy::get_nearest_larger_size(1))
{ trigger_policy_base::notify_externally_resized(m_size); }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
hash_standard_resize_policy(const Size_Policy& r_size_policy)
: Size_Policy(r_size_policy), m_size(Size_Policy::get_nearest_larger_size(1))
{ trigger_policy_base::notify_externally_resized(m_size); }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
hash_standard_resize_policy(const Size_Policy& r_size_policy,
			    const Trigger_Policy& r_trigger_policy)
: Size_Policy(r_size_policy), Trigger_Policy(r_trigger_policy),
  m_size(Size_Policy::get_nearest_larger_size(1))
{ trigger_policy_base::notify_externally_resized(m_size); }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~hash_standard_resize_policy()
{ }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
  trigger_policy_base::swap(other);
  size_policy_base::swap(other);
  std::swap(m_size, other.m_size);
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_find_search_start()
{ trigger_policy_base::notify_find_search_start(); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_find_search_collision()
{ trigger_policy_base::notify_find_search_collision(); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_find_search_end()
{ trigger_policy_base::notify_find_search_end(); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_insert_search_start()
{ trigger_policy_base::notify_insert_search_start(); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_insert_search_collision()
{ trigger_policy_base::notify_insert_search_collision(); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_insert_search_end()
{ trigger_policy_base::notify_insert_search_end(); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_erase_search_start()
{ trigger_policy_base::notify_erase_search_start(); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_erase_search_collision()
{ trigger_policy_base::notify_erase_search_collision(); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_erase_search_end()
{ trigger_policy_base::notify_erase_search_end(); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_inserted(size_type num_e)
{ trigger_policy_base::notify_inserted(num_e); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
notify_erased(size_type num_e)
{ trigger_policy_base::notify_erased(num_e); }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_cleared()
{ trigger_policy_base::notify_cleared(); }

PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
is_resize_needed() const
{ return trigger_policy_base::is_resize_needed(); }

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
get_new_size(size_type size, size_type num_used_e) const
{
  if (trigger_policy_base::is_grow_needed(size, num_used_e))
    return size_policy_base::get_nearest_larger_size(size);
  return size_policy_base::get_nearest_smaller_size(size);
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_resized(size_type new_size)
{
  trigger_policy_base::notify_resized(new_size);
  m_size = new_size;
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
get_actual_size() const
{
  PB_DS_STATIC_ASSERT(access, external_size_access);
  return m_size;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
resize(size_type new_size)
{
  PB_DS_STATIC_ASSERT(access, external_size_access);
  size_type actual_size = size_policy_base::get_nearest_larger_size(1);
  while (actual_size < new_size)
    {
      const size_type pot = size_policy_base::get_nearest_larger_size(actual_size);

      if (pot == actual_size && pot < new_size)
	__throw_resize_error();
      actual_size = pot;
    }

  if (actual_size > 0)
    --actual_size;

  const size_type old_size = m_size;
  try
    {
      do_resize(actual_size - 1);
    }
  catch(insert_error& )
    {
      m_size = old_size;
      __throw_resize_error();
    }
  catch(...)
    {
      m_size = old_size;
      __throw_exception_again;
    }
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
do_resize(size_type)
{
  // Do nothing
}

PB_DS_CLASS_T_DEC
Trigger_Policy&
PB_DS_CLASS_C_DEC::
get_trigger_policy()
{ return *this; }

PB_DS_CLASS_T_DEC
const Trigger_Policy&
PB_DS_CLASS_C_DEC::
get_trigger_policy() const
{ return *this; }

PB_DS_CLASS_T_DEC
Size_Policy&
PB_DS_CLASS_C_DEC::
get_size_policy()
{ return *this; }

PB_DS_CLASS_T_DEC
const Size_Policy&
PB_DS_CLASS_C_DEC::
get_size_policy() const
{ return *this; }

#undef PB_DS_STATIC_ASSERT


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 sample_resize_policy.hpp
 * Contains a sample resize policy for hash tables.
 */

#ifndef PB_DS_SAMPLE_RESIZE_POLICY_HPP
#define PB_DS_SAMPLE_RESIZE_POLICY_HPP

// A sample resize policy.
class sample_resize_policy
{
public:

  // Size type.
  typedef size_t size_type;

  // Default constructor.
  sample_resize_policy();

  // Copy constructor.
  sample_range_hashing(const sample_resize_policy& other);

  // Swaps content.
  inline void
  swap(sample_resize_policy& other);

protected:

  // Notifies a search started.
  inline void
  notify_insert_search_start();

  // Notifies a search encountered a collision.
  inline void
  notify_insert_search_collision();

  // Notifies a search ended.
  inline void
  notify_insert_search_end();

  // Notifies a search started.
  inline void
  notify_find_search_start();

  // Notifies a search encountered a collision.
  inline void
  notify_find_search_collision();

  // Notifies a search ended.
  inline void
  notify_find_search_end();

  // Notifies a search started.
  inline void
  notify_erase_search_start();

  // Notifies a search encountered a collision.
  inline void
  notify_erase_search_collision();

  // Notifies a search ended.
  inline void
  notify_erase_search_end();

  // Notifies an element was inserted.
  inline void
  notify_inserted(size_type num_e);

  // Notifies an element was erased.
  inline void
  notify_erased(size_type num_e);

  // Notifies the table was cleared.
  void
  notify_cleared();

  // Notifies the table was resized to new_size.
  void
  notify_resized(size_type new_size);

  // Queries whether a resize is needed.
  inline bool
  is_resize_needed() const;

  // Queries what the new size should be.
  size_type
  get_new_size(size_type size, size_type num_used_e) const;
};

#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 sample_resize_trigger.hpp
 * Contains a sample resize trigger policy class.
 */

#ifndef PB_DS_SAMPLE_RESIZE_TRIGGER_HPP
#define PB_DS_SAMPLE_RESIZE_TRIGGER_HPP

// A sample resize trigger policy.
class sample_resize_trigger
{
public:

  // Size type.
  typedef size_t size_type;

  // Default constructor.
  sample_resize_trigger();

  // Copy constructor.
  sample_range_hashing(const sample_resize_trigger& other);

  // Swaps content.
  inline void
  swap(sample_resize_trigger& other);

protected:

  // Notifies a search started.
  inline void
  notify_insert_search_start();

  // Notifies a search encountered a collision.
  inline void
  notify_insert_search_collision();

  // Notifies a search ended.
  inline void
  notify_insert_search_end();

  // Notifies a search started.
  inline void
  notify_find_search_start();

  // Notifies a search encountered a collision.
  inline void
  notify_find_search_collision();

  // Notifies a search ended.
  inline void
  notify_find_search_end();

  // Notifies a search started.
  inline void
  notify_erase_search_start();

  // Notifies a search encountered a collision.
  inline void
  notify_erase_search_collision();

  // Notifies a search ended.
  inline void
  notify_erase_search_end();

  // Notifies an element was inserted. the total number of entries in
  // the table is num_entries.
  inline void
  notify_inserted(size_type num_entries);

  // Notifies an element was erased.
  inline void
  notify_erased(size_type num_entries);

  // Notifies the table was cleared.
  void
  notify_cleared();

  // Notifies the table was resized as a result of this object's
  // signifying that a resize is needed.
  void
  notify_resized(size_type new_size);

  // Notifies the table was resized externally.
  void
  notify_externally_resized(size_type new_size);

  // Queries whether a resize is needed.
  inline bool
  is_resize_needed() const;

  // Queries whether a grow is needed.
  inline bool
  is_grow_needed(size_type size, size_type num_entries) const;

private:

  // Resizes to new_size.
  virtual void
  do_resize(size_type new_size);
};

} // namespace pb_ds

#endif