diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_')
17 files changed, 3197 insertions, 0 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp new file mode 100644 index 000000000..7315d951f --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/bin_search_tree_.hpp @@ -0,0 +1,497 @@ +// -*- 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 bin_search_tree_.hpp + * Contains an implementation class for bin_search_tree_. + */ +/* + * This implementation uses an idea from the SGI STL (using a "header" node + * which is needed for efficient iteration). + */ + +#include <ext/pb_ds/exception.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/tree_policy.hpp> +#include <ext/pb_ds/detail/cond_dealtor.hpp> +#include <ext/pb_ds/detail/type_utils.hpp> +#include <ext/pb_ds/detail/tree_trace_base.hpp> +#include <utility> +#include <functional> +#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_CLASS_NAME \ + bin_search_tree_data_ +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR +#define PB_DS_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_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, \ + true, \ + Allocator> +#endif + + /** + * class description = "8i|\|4ree $34rc|-| 7r33 74813."> + **/ + template<typename Key, + typename Mapped, + class Cmp_Fn, + class Node_And_It_Traits, + class Allocator> + class PB_DS_CLASS_NAME : +#ifdef _GLIBCXX_DEBUG + public 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 PB_DS_TYPES_TRAITS_C_DEC, + public Node_And_It_Traits::node_update + { + + protected: + typedef + typename Allocator::template rebind< + typename Node_And_It_Traits::node>::other + node_allocator; + + typedef typename node_allocator::value_type node; + + typedef typename node_allocator::pointer node_pointer; + + typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; + + typedef + typename Node_And_It_Traits::null_node_update_pointer + null_node_update_pointer; + + private: + typedef cond_dealtor< node, Allocator> cond_dealtor_t; + +#ifdef _GLIBCXX_DEBUG + typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; +#endif + + public: + + typedef typename Allocator::size_type size_type; + + typedef typename Allocator::difference_type difference_type; + + typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_type key_type; + + typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_pointer key_pointer; + + typedef + typename PB_DS_TYPES_TRAITS_C_DEC::const_key_pointer + const_key_pointer; + + typedef typename PB_DS_TYPES_TRAITS_C_DEC::key_reference key_reference; + + typedef + typename PB_DS_TYPES_TRAITS_C_DEC::const_key_reference + const_key_reference; + +#ifdef PB_DS_DATA_TRUE_INDICATOR + typedef typename PB_DS_TYPES_TRAITS_C_DEC::mapped_type mapped_type; + + typedef + typename PB_DS_TYPES_TRAITS_C_DEC::mapped_pointer + mapped_pointer; + + typedef + typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_pointer + const_mapped_pointer; + + typedef + typename PB_DS_TYPES_TRAITS_C_DEC::mapped_reference + mapped_reference; + + typedef + typename PB_DS_TYPES_TRAITS_C_DEC::const_mapped_reference + const_mapped_reference; +#endif + + typedef typename PB_DS_TYPES_TRAITS_C_DEC::value_type value_type; + + typedef typename PB_DS_TYPES_TRAITS_C_DEC::pointer pointer; + + typedef typename PB_DS_TYPES_TRAITS_C_DEC::const_pointer const_pointer; + + typedef typename PB_DS_TYPES_TRAITS_C_DEC::reference reference; + + typedef + typename PB_DS_TYPES_TRAITS_C_DEC::const_reference + const_reference; + + typedef + typename Node_And_It_Traits::const_point_iterator + const_point_iterator; + + typedef const_point_iterator const_iterator; + + typedef typename Node_And_It_Traits::point_iterator point_iterator; + + typedef point_iterator iterator; + + typedef + typename Node_And_It_Traits::const_reverse_iterator + const_reverse_iterator; + + typedef typename Node_And_It_Traits::reverse_iterator reverse_iterator; + + typedef + typename Node_And_It_Traits::const_node_iterator + const_node_iterator; + + typedef typename Node_And_It_Traits::node_iterator node_iterator; + + typedef Cmp_Fn cmp_fn; + + typedef Allocator allocator_type; + + typedef typename Node_And_It_Traits::node_update node_update; + + public: + + PB_DS_CLASS_NAME(); + + PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn); + + PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn, const node_update& r_update); + + PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other); + + void + swap(PB_DS_CLASS_C_DEC& other); + + ~PB_DS_CLASS_NAME(); + + inline bool + empty() const; + + inline size_type + size() const; + + inline size_type + max_size() const; + + Cmp_Fn& + get_cmp_fn(); + + const Cmp_Fn& + get_cmp_fn() const; + + inline point_iterator + lower_bound(const_key_reference r_key); + + inline const_point_iterator + lower_bound(const_key_reference r_key) const; + + inline point_iterator + upper_bound(const_key_reference r_key); + + inline const_point_iterator + upper_bound(const_key_reference r_key) const; + + inline point_iterator + find(const_key_reference r_key); + + inline const_point_iterator + find(const_key_reference r_key) const; + + inline iterator + begin(); + + inline const_iterator + begin() const; + + inline iterator + end(); + + inline const_iterator + end() const; + + inline reverse_iterator + rbegin(); + + inline const_reverse_iterator + rbegin() const; + + inline reverse_iterator + rend(); + + inline const_reverse_iterator + rend() const; + + inline const_node_iterator + node_begin() const; + + inline node_iterator + node_begin(); + + inline const_node_iterator + node_end() const; + + inline node_iterator + node_end(); + + void + clear(); + + protected: + + void + value_swap(PB_DS_CLASS_C_DEC& other); + + void + initialize_min_max(); + + inline iterator + insert_imp_empty(const_reference r_value); + + inline iterator + insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd); + + inline node_pointer + get_new_node_for_leaf_insert(const_reference r_val, false_type); + + inline node_pointer + get_new_node_for_leaf_insert(const_reference r_val, true_type); + + inline void + actual_erase_node(node_pointer p_nd); + + inline std::pair<node_pointer, bool> + erase(node_pointer p_nd); + + inline void + update_min_max_for_erased_node(node_pointer p_nd); + + static void + clear_imp(node_pointer p_nd); + + inline std::pair< + point_iterator, + bool> + insert_leaf(const_reference r_value); + + inline void + rotate_left(node_pointer p_x); + + inline void + rotate_right(node_pointer p_y); + + inline void + rotate_parent(node_pointer p_nd); + + inline void + apply_update(node_pointer p_nd, null_node_update_pointer); + + template<typename Node_Update_> + inline void + apply_update(node_pointer p_nd, Node_Update_* p_update); + + inline void + update_to_top(node_pointer p_nd, null_node_update_pointer); + + template<typename Node_Update_> + inline void + update_to_top(node_pointer p_nd, Node_Update_* p_update); + + bool + join_prep(PB_DS_CLASS_C_DEC& other); + + void + join_finish(PB_DS_CLASS_C_DEC& other); + + bool + split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other); + + void + split_finish(PB_DS_CLASS_C_DEC& other); + + size_type + recursive_count(node_pointer p_nd) const; + +#ifdef _GLIBCXX_DEBUG + void + assert_valid() const; + + void + structure_only_assert_valid() const; + + void + assert_node_consistent(const node_pointer p_nd) const; +#endif + + private: +#ifdef _GLIBCXX_DEBUG + void + assert_iterators() const; + + void + assert_consistent_with_debug_base() const; + + void + assert_node_consistent_with_left(const node_pointer p_nd) const; + + void + assert_node_consistent_with_right(const node_pointer p_nd) const; + + void + assert_consistent_with_debug_base(const node_pointer p_nd) const; + + void + assert_min() const; + + void + assert_min_imp(const node_pointer p_nd) const; + + void + assert_max() const; + + void + assert_max_imp(const node_pointer p_nd) const; + + void + assert_size() const; + + typedef std::pair< const_pointer, const_pointer> node_consistent_t; + + node_consistent_t + assert_node_consistent_(const node_pointer p_nd) const; +#endif + + void + initialize(); + + node_pointer + recursive_copy_node(const node_pointer p_nd); + + protected: + node_pointer m_p_head; + + size_type m_size; + + static node_allocator s_node_allocator; + }; + +#include <ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp> +#include <ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp> +#include <ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp> +#include <ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp> +#include <ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp> +#include <ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp> +#include <ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp> +#include <ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp> +#include <ext/pb_ds/detail/bin_search_tree_/rotate_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_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 + + } // namespace detail +} // namespace __gnu_pbds diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_dtor_entry_dealtor.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_dtor_entry_dealtor.hpp new file mode 100644 index 000000000..370574c90 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_dtor_entry_dealtor.hpp @@ -0,0 +1,70 @@ +// -*- 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_entry_dealtor.hpp + * Contains a binary tree container conditional deallocator + */ + +class bin_search_tree_cond_dtor_entry_dealtor_ +{ +public: + inline + bin_search_tree_cond_dtor_entry_dealtor_(node_pointer p_nd) : m_p_nd(p_nd), + m_no_action_dtor(false) + { } + + inline void + set_no_action_dtor() + { + m_no_action_dtor = true; + } + + inline + ~bin_search_tree_cond_dtor_entry_dealtor_() + { + if (m_no_action_dtor) + return; + + typename Allocator::template rebind<Node>::other(). + deallocate(m_p_nd, 1); + } + +protected: + node_pointer m_p_nd; + + bool m_no_action_dtor; +}; + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_key_dtor_entry_dealtor.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_key_dtor_entry_dealtor.hpp new file mode 100644 index 000000000..612ecebbe --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/cond_key_dtor_entry_dealtor.hpp @@ -0,0 +1,81 @@ +// -*- 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_key_dtor_entry_dealtor.hpp + * Contains a binary tree container conditional deallocator + */ + +class bin_seach_tree_cond_key_dtor_entry_dealtor_ +{ +public: + inline + bin_seach_tree_cond_key_dtor_entry_dealtor_(node_pointer p_nd) : m_p_nd(p_nd), + m_no_action_dtor(false), + m_key_destruct(false) + { } + + inline void + set_no_action_dtor() + { + m_no_action_dtor = true; + } + + inline void + set_key_destruct() + { + m_key_destruct = true; + } + + inline + ~bin_seach_tree_cond_key_dtor_entry_dealtor_() + { + if (m_no_action_dtor) + return; + + if (m_key_destruct) + m_p_nd->m_value.first.~Key(); + + bin_tree_base::s_alloc.deallocate(m_p_nd, 1); + } + +protected: + node_pointer m_p_nd; + + bool m_no_action_dtor; + + bool m_key_destruct; +}; + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp new file mode 100644 index 000000000..925d204dc --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/constructors_destructor_fn_imps.hpp @@ -0,0 +1,218 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 2008, 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 bin_search_tree_. + */ + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::node_allocator +PB_DS_CLASS_C_DEC::s_node_allocator; + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME() : m_p_head(s_node_allocator.allocate(1)), m_size(0) +{ + initialize(); + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME(const Cmp_Fn& r_cmp_fn) : + Cmp_Fn(r_cmp_fn), m_p_head(s_node_allocator.allocate(1)), m_size(0) +{ + initialize(); + _GLIBCXX_DEBUG_ONLY(structure_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) : + Cmp_Fn(r_cmp_fn), + node_update(r_node_update), + m_p_head(s_node_allocator.allocate(1)), + m_size(0) +{ + initialize(); + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) : +#ifdef _GLIBCXX_DEBUG + debug_base(other), +#endif +#ifdef PB_DS_TREE_TRACE + PB_DS_TREE_TRACE_BASE_C_DEC(other), +#endif + Cmp_Fn(other), + node_update(other), + m_p_head(s_node_allocator.allocate(1)), + m_size(0) +{ + initialize(); + m_size = other.m_size; + _GLIBCXX_DEBUG_ONLY(other.structure_only_assert_valid();) + + __try + { + m_p_head->m_p_parent = recursive_copy_node(other.m_p_head->m_p_parent); + if (m_p_head->m_p_parent != NULL) + m_p_head->m_p_parent->m_p_parent = m_p_head; + m_size = other.m_size; + initialize_min_max(); + } + __catch(...) + { + _GLIBCXX_DEBUG_ONLY(debug_base::clear();) + s_node_allocator.deallocate(m_p_head, 1); + __throw_exception_again; + } + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +swap(PB_DS_CLASS_C_DEC& other) +{ + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.structure_only_assert_valid();) + value_swap(other); + std::swap((Cmp_Fn& )(*this), (Cmp_Fn& )other); + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.structure_only_assert_valid();) +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +value_swap(PB_DS_CLASS_C_DEC& other) +{ + _GLIBCXX_DEBUG_ONLY(debug_base::swap(other);) + std::swap(m_p_head, other.m_p_head); + std::swap(m_size, other.m_size); +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +~PB_DS_CLASS_NAME() +{ + clear(); + s_node_allocator.deallocate(m_p_head, 1); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +initialize() +{ + m_p_head->m_p_parent = NULL; + m_p_head->m_p_left = m_p_head; + m_p_head->m_p_right = m_p_head; + m_size = 0; +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::node_pointer +PB_DS_CLASS_C_DEC:: +recursive_copy_node(const node_pointer p_nd) +{ + if (p_nd == NULL) + return (NULL); + + node_pointer p_ret = s_node_allocator.allocate(1); + __try + { + new (p_ret) node(*p_nd); + } + __catch(...) + { + s_node_allocator.deallocate(p_ret, 1); + __throw_exception_again; + } + + p_ret->m_p_left = p_ret->m_p_right = NULL; + + __try + { + p_ret->m_p_left = recursive_copy_node(p_nd->m_p_left); + p_ret->m_p_right = recursive_copy_node(p_nd->m_p_right); + } + __catch(...) + { + clear_imp(p_ret); + __throw_exception_again; + } + + if (p_ret->m_p_left != NULL) + p_ret->m_p_left->m_p_parent = p_ret; + + if (p_ret->m_p_right != NULL) + p_ret->m_p_right->m_p_parent = p_ret; + + _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_ret);) + return p_ret; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +initialize_min_max() +{ + if (m_p_head->m_p_parent == NULL) + { + m_p_head->m_p_left = m_p_head->m_p_right = m_p_head; + return; + } + + { + node_pointer p_min = m_p_head->m_p_parent; + while (p_min->m_p_left != NULL) + p_min = p_min->m_p_left; + m_p_head->m_p_left = p_min; + } + + { + node_pointer p_max = m_p_head->m_p_parent; + while (p_max->m_p_right != NULL) + p_max = p_max->m_p_right; + m_p_head->m_p_right = p_max; + } +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp new file mode 100644 index 000000000..e3447bd4b --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/debug_fn_imps.hpp @@ -0,0 +1,272 @@ +// -*- 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 bin_search_tree_. + */ + +#ifdef _GLIBCXX_DEBUG + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_valid() const +{ + structure_only_assert_valid(); + assert_consistent_with_debug_base(); + assert_size(); + assert_iterators(); + if (m_p_head->m_p_parent == NULL) + { + _GLIBCXX_DEBUG_ASSERT(m_size == 0); + } + else + { + _GLIBCXX_DEBUG_ASSERT(m_size > 0); + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +structure_only_assert_valid() const +{ + _GLIBCXX_DEBUG_ASSERT(m_p_head != NULL); + if (m_p_head->m_p_parent == NULL) + { + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head); + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head); + } + else + { + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent->m_p_parent == m_p_head); + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left != m_p_head); + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right != m_p_head); + } + + if (m_p_head->m_p_parent != NULL) + assert_node_consistent(m_p_head->m_p_parent); + assert_min(); + assert_max(); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_node_consistent(const node_pointer p_nd) const +{ + assert_node_consistent_(p_nd); +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::node_consistent_t +PB_DS_CLASS_C_DEC:: +assert_node_consistent_(const node_pointer p_nd) const +{ + if (p_nd == NULL) + return (std::make_pair((const_pointer)NULL,(const_pointer)NULL)); + + assert_node_consistent_with_left(p_nd); + assert_node_consistent_with_right(p_nd); + + const std::pair<const_pointer, const_pointer> + l_range = assert_node_consistent_(p_nd->m_p_left); + + if (l_range.second != NULL) + _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(*l_range.second), + PB_DS_V2F(p_nd->m_value))); + + const std::pair<const_pointer, const_pointer> + r_range = assert_node_consistent_(p_nd->m_p_right); + + if (r_range.first != NULL) + _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), + PB_DS_V2F(*r_range.first))); + + return (std::make_pair((l_range.first != NULL)? l_range.first :& p_nd->m_value,(r_range.second != NULL)? r_range.second :& p_nd->m_value)); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_node_consistent_with_left(const node_pointer p_nd) const +{ + if (p_nd->m_p_left == NULL) + return; + _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left->m_p_parent == p_nd); + _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), + PB_DS_V2F(p_nd->m_p_left->m_value))); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_node_consistent_with_right(const node_pointer p_nd) const +{ + if (p_nd->m_p_right == NULL) + return; + _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_right->m_p_parent == p_nd); + _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_p_right->m_value), + PB_DS_V2F(p_nd->m_value))); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_min() const +{ + assert_min_imp(m_p_head->m_p_parent); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_min_imp(const node_pointer p_nd) const +{ + if (p_nd == NULL) + { + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_left == m_p_head); + return; + } + + if (p_nd->m_p_left == NULL) + { + _GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_left); + return; + } + assert_min_imp(p_nd->m_p_left); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_max() const +{ + assert_max_imp(m_p_head->m_p_parent); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_max_imp(const node_pointer p_nd) const +{ + if (p_nd == NULL) + { + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_right == m_p_head); + return; + } + + if (p_nd->m_p_right == NULL) + { + _GLIBCXX_DEBUG_ASSERT(p_nd == m_p_head->m_p_right); + return; + } + + assert_max_imp(p_nd->m_p_right); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_iterators() const +{ + size_type iterated_num = 0; + const_iterator prev_it = end(); + for (const_iterator it = begin(); it != end(); ++it) + { + ++iterated_num; + _GLIBCXX_DEBUG_ASSERT(lower_bound(PB_DS_V2F(*it)).m_p_nd == it.m_p_nd); + const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*it)); + --upper_bound_it; + _GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == it.m_p_nd); + + 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); + size_type reverse_iterated_num = 0; + const_reverse_iterator reverse_prev_it = rend(); + for (const_reverse_iterator reverse_it = rbegin(); reverse_it != rend(); + ++reverse_it) + { + ++reverse_iterated_num; + _GLIBCXX_DEBUG_ASSERT(lower_bound( + PB_DS_V2F(*reverse_it)).m_p_nd == reverse_it.m_p_nd); + + const_iterator upper_bound_it = upper_bound(PB_DS_V2F(*reverse_it)); + --upper_bound_it; + _GLIBCXX_DEBUG_ASSERT(upper_bound_it.m_p_nd == reverse_it.m_p_nd); + if (reverse_prev_it != rend()) + _GLIBCXX_DEBUG_ASSERT(!Cmp_Fn::operator()(PB_DS_V2F(*reverse_prev_it), + PB_DS_V2F(*reverse_it))); + reverse_prev_it = reverse_it; + } + _GLIBCXX_DEBUG_ASSERT(reverse_iterated_num == m_size); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_consistent_with_debug_base() const +{ + debug_base::check_size(m_size); + assert_consistent_with_debug_base(m_p_head->m_p_parent); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_consistent_with_debug_base(const node_pointer p_nd) const +{ + if (p_nd == NULL) + return; + debug_base::check_key_exists(PB_DS_V2F(p_nd->m_value)); + assert_consistent_with_debug_base(p_nd->m_p_left); + assert_consistent_with_debug_base(p_nd->m_p_right); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_size() const +{ + _GLIBCXX_DEBUG_ASSERT(recursive_count(m_p_head->m_p_parent) == m_size); +} + +#endif diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp new file mode 100644 index 000000000..a000c744c --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/erase_fn_imps.hpp @@ -0,0 +1,120 @@ +// -*- 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 bin_search_tree_. + */ + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +actual_erase_node(node_pointer p_z) +{ + _GLIBCXX_DEBUG_ASSERT(m_size > 0); + --m_size; + + _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_z->m_value))); + + p_z->~node(); + + s_node_allocator.deallocate(p_z, 1); +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +update_min_max_for_erased_node(node_pointer p_z) +{ + if (m_size == 1) + { + m_p_head->m_p_left = m_p_head->m_p_right = m_p_head; + + return; + } + + if (m_p_head->m_p_left == p_z) + { + iterator it(p_z); + + ++it; + + m_p_head->m_p_left = it.m_p_nd; + } + else if (m_p_head->m_p_right == p_z) + { + iterator it(p_z); + + --it; + + m_p_head->m_p_right = it.m_p_nd; + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +clear() +{ + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) + + clear_imp(m_p_head->m_p_parent); + + m_size = 0; + + initialize(); + + _GLIBCXX_DEBUG_ONLY(debug_base::clear();) + + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) + } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +clear_imp(node_pointer p_nd) +{ + if (p_nd == NULL) + return; + + clear_imp(p_nd->m_p_left); + + clear_imp(p_nd->m_p_right); + + p_nd->~node(); + + s_node_allocator.deallocate(p_nd, 1); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp new file mode 100644 index 000000000..413304b80 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/find_fn_imps.hpp @@ -0,0 +1,182 @@ +// -*- 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 class for bin_search_tree_. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_point_iterator +PB_DS_CLASS_C_DEC:: +lower_bound(const_key_reference r_key) const +{ + node_pointer p_pot = m_p_head; + node_pointer p_nd = m_p_head->m_p_parent; + + while (p_nd != NULL) + if (Cmp_Fn::operator()( + PB_DS_V2F(p_nd->m_value), + r_key)) + p_nd = p_nd->m_p_right; + else + { + p_pot = p_nd; + + p_nd = p_nd->m_p_left; + } + + return (iterator(p_pot)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_iterator +PB_DS_CLASS_C_DEC:: +lower_bound(const_key_reference r_key) +{ + node_pointer p_pot = m_p_head; + node_pointer p_nd = m_p_head->m_p_parent; + + while (p_nd != NULL) + if (Cmp_Fn::operator()( + PB_DS_V2F(p_nd->m_value), + r_key)) + p_nd = p_nd->m_p_right; + else + { + p_pot = p_nd; + + p_nd = p_nd->m_p_left; + } + + return (iterator(p_pot)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_point_iterator +PB_DS_CLASS_C_DEC:: +upper_bound(const_key_reference r_key) const +{ + node_pointer p_pot = m_p_head; + node_pointer p_nd = m_p_head->m_p_parent; + + while (p_nd != NULL) + if (Cmp_Fn::operator()(r_key, + PB_DS_V2F(p_nd->m_value))) + { + p_pot = p_nd, + + p_nd = p_nd->m_p_left; + } + else + p_nd = p_nd->m_p_right; + + return (const_iterator(p_pot)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_iterator +PB_DS_CLASS_C_DEC:: +upper_bound(const_key_reference r_key) +{ + node_pointer p_pot = m_p_head; + node_pointer p_nd = m_p_head->m_p_parent; + + while (p_nd != NULL) + if (Cmp_Fn::operator()(r_key, + PB_DS_V2F(p_nd->m_value))) + { + p_pot = p_nd, + + p_nd = p_nd->m_p_left; + } + else + p_nd = p_nd->m_p_right; + + return (point_iterator(p_pot)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_iterator +PB_DS_CLASS_C_DEC:: +find(const_key_reference r_key) +{ + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) + + node_pointer p_pot = m_p_head; + node_pointer p_nd = m_p_head->m_p_parent; + + while (p_nd != NULL) + if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) + { + p_pot = p_nd; + + p_nd = p_nd->m_p_left; + } + else + p_nd = p_nd->m_p_right; + + return point_iterator((p_pot != m_p_head&& Cmp_Fn::operator()( + r_key, + PB_DS_V2F(p_pot->m_value)))? + m_p_head : p_pot); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_point_iterator +PB_DS_CLASS_C_DEC:: +find(const_key_reference r_key) const +{ + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) + + node_pointer p_pot = m_p_head; + node_pointer p_nd = m_p_head->m_p_parent; + + while (p_nd != NULL) + if (!Cmp_Fn::operator()(PB_DS_V2F(p_nd->m_value), r_key)) + { + p_pot = p_nd; + + p_nd = p_nd->m_p_left; + } + else + p_nd = p_nd->m_p_right; + + return const_point_iterator((p_pot != m_p_head&& Cmp_Fn::operator()( + r_key, + PB_DS_V2F(p_pot->m_value)))? + m_p_head : p_pot); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp new file mode 100644 index 000000000..b3e46112f --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/info_fn_imps.hpp @@ -0,0 +1,64 @@ +// -*- 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 bin_search_tree_. + */ + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +empty() const +{ + return (m_size == 0); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +size() const +{ + return (m_size); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +max_size() const +{ + return (s_node_allocator.max_size()); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp new file mode 100644 index 000000000..3abf0a08d --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/insert_fn_imps.hpp @@ -0,0 +1,211 @@ +// -*- 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 bin_search_tree_. + */ + +PB_DS_CLASS_T_DEC +inline std::pair<typename PB_DS_CLASS_C_DEC::point_iterator, bool> +PB_DS_CLASS_C_DEC:: +insert_leaf(const_reference r_value) +{ + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) + + if (m_size == 0) + return (std::make_pair( + insert_imp_empty(r_value), + true)); + + node_pointer p_nd = m_p_head->m_p_parent; + node_pointer p_pot = m_p_head; + + while (p_nd != NULL) + if (!Cmp_Fn::operator()( + PB_DS_V2F(p_nd->m_value), + PB_DS_V2F(r_value))) + { + p_pot = p_nd; + + p_nd = p_nd->m_p_left; + } + else + p_nd = p_nd->m_p_right; + + if (p_pot == m_p_head) + return (std::make_pair( + insert_leaf_new(r_value, m_p_head->m_p_right, false), + true)); + + if (!Cmp_Fn::operator()( + PB_DS_V2F(r_value), + PB_DS_V2F(p_pot->m_value))) + { + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists( + PB_DS_V2F(r_value))); + + return (std::make_pair(p_pot, false)); + } + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist( + PB_DS_V2F(r_value))); + + p_nd = p_pot->m_p_left; + if (p_nd == NULL) + return (std::make_pair( + insert_leaf_new(r_value, p_pot, true), + true)); + + while (p_nd->m_p_right != NULL) + p_nd = p_nd->m_p_right; + + return (std::make_pair( + insert_leaf_new(r_value, p_nd, false), + true)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC:: +insert_leaf_new(const_reference r_value, node_pointer p_nd, bool left_nd) +{ + node_pointer p_new_nd = + get_new_node_for_leaf_insert( r_value, traits_base::m_no_throw_copies_indicator); + + if (left_nd) + { + _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left == NULL); + _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()( + PB_DS_V2F(r_value), + PB_DS_V2F(p_nd->m_value))); + + p_nd->m_p_left = p_new_nd; + + if (m_p_head->m_p_left == p_nd) + m_p_head->m_p_left = p_new_nd; + } + else + { + _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_right == NULL); + _GLIBCXX_DEBUG_ASSERT(Cmp_Fn::operator()( + PB_DS_V2F(p_nd->m_value), + PB_DS_V2F(r_value))); + + p_nd->m_p_right = p_new_nd; + + if (m_p_head->m_p_right == p_nd) + m_p_head->m_p_right = p_new_nd; + } + + p_new_nd->m_p_parent = p_nd; + + p_new_nd->m_p_left = p_new_nd->m_p_right = NULL; + + _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_nd)); + + update_to_top(p_new_nd, (node_update* )this); + + _GLIBCXX_DEBUG_ONLY(debug_base::insert_new( + PB_DS_V2F(r_value))); + + return (iterator(p_new_nd)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC:: +insert_imp_empty(const_reference r_value) +{ + node_pointer p_new_node = + get_new_node_for_leaf_insert( r_value, traits_base::m_no_throw_copies_indicator); + + m_p_head->m_p_left = m_p_head->m_p_right = + m_p_head->m_p_parent = p_new_node; + + p_new_node->m_p_parent = m_p_head; + + p_new_node->m_p_left = p_new_node->m_p_right = NULL; + + _GLIBCXX_DEBUG_ONLY(debug_base::insert_new( + PB_DS_V2F(r_value))); + + update_to_top(m_p_head->m_p_parent, (node_update* )this); + + return (iterator(p_new_node)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::node_pointer +PB_DS_CLASS_C_DEC:: +get_new_node_for_leaf_insert(const_reference r_val, false_type) +{ + node_pointer p_new_nd = s_node_allocator.allocate(1); + + cond_dealtor_t cond(p_new_nd); + + new (const_cast<void* >( + static_cast<const void* >(&p_new_nd->m_value))) + typename node::value_type(r_val); + + cond.set_no_action(); + + p_new_nd->m_p_left = p_new_nd->m_p_right = NULL; + + ++m_size; + + return (p_new_nd); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::node_pointer +PB_DS_CLASS_C_DEC:: +get_new_node_for_leaf_insert(const_reference r_val, true_type) +{ + node_pointer p_new_nd = s_node_allocator.allocate(1); + + new (const_cast<void* >( + static_cast<const void* >(&p_new_nd->m_value))) + typename node::value_type(r_val); + + p_new_nd->m_p_left = p_new_nd->m_p_right = NULL; + + ++m_size; + + return (p_new_nd); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp new file mode 100644 index 000000000..ed7f1b172 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/iterators_fn_imps.hpp @@ -0,0 +1,136 @@ +// -*- 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 bin_search_tree_. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC:: +begin() +{ + return (iterator(m_p_head->m_p_left)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_iterator +PB_DS_CLASS_C_DEC:: +begin() const +{ + return (const_iterator(m_p_head->m_p_left)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC:: +end() +{ + return (iterator(m_p_head)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_iterator +PB_DS_CLASS_C_DEC:: +end() const +{ + return (const_iterator(m_p_head)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator +PB_DS_CLASS_C_DEC:: +rbegin() const +{ + return (const_reverse_iterator(m_p_head->m_p_right)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::reverse_iterator +PB_DS_CLASS_C_DEC:: +rbegin() +{ + return (reverse_iterator(m_p_head->m_p_right)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::reverse_iterator +PB_DS_CLASS_C_DEC:: +rend() +{ + return (reverse_iterator(m_p_head)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator +PB_DS_CLASS_C_DEC:: +rend() const +{ + return (const_reverse_iterator(m_p_head)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_node_iterator +PB_DS_CLASS_C_DEC:: +node_begin() const +{ + return (const_node_iterator(m_p_head->m_p_parent)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::node_iterator +PB_DS_CLASS_C_DEC:: +node_begin() +{ + return (node_iterator(m_p_head->m_p_parent)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_node_iterator +PB_DS_CLASS_C_DEC:: +node_end() const +{ + return (const_node_iterator(NULL)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::node_iterator +PB_DS_CLASS_C_DEC:: +node_end() +{ + return (node_iterator(NULL)); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp new file mode 100644 index 000000000..365f02b6e --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp @@ -0,0 +1,237 @@ +// -*- 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_iterators.hpp + * Contains an implementation class for bin_search_tree_. + */ + +#ifndef PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP +#define PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP + +#include <ext/pb_ds/tag_and_trait.hpp> + +namespace __gnu_pbds +{ + namespace detail + { + +#define PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC \ + bin_search_tree_const_node_it_< \ + Node, \ + Const_Iterator, \ + Iterator, \ + Allocator> + + // Const node iterator. + template<typename Node, + class Const_Iterator, + class Iterator, + class Allocator> + class bin_search_tree_const_node_it_ + { + private: + + private: + typedef + typename Allocator::template rebind< + Node>::other::pointer + node_pointer; + + public: + + // Category. + typedef trivial_iterator_tag iterator_category; + + // Difference type. + typedef trivial_iterator_difference_type difference_type; + + // __Iterator's value type. + typedef Const_Iterator value_type; + + // __Iterator's reference type. + typedef Const_Iterator reference; + + // __Iterator's __const reference type. + typedef Const_Iterator const_reference; + + // Metadata type. + typedef typename Node::metadata_type metadata_type; + + // Const metadata reference type. + typedef + typename Allocator::template rebind< + metadata_type>::other::const_reference + const_metadata_reference; + + public: + + // Default constructor. + /* + inline + bin_search_tree_const_node_it_() + */ + + inline + bin_search_tree_const_node_it_(const node_pointer p_nd = NULL) : m_p_nd(const_cast<node_pointer>(p_nd)) + { } + + // Access. + inline const_reference + operator*() const + { + return (Const_Iterator(m_p_nd)); + } + + // Metadata access. + inline const_metadata_reference + get_metadata() const + { + return (m_p_nd->get_metadata()); + } + + // Returns the __const node iterator associated with the left node. + inline PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC + get_l_child() const + { + return (PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_left)); + } + + // Returns the __const node iterator associated with the right node. + inline PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC + get_r_child() const + { + return (PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_right)); + } + + // Compares to a different iterator object. + inline bool + operator==(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC& other) const + { + return (m_p_nd == other.m_p_nd); + } + + // Compares (negatively) to a different iterator object. + inline bool + operator!=(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC& other) const + { + return (m_p_nd != other.m_p_nd); + } + + public: + node_pointer m_p_nd; + }; + +#define PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC \ + bin_search_tree_node_it_< \ + Node, \ + Const_Iterator, \ + Iterator, \ + Allocator> + + // Node iterator. + template<typename Node, + class Const_Iterator, + class Iterator, + class Allocator> + class bin_search_tree_node_it_ : + public PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC + + { + + private: + typedef + typename Allocator::template rebind< + Node>::other::pointer + node_pointer; + + public: + + // __Iterator's value type. + typedef Iterator value_type; + + // __Iterator's reference type. + typedef Iterator reference; + + // __Iterator's __const reference type. + typedef Iterator const_reference; + + public: + + // Default constructor. + /* + inline + bin_search_tree_node_it_(); + */ + + inline + bin_search_tree_node_it_(const node_pointer p_nd = NULL) : PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC( + const_cast<node_pointer>(p_nd)) + { } + + // Access. + inline Iterator + operator*() const + { + return (Iterator(PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd)); + } + + // Returns the node iterator associated with the left node. + inline PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC + get_l_child() const + { + return (PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC( + PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_left)); + } + + // Returns the node iterator associated with the right node. + inline PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC + get_r_child() const + { + return (PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC( + PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_right)); + } + + }; + +#undef PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC + +#undef PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC + + } // namespace detail +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp new file mode 100644 index 000000000..bb249e070 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp @@ -0,0 +1,381 @@ +// -*- 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 point_iterators.hpp + * Contains an implementation class for bin_search_tree_. + */ + +#ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP +#define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP + +#include <ext/pb_ds/tag_and_trait.hpp> +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { + +#define PB_DS_TREE_CONST_IT_C_DEC \ + bin_search_tree_const_it_< \ + Node_Pointer, \ + Value_Type, \ + Pointer, \ + Const_Pointer, \ + Reference, \ + Const_Reference, \ + Is_Forward_Iterator, \ + Allocator> + +#define PB_DS_TREE_CONST_ODIR_IT_C_DEC \ + bin_search_tree_const_it_< \ + Node_Pointer, \ + Value_Type, \ + Pointer, \ + Const_Pointer, \ + Reference, \ + Const_Reference, \ + !Is_Forward_Iterator, \ + Allocator> + +#define PB_DS_TREE_IT_C_DEC \ + bin_search_tree_it_< \ + Node_Pointer, \ + Value_Type, \ + Pointer, \ + Const_Pointer, \ + Reference, \ + Const_Reference, \ + Is_Forward_Iterator, \ + Allocator> + +#define PB_DS_TREE_ODIR_IT_C_DEC \ + bin_search_tree_it_< \ + Node_Pointer, \ + Value_Type, \ + Pointer, \ + Const_Pointer, \ + Reference, \ + Const_Reference, \ + !Is_Forward_Iterator, \ + Allocator> + + // Const iterator. + template<typename Node_Pointer, + typename Value_Type, + typename Pointer, + typename Const_Pointer, + typename Reference, + typename Const_Reference, + bool Is_Forward_Iterator, + class Allocator> + class bin_search_tree_const_it_ + { + + public: + + typedef std::bidirectional_iterator_tag iterator_category; + + typedef typename Allocator::difference_type difference_type; + + typedef Value_Type value_type; + + typedef Pointer pointer; + + typedef Const_Pointer const_pointer; + + typedef Reference reference; + + typedef Const_Reference const_reference; + + public: + + inline + bin_search_tree_const_it_(const Node_Pointer p_nd = NULL) + : m_p_nd(const_cast<Node_Pointer>(p_nd)) + { } + + inline + bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) + : m_p_nd(other.m_p_nd) + { } + + inline + PB_DS_TREE_CONST_IT_C_DEC& + operator=(const PB_DS_TREE_CONST_IT_C_DEC& other) + { + m_p_nd = other.m_p_nd; + return *this; + } + + inline + PB_DS_TREE_CONST_IT_C_DEC& + operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) + { + m_p_nd = other.m_p_nd; + return *this; + } + + inline const_pointer + operator->() const + { + _GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL); + return &m_p_nd->m_value; + } + + inline const_reference + operator*() const + { + _GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL); + return m_p_nd->m_value; + } + + inline bool + operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const + { return m_p_nd == other.m_p_nd; } + + inline bool + operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const + { return m_p_nd == other.m_p_nd; } + + inline bool + operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const + { return m_p_nd != other.m_p_nd; } + + inline bool + operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const + { return m_p_nd != other.m_p_nd; } + + inline PB_DS_TREE_CONST_IT_C_DEC& + operator++() + { + _GLIBCXX_DEBUG_ASSERT(m_p_nd != NULL); + inc(integral_constant<int,Is_Forward_Iterator>()); + return *this; + } + + inline PB_DS_TREE_CONST_IT_C_DEC + operator++(int) + { + PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); + operator++(); + return ret_it; + } + + inline PB_DS_TREE_CONST_IT_C_DEC& + operator--() + { + dec(integral_constant<int,Is_Forward_Iterator>()); + return *this; + } + + inline PB_DS_TREE_CONST_IT_C_DEC + operator--(int) + { + PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd); + operator--(); + return ret_it; + } + + protected: + inline void + inc(false_type) + { dec(true_type()); } + + void + inc(true_type) + { + if (m_p_nd->special()&& + m_p_nd->m_p_parent->m_p_parent == m_p_nd) + { + m_p_nd = m_p_nd->m_p_left; + return; + } + + if (m_p_nd->m_p_right != NULL) + { + m_p_nd = m_p_nd->m_p_right; + while (m_p_nd->m_p_left != NULL) + m_p_nd = m_p_nd->m_p_left; + return; + } + + Node_Pointer p_y = m_p_nd->m_p_parent; + while (m_p_nd == p_y->m_p_right) + { + m_p_nd = p_y; + p_y = p_y->m_p_parent; + } + + if (m_p_nd->m_p_right != p_y) + m_p_nd = p_y; + } + + inline void + dec(false_type) + { inc(true_type()); } + + void + dec(true_type) + { + if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd) + { + m_p_nd = m_p_nd->m_p_right; + return; + } + + if (m_p_nd->m_p_left != NULL) + { + Node_Pointer p_y = m_p_nd->m_p_left; + while (p_y->m_p_right != NULL) + p_y = p_y->m_p_right; + m_p_nd = p_y; + return; + } + + Node_Pointer p_y = m_p_nd->m_p_parent; + while (m_p_nd == p_y->m_p_left) + { + m_p_nd = p_y; + p_y = p_y->m_p_parent; + } + if (m_p_nd->m_p_left != p_y) + m_p_nd = p_y; + } + + public: + Node_Pointer m_p_nd; + }; + + // Iterator. + template<typename Node_Pointer, + typename Value_Type, + typename Pointer, + typename Const_Pointer, + typename Reference, + typename Const_Reference, + bool Is_Forward_Iterator, + class Allocator> + class bin_search_tree_it_ : + public PB_DS_TREE_CONST_IT_C_DEC + + { + + public: + + inline + bin_search_tree_it_(const Node_Pointer p_nd = NULL) + : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd) + { } + + inline + bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other) + : PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd) + { } + + inline + PB_DS_TREE_IT_C_DEC& + operator=(const PB_DS_TREE_IT_C_DEC& other) + { + base_it_type::m_p_nd = other.m_p_nd; + return *this; + } + + inline + PB_DS_TREE_IT_C_DEC& + operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other) + { + base_it_type::m_p_nd = other.m_p_nd; + return *this; + } + + inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer + operator->() const + { + _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != NULL); + return &base_it_type::m_p_nd->m_value; + } + + inline typename PB_DS_TREE_CONST_IT_C_DEC::reference + operator*() const + { + _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != NULL); + return base_it_type::m_p_nd->m_value; + } + + inline PB_DS_TREE_IT_C_DEC& + operator++() + { + PB_DS_TREE_CONST_IT_C_DEC:: operator++(); + return *this; + } + + inline PB_DS_TREE_IT_C_DEC + operator++(int) + { + PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); + operator++(); + return ret_it; + } + + inline PB_DS_TREE_IT_C_DEC& + operator--() + { + PB_DS_TREE_CONST_IT_C_DEC:: operator--(); + return *this; + } + + inline PB_DS_TREE_IT_C_DEC + operator--(int) + { + PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd); + operator--(); + return ret_it; + } + + protected: + typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type; + }; + +#undef PB_DS_TREE_CONST_IT_C_DEC +#undef PB_DS_TREE_CONST_ODIR_IT_C_DEC +#undef PB_DS_TREE_IT_C_DEC +#undef PB_DS_TREE_ODIR_IT_C_DEC + + } // namespace detail +} // namespace __gnu_pbds + +#endif diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp new file mode 100644 index 000000000..63f307d39 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/policy_access_fn_imps.hpp @@ -0,0 +1,56 @@ +// -*- 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); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/r_erase_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/r_erase_fn_imps.hpp new file mode 100644 index 000000000..667ef8470 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/r_erase_fn_imps.hpp @@ -0,0 +1,120 @@ +// -*- 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 r_erase_fn_imps.hpp + * Contains an implementation class for bin_search_tree_. + */ + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +actual_erase_node(node_pointer p_z) +{ + _GLIBCXX_DEBUG_ASSERT(m_size > 0); + --m_size; + + _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_z->m_value))); + + p_z->~node(); + + s_node_allocator.deallocate(p_z, 1); +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +update_min_max_for_erased_node(node_pointer p_z) +{ + if (m_size == 1) + { + m_p_head->m_p_left = m_p_head->m_p_right = m_p_head; + + return; + } + + if (m_p_head->m_p_left == p_z) + { + iterator it(p_z); + + ++it; + + m_p_head->m_p_left = it.m_p_nd; + } + else if (m_p_head->m_p_right == p_z) + { + iterator it(p_z); + + --it; + + m_p_head->m_p_right = it.m_p_nd; + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +clear() +{ + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) + + clear_imp(m_p_head->m_p_parent); + + m_size = 0; + + initialize(); + + _GLIBCXX_DEBUG_ONLY(debug_base::clear();) + + _GLIBCXX_DEBUG_ONLY(structure_only_assert_valid();) + } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +clear_imp(node_pointer p_nd) +{ + if (p_nd == NULL) + return; + + clear_imp(p_nd->m_p_left); + + clear_imp(p_nd->m_p_right); + + p_nd->~Node(); + + s_node_allocator.deallocate(p_nd, 1); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp new file mode 100644 index 000000000..0598657fe --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/rotate_fn_imps.hpp @@ -0,0 +1,156 @@ +// -*- 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 rotate_fn_imps.hpp + * Contains imps for rotating nodes. + */ + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +rotate_left(node_pointer p_x) +{ + node_pointer p_y = p_x->m_p_right; + + p_x->m_p_right = p_y->m_p_left; + + if (p_y->m_p_left != NULL) + p_y->m_p_left->m_p_parent = p_x; + + p_y->m_p_parent = p_x->m_p_parent; + + if (p_x == m_p_head->m_p_parent) + m_p_head->m_p_parent = p_y; + else if (p_x == p_x->m_p_parent->m_p_left) + p_x->m_p_parent->m_p_left = p_y; + else + p_x->m_p_parent->m_p_right = p_y; + + p_y->m_p_left = p_x; + p_x->m_p_parent = p_y; + + _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);) + _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);) + + apply_update(p_x, (node_update* )this); + apply_update(p_x->m_p_parent, (node_update* )this); +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +rotate_right(node_pointer p_x) +{ + node_pointer p_y = p_x->m_p_left; + + p_x->m_p_left = p_y->m_p_right; + + if (p_y->m_p_right != NULL) + p_y->m_p_right->m_p_parent = p_x; + + p_y->m_p_parent = p_x->m_p_parent; + + if (p_x == m_p_head->m_p_parent) + m_p_head->m_p_parent = p_y; + else if (p_x == p_x->m_p_parent->m_p_right) + p_x->m_p_parent->m_p_right = p_y; + else + p_x->m_p_parent->m_p_left = p_y; + + p_y->m_p_right = p_x; + p_x->m_p_parent = p_y; + + _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_x);) + _GLIBCXX_DEBUG_ONLY(assert_node_consistent(p_y);) + + apply_update(p_x, (node_update* )this); + apply_update(p_x->m_p_parent, (node_update* )this); +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +rotate_parent(node_pointer p_nd) +{ + node_pointer p_parent = p_nd->m_p_parent; + + if (p_nd == p_parent->m_p_left) + rotate_right(p_parent); + else + rotate_left(p_parent); + + _GLIBCXX_DEBUG_ASSERT(p_parent->m_p_parent = p_nd); + _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_left == p_parent || + p_nd->m_p_right == p_parent); +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +apply_update(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/) +{ } + +PB_DS_CLASS_T_DEC +template<typename Node_Update_> +inline void +PB_DS_CLASS_C_DEC:: +apply_update(node_pointer p_nd, Node_Update_* /*p_update*/) +{ + node_update::operator()( + node_iterator(p_nd), + const_node_iterator(static_cast<node_pointer>(NULL))); +} + +PB_DS_CLASS_T_DEC +template<typename Node_Update_> +inline void +PB_DS_CLASS_C_DEC:: +update_to_top(node_pointer p_nd, Node_Update_* p_update) +{ + while (p_nd != m_p_head) + { + apply_update(p_nd, p_update); + + p_nd = p_nd->m_p_parent; + } +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +update_to_top(node_pointer /*p_nd*/, null_node_update_pointer /*p_update*/) +{ } + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp new file mode 100644 index 000000000..9d2bd6d74 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/split_join_fn_imps.hpp @@ -0,0 +1,146 @@ +// -*- 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 bin_search_tree_. + */ + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +join_prep(PB_DS_CLASS_C_DEC& other) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + if (other.m_size == 0) + return false; + + if (m_size == 0) + { + value_swap(other); + return false; + } + + const bool greater = Cmp_Fn::operator()(PB_DS_V2F(m_p_head->m_p_right->m_value), PB_DS_V2F(other.m_p_head->m_p_left->m_value)); + + const bool lesser = Cmp_Fn::operator()(PB_DS_V2F(other.m_p_head->m_p_right->m_value), PB_DS_V2F(m_p_head->m_p_left->m_value)); + + if (!greater && !lesser) + __throw_join_error(); + + if (lesser) + value_swap(other); + + m_size += other.m_size; + _GLIBCXX_DEBUG_ONLY(debug_base::join(other);) + return true; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +join_finish(PB_DS_CLASS_C_DEC& other) +{ + initialize_min_max(); + other.initialize(); +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + other.clear(); + + if (m_size == 0) + { + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + return false; + } + + if (Cmp_Fn::operator()(r_key, PB_DS_V2F(m_p_head->m_p_left->m_value))) + { + value_swap(other); + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + return false; + } + + if (!Cmp_Fn::operator()(r_key, PB_DS_V2F(m_p_head->m_p_right->m_value))) + { + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + return false; + } + + if (m_size == 1) + { + value_swap(other); + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + return false; + } + + _GLIBCXX_DEBUG_ONLY(debug_base::split(r_key,(Cmp_Fn& )(*this), other);) + return true; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +split_finish(PB_DS_CLASS_C_DEC& other) +{ + other.initialize_min_max(); + other.m_size = std::distance(other.begin(), other.end()); + m_size -= other.m_size; + initialize_min_max(); + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +recursive_count(node_pointer p) const +{ + if (p == NULL) + return 0; + return 1 + recursive_count(p->m_p_left) + recursive_count(p->m_p_right); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp new file mode 100644 index 000000000..58c30c3fe --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp @@ -0,0 +1,250 @@ +// -*- 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 bin_search_tree_. + */ + +#ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP +#define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP + +#include <ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp> +#include <ext/pb_ds/detail/bin_search_tree_/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 Node, + class Allocator> + struct bin_search_tree_traits + { + private: + typedef + types_traits< + Key, + Mapped, + Allocator, + false> + type_traits; + + public: + typedef Node node; + + typedef + bin_search_tree_const_it_< + typename Allocator::template rebind< + node>::other::pointer, + typename type_traits::value_type, + typename type_traits::pointer, + typename type_traits::const_pointer, + typename type_traits::reference, + typename type_traits::const_reference, + true, + Allocator> + const_point_iterator; + + typedef + bin_search_tree_it_< + typename Allocator::template rebind< + node>::other::pointer, + typename type_traits::value_type, + typename type_traits::pointer, + typename type_traits::const_pointer, + typename type_traits::reference, + typename type_traits::const_reference, + true, + Allocator> + point_iterator; + + typedef + bin_search_tree_const_it_< + typename Allocator::template rebind< + node>::other::pointer, + typename type_traits::value_type, + typename type_traits::pointer, + typename type_traits::const_pointer, + typename type_traits::reference, + typename type_traits::const_reference, + false, + Allocator> + const_reverse_iterator; + + typedef + bin_search_tree_it_< + typename Allocator::template rebind< + node>::other::pointer, + typename type_traits::value_type, + typename type_traits::pointer, + typename type_traits::const_pointer, + typename type_traits::reference, + typename type_traits::const_reference, + false, + Allocator> + reverse_iterator; + + typedef + bin_search_tree_const_node_it_< + Node, + const_point_iterator, + point_iterator, + Allocator> + const_node_iterator; + + typedef + bin_search_tree_node_it_< + Node, + const_point_iterator, + point_iterator, + 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 Node, + class Allocator> + struct bin_search_tree_traits< + Key, + null_mapped_type, + Cmp_Fn, + Node_Update, + Node, + Allocator> + { + private: + typedef + types_traits< + Key, + null_mapped_type, + Allocator, + false> + type_traits; + + public: + typedef Node node; + + typedef + bin_search_tree_const_it_< + typename Allocator::template rebind< + node>::other::pointer, + typename type_traits::value_type, + typename type_traits::pointer, + typename type_traits::const_pointer, + typename type_traits::reference, + typename type_traits::const_reference, + true, + Allocator> + const_point_iterator; + + typedef const_point_iterator point_iterator; + + typedef + bin_search_tree_const_it_< + typename Allocator::template rebind< + node>::other::pointer, + typename type_traits::value_type, + typename type_traits::pointer, + typename type_traits::const_pointer, + typename type_traits::reference, + typename type_traits::const_reference, + false, + Allocator> + const_reverse_iterator; + + typedef const_reverse_iterator reverse_iterator; + + typedef + bin_search_tree_const_node_it_< + Node, + const_point_iterator, + point_iterator, + Allocator> + const_node_iterator; + + typedef const_node_iterator 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; + }; + + } // namespace detail +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP |