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

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

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

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

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

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

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

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

#ifdef _GLIBCXX_DEBUG

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid() const
{
  if (m_p_head->m_p_parent != NULL)
    m_p_head->m_p_parent->assert_valid(this);
  assert_iterators();
  assert_reverse_iterators();
  if (m_p_head->m_p_parent == NULL)
    {
      _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_min == m_p_head);
      _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_max == m_p_head);
      _GLIBCXX_DEBUG_ASSERT(empty());
      return;
    }

  _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_min->m_type == pat_trie_leaf_node_type);
  _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_max->m_type == pat_trie_leaf_node_type);
  _GLIBCXX_DEBUG_ASSERT(!empty());
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_iterators() const
{
  size_type calc_size = 0;
  for (const_iterator it = begin(); it != end(); ++it)
    {
      ++calc_size;
      map_debug_base::check_key_exists(PB_DS_V2F(*it));
      _GLIBCXX_DEBUG_ASSERT(lower_bound(PB_DS_V2F(*it)) == it);
      _GLIBCXX_DEBUG_ASSERT(--upper_bound(PB_DS_V2F(*it)) == it);
    }
  _GLIBCXX_DEBUG_ASSERT(calc_size == m_size);
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_reverse_iterators() const
{
  size_type calc_size = 0;
  for (const_reverse_iterator it = rbegin(); it != rend(); ++it)
    {
      ++calc_size;
      const_node_pointer p_nd =
	const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(PB_DS_V2F(*it));
      _GLIBCXX_DEBUG_ASSERT(p_nd == it.m_p_nd);
    }
  _GLIBCXX_DEBUG_ASSERT(calc_size == m_size);
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
recursive_count_leafs(const_node_pointer p_nd)
{
  if (p_nd == NULL)
    return (0);
  if (p_nd->m_type == pat_trie_leaf_node_type)
    return (1);
  _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type);
  size_type ret = 0;
  for (typename internal_node::const_iterator it =
	 static_cast<const_internal_node_pointer>(p_nd)->begin();
       it != static_cast<const_internal_node_pointer>(p_nd)->end();
       ++it)
    ret += recursive_count_leafs(*it);
  return ret;
}

#endif


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

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

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

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

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

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

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

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

PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
erase(const_key_reference r_key)
{
  node_pointer p_nd = find_imp(r_key);
  if (p_nd == NULL || p_nd->m_type == pat_trie_internal_node_type)
    {
      _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key));
      return false;
    }

  _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type);
  if (!synth_e_access_traits::equal_keys(PB_DS_V2F(reinterpret_cast<leaf_pointer>(p_nd)->value()), r_key))
    {
      _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key));
      return false;
    }

  _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key));
  erase_leaf(static_cast<leaf_pointer>(p_nd));
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  return true;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
erase_fixup(internal_node_pointer p_nd)
{
  _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) >= 1);
  if (std::distance(p_nd->begin(), p_nd->end()) == 1)
    {
      node_pointer p_parent = p_nd->m_p_parent;
      if (p_parent == m_p_head)
	m_p_head->m_p_parent =* p_nd->begin();
      else
        {
	  _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type);
	  node_pointer p_new_child =* p_nd->begin();
	  static_cast<internal_node_pointer>(p_parent)->replace_child(
								      p_new_child,
								      pref_begin(p_new_child),
								      pref_end(p_new_child),
								      this);
        }
      (*p_nd->begin())->m_p_parent = p_nd->m_p_parent;
      p_nd->~internal_node();
      s_internal_node_allocator.deallocate(p_nd, 1);

      if (p_parent == m_p_head)
	return;

      _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type);
      p_nd = static_cast<internal_node_pointer>(p_parent);
    }

  while (true)
    {
      _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) > 1);
      p_nd->update_prefixes(this);
      apply_update(p_nd, (node_update* )this);
      _GLIBCXX_DEBUG_ONLY(p_nd->assert_valid(this);)
      if (p_nd->m_p_parent->m_type == pat_trie_head_node_type)
        return;

      _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent->m_type ==
		       pat_trie_internal_node_type);

      p_nd = static_cast<internal_node_pointer>(p_nd->m_p_parent);
    }
}

PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
actual_erase_leaf(leaf_pointer p_l)
{
  _GLIBCXX_DEBUG_ASSERT(m_size > 0);
  --m_size;
  _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_l->value())));
  p_l->~leaf();
  s_leaf_allocator.deallocate(p_l, 1);
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
clear()
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  if (empty())
    return;

  clear_imp(m_p_head->m_p_parent);
  m_size = 0;
  initialize();
  _GLIBCXX_DEBUG_ONLY(map_debug_base::clear();)
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
clear_imp(node_pointer p_nd)
{
  if (p_nd->m_type == pat_trie_internal_node_type)
    {
      _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type);
      for (typename internal_node::iterator it =
	     static_cast<internal_node_pointer>(p_nd)->begin();
	   it != static_cast<internal_node_pointer>(p_nd)->end();
	   ++it)
        {
	  node_pointer p_child =* it;
	  clear_imp(p_child);
        }
      s_internal_node_allocator.deallocate(static_cast<internal_node_pointer>(p_nd), 1);
      return;
    }

  _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type);
  static_cast<leaf_pointer>(p_nd)->~leaf();
  s_leaf_allocator.deallocate(static_cast<leaf_pointer>(p_nd), 1);
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_iterator
PB_DS_CLASS_C_DEC::
erase(const_iterator it)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid());

  if (it == end())
    return it;

  const_iterator ret_it = it;
  ++ret_it;
  _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type);
  erase_leaf(static_cast<leaf_pointer>(it.m_p_nd));
  _GLIBCXX_DEBUG_ONLY(assert_valid());
  return ret_it;
}

#ifdef PB_DS_DATA_TRUE_INDICATOR
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::
erase(iterator it)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid());

  if (it == end())
    return it;
  iterator ret_it = it;
  ++ret_it;
  _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type);
  erase_leaf(static_cast<leaf_pointer>(it.m_p_nd));
  _GLIBCXX_DEBUG_ONLY(assert_valid());
  return ret_it;
}
#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator
PB_DS_CLASS_C_DEC::
erase(const_reverse_iterator it)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid());

  if (it.m_p_nd == m_p_head)
    return it;
  const_reverse_iterator ret_it = it;
  ++ret_it;

  _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type);
  erase_leaf(static_cast<leaf_pointer>(it.m_p_nd));
  _GLIBCXX_DEBUG_ONLY(assert_valid());
  return ret_it;
}

#ifdef PB_DS_DATA_TRUE_INDICATOR
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::reverse_iterator
PB_DS_CLASS_C_DEC::
erase(reverse_iterator it)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid());

  if (it.m_p_nd == m_p_head)
    return it;
  reverse_iterator ret_it = it;
  ++ret_it;

  _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type);
  erase_leaf(static_cast<leaf_pointer>(it.m_p_nd));
  _GLIBCXX_DEBUG_ONLY(assert_valid());
  return ret_it;
}
#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR

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)
{
  size_type num_ersd = 0;
  _GLIBCXX_DEBUG_ONLY(assert_valid();)

  iterator it = begin();
  while (it != end())
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
        if (pred(*it))
	  {
            ++num_ersd;
            it = erase(it);
	  }
        else
	  ++it;
    }

  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  return num_ersd;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
erase_leaf(leaf_pointer p_l)
{
  update_min_max_for_erased_leaf(p_l);
  if (p_l->m_p_parent->m_type == pat_trie_head_node_type)
    {
      _GLIBCXX_DEBUG_ASSERT(size() == 1);
      clear();
      return;
    }

  _GLIBCXX_DEBUG_ASSERT(size() > 1);
  _GLIBCXX_DEBUG_ASSERT(p_l->m_p_parent->m_type ==
		   pat_trie_internal_node_type);

  internal_node_pointer p_parent =
    static_cast<internal_node_pointer>(p_l->m_p_parent);

  p_parent->remove_child(p_l);
  erase_fixup(p_parent);
  actual_erase_leaf(p_l);
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
update_min_max_for_erased_leaf(leaf_pointer p_l)
{
  if (m_size == 1)
    {
      m_p_head->m_p_min = m_p_head;
      m_p_head->m_p_max = m_p_head;
      return;
    }

  if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_min))
    {
      iterator it(p_l);
      ++it;
      m_p_head->m_p_min = it.m_p_nd;
      return;
    }

  if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_max))
    {
      iterator it(p_l);
      --it;
      m_p_head->m_p_max = it.m_p_nd;
    }
}

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 find_fn_imps.hpp
 * Contains an implementation class for bin_search_tree_.
 */

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::point_iterator
PB_DS_CLASS_C_DEC::
find(const_key_reference r_key)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  node_pointer p_nd = find_imp(r_key);

  if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type)
    {
      _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);)
      return end();
    }

  if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_nd)->value()), r_key))
    {
      _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key));
      return iterator(p_nd);
    }

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

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_point_iterator
PB_DS_CLASS_C_DEC::
find(const_key_reference r_key) const
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)

  const_node_pointer p_nd = const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(r_key);

  if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type)
    {
      _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_does_not_exist(r_key);)
      return end();
    }

  if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key))
    {
      _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(r_key));
      return const_iterator(const_cast<node_pointer>(p_nd));
    }

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

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
find_imp(const_key_reference r_key)
{
  if (empty())
    return (NULL);

  typename synth_e_access_traits::const_iterator b_it =
    synth_e_access_traits::begin(r_key);
  typename synth_e_access_traits::const_iterator e_it =
    synth_e_access_traits::end(r_key);

  node_pointer p_nd = m_p_head->m_p_parent;
  _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);

  while (p_nd->m_type != pat_trie_leaf_node_type)
    {
      _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type);
      node_pointer p_next_nd = static_cast<internal_node_pointer>(p_nd)->get_child_node(b_it,  e_it,  this);

      if (p_next_nd == NULL)
	return p_nd;
      p_nd = p_next_nd;
    }
  return p_nd;
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
lower_bound_imp(const_key_reference r_key)
{
  if (empty())
    return (m_p_head);

  node_pointer p_nd = m_p_head->m_p_parent;
  _GLIBCXX_DEBUG_ASSERT(p_nd != NULL);

  typename PB_DS_CLASS_C_DEC::const_e_iterator b_it =
    synth_e_access_traits::begin(r_key);

  typename PB_DS_CLASS_C_DEC::const_e_iterator e_it =
    synth_e_access_traits::end(r_key);

  size_type checked_ind = 0;
  while (true)
    {
      if (p_nd->m_type == pat_trie_leaf_node_type)
        {
	  if (!synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key))
	    return p_nd;
	  iterator it(p_nd);
	  ++it;
	  return it.m_p_nd;
        }

      _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type);
      const size_type new_checked_ind =
	static_cast<internal_node_pointer>(p_nd)->get_e_ind();

      p_nd =
	static_cast<internal_node_pointer>(p_nd)->get_lower_bound_child_node(                b_it, e_it, checked_ind, this);
      checked_ind = new_checked_ind;
    }
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::point_iterator
PB_DS_CLASS_C_DEC::
lower_bound(const_key_reference r_key)
{ return point_iterator(lower_bound_imp(r_key)); }

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_point_iterator
PB_DS_CLASS_C_DEC::
lower_bound(const_key_reference r_key) const
{
  return const_point_iterator(const_cast<PB_DS_CLASS_C_DEC* >(this)->lower_bound_imp(r_key));
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::point_iterator
PB_DS_CLASS_C_DEC::
upper_bound(const_key_reference r_key)
{
  point_iterator l_bound_it = lower_bound(r_key);

  _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() ||
		   !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it),
						    r_key));

  if (l_bound_it == end() ||
      synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it)))
    return l_bound_it;

  return ++l_bound_it;
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_point_iterator
PB_DS_CLASS_C_DEC::
upper_bound(const_key_reference r_key) const
{
  const_point_iterator l_bound_it = lower_bound(r_key);

  _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() ||
		   !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it),
						    r_key));

  if (l_bound_it == end() ||
      synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it)))
    return l_bound_it;
  return ++l_bound_it;
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_e_iterator
PB_DS_CLASS_C_DEC::
pref_begin(const_node_pointer p_nd)
{
  if (p_nd->m_type == pat_trie_leaf_node_type)
    return (synth_e_access_traits::begin(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value())));

  _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type);
  return static_cast<const_internal_node_pointer>(p_nd)->pref_b_it();
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_e_iterator
PB_DS_CLASS_C_DEC::
pref_end(const_node_pointer p_nd)
{
  if (p_nd->m_type == pat_trie_leaf_node_type)
    return (synth_e_access_traits::end(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value())));

  _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type);
  return static_cast<const_internal_node_pointer>(p_nd)->pref_e_it();
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_leaf_pointer
PB_DS_CLASS_C_DEC::
leftmost_descendant(const_node_pointer p_nd)
{
  if (p_nd->m_type == pat_trie_leaf_node_type)
    return static_cast<const_leaf_pointer>(p_nd);
  return static_cast<const_internal_node_pointer>(p_nd)->leftmost_descendant();
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::leaf_pointer
PB_DS_CLASS_C_DEC::
leftmost_descendant(node_pointer p_nd)
{
  if (p_nd->m_type == pat_trie_leaf_node_type)
    return static_cast<leaf_pointer>(p_nd);
  return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant();
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_leaf_pointer
PB_DS_CLASS_C_DEC::
rightmost_descendant(const_node_pointer p_nd)
{
  if (p_nd->m_type == pat_trie_leaf_node_type)
    return static_cast<const_leaf_pointer>(p_nd);
  return static_cast<const_internal_node_pointer>(p_nd)->rightmost_descendant();
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::leaf_pointer
PB_DS_CLASS_C_DEC::
rightmost_descendant(node_pointer p_nd)
{
  if (p_nd->m_type == pat_trie_leaf_node_type)
    return static_cast<leaf_pointer>(p_nd);
  return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant();
}


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 head.hpp
 * Contains a leaf for a patricia tree.
 */

#ifndef PB_DS_PAT_TRIE_IHEAD_HPP
#define PB_DS_PAT_TRIE_IHEAD_HPP

#include <ext/pb_ds/detail/pat_trie_/node_base.hpp>
#include <debug/debug.h>

namespace pb_ds
{
  namespace detail
  {
#define PB_DS_CLASS_T_DEC \
    template<typename Type_Traits, typename E_Access_Traits,	\
	      typename Metadata, typename Allocator>

#define PB_DS_CLASS_C_DEC \
    pat_trie_head<Type_Traits, E_Access_Traits,	Metadata, Allocator>

#define PB_DS_BASE_C_DEC \
    pat_trie_node_base<Type_Traits, E_Access_Traits, Metadata, Allocator>

    template<typename Type_Traits,
	     typename E_Access_Traits,
	     typename Metadata,
	     typename Allocator>
    struct pat_trie_head : public PB_DS_BASE_C_DEC
    {
    private:
      typedef E_Access_Traits e_access_traits;

      typedef
      typename Allocator::template rebind<
	e_access_traits>::other::const_pointer
      const_e_access_traits_pointer;

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

#ifdef _GLIBCXX_DEBUG
      typedef
      typename PB_DS_BASE_C_DEC::subtree_debug_info
      subtree_debug_info;
#endif

    public:
      pat_trie_head();

#ifdef _GLIBCXX_DEBUG
      virtual subtree_debug_info
      assert_valid_imp(const_e_access_traits_pointer p_traits) const;
#endif

    public:
      node_pointer m_p_min;

      node_pointer m_p_max;
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    pat_trie_head() : PB_DS_BASE_C_DEC(pat_trie_head_node_type)
    { }

#ifdef _GLIBCXX_DEBUG
    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::subtree_debug_info
    PB_DS_CLASS_C_DEC::
    assert_valid_imp(const_e_access_traits_pointer /*p_traits*/) const
    {
      _GLIBCXX_DEBUG_ASSERT(false);
      return subtree_debug_info();
    }
#endif

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_BASE_C_DEC

  } // namespace detail
} // namespace pb_ds

#endif


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

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

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

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

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

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

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

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

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

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

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


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

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

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

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

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

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

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

/**
 * @file insert_join_fn_imps.hpp
 * Contains an implementation class for bin_search_tree_.
 */

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
join(PB_DS_CLASS_C_DEC& other)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid(););
  _GLIBCXX_DEBUG_ONLY(other.assert_valid(););
  split_join_branch_bag bag;
  if (!join_prep(other, bag))
    {
      _GLIBCXX_DEBUG_ONLY(assert_valid(););
      _GLIBCXX_DEBUG_ONLY(other.assert_valid(););
      return;
    }

  m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent,
				  other.m_p_head->m_p_parent, 0, bag);

  m_p_head->m_p_parent->m_p_parent = m_p_head;
  m_size += other.m_size;
  other.initialize();
  _GLIBCXX_DEBUG_ONLY(other.assert_valid(););
  m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent);
  m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent);
  _GLIBCXX_DEBUG_ONLY(assert_valid(););
}

PB_DS_CLASS_T_DEC
bool
PB_DS_CLASS_C_DEC::
join_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag)
{
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  _GLIBCXX_DEBUG_ONLY(other.assert_valid();)
  if (other.m_size == 0)
    return false;

  if (m_size == 0)
    {
      value_swap(other);
      return false;
    }

  const bool greater = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(
												 m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast<const_leaf_pointer>(
												 other.m_p_head->m_p_min)->value()));

  const bool lesser = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(
												other.m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value()));

  if (!greater && !lesser)
    __throw_join_error();

  rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag);
  _GLIBCXX_DEBUG_ONLY(map_debug_base::join(other);)
  return true;
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
rec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag)
{
  if (p_l->m_type == pat_trie_leaf_node_type)
    {
      if (p_r->m_type == pat_trie_leaf_node_type)
        {
	  rec_join_prep(static_cast<const_leaf_pointer>(p_l),
			static_cast<const_leaf_pointer>(p_r), r_bag);
	  return;
        }

      _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
      rec_join_prep(static_cast<const_leaf_pointer>(p_l),
		    static_cast<const_internal_node_pointer>(p_r), r_bag);
      return;
    }

  _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type);
  if (p_r->m_type == pat_trie_leaf_node_type)
    {
      rec_join_prep(static_cast<const_internal_node_pointer>(p_l),
		    static_cast<const_leaf_pointer>(p_r), r_bag);
      return;
    }

  _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type);

  rec_join_prep(static_cast<const_internal_node_pointer>(p_l),
		static_cast<const_internal_node_pointer>(p_r), r_bag);
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
rec_join_prep(const_leaf_pointer /*p_l*/, const_leaf_pointer /*p_r*/,
	      split_join_branch_bag& r_bag)
{ r_bag.add_branch(); }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
rec_join_prep(const_leaf_pointer /*p_l*/, const_internal_node_pointer /*p_r*/,
	      split_join_branch_bag& r_bag)
{ r_bag.add_branch(); }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
rec_join_prep(const_internal_node_pointer /*p_l*/, const_leaf_pointer /*p_r*/,
	      split_join_branch_bag& r_bag)
{ r_bag.add_branch(); }

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
rec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r,
	      split_join_branch_bag& r_bag)
{
  if (p_l->get_e_ind() == p_r->get_e_ind() &&
      synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(),
					    p_r->pref_b_it(), p_r->pref_e_it()))
    {
      for (typename internal_node::const_iterator it = p_r->begin();
	   it != p_r->end(); ++ it)
        {
	  const_node_pointer p_l_join_child = p_l->get_join_child(*it, this);
	  if (p_l_join_child != NULL)
	    rec_join_prep(p_l_join_child, * it, r_bag);
        }
      return;
    }

  if (p_r->get_e_ind() < p_l->get_e_ind() &&
      p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
    {
      const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this);
      if (p_r_join_child != NULL)
	rec_join_prep(p_r_join_child, p_l, r_bag);
      return;
    }

  if (p_r->get_e_ind() < p_l->get_e_ind() &&
      p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
    {
      const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this);
      if (p_r_join_child != NULL)
	rec_join_prep(p_r_join_child, p_l, r_bag);
      return;
    }
  r_bag.add_branch();
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag)
{
  _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
  if (p_l == NULL)
    {
      apply_update(p_r, (node_update* )this);
      return (p_r);
    }

  if (p_l->m_type == pat_trie_leaf_node_type)
    {
      if (p_r->m_type == pat_trie_leaf_node_type)
        {
	  node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l),
					static_cast<leaf_pointer>(p_r), r_bag);
	  apply_update(p_ret, (node_update* )this);
	  return p_ret;
        }

      _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
      node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l),
				    static_cast<internal_node_pointer>(p_r),
				    checked_ind, r_bag);
      apply_update(p_ret, (node_update* )this);
      return p_ret;
    }

  _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type);
  if (p_r->m_type == pat_trie_leaf_node_type)
    {
      node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l),
				    static_cast<leaf_pointer>(p_r),
				    checked_ind, r_bag);
      apply_update(p_ret, (node_update* )this);
      return p_ret;
    }

  _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type);
  node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l),
				static_cast<internal_node_pointer>(p_r),
				r_bag);

  apply_update(p_ret, (node_update* )this);
  return p_ret;
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
rec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag)
{
  _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
  if (p_l == NULL)
    return (p_r);
  node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
  _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == 2);
  return p_ret;
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
rec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind,
	 split_join_branch_bag& r_bag)
{
#ifdef _GLIBCXX_DEBUG
  const size_type lhs_leafs = recursive_count_leafs(p_l);
  const size_type rhs_leafs = recursive_count_leafs(p_r);
#endif

  _GLIBCXX_DEBUG_ASSERT(p_r != NULL);
  node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag);
  _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs);
  return p_ret;
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
rec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag)
{
  _GLIBCXX_DEBUG_ASSERT(p_l != NULL);
  _GLIBCXX_DEBUG_ASSERT(p_r != NULL);

#ifdef _GLIBCXX_DEBUG
  const size_type lhs_leafs = recursive_count_leafs(p_l);
  const size_type rhs_leafs = recursive_count_leafs(p_r);
#endif

  if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this))
    {
      node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
      _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);)
      _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) ==
       		            lhs_leafs + rhs_leafs);
      return p_ret;
    }

  node_pointer p_pot_child = p_l->add_child(p_r, pref_begin(p_r),
					    pref_end(p_r), this);
  if (p_pot_child != p_r)
    {
      node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(),
					  r_bag);

      p_l->replace_child(p_new_child, pref_begin(p_new_child),
			 pref_end(p_new_child), this);
    }

  _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this));
  _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs);
  return p_l;
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
rec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag)
{
  _GLIBCXX_DEBUG_ASSERT(p_l != NULL);
  _GLIBCXX_DEBUG_ASSERT(p_r != NULL);

#ifdef _GLIBCXX_DEBUG
  const size_type lhs_leafs = recursive_count_leafs(p_l);
  const size_type rhs_leafs = recursive_count_leafs(p_r);
#endif

  if (p_l->get_e_ind() == p_r->get_e_ind() &&
      synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(),
					    p_r->pref_b_it(), p_r->pref_e_it()))
    {
      for (typename internal_node::iterator it = p_r->begin();
	   it != p_r->end(); ++ it)
        {
	  node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this),
					      * it, 0, r_bag);
	  p_l->replace_child(p_new_child, pref_begin(p_new_child),
			     pref_end(p_new_child), this);
        }

      p_r->~internal_node();
      s_internal_node_allocator.deallocate(p_r, 1);
      _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);)
      _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs);
      return p_l;
    }

  if (p_l->get_e_ind() < p_r->get_e_ind() &&
      p_l->should_be_mine(p_r->pref_b_it(), p_r->pref_e_it(), 0, this))
    {
      node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this),
					  p_r, 0, r_bag);
      p_l->replace_child(p_new_child, pref_begin(p_new_child),
			 pref_end(p_new_child), this);
      _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);)
      return p_l;
    }

  if (p_r->get_e_ind() < p_l->get_e_ind() &&
      p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this))
    {
      node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l,
					  0, r_bag);

      p_r->replace_child(p_new_child, pref_begin(p_new_child),
			 pref_end(p_new_child), this);

      _GLIBCXX_DEBUG_ONLY(p_r->assert_valid(this);)
      _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_r) == lhs_leafs + rhs_leafs);
      return p_r;
    }

  node_pointer p_ret = insert_branch(p_l, p_r, r_bag);
  _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);)
  _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs);
  return p_ret;
}

PB_DS_CLASS_T_DEC
inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool>
PB_DS_CLASS_C_DEC::
insert(const_reference r_val)
{
  node_pointer p_lf = find_imp(PB_DS_V2F(r_val));
  if (p_lf != NULL && p_lf->m_type == pat_trie_leaf_node_type &&
      synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()), PB_DS_V2F(r_val)))
    {
      _GLIBCXX_DEBUG_ONLY(map_debug_base::check_key_exists(PB_DS_V2F(r_val)));
      _GLIBCXX_DEBUG_ONLY(assert_valid();)
      return std::make_pair(iterator(p_lf), false);
    }

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

  leaf_pointer p_new_lf = s_leaf_allocator.allocate(1);
  cond_dealtor cond(p_new_lf);

  new (p_new_lf) leaf(r_val);
  apply_update(p_new_lf, (node_update* )this);
  cond.set_call_destructor();
  split_join_branch_bag bag;
  bag.add_branch();
  m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag);
  m_p_head->m_p_parent->m_p_parent = m_p_head;
  cond.set_no_action_dtor();
  ++m_size;
  update_min_max_for_inserted_leaf(p_new_lf);
  _GLIBCXX_DEBUG_ONLY(map_debug_base::insert_new(PB_DS_V2F(r_val));)
  _GLIBCXX_DEBUG_ONLY(assert_valid();)
  return std::make_pair(point_iterator(p_new_lf), true);
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
keys_diff_ind(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r)
{
  size_type diff_pos = 0;
  while (b_l != e_l)
    {
      if (b_r == e_r)
	return (diff_pos);
      if (e_access_traits::e_pos(*b_l) != e_access_traits::e_pos(*b_r))
	return (diff_pos);
      ++b_l;
      ++b_r;
      ++diff_pos;
    }
  _GLIBCXX_DEBUG_ASSERT(b_r != e_r);
  return diff_pos;
}

PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::internal_node_pointer
PB_DS_CLASS_C_DEC::
insert_branch(node_pointer p_l, node_pointer p_r, split_join_branch_bag& r_bag)
{
  typename synth_e_access_traits::const_iterator left_b_it = pref_begin(p_l);
  typename synth_e_access_traits::const_iterator left_e_it = pref_end(p_l);
  typename synth_e_access_traits::const_iterator right_b_it = pref_begin(p_r);
  typename synth_e_access_traits::const_iterator right_e_it = pref_end(p_r);

  const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it,
					   right_b_it, right_e_it);

  internal_node_pointer p_new_nd = r_bag.get_branch();
  new (p_new_nd) internal_node(diff_ind, left_b_it);
  p_new_nd->add_child(p_l, left_b_it, left_e_it, this);
  p_new_nd->add_child(p_r, right_b_it, right_e_it, this);
  p_l->m_p_parent = p_new_nd;
  p_r->m_p_parent = p_new_nd;
  _GLIBCXX_DEBUG_ONLY(p_new_nd->assert_valid(this);)
  return (p_new_nd);
}

PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
update_min_max_for_inserted_leaf(leaf_pointer p_new_lf)
{
  if (m_p_head->m_p_min == m_p_head ||
      synth_e_access_traits::cmp_keys(PB_DS_V2F(p_new_lf->value()),
				      PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value())))
    m_p_head->m_p_min = p_new_lf;

  if (m_p_head->m_p_max == m_p_head ||
      synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_max)->value()), PB_DS_V2F(p_new_lf->value())))
    m_p_head->m_p_max = p_new_lf;
}


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 internal_node.hpp
 * Contains an internal PB_DS_BASE_C_DEC for a patricia tree.
 */

#ifndef PB_DS_PAT_TRIE_INTERNAL_NODE_HPP
#define PB_DS_PAT_TRIE_INTERNAL_NODE_HPP

#include <debug/debug.h>

namespace pb_ds
{
  namespace detail
  {
#define PB_DS_CLASS_T_DEC \
    template<typename Type_Traits, typename E_Access_Traits,  \
	     typename Metadata, typename Allocator>

#define PB_DS_CLASS_C_DEC \
    pat_trie_internal_node<Type_Traits, E_Access_Traits, Metadata, Allocator>

#define PB_DS_BASE_C_DEC \
    pat_trie_node_base<Type_Traits, E_Access_Traits, Metadata, Allocator>

#define PB_DS_LEAF_C_DEC \
    pat_trie_leaf<Type_Traits, E_Access_Traits, Metadata, Allocator>

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

    template<typename Type_Traits,
	     typename E_Access_Traits,
	     typename Metadata,
	     typename Allocator>
    struct pat_trie_internal_node : public PB_DS_BASE_C_DEC
    {
    private:
      typedef PB_DS_BASE_C_DEC 			base_type;
      typedef Type_Traits 			type_traits;
      typedef typename type_traits::value_type 	value_type;
      typedef typename Allocator::size_type 	size_type;

      typedef E_Access_Traits e_access_traits;
      typedef typename e_access_traits::const_iterator const_e_iterator;
      typedef typename Allocator::template rebind<e_access_traits>::other access_rebind;
      typedef typename access_rebind::const_pointer const_e_access_traits_pointer;

      typedef typename Allocator::template rebind<base_type>::other base_rebind;
      typedef typename base_rebind::pointer node_pointer;
      typedef typename base_rebind::const_pointer const_node_pointer;

      typedef PB_DS_LEAF_C_DEC leaf;
      typedef typename Allocator::template rebind<leaf>::other leaf_rebind;
      typedef typename leaf_rebind::pointer leaf_pointer;
      typedef typename leaf_rebind::const_pointer const_leaf_pointer;

      typedef typename Allocator::template rebind<pat_trie_internal_node>::other internal_node_rebind;
      typedef typename internal_node_rebind::pointer internal_node_pointer;
      typedef typename internal_node_rebind::const_pointer const_internal_node_pointer;

#ifdef _GLIBCXX_DEBUG
      typedef typename base_type::subtree_debug_info subtree_debug_info;

      virtual subtree_debug_info
      assert_valid_imp(const_e_access_traits_pointer) const;
#endif

      inline size_type
      get_pref_pos(const_e_iterator, const_e_iterator,
		   const_e_access_traits_pointer) const;

    public:
      typedef typename Allocator::template rebind<node_pointer>::other node_pointer_rebind;
      typedef typename node_pointer_rebind::pointer node_pointer_pointer;
      typedef typename node_pointer_rebind::reference node_pointer_reference;

      enum
	{
	  arr_size = E_Access_Traits::max_size + 1
	};
      PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2);

#include <ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp>
#include <ext/pb_ds/detail/pat_trie_/child_iterator.hpp>

      pat_trie_internal_node(size_type, const const_e_iterator);

      void
      update_prefixes(const_e_access_traits_pointer);

      const_iterator
      begin() const;

      iterator
      begin();

      const_iterator
      end() const;

      iterator
      end();

      inline node_pointer
      get_child_node(const_e_iterator, const_e_iterator,
		     const_e_access_traits_pointer);

      inline const_node_pointer
      get_child_node(const_e_iterator, const_e_iterator,
		     const_e_access_traits_pointer) const;

      inline iterator
      get_child_it(const_e_iterator, const_e_iterator,
		   const_e_access_traits_pointer);

      inline node_pointer
      get_lower_bound_child_node(const_e_iterator, const_e_iterator,
				 size_type, const_e_access_traits_pointer);

      inline node_pointer
      add_child(node_pointer, const_e_iterator, const_e_iterator,
		const_e_access_traits_pointer);

      inline const_node_pointer
      get_join_child(const_node_pointer, const_e_access_traits_pointer) const;

      inline node_pointer
      get_join_child(node_pointer, const_e_access_traits_pointer);

      void
      remove_child(node_pointer p_nd);

      iterator
      remove_child(iterator it);

      void
      replace_child(node_pointer, const_e_iterator, const_e_iterator,
		    const_e_access_traits_pointer);

      inline const_e_iterator
      pref_b_it() const;

      inline const_e_iterator
      pref_e_it() const;

      inline size_type
      get_e_ind() const;

      bool
      should_be_mine(const_e_iterator, const_e_iterator, size_type,
		     const_e_access_traits_pointer) const;

      leaf_pointer
      leftmost_descendant();

      const_leaf_pointer
      leftmost_descendant() const;

      leaf_pointer
      rightmost_descendant();

      const_leaf_pointer
      rightmost_descendant() const;

#ifdef _GLIBCXX_DEBUG
      size_type
      e_ind() const;
#endif

    private:
      pat_trie_internal_node(const pat_trie_internal_node&);

      size_type
      get_begin_pos() const;

      const size_type m_e_ind;
      const_e_iterator m_pref_b_it;
      const_e_iterator m_pref_e_it;
      node_pointer m_a_p_children[arr_size];
      static leaf_rebind s_leaf_alloc;
      static internal_node_rebind s_internal_node_alloc;
    };

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::leaf_rebind
    PB_DS_CLASS_C_DEC::s_leaf_alloc;

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::internal_node_rebind
    PB_DS_CLASS_C_DEC::s_internal_node_alloc;

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    get_pref_pos(const_e_iterator b_it, const_e_iterator e_it,
		 const_e_access_traits_pointer p_traits) const
    {
      if (static_cast<size_t>(std::distance(b_it, e_it)) <= m_e_ind)
	return 0;
      std::advance(b_it, m_e_ind);
      return 1 + p_traits->e_pos(*b_it);
    }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    pat_trie_internal_node(size_type len, const const_e_iterator it) :
      PB_DS_BASE_C_DEC(pat_trie_internal_node_type),
      m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it)
    {
      std::advance(m_pref_e_it, m_e_ind);
      std::fill(m_a_p_children, m_a_p_children + arr_size,
		static_cast<node_pointer>(NULL));
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    update_prefixes(const_e_access_traits_pointer p_traits)
    {
      node_pointer p_first = *begin();
      if (p_first->m_type == pat_trie_leaf_node_type)
	{
	  const_leaf_pointer p = static_cast<const_leaf_pointer>(p_first);
	  m_pref_b_it = p_traits->begin(e_access_traits::extract_key(p->value()));
	}
      else
	{
	  _GLIBCXX_DEBUG_ASSERT(p_first->m_type == pat_trie_internal_node_type);
	  m_pref_b_it = static_cast<internal_node_pointer>(p_first)->pref_b_it();
	}
      m_pref_e_it = m_pref_b_it;
      std::advance(m_pref_e_it, m_e_ind);
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::const_iterator
    PB_DS_CLASS_C_DEC::
    begin() const
    {
      typedef node_pointer_pointer pointer_type;
      pointer_type p = const_cast<pointer_type>(m_a_p_children);
      return const_iterator(p + get_begin_pos(), p + arr_size);
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::iterator
    PB_DS_CLASS_C_DEC::
    begin()
    {
      return iterator(m_a_p_children + get_begin_pos(),
		      m_a_p_children + arr_size);
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::const_iterator
    PB_DS_CLASS_C_DEC::
    end() const
    {
      typedef node_pointer_pointer pointer_type;
      pointer_type p = const_cast<pointer_type>(m_a_p_children) + arr_size;
      return const_iterator(p, p);
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::iterator
    PB_DS_CLASS_C_DEC::
    end()
    { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::node_pointer
    PB_DS_CLASS_C_DEC::
    get_child_node(const_e_iterator b_it, const_e_iterator e_it,
		   const_e_access_traits_pointer p_traits)
    {
      const size_type i = get_pref_pos(b_it, e_it, p_traits);
      _GLIBCXX_DEBUG_ASSERT(i < arr_size);
      return m_a_p_children[i];
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::iterator
    PB_DS_CLASS_C_DEC::
    get_child_it(const_e_iterator b_it, const_e_iterator e_it,
		 const_e_access_traits_pointer p_traits)
    {
      const size_type i = get_pref_pos(b_it, e_it, p_traits);
      _GLIBCXX_DEBUG_ASSERT(i < arr_size);
      _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != NULL);
      return iterator(m_a_p_children + i, m_a_p_children + i);
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::const_node_pointer
    PB_DS_CLASS_C_DEC::
    get_child_node(const_e_iterator b_it, const_e_iterator e_it,
		   const_e_access_traits_pointer p_traits) const
    { return const_cast<node_pointer>(get_child_node(b_it, e_it, p_traits)); }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::node_pointer
    PB_DS_CLASS_C_DEC::
    get_lower_bound_child_node(const_e_iterator b_it, const_e_iterator e_it,
			       size_type checked_ind,
			       const_e_access_traits_pointer p_traits)
    {
      if (!should_be_mine(b_it, e_it, checked_ind, p_traits))
	{
	  if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it, m_pref_e_it, true))
	    return leftmost_descendant();
	  return rightmost_descendant();
	}

      size_type i = get_pref_pos(b_it, e_it, p_traits);
      _GLIBCXX_DEBUG_ASSERT(i < arr_size);

      if (m_a_p_children[i] != NULL)
	return m_a_p_children[i];

      while (++i < arr_size)
	if (m_a_p_children[i] != NULL)
	  {
	    if (m_a_p_children[i]->m_type == pat_trie_leaf_node_type)
	      return m_a_p_children[i];

	    _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i]->m_type == pat_trie_internal_node_type);

	    return static_cast<internal_node_pointer>(m_a_p_children[i])->leftmost_descendant();
	  }

      return rightmost_descendant();
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::node_pointer
    PB_DS_CLASS_C_DEC::
    add_child(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it,
	      const_e_access_traits_pointer p_traits)
    {
      const size_type i = get_pref_pos(b_it, e_it, p_traits);
      _GLIBCXX_DEBUG_ASSERT(i < arr_size);
      if (m_a_p_children[i] == NULL)
	{
	  m_a_p_children[i] = p_nd;
	  p_nd->m_p_parent = this;
	  return p_nd;
	}
      return m_a_p_children[i];
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::const_node_pointer
    PB_DS_CLASS_C_DEC::
    get_join_child(const_node_pointer p_nd, const_e_access_traits_pointer p_traits) const
    {
      node_pointer p = const_cast<node_pointer>(p_nd);
      return const_cast<internal_node_pointer>(this)->get_join_child(p, p_traits);
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::node_pointer
    PB_DS_CLASS_C_DEC::
    get_join_child(node_pointer p_nd, const_e_access_traits_pointer p_traits)
    {
      size_type i;
      const_e_iterator b_it;
      const_e_iterator e_it;
      if (p_nd->m_type == pat_trie_leaf_node_type)
	{
	  typename Type_Traits::const_key_reference r_key =
	    e_access_traits::extract_key(static_cast<const_leaf_pointer>(p_nd)->value());

	  b_it = p_traits->begin(r_key);
	  e_it = p_traits->end(r_key);
	}
      else
	{
	  b_it = static_cast<internal_node_pointer>(p_nd)->pref_b_it();
	  e_it = static_cast<internal_node_pointer>(p_nd)->pref_e_it();
	}
      i = get_pref_pos(b_it, e_it, p_traits);
      _GLIBCXX_DEBUG_ASSERT(i < arr_size);
      return m_a_p_children[i];
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    remove_child(node_pointer p_nd)
    {
      size_type i = 0;
      for (; i < arr_size; ++i)
	if (m_a_p_children[i] == p_nd)
	  {
	    m_a_p_children[i] = NULL;
	    return;
	  }
      _GLIBCXX_DEBUG_ASSERT(i != arr_size);
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::iterator
    PB_DS_CLASS_C_DEC::
    remove_child(iterator it)
    {
      iterator ret = it;
      ++ret;
      * it.m_p_p_cur = NULL;
      return ret;
    }

    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    replace_child(node_pointer p_nd, const_e_iterator b_it,
		  const_e_iterator e_it,
		  const_e_access_traits_pointer p_traits)
    {
      const size_type i = get_pref_pos(b_it, e_it, p_traits);
      _GLIBCXX_DEBUG_ASSERT(i < arr_size);
      m_a_p_children[i] = p_nd;
      p_nd->m_p_parent = this;
    }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::const_e_iterator
    PB_DS_CLASS_C_DEC::
    pref_b_it() const
    { return m_pref_b_it; }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::const_e_iterator
    PB_DS_CLASS_C_DEC::
    pref_e_it() const
    { return m_pref_e_it; }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    get_e_ind() const
    { return m_e_ind; }

    PB_DS_CLASS_T_DEC
    bool
    PB_DS_CLASS_C_DEC::
    should_be_mine(const_e_iterator b_it, const_e_iterator e_it,
		   size_type checked_ind,
		   const_e_access_traits_pointer p_traits) const
    {
      if (m_e_ind == 0)
	return true;

      const size_type num_es = std::distance(b_it, e_it);
      if (num_es < m_e_ind)
	return false;

      const_e_iterator key_b_it = b_it;
      std::advance(key_b_it, checked_ind);
      const_e_iterator key_e_it = b_it;
      std::advance(key_e_it, m_e_ind);

      const_e_iterator value_b_it = m_pref_b_it;
      std::advance(value_b_it, checked_ind);
      const_e_iterator value_e_it = m_pref_b_it;
      std::advance(value_e_it, m_e_ind);

      return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it,
				      value_e_it);
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::leaf_pointer
    PB_DS_CLASS_C_DEC::
    leftmost_descendant()
    {
      node_pointer p_pot =* begin();
      if (p_pot->m_type == pat_trie_leaf_node_type)
	return (static_cast<leaf_pointer>(p_pot));
      _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type);
      return static_cast<internal_node_pointer>(p_pot)->leftmost_descendant();
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::const_leaf_pointer
    PB_DS_CLASS_C_DEC::
    leftmost_descendant() const
    {
      return const_cast<internal_node_pointer>(this)->leftmost_descendant();
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::leaf_pointer
    PB_DS_CLASS_C_DEC::
    rightmost_descendant()
    {
      const size_type num_children = std::distance(begin(), end());
      _GLIBCXX_DEBUG_ASSERT(num_children >= 2);

      iterator it = begin();
      std::advance(it, num_children - 1);
      node_pointer p_pot =* it;
      if (p_pot->m_type == pat_trie_leaf_node_type)
	return static_cast<leaf_pointer>(p_pot);
      _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type);
      return static_cast<internal_node_pointer>(p_pot)->rightmost_descendant();
    }

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::const_leaf_pointer
    PB_DS_CLASS_C_DEC::
    rightmost_descendant() const
    {
      return const_cast<internal_node_pointer>(this)->rightmost_descendant();
    }

#ifdef _GLIBCXX_DEBUG
    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    e_ind() const
    { return m_e_ind; }
#endif

    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::size_type
    PB_DS_CLASS_C_DEC::
    get_begin_pos() const
    {
      size_type i;
      for (i = 0; i < arr_size && m_a_p_children[i] == NULL; ++i)
	;
      return i;
    }

#ifdef _GLIBCXX_DEBUG
    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::subtree_debug_info
    PB_DS_CLASS_C_DEC::
    assert_valid_imp(const_e_access_traits_pointer p_traits) const
    {
      _GLIBCXX_DEBUG_ASSERT(base_type::m_type == pat_trie_internal_node_type);
      _GLIBCXX_DEBUG_ASSERT(static_cast<size_type>(std::distance(pref_b_it(), pref_e_it())) == m_e_ind);
      _GLIBCXX_DEBUG_ASSERT(std::distance(begin(), end()) >= 2);

      for (typename pat_trie_internal_node::const_iterator it = begin();
	   it != end(); ++it)
	{
	  const_node_pointer p_nd =* it;
	  _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent == this);
	  subtree_debug_info child_ret = p_nd->assert_valid_imp(p_traits);

	  _GLIBCXX_DEBUG_ASSERT(static_cast<size_type>(std::distance(child_ret.first, child_ret.second)) >= m_e_ind);
	  _GLIBCXX_DEBUG_ASSERT(should_be_mine(child_ret.first, child_ret.second, 0, p_traits));
	  _GLIBCXX_DEBUG_ASSERT(get_pref_pos(child_ret.first, child_ret.second, p_traits) == static_cast<size_type>(it.m_p_p_cur - m_a_p_children));
	}
      return std::make_pair(pref_b_it(), pref_e_it());
    }
#endif

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_BASE_C_DEC
#undef PB_DS_LEAF_C_DEC
#undef PB_DS_STATIC_ASSERT

  } // 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 iterators_fn_imps.hpp
 * Contains an implementation class for bin_search_tree_.
 */

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::iterator
PB_DS_CLASS_C_DEC::
begin()
{ return iterator(m_p_head->m_p_min); }

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_iterator
PB_DS_CLASS_C_DEC::
begin() const
{ return const_iterator(m_p_head->m_p_min); }

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

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

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator
PB_DS_CLASS_C_DEC::
rbegin() const
{
  if (empty())
    return rend();
  return --end();
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::reverse_iterator
PB_DS_CLASS_C_DEC::
rbegin()
{
  if (empty())
    return rend();
  return --end();
}

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::reverse_iterator
PB_DS_CLASS_C_DEC::
rend()
{ return reverse_iterator(m_p_head); }

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator
PB_DS_CLASS_C_DEC::
rend() const
{ return const_reverse_iterator(m_p_head); }

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_node_iterator
PB_DS_CLASS_C_DEC::
node_begin() const
{ return const_node_iterator(m_p_head->m_p_parent, this); }

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_iterator
PB_DS_CLASS_C_DEC::
node_begin()
{ return node_iterator(m_p_head->m_p_parent, this); }

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_node_iterator
PB_DS_CLASS_C_DEC::
node_end() const
{ return const_node_iterator(NULL, this); }

PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_iterator
PB_DS_CLASS_C_DEC::
node_end()
{ return node_iterator(NULL, 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 leaf.hpp
 * Contains a pat_trie_leaf for a patricia tree.
 */

#ifndef PB_DS_PAT_TRIE_LEAF_HPP
#define PB_DS_PAT_TRIE_LEAF_HPP

#include <debug/debug.h>

namespace pb_ds
{
  namespace detail
  {

#define PB_DS_CLASS_T_DEC						\
    template<								\
						class Type_Traits,	\
						class E_Access_Traits,	\
						class Metadata,		\
						class Allocator>

#define PB_DS_CLASS_C_DEC						\
    pat_trie_leaf<							\
						Type_Traits,		\
						E_Access_Traits,	\
						Metadata,		\
						Allocator>

#define PB_DS_BASE_C_DEC					\
    pat_trie_node_base<						\
					Type_Traits,		\
					E_Access_Traits,	\
					Metadata,		\
					Allocator>

#define PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC				\
    pat_trie_subtree_debug_info<					\
							Type_Traits,	\
							E_Access_Traits, \
							Allocator>

    template<typename Type_Traits,
	     class E_Access_Traits,
	     class Metadata,
	     class Allocator>
    struct pat_trie_leaf : public PB_DS_BASE_C_DEC
    {
    private:
      typedef typename Type_Traits::value_type value_type;

      typedef typename Type_Traits::const_reference const_reference;

      typedef typename Type_Traits::reference reference;

      typedef
      typename Allocator::template rebind<
	E_Access_Traits>::other::const_pointer
      const_e_access_traits_pointer;

#ifdef _GLIBCXX_DEBUG
      typedef
      typename PB_DS_BASE_C_DEC::subtree_debug_info
      subtree_debug_info;
#endif

      typedef PB_DS_BASE_C_DEC base_type;

    public:
      pat_trie_leaf(const_reference r_val);

      inline reference
      value();

      inline const_reference
      value() const;

#ifdef _GLIBCXX_DEBUG
      virtual subtree_debug_info
      assert_valid_imp(const_e_access_traits_pointer p_traits) const;

      virtual
      ~pat_trie_leaf();
#endif

    private:
      pat_trie_leaf(const PB_DS_CLASS_C_DEC& other);

      value_type m_value;
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    pat_trie_leaf(const_reference r_val) :
    PB_DS_BASE_C_DEC(pat_trie_leaf_node_type), m_value(r_val)
    { }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::reference
    PB_DS_CLASS_C_DEC::
    value()
    { return m_value; }

    PB_DS_CLASS_T_DEC
    inline typename PB_DS_CLASS_C_DEC::const_reference
    PB_DS_CLASS_C_DEC::
    value() const
    { return m_value; }

#ifdef _GLIBCXX_DEBUG
    PB_DS_CLASS_T_DEC
    typename PB_DS_CLASS_C_DEC::subtree_debug_info
    PB_DS_CLASS_C_DEC::
    assert_valid_imp(const_e_access_traits_pointer p_traits) const
    {
      _GLIBCXX_DEBUG_ASSERT(base_type::m_type == pat_trie_leaf_node_type);
      subtree_debug_info ret;
      const_reference r_val = value();
      return std::make_pair(p_traits->begin(p_traits->extract_key(r_val)),
			     p_traits->end(p_traits->extract_key(r_val)));
    }

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    ~pat_trie_leaf() { }
#endif

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_BASE_C_DEC
#undef PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC

  } // namespace detail
} // namespace pb_ds

#endif


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

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

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

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

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

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

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

/**
 * @file node_base.hpp
 * Contains a pat_trie_node_base base for a patricia tree.
 */

#ifndef PB_DS_PAT_TRIE_NODE_BASE_HPP
#define PB_DS_PAT_TRIE_NODE_BASE_HPP

#include <ext/pb_ds/detail/pat_trie_/node_metadata_base.hpp>

namespace pb_ds
{
  namespace detail
  {
#define PB_DS_CLASS_T_DEC \
    template<typename Type_Traits, typename E_Access_Traits,	\
	     typename Metadata,	typename Allocator>

#define PB_DS_CLASS_C_DEC \
    pat_trie_node_base<Type_Traits, E_Access_Traits, Metadata, Allocator>

#define PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC	\
    pat_trie_subtree_debug_info<Type_Traits, E_Access_Traits, Allocator>

    enum pat_trie_node_type
      {
	pat_trie_internal_node_type,
	pat_trie_leaf_node_type,
	pat_trie_head_node_type
      };

    template<typename Type_Traits,
	     typename E_Access_Traits,
	     typename Metadata,
	     typename Allocator>
    struct pat_trie_node_base : public pat_trie_node_metadata_base<
      Metadata,
      Allocator>
    {
    public:
      typedef
      typename Allocator::template rebind<
      pat_trie_node_base>::other::pointer
      node_pointer;

      typedef
      typename Allocator::template rebind<
	E_Access_Traits>::other::const_pointer
      const_e_access_traits_pointer;

#ifdef _GLIBCXX_DEBUG
      typedef
      std::pair<
	typename E_Access_Traits::const_iterator,
	typename E_Access_Traits::const_iterator>
      subtree_debug_info;
#endif

      pat_trie_node_base(pat_trie_node_type type);

#ifdef _GLIBCXX_DEBUG
      void
      assert_valid(const_e_access_traits_pointer p_traits) const;

      virtual subtree_debug_info
      assert_valid_imp(const_e_access_traits_pointer p_traits) const = 0;
#endif

      node_pointer m_p_parent;
      const pat_trie_node_type m_type;
    };

    PB_DS_CLASS_T_DEC
    PB_DS_CLASS_C_DEC::
    pat_trie_node_base(pat_trie_node_type type) : m_type(type)
    { }

#ifdef _GLIBCXX_DEBUG
    PB_DS_CLASS_T_DEC
    void
    PB_DS_CLASS_C_DEC::
    assert_valid(const_e_access_traits_pointer p_traits) const
    { assert_valid_imp(p_traits); }
#endif

#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC

  } // namespace detail
} // namespace pb_ds

#endif


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

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

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

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

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

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

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

/**
 * @file node_iterators.hpp
 * Contains an implementation class for pat_trie_.
 */

#ifndef PB_DS_PAT_TRIE_NODE_ITERATORS_HPP
#define PB_DS_PAT_TRIE_NODE_ITERATORS_HPP

#include <debug/debug.h>

namespace pb_ds
{
  namespace detail
  {

#define PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC			\
    pat_trie_const_node_it_<						\
							Node,		\
							Leaf,		\
							Head,		\
							Internal_Node,	\
							Const_Iterator,	\
							Iterator,	\
							E_Access_Traits, \
							Allocator>

#define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC			\
    pat_trie_node_it_<						\
					Node,			\
					Leaf,			\
					Head,			\
					Internal_Node,		\
					Const_Iterator,		\
					Iterator,		\
					E_Access_Traits,	\
					Allocator>

    // Const node iterator.
    template<typename Node,
	     class Leaf,
	     class Head,
	     class Internal_Node,
	     class Const_Iterator,
	     class Iterator,
	     class E_Access_Traits,
	     class Allocator>
    class pat_trie_const_node_it_
    {
    protected:
      typedef
      typename Allocator::template rebind<
      Node>::other::pointer
      node_pointer;

      typedef
      typename Allocator::template rebind<
	Leaf>::other::const_pointer
      const_leaf_pointer;

      typedef
      typename Allocator::template rebind<
	Leaf>::other::pointer
      leaf_pointer;

      typedef
      typename Allocator::template rebind<
	Internal_Node>::other::pointer
      internal_node_pointer;

      typedef
      typename Allocator::template rebind<
	Internal_Node>::other::const_pointer
      const_internal_node_pointer;

      typedef
      typename Allocator::template rebind<
	E_Access_Traits>::other::const_pointer
      const_e_access_traits_pointer;

    private:
      inline typename E_Access_Traits::const_iterator
      pref_begin() const
      {
	if (m_p_nd->m_type == pat_trie_leaf_node_type)
	  return (m_p_traits->begin(
				    m_p_traits->extract_key(
							    static_cast<const_leaf_pointer>(m_p_nd)->value())));

	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);

	return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_b_it());
      }

      inline typename E_Access_Traits::const_iterator
      pref_end() const
      {
	if (m_p_nd->m_type == pat_trie_leaf_node_type)
	  return (m_p_traits->end(
				  m_p_traits->extract_key(
							  static_cast<const_leaf_pointer>(m_p_nd)->value())));

	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);

	return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_e_it());
      }

    public:

      // Size type.
      typedef typename Allocator::size_type size_type;

      // Category.
      typedef trivial_iterator_tag iterator_category;

      // Difference type.
      typedef trivial_iterator_difference_type difference_type;

      // __Iterator's value type.
      typedef Const_Iterator value_type;

      // __Iterator's reference type.
      typedef value_type reference;

      // __Iterator's __const reference type.
      typedef value_type const_reference;

      // Element access traits.
      typedef E_Access_Traits e_access_traits;

      // A key's element __const iterator.
      typedef typename e_access_traits::const_iterator const_e_iterator;

      // Metadata type.
      typedef typename Node::metadata_type metadata_type;

      // Const metadata reference type.
      typedef
      typename Allocator::template rebind<
	metadata_type>::other::const_reference
      const_metadata_reference;

      // Default constructor.
      /*
	inline
	pat_trie_const_node_it_()
      */
      inline
      pat_trie_const_node_it_(node_pointer p_nd = NULL,
			      const_e_access_traits_pointer p_traits = NULL)
      : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits)
      { }

      // Subtree valid prefix.
      inline std::pair<const_e_iterator, const_e_iterator>
      valid_prefix() const
      { return std::make_pair(pref_begin(), pref_end()); }

      // Const access; returns the __const iterator* associated with
      // the current leaf.
      inline const_reference
      operator*() const
      {
	_GLIBCXX_DEBUG_ASSERT(num_children() == 0);
	return Const_Iterator(m_p_nd);
      }

      // Metadata access.
      inline const_metadata_reference
      get_metadata() const
      { return m_p_nd->get_metadata(); }

      // Returns the number of children in the corresponding node.
      inline size_type
      num_children() const
      {
	if (m_p_nd->m_type == pat_trie_leaf_node_type)
	  return 0;
	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
	return std::distance(static_cast<internal_node_pointer>(m_p_nd)->begin(),  static_cast<internal_node_pointer>(m_p_nd)->end());
      }

      // Returns a __const node __iterator to the corresponding node's
      // i-th child.
      PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
      get_child(size_type i) const
      {
	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
	typename Internal_Node::iterator it =
	  static_cast<internal_node_pointer>(m_p_nd)->begin();

	std::advance(it, i);
	return PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC(*it, m_p_traits);
      }

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

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

    private:

      friend class PB_DS_CLASS_C_DEC;

    public:
      node_pointer m_p_nd;

      const_e_access_traits_pointer m_p_traits;
    };

    // Node iterator.
    template<typename Node,
	     class Leaf,
	     class Head,
	     class Internal_Node,
	     class Const_Iterator,
	     class Iterator,
	     class E_Access_Traits,
	     class Allocator>
    class pat_trie_node_it_ :
      public PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC

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

      typedef Iterator iterator;

      typedef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC base_type;

      typedef
      typename base_type::const_e_access_traits_pointer
      const_e_access_traits_pointer;

      typedef typename base_type::internal_node_pointer internal_node_pointer;

    public:

      // Size type.
      typedef
      typename PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC::size_type
      size_type;

      // __Iterator's value type.
      typedef Iterator value_type;

      // __Iterator's reference type.
      typedef value_type reference;

      // __Iterator's __const reference type.
      typedef value_type const_reference;

      // Default constructor.
      /*
	inline
	pat_trie_node_it_() ;
      */

      inline
      pat_trie_node_it_(node_pointer p_nd = NULL,  const_e_access_traits_pointer p_traits = NULL) : base_type(p_nd, p_traits)
      { }

      // Access; returns the iterator*  associated with the current leaf.
      inline reference
      operator*() const
      {
	_GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0);
	return Iterator(base_type::m_p_nd);

      }

      // Returns a node __iterator to the corresponding node's i-th child.
      PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC
      get_child(size_type i) const
      {
	_GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == pat_trie_internal_node_type);

	typename Internal_Node::iterator it =
	  static_cast<internal_node_pointer>(base_type::m_p_nd)->begin();

	std::advance(it, i);
	return PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC(*it, base_type::m_p_traits);
      }

    private:
      friend class PB_DS_CLASS_C_DEC;
    };

#undef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
#undef PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC

  } // namespace detail
} // namespace pb_ds

#endif


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

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

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

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

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

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

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

/**
 * @file node_metadata_base.hpp
 * Contains an internal PB_DS_BASE_C_DEC for a patricia tree.
 */

#ifndef PB_DS_PAT_TRIE_NODE_METADATA_BASE_HPP
#define PB_DS_PAT_TRIE_NODE_METADATA_BASE_HPP

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

namespace pb_ds
{
  namespace detail
  {

    template<typename Metadata, class Allocator>
    struct pat_trie_node_metadata_base
    {
    public:
      typedef Metadata metadata_type;

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

    public:
      inline const_metadata_reference
      get_metadata() const
      {
	return (m_metadata);
      }

    public:
      metadata_type m_metadata;
    };

    template<typename Allocator>
    struct pat_trie_node_metadata_base<
      null_node_metadata,
      Allocator>
    {
    public:
      typedef null_node_metadata metadata_type;
    };

  } // namespace detail
} // namespace pb_ds

#endif // #ifndef PB_DS_PAT_TRIE_NODE_BASE_HPP