inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file erase_no_store_hash_fn_imps.hpp * Contains implementations of cc_ht_map_'s erase related functions, * when the hash value is not stored. */ PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: erase(const_key_reference r_key) { _GLIBCXX_DEBUG_ONLY(assert_valid();) return erase_in_pos_imp(r_key, ranged_hash_fn_base::operator()(r_key)); } PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: erase_in_pos_imp(const_key_reference r_key, size_type pos) { _GLIBCXX_DEBUG_ONLY(assert_valid();) entry_pointer p_e = m_entries[pos]; resize_base::notify_erase_search_start(); if (p_e == NULL) { resize_base::notify_erase_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) _GLIBCXX_DEBUG_ONLY(assert_valid();) return false; } if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), r_key)) { resize_base::notify_erase_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base:: check_key_exists(r_key);) erase_entry_pointer(m_entries[pos]); do_resize_if_needed_no_throw(); _GLIBCXX_DEBUG_ONLY(assert_valid();) return true; } while (true) { entry_pointer p_next_e = p_e->m_p_next; if (p_next_e == NULL) { resize_base::notify_erase_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) _GLIBCXX_DEBUG_ONLY(assert_valid();) return false; } if (hash_eq_fn_base::operator()(PB_DS_V2F(p_next_e->m_value), r_key)) { resize_base::notify_erase_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) erase_entry_pointer(p_e->m_p_next); do_resize_if_needed_no_throw(); _GLIBCXX_DEBUG_ONLY(assert_valid();) return true; } resize_base::notify_erase_search_collision(); p_e = p_next_e; } } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file erase_store_hash_fn_imps.hpp * Contains implementations of cc_ht_map_'s erase related functions, * when the hash value is stored. */ PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: erase_in_pos_imp(const_key_reference r_key, const comp_hash& r_pos_hash_pair) { _GLIBCXX_DEBUG_ONLY(assert_valid();) entry_pointer p_e = m_entries[r_pos_hash_pair.first]; resize_base::notify_erase_search_start(); if (p_e == NULL) { resize_base::notify_erase_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base:: check_key_does_not_exist(r_key);) _GLIBCXX_DEBUG_ONLY(assert_valid();) return false; } if (hash_eq_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash, r_key, r_pos_hash_pair.second)) { resize_base::notify_erase_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) erase_entry_pointer(m_entries[r_pos_hash_pair.first]); do_resize_if_needed_no_throw(); _GLIBCXX_DEBUG_ONLY(assert_valid();) return true; } while (true) { entry_pointer p_next_e = p_e->m_p_next; if (p_next_e == NULL) { resize_base::notify_erase_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) _GLIBCXX_DEBUG_ONLY(assert_valid();) return false; } if (hash_eq_fn_base::operator()(PB_DS_V2F(p_next_e->m_value), p_next_e->m_hash, r_key, r_pos_hash_pair.second)) { resize_base::notify_erase_search_end(); _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key);) erase_entry_pointer(p_e->m_p_next); do_resize_if_needed_no_throw(); _GLIBCXX_DEBUG_ONLY(assert_valid();) return true; } resize_base::notify_erase_search_collision(); p_e = p_next_e; } } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file resize_store_hash_fn_imps.hpp * Contains implementations of cc_ht_map_'s resize related functions, when the * hash value is stored. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::entry_pointer PB_DS_CLASS_C_DEC:: resize_imp_no_exceptions_reassign_pointer(entry_pointer p_e, entry_pointer_array a_p_entries_resized, true_type) { const comp_hash pos_hash_pair = ranged_hash_fn_base::operator()(PB_DS_V2F(p_e->m_value), p_e->m_hash); entry_pointer const p_next_e = p_e->m_p_next; p_e->m_p_next = a_p_entries_resized[pos_hash_pair.first]; a_p_entries_resized[pos_hash_pair.first] = p_e; return p_next_e; } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file constructor_destructor_fn_imps.hpp * Contains implementations of cc_ht_map_'s constructors, destructor, * and related functions. */ PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::entry_allocator PB_DS_CLASS_C_DEC::s_entry_allocator; PB_DS_CLASS_T_DEC typename PB_DS_CLASS_C_DEC::entry_pointer_allocator PB_DS_CLASS_C_DEC::s_entry_pointer_allocator; PB_DS_CLASS_T_DEC template void PB_DS_CLASS_C_DEC:: copy_from_range(It first_it, It last_it) { while (first_it != last_it) insert(*(first_it++)); } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME() : ranged_hash_fn_base(resize_base::get_nearest_larger_size(1)), m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), m_entries(s_entry_pointer_allocator.allocate(m_num_e)) { initialize(); _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn) : ranged_hash_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn), m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), m_entries(s_entry_pointer_allocator.allocate(m_num_e)) { initialize(); _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn) : PB_DS_HASH_EQ_FN_C_DEC(r_eq_fn), ranged_hash_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn), m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), m_entries(s_entry_pointer_allocator.allocate(m_num_e)) { std::fill(m_entries, m_entries + m_num_e, (entry_pointer)NULL); Resize_Policy::notify_cleared(); ranged_hash_fn_base::notify_resized(m_num_e); _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn) : PB_DS_HASH_EQ_FN_C_DEC(r_eq_fn), ranged_hash_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn, r_comb_hash_fn), m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), m_entries(s_entry_pointer_allocator.allocate(m_num_e)) { initialize(); _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: PB_DS_CLASS_NAME(const Hash_Fn& r_hash_fn, const Eq_Fn& r_eq_fn, const Comb_Hash_Fn& r_comb_hash_fn, const Resize_Policy& r_resize_policy) : PB_DS_HASH_EQ_FN_C_DEC(r_eq_fn), Resize_Policy(r_resize_policy), ranged_hash_fn_base(resize_base::get_nearest_larger_size(1), r_hash_fn, r_comb_hash_fn), m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), m_entries(s_entry_pointer_allocator.allocate(m_num_e)) { initialize(); _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::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 PB_DS_HASH_EQ_FN_C_DEC(other), resize_base(other), ranged_hash_fn_base(other), m_num_e(resize_base::get_nearest_larger_size(1)), m_num_used_e(0), m_entries(m_entries = s_entry_pointer_allocator.allocate(m_num_e)) { initialize(); _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) try { copy_from_range(other.begin(), other.end()); } catch(...) { deallocate_all(); __throw_exception_again; } _GLIBCXX_DEBUG_ONLY(PB_DS_CLASS_C_DEC::assert_valid();) } PB_DS_CLASS_T_DEC PB_DS_CLASS_C_DEC:: ~PB_DS_CLASS_NAME() { deallocate_all(); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: swap(PB_DS_CLASS_C_DEC& other) { _GLIBCXX_DEBUG_ONLY(assert_valid()); _GLIBCXX_DEBUG_ONLY(other.assert_valid()); std::swap(m_entries, other.m_entries); std::swap(m_num_e, other.m_num_e); std::swap(m_num_used_e, other.m_num_used_e); ranged_hash_fn_base::swap(other); hash_eq_fn_base::swap(other); resize_base::swap(other); _GLIBCXX_DEBUG_ONLY(debug_base::swap(other)); _GLIBCXX_DEBUG_ONLY(assert_valid()); _GLIBCXX_DEBUG_ONLY(other.assert_valid()); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: deallocate_all() { clear(); s_entry_pointer_allocator.deallocate(m_entries, m_num_e); } PB_DS_CLASS_T_DEC void PB_DS_CLASS_C_DEC:: initialize() { std::fill(m_entries, m_entries + m_num_e, entry_pointer(NULL)); Resize_Policy::notify_resized(m_num_e); Resize_Policy::notify_cleared(); ranged_hash_fn_base::notify_resized(m_num_e); } H .X ..I split_join_fn_imps.hppJnode_iterators.hppKinsert_fn_imps.hppL$cond_dtor_entry_dealtor.hppMinfo_fn_imps.hppN$policy_access_fn_imps.hppOfind_fn_imps.hppP,#constructors_destructor_fn_imps.hppQpoint_iterators.hppRdebug_fn_imps.hppS(cond_key_dtor_entry_dealtor.hppTerase_fn_imps.hppU traits.hppV iterators_fn_imps.hppWrotate_fn_imps.hppXr_erase_fn_imps.hppYbin_search_tree_.hpp// -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file 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); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file node_iterators.hpp * Contains an implementation class for bin_search_tree_. */ #ifndef PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP #define PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP #include 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 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(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 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(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 // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file insert_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC inline std::pair 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( static_cast(&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( static_cast(&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); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file cond_dtor_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::other(). deallocate(m_p_nd, 1); } protected: node_pointer m_p_nd; bool m_no_action_dtor; }; // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file info_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC inline bool PB_DS_CLASS_C_DEC:: empty() const { return (m_size == 0); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: size() const { return (m_size); } PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::size_type PB_DS_CLASS_C_DEC:: max_size() const { return (s_node_allocator.max_size()); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file policy_access_fn_imps.hpp * Contains an implementation class for 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); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file find_fn_imps.hpp * Contains an implementation class for bin_search_tree_. */ PB_DS_CLASS_T_DEC inline typename PB_DS_CLASS_C_DEC::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); } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file constructors_destructor_fn_imps.hpp * Contains an implementation class for 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; } } // -*- C++ -*- // Copyright (C) 2005, 2006 Free Software Foundation, Inc. // // This file is part of the GNU ISO C++ Library. This library is free // software; you can redistribute it and/or modify it under the terms // of the GNU General Public License as published by the Free Software // Foundation; either version 2, or (at your option) any later // version. // This library is distributed in the hope that it will be useful, but // WITHOUT ANY WARRANTY; without even the implied warranty of // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU // General Public License for more details. // You should have received a copy of the GNU General Public License // along with this library; see the file COPYING. If not, write to // the Free Software Foundation, 59 Temple Place - Suite 330, Boston, // MA 02111-1307, USA. // As a special exception, you may use this file as part of a free // software library without restriction. Specifically, if other files // instantiate templates or use macros or inline functions from this // file, or you compile this file and link it with other files to // produce an executable, this file does not by itself cause the // resulting executable to be covered by the GNU General Public // License. This exception does not however invalidate any other // reasons why the executable file might be covered by the GNU General // Public License. // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. // Permission to use, copy, modify, sell, and distribute this software // is hereby granted without fee, provided that the above copyright // notice appears in all copies, and that both that copyright notice // and this permission notice appear in supporting documentation. None // of the above authors, nor IBM Haifa Research Laboratories, make any // representation about the suitability of this software for any // purpose. It is provided "as is" without express or implied // warranty. /** * @file 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 #include 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 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(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()); 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()); 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 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 oper