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 iterator_fn_imps.hpp
 * Contains implementations of gp_ht_map_'s iterators related functions, e.g.,
 *    begin().
 */

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::s_end_it;

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::const_iterator
PB_DS_CLASS_C_DEC::s_const_end_it;

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::
begin()
{
  pointer_ p_value;
  size_type pos;
  get_start_it_state(p_value, pos);
  return iterator(p_value, pos, this);
}

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

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_iterator
PB_DS_CLASS_C_DEC::
begin() const
{
  const_pointer_ p_value;
  size_type pos;
  get_start_it_state(p_value, pos);
  return const_iterator(p_value, pos, this);
}

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


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

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

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

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

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

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

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

/**
 * @file policy_access_fn_imps.hpp
 * Contains implementations of gp_ht_map_'s policy agpess
 *    functions.
 */

PB_DS_CLASS_T_DEC
Hash_Fn&
PB_DS_CLASS_C_DEC::
get_hash_fn()
{ return *this; }

PB_DS_CLASS_T_DEC
const Hash_Fn&
PB_DS_CLASS_C_DEC::
get_hash_fn() const
{ return *this; }

PB_DS_CLASS_T_DEC
Eq_Fn&
PB_DS_CLASS_C_DEC::
get_eq_fn()
{ return *this; }

PB_DS_CLASS_T_DEC
const Eq_Fn&
PB_DS_CLASS_C_DEC::
get_eq_fn() const
{ return *this; }

PB_DS_CLASS_T_DEC
Probe_Fn&
PB_DS_CLASS_C_DEC::
get_probe_fn()
{ return *this; }

PB_DS_CLASS_T_DEC
const Probe_Fn&
PB_DS_CLASS_C_DEC::
get_probe_fn() const
{ return *this; }

PB_DS_CLASS_T_DEC
Comb_Probe_Fn&
PB_DS_CLASS_C_DEC::
get_comb_probe_fn()
{ return *this; }

PB_DS_CLASS_T_DEC
const Comb_Probe_Fn&
PB_DS_CLASS_C_DEC::
get_comb_probe_fn() const
{ return *this; }

PB_DS_CLASS_T_DEC
Resize_Policy&
PB_DS_CLASS_C_DEC::
get_resize_policy()
{ return *this; }

PB_DS_CLASS_T_DEC
const Resize_Policy&
PB_DS_CLASS_C_DEC::
get_resize_policy() const
{ return *this; }

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 resize_fn_imps.hpp
 * Contains implementations of gp_ht_map_'s resize related functions.
 */

PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
do_resize_if_needed()
{
  if (!resize_base::is_resize_needed())
    return false;
  resize_imp(resize_base::get_new_size(m_num_e, m_num_used_e));
  return true;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
do_resize(size_type n)
{ resize_imp(resize_base::get_nearest_larger_size(n)); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
do_resize_if_needed_no_throw()
{
  if (!resize_base::is_resize_needed())
    return;

  try
    {
      resize_imp(resize_base::get_new_size(m_num_e, m_num_used_e));
    }
  catch(...)
    { }

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
resize_imp(size_type new_size)
{
#ifdef PB_DS_REGRESSION
  typename Allocator::group_throw_prob_adjustor adjust(m_num_e);
#endif

  if (new_size == m_num_e)
    return;

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  const size_type old_size = m_num_e;
  entry_array a_entries_resized = NULL;

  // Following line might throw an exception.
  a_entries_resized = s_entry_allocator.allocate(new_size);

  ranged_probe_fn_base::notify_resized(new_size);
  m_num_e = new_size;

  for (size_type i = 0; i < m_num_e; ++i)
    a_entries_resized[i].m_stat = empty_entry_status;

  try
    {
      resize_imp(a_entries_resized, old_size);
    }
  catch(...)
    {
      erase_all_valid_entries(a_entries_resized, new_size);
      m_num_e = old_size;
      s_entry_allocator.deallocate(a_entries_resized, new_size);
      ranged_probe_fn_base::notify_resized(old_size);
      __throw_exception_again;
    }

  // At this point no exceptions can be thrown.
  _GLIBCXX_DEBUG_ONLY(assert_entry_array_valid(a_entries_resized, traits_base::m_store_extra_indicator);)

  Resize_Policy::notify_resized(new_size);
  erase_all_valid_entries(m_entries, old_size);
  s_entry_allocator.deallocate(m_entries, old_size);
  m_entries = a_entries_resized;
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
resize_imp(entry_array a_entries_resized, size_type old_size)
{
  for (size_type pos = 0; pos < old_size; ++pos)
    if (m_entries[pos].m_stat == valid_entry_status)
      resize_imp_reassign(m_entries + pos, a_entries_resized,
			  traits_base::m_store_extra_indicator);
}

#include <ext/pb_ds/detail/gp_hash_table_map_/resize_no_store_hash_fn_imps.hpp>
#include <ext/pb_ds/detail/gp_hash_table_map_/resize_store_hash_fn_imps.hpp>


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

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

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

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

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

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

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

/**
 * @file resize_no_store_hash_fn_imps.hpp
 * Contains implementations of gp_ht_map_'s resize related functions, when the
 *    hash value is not stored.
 */

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized,
		    false_type)
{
  const_key_reference r_key = PB_DS_V2F(p_e->m_value);
  size_type hash = ranged_probe_fn_base::operator()(r_key);
  size_type i;
  for (i = 0; i < m_num_e; ++i)
    {
      const size_type pos = ranged_probe_fn_base::operator()(r_key, hash, i);
      entry_pointer p_new_e = a_entries_resized + pos;
      switch(p_new_e->m_stat)
        {
        case empty_entry_status:
	  new (&p_new_e->m_value) value_type(p_e->m_value);
	  p_new_e->m_stat = valid_entry_status;
	  return;
        case erased_entry_status:
	  _GLIBCXX_DEBUG_ASSERT(0);
	  break;
        case valid_entry_status:
	  break;
        default:
	  _GLIBCXX_DEBUG_ASSERT(0);
        };
    }
  __throw_insert_error();
}


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

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

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

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

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

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

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

/**
 * @file resize_store_hash_fn_imps.hpp
 * Contains implementations of gp_ht_map_'s resize related functions, when the
 *    hash value is stored.
 */

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
resize_imp_reassign(entry_pointer p_e, entry_array a_entries_resized,
		    true_type)
{
  const_key_reference r_key = PB_DS_V2F(p_e->m_value);
  size_type hash = ranged_probe_fn_base::operator()(r_key, p_e->m_hash);

  size_type i;
  for (i = 0; i < m_num_e; ++i)
    {
      const size_type pos = ranged_probe_fn_base::operator()(r_key, hash, i);
      entry_pointer p_new_e = a_entries_resized + pos;
      switch(p_new_e->m_stat)
        {
        case empty_entry_status:
	  new (&p_new_e->m_value) value_type(p_e->m_value);
	  p_new_e->m_hash = hash;
	  p_new_e->m_stat = valid_entry_status;
	  return;
        case erased_entry_status:
	  _GLIBCXX_DEBUG_ASSERT(0);
	  break;
        case valid_entry_status:
	  break;
        default:
	  _GLIBCXX_DEBUG_ASSERT(0);
        };
    }
  __throw_insert_error();
}


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 standard_policies.hpp
 * Contains standard policies for gp_ht_map types.
 */

#ifndef PB_DS_GP_HT_MAP_STANDARD_POLICIES_HPP
#define PB_DS_GP_HT_MAP_STANDARD_POLICIES_HPP

#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/ht_load_check_resize_trigger.hpp>
#include <ext/pb_ds/linear_probe_fn.hpp>
#include <ext/pb_ds/quadratic_probe_fn.hpp>

namespace pb_ds
{
  namespace detail
  {
    template<typename Comb_Probe_Fn>
    struct default_probe_fn
    {
    private:
      typedef typename Comb_Probe_Fn::size_type size_type;

    public:
      typedef
      typename __conditional_type<
      is_same<
      pb_ds::direct_mask_range_hashing<size_t>,
      Comb_Probe_Fn>::value,
      pb_ds::linear_probe_fn<size_type>,
      pb_ds::quadratic_probe_fn<size_type> >::__type
      type;
    };

  } // 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 trace_fn_imps.hpp
 * Contains implementations of gp_ht_map_'s trace-mode functions.
 */

#ifdef PB_DS_HT_MAP_TRACE_

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
trace() const
{
  std::cerr << static_cast<unsigned long>(m_num_e) << " " <<
    static_cast<unsigned long>(m_num_used_e) << std::endl;

  for (size_type i = 0; i < m_num_e; ++i)
    {
      std::cerr << static_cast<unsigned long>(i) << " ";

      switch(m_entries[i].m_stat)
        {
	case empty_entry_status:
	  std::cerr << "<empty>";
	  break;
	case erased_entry_status:
	  std::cerr << "<erased>";
	  break;
	case valid_entry_status:
	  std::cerr << PB_DS_V2F(m_entries[i].m_value);
	  break;
	default:
	  _GLIBCXX_DEBUG_ASSERT(0);
	};

      std::cerr << std::endl;
    }
}

#endif // #ifdef PB_DS_HT_MAP_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 direct_mask_range_hashing_imp.hpp
 * Contains a range-hashing policy implementation
 */

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{ mask_based_base::swap(other); }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_resized(size_type size)
{ mask_based_base::notify_resized(size); }

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
operator()(size_type hash) const
{ return mask_based_base::range_hash(hash); }


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 direct_mod_range_hashing_imp.hpp
 * Contains a range-hashing policy implementation
 */

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{ mod_based_base::swap(other); }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
notify_resized(size_type n)
{ mod_based_base::notify_resized(n); }

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
operator()(size_type hash) const
{ return mod_based_base::range_hash(hash); }


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

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{ }

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
operator()(size_type i) const
{
  return (i);
}


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 mask_based_range_hashing.hpp
 * Contains a range hashing policy base.
 */

#ifndef PB_DS_MASK_BASED_RANGE_HASHING_HPP
#define PB_DS_MASK_BASED_RANGE_HASHING_HPP

namespace pb_ds
{
  namespace detail
  {
#define PB_DS_CLASS_T_DEC template<typename Size_Type>
#define PB_DS_CLASS_C_DEC mask_based_range_hashing<Size_Type>

    template<typename Size_Type>
    class mask_based_range_hashing
    {
    protected:
      typedef Size_Type size_type;

      void
      swap(mask_based_range_hashing& other)
      { std::swap(m_mask, other.m_mask); }

      void
      notify_resized(size_type size);

      inline size_type
      range_hash(size_type hash) const
      { return size_type(hash & m_mask); }

    private:
      size_type 		m_mask;
      const static size_type 	s_num_bits_in_size_type;
      const static size_type 	s_highest_bit_1;
    };

    PB_DS_CLASS_T_DEC
    const typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::s_num_bits_in_size_type =
      sizeof(typename PB_DS_CLASS_C_DEC::size_type) << 3;

    PB_DS_CLASS_T_DEC
    const typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC::s_highest_bit_1 = static_cast<typename PB_DS_CLASS_C_DEC::size_type>(1) << (s_num_bits_in_size_type - 1);

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    notify_resized(size_type size)
    {
      size_type i = 0;
      while (size ^ s_highest_bit_1)
	{
	  size <<= 1;
	  ++i;
	}

      m_mask = 1;
      i += 2;
      while (i++ < s_num_bits_in_size_type)
        m_mask = (m_mask << 1) ^ 1;
    }

#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 mod_based_range_hashing.hpp
 * Contains a range hashing policy base.
 */

#ifndef PB_DS_MOD_BASED_RANGE_HASHING_HPP
#define PB_DS_MOD_BASED_RANGE_HASHING_HPP

namespace pb_ds
{

  namespace detail
  {

#define PB_DS_CLASS_T_DEC			\
    template<typename Size_Type>

#define PB_DS_CLASS_C_DEC					\
    mod_based_range_hashing<					\
						Size_Type>

    template<typename Size_Type>
    class mod_based_range_hashing
    {
    protected:
      typedef Size_Type size_type;

    protected:
      void
      swap(PB_DS_CLASS_C_DEC& other);

      void
      notify_resized(size_type size);

      inline size_type
      range_hash(size_type hash) const;

    private:
      size_type m_size;
    };

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

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

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    range_hash(size_type hash) const
    {
      return (hash % m_size);
    }

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

  } // namespace detail

} // namespace pb_ds

#endif // #ifndef PB_DS_MOD_BASED_RANGE_HASHING_HPP


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

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

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

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

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

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

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

/**
 * @file probe_fn_base.hpp
 * Contains a probe policy base.
 */

#ifndef PB_DS_PROBE_FN_BASE_HPP
#define PB_DS_PROBE_FN_BASE_HPP

#include <functional>

namespace pb_ds
{
  namespace detail
  {
    template<typename Allocator>
    class probe_fn_base
    {
    protected:
      ~probe_fn_base() { }
    };
} // 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 quadratic_probe_fn_imp.hpp
 * Contains a probe policy implementation
 */

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{ }

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
operator()(size_type i) const
{
  return (i*  i);
}


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 ranged_hash_fn.hpp
 * Contains a unified ranged hash functor, allowing the hash tables
 * to deal with a single class for ranged hashing.
 */

#ifndef PB_DS_RANGED_HASH_FN_HPP
#define PB_DS_RANGED_HASH_FN_HPP

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

namespace pb_ds
{
  namespace detail
  {
    template<typename Key, typename Hash_Fn, typename Allocator,
	     typename Comb_Hash_Fn, bool Store_Hash>
    class ranged_hash_fn;

#define PB_DS_CLASS_T_DEC \
    template<typename Key, typename Hash_Fn, typename Allocator, \
	     typename Comb_Hash_Fn>

#define PB_DS_CLASS_C_DEC \
    ranged_hash_fn<Key,	Hash_Fn, Allocator, Comb_Hash_Fn, false>

    /**
     * Specialization 1
     * The client supplies a hash function and a ranged hash function,
     * and requests that hash values not be stored.
     **/
    template<typename Key, typename Hash_Fn, typename Allocator,
	     typename Comb_Hash_Fn>
    class ranged_hash_fn< Key, Hash_Fn, Allocator, Comb_Hash_Fn, false>
    : public Hash_Fn, public Comb_Hash_Fn
    {
    protected:
      typedef typename Allocator::size_type size_type;
      typedef Hash_Fn hash_fn_base;
      typedef Comb_Hash_Fn comb_hash_fn_base;
      typedef typename Allocator::template rebind< Key>::other key_allocator;
      typedef typename key_allocator::const_reference const_key_reference;

      ranged_hash_fn(size_type);

      ranged_hash_fn(size_type, const Hash_Fn&);

      ranged_hash_fn(size_type, const Hash_Fn&, const Comb_Hash_Fn&);

      void
      swap(PB_DS_CLASS_C_DEC&);

      void
      notify_resized(size_type);

      inline size_type
      operator()(const_key_reference) const;
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_hash_fn(size_type size)
    { Comb_Hash_Fn::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn)
    : Hash_Fn(r_hash_fn)
    { Comb_Hash_Fn::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn,
		   const Comb_Hash_Fn& r_comb_hash_fn)
    : Hash_Fn(r_hash_fn), Comb_Hash_Fn(r_comb_hash_fn)
    { comb_hash_fn_base::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    swap(PB_DS_CLASS_C_DEC& other)
    {
      comb_hash_fn_base::swap(other);
      std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    notify_resized(size_type size)
    { comb_hash_fn_base::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    operator()(const_key_reference r_key) const
    { return (comb_hash_fn_base::operator()(hash_fn_base::operator()(r_key)));}

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC \
    template<typename Key, typename Hash_Fn, typename Allocator, \
	     typename Comb_Hash_Fn>

#define PB_DS_CLASS_C_DEC \
    ranged_hash_fn<Key,Hash_Fn,	Allocator, Comb_Hash_Fn, true>

    /**
     * Specialization 2
     * The client supplies a hash function and a ranged hash function,
     * and requests that hash values be stored.
     **/
    template<typename Key, typename Hash_Fn, typename Allocator,
	     typename Comb_Hash_Fn>
    class ranged_hash_fn<Key, Hash_Fn, Allocator, Comb_Hash_Fn, true>
    : public Hash_Fn, public Comb_Hash_Fn
    {
    protected:
      typedef typename Allocator::size_type size_type;
      typedef std::pair<size_type, size_type> comp_hash;
      typedef Hash_Fn hash_fn_base;
      typedef Comb_Hash_Fn comb_hash_fn_base;
      typedef typename Allocator::template rebind<Key>::other key_allocator;
      typedef typename key_allocator::const_reference const_key_reference;

      ranged_hash_fn(size_type);

      ranged_hash_fn(size_type, const Hash_Fn&);

      ranged_hash_fn(size_type, const Hash_Fn&, const Comb_Hash_Fn&);

      void
      swap(PB_DS_CLASS_C_DEC&);

      void
      notify_resized(size_type);

      inline comp_hash
      operator()(const_key_reference) const;

      inline comp_hash
      operator()(const_key_reference, size_type) const;
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_hash_fn(size_type size)
    { Comb_Hash_Fn::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn) :
      Hash_Fn(r_hash_fn)
    { Comb_Hash_Fn::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_hash_fn(size_type size, const Hash_Fn& r_hash_fn,
		   const Comb_Hash_Fn& r_comb_hash_fn)
    : Hash_Fn(r_hash_fn), Comb_Hash_Fn(r_comb_hash_fn)
    { comb_hash_fn_base::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    swap(PB_DS_CLASS_C_DEC& other)
    {
      comb_hash_fn_base::swap(other);
      std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    notify_resized(size_type size)
    { comb_hash_fn_base::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::comp_hash
    PB_DS_CLASS_C_DEC::
    operator()(const_key_reference r_key) const
    {
      const size_type hash = hash_fn_base::operator()(r_key);
      return std::make_pair(comb_hash_fn_base::operator()(hash), hash);
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::comp_hash
    PB_DS_CLASS_C_DEC::
    operator()
#ifdef _GLIBCXX_DEBUG
      (const_key_reference r_key, size_type hash) const
#else
      (const_key_reference /*r_key*/, size_type hash) const
#endif
    {
      _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key));
      return std::make_pair(comb_hash_fn_base::operator()(hash), hash);
    }

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC \
    template<typename Key, typename Allocator, typename Comb_Hash_Fn>

#define PB_DS_CLASS_C_DEC \
    ranged_hash_fn<Key,	null_hash_fn, Allocator, Comb_Hash_Fn, false>

    /**
     * Specialization 3
     * The client does not supply a hash function (by specifying
     * null_hash_fn as the Hash_Fn parameter), and requests that hash
     * values not be stored.
     **/
    template<typename Key, typename Allocator, typename Comb_Hash_Fn>
    class ranged_hash_fn<Key, null_hash_fn, Allocator, Comb_Hash_Fn, false>
    : public null_hash_fn, public Comb_Hash_Fn
    {
    protected:
      typedef typename Allocator::size_type size_type;
      typedef Comb_Hash_Fn comb_hash_fn_base;

      ranged_hash_fn(size_type);

      ranged_hash_fn(size_type, const Comb_Hash_Fn&);

      ranged_hash_fn(size_type, const null_hash_fn&, const Comb_Hash_Fn&);

      void
      swap(PB_DS_CLASS_C_DEC&);
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_hash_fn(size_type size)
    { Comb_Hash_Fn::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn) :
      Comb_Hash_Fn(r_comb_hash_fn)
    { }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_hash_fn(size_type size, const null_hash_fn& r_null_hash_fn,
		   const Comb_Hash_Fn& r_comb_hash_fn)
    : Comb_Hash_Fn(r_comb_hash_fn)
    { }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    swap(PB_DS_CLASS_C_DEC& other)
    { comb_hash_fn_base::swap(other); }

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC \
    template<typename Key, typename Allocator, typename Comb_Hash_Fn>

#define PB_DS_CLASS_C_DEC \
    ranged_hash_fn<Key,	null_hash_fn, Allocator, Comb_Hash_Fn, true>

    /**
     * Specialization 4
     * The client does not supply a hash function (by specifying
     * null_hash_fn as the Hash_Fn parameter), and requests that hash
     * values be stored.
     **/
    template<typename Key, typename Allocator, typename Comb_Hash_Fn>
    class ranged_hash_fn<Key, null_hash_fn, Allocator, Comb_Hash_Fn, true>
    : public null_hash_fn, public Comb_Hash_Fn
    {
    protected:
      typedef typename Allocator::size_type size_type;
      typedef Comb_Hash_Fn comb_hash_fn_base;

      ranged_hash_fn(size_type);

      ranged_hash_fn(size_type, const Comb_Hash_Fn&);

      ranged_hash_fn(size_type, const null_hash_fn&, const Comb_Hash_Fn&);

      void
      swap(PB_DS_CLASS_C_DEC&);
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_hash_fn(size_type size)
    { Comb_Hash_Fn::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_hash_fn(size_type size, const Comb_Hash_Fn& r_comb_hash_fn)
    : Comb_Hash_Fn(r_comb_hash_fn)
    { }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_hash_fn(size_type size, const null_hash_fn& r_null_hash_fn,
		   const Comb_Hash_Fn& r_comb_hash_fn)
    : Comb_Hash_Fn(r_comb_hash_fn)
    { }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    swap(PB_DS_CLASS_C_DEC& other)
    { comb_hash_fn_base::swap(other); }

#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 ranged_probe_fn.hpp
 * Contains a unified ranged probe functor, allowing the probe tables to deal with
 *    a single class for ranged probeing.
 */

#ifndef PB_DS_RANGED_PROBE_FN_HPP
#define PB_DS_RANGED_PROBE_FN_HPP

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

namespace pb_ds
{
  namespace detail
  {
    template<typename Key, typename Hash_Fn, typename Allocator,
	     typename Comb_Probe_Fn, typename Probe_Fn, bool Store_Hash>
    class ranged_probe_fn;

#define PB_DS_CLASS_T_DEC \
    template<typename Key, typename Hash_Fn, typename Allocator, \
	     typename Comb_Probe_Fn, typename Probe_Fn>

#define PB_DS_CLASS_C_DEC \
    ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, false>

    /**
     * Specialization 1
     * The client supplies a probe function and a ranged probe
     * function, and requests that hash values not be stored.
     **/
    template<typename Key, typename Hash_Fn, typename Allocator,
	     typename Comb_Probe_Fn, typename Probe_Fn>
    class ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn,
			  Probe_Fn, false>
    : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
    {
    protected:
      typedef typename Allocator::size_type size_type;
      typedef Comb_Probe_Fn comb_probe_fn_base;
      typedef Hash_Fn hash_fn_base;
      typedef Probe_Fn probe_fn_base;
      typedef typename Allocator::template rebind<Key>::other key_allocator;
      typedef typename key_allocator::const_reference const_key_reference;

      ranged_probe_fn(size_type);

      ranged_probe_fn(size_type, const Hash_Fn&);

      ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&);

      ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&,
		      const Probe_Fn&);

      void
      swap(PB_DS_CLASS_C_DEC&);

      void
      notify_resized(size_type);

      inline size_type
      operator()(const_key_reference) const;

      inline size_type
      operator()(const_key_reference, size_type, size_type) const;
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size)
    { Comb_Probe_Fn::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn)
    : Hash_Fn(r_hash_fn)
    { Comb_Probe_Fn::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
		    const Comb_Probe_Fn& r_comb_probe_fn)
    : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn)
    { comb_probe_fn_base::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
		    const Comb_Probe_Fn& r_comb_probe_fn,
		    const Probe_Fn& r_probe_fn)
    : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn)
    { comb_probe_fn_base::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    swap(PB_DS_CLASS_C_DEC& other)
    {
      comb_probe_fn_base::swap(other);
      std::swap((Hash_Fn& )(*this), (Hash_Fn&)other);
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    notify_resized(size_type size)
    { comb_probe_fn_base::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    operator()(const_key_reference r_key) const
    { return comb_probe_fn_base::operator()(hash_fn_base::operator()(r_key)); }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    operator()(const_key_reference, size_type hash, size_type i) const
    {
      return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
    }

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

#define PB_DS_CLASS_T_DEC \
    template<typename Key, typename Hash_Fn, typename Allocator, \
	     typename Comb_Probe_Fn, typename Probe_Fn>

#define PB_DS_CLASS_C_DEC \
    ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn, Probe_Fn, true>

    /**
     * Specialization 2- The client supplies a probe function and a ranged
     *    probe function, and requests that hash values not be stored.
     **/
    template<typename Key, typename Hash_Fn, typename Allocator,
	     typename Comb_Probe_Fn, typename Probe_Fn>
    class ranged_probe_fn<Key, Hash_Fn, Allocator, Comb_Probe_Fn,
			  Probe_Fn, true>
    : public Hash_Fn, public Comb_Probe_Fn, public Probe_Fn
    {
    protected:
      typedef typename Allocator::size_type size_type;
      typedef std::pair<size_type, size_type> comp_hash;
      typedef Comb_Probe_Fn comb_probe_fn_base;
      typedef Hash_Fn hash_fn_base;
      typedef Probe_Fn probe_fn_base;
      typedef typename Allocator::template rebind<Key>::other key_allocator;
      typedef typename key_allocator::const_reference const_key_reference;

      ranged_probe_fn(size_type);

      ranged_probe_fn(size_type, const Hash_Fn&);

      ranged_probe_fn(size_type, const Hash_Fn&,
		      const Comb_Probe_Fn&);

      ranged_probe_fn(size_type, const Hash_Fn&, const Comb_Probe_Fn&,
		      const Probe_Fn&);

      void
      swap(PB_DS_CLASS_C_DEC&);

      void
      notify_resized(size_type);

      inline comp_hash
      operator()(const_key_reference) const;

      inline size_type
      operator()(const_key_reference, size_type, size_type) const;

      inline size_type
      operator()(const_key_reference, size_type) const;
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size)
    { Comb_Probe_Fn::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn)
    : Hash_Fn(r_hash_fn)
    { Comb_Probe_Fn::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
		    const Comb_Probe_Fn& r_comb_probe_fn)
    : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn)
    { comb_probe_fn_base::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ranged_probe_fn(size_type size, const Hash_Fn& r_hash_fn,
		    const Comb_Probe_Fn& r_comb_probe_fn,
		    const Probe_Fn& r_probe_fn)
    : Hash_Fn(r_hash_fn), Comb_Probe_Fn(r_comb_probe_fn), Probe_Fn(r_probe_fn)
    { comb_probe_fn_base::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    swap(PB_DS_CLASS_C_DEC& other)
    {
      comb_probe_fn_base::swap(other);
      std::swap((Hash_Fn& )(*this), (Hash_Fn& )other);
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    notify_resized(size_type size)
    { comb_probe_fn_base::notify_resized(size); }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::comp_hash
    PB_DS_CLASS_C_DEC::
    operator()(const_key_reference r_key) const
    {
      const size_type hash = hash_fn_base::operator()(r_key);
      return std::make_pair(comb_probe_fn_base::operator()(hash), hash);
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    operator()(const_key_reference, size_type hash, size_type i) const
    {
      return comb_probe_fn_base::operator()(hash + probe_fn_base::operator()(i));
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    operator()
#ifdef _GLIBCXX_DEBUG
      (const_key_reference r_key, size_type hash) const
#else
      (const_key_reference /*r_key*/, size_type hash) const
#endif
    {
      _GLIBCXX_DEBUG_ASSERT(hash == hash_fn_base::operator()(r_key));
      return hash;
    }

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

    /**
     * Specialization 3 and 4
     * The client does not supply a hash function or probe function,
     * and requests that hash values not be stored.
     **/
    template<typename Key, typename Allocator, typename Comb_Probe_Fn>
    class ranged_probe_fn<Key, null_hash_fn, Allocator, Comb_Probe_Fn,
			  null_probe_fn, false>
    : public Comb_Probe_Fn, public null_hash_fn, public null_probe_fn
    {
    protected:
      typedef typename Allocator::size_type size_type;
      typedef Comb_Probe_Fn comb_probe_fn_base;
      typedef typename Allocator::template rebind<Key>::other key_allocator;
      typedef typename key_allocator::const_reference const_key_reference;

      ranged_probe_fn(size_type size)
      { Comb_Probe_Fn::notify_resized(size); }

      ranged_probe_fn(size_type, const Comb_Probe_Fn& r_comb_probe_fn)
      : Comb_Probe_Fn(r_comb_probe_fn)
      { }

      ranged_probe_fn(size_type, const null_hash_fn&,
		      const Comb_Probe_Fn& r_comb_probe_fn,
		      const null_probe_fn&)
      : Comb_Probe_Fn(r_comb_probe_fn)
      { }

      void
      swap(ranged_probe_fn& other)
      { comb_probe_fn_base::swap(other); }
    };
  } // 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 sample_probe_fn.hpp
 * Contains a sample probe policy.
 */

#ifndef PB_DS_SAMPLE_PROBE_FN_HPP
#define PB_DS_SAMPLE_PROBE_FN_HPP

// A sample probe policy.
class sample_probe_fn
{

public:

  // Size type.
  typedef size_t size_type;

public:

  // Default constructor.
  sample_probe_fn();

  // Copy constructor.
  sample_probe_fn(const sample_probe_fn& other);

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

protected:

  // Returns the i-th offset from the hash value of some key r_key.
  inline size_type
  operator()(const_key_reference r_key, size_type i) const;

};

#endif // #ifndef PB_DS_SAMPLE_PROBE_FN_HPP


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

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

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

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

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

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

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

/**
 * @file sample_range_hashing.hpp
 * Contains a range hashing policy.
 */

#ifndef PB_DS_SAMPLE_RANGE_HASHING_HPP
#define PB_DS_SAMPLE_RANGE_HASHING_HPP

// A sample range-hashing functor.
class sample_range_hashing
{

public:

  // Size type.
  typedef size_t size_type;

public:

  // Default constructor.
  sample_range_hashing();

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

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

protected:

  // Notifies the policy object that the container's __size has changed to size.
  void
  notify_resized(size_type size);

  // Transforms the __hash value hash into a ranged-hash value.
  inline size_type
  operator()(size_type hash) const;

};

#endif // #ifndef PB_DS_SAMPLE_RANGE_HASHING_HPP


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

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

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

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

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

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

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

/**
 * @file sample_ranged_hash_fn.hpp
 * Contains a ranged hash policy.
 */

#ifndef PB_DS_SAMPLE_RANGED_HASH_FN_HPP
#define PB_DS_SAMPLE_RANGED_HASH_FN_HPP

// A sample ranged-hash functor.
class sample_ranged_hash_fn
{

public:

  // Size type.
  typedef size_t size_type;

public:

  // Default constructor.
  sample_ranged_hash_fn();

  // Copy constructor.
  sample_ranged_hash_fn(const sample_ranged_hash_fn& other);

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

protected:

  // Notifies the policy object that the container's __size has changed to size.
  void
  notify_resized(size_type size);

  // Transforms r_key into a position within the table.
  inline size_type
  operator()(const_key_reference r_key) const;

};

#endif // #ifndef PB_DS_SAMPLE_RANGED_HASH_FN_HPP


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

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

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

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

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

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

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

/**
 * @file sample_ranged_probe_fn.hpp
 * Contains a ranged probe policy.
 */

#ifndef PB_DS_SAMPLE_RANGED_PROBE_FN_HPP
#define PB_DS_SAMPLE_RANGED_PROBE_FN_HPP

// A sample ranged-probe functor.
class sample_ranged_probe_fn
{

public:

  // Size type.
  typedef size_t size_type;

public:

  // Default constructor.
  sample_ranged_probe_fn();

  // Copy constructor.
  sample_ranged_probe_fn(const sample_ranged_probe_fn& other);

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

protected:

  // Notifies the policy object that the container's __size has changed to size.
  void
  notify_resized(size_type size);

  // Transforms the const key reference r_key into the i-th position within the table. This method is called for each collision within the probe sequence.
  inline size_type
  operator()(const_key_reference r_key, size_t hash, size_type i) const;

};

#endif // #ifndef PB_DS_SAMPLE_RANGED_PROBE_FN_HPP


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

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

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

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

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

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

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

/**
 * @file const_iterator.hpp
 * Contains an iterator class returned by the table's const find and insert
 *     methods.
 */

#ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_CONST_ITERATOR_HPP
#define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_CONST_ITERATOR_HPP

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

namespace pb_ds
{
  namespace detail
  {

#define PB_DS_CLASS_C_DEC						\
    left_child_next_sibling_heap_const_iterator_<Node, Allocator>

#define PB_DS_BASE_C_DEC						\
    left_child_next_sibling_heap_node_const_point_iterator_<Node, Allocator>

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

    private:
      typedef typename PB_DS_BASE_C_DEC::node_pointer node_pointer;

      typedef PB_DS_BASE_C_DEC base_type;

    public:

      // Category.
      typedef std::forward_iterator_tag iterator_category;

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

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

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

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

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

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

    public:

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

      // Default constructor.
      inline
      left_child_next_sibling_heap_const_iterator_()
      { }

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

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

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

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

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

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

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

#undef PB_DS_CLASS_C_DEC
#undef PB_DS_BASE_C_DEC

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

#ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_CONST_FIND_ITERATOR_HPP
#define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_CONST_FIND_ITERATOR_HPP

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

namespace pb_ds
{
  namespace detail
  {

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

#define PB_DS_CLASS_C_DEC \
    left_child_next_sibling_heap_node_const_point_iterator_<Node, Allocator>

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

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

    public:

      // Category.
      typedef trivial_iterator_tag iterator_category;

      // Difference type.
      typedef trivial_iterator_difference_type difference_type;

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

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

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

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

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

    public:

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

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

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

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

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

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

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

    public:
      node_pointer m_p_nd;
    };

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

  } // namespace detail
} // namespace pb_ds

#endif


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

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

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

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

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

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

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

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

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::node_allocator
PB_DS_CLASS_C_DEC::s_node_allocator;

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::no_throw_copies_t
PB_DS_CLASS_C_DEC::s_no_throw_copies_ind;

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
left_child_next_sibling_heap_() :
  m_p_root(NULL),
  m_size(0)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
left_child_next_sibling_heap_(const Cmp_Fn& r_cmp_fn) :
  Cmp_Fn(r_cmp_fn),
  m_p_root(NULL),
  m_size(0)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
left_child_next_sibling_heap_(const PB_DS_CLASS_C_DEC& other)
: Cmp_Fn(other), m_p_root(NULL), m_size(0)
{
  m_size = other.m_size;
  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
  m_p_root = recursive_copy_node(other.m_p_root);
  m_size = other.m_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();)
  value_swap(other);
  std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )other);
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}

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

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~left_child_next_sibling_heap_()
{
  clear();
}

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

  node_pointer p_ret = s_node_allocator.allocate(1);

  try
    {
      new (p_ret) node(*p_nd);
    }
  catch(...)
    {
      s_node_allocator.deallocate(p_ret, 1);
      __throw_exception_again;
    }

  p_ret->m_p_l_child = p_ret->m_p_next_sibling =
    p_ret->m_p_prev_or_parent = NULL;

  try
    {
      p_ret->m_p_l_child = recursive_copy_node(p_nd->m_p_l_child);
      p_ret->m_p_next_sibling = recursive_copy_node(p_nd->m_p_next_sibling);
    }
  catch(...)
    {
      clear_imp(p_ret);
      __throw_exception_again;
    }

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

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

  return p_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 debug_fn_imps.hpp
 * Contains an implementation class for left_child_next_sibling_heap_.
 */

#ifdef _GLIBCXX_DEBUG

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid() const
{
  _GLIBCXX_DEBUG_ASSERT(m_p_root == NULL || m_p_root->m_p_prev_or_parent == NULL);

  if (m_p_root != NULL)
    assert_node_consistent(m_p_root, Single_Link_Roots);
  assert_size();
  assert_iterators();
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_node_consistent(const_node_pointer p_nd, bool single_link) const
{
  if (p_nd == NULL)
    return;

  assert_node_consistent(p_nd->m_p_l_child, false);
  assert_node_consistent(p_nd->m_p_next_sibling, single_link);

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

  if (p_nd->m_p_l_child == NULL)
    return;

  const_node_pointer p_child = p_nd->m_p_l_child;
  while (p_child != NULL)
    {
      const_node_pointer p_next_child = p_child->m_p_next_sibling;
      _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(p_nd->m_value, p_child->m_value));
      p_child = p_next_child;
    }
  _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_l_child->m_p_prev_or_parent == p_nd);
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_iterators() const
{
  const size_type calc_size = std::distance(begin(), end());
  if (calc_size == size())
    return;
  _GLIBCXX_DEBUG_ASSERT(0);
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_size() const
{
  if (size_from_node(m_p_root) == m_size)
    return;
  _GLIBCXX_DEBUG_ASSERT(0);
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
size_under_node(const_node_pointer p_nd)
{ return 1 + size_from_node(p_nd->m_p_l_child); }

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
size_from_node(const_node_pointer p_nd)
{
  size_type ret = 0;
  while (p_nd != NULL)
    {
      ret += 1 + size_from_node(p_nd->m_p_l_child);
      p_nd = p_nd->m_p_next_sibling;
    }
  return ret;
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
degree(const_node_pointer p_nd)
{
  size_type ret = 0;
  const_node_pointer p_child = p_nd->m_p_l_child;
  while (p_child != NULL)
    {
      ++ret;
      p_child = p_child->m_p_next_sibling;
    }
  return ret;
}

#endif


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

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

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

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

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

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

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

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

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
clear()
{
  clear_imp(m_p_root);
  _GLIBCXX_DEBUG_ASSERT(m_size == 0);
  m_p_root = NULL;
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
actual_erase_node(node_pointer p_nd)
{
  _GLIBCXX_DEBUG_ASSERT(m_size > 0);
  --m_size;
  p_nd->~node();
  s_node_allocator.deallocate(p_nd, 1);
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
clear_imp(node_pointer p_nd)
{
  while (p_nd != NULL)
    {
      clear_imp(p_nd->m_p_l_child);
      node_pointer p_next = p_nd->m_p_next_sibling;
      actual_erase_node(p_nd);
      p_nd = p_next;
    }
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
to_linked_list()
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  node_pointer p_cur = m_p_root;
  while (p_cur != NULL)
    if (p_cur->m_p_l_child != NULL)
      {
	node_pointer p_child_next = p_cur->m_p_l_child->m_p_next_sibling;
	p_cur->m_p_l_child->m_p_next_sibling = p_cur->m_p_next_sibling;
	p_cur->m_p_next_sibling = p_cur->m_p_l_child;
	p_cur->m_p_l_child = p_child_next;
      }
    else
      p_cur = p_cur->m_p_next_sibling;

#ifdef _GLIBCXX_DEBUG
  const_node_pointer p_counter = m_p_root;
  size_type count = 0;
  while (p_counter != NULL)
    {
      ++count;
      _GLIBCXX_DEBUG_ASSERT(p_counter->m_p_l_child == NULL);
      p_counter = p_counter->m_p_next_sibling;
    }
  _GLIBCXX_DEBUG_ASSERT(count == m_size);
#endif
}

PB_DS_CLASS_T_DEC
template<typename Pred>
typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
prune(Pred pred)
{
  node_pointer p_cur = m_p_root;
  m_p_root = NULL;
  node_pointer p_out = NULL;
  while (p_cur != NULL)
    {
      node_pointer p_next = p_cur->m_p_next_sibling;
      if (pred(p_cur->m_value))
        {
	  p_cur->m_p_next_sibling = p_out;
	  if (p_out != NULL)
	    p_out->m_p_prev_or_parent = p_cur;
	  p_out = p_cur;
        }
      else
        {
	  p_cur->m_p_next_sibling = m_p_root;
	  if (m_p_root != NULL)
	    m_p_root->m_p_prev_or_parent = p_cur;
	  m_p_root = p_cur;
        }
      p_cur = p_next;
    }
  return p_out;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
bubble_to_top(node_pointer p_nd)
{
  node_pointer p_parent = parent(p_nd);
  while (p_parent != NULL)
    {
      swap_with_parent(p_nd, p_parent);
      p_parent = parent(p_nd);
    }
}


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

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

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

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

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

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

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

/**
 * @file info_fn_imps.hpp
 * Contains an implementation class for left_child_next_sibling_heap_.
 */

PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
empty() const
{
  return (m_size == 0);
}

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

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
max_size() const
{
  return (s_node_allocator.max_size());
}