OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

Compare Revisions

  • This comparison shows the changes necessary to convert path 
    /openrisc/tags/gnu-src/gcc-4.5.1/gcc-4.5.1-or32-1.0rc4/libstdc++-v3/include/ext/pb_ds/detail/rb_tree_map_
    from Rev 424 to Rev 519
    ↔ Reverse comparison
  •

Rev 424 → Rev 519

/erase_fn_imps.hpp
0,0 → 1,289
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 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 3, 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.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file erase_fn_imps.hpp
* Contains an implementation for rb_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
erase(const_key_reference r_key)
{
point_iterator it = find(r_key);
if (it == base_type::end())
return false;
erase(it);
return true;
}
 
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 == base_type::end())
return it;
 
iterator ret_it = it;
++ret_it;
erase_node(it.m_p_nd);
_GLIBCXX_DEBUG_ONLY(assert_valid());
return ret_it;
}
 
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 == base_type::m_p_head)
return it;
 
reverse_iterator ret_it = it;
++ret_it;
erase_node(it.m_p_nd);
_GLIBCXX_DEBUG_ONLY(assert_valid());
return ret_it;
}
 
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(assert_valid();)
size_type num_ersd = 0;
iterator it = base_type::begin();
while (it != base_type::end())
{
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_node(node_pointer p_nd)
{
remove_node(p_nd);
base_type::actual_erase_node(p_nd);
_GLIBCXX_DEBUG_ONLY(assert_valid());
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
remove_node(node_pointer p_z)
{
update_min_max_for_erased_node(p_z);
node_pointer p_y = p_z;
node_pointer p_x = NULL;
node_pointer p_new_x_parent = NULL;
 
if (p_y->m_p_left == NULL)
p_x = p_y->m_p_right;
else if (p_y->m_p_right == NULL)
p_x = p_y->m_p_left;
else
{
p_y = p_y->m_p_right;
while (p_y->m_p_left != NULL)
p_y = p_y->m_p_left;
p_x = p_y->m_p_right;
}
 
if (p_y == p_z)
{
p_new_x_parent = p_y->m_p_parent;
if (p_x != NULL)
p_x->m_p_parent = p_y->m_p_parent;
 
if (base_type::m_p_head->m_p_parent == p_z)
base_type::m_p_head->m_p_parent = p_x;
else if (p_z->m_p_parent->m_p_left == p_z)
{
p_y->m_p_left = p_z->m_p_parent;
p_z->m_p_parent->m_p_left = p_x;
}
else
{
p_y->m_p_left = NULL;
p_z->m_p_parent->m_p_right = p_x;
}
}
else
{
p_z->m_p_left->m_p_parent = p_y;
p_y->m_p_left = p_z->m_p_left;
if (p_y != p_z->m_p_right)
{
p_new_x_parent = p_y->m_p_parent;
if (p_x != NULL)
p_x->m_p_parent = p_y->m_p_parent;
p_y->m_p_parent->m_p_left = p_x;
p_y->m_p_right = p_z->m_p_right;
p_z->m_p_right->m_p_parent = p_y;
}
else
p_new_x_parent = p_y;
 
if (base_type::m_p_head->m_p_parent == p_z)
base_type::m_p_head->m_p_parent = p_y;
else if (p_z->m_p_parent->m_p_left == p_z)
p_z->m_p_parent->m_p_left = p_y;
else
p_z->m_p_parent->m_p_right = p_y;
 
p_y->m_p_parent = p_z->m_p_parent;
std::swap(p_y->m_red, p_z->m_red);
p_y = p_z;
}
 
update_to_top(p_new_x_parent, (node_update* )this);
 
if (p_y->m_red)
return;
 
remove_fixup(p_x, p_new_x_parent);
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
remove_fixup(node_pointer p_x, node_pointer p_new_x_parent)
{
_GLIBCXX_DEBUG_ASSERT(p_x == NULL || p_x->m_p_parent == p_new_x_parent);
 
while (p_x != base_type::m_p_head->m_p_parent && is_effectively_black(p_x))
if (p_x == p_new_x_parent->m_p_left)
{
node_pointer p_w = p_new_x_parent->m_p_right;
if (p_w->m_red)
{
p_w->m_red = false;
p_new_x_parent->m_red = true;
base_type::rotate_left(p_new_x_parent);
p_w = p_new_x_parent->m_p_right;
}
 
if (is_effectively_black(p_w->m_p_left)
&& is_effectively_black(p_w->m_p_right))
{
p_w->m_red = true;
p_x = p_new_x_parent;
p_new_x_parent = p_new_x_parent->m_p_parent;
}
else
{
if (is_effectively_black(p_w->m_p_right))
{
if (p_w->m_p_left != NULL)
p_w->m_p_left->m_red = false;
 
p_w->m_red = true;
base_type::rotate_right(p_w);
p_w = p_new_x_parent->m_p_right;
}
 
p_w->m_red = p_new_x_parent->m_red;
p_new_x_parent->m_red = false;
 
if (p_w->m_p_right != NULL)
p_w->m_p_right->m_red = false;
 
base_type::rotate_left(p_new_x_parent);
update_to_top(p_new_x_parent, (node_update* )this);
break;
}
}
else
{
node_pointer p_w = p_new_x_parent->m_p_left;
if (p_w->m_red == true)
{
p_w->m_red = false;
p_new_x_parent->m_red = true;
base_type::rotate_right(p_new_x_parent);
p_w = p_new_x_parent->m_p_left;
}
 
if (is_effectively_black(p_w->m_p_right)
&& is_effectively_black(p_w->m_p_left))
{
p_w->m_red = true;
p_x = p_new_x_parent;
p_new_x_parent = p_new_x_parent->m_p_parent;
}
else
{
if (is_effectively_black(p_w->m_p_left))
{
if (p_w->m_p_right != NULL)
p_w->m_p_right->m_red = false;
 
p_w->m_red = true;
base_type::rotate_left(p_w);
p_w = p_new_x_parent->m_p_left;
}
 
p_w->m_red = p_new_x_parent->m_red;
p_new_x_parent->m_red = false;
 
if (p_w->m_p_left != NULL)
p_w->m_p_left->m_red = false;
 
base_type::rotate_right(p_new_x_parent);
update_to_top(p_new_x_parent, (node_update* )this);
break;
}
}
 
if (p_x != NULL)
p_x->m_red = false;
}
/find_fn_imps.hpp
0,0 → 1,39
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 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 3, 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.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// 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 for rb_tree_.
*/
/insert_fn_imps.hpp
0,0 → 1,115
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 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 3, 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.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file insert_fn_imps.hpp
* Contains an implementation for rb_tree_.
*/
 
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_value)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
std::pair<point_iterator, bool> ins_pair = base_type::insert_leaf(r_value);
if (ins_pair.second == true)
{
ins_pair.first.m_p_nd->m_red = true;
_GLIBCXX_DEBUG_ONLY(this->structure_only_assert_valid();)
insert_fixup(ins_pair.first.m_p_nd);
}
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
return ins_pair;
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
insert_fixup(node_pointer p_nd)
{
_GLIBCXX_DEBUG_ASSERT(p_nd->m_red == true);
while (p_nd != base_type::m_p_head->m_p_parent && p_nd->m_p_parent->m_red)
{
if (p_nd->m_p_parent == p_nd->m_p_parent->m_p_parent->m_p_left)
{
node_pointer p_y = p_nd->m_p_parent->m_p_parent->m_p_right;
if (p_y != NULL && p_y->m_red)
{
p_nd->m_p_parent->m_red = false;
p_y->m_red = false;
p_nd->m_p_parent->m_p_parent->m_red = true;
p_nd = p_nd->m_p_parent->m_p_parent;
}
else
{
if (p_nd == p_nd->m_p_parent->m_p_right)
{
p_nd = p_nd->m_p_parent;
base_type::rotate_left(p_nd);
}
p_nd->m_p_parent->m_red = false;
p_nd->m_p_parent->m_p_parent->m_red = true;
base_type::rotate_right(p_nd->m_p_parent->m_p_parent);
}
}
else
{
node_pointer p_y = p_nd->m_p_parent->m_p_parent->m_p_left;
if (p_y != NULL && p_y->m_red)
{
p_nd->m_p_parent->m_red = false;
p_y->m_red = false;
p_nd->m_p_parent->m_p_parent->m_red = true;
p_nd = p_nd->m_p_parent->m_p_parent;
}
else
{
if (p_nd == p_nd->m_p_parent->m_p_left)
{
p_nd = p_nd->m_p_parent;
base_type::rotate_right(p_nd);
}
p_nd->m_p_parent->m_red = false;
p_nd->m_p_parent->m_p_parent->m_red = true;
base_type::rotate_left(p_nd->m_p_parent->m_p_parent);
}
}
}
 
base_type::update_to_top(p_nd, (node_update* )this);
base_type::m_p_head->m_p_parent->m_red = false;
}
/constructors_destructor_fn_imps.hpp
0,0 → 1,100
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 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 3, 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.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file constructors_destructor_fn_imps.hpp
* Contains an implementation for rb_tree_.
*/
 
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()
{
initialize();
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn) :
base_type(r_cmp_fn)
{
initialize();
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) :
base_type(r_cmp_fn, r_node_update)
{
initialize();
_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) :
base_type(other)
{
initialize();
_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();)
base_type::swap(other);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
initialize()
{ base_type::m_p_head->m_red = true; }
/debug_fn_imps.hpp
0,0 → 1,78
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 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 3, 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.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file debug_fn_imps.hpp
* Contains an implementation for rb_tree_.
*/
 
#ifdef _GLIBCXX_DEBUG
 
PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
assert_node_consistent(const node_pointer p_nd) const
{
if (p_nd == NULL)
return 1;
 
const size_type l_height = assert_node_consistent(p_nd->m_p_left);
const size_type r_height = assert_node_consistent(p_nd->m_p_right);
if (p_nd->m_red)
{
_GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_nd->m_p_left));
_GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_nd->m_p_right));
}
_GLIBCXX_DEBUG_ASSERT(l_height == r_height);
return (p_nd->m_red ? 0 : 1) + l_height;
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid() const
{
base_type::assert_valid();
const node_pointer p_head = base_type::m_p_head;
_GLIBCXX_DEBUG_ASSERT(p_head->m_red);
if (p_head->m_p_parent != NULL)
{
_GLIBCXX_DEBUG_ASSERT(!p_head->m_p_parent->m_red);
assert_node_consistent(p_head->m_p_parent);
}
}
 
#endif
 
/rb_tree_.hpp
0,0 → 1,280
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 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 3, 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.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file rb_tree_.hpp
* Contains an implementation for rb_tree_.
*/
/*
* This implementation uses an idea from the SGI STL (using a @a header node
* which is needed for efficient iteration).
*/
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
#ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
#define PB_DS_BIN_SEARCH_TREE_HPP__DATA_TRUE_INDICATOR
#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
#endif
#endif
 
#ifdef PB_DS_DATA_FALSE_INDICATOR
#ifndef PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
#define PB_DS_BIN_SEARCH_TREE_HPP__DATA_FALSE_INDICATOR
#include <ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp>
#endif
#endif
 
#include <ext/pb_ds/detail/standard_policies.hpp>
#include <ext/pb_ds/detail/basic_types.hpp>
#include <utility>
#include <vector>
#include <assert.h>
#include <debug/debug.h>
 
namespace __gnu_pbds
{
namespace detail
{
#define PB_DS_CLASS_T_DEC \
template<typename Key, typename Mapped, typename Cmp_Fn, \
typename Node_And_It_Traits, typename Allocator>
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_CLASS_NAME rb_tree_data_
#endif
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_BASE_CLASS_NAME bin_search_tree_data_
#endif
 
#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_CLASS_NAME rb_tree_no_data_
#endif
 
#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_BASE_CLASS_NAME bin_search_tree_no_data_
#endif
 
#define PB_DS_CLASS_C_DEC \
PB_DS_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator>
 
#define PB_DS_BASE_C_DEC \
PB_DS_BASE_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator>
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_V2F(X) (X).first
#define PB_DS_V2S(X) (X).second
#define PB_DS_EP2VP(X)& ((X)->m_value)
#endif
 
#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_V2F(X) (X)
#define PB_DS_V2S(X) Mapped_Data()
#define PB_DS_EP2VP(X)& ((X)->m_value.first)
#endif
 
template<typename Key,
typename Mapped,
typename Cmp_Fn,
typename Node_And_It_Traits,
typename Allocator>
class PB_DS_CLASS_NAME : public PB_DS_BASE_C_DEC
{
private:
typedef PB_DS_BASE_C_DEC base_type;
typedef typename base_type::node_pointer node_pointer;
 
public:
typedef Cmp_Fn cmp_fn;
typedef Allocator allocator_type;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
typedef typename base_type::key_type key_type;
typedef typename base_type::key_pointer key_pointer;
typedef typename base_type::const_key_pointer const_key_pointer;
typedef typename base_type::key_reference key_reference;
typedef typename base_type::const_key_reference const_key_reference;
typedef typename base_type::mapped_type mapped_type;
typedef typename base_type::mapped_pointer mapped_pointer;
typedef typename base_type::const_mapped_pointer const_mapped_pointer;
typedef typename base_type::mapped_reference mapped_reference;
typedef typename base_type::const_mapped_reference const_mapped_reference;
typedef typename base_type::value_type value_type;
typedef typename base_type::pointer pointer;
typedef typename base_type::const_pointer const_pointer;
typedef typename base_type::reference reference;
typedef typename base_type::const_reference const_reference;
typedef typename base_type::point_iterator point_iterator;
typedef typename base_type::const_iterator const_point_iterator;
typedef typename base_type::iterator iterator;
typedef typename base_type::const_iterator const_iterator;
typedef typename base_type::reverse_iterator reverse_iterator;
typedef typename base_type::const_reverse_iterator const_reverse_iterator;
typedef typename base_type::node_update node_update;
 
 
PB_DS_CLASS_NAME();
 
PB_DS_CLASS_NAME(const Cmp_Fn&);
 
PB_DS_CLASS_NAME(const Cmp_Fn&, const node_update&);
 
PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
 
void
swap(PB_DS_CLASS_C_DEC&);
 
template<typename It>
void
copy_from_range(It, It);
 
inline std::pair<point_iterator, bool>
insert(const_reference);
 
inline mapped_reference
operator[](const_key_reference r_key)
{
#ifdef PB_DS_DATA_TRUE_INDICATOR
_GLIBCXX_DEBUG_ONLY(assert_valid();)
std::pair<point_iterator, bool> ins_pair =
base_type::insert_leaf(value_type(r_key, mapped_type()));
 
if (ins_pair.second == true)
{
ins_pair.first.m_p_nd->m_red = true;
_GLIBCXX_DEBUG_ONLY(this->structure_only_assert_valid();)
insert_fixup(ins_pair.first.m_p_nd);
}
_GLIBCXX_DEBUG_ONLY(assert_valid();)
return ins_pair.first.m_p_nd->m_value.second;
#else
insert(r_key);
return base_type::s_null_mapped;
#endif
}
 
inline bool
erase(const_key_reference);
 
inline iterator
erase(iterator);
 
inline reverse_iterator
erase(reverse_iterator);
 
template<typename Pred>
inline size_type
erase_if(Pred);
 
void
join(PB_DS_CLASS_C_DEC&);
 
void
split(const_key_reference, PB_DS_CLASS_C_DEC&);
 
protected:
 
private:
 
#ifdef _GLIBCXX_DEBUG
void
assert_valid() const;
 
size_type
assert_node_consistent(const node_pointer) const;
#endif
 
inline static bool
is_effectively_black(const node_pointer);
 
void
initialize();
 
void
insert_fixup(node_pointer);
 
void
erase_node(node_pointer);
 
void
remove_node(node_pointer);
 
void
remove_fixup(node_pointer, node_pointer);
 
void
split_imp(node_pointer, PB_DS_CLASS_C_DEC&);
 
inline node_pointer
split_min();
 
std::pair<node_pointer, node_pointer>
split_min_imp();
 
void
join_imp(node_pointer, node_pointer);
 
std::pair<node_pointer, node_pointer>
find_join_pos_right(node_pointer, size_type, size_type);
 
std::pair<node_pointer, node_pointer>
find_join_pos_left(node_pointer, size_type, size_type);
 
inline size_type
black_height(node_pointer);
 
void
split_at_node(node_pointer, PB_DS_CLASS_C_DEC&);
};
 
#include <ext/pb_ds/detail/rb_tree_map_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/rb_tree_map_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/rb_tree_map_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/rb_tree_map_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/rb_tree_map_/split_join_fn_imps.hpp>
#include <ext/pb_ds/detail/rb_tree_map_/info_fn_imps.hpp>
 
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_CLASS_NAME
#undef PB_DS_BASE_CLASS_NAME
#undef PB_DS_BASE_C_DEC
#undef PB_DS_V2F
#undef PB_DS_EP2VP
#undef PB_DS_V2S
 
} // namespace detail
} // namespace __gnu_pbds
 
/node.hpp
0,0 → 1,138
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 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 3, 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.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file node.hpp
* Contains an implementation for rb_tree_.
*/
 
#ifndef PB_DS_RB_TREE_NODE_HPP
#define PB_DS_RB_TREE_NODE_HPP
 
#include <ext/pb_ds/detail/basic_tree_policy/null_node_metadata.hpp>
 
namespace __gnu_pbds
{
namespace detail
{
template<typename Value_Type, class Metadata, class Allocator>
struct rb_tree_node_
{
public:
typedef Value_Type value_type;
typedef Metadata metadata_type;
 
typedef
typename Allocator::template rebind<
rb_tree_node_<
Value_Type,
Metadata,
Allocator> >::other::pointer
node_pointer;
 
typedef
typename Allocator::template rebind<
metadata_type>::other::reference
metadata_reference;
 
typedef
typename Allocator::template rebind<
metadata_type>::other::const_reference
const_metadata_reference;
 
inline bool
special() const
{ return m_red; }
 
inline const_metadata_reference
get_metadata() const
{ return m_metadata; }
 
inline metadata_reference
get_metadata()
{ return m_metadata; }
 
#ifdef PB_DS_BIN_SEARCH_TREE_TRACE_
void
trace() const
{
std::cout << PB_DS_V2F(m_value) <<(m_red? " <r> " : " <b> ")
<< "(" << m_metadata << ")";
}
#endif
 
node_pointer m_p_left;
node_pointer m_p_right;
node_pointer m_p_parent;
value_type m_value;
bool m_red;
metadata_type m_metadata;
};
 
template<typename Value_Type, class Allocator>
struct rb_tree_node_<Value_Type, null_node_metadata, Allocator>
{
public:
typedef Value_Type value_type;
typedef null_node_metadata metadata_type;
 
typedef
typename Allocator::template rebind<
rb_tree_node_<
Value_Type,
null_node_metadata,
Allocator> >::other::pointer
node_pointer;
 
inline bool
special() const
{ return m_red; }
 
#ifdef PB_DS_BIN_SEARCH_TREE_TRACE_
void
trace() const
{ std::cout << PB_DS_V2F(m_value) <<(m_red? " <r> " : " <b> "); }
#endif
 
node_pointer m_p_left;
node_pointer m_p_right;
node_pointer m_p_parent;
value_type m_value;
bool m_red;
};
} // namespace detail
} // namespace __gnu_pbds
 
#endif
/split_join_fn_imps.hpp
0,0 → 1,313
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 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 3, 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.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file split_join_fn_imps.hpp
* Contains an implementation for rb_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
join(PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();)
if (base_type::join_prep(other) == false)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return;
}
 
const node_pointer p_x = other.split_min();
join_imp(p_x, other.m_p_head->m_p_parent);
base_type::join_finish(other);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(base_type::assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();)
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
join_imp(node_pointer p_x, node_pointer p_r)
{
_GLIBCXX_DEBUG_ASSERT(p_x != NULL);
if (p_r != NULL)
p_r->m_red = false;
 
const size_type h = black_height(base_type::m_p_head->m_p_parent);
const size_type other_h = black_height(p_r);
node_pointer p_x_l;
node_pointer p_x_r;
std::pair<node_pointer, node_pointer> join_pos;
const bool right_join = h >= other_h;
if (right_join)
{
join_pos = find_join_pos_right(base_type::m_p_head->m_p_parent,
h, other_h);
p_x_l = join_pos.first;
p_x_r = p_r;
}
else
{
p_x_l = base_type::m_p_head->m_p_parent;
base_type::m_p_head->m_p_parent = p_r;
if (p_r != NULL)
p_r->m_p_parent = base_type::m_p_head;
 
join_pos = find_join_pos_left(base_type::m_p_head->m_p_parent,
h, other_h);
p_x_r = join_pos.first;
}
 
node_pointer p_parent = join_pos.second;
if (p_parent == base_type::m_p_head)
{
base_type::m_p_head->m_p_parent = p_x;
p_x->m_p_parent = base_type::m_p_head;
}
else
{
p_x->m_p_parent = p_parent;
if (right_join)
p_x->m_p_parent->m_p_right = p_x;
else
p_x->m_p_parent->m_p_left = p_x;
}
 
p_x->m_p_left = p_x_l;
if (p_x_l != NULL)
p_x_l->m_p_parent = p_x;
 
p_x->m_p_right = p_x_r;
if (p_x_r != NULL)
p_x_r->m_p_parent = p_x;
 
p_x->m_red = true;
 
base_type::initialize_min_max();
_GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
base_type::update_to_top(p_x, (node_update* )this);
insert_fixup(p_x);
_GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid());
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_pointer
PB_DS_CLASS_C_DEC::
split_min()
{
node_pointer p_min = base_type::m_p_head->m_p_left;
 
#ifdef _GLIBCXX_DEBUG
const node_pointer p_head = base_type::m_p_head;
_GLIBCXX_DEBUG_ASSERT(p_min != p_head);
#endif
 
remove_node(p_min);
return p_min;
}
 
PB_DS_CLASS_T_DEC
std::pair<
typename PB_DS_CLASS_C_DEC::node_pointer,
typename PB_DS_CLASS_C_DEC::node_pointer>
PB_DS_CLASS_C_DEC::
find_join_pos_right(node_pointer p_l, size_type h_l, size_type h_r)
{
_GLIBCXX_DEBUG_ASSERT(h_l >= h_r);
 
if (base_type::m_p_head->m_p_parent == NULL)
return (std::make_pair((node_pointer)NULL, base_type::m_p_head));
 
node_pointer p_l_parent = base_type::m_p_head;
while (h_l > h_r)
{
if (p_l->m_red == false)
{
_GLIBCXX_DEBUG_ASSERT(h_l > 0);
--h_l;
}
 
p_l_parent = p_l;
p_l = p_l->m_p_right;
}
 
if (!is_effectively_black(p_l))
{
p_l_parent = p_l;
p_l = p_l->m_p_right;
}
 
_GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_l));
_GLIBCXX_DEBUG_ASSERT(black_height(p_l) == h_r);
_GLIBCXX_DEBUG_ASSERT(p_l == NULL || p_l->m_p_parent == p_l_parent);
return std::make_pair(p_l, p_l_parent);
}
 
PB_DS_CLASS_T_DEC
std::pair<
typename PB_DS_CLASS_C_DEC::node_pointer,
typename PB_DS_CLASS_C_DEC::node_pointer>
PB_DS_CLASS_C_DEC::
find_join_pos_left(node_pointer p_r, size_type h_l, size_type h_r)
{
_GLIBCXX_DEBUG_ASSERT(h_r > h_l);
if (base_type::m_p_head->m_p_parent == NULL)
return (std::make_pair((node_pointer)NULL,
base_type::m_p_head));
node_pointer p_r_parent = base_type::m_p_head;
while (h_r > h_l)
{
if (p_r->m_red == false)
{
_GLIBCXX_DEBUG_ASSERT(h_r > 0);
--h_r;
}
 
p_r_parent = p_r;
p_r = p_r->m_p_left;
}
 
if (!is_effectively_black(p_r))
{
p_r_parent = p_r;
p_r = p_r->m_p_left;
}
 
_GLIBCXX_DEBUG_ASSERT(is_effectively_black(p_r));
_GLIBCXX_DEBUG_ASSERT(black_height(p_r) == h_l);
_GLIBCXX_DEBUG_ASSERT(p_r == NULL || p_r->m_p_parent == p_r_parent);
return std::make_pair(p_r, p_r_parent);
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
black_height(node_pointer p_nd)
{
size_type h = 1;
while (p_nd != NULL)
{
if (p_nd->m_red == false)
++h;
p_nd = p_nd->m_p_left;
}
return h;
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid());
_GLIBCXX_DEBUG_ONLY(base_type::assert_valid();)
 
_GLIBCXX_DEBUG_ONLY(other.assert_valid());
_GLIBCXX_DEBUG_ONLY(other.base_type::assert_valid();)
 
if (base_type::split_prep(r_key, other) == false)
{
_GLIBCXX_DEBUG_ONLY(assert_valid());
_GLIBCXX_DEBUG_ONLY(other.assert_valid());
return;
}
 
_GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();)
node_pointer p_nd = upper_bound(r_key).m_p_nd;
do
{
node_pointer p_next_nd = p_nd->m_p_parent;
if (Cmp_Fn::operator()(r_key, PB_DS_V2F(p_nd->m_value)))
split_at_node(p_nd, other);
 
_GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid();)
p_nd = p_next_nd;
}
while (p_nd != base_type::m_p_head);
 
base_type::split_finish(other);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
split_at_node(node_pointer p_nd, PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ASSERT(p_nd != NULL);
 
node_pointer p_l = p_nd->m_p_left;
node_pointer p_r = p_nd->m_p_right;
node_pointer p_parent = p_nd->m_p_parent;
if (p_parent == base_type::m_p_head)
{
base_type::m_p_head->m_p_parent = p_l;
if (p_l != NULL)
{
p_l->m_p_parent = base_type::m_p_head;
p_l->m_red = false;
}
}
else
{
if (p_parent->m_p_left == p_nd)
p_parent->m_p_left = p_l;
else
p_parent->m_p_right = p_l;
 
if (p_l != NULL)
p_l->m_p_parent = p_parent;
 
update_to_top(p_parent, (node_update* )this);
 
if (!p_nd->m_red)
remove_fixup(p_l, p_parent);
}
 
base_type::initialize_min_max();
other.join_imp(p_nd, p_r);
_GLIBCXX_DEBUG_ONLY(base_type::structure_only_assert_valid());
_GLIBCXX_DEBUG_ONLY(other.base_type::structure_only_assert_valid());
}
 
/info_fn_imps.hpp
0,0 → 1,46
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 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 3, 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.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// 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 for rb_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
is_effectively_black(const node_pointer p_nd)
{ return (p_nd == NULL || !p_nd->m_red); }
 
/traits.hpp
0,0 → 1,124
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2009 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 3, 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.
 
// Under Section 7 of GPL version 3, you are granted additional
// permissions described in the GCC Runtime Library Exception, version
// 3.1, as published by the Free Software Foundation.
 
// You should have received a copy of the GNU General Public License and
// a copy of the GCC Runtime Library Exception along with this program;
// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see
// <http://www.gnu.org/licenses/>.
 
// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
 
// Permission to use, copy, modify, sell, and distribute this software
// is hereby granted without fee, provided that the above copyright
// notice appears in all copies, and that both that copyright notice
// and this permission notice appear in supporting documentation. None
// of the above authors, nor IBM Haifa Research Laboratories, make any
// representation about the suitability of this software for any
// purpose. It is provided "as is" without express or implied
// warranty.
 
/**
* @file traits.hpp
* Contains an implementation for rb_tree_.
*/
 
#ifndef PB_DS_RB_TREE_NODE_AND_IT_TRAITS_HPP
#define PB_DS_RB_TREE_NODE_AND_IT_TRAITS_HPP
 
#include <ext/pb_ds/detail/rb_tree_map_/node.hpp>
 
namespace __gnu_pbds
{
namespace detail
{
template<typename Key,
typename Mapped,
typename Cmp_Fn,
template<typename Const_Node_Iterator,
class Node_Iterator,
class Cmp_Fn_,
class Allocator_>
class Node_Update,
typename Allocator>
struct tree_traits<
Key,
Mapped,
Cmp_Fn,
Node_Update,
rb_tree_tag,
Allocator> : public bin_search_tree_traits<
Key,
Mapped,
Cmp_Fn,
Node_Update,
rb_tree_node_<
typename types_traits<
Key,
Mapped,
Allocator,
false>::value_type,
typename tree_node_metadata_selector<
Key,
Mapped,
Cmp_Fn,
Node_Update,
Allocator>::type,
Allocator>,
Allocator>
{ };
 
template<typename Key,
class Cmp_Fn,
template<typename Const_Node_Iterator,
class Node_Iterator,
class Cmp_Fn_,
class Allocator_>
class Node_Update,
class Allocator>
struct tree_traits<
Key,
null_mapped_type,
Cmp_Fn,
Node_Update,
rb_tree_tag,
Allocator> : public bin_search_tree_traits<
Key,
null_mapped_type,
Cmp_Fn,
Node_Update,
rb_tree_node_<
typename types_traits<
Key,
null_mapped_type,
Allocator,
false>::value_type,
typename tree_node_metadata_selector<
Key,
null_mapped_type,
Cmp_Fn,
Node_Update,
Allocator>::type,
Allocator>,
Allocator>
{ };
 
} // namespace detail
} // namespace __gnu_pbds
 
#endif

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.