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

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

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

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

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

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

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

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

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
get_new_node_for_insert(const_reference r_val)
{
  return get_new_node_for_insert(r_val, s_no_throw_copies_ind);
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
get_new_node_for_insert(const_reference r_val, false_type)
{
  node_pointer p_new_nd = s_node_allocator.allocate(1);

  cond_dealtor_t cond(p_new_nd);

  new (const_cast<void* >(
			  static_cast<const void* >(&p_new_nd->m_value)))
    typename node::value_type(r_val);

  cond.set_no_action();

  ++m_size;

  return (p_new_nd);
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
get_new_node_for_insert(const_reference r_val, true_type)
{
  node_pointer p_new_nd = s_node_allocator.allocate(1);

  new (const_cast<void* >(
			  static_cast<const void* >(&p_new_nd->m_value)))
    typename node::value_type(r_val);

  ++m_size;

  return (p_new_nd);
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
make_child_of(node_pointer p_nd, node_pointer p_new_parent)
{
  _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
  _GLIBCXX_DEBUG_ASSERT(p_new_parent != NULL);

  p_nd->m_p_next_sibling = p_new_parent->m_p_l_child;

  if (p_new_parent->m_p_l_child != NULL)
    p_new_parent->m_p_l_child->m_p_prev_or_parent = p_nd;

  p_nd->m_p_prev_or_parent = p_new_parent;

  p_new_parent->m_p_l_child = p_nd;
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
parent(node_pointer p_nd)
{
  while (true)
    {
      node_pointer p_pot = p_nd->m_p_prev_or_parent;

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

      p_nd = p_pot;
    }
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
swap_with_parent(node_pointer p_nd, node_pointer p_parent)
{
  if (p_parent == m_p_root)
    m_p_root = p_nd;

  _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
  _GLIBCXX_DEBUG_ASSERT(p_parent != NULL);
  _GLIBCXX_DEBUG_ASSERT(parent(p_nd) == p_parent);

  const bool nd_direct_child = p_parent->m_p_l_child == p_nd;
  const bool parent_root = p_parent->m_p_prev_or_parent == NULL;
  const bool parent_direct_child =
    !parent_root&&  p_parent->m_p_prev_or_parent->m_p_l_child == p_parent;

  std::swap(p_parent->m_p_prev_or_parent, p_nd->m_p_prev_or_parent);
  std::swap(p_parent->m_p_next_sibling, p_nd->m_p_next_sibling);
  std::swap(p_parent->m_p_l_child, p_nd->m_p_l_child);
  std::swap(p_parent->m_metadata, p_nd->m_metadata);

  _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_l_child != NULL);
  _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_prev_or_parent != NULL);

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

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

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

  if (parent_direct_child)
    p_nd->m_p_prev_or_parent->m_p_l_child = p_nd;
  else if (!parent_root)
    p_nd->m_p_prev_or_parent->m_p_next_sibling = p_nd;

  if (!nd_direct_child)
    {
      p_nd->m_p_l_child->m_p_prev_or_parent = p_nd;

      p_parent->m_p_prev_or_parent->m_p_next_sibling = p_parent;
    }
  else
    {
      _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_l_child == p_nd);
      _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_prev_or_parent == p_parent);

      p_nd->m_p_l_child = p_parent;
      p_parent->m_p_prev_or_parent = p_nd;
    }

  _GLIBCXX_DEBUG_ASSERT(parent(p_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 iterators_fn_imps.hpp
 * Contains an implementation class for left_child_next_sibling_heap_.
 */

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

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

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

  return (iterator(p_nd));
}

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

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

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

  return (const_iterator(p_nd));
}

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

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

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

#ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_HPP
#define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_HPP

/*
 * Based on CLRS.
 */

#include <iterator>
#include <ext/pb_ds/detail/cond_dealtor.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/node.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/const_point_iterator.hpp>
#include <ext/pb_ds/detail/left_child_next_sibling_heap_/const_iterator.hpp>
#ifdef PB_DS_LC_NS_HEAP_TRACE_
#include <iostream>
#endif
#include <debug/debug.h>

namespace pb_ds
{
  namespace detail
  {

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

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

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

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

      typedef typename node_allocator::value_type node;

      typedef typename node_allocator::pointer node_pointer;

      typedef typename node_allocator::const_pointer const_node_pointer;

      typedef Node_Metadata node_metadata;

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

    private:
      typedef cond_dealtor< node, Allocator> cond_dealtor_t;

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

      typedef integral_constant<int, simple_value> no_throw_copies_t;

    public:

      typedef typename Allocator::size_type size_type;

      typedef typename Allocator::difference_type difference_type;

      typedef Value_Type value_type;

      typedef
      typename Allocator::template rebind<
	value_type>::other::pointer
      pointer;

      typedef
      typename Allocator::template rebind<
	value_type>::other::const_pointer
      const_pointer;

      typedef
      typename Allocator::template rebind<
	value_type>::other::reference
      reference;

      typedef
      typename Allocator::template rebind<
	value_type>::other::const_reference
      const_reference;

      typedef
      left_child_next_sibling_heap_node_const_point_iterator_<
	node,
	Allocator>
      const_point_iterator;

      typedef const_point_iterator point_iterator;

      typedef
      left_child_next_sibling_heap_const_iterator_<
	node,
	Allocator>
      const_iterator;

      typedef const_iterator iterator;

      typedef Cmp_Fn cmp_fn;

      typedef Allocator allocator;

    public:

      left_child_next_sibling_heap_();

      left_child_next_sibling_heap_(const Cmp_Fn& r_cmp_fn);

      left_child_next_sibling_heap_(const PB_DS_CLASS_C_DEC& other);

      void
      swap(PB_DS_CLASS_C_DEC& other);

      ~left_child_next_sibling_heap_();

      inline bool
      empty() const;

      inline size_type
      size() const;

      inline size_type
      max_size() const;

      Cmp_Fn&
      get_cmp_fn();

      const Cmp_Fn&
      get_cmp_fn() const;

      inline iterator
      begin();

      inline const_iterator
      begin() const;

      inline iterator
      end();

      inline const_iterator
      end() const;

      void
      clear();

#ifdef PB_DS_LC_NS_HEAP_TRACE_
      void
      trace() const;
#endif

    protected:

      inline node_pointer
      get_new_node_for_insert(const_reference r_val);

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

      void
      value_swap(PB_DS_CLASS_C_DEC& other);

      inline static node_pointer
      parent(node_pointer p_nd);

      inline void
      swap_with_parent(node_pointer p_nd, node_pointer p_parent);

      void
      bubble_to_top(node_pointer p_nd);

      inline void
      actual_erase_node(node_pointer p_nd);

      void
      clear_imp(node_pointer p_nd);

      void
      to_linked_list();

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

#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;

      void
      assert_node_consistent(const_node_pointer p_nd, bool single_link) const;

      static size_type
      size_under_node(const_node_pointer p_nd);

      static size_type
      degree(const_node_pointer p_nd);
#endif

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

    protected:
      node_pointer m_p_root;

      size_type m_size;

    private:
#ifdef _GLIBCXX_DEBUG
      void
      assert_iterators() const;

      void
      assert_size() const;

      static size_type
      size_from_node(const_node_pointer p_nd);
#endif

      node_pointer
      recursive_copy_node(const_node_pointer p_nd);

      inline node_pointer
      get_new_node_for_insert(const_reference r_val, false_type);

      inline node_pointer
      get_new_node_for_insert(const_reference r_val, true_type);

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

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

    private:
      static node_allocator s_node_allocator;

      static no_throw_copies_t s_no_throw_copies_ind;
    };

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

#undef PB_DS_CLASS_C_DEC
#undef PB_DS_CLASS_T_DEC

  } // namespace detail
} // namespace 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 node.hpp
 * Contains an implementation struct for this type of heap's node.
 */

#ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NODE_HPP
#define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NODE_HPP

#include <ext/pb_ds/detail/left_child_next_sibling_heap_/null_metadata.hpp>

namespace pb_ds
{
  namespace detail
  {

    template<typename Value_Type, typename Metadata_Type, class Allocator>
    struct left_child_next_sibling_heap_node_
    {
    private:
      typedef
      left_child_next_sibling_heap_node_<
      Value_Type,
      Metadata_Type,
      Allocator>
      this_type;

    public:
      typedef typename Allocator::size_type size_type;

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

      typedef Value_Type value_type;

      typedef Metadata_Type metadata_type;

    public:
      value_type m_value;

      metadata_type m_metadata;

      node_pointer m_p_l_child;

      node_pointer m_p_next_sibling;

      node_pointer m_p_prev_or_parent;
    };

    template<typename Value_Type, class Allocator>
    struct left_child_next_sibling_heap_node_<
      Value_Type,
      null_left_child_next_sibling_heap_node_metadata,
      Allocator>
    {
    private:
      typedef
      left_child_next_sibling_heap_node_<
      Value_Type,
      null_left_child_next_sibling_heap_node_metadata,
      Allocator>
      this_type;

    public:
      typedef typename Allocator::size_type size_type;

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

      typedef Value_Type value_type;

    public:
      value_type m_value;

      node_pointer m_p_l_child;

      node_pointer m_p_next_sibling;

      node_pointer m_p_prev_or_parent;
    };

  } // namespace detail
} // namespace pb_ds

#endif // #ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NODE_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 null_metadata.hpp
 * Contains an implementation struct for this type of heap's node.
 */

#ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NULL_METADATA_HPP
#define PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NULL_METADATA_HPP

#include <ext/pb_ds/detail/left_child_next_sibling_heap_/null_metadata.hpp>

namespace pb_ds
{
  namespace detail
  {

    struct null_left_child_next_sibling_heap_node_metadata
    { };

  } // namespace detail
} // namespace pb_ds

#endif // #ifndef PB_DS_LEFT_CHILD_NEXT_SIBLING_HEAP_NULL_METADATA_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 policy_access_fn_imps.hpp
 * Contains an implementation class for left_child_next_sibling_heap_.
 */

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

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


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

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

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

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

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

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

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

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

#ifdef PB_DS_LC_NS_HEAP_TRACE_

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

  trace_node(m_p_root, 0);

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

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
trace_node(const_node_pointer p_nd, size_type level)
{
  while (p_nd != NULL)
    {
      for (size_type i = 0; i < level; ++i)
	std::cerr << ' ';

      std::cerr << p_nd <<
	" prev = " << p_nd->m_p_prev_or_parent <<
	" next " << p_nd->m_p_next_sibling <<
	" left = " << p_nd->m_p_l_child << " ";

      trace_node_metadata(p_nd, type_to_type<node_metadata>());

      std::cerr << p_nd->m_value << std::endl;

      trace_node(p_nd->m_p_l_child, level + 1);

      p_nd = p_nd->m_p_next_sibling;
    }
}

PB_DS_CLASS_T_DEC
template<typename Metadata_>
void
PB_DS_CLASS_C_DEC::
trace_node_metadata(const_node_pointer p_nd, type_to_type<Metadata_>)
{
  std::cerr << "(" << p_nd->m_metadata << ") ";
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
trace_node_metadata(const_node_pointer, type_to_type<null_left_child_next_sibling_heap_node_metadata>)
{ }

#endif // #ifdef PB_DS_LC_NS_HEAP_TRACE_


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

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

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

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

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

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

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

/**
 * @file constructor_destructor_fn_imps.hpp
 * Contains implementations of PB_DS_CLASS_NAME.
 */

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::entry_allocator
PB_DS_CLASS_C_DEC::s_entry_allocator;

PB_DS_CLASS_T_DEC
Eq_Fn PB_DS_CLASS_C_DEC::s_eq_fn;

PB_DS_CLASS_T_DEC
null_lu_metadata PB_DS_CLASS_C_DEC::s_null_lu_metadata;

PB_DS_CLASS_T_DEC
Update_Policy PB_DS_CLASS_C_DEC::s_update_policy;

PB_DS_CLASS_T_DEC
type_to_type<
  typename PB_DS_CLASS_C_DEC::update_metadata> PB_DS_CLASS_C_DEC::s_metadata_type_indicator;

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

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME() : m_p_l(NULL)
{ _GLIBCXX_DEBUG_ONLY(assert_valid();) }

PB_DS_CLASS_T_DEC
template<typename It>
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME(It first_it, It last_it) : m_p_l(NULL)
{
  copy_from_range(first_it, last_it);
  _GLIBCXX_DEBUG_ONLY(assert_valid(););
}

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) :
#ifdef _GLIBCXX_DEBUG
  map_debug_base(),
#endif
m_p_l(NULL)
{
  try
    {
      for (const_iterator it = other.begin(); it != other.end(); ++it)
        {
	  entry_pointer p_l = allocate_new_entry(*it,
			PB_DS_TYPES_TRAITS_C_DEC::m_no_throw_copies_indicator);

	  p_l->m_p_next = m_p_l;
	  m_p_l = p_l;
        }
    }
  catch(...)
    {
      deallocate_all();
      __throw_exception_again;
    }
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
  _GLIBCXX_DEBUG_ONLY(map_debug_base::swap(other);)
  std::swap(m_p_l, other.m_p_l);
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
deallocate_all()
{
  entry_pointer p_l = m_p_l;
  while (p_l != NULL)
    {
      entry_pointer p_next_l = p_l->m_p_next;
      actual_erase_entry(p_l);
      p_l = p_next_l;
    }
  m_p_l = NULL;
}

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~PB_DS_CLASS_NAME()
{ deallocate_all(); }


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 implementations of cc_ht_map_'s debug-mode functions.
 */

#ifdef _GLIBCXX_DEBUG

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid() const
{
  size_type calc_size = 0;
  for (const_iterator it = begin(); it != end(); ++it)
    {
      map_debug_base::check_key_exists(PB_DS_V2F(*it));
      ++calc_size;
    }
  map_debug_base::check_size(calc_size);
}

#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 entry_metadata_base.hpp
 * Contains an implementation for a list update map.
 */

#ifndef PB_DS_LU_MAP_ENTRY_METADATA_BASE_HPP
#define PB_DS_LU_MAP_ENTRY_METADATA_BASE_HPP

namespace pb_ds
{
  namespace detail
  {
    template<typename Metadata>
    struct lu_map_entry_metadata_base
    {
      Metadata m_update_metadata;
    };

    template<>
    struct lu_map_entry_metadata_base<null_lu_metadata>
    { };
  } // 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 erase_fn_imps.hpp
 * Contains implementations of lu_map_.
 */

PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
erase(const_key_reference r_key)
{
  _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
  if (m_p_l == NULL)
    return false;

  if (s_eq_fn(r_key, PB_DS_V2F(m_p_l->m_value)))
    {
      entry_pointer p_next = m_p_l->m_p_next;
      actual_erase_entry(m_p_l);
      m_p_l = p_next;
      return true;
    }

  entry_pointer p_l = m_p_l;
  while (p_l->m_p_next != NULL)
    if (s_eq_fn(r_key, PB_DS_V2F(p_l->m_p_next->m_value)))
      {
	erase_next(p_l);
	return true;
      }
    else
      p_l = p_l->m_p_next;
  return false;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
clear()
{
  deallocate_all();
}

PB_DS_CLASS_T_DEC
template<typename Pred>
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
erase_if(Pred pred)
{
  _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
  size_type num_ersd = 0;
  while (m_p_l != NULL && pred(m_p_l->m_value))
    {
      entry_pointer p_next = m_p_l->m_p_next;
      ++num_ersd;
      actual_erase_entry(m_p_l);
      m_p_l = p_next;
    }

  if (m_p_l == NULL)
    return num_ersd;

  entry_pointer p_l = m_p_l;
  while (p_l->m_p_next != NULL)
    {
      if (pred(p_l->m_p_next->m_value))
        {
	  ++num_ersd;
	  erase_next(p_l);
        }
      else
	p_l = p_l->m_p_next;
    }

  _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
  return num_ersd;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
erase_next(entry_pointer p_l)
{
  _GLIBCXX_DEBUG_ASSERT(p_l != NULL);
  _GLIBCXX_DEBUG_ASSERT(p_l != m_p_l);
  _GLIBCXX_DEBUG_ASSERT(p_l->m_p_next != NULL);
  entry_pointer p_next_l = p_l->m_p_next->m_p_next;
  actual_erase_entry(p_l->m_p_next);
  p_l->m_p_next = p_next_l;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
actual_erase_entry(entry_pointer p_l)
{
  _GLIBCXX_DEBUG_ONLY(map_debug_base::erase_existing(PB_DS_V2F(p_l->m_value));)
  p_l->~entry();
  s_entry_allocator.deallocate(p_l, 1);
}


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

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

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

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

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

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

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

/**
 * @file find_fn_imps.hpp
 * Contains implementations of lu_map_.
 */

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::entry_pointer
PB_DS_CLASS_C_DEC::
find_imp(const_key_reference r_key) const
{
  if (m_p_l == NULL)
    return NULL;
  if (s_eq_fn(r_key, PB_DS_V2F(m_p_l->m_value)))
    {
      apply_update(m_p_l, s_metadata_type_indicator);
      _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key);)
      return m_p_l;
    }

  entry_pointer p_l = m_p_l;
  while (p_l->m_p_next != NULL)
    {
      entry_pointer p_next = p_l->m_p_next;
      if (s_eq_fn(r_key, PB_DS_V2F(p_next->m_value)))
        {
	  if (apply_update(p_next, s_metadata_type_indicator))
            {
	      p_l->m_p_next = p_next->m_p_next;
	      p_next->m_p_next = m_p_l;
	      m_p_l = p_next;
	      return m_p_l;
            }
	  return p_next;
        }
      else
	p_l = p_next;
    }

  _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);)
  return NULL;
}

PB_DS_CLASS_T_DEC
template<typename Metadata>
inline bool
PB_DS_CLASS_C_DEC::
apply_update(entry_pointer p_l, type_to_type<Metadata>)
{ return s_update_policy(p_l->m_update_metadata); }

PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
apply_update(entry_pointer, type_to_type<null_lu_metadata>)
{ return s_update_policy(s_null_lu_metadata); }


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 implementations of lu_map_.
 */

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
size() const
{ return std::distance(begin(), end()); }

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

PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
empty() const
{ return (m_p_l == NULL); }


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

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

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

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

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

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

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

/**
 * @file insert_fn_imps.hpp
 * Contains implementations of lu_map_.
 */

PB_DS_CLASS_T_DEC
inline std::pair<
  typename PB_DS_CLASS_C_DEC::point_iterator,
  bool>
PB_DS_CLASS_C_DEC::
insert(const_reference r_val)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  entry_pointer p_l = find_imp(PB_DS_V2F(r_val));

  if (p_l != NULL)
    {
      _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(PB_DS_V2F(r_val));)
      return std::make_pair(point_iterator(&p_l->m_value), false);
    }

  _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(PB_DS_V2F(r_val));)

  p_l = allocate_new_entry(r_val, traits_base::m_no_throw_copies_indicator);
  p_l->m_p_next = m_p_l;
  m_p_l = p_l;
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  return std::make_pair(point_iterator(&p_l->m_value), true);
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::entry_pointer
PB_DS_CLASS_C_DEC::
allocate_new_entry(const_reference r_val, false_type)
{
  entry_pointer p_l = s_entry_allocator.allocate(1);
  cond_dealtor_t cond(p_l);
  new (const_cast<void* >(static_cast<const void* >(&p_l->m_value)))
    value_type(r_val);

  cond.set_no_action();
  _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(r_val));)
  init_entry_metadata(p_l, s_metadata_type_indicator);
  return p_l;
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::entry_pointer
PB_DS_CLASS_C_DEC::
allocate_new_entry(const_reference    r_val, true_type)
{
  entry_pointer p_l = s_entry_allocator.allocate(1);
  new (&p_l->m_value) value_type(r_val);
  _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(r_val));)
  init_entry_metadata(p_l, s_metadata_type_indicator);
  return p_l;
}

PB_DS_CLASS_T_DEC
template<typename Metadata>
inline void
PB_DS_CLASS_C_DEC::
init_entry_metadata(entry_pointer p_l, type_to_type<Metadata>)
{ new (&p_l->m_update_metadata) Metadata(s_update_policy()); }

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
init_entry_metadata(entry_pointer, type_to_type<null_lu_metadata>)
{ }


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

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

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

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

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

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

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

/**
 * @file iterators_fn_imps.hpp
 * Contains implementations of lu_map_.
 */

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::
begin()
{
  if (m_p_l == NULL)
    {
      _GLIBCXX_DEBUG_ASSERT(empty());
      return end();
    }
  return iterator(&m_p_l->m_value, m_p_l, this);
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_iterator
PB_DS_CLASS_C_DEC::
begin() const
{
  if (m_p_l == NULL)
    {
      _GLIBCXX_DEBUG_ASSERT(empty());
      return end();
    }
  return iterator(&m_p_l->m_value, m_p_l, const_cast<PB_DS_CLASS_C_DEC* >(this));
}

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

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_iterator
PB_DS_CLASS_C_DEC::
end() const
{
  return const_iterator(NULL, NULL, const_cast<PB_DS_CLASS_C_DEC* const>(this));
}


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

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

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

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

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

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

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

/**
 * @file lu_map_.hpp
 * Contains a list update map.
 */

#include <utility>
#include <iterator>
#include <ext/pb_ds/detail/cond_dealtor.hpp>
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/detail/types_traits.hpp>
#include <ext/pb_ds/detail/list_update_map_/entry_metadata_base.hpp>
#include <ext/pb_ds/exception.hpp>
#ifdef _GLIBCXX_DEBUG
#include <ext/pb_ds/detail/map_debug_base.hpp>
#endif
#ifdef PB_DS_LU_MAP_TRACE_
#include <iostream>
#endif
#include <debug/debug.h>

namespace pb_ds
{
  namespace detail
  {
#define PB_DS_CLASS_T_DEC \
    template<typename Key, typename Mapped, class Eq_Fn, \
	     class Allocator, class Update_Policy>

#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_CLASS_NAME lu_map_data_
#endif

#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_CLASS_NAME lu_map_no_data_
#endif

#define PB_DS_CLASS_C_DEC \
    PB_DS_CLASS_NAME<Key, Mapped, Eq_Fn, Allocator, Update_Policy>

#define PB_DS_TYPES_TRAITS_C_DEC \
    types_traits<Key, Mapped, Allocator, false>

#ifdef _GLIBCXX_DEBUG
#define PB_DS_MAP_DEBUG_BASE_C_DEC \
    map_debug_base<Key, Eq_Fn, \
	      typename Allocator::template rebind<Key>::other::const_reference>
#endif

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

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

    /* Skip to the lu, my darling. */
    // list-based (with updates) associative container.
    template<typename Key,
	     typename Mapped,
	     class Eq_Fn,
	     class Allocator,
	     class Update_Policy>
    class PB_DS_CLASS_NAME :
#ifdef _GLIBCXX_DEBUG
      protected PB_DS_MAP_DEBUG_BASE_C_DEC,
#endif
      public PB_DS_TYPES_TRAITS_C_DEC
    {
    private:
      typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;

      struct entry
     : public lu_map_entry_metadata_base<typename Update_Policy::metadata_type>
      {
	typename traits_base::value_type m_value;
	typename Allocator::template rebind<entry>::other::pointer m_p_next;
      };

      typedef typename Allocator::template rebind<entry>::other entry_allocator;
      typedef typename entry_allocator::pointer entry_pointer;
      typedef typename entry_allocator::const_pointer const_entry_pointer;
      typedef typename entry_allocator::reference entry_reference;
      typedef typename entry_allocator::const_reference const_entry_reference;

      typedef typename Allocator::template rebind<entry_pointer>::other entry_pointer_allocator;
      typedef typename entry_pointer_allocator::pointer entry_pointer_array;

      typedef typename traits_base::value_type value_type_;
      typedef typename traits_base::pointer pointer_;
      typedef typename traits_base::const_pointer const_pointer_;
      typedef typename traits_base::reference reference_;
      typedef typename traits_base::const_reference const_reference_;

#define PB_DS_GEN_POS entry_pointer

#include <ext/pb_ds/detail/unordered_iterator/const_point_iterator.hpp>
#include <ext/pb_ds/detail/unordered_iterator/point_iterator.hpp>
#include <ext/pb_ds/detail/unordered_iterator/const_iterator.hpp>
#include <ext/pb_ds/detail/unordered_iterator/iterator.hpp>

#undef PB_DS_GEN_POS

#ifdef _GLIBCXX_DEBUG
      typedef PB_DS_MAP_DEBUG_BASE_C_DEC map_debug_base;
#endif

      typedef cond_dealtor<entry, Allocator> cond_dealtor_t;

    public:
      typedef Allocator allocator;
      typedef typename Allocator::size_type size_type;
      typedef typename Allocator::difference_type difference_type;
      typedef Eq_Fn eq_fn;
      typedef Update_Policy update_policy;
      typedef typename Update_Policy::metadata_type update_metadata;
      typedef typename traits_base::key_type key_type;
      typedef typename traits_base::key_pointer key_pointer;
      typedef typename traits_base::const_key_pointer const_key_pointer;
      typedef typename traits_base::key_reference key_reference;
      typedef typename traits_base::const_key_reference const_key_reference;
      typedef typename traits_base::mapped_type mapped_type;
      typedef typename traits_base::mapped_pointer mapped_pointer;
      typedef typename traits_base::const_mapped_pointer const_mapped_pointer;
      typedef typename traits_base::mapped_reference mapped_reference;
      typedef typename traits_base::const_mapped_reference const_mapped_reference;
      typedef typename traits_base::value_type value_type;
      typedef typename traits_base::pointer pointer;
      typedef typename traits_base::const_pointer const_pointer;
      typedef typename traits_base::reference reference;
      typedef typename traits_base::const_reference const_reference;

#ifdef PB_DS_DATA_TRUE_INDICATOR
      typedef point_iterator_ point_iterator;
#endif

#ifdef PB_DS_DATA_FALSE_INDICATOR
      typedef const_point_iterator_ point_iterator;
#endif

      typedef const_point_iterator_ const_point_iterator;

#ifdef PB_DS_DATA_TRUE_INDICATOR
      typedef iterator_ iterator;
#endif

#ifdef PB_DS_DATA_FALSE_INDICATOR
      typedef const_iterator_ iterator;
#endif

      typedef const_iterator_ const_iterator;

    public:
      PB_DS_CLASS_NAME();

      PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);

      virtual
      ~PB_DS_CLASS_NAME();

      template<typename It>
      PB_DS_CLASS_NAME(It first_it, It last_it);

      void
      swap(PB_DS_CLASS_C_DEC&);

      inline size_type
      size() const;

      inline size_type
      max_size() const;

      inline bool
      empty() const;

      inline mapped_reference
      operator[](const_key_reference r_key)
      {
#ifdef PB_DS_DATA_TRUE_INDICATOR
	_GLIBCXX_DEBUG_ONLY(assert_valid();)
	return insert(std::make_pair(r_key, mapped_type())).first->second;
#else
	insert(r_key);
	return traits_base::s_null_mapped;
#endif
      }

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

      inline point_iterator
      find(const_key_reference r_key)
      {
	_GLIBCXX_DEBUG_ONLY(assert_valid();)
	entry_pointer p_e = find_imp(r_key);
	return point_iterator(p_e == NULL ? NULL: &p_e->m_value);
      }

      inline const_point_iterator
      find(const_key_reference r_key) const
      {
	_GLIBCXX_DEBUG_ONLY(assert_valid();)
	entry_pointer p_e = find_imp(r_key);
	return const_point_iterator(p_e == NULL ? NULL: &p_e->m_value);
      }

      inline bool
      erase(const_key_reference);

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

      void
      clear();

      inline iterator
      begin();

      inline const_iterator
      begin() const;

      inline iterator
      end();

      inline const_iterator
      end() const;

#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;
#endif

#ifdef PB_DS_LU_MAP_TRACE_
      void
      trace() const;
#endif

    protected:

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

    private:
#ifdef PB_DS_DATA_TRUE_INDICATOR
      friend class iterator_;
#endif

      friend class const_iterator_;

      inline entry_pointer
      allocate_new_entry(const_reference, false_type);

      inline entry_pointer
      allocate_new_entry(const_reference, true_type);

      template<typename Metadata>
      inline static void
      init_entry_metadata(entry_pointer, type_to_type<Metadata>);

      inline static void
      init_entry_metadata(entry_pointer, type_to_type<null_lu_metadata>);

      void
      deallocate_all();

      void
      erase_next(entry_pointer);

      void
      actual_erase_entry(entry_pointer);

      void
      inc_it_state(const_pointer& r_p_value, entry_pointer& r_pos) const
      {
	r_pos = r_pos->m_p_next;
	r_p_value = (r_pos == NULL) ? NULL : &r_pos->m_value;
      }

      template<typename Metadata>
      inline static bool
      apply_update(entry_pointer, type_to_type<Metadata>);

      inline static bool
      apply_update(entry_pointer, type_to_type<null_lu_metadata>);

      inline entry_pointer
      find_imp(const_key_reference) const;

      static entry_allocator s_entry_allocator;
      static Eq_Fn s_eq_fn;
      static Update_Policy s_update_policy;
      static type_to_type<update_metadata> s_metadata_type_indicator;
      static null_lu_metadata s_null_lu_metadata;

      mutable entry_pointer m_p_l;
    };

#include <ext/pb_ds/detail/list_update_map_/constructor_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/list_update_map_/info_fn_imps.hpp>
#include <ext/pb_ds/detail/list_update_map_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/list_update_map_/iterators_fn_imps.hpp>
#include <ext/pb_ds/detail/list_update_map_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/list_update_map_/find_fn_imps.hpp>
#include <ext/pb_ds/detail/list_update_map_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/list_update_map_/trace_fn_imps.hpp>

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#undef  PB_DS_TYPES_TRAITS_C_DEC
#undef PB_DS_MAP_DEBUG_BASE_C_DEC
#undef PB_DS_CLASS_NAME
#undef PB_DS_V2F
#undef PB_DS_EP2VP
#undef PB_DS_V2S

  } // namespace detail
} // namespace pb_ds


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

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

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

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

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

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

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

/**
 * @file trace_fn_imps.hpp
 * Contains implementations of lu_map_.
 */

#ifdef PB_DS_LU_MAP_TRACE_

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
trace() const
{
  std::cerr << m_p_l << std::endl << std::endl;
  const_entry_pointer p_l = m_p_l;
  while (p_l != NULL)
    {
      std::cerr << PB_DS_V2F(p_l->m_value) << std::endl;
      p_l = p_l->m_p_next;
    }
  std::cerr << std::endl;
}

#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 counter_lu_metadata.hpp
 * Contains implementation of a lu counter policy's metadata.
 */

namespace pb_ds
{
  namespace detail
  {
    template<typename Size_Type>
    class counter_lu_policy_base;

    // A list-update metadata type that moves elements to the front of
    // the list based on the counter algorithm.
    template<typename Size_Type = size_t>
    class counter_lu_metadata
    {
    public:
      typedef Size_Type size_type;

    private:
      counter_lu_metadata(size_type init_count) : m_count(init_count)
      { }

      friend class counter_lu_policy_base<size_type>;

      mutable size_type m_count;
    };

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

      counter_lu_metadata<size_type>
      operator()(size_type max_size) const
      { return counter_lu_metadata<Size_Type>(rand() % max_size); }

      template<typename Metadata_Reference>
      bool
      operator()(Metadata_Reference r_data, size_type m_max_count) const
      {
	if (++r_data.m_count != m_max_count)
	  return false;
	r_data.m_count = 0;
	return true;
      }
    };
  } // namespace detail
} // namespace pb_ds


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

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

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

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

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

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

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

/**
 * @file counter_lu_policy_imp.hpp
 * Contains a lu counter policy implementation.
 */

PB_DS_CLASS_T_DEC
detail::counter_lu_metadata<typename Allocator::size_type>
PB_DS_CLASS_C_DEC::
operator()() const
{ return (base_type::operator()(max_count)); }

PB_DS_CLASS_T_DEC
bool
PB_DS_CLASS_C_DEC::
operator()(metadata_reference r_data) const
{ return (base_type::operator()(r_data, max_count)); }


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 mtf_lu_policy_imp.hpp
 * Contains a move-to-front policy implementation.
 */

PB_DS_CLASS_T_DEC
null_lu_metadata PB_DS_CLASS_C_DEC::s_metadata;

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::metadata_type
PB_DS_CLASS_C_DEC::
operator()() const
{ return s_metadata; }

PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
operator()(metadata_reference /*r_data*/) const
{ return true; }


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

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

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

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

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

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

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

/**
 * @file sample_update_policy.hpp
 * Contains a sample policy for list update containers.
 */

#ifndef PB_DS_SAMPLE_UPDATE_POLICY_HPP
#define PB_DS_SAMPLE_UPDATE_POLICY_HPP

// A sample list-update policy.
struct sample_update_policy
{
  // Default constructor.
  sample_update_policy();

  // Copy constructor.
  sample_update_policy(const sample_update_policy&);

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

protected:
  // Metadata on which this functor operates.
  typedef some_metadata_type metadata_type;

  // Creates a metadata object.
  metadata_type
  operator()() const;

  // Decides whether a metadata object should be moved to the front of
  // the list. A list-update based containers object will call this
  // method to decide whether to move a node to the front of the
  // list. The method shoule return true if the node should be moved
  // to the front of the list.
  bool
  operator()(metadata_reference) const;
};

#endif


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

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

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

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

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

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

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

/**
 * @file map_debug_base.hpp
 * Contains a debug-mode base for all maps.
 */

#ifndef PB_DS_MAP_DEBUG_BASE_HPP
#define PB_DS_MAP_DEBUG_BASE_HPP

#ifdef _GLIBCXX_DEBUG

#include <list>
#include <utility>
#include <ext/throw_allocator.h>
#include <debug/debug.h>

namespace pb_ds
{
  namespace detail
  {

#define PB_DS_CLASS_T_DEC \
    template<typename Key, class Eq_Fn, typename Const_Key_Reference>

#define PB_DS_CLASS_C_DEC \
    map_debug_base<Key, Eq_Fn, Const_Key_Reference>

    template<typename Key, class Eq_Fn, typename Const_Key_Reference>
    class map_debug_base
    {
    private:
      typedef typename std::allocator< Key> key_allocator;

      typedef typename key_allocator::size_type size_type;

      typedef Const_Key_Reference const_key_reference;

    protected:
      map_debug_base();

      map_debug_base(const PB_DS_CLASS_C_DEC& other);

      ~map_debug_base();

      inline void
      insert_new(const_key_reference r_key);

      inline void
      erase_existing(const_key_reference r_key);

      void
      clear();

      inline void
      check_key_exists(const_key_reference r_key) const;

      inline void
      check_key_does_not_exist(const_key_reference r_key) const;

      inline void
      check_size(size_type size) const;

      void
      swap(PB_DS_CLASS_C_DEC& other);

      template<typename Cmp_Fn>
      void
      split(const_key_reference, Cmp_Fn, PB_DS_CLASS_C_DEC&);

      void
      join(PB_DS_CLASS_C_DEC& other);

    private:
      typedef std::list< Key> 			key_set;
      typedef typename key_set::iterator 	key_set_iterator;
      typedef typename key_set::const_iterator 	const_key_set_iterator;

#ifdef _GLIBCXX_DEBUG
      void
      assert_valid() const;
#endif

      const_key_set_iterator
      find(const_key_reference r_key) const;

      key_set_iterator
      find(const_key_reference r_key);

      key_set 	m_key_set;
      Eq_Fn 	m_eq;
    };

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

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    map_debug_base(const PB_DS_CLASS_C_DEC& other) : m_key_set(other.m_key_set)
    { _GLIBCXX_DEBUG_ONLY(assert_valid();) }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ~map_debug_base()
    { _GLIBCXX_DEBUG_ONLY(assert_valid();) }

    PB_DS_CLASS_T_DEC
    inline void
    PB_DS_CLASS_C_DEC::
    insert_new(const_key_reference r_key)
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      __gnu_cxx::throw_allocator<char> alloc;
      const double orig_throw_prob = alloc.get_throw_prob();
      alloc.set_throw_prob(0);
      if (find(r_key) != m_key_set.end())
	{
	  std::cerr << "insert_new " << r_key << std::endl;
	  abort();
	}

      try
	{
	  m_key_set.push_back(r_key);
	}
      catch(...)
	{
	  std::cerr << "insert_new 1" << r_key << std::endl;
	  abort();
	}
      alloc.set_throw_prob(orig_throw_prob);
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

    PB_DS_CLASS_T_DEC
    inline void
    PB_DS_CLASS_C_DEC::
    erase_existing(const_key_reference r_key)
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      key_set_iterator it = find(r_key);
      if (it == m_key_set.end())
	{
	  std::cerr << "erase_existing " << r_key << std::endl;
	  abort();
	}
      m_key_set.erase(it);
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    clear()
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      m_key_set.clear();
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

    PB_DS_CLASS_T_DEC
    inline void
    PB_DS_CLASS_C_DEC::
    check_key_exists(const_key_reference r_key) const
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      if (find(r_key) == m_key_set.end())
        {
          std::cerr << "check_key_exists " << r_key << std::endl;
          abort();
        }
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

    PB_DS_CLASS_T_DEC
    inline void
    PB_DS_CLASS_C_DEC::
    check_key_does_not_exist(const_key_reference r_key) const
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      if (find(r_key) != m_key_set.end())
        {
	  std::cerr << "check_key_does_not_exist " << r_key << std::endl;
          abort();
        }
    }

    PB_DS_CLASS_T_DEC
    inline void
    PB_DS_CLASS_C_DEC::
    check_size(size_type size) const
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      const size_type key_set_size = m_key_set.size();
      if (size != key_set_size)
	{
	  std::cerr << "check_size " << size
		    << " " << key_set_size << std::endl;
	  abort();
	}
      _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();)
      m_key_set.swap(other.m_key_set);
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::const_key_set_iterator
    PB_DS_CLASS_C_DEC::
    find(const_key_reference r_key) const
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      typedef const_key_set_iterator iterator_type;
      for (iterator_type it = m_key_set.begin(); it != m_key_set.end(); ++it)
	if (m_eq(*it, r_key))
          return it;
      return m_key_set.end();
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::key_set_iterator
    PB_DS_CLASS_C_DEC::
    find(const_key_reference r_key)
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      key_set_iterator it = m_key_set.begin();
      while (it != m_key_set.end())
	{
	  if (m_eq(*it, r_key))
            return it;
	  ++it;
	}
      return it;
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
     }

#ifdef _GLIBCXX_DEBUG
    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    assert_valid() const
    {
      const_key_set_iterator prime_it = m_key_set.begin();
      while (prime_it != m_key_set.end())
	{
	  const_key_set_iterator sec_it = prime_it;
	  ++sec_it;
	  while (sec_it != m_key_set.end())
	    {
	      _GLIBCXX_DEBUG_ASSERT(!m_eq(*sec_it, *prime_it));
	      _GLIBCXX_DEBUG_ASSERT(!m_eq(*prime_it, *sec_it));
	      ++sec_it;
	    }
	  ++prime_it;
	}
    }
#endif

    PB_DS_CLASS_T_DEC
    template<typename Cmp_Fn>
    void
    PB_DS_CLASS_C_DEC::
    split(const_key_reference r_key, Cmp_Fn cmp_fn, PB_DS_CLASS_C_DEC& other)
    {
      __gnu_cxx::throw_allocator<char> alloc;
      const double orig_throw_prob = alloc.get_throw_prob();
      alloc.set_throw_prob(0);
      other.clear();
      key_set_iterator it = m_key_set.begin();
      while (it != m_key_set.end())
        if (cmp_fn(r_key, * it))
	  {
            other.insert_new(*it);
            it = m_key_set.erase(it);
	  }
        else
	  ++it;
      alloc.set_throw_prob(orig_throw_prob);
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    join(PB_DS_CLASS_C_DEC& other)
    {
      __gnu_cxx::throw_allocator<char> alloc;
      const double orig_throw_prob = alloc.get_throw_prob();
      alloc.set_throw_prob(0);
      key_set_iterator it = other.m_key_set.begin();
      while (it != other.m_key_set.end())
	{
	  insert_new(*it);
	  it = other.m_key_set.erase(it);
	}
      _GLIBCXX_DEBUG_ASSERT(other.m_key_set.empty());
      alloc.set_throw_prob(orig_throw_prob);
    }

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC

} // namespace detail
} // namespace pb_ds

#endif

#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 cond_dtor.hpp
 * Contains a conditional destructor
 */

template<typename Size_Type>
class cond_dtor
{
public:
  cond_dtor(value_vector a_vec, iterator& r_last_it, Size_Type total_size)
  : m_a_vec(a_vec), m_r_last_it(r_last_it), m_max_size(total_size),
    m_no_action(false)
  { }

  ~cond_dtor()
  {
    if (m_no_action)
      return;
    iterator it = m_a_vec;
    while (it != m_r_last_it)
      {
	it->~value_type();
	++it;
      }

    if (m_max_size > 0)
      value_allocator().deallocate(m_a_vec, m_max_size);
  }

  inline void
  set_no_action()
  { m_no_action = true; }

protected:
  value_vector m_a_vec;
  iterator& m_r_last_it;
  const Size_Type m_max_size;
  bool m_no_action;
};


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 ov_tree_.
 */

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::value_allocator
PB_DS_CLASS_C_DEC::s_value_alloc;

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::metadata_allocator
PB_DS_CLASS_C_DEC::s_metadata_alloc;

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_OV_TREE_CLASS_NAME() :
  m_a_values(NULL),
  m_a_metadata(NULL),
  m_end_it(NULL),
  m_size(0)
{ _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn) :
  cmp_fn_base(r_cmp_fn),
  m_a_values(NULL),
  m_a_metadata(NULL),
  m_end_it(NULL),
  m_size(0)
{ _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) :
  cmp_fn_base(r_cmp_fn),
  node_update(r_node_update),
  m_a_values(NULL),
  m_a_metadata(NULL),
  m_end_it(NULL),
  m_size(0)
{ _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) }

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_OV_TREE_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) :
#ifdef _GLIBCXX_DEBUG
  map_debug_base(other),
#endif
#ifdef PB_DS_TREE_TRACE
  PB_DS_TREE_TRACE_BASE_C_DEC(other),
#endif
  cmp_fn_base(other),
  node_update(other),
  m_a_values(NULL),
  m_a_metadata(NULL),
  m_end_it(NULL),
  m_size(0)
{
  copy_from_ordered_range(other.begin(), other.end());
  _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
}

PB_DS_CLASS_T_DEC
template<typename It>
inline void
PB_DS_CLASS_C_DEC::
copy_from_range(It first_it, It last_it)
{
#ifdef PB_DS_DATA_TRUE_INDICATOR
  typedef
    std::map<
    key_type,
    mapped_type,
    Cmp_Fn,
    typename Allocator::template rebind<
    value_type>::other>
    map_type;
#else
  typedef
    std::set<
    key_type,
    Cmp_Fn,
    typename Allocator::template rebind<
    Key>::other>
    map_type;
#endif

  map_type m(first_it, last_it);
  copy_from_ordered_range(m.begin(), m.end());
}

PB_DS_CLASS_T_DEC
template<typename It>
void
PB_DS_CLASS_C_DEC::
copy_from_ordered_range(It first_it, It last_it)
{
  const size_type len = std::distance(first_it, last_it);
  if (len == 0)
    return;

  value_vector a_values = s_value_alloc.allocate(len);
  iterator target_it = a_values;
  It source_it = first_it;
  It source_end_it = last_it;

  cond_dtor<size_type> cd(a_values, target_it, len);
  while (source_it != source_end_it)
    {
      new (const_cast<void* >(static_cast<const void* >(target_it)))
	value_type(*source_it++);

      ++target_it;
    }

  reallocate_metadata((node_update* )this, len);
  cd.set_no_action();
  m_a_values = a_values;
  m_size = len;
  m_end_it = m_a_values + m_size;
  update(PB_DS_node_begin_imp(), (node_update* )this);

#ifdef _GLIBCXX_DEBUG
  const_iterator dbg_it = m_a_values;
  while (dbg_it != m_end_it)
    {
      map_debug_base::insert_new(PB_DS_V2F(*dbg_it));
      dbg_it++;
    }
  PB_DS_CLASS_C_DEC::assert_valid();
#endif
}

PB_DS_CLASS_T_DEC
template<typename It>
void
PB_DS_CLASS_C_DEC::
copy_from_ordered_range(It first_it, It last_it, It other_first_it,
			It other_last_it)
{
  clear();
  const size_type len = std::distance(first_it, last_it)
    		         + std::distance(other_first_it, other_last_it);

  value_vector a_values = s_value_alloc.allocate(len);

  iterator target_it = a_values;
  It source_it = first_it;
  It source_end_it = last_it;

  cond_dtor<size_type> cd(a_values, target_it, len);
  while (source_it != source_end_it)
    {
      new (const_cast<void* >(static_cast<const void* >(target_it)))
	value_type(*source_it++);
      ++target_it;
    }

  source_it = other_first_it;
  source_end_it = other_last_it;

  while (source_it != source_end_it)
    {
      new (const_cast<void* >(static_cast<const void* >(target_it)))
	value_type(*source_it++);
      ++target_it;
    }

  reallocate_metadata((node_update* )this, len);
  cd.set_no_action();
  m_a_values = a_values;
  m_size = len;
  m_end_it = m_a_values + m_size;
  update(PB_DS_node_begin_imp(), (node_update* )this);

#ifdef _GLIBCXX_DEBUG
  const_iterator dbg_it = m_a_values;
  while (dbg_it != m_end_it)
    {
      map_debug_base::insert_new(PB_DS_V2F(*dbg_it));
      dbg_it++;
    }
  PB_DS_CLASS_C_DEC::assert_valid();
#endif
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  value_swap(other);
  std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )other);
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
value_swap(PB_DS_CLASS_C_DEC& other)
{
  std::swap(m_a_values, other.m_a_values);
  std::swap(m_a_metadata, other.m_a_metadata);
  std::swap(m_size, other.m_size);
  std::swap(m_end_it, other.m_end_it);
  _GLIBCXX_DEBUG_ONLY(map_debug_base::swap(other);)
}

PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~PB_DS_OV_TREE_CLASS_NAME()
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  cond_dtor<size_type> cd(m_a_values, m_end_it, m_size);
  reallocate_metadata((node_update* )this, 0);
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
update(node_iterator /*it*/, null_node_update_pointer)
{ }

PB_DS_CLASS_T_DEC
template<typename Node_Update>
void
PB_DS_CLASS_C_DEC::
update(node_iterator nd_it, Node_Update* p_update)
{
  const_node_iterator end_it = PB_DS_node_end_imp();
  if (nd_it == end_it)
    return;
  update(nd_it.get_l_child(), p_update);
  update(nd_it.get_r_child(), p_update);
  node_update::operator()(nd_it, end_it);
}