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/ov_tree_map_
    from Rev 424 to Rev 519
    ↔ Reverse comparison
  •

Rev 424 → Rev 519

/erase_fn_imps.hpp
0,0 → 1,193
// -*- 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 class for ov_tree_.
*/
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
clear()
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
if (m_size == 0)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
return;
}
else
{
reallocate_metadata((node_update* )this, 0);
cond_dtor<size_type> cd(m_a_values, m_end_it, m_size);
}
 
_GLIBCXX_DEBUG_ONLY(debug_base::clear();)
m_a_values = NULL;
m_size = 0;
m_end_it = m_a_values;
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
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();)
 
#ifdef PB_DS_REGRESSION
typename Allocator::group_adjustor adjust(m_size);
#endif
 
size_type new_size = 0;
size_type num_val_ersd = 0;
iterator source_it = m_a_values;
for (source_it = begin(); source_it != m_end_it; ++source_it)
if (!pred(*source_it))
++new_size;
else
++num_val_ersd;
 
if (new_size == 0)
{
clear();
return num_val_ersd;
}
 
value_vector a_new_values = s_value_alloc.allocate(new_size);
iterator target_it = a_new_values;
cond_dtor<size_type> cd(a_new_values, target_it, new_size);
_GLIBCXX_DEBUG_ONLY(debug_base::clear());
for (source_it = begin(); source_it != m_end_it; ++source_it)
{
if (!pred(*source_it))
{
new (const_cast<void*>(static_cast<const void* >(target_it)))
value_type(*source_it);
 
_GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(*source_it)));
++target_it;
}
}
 
reallocate_metadata((node_update* )this, new_size);
cd.set_no_action();
 
{
cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size);
}
 
m_a_values = a_new_values;
m_size = new_size;
m_end_it = target_it;
update(node_begin(), (node_update* )this);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
return num_val_ersd;
}
 
PB_DS_CLASS_T_DEC
template<typename It>
It
PB_DS_CLASS_C_DEC::
erase_imp(It it)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
if (it == end())
return end();
 
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::check_key_exists(PB_DS_V2F(*it));)
 
#ifdef PB_DS_REGRESSION
typename Allocator::group_adjustor adjust(m_size);
#endif
 
_GLIBCXX_DEBUG_ASSERT(m_size > 0);
value_vector a_values = s_value_alloc.allocate(m_size - 1);
iterator source_it = begin();
iterator source_end_it = end();
iterator target_it = a_values;
iterator ret_it = end();
 
cond_dtor<size_type> cd(a_values, target_it, m_size - 1);
 
_GLIBCXX_DEBUG_ONLY(size_type cnt = 0;)
 
while (source_it != source_end_it)
{
if (source_it != it)
{
_GLIBCXX_DEBUG_ONLY(++cnt;)
_GLIBCXX_DEBUG_ASSERT(cnt != m_size);
new (const_cast<void* >(static_cast<const void* >(target_it)))
value_type(*source_it);
 
++target_it;
}
else
ret_it = target_it;
++source_it;
}
 
_GLIBCXX_DEBUG_ASSERT(m_size > 0);
reallocate_metadata((node_update* )this, m_size - 1);
cd.set_no_action();
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::erase_existing(PB_DS_V2F(*it));)
{
cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size);
}
 
m_a_values = a_values;
--m_size;
m_end_it = m_a_values + m_size;
update(node_begin(), (node_update* )this);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
return It(ret_it);
}
 
PB_DS_CLASS_T_DEC
bool
PB_DS_CLASS_C_DEC::
erase(const_key_reference r_key)
{
point_iterator it = find(r_key);
if (it == end())
return false;
erase(it);
return true;
}
 
/cond_dtor.hpp
0,0 → 1,74
// -*- 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 cond_dtor.hpp
* Contains a conditional destructor
*/
 
template<typename Size_Type>
class cond_dtor
{
public:
cond_dtor(value_vector a_vec, iterator& r_last_it, Size_Type total_size)
: m_a_vec(a_vec), m_r_last_it(r_last_it), m_max_size(total_size),
m_no_action(false)
{ }
 
~cond_dtor()
{
if (m_no_action)
return;
iterator it = m_a_vec;
while (it != m_r_last_it)
{
it->~value_type();
++it;
}
 
if (m_max_size > 0)
value_allocator().deallocate(m_a_vec, m_max_size);
}
 
inline void
set_no_action()
{ m_no_action = true; }
 
protected:
value_vector m_a_vec;
iterator& m_r_last_it;
const Size_Type m_max_size;
bool m_no_action;
};
/policy_access_fn_imps.hpp
0,0 → 1,51
// -*- 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 policy_access_fn_imps.hpp
* Contains an implementation class for bin_search_tree_.
*/
 
PB_DS_CLASS_T_DEC
Cmp_Fn&
PB_DS_CLASS_C_DEC::
get_cmp_fn()
{ return *this; }
 
PB_DS_CLASS_T_DEC
const Cmp_Fn&
PB_DS_CLASS_C_DEC::
get_cmp_fn() const
{ return *this; }
/insert_fn_imps.hpp
0,0 → 1,63
// -*- 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 class for ov_tree_.
*/
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
reallocate_metadata(null_node_update_pointer, size_type)
{ }
 
PB_DS_CLASS_T_DEC
template<typename Node_Update_>
void
PB_DS_CLASS_C_DEC::
reallocate_metadata(Node_Update_* , size_type new_size)
{
metadata_pointer a_new_metadata_vec =(new_size == 0) ? NULL : s_metadata_alloc.allocate(new_size);
 
if (m_a_metadata != NULL)
{
for (size_type i = 0; i < m_size; ++i)
m_a_metadata[i].~metadata_type();
s_metadata_alloc.deallocate(m_a_metadata, m_size);
}
std::swap(m_a_metadata, a_new_metadata_vec);
}
 
/ov_tree_map_.hpp
0,0 → 1,522
// -*- 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 ov_tree_map_.hpp
* Contains an implementation class for ov_tree_.
*/
 
#include <map>
#include <set>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp>
#include <ext/pb_ds/detail/types_traits.hpp>
#include <ext/pb_ds/detail/debug_map_base.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <ext/pb_ds/exception.hpp>
#include <ext/pb_ds/detail/tree_trace_base.hpp>
#include <utility>
#include <functional>
#include <algorithm>
#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, class Cmp_Fn, \
class Node_And_It_Traits, class Allocator>
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_OV_TREE_CLASS_NAME ov_tree_data_
#endif
 
#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_OV_TREE_CLASS_NAME ov_tree_no_data_
#endif
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_const_node_iterator_data_
#else
#define PB_DS_CONST_NODE_ITERATOR_NAME ov_tree_const_node_iterator_no_data_
#endif
 
#define PB_DS_CLASS_C_DEC \
PB_DS_OV_TREE_CLASS_NAME<Key, Mapped, Cmp_Fn, Node_And_It_Traits, Allocator>
 
#define PB_DS_TYPES_TRAITS_C_DEC \
types_traits<Key, Mapped, Allocator, false>
 
#ifdef _GLIBCXX_DEBUG
#define PB_DS_DEBUG_MAP_BASE_C_DEC \
debug_map_base<Key, eq_by_less<Key, Cmp_Fn>, \
typename Allocator::template rebind<Key>::other::const_reference>
#endif
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
#define PB_DS_V2F(X) (X).first
#define PB_DS_V2S(X) (X).second
#define PB_DS_EP2VP(X)& ((X)->m_value)
#endif
 
#ifdef PB_DS_DATA_FALSE_INDICATOR
#define PB_DS_V2F(X) (X)
#define PB_DS_V2S(X) Mapped_Data()
#define PB_DS_EP2VP(X)& ((X)->m_value.first)
#endif
 
#ifdef PB_DS_TREE_TRACE
#define PB_DS_TREE_TRACE_BASE_C_DEC \
tree_trace_base<typename Node_And_It_Traits::const_node_iterator, \
typename Node_And_It_Traits::node_iterator, \
Cmp_Fn, false, Allocator>
#endif
 
// Ordered-vector tree associative-container.
template<typename Key, typename Mapped, class Cmp_Fn,
class Node_And_It_Traits, class Allocator>
class PB_DS_OV_TREE_CLASS_NAME :
#ifdef _GLIBCXX_DEBUG
protected PB_DS_DEBUG_MAP_BASE_C_DEC,
#endif
#ifdef PB_DS_TREE_TRACE
public PB_DS_TREE_TRACE_BASE_C_DEC,
#endif
public Cmp_Fn,
public Node_And_It_Traits::node_update,
public PB_DS_TYPES_TRAITS_C_DEC
{
private:
typedef PB_DS_TYPES_TRAITS_C_DEC traits_base;
 
typedef typename remove_const<typename traits_base::value_type>::type non_const_value_type;
 
typedef typename Allocator::template rebind<non_const_value_type>::other value_allocator;
typedef typename value_allocator::pointer value_vector;
 
 
typedef Cmp_Fn cmp_fn_base;
 
#ifdef _GLIBCXX_DEBUG
typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base;
#endif
 
typedef typename traits_base::pointer mapped_pointer_;
typedef typename traits_base::const_pointer const_mapped_pointer_;
 
typedef typename Node_And_It_Traits::metadata_type metadata_type;
 
typedef typename Allocator::template rebind<metadata_type>::other metadata_allocator;
typedef typename metadata_allocator::pointer metadata_pointer;
typedef typename metadata_allocator::const_reference const_metadata_reference;
typedef typename metadata_allocator::reference metadata_reference;
 
typedef
typename Node_And_It_Traits::null_node_update_pointer
null_node_update_pointer;
 
public:
 
typedef Allocator allocator_type;
typedef typename Allocator::size_type size_type;
typedef typename Allocator::difference_type difference_type;
 
typedef Cmp_Fn cmp_fn;
 
typedef typename Node_And_It_Traits::node_update node_update;
 
typedef typename traits_base::key_type key_type;
typedef typename traits_base::key_pointer key_pointer;
typedef typename traits_base::const_key_pointer const_key_pointer;
typedef typename traits_base::key_reference key_reference;
typedef typename traits_base::const_key_reference const_key_reference;
typedef typename traits_base::mapped_type mapped_type;
typedef typename traits_base::mapped_pointer mapped_pointer;
typedef typename traits_base::const_mapped_pointer const_mapped_pointer;
typedef typename traits_base::mapped_reference mapped_reference;
typedef typename traits_base::const_mapped_reference const_mapped_reference;
typedef typename traits_base::value_type value_type;
typedef typename traits_base::pointer pointer;
typedef typename traits_base::const_pointer const_pointer;
typedef typename traits_base::reference reference;
typedef typename traits_base::const_reference const_reference;
 
typedef const_pointer const_point_iterator;
 
#ifdef PB_DS_DATA_TRUE_INDICATOR
typedef pointer point_iterator;
#else
typedef const_point_iterator point_iterator;
#endif
 
typedef const_point_iterator const_iterator;
 
typedef point_iterator iterator;
 
#include <ext/pb_ds/detail/ov_tree_map_/cond_dtor.hpp>
 
typedef
typename Node_And_It_Traits::const_node_iterator
const_node_iterator;
 
typedef typename Node_And_It_Traits::node_iterator node_iterator;
 
public:
 
PB_DS_OV_TREE_CLASS_NAME();
 
PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn&);
 
PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn&, const node_update&);
 
PB_DS_OV_TREE_CLASS_NAME(const PB_DS_CLASS_C_DEC&);
 
~PB_DS_OV_TREE_CLASS_NAME();
 
void
swap(PB_DS_CLASS_C_DEC&);
 
template<typename It>
void
copy_from_range(It, It);
 
inline size_type
max_size() const;
 
inline bool
empty() const;
 
inline size_type
size() const;
 
Cmp_Fn&
get_cmp_fn();
 
const Cmp_Fn&
get_cmp_fn() const;
 
inline mapped_reference
operator[](const_key_reference r_key)
{
#ifdef PB_DS_DATA_TRUE_INDICATOR
_GLIBCXX_DEBUG_ONLY(assert_valid();)
point_iterator it = lower_bound(r_key);
if (it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it)))
{
_GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key));
_GLIBCXX_DEBUG_ONLY(assert_valid();)
return it->second;
}
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
return (insert_new_val(it, std::make_pair(r_key, mapped_type()))->second);
#else
insert(r_key);
return traits_base::s_null_mapped;
#endif
}
 
inline std::pair<point_iterator, bool>
insert(const_reference r_value)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
const_key_reference r_key = PB_DS_V2F(r_value);
point_iterator it = lower_bound(r_key);
 
if (it != end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*it)))
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key));
return std::make_pair(it, false);
}
 
_GLIBCXX_DEBUG_ONLY(assert_valid();)
return std::make_pair(insert_new_val(it, r_value), true);
}
 
inline point_iterator
lower_bound(const_key_reference r_key)
{
pointer it = m_a_values;
pointer e_it = m_a_values + m_size;
while (it != e_it)
{
pointer mid_it = it + ((e_it - it) >> 1);
if (cmp_fn_base::operator()(PB_DS_V2F(*mid_it), r_key))
it = ++mid_it;
else
e_it = mid_it;
}
return it;
}
 
inline const_point_iterator
lower_bound(const_key_reference r_key) const
{ return const_cast<PB_DS_CLASS_C_DEC& >(*this).lower_bound(r_key); }
 
inline point_iterator
upper_bound(const_key_reference r_key)
{
iterator pot_it = lower_bound(r_key);
if (pot_it != end()&& !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
{
_GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key));
return ++pot_it;
}
 
_GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key));
return pot_it;
}
 
inline const_point_iterator
upper_bound(const_key_reference r_key) const
{ return const_cast<PB_DS_CLASS_C_DEC&>(*this).upper_bound(r_key); }
 
inline point_iterator
find(const_key_reference r_key)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
iterator pot_it = lower_bound(r_key);
if (pot_it != end() && !Cmp_Fn::operator()(r_key, PB_DS_V2F(*pot_it)))
{
_GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key));
return pot_it;
}
 
_GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key));
return end();
}
 
inline const_point_iterator
find(const_key_reference r_key) const
{ return (const_cast<PB_DS_CLASS_C_DEC& >(*this).find(r_key)); }
 
bool
erase(const_key_reference);
 
template<typename Pred>
inline size_type
erase_if(Pred);
 
inline iterator
erase(iterator it)
{ return erase_imp<iterator>(it); }
 
void
clear();
 
void
join(PB_DS_CLASS_C_DEC&);
 
void
split(const_key_reference, PB_DS_CLASS_C_DEC&);
 
inline iterator
begin()
{ return m_a_values; }
 
inline const_iterator
begin() const
{ return m_a_values; }
 
inline iterator
end()
{ return m_end_it; }
 
inline const_iterator
end() const
{ return m_end_it; }
 
inline const_node_iterator
node_begin() const;
 
inline const_node_iterator
node_end() const;
 
inline node_iterator
node_begin();
 
inline node_iterator
node_end();
 
private:
 
inline void
update(node_iterator /*it*/, null_node_update_pointer);
 
template<typename Node_Update>
void
update(node_iterator, Node_Update*);
 
void
reallocate_metadata(null_node_update_pointer, size_type);
 
template<typename Node_Update_>
void
reallocate_metadata(Node_Update_*, size_type);
 
template<typename It>
void
copy_from_ordered_range(It, It);
 
void
value_swap(PB_DS_CLASS_C_DEC&);
 
template<typename It>
void
copy_from_ordered_range(It, It, It, It);
 
template<typename Ptr>
inline static Ptr
mid_pointer(Ptr p_begin, Ptr p_end)
{
_GLIBCXX_DEBUG_ASSERT(p_end >= p_begin);
return (p_begin + (p_end - p_begin) / 2);
}
 
inline iterator
insert_new_val(iterator it, const_reference r_value)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
#ifdef PB_DS_REGRESSION
typename Allocator::group_adjustor adjust(m_size);
#endif
 
_GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(PB_DS_V2F(r_value)));
 
value_vector a_values = s_value_alloc.allocate(m_size + 1);
 
iterator source_it = begin();
iterator source_end_it = end();
iterator target_it = a_values;
iterator ret_it;
 
cond_dtor<size_type> cd(a_values, target_it, m_size + 1);
while (source_it != it)
{
new (const_cast<void* >(static_cast<const void* >(target_it)))
value_type(*source_it++);
++target_it;
}
 
new (const_cast<void* >(static_cast<const void* >(ret_it = target_it)))
value_type(r_value);
++target_it;
 
while (source_it != source_end_it)
{
new (const_cast<void* >(static_cast<const void* >(target_it)))
value_type(*source_it++);
++target_it;
}
 
reallocate_metadata((node_update* )this, m_size + 1);
cd.set_no_action();
if (m_size != 0)
{
cond_dtor<size_type> cd1(m_a_values, m_end_it, m_size);
}
 
++m_size;
m_a_values = a_values;
m_end_it = m_a_values + m_size;
_GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_value)));
update(node_begin(), (node_update* )this);
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
return ret_it;
}
 
#ifdef _GLIBCXX_DEBUG
void
assert_valid() const;
 
void
assert_iterators() const;
#endif
 
template<typename It>
It
erase_imp(It it);
 
inline const_node_iterator
PB_DS_node_begin_imp() const;
 
inline const_node_iterator
PB_DS_node_end_imp() const;
 
inline node_iterator
PB_DS_node_begin_imp();
 
inline node_iterator
PB_DS_node_end_imp();
 
private:
static value_allocator s_value_alloc;
static metadata_allocator s_metadata_alloc;
 
value_vector m_a_values;
metadata_pointer m_a_metadata;
iterator m_end_it;
size_type m_size;
};
 
#include <ext/pb_ds/detail/ov_tree_map_/constructors_destructor_fn_imps.hpp>
#include <ext/pb_ds/detail/ov_tree_map_/iterators_fn_imps.hpp>
#include <ext/pb_ds/detail/ov_tree_map_/debug_fn_imps.hpp>
#include <ext/pb_ds/detail/ov_tree_map_/erase_fn_imps.hpp>
#include <ext/pb_ds/detail/ov_tree_map_/insert_fn_imps.hpp>
#include <ext/pb_ds/detail/ov_tree_map_/info_fn_imps.hpp>
#include <ext/pb_ds/detail/ov_tree_map_/split_join_fn_imps.hpp>
#include <ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp>
 
#undef PB_DS_CLASS_C_DEC
#undef PB_DS_CLASS_T_DEC
#undef PB_DS_OV_TREE_CLASS_NAME
#undef PB_DS_TYPES_TRAITS_C_DEC
#undef PB_DS_DEBUG_MAP_BASE_C_DEC
#ifdef PB_DS_TREE_TRACE
#undef PB_DS_TREE_TRACE_BASE_C_DEC
#endif
 
#undef PB_DS_V2F
#undef PB_DS_EP2VP
#undef PB_DS_V2S
#undef PB_DS_CONST_NODE_ITERATOR_NAME
 
} // namespace detail
} // namespace __gnu_pbds
/constructors_destructor_fn_imps.hpp
0,0 → 1,273
// -*- 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 class for ov_tree_.
*/
 
PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::value_allocator
PB_DS_CLASS_C_DEC::s_value_alloc;
 
PB_DS_CLASS_T_DEC
typename PB_DS_CLASS_C_DEC::metadata_allocator
PB_DS_CLASS_C_DEC::s_metadata_alloc;
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_OV_TREE_CLASS_NAME() :
m_a_values(NULL),
m_a_metadata(NULL),
m_end_it(NULL),
m_size(0)
{ _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) }
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn) :
cmp_fn_base(r_cmp_fn),
m_a_values(NULL),
m_a_metadata(NULL),
m_end_it(NULL),
m_size(0)
{ _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) }
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_OV_TREE_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_node_update) :
cmp_fn_base(r_cmp_fn),
node_update(r_node_update),
m_a_values(NULL),
m_a_metadata(NULL),
m_end_it(NULL),
m_size(0)
{ _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) }
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
PB_DS_OV_TREE_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) :
#ifdef _GLIBCXX_DEBUG
debug_base(other),
#endif
#ifdef PB_DS_TREE_TRACE
PB_DS_TREE_TRACE_BASE_C_DEC(other),
#endif
cmp_fn_base(other),
node_update(other),
m_a_values(NULL),
m_a_metadata(NULL),
m_end_it(NULL),
m_size(0)
{
copy_from_ordered_range(other.begin(), other.end());
_GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();)
}
 
PB_DS_CLASS_T_DEC
template<typename It>
inline void
PB_DS_CLASS_C_DEC::
copy_from_range(It first_it, It last_it)
{
#ifdef PB_DS_DATA_TRUE_INDICATOR
typedef
std::map<
key_type,
mapped_type,
Cmp_Fn,
typename Allocator::template rebind<
value_type>::other>
map_type;
#else
typedef
std::set<
key_type,
Cmp_Fn,
typename Allocator::template rebind<
Key>::other>
map_type;
#endif
 
map_type m(first_it, last_it);
copy_from_ordered_range(m.begin(), m.end());
}
 
PB_DS_CLASS_T_DEC
template<typename It>
void
PB_DS_CLASS_C_DEC::
copy_from_ordered_range(It first_it, It last_it)
{
const size_type len = std::distance(first_it, last_it);
if (len == 0)
return;
 
value_vector a_values = s_value_alloc.allocate(len);
iterator target_it = a_values;
It source_it = first_it;
It source_end_it = last_it;
 
cond_dtor<size_type> cd(a_values, target_it, len);
while (source_it != source_end_it)
{
new (const_cast<void* >(static_cast<const void* >(target_it)))
value_type(*source_it++);
 
++target_it;
}
 
reallocate_metadata((node_update* )this, len);
cd.set_no_action();
m_a_values = a_values;
m_size = len;
m_end_it = m_a_values + m_size;
update(PB_DS_node_begin_imp(), (node_update* )this);
 
#ifdef _GLIBCXX_DEBUG
const_iterator dbg_it = m_a_values;
while (dbg_it != m_end_it)
{
debug_base::insert_new(PB_DS_V2F(*dbg_it));
dbg_it++;
}
PB_DS_CLASS_C_DEC::assert_valid();
#endif
}
 
PB_DS_CLASS_T_DEC
template<typename It>
void
PB_DS_CLASS_C_DEC::
copy_from_ordered_range(It first_it, It last_it, It other_first_it,
It other_last_it)
{
clear();
const size_type len = std::distance(first_it, last_it)
+ std::distance(other_first_it, other_last_it);
 
value_vector a_values = s_value_alloc.allocate(len);
 
iterator target_it = a_values;
It source_it = first_it;
It source_end_it = last_it;
 
cond_dtor<size_type> cd(a_values, target_it, len);
while (source_it != source_end_it)
{
new (const_cast<void* >(static_cast<const void* >(target_it)))
value_type(*source_it++);
++target_it;
}
 
source_it = other_first_it;
source_end_it = other_last_it;
 
while (source_it != source_end_it)
{
new (const_cast<void* >(static_cast<const void* >(target_it)))
value_type(*source_it++);
++target_it;
}
 
reallocate_metadata((node_update* )this, len);
cd.set_no_action();
m_a_values = a_values;
m_size = len;
m_end_it = m_a_values + m_size;
update(PB_DS_node_begin_imp(), (node_update* )this);
 
#ifdef _GLIBCXX_DEBUG
const_iterator dbg_it = m_a_values;
while (dbg_it != m_end_it)
{
debug_base::insert_new(PB_DS_V2F(*dbg_it));
dbg_it++;
}
PB_DS_CLASS_C_DEC::assert_valid();
#endif
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
swap(PB_DS_CLASS_C_DEC& other)
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
value_swap(other);
std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )other);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
value_swap(PB_DS_CLASS_C_DEC& other)
{
std::swap(m_a_values, other.m_a_values);
std::swap(m_a_metadata, other.m_a_metadata);
std::swap(m_size, other.m_size);
std::swap(m_end_it, other.m_end_it);
_GLIBCXX_DEBUG_ONLY(debug_base::swap(other);)
}
 
PB_DS_CLASS_T_DEC
PB_DS_CLASS_C_DEC::
~PB_DS_OV_TREE_CLASS_NAME()
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
cond_dtor<size_type> cd(m_a_values, m_end_it, m_size);
reallocate_metadata((node_update* )this, 0);
}
 
PB_DS_CLASS_T_DEC
inline void
PB_DS_CLASS_C_DEC::
update(node_iterator /*it*/, null_node_update_pointer)
{ }
 
PB_DS_CLASS_T_DEC
template<typename Node_Update>
void
PB_DS_CLASS_C_DEC::
update(node_iterator nd_it, Node_Update* p_update)
{
const_node_iterator end_it = PB_DS_node_end_imp();
if (nd_it == end_it)
return;
update(nd_it.get_l_child(), p_update);
update(nd_it.get_r_child(), p_update);
node_update::operator()(nd_it, end_it);
}
/debug_fn_imps.hpp
0,0 → 1,84
// -*- 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 class for ov_tree_.
*/
 
#ifdef _GLIBCXX_DEBUG
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_valid() const
{
std::cout << "av1" << std::endl;
 
if (m_a_values == NULL || m_end_it == NULL || m_size == 0)
_GLIBCXX_DEBUG_ASSERT(m_a_values == NULL && m_end_it == NULL && m_size == 0);
 
std::cout << "av2" << std::endl;
assert_iterators();
std::cout << "av3" << std::endl;
}
 
PB_DS_CLASS_T_DEC
void
PB_DS_CLASS_C_DEC::
assert_iterators() const
{
debug_base::check_size(m_size);
size_type iterated_num = 0;
const_iterator prev_it = end();
_GLIBCXX_DEBUG_ASSERT( m_end_it == m_a_values + m_size);
for (const_iterator it = begin(); it != end(); ++it)
{
++iterated_num;
_GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(PB_DS_V2F(*it));)
_GLIBCXX_DEBUG_ASSERT(lower_bound(PB_DS_V2F(*it)) == it);
const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*it));
--upper_bound_it;
_GLIBCXX_DEBUG_ASSERT(upper_bound_it == it);
if (prev_it != end())
_GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*prev_it),
PB_DS_V2F(*it)));
prev_it = it;
}
_GLIBCXX_DEBUG_ASSERT(iterated_num == m_size);
}
 
#endif
 
/node_iterators.hpp
0,0 → 1,292
// -*- C++ -*-
 
// Copyright (C) 2005, 2006, 2007, 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_iterators.hpp
* Contains an implementation class for ov_tree_.
*/
 
#ifndef PB_DS_OV_TREE_NODE_ITERATORS_HPP
#define PB_DS_OV_TREE_NODE_ITERATORS_HPP
 
#include <ext/pb_ds/tag_and_trait.hpp>
#include <ext/pb_ds/detail/type_utils.hpp>
#include <debug/debug.h>
 
namespace __gnu_pbds
{
namespace detail
{
 
#define PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC \
ov_tree_node_const_it_<Value_Type, Metadata_Type, Allocator>
 
// Const node reference.
template<typename Value_Type, typename Metadata_Type, class Allocator>
class ov_tree_node_const_it_
{
 
protected:
typedef
typename Allocator::template rebind<
Value_Type>::other::pointer
pointer;
 
typedef
typename Allocator::template rebind<
Value_Type>::other::const_pointer
const_pointer;
 
typedef
typename Allocator::template rebind<
Metadata_Type>::other::const_pointer
const_metadata_pointer;
 
typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC this_type;
 
protected:
 
template<typename Ptr>
inline static Ptr
mid_pointer(Ptr p_begin, Ptr p_end)
{
_GLIBCXX_DEBUG_ASSERT(p_end >= p_begin);
return (p_begin + (p_end - p_begin) / 2);
}
 
public:
 
typedef trivial_iterator_tag iterator_category;
 
typedef trivial_iterator_difference_type difference_type;
 
typedef
typename Allocator::template rebind<
Value_Type>::other::const_pointer
value_type;
 
typedef
typename Allocator::template rebind<
typename remove_const<
Value_Type>::type>::other::const_pointer
reference;
 
typedef
typename Allocator::template rebind<
typename remove_const<
Value_Type>::type>::other::const_pointer
const_reference;
 
typedef Metadata_Type metadata_type;
 
typedef
typename Allocator::template rebind<
metadata_type>::other::const_reference
const_metadata_reference;
 
public:
inline
ov_tree_node_const_it_(const_pointer p_nd = NULL, const_pointer p_begin_nd = NULL, const_pointer p_end_nd = NULL, const_metadata_pointer p_metadata = NULL) : m_p_value(const_cast<pointer>(p_nd)), m_p_begin_value(const_cast<pointer>(p_begin_nd)), m_p_end_value(const_cast<pointer>(p_end_nd)), m_p_metadata(p_metadata)
{ }
 
inline const_reference
operator*() const
{ return m_p_value; }
 
inline const_metadata_reference
get_metadata() const
{
enum
{
has_metadata = !is_same<Metadata_Type, null_node_metadata>::value
};
 
PB_DS_STATIC_ASSERT(should_have_metadata, has_metadata);
_GLIBCXX_DEBUG_ASSERT(m_p_metadata != NULL);
return *m_p_metadata;
}
 
inline this_type
get_l_child() const
{
if (m_p_begin_value == m_p_value)
return (this_type(m_p_begin_value, m_p_begin_value, m_p_begin_value));
 
const_metadata_pointer p_begin_metadata =
m_p_metadata - (m_p_value - m_p_begin_value);
 
return (this_type(mid_pointer(m_p_begin_value, m_p_value),
m_p_begin_value,
m_p_value,
mid_pointer(p_begin_metadata, m_p_metadata)));
}
 
inline this_type
get_r_child() const
{
if (m_p_value == m_p_end_value)
return (this_type(m_p_end_value, m_p_end_value, m_p_end_value));
 
const_metadata_pointer p_end_metadata =
m_p_metadata + (m_p_end_value - m_p_value);
 
return (this_type(mid_pointer(m_p_value + 1, m_p_end_value),
m_p_value + 1,
m_p_end_value,(m_p_metadata == NULL) ?
NULL : mid_pointer(m_p_metadata + 1, p_end_metadata)));
}
 
inline bool
operator==(const this_type& other) const
{
const bool is_end = m_p_begin_value == m_p_end_value;
const bool is_other_end = other.m_p_begin_value == other.m_p_end_value;
 
if (is_end)
return (is_other_end);
 
if (is_other_end)
return (is_end);
 
return m_p_value == other.m_p_value;
}
 
inline bool
operator!=(const this_type& other) const
{ return !operator==(other); }
 
public:
pointer m_p_value;
pointer m_p_begin_value;
pointer m_p_end_value;
 
const_metadata_pointer m_p_metadata;
};
 
#define PB_DS_OV_TREE_NODE_ITERATOR_C_DEC \
ov_tree_node_it_<Value_Type, Metadata_Type, Allocator>
 
// Node reference.
template<typename Value_Type, typename Metadata_Type, class Allocator>
class ov_tree_node_it_ : public PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC
{
 
private:
typedef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC this_type;
 
typedef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC base_type;
 
typedef typename base_type::pointer pointer;
 
typedef typename base_type::const_pointer const_pointer;
 
typedef
typename base_type::const_metadata_pointer
const_metadata_pointer;
 
public:
 
typedef trivial_iterator_tag iterator_category;
 
typedef trivial_iterator_difference_type difference_type;
 
typedef
typename Allocator::template rebind<
Value_Type>::other::pointer
value_type;
 
typedef
typename Allocator::template rebind<
typename remove_const<
Value_Type>::type>::other::pointer
reference;
 
typedef
typename Allocator::template rebind<
typename remove_const<
Value_Type>::type>::other::pointer
const_reference;
 
public:
inline
ov_tree_node_it_(const_pointer p_nd = NULL, const_pointer p_begin_nd = NULL, const_pointer p_end_nd = NULL, const_metadata_pointer p_metadata = NULL) : base_type(p_nd, p_begin_nd, p_end_nd, p_metadata)
{ }
 
// Access.
inline reference
operator*() const
{ return reference(base_type::m_p_value); }
 
// Returns the node reference associated with the left node.
inline ov_tree_node_it_
get_l_child() const
{
if (base_type::m_p_begin_value == base_type::m_p_value)
return (this_type(base_type::m_p_begin_value, base_type::m_p_begin_value, base_type::m_p_begin_value));
 
const_metadata_pointer p_begin_metadata =
base_type::m_p_metadata - (base_type::m_p_value - base_type::m_p_begin_value);
 
return (this_type(base_type::mid_pointer(base_type::m_p_begin_value, base_type::m_p_value),
base_type::m_p_begin_value,
base_type::m_p_value,
base_type::mid_pointer(p_begin_metadata, base_type::m_p_metadata)));
}
 
// Returns the node reference associated with the right node.
inline ov_tree_node_it_
get_r_child() const
{
if (base_type::m_p_value == base_type::m_p_end_value)
return (this_type(base_type::m_p_end_value, base_type::m_p_end_value, base_type::m_p_end_value));
 
const_metadata_pointer p_end_metadata =
base_type::m_p_metadata + (base_type::m_p_end_value - base_type::m_p_value);
 
return (this_type(base_type::mid_pointer(base_type::m_p_value + 1, base_type::m_p_end_value),
base_type::m_p_value + 1,
base_type::m_p_end_value,(base_type::m_p_metadata == NULL)?
NULL : base_type::mid_pointer(base_type::m_p_metadata + 1, p_end_metadata)));
}
 
};
 
#undef PB_DS_OV_TREE_NODE_ITERATOR_C_DEC
#undef PB_DS_OV_TREE_CONST_NODE_ITERATOR_C_DEC
 
} // namespace detail
} // namespace __gnu_pbds
 
#endif
/split_join_fn_imps.hpp
0,0 → 1,137
// -*- 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 class for ov_tree_.
*/
 
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(other.assert_valid();)
 
if (m_size == 0)
{
other.clear();
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return;
}
 
if (Cmp_Fn::operator()(r_key, PB_DS_V2F(*begin())))
{
value_swap(other);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return;
}
 
if (!Cmp_Fn::operator()(r_key, PB_DS_V2F(*(end() - 1))))
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return;
}
 
if (m_size == 1)
{
value_swap(other);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
return;
}
 
_GLIBCXX_DEBUG_ONLY(debug_base::join(other);)
iterator it = upper_bound(r_key);
PB_DS_CLASS_C_DEC new_other(other, other);
new_other.copy_from_ordered_range(it, end());
PB_DS_CLASS_C_DEC new_this(*this, * this);
new_this.copy_from_ordered_range(begin(), it);
 
// No exceptions from this point.
_GLIBCXX_DEBUG_ONLY(debug_base::split(r_key,(Cmp_Fn& )(*this), other);)
other.update(other.node_begin(), (node_update* )(&other));
update(node_begin(), (node_update* )this);
other.value_swap(new_other);
value_swap(new_this);
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}
 
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();)
if (other.m_size == 0)
return;
 
if (m_size == 0)
{
value_swap(other);
return;
}
 
const bool greater = Cmp_Fn::operator()(PB_DS_V2F(*(end() - 1)),
PB_DS_V2F(*other.begin()));
 
const bool lesser = Cmp_Fn::operator()(PB_DS_V2F(*(other.end() - 1)),
PB_DS_V2F(*begin()));
 
if (!greater && !lesser)
__throw_join_error();
 
PB_DS_CLASS_C_DEC new_this(*this, *this);
 
if (greater)
new_this.copy_from_ordered_range(begin(), end(),
other.begin(), other.end());
else
new_this.copy_from_ordered_range(other.begin(), other.end(),
begin(), end());
 
// No exceptions from this point.
_GLIBCXX_DEBUG_ONLY(debug_base::join(other);)
value_swap(new_this);
other.clear();
_GLIBCXX_DEBUG_ONLY(assert_valid();)
_GLIBCXX_DEBUG_ONLY(other.assert_valid();)
}
/info_fn_imps.hpp
0,0 → 1,60
// -*- 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 class for ov_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::size_type
PB_DS_CLASS_C_DEC::
size() const
{
_GLIBCXX_DEBUG_ONLY(assert_valid();)
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_value_alloc.max_size(); }
 
PB_DS_CLASS_T_DEC
inline bool
PB_DS_CLASS_C_DEC::
empty() const
{ return size() == 0; }
/traits.hpp
0,0 → 1,183
// -*- 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 class for ov_tree_.
*/
 
#ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP
#define PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP
 
#include <ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp>
 
namespace __gnu_pbds
{
namespace detail
{
 
template<typename Key,
typename Mapped,
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,
Mapped,
Cmp_Fn,
Node_Update,
ov_tree_tag,
Allocator>
{
private:
typedef
typename types_traits<
Key,
Mapped,
Allocator,
false>::value_type
value_type;
 
public:
typedef
typename tree_node_metadata_selector<
Key,
Mapped,
Cmp_Fn,
Node_Update,
Allocator>::type
metadata_type;
 
typedef
ov_tree_node_const_it_<
value_type,
metadata_type,
Allocator>
const_node_iterator;
 
typedef
ov_tree_node_it_<
value_type,
metadata_type,
Allocator>
node_iterator;
 
typedef
Node_Update<
const_node_iterator,
node_iterator,
Cmp_Fn,
Allocator>
node_update;
 
typedef
__gnu_pbds::null_tree_node_update<
const_node_iterator,
node_iterator,
Cmp_Fn,
Allocator>*
null_node_update_pointer;
};
 
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,
ov_tree_tag,
Allocator>
{
private:
typedef
typename types_traits<
Key,
null_mapped_type,
Allocator,
false>::value_type
value_type;
 
public:
typedef
typename tree_node_metadata_selector<
Key,
null_mapped_type,
Cmp_Fn,
Node_Update,
Allocator>::type
metadata_type;
 
typedef
ov_tree_node_const_it_<
value_type,
metadata_type,
Allocator>
const_node_iterator;
 
typedef const_node_iterator node_iterator;
 
typedef
Node_Update<
const_node_iterator,
const_node_iterator,
Cmp_Fn,
Allocator>
node_update;
 
typedef
__gnu_pbds::null_tree_node_update<
const_node_iterator,
node_iterator,
Cmp_Fn,
Allocator>*
null_node_update_pointer;
};
 
} // namespace detail
} // namespace __gnu_pbds
 
#endif // #ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP
 
/iterators_fn_imps.hpp
0,0 → 1,103
// -*- 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 iterators_fn_imps.hpp
* Contains an implementation class for ov_tree_.
*/
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_node_iterator
PB_DS_CLASS_C_DEC::
node_begin() const
{ return PB_DS_node_begin_imp(); }
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_node_iterator
PB_DS_CLASS_C_DEC::
node_end() const
{ return PB_DS_node_end_imp(); }
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_iterator
PB_DS_CLASS_C_DEC::
node_begin()
{ return PB_DS_node_begin_imp(); }
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_iterator
PB_DS_CLASS_C_DEC::
node_end()
{ return PB_DS_node_end_imp(); }
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_node_iterator
PB_DS_CLASS_C_DEC::
PB_DS_node_begin_imp() const
{
return const_node_iterator(const_cast<pointer>(mid_pointer(begin(), end())),
const_cast<pointer>(begin()),
const_cast<pointer>(end()),(m_a_metadata == NULL)?
NULL :
mid_pointer(m_a_metadata, m_a_metadata + m_size));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::const_node_iterator
PB_DS_CLASS_C_DEC::
PB_DS_node_end_imp() const
{
return const_node_iterator(end(), end(), end(),
(m_a_metadata == NULL) ? NULL : m_a_metadata + m_size);
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_iterator
PB_DS_CLASS_C_DEC::
PB_DS_node_begin_imp()
{
return node_iterator(mid_pointer(begin(), end()), begin(), end(),
(m_a_metadata == NULL) ? NULL : mid_pointer(m_a_metadata, m_a_metadata + m_size));
}
 
PB_DS_CLASS_T_DEC
inline typename PB_DS_CLASS_C_DEC::node_iterator
PB_DS_CLASS_C_DEC::
PB_DS_node_end_imp()
{
return node_iterator(end(), end(),
end(),(m_a_metadata == NULL) ? NULL : m_a_metadata + m_size);
}
 

powered by: WebSVN 2.1.0

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