diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_')
27 files changed, 5700 insertions, 0 deletions
diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp new file mode 100644 index 000000000..15f349efb --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp @@ -0,0 +1,93 @@ +// -*- 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 child_iterator.hpp + * Contains a iterator for a patricia tree. + */ + +struct iterator : public const_iterator +{ +public: + typedef std::forward_iterator_tag iterator_category; + typedef typename Allocator::difference_type difference_type; + typedef node_pointer value_type; + typedef node_pointer_pointer pointer; + typedef node_pointer_reference reference; + + inline + iterator(node_pointer_pointer p_p_cur = NULL, + node_pointer_pointer p_p_end = NULL) + : const_iterator(p_p_cur, p_p_end) + { } + + inline bool + operator==(const iterator& other) const + { return const_iterator::m_p_p_cur == other.m_p_p_cur; } + + inline bool + operator!=(const iterator& other) const + { return const_iterator::m_p_p_cur != other.m_p_p_cur; } + + inline iterator& + operator++() + { + const_iterator::operator++(); + return *this; + } + + inline iterator + operator++(int) + { + iterator ret_it(*this); + operator++(); + return ret_it; + } + + node_pointer_pointer + operator->() + { + _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();) + return const_iterator::m_p_p_cur; + } + + node_pointer + operator*() + { + _GLIBCXX_DEBUG_ONLY(const_iterator::assert_referencible();) + return *const_iterator::m_p_p_cur; + } +}; + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp new file mode 100644 index 000000000..184b98652 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp @@ -0,0 +1,79 @@ +// -*- 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 cond_dealtor +{ +public: + inline + cond_dealtor(leaf_pointer p_nd) : m_p_nd(p_nd), + m_no_action_dtor(false), + m_call_destructor(false) + { } + + inline void + set_no_action_dtor() + { + m_no_action_dtor = true; + } + + inline void + set_call_destructor() + { + m_call_destructor = true; + } + + inline + ~cond_dealtor() + { + if (m_no_action_dtor) + return; + + if (m_call_destructor) + m_p_nd->~leaf(); + + s_leaf_allocator.deallocate(m_p_nd, 1); + } + +protected: + leaf_pointer m_p_nd; + bool m_no_action_dtor; + bool m_call_destructor; +}; + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp new file mode 100644 index 000000000..bc349cf2d --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp @@ -0,0 +1,111 @@ +// -*- 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 const_child_iterator.hpp + * Contains a const_iterator for a patricia tree. + */ + +struct const_iterator +{ +public: + typedef std::forward_iterator_tag iterator_category; + + typedef typename Allocator::difference_type difference_type; + + typedef node_pointer value_type; + + typedef node_pointer_pointer pointer; + + typedef node_pointer_reference reference; + +public: + inline + const_iterator(node_pointer_pointer p_p_cur = NULL, + node_pointer_pointer p_p_end = NULL) + : m_p_p_cur(p_p_cur), m_p_p_end(p_p_end) + { } + + inline bool + operator==(const const_iterator& other) const + { return m_p_p_cur == other.m_p_p_cur; } + + inline bool + operator!=(const const_iterator& other) const + { return m_p_p_cur != other.m_p_p_cur; } + + inline const_iterator& + operator++() + { + do + ++m_p_p_cur; + while (m_p_p_cur != m_p_p_end&& * m_p_p_cur == NULL); + return *this; + } + + inline const_iterator + operator++(int) + { + const_iterator ret_it(*this); + operator++(); + return ret_it; + } + + const node_pointer_pointer + operator->() const + { + _GLIBCXX_DEBUG_ONLY(assert_referencible();) + return (m_p_p_cur); + } + + const_node_pointer + operator*() const + { + _GLIBCXX_DEBUG_ONLY(assert_referencible();) + return (*m_p_p_cur); + } + +protected: +#ifdef _GLIBCXX_DEBUG + void + assert_referencible() const + { _GLIBCXX_DEBUG_ASSERT(m_p_p_cur != m_p_p_end&& * m_p_p_cur != NULL); } +#endif + +public: + node_pointer_pointer m_p_p_cur; + node_pointer_pointer m_p_p_end; +}; + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp new file mode 100644 index 000000000..ca38f932a --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp @@ -0,0 +1,214 @@ +// -*- 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::head_allocator +PB_DS_CLASS_C_DEC::s_head_allocator; + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::internal_node_allocator +PB_DS_CLASS_C_DEC::s_internal_node_allocator; + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::leaf_allocator +PB_DS_CLASS_C_DEC::s_leaf_allocator; + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME() : + m_p_head(s_head_allocator.allocate(1)), + m_size(0) +{ + initialize(); + _GLIBCXX_DEBUG_ONLY(assert_valid();) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME(const e_access_traits& r_e_access_traits) : + synth_e_access_traits(r_e_access_traits), + m_p_head(s_head_allocator.allocate(1)), + m_size(0) +{ + initialize(); + _GLIBCXX_DEBUG_ONLY(assert_valid();) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC& other) : +#ifdef _GLIBCXX_DEBUG + debug_base(other), +#endif + synth_e_access_traits(other), + node_update(other), + m_p_head(s_head_allocator.allocate(1)), + m_size(0) +{ + initialize(); + m_size = other.m_size; + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + if (other.m_p_head->m_p_parent == NULL) + { + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return; + } + __try + { + m_p_head->m_p_parent = recursive_copy_node(other.m_p_head->m_p_parent); + } + __catch(...) + { + s_head_allocator.deallocate(m_p_head, 1); + __throw_exception_again; + } + + m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent); + m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); + m_p_head->m_p_parent->m_p_parent = m_p_head; + _GLIBCXX_DEBUG_ONLY(assert_valid();) +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +swap(PB_DS_CLASS_C_DEC& other) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + value_swap(other); + std::swap((e_access_traits& )(*this), (e_access_traits& )other); + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.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_head_allocator.deallocate(m_p_head, 1); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +initialize() +{ + new (m_p_head) head(); + m_p_head->m_p_parent = NULL; + m_p_head->m_p_min = m_p_head; + m_p_head->m_p_max = m_p_head; + m_size = 0; +} + +PB_DS_CLASS_T_DEC +template<typename It> +void +PB_DS_CLASS_C_DEC:: +copy_from_range(It first_it, It last_it) +{ + while (first_it != last_it) + insert(*(first_it++)); +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::node_pointer +PB_DS_CLASS_C_DEC:: +recursive_copy_node(const_node_pointer p_other_nd) +{ + _GLIBCXX_DEBUG_ASSERT(p_other_nd != NULL); + if (p_other_nd->m_type == pat_trie_leaf_node_type) + { + const_leaf_pointer p_other_leaf = static_cast<const_leaf_pointer>(p_other_nd); + + leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); + cond_dealtor cond(p_new_lf); + new (p_new_lf) leaf(p_other_leaf->value()); + apply_update(p_new_lf, (node_update* )this); + cond.set_no_action_dtor(); + return (p_new_lf); + } + + _GLIBCXX_DEBUG_ASSERT(p_other_nd->m_type == pat_trie_internal_node_type); + node_pointer a_p_children[internal_node::arr_size]; + size_type child_i = 0; + const_internal_node_pointer p_other_internal_nd = + static_cast<const_internal_node_pointer>(p_other_nd); + + typename internal_node::const_iterator child_it = + p_other_internal_nd->begin(); + + internal_node_pointer p_ret; + __try + { + while (child_it != p_other_internal_nd->end()) + a_p_children[child_i++] = recursive_copy_node(*(child_it++)); + p_ret = s_internal_node_allocator.allocate(1); + } + __catch(...) + { + while (child_i-- > 0) + clear_imp(a_p_children[child_i]); + __throw_exception_again; + } + + new (p_ret) internal_node(p_other_internal_nd->get_e_ind(), + pref_begin(a_p_children[0])); + + --child_i; + _GLIBCXX_DEBUG_ASSERT(child_i > 1); + do + p_ret->add_child(a_p_children[child_i], pref_begin(a_p_children[child_i]), + pref_end(a_p_children[child_i]), this); + while (child_i-- > 0); + apply_update(p_ret, (node_update* )this); + return p_ret; +} diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp new file mode 100644 index 000000000..de7565788 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp @@ -0,0 +1,117 @@ +// -*- 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 pat_trie_. + */ + +#ifdef _GLIBCXX_DEBUG + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_valid() const +{ + if (m_p_head->m_p_parent != NULL) + m_p_head->m_p_parent->assert_valid(this); + assert_iterators(); + assert_reverse_iterators(); + if (m_p_head->m_p_parent == NULL) + { + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_min == m_p_head); + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_max == m_p_head); + _GLIBCXX_DEBUG_ASSERT(empty()); + return; + } + + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_min->m_type == pat_trie_leaf_node_type); + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_max->m_type == pat_trie_leaf_node_type); + _GLIBCXX_DEBUG_ASSERT(!empty()); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_iterators() const +{ + size_type calc_size = 0; + for (const_iterator it = begin(); it != end(); ++it) + { + ++calc_size; + debug_base::check_key_exists(PB_DS_V2F(*it)); + _GLIBCXX_DEBUG_ASSERT(lower_bound(PB_DS_V2F(*it)) == it); + _GLIBCXX_DEBUG_ASSERT(--upper_bound(PB_DS_V2F(*it)) == it); + } + _GLIBCXX_DEBUG_ASSERT(calc_size == m_size); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_reverse_iterators() const +{ + size_type calc_size = 0; + for (const_reverse_iterator it = rbegin(); it != rend(); ++it) + { + ++calc_size; + const_node_pointer p_nd = + const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(PB_DS_V2F(*it)); + _GLIBCXX_DEBUG_ASSERT(p_nd == it.m_p_nd); + } + _GLIBCXX_DEBUG_ASSERT(calc_size == m_size); +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +recursive_count_leafs(const_node_pointer p_nd) +{ + if (p_nd == NULL) + return (0); + if (p_nd->m_type == pat_trie_leaf_node_type) + return (1); + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); + size_type ret = 0; + for (typename internal_node::const_iterator it = + static_cast<const_internal_node_pointer>(p_nd)->begin(); + it != static_cast<const_internal_node_pointer>(p_nd)->end(); + ++it) + ret += recursive_count_leafs(*it); + return ret; +} + +#endif + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp new file mode 100644 index 000000000..90988184a --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp @@ -0,0 +1,319 @@ +// -*- 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 bool +PB_DS_CLASS_C_DEC:: +erase(const_key_reference r_key) +{ + node_pointer p_nd = find_imp(r_key); + if (p_nd == NULL || p_nd->m_type == pat_trie_internal_node_type) + { + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key)); + return false; + } + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); + if (!synth_e_access_traits::equal_keys(PB_DS_V2F(reinterpret_cast<leaf_pointer>(p_nd)->value()), r_key)) + { + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key)); + return false; + } + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); + erase_leaf(static_cast<leaf_pointer>(p_nd)); + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return true; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +erase_fixup(internal_node_pointer p_nd) +{ + _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) >= 1); + if (std::distance(p_nd->begin(), p_nd->end()) == 1) + { + node_pointer p_parent = p_nd->m_p_parent; + if (p_parent == m_p_head) + m_p_head->m_p_parent =* p_nd->begin(); + else + { + _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type); + node_pointer p_new_child =* p_nd->begin(); + static_cast<internal_node_pointer>(p_parent)->replace_child( + p_new_child, + pref_begin(p_new_child), + pref_end(p_new_child), + this); + } + (*p_nd->begin())->m_p_parent = p_nd->m_p_parent; + p_nd->~internal_node(); + s_internal_node_allocator.deallocate(p_nd, 1); + + if (p_parent == m_p_head) + return; + + _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == pat_trie_internal_node_type); + p_nd = static_cast<internal_node_pointer>(p_parent); + } + + while (true) + { + _GLIBCXX_DEBUG_ASSERT(std::distance(p_nd->begin(), p_nd->end()) > 1); + p_nd->update_prefixes(this); + apply_update(p_nd, (node_update* )this); + _GLIBCXX_DEBUG_ONLY(p_nd->assert_valid(this);) + if (p_nd->m_p_parent->m_type == pat_trie_head_node_type) + return; + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent->m_type == + pat_trie_internal_node_type); + + p_nd = static_cast<internal_node_pointer>(p_nd->m_p_parent); + } +} + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +actual_erase_leaf(leaf_pointer p_l) +{ + _GLIBCXX_DEBUG_ASSERT(m_size > 0); + --m_size; + _GLIBCXX_DEBUG_ONLY(erase_existing(PB_DS_V2F(p_l->value()))); + p_l->~leaf(); + s_leaf_allocator.deallocate(p_l, 1); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +clear() +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + if (empty()) + return; + + clear_imp(m_p_head->m_p_parent); + m_size = 0; + initialize(); + _GLIBCXX_DEBUG_ONLY(debug_base::clear();) + _GLIBCXX_DEBUG_ONLY(assert_valid();) +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +clear_imp(node_pointer p_nd) +{ + if (p_nd->m_type == pat_trie_internal_node_type) + { + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); + for (typename internal_node::iterator it = + static_cast<internal_node_pointer>(p_nd)->begin(); + it != static_cast<internal_node_pointer>(p_nd)->end(); + ++it) + { + node_pointer p_child =* it; + clear_imp(p_child); + } + s_internal_node_allocator.deallocate(static_cast<internal_node_pointer>(p_nd), 1); + return; + } + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); + static_cast<leaf_pointer>(p_nd)->~leaf(); + s_leaf_allocator.deallocate(static_cast<leaf_pointer>(p_nd), 1); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_iterator +PB_DS_CLASS_C_DEC:: +erase(const_iterator it) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid()); + + if (it == end()) + return it; + + const_iterator ret_it = it; + ++ret_it; + _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); + erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); + _GLIBCXX_DEBUG_ONLY(assert_valid()); + return ret_it; +} + +#ifdef PB_DS_DATA_TRUE_INDICATOR +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC:: +erase(iterator it) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid()); + + if (it == end()) + return it; + iterator ret_it = it; + ++ret_it; + _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); + erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); + _GLIBCXX_DEBUG_ONLY(assert_valid()); + return ret_it; +} +#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator +PB_DS_CLASS_C_DEC:: +erase(const_reverse_iterator it) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid()); + + if (it.m_p_nd == m_p_head) + return it; + const_reverse_iterator ret_it = it; + ++ret_it; + + _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); + erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); + _GLIBCXX_DEBUG_ONLY(assert_valid()); + return ret_it; +} + +#ifdef PB_DS_DATA_TRUE_INDICATOR +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::reverse_iterator +PB_DS_CLASS_C_DEC:: +erase(reverse_iterator it) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid()); + + if (it.m_p_nd == m_p_head) + return it; + reverse_iterator ret_it = it; + ++ret_it; + + _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == pat_trie_leaf_node_type); + erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); + _GLIBCXX_DEBUG_ONLY(assert_valid()); + return ret_it; +} +#endif // #ifdef PB_DS_DATA_TRUE_INDICATOR + +PB_DS_CLASS_T_DEC +template<typename Pred> +inline typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +erase_if(Pred pred) +{ + size_type num_ersd = 0; + _GLIBCXX_DEBUG_ONLY(assert_valid();) + + iterator it = begin(); + while (it != end()) + { + _GLIBCXX_DEBUG_ONLY(assert_valid();) + if (pred(*it)) + { + ++num_ersd; + it = erase(it); + } + else + ++it; + } + + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return num_ersd; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +erase_leaf(leaf_pointer p_l) +{ + update_min_max_for_erased_leaf(p_l); + if (p_l->m_p_parent->m_type == pat_trie_head_node_type) + { + _GLIBCXX_DEBUG_ASSERT(size() == 1); + clear(); + return; + } + + _GLIBCXX_DEBUG_ASSERT(size() > 1); + _GLIBCXX_DEBUG_ASSERT(p_l->m_p_parent->m_type == + pat_trie_internal_node_type); + + internal_node_pointer p_parent = + static_cast<internal_node_pointer>(p_l->m_p_parent); + + p_parent->remove_child(p_l); + erase_fixup(p_parent); + actual_erase_leaf(p_l); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +update_min_max_for_erased_leaf(leaf_pointer p_l) +{ + if (m_size == 1) + { + m_p_head->m_p_min = m_p_head; + m_p_head->m_p_max = m_p_head; + return; + } + + if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_min)) + { + iterator it(p_l); + ++it; + m_p_head->m_p_min = it.m_p_nd; + return; + } + + if (p_l == static_cast<const_leaf_pointer>(m_p_head->m_p_max)) + { + iterator it(p_l); + --it; + m_p_head->m_p_max = it.m_p_nd; + } +} diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp new file mode 100644 index 000000000..2552ead8b --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp @@ -0,0 +1,269 @@ +// -*- 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::point_iterator +PB_DS_CLASS_C_DEC:: +find(const_key_reference r_key) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + node_pointer p_nd = find_imp(r_key); + + if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) + { + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) + return end(); + } + + if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_nd)->value()), r_key)) + { + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); + return iterator(p_nd); + } + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) + return end(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_point_iterator +PB_DS_CLASS_C_DEC:: +find(const_key_reference r_key) const +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + + const_node_pointer p_nd = const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(r_key); + + if (p_nd == NULL || p_nd->m_type != pat_trie_leaf_node_type) + { + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) + return end(); + } + + if (synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key)) + { + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(r_key)); + return const_iterator(const_cast<node_pointer>(p_nd)); + } + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(r_key);) + return end(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::node_pointer +PB_DS_CLASS_C_DEC:: +find_imp(const_key_reference r_key) +{ + if (empty()) + return (NULL); + + typename synth_e_access_traits::const_iterator b_it = + synth_e_access_traits::begin(r_key); + typename synth_e_access_traits::const_iterator e_it = + synth_e_access_traits::end(r_key); + + node_pointer p_nd = m_p_head->m_p_parent; + _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); + + while (p_nd->m_type != pat_trie_leaf_node_type) + { + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); + node_pointer p_next_nd = static_cast<internal_node_pointer>(p_nd)->get_child_node(b_it, e_it, this); + + if (p_next_nd == NULL) + return p_nd; + p_nd = p_next_nd; + } + return p_nd; +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::node_pointer +PB_DS_CLASS_C_DEC:: +lower_bound_imp(const_key_reference r_key) +{ + if (empty()) + return (m_p_head); + + node_pointer p_nd = m_p_head->m_p_parent; + _GLIBCXX_DEBUG_ASSERT(p_nd != NULL); + + typename PB_DS_CLASS_C_DEC::const_e_iterator b_it = + synth_e_access_traits::begin(r_key); + + typename PB_DS_CLASS_C_DEC::const_e_iterator e_it = + synth_e_access_traits::end(r_key); + + size_type checked_ind = 0; + while (true) + { + if (p_nd->m_type == pat_trie_leaf_node_type) + { + if (!synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()), r_key)) + return p_nd; + iterator it(p_nd); + ++it; + return it.m_p_nd; + } + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); + const size_type new_checked_ind = + static_cast<internal_node_pointer>(p_nd)->get_e_ind(); + + p_nd = + static_cast<internal_node_pointer>(p_nd)->get_lower_bound_child_node( b_it, e_it, checked_ind, this); + checked_ind = new_checked_ind; + } +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_iterator +PB_DS_CLASS_C_DEC:: +lower_bound(const_key_reference r_key) +{ return point_iterator(lower_bound_imp(r_key)); } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_point_iterator +PB_DS_CLASS_C_DEC:: +lower_bound(const_key_reference r_key) const +{ + return const_point_iterator(const_cast<PB_DS_CLASS_C_DEC* >(this)->lower_bound_imp(r_key)); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_iterator +PB_DS_CLASS_C_DEC:: +upper_bound(const_key_reference r_key) +{ + point_iterator l_bound_it = lower_bound(r_key); + + _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || + !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), + r_key)); + + if (l_bound_it == end() || + synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) + return l_bound_it; + + return ++l_bound_it; +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_point_iterator +PB_DS_CLASS_C_DEC:: +upper_bound(const_key_reference r_key) const +{ + const_point_iterator l_bound_it = lower_bound(r_key); + + _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || + !synth_e_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), + r_key)); + + if (l_bound_it == end() || + synth_e_access_traits::cmp_keys(r_key, PB_DS_V2F(*l_bound_it))) + return l_bound_it; + return ++l_bound_it; +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_e_iterator +PB_DS_CLASS_C_DEC:: +pref_begin(const_node_pointer p_nd) +{ + if (p_nd->m_type == pat_trie_leaf_node_type) + return (synth_e_access_traits::begin(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); + return static_cast<const_internal_node_pointer>(p_nd)->pref_b_it(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_e_iterator +PB_DS_CLASS_C_DEC:: +pref_end(const_node_pointer p_nd) +{ + if (p_nd->m_type == pat_trie_leaf_node_type) + return (synth_e_access_traits::end(PB_DS_V2F(static_cast<const_leaf_pointer>(p_nd)->value()))); + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); + return static_cast<const_internal_node_pointer>(p_nd)->pref_e_it(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_leaf_pointer +PB_DS_CLASS_C_DEC:: +leftmost_descendant(const_node_pointer p_nd) +{ + if (p_nd->m_type == pat_trie_leaf_node_type) + return static_cast<const_leaf_pointer>(p_nd); + return static_cast<const_internal_node_pointer>(p_nd)->leftmost_descendant(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::leaf_pointer +PB_DS_CLASS_C_DEC:: +leftmost_descendant(node_pointer p_nd) +{ + if (p_nd->m_type == pat_trie_leaf_node_type) + return static_cast<leaf_pointer>(p_nd); + return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_leaf_pointer +PB_DS_CLASS_C_DEC:: +rightmost_descendant(const_node_pointer p_nd) +{ + if (p_nd->m_type == pat_trie_leaf_node_type) + return static_cast<const_leaf_pointer>(p_nd); + return static_cast<const_internal_node_pointer>(p_nd)->rightmost_descendant(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::leaf_pointer +PB_DS_CLASS_C_DEC:: +rightmost_descendant(node_pointer p_nd) +{ + if (p_nd->m_type == pat_trie_leaf_node_type) + return static_cast<leaf_pointer>(p_nd); + return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant(); +} + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/head.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/head.hpp new file mode 100644 index 000000000..0c7381294 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/head.hpp @@ -0,0 +1,124 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file head.hpp + * Contains a leaf for a patricia tree. + */ + +#ifndef PB_DS_PAT_TRIE_IHEAD_HPP +#define PB_DS_PAT_TRIE_IHEAD_HPP + +#include <ext/pb_ds/detail/pat_trie_/node_base.hpp> +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { +#define PB_DS_CLASS_T_DEC \ + template<typename Type_Traits, typename E_Access_Traits, \ + typename Metadata, typename Allocator> + +#define PB_DS_CLASS_C_DEC \ + pat_trie_head<Type_Traits, E_Access_Traits, Metadata, Allocator> + +#define PB_DS_BASE_C_DEC \ + pat_trie_node_base<Type_Traits, E_Access_Traits, Metadata, Allocator> + + template<typename Type_Traits, + typename E_Access_Traits, + typename Metadata, + typename Allocator> + struct pat_trie_head : public PB_DS_BASE_C_DEC + { + private: + typedef E_Access_Traits e_access_traits; + + typedef + typename Allocator::template rebind< + e_access_traits>::other::const_pointer + const_e_access_traits_pointer; + + typedef + typename Allocator::template rebind< + PB_DS_BASE_C_DEC>::other::pointer + node_pointer; + +#ifdef _GLIBCXX_DEBUG + typedef + typename PB_DS_BASE_C_DEC::subtree_debug_info + subtree_debug_info; +#endif + + public: + pat_trie_head(); + +#ifdef _GLIBCXX_DEBUG + virtual subtree_debug_info + assert_valid_imp(const_e_access_traits_pointer p_traits) const; +#endif + + public: + node_pointer m_p_min; + + node_pointer m_p_max; + }; + + PB_DS_CLASS_T_DEC + PB_DS_CLASS_C_DEC:: + pat_trie_head() : PB_DS_BASE_C_DEC(pat_trie_head_node_type) + { } + +#ifdef _GLIBCXX_DEBUG + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::subtree_debug_info + PB_DS_CLASS_C_DEC:: + assert_valid_imp(const_e_access_traits_pointer /*p_traits*/) const + { + _GLIBCXX_DEBUG_ASSERT(false); + return subtree_debug_info(); + } +#endif + +#undef PB_DS_CLASS_T_DEC +#undef PB_DS_CLASS_C_DEC +#undef PB_DS_BASE_C_DEC + + } // namespace detail +} // namespace __gnu_pbds + +#endif + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp new file mode 100644 index 000000000..81d7096a9 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp @@ -0,0 +1,58 @@ +// -*- 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_internal_node_allocator.max_size(); } + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp new file mode 100644 index 000000000..e6049743f --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp @@ -0,0 +1,465 @@ +// -*- 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_join_fn_imps.hpp + * Contains an implementation class for bin_search_tree_. + */ + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +join(PB_DS_CLASS_C_DEC& other) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();); + _GLIBCXX_DEBUG_ONLY(other.assert_valid();); + split_join_branch_bag bag; + if (!join_prep(other, bag)) + { + _GLIBCXX_DEBUG_ONLY(assert_valid();); + _GLIBCXX_DEBUG_ONLY(other.assert_valid();); + return; + } + + m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, + other.m_p_head->m_p_parent, 0, bag); + + m_p_head->m_p_parent->m_p_parent = m_p_head; + m_size += other.m_size; + other.initialize(); + _GLIBCXX_DEBUG_ONLY(other.assert_valid();); + m_p_head->m_p_min = leftmost_descendant(m_p_head->m_p_parent); + m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); + _GLIBCXX_DEBUG_ONLY(assert_valid();); +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +join_prep(PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + if (other.m_size == 0) + return false; + + if (m_size == 0) + { + value_swap(other); + return false; + } + + const bool greater = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>( + m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast<const_leaf_pointer>( + other.m_p_head->m_p_min)->value())); + + const bool lesser = synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>( + other.m_p_head->m_p_max)->value()),PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value())); + + if (!greater && !lesser) + __throw_join_error(); + + rec_join_prep(m_p_head->m_p_parent, other.m_p_head->m_p_parent, r_bag); + _GLIBCXX_DEBUG_ONLY(debug_base::join(other);) + return true; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rec_join_prep(const_node_pointer p_l, const_node_pointer p_r, split_join_branch_bag& r_bag) +{ + if (p_l->m_type == pat_trie_leaf_node_type) + { + if (p_r->m_type == pat_trie_leaf_node_type) + { + rec_join_prep(static_cast<const_leaf_pointer>(p_l), + static_cast<const_leaf_pointer>(p_r), r_bag); + return; + } + + _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); + rec_join_prep(static_cast<const_leaf_pointer>(p_l), + static_cast<const_internal_node_pointer>(p_r), r_bag); + return; + } + + _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type); + if (p_r->m_type == pat_trie_leaf_node_type) + { + rec_join_prep(static_cast<const_internal_node_pointer>(p_l), + static_cast<const_leaf_pointer>(p_r), r_bag); + return; + } + + _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); + + rec_join_prep(static_cast<const_internal_node_pointer>(p_l), + static_cast<const_internal_node_pointer>(p_r), r_bag); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rec_join_prep(const_leaf_pointer /*p_l*/, const_leaf_pointer /*p_r*/, + split_join_branch_bag& r_bag) +{ r_bag.add_branch(); } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rec_join_prep(const_leaf_pointer /*p_l*/, const_internal_node_pointer /*p_r*/, + split_join_branch_bag& r_bag) +{ r_bag.add_branch(); } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rec_join_prep(const_internal_node_pointer /*p_l*/, const_leaf_pointer /*p_r*/, + split_join_branch_bag& r_bag) +{ r_bag.add_branch(); } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rec_join_prep(const_internal_node_pointer p_l, const_internal_node_pointer p_r, + split_join_branch_bag& r_bag) +{ + if (p_l->get_e_ind() == p_r->get_e_ind() && + synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(), + p_r->pref_b_it(), p_r->pref_e_it())) + { + for (typename internal_node::const_iterator it = p_r->begin(); + it != p_r->end(); ++ it) + { + const_node_pointer p_l_join_child = p_l->get_join_child(*it, this); + if (p_l_join_child != NULL) + rec_join_prep(p_l_join_child, * it, r_bag); + } + return; + } + + if (p_r->get_e_ind() < p_l->get_e_ind() && + p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) + { + const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this); + if (p_r_join_child != NULL) + rec_join_prep(p_r_join_child, p_l, r_bag); + return; + } + + if (p_r->get_e_ind() < p_l->get_e_ind() && + p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) + { + const_node_pointer p_r_join_child = p_r->get_join_child(p_l, this); + if (p_r_join_child != NULL) + rec_join_prep(p_r_join_child, p_l, r_bag); + return; + } + r_bag.add_branch(); +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::node_pointer +PB_DS_CLASS_C_DEC:: +rec_join(node_pointer p_l, node_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) +{ + _GLIBCXX_DEBUG_ASSERT(p_r != NULL); + if (p_l == NULL) + { + apply_update(p_r, (node_update* )this); + return (p_r); + } + + if (p_l->m_type == pat_trie_leaf_node_type) + { + if (p_r->m_type == pat_trie_leaf_node_type) + { + node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), + static_cast<leaf_pointer>(p_r), r_bag); + apply_update(p_ret, (node_update* )this); + return p_ret; + } + + _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); + node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), + static_cast<internal_node_pointer>(p_r), + checked_ind, r_bag); + apply_update(p_ret, (node_update* )this); + return p_ret; + } + + _GLIBCXX_DEBUG_ASSERT(p_l->m_type == pat_trie_internal_node_type); + if (p_r->m_type == pat_trie_leaf_node_type) + { + node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l), + static_cast<leaf_pointer>(p_r), + checked_ind, r_bag); + apply_update(p_ret, (node_update* )this); + return p_ret; + } + + _GLIBCXX_DEBUG_ASSERT(p_r->m_type == pat_trie_internal_node_type); + node_pointer p_ret = rec_join(static_cast<internal_node_pointer>(p_l), + static_cast<internal_node_pointer>(p_r), + r_bag); + + apply_update(p_ret, (node_update* )this); + return p_ret; +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::node_pointer +PB_DS_CLASS_C_DEC:: +rec_join(leaf_pointer p_l, leaf_pointer p_r, split_join_branch_bag& r_bag) +{ + _GLIBCXX_DEBUG_ASSERT(p_r != NULL); + if (p_l == NULL) + return (p_r); + node_pointer p_ret = insert_branch(p_l, p_r, r_bag); + _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == 2); + return p_ret; +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::node_pointer +PB_DS_CLASS_C_DEC:: +rec_join(leaf_pointer p_l, internal_node_pointer p_r, size_type checked_ind, + split_join_branch_bag& r_bag) +{ +#ifdef _GLIBCXX_DEBUG + const size_type lhs_leafs = recursive_count_leafs(p_l); + const size_type rhs_leafs = recursive_count_leafs(p_r); +#endif + + _GLIBCXX_DEBUG_ASSERT(p_r != NULL); + node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag); + _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs); + return p_ret; +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::node_pointer +PB_DS_CLASS_C_DEC:: +rec_join(internal_node_pointer p_l, leaf_pointer p_r, size_type checked_ind, split_join_branch_bag& r_bag) +{ + _GLIBCXX_DEBUG_ASSERT(p_l != NULL); + _GLIBCXX_DEBUG_ASSERT(p_r != NULL); + +#ifdef _GLIBCXX_DEBUG + const size_type lhs_leafs = recursive_count_leafs(p_l); + const size_type rhs_leafs = recursive_count_leafs(p_r); +#endif + + if (!p_l->should_be_mine(pref_begin(p_r), pref_end(p_r), checked_ind, this)) + { + node_pointer p_ret = insert_branch(p_l, p_r, r_bag); + _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);) + _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == + lhs_leafs + rhs_leafs); + return p_ret; + } + + node_pointer p_pot_child = p_l->add_child(p_r, pref_begin(p_r), + pref_end(p_r), this); + if (p_pot_child != p_r) + { + node_pointer p_new_child = rec_join(p_pot_child, p_r, p_l->get_e_ind(), + r_bag); + + p_l->replace_child(p_new_child, pref_begin(p_new_child), + pref_end(p_new_child), this); + } + + _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this)); + _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs); + return p_l; +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::node_pointer +PB_DS_CLASS_C_DEC:: +rec_join(internal_node_pointer p_l, internal_node_pointer p_r, split_join_branch_bag& r_bag) +{ + _GLIBCXX_DEBUG_ASSERT(p_l != NULL); + _GLIBCXX_DEBUG_ASSERT(p_r != NULL); + +#ifdef _GLIBCXX_DEBUG + const size_type lhs_leafs = recursive_count_leafs(p_l); + const size_type rhs_leafs = recursive_count_leafs(p_r); +#endif + + if (p_l->get_e_ind() == p_r->get_e_ind() && + synth_e_access_traits::equal_prefixes(p_l->pref_b_it(), p_l->pref_e_it(), + p_r->pref_b_it(), p_r->pref_e_it())) + { + for (typename internal_node::iterator it = p_r->begin(); + it != p_r->end(); ++ it) + { + node_pointer p_new_child = rec_join(p_l->get_join_child(*it, this), + * it, 0, r_bag); + p_l->replace_child(p_new_child, pref_begin(p_new_child), + pref_end(p_new_child), this); + } + + p_r->~internal_node(); + s_internal_node_allocator.deallocate(p_r, 1); + _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);) + _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_l) == lhs_leafs + rhs_leafs); + return p_l; + } + + if (p_l->get_e_ind() < p_r->get_e_ind() && + p_l->should_be_mine(p_r->pref_b_it(), p_r->pref_e_it(), 0, this)) + { + node_pointer p_new_child = rec_join(p_l->get_join_child(p_r, this), + p_r, 0, r_bag); + p_l->replace_child(p_new_child, pref_begin(p_new_child), + pref_end(p_new_child), this); + _GLIBCXX_DEBUG_ONLY(p_l->assert_valid(this);) + return p_l; + } + + if (p_r->get_e_ind() < p_l->get_e_ind() && + p_r->should_be_mine(p_l->pref_b_it(), p_l->pref_e_it(), 0, this)) + { + node_pointer p_new_child = rec_join(p_r->get_join_child(p_l, this), p_l, + 0, r_bag); + + p_r->replace_child(p_new_child, pref_begin(p_new_child), + pref_end(p_new_child), this); + + _GLIBCXX_DEBUG_ONLY(p_r->assert_valid(this);) + _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_r) == lhs_leafs + rhs_leafs); + return p_r; + } + + node_pointer p_ret = insert_branch(p_l, p_r, r_bag); + _GLIBCXX_DEBUG_ONLY(p_ret->assert_valid(this);) + _GLIBCXX_DEBUG_ASSERT(recursive_count_leafs(p_ret) == lhs_leafs + rhs_leafs); + return p_ret; +} + +PB_DS_CLASS_T_DEC +inline std::pair<typename PB_DS_CLASS_C_DEC::iterator, bool> +PB_DS_CLASS_C_DEC:: +insert(const_reference r_val) +{ + node_pointer p_lf = find_imp(PB_DS_V2F(r_val)); + if (p_lf != NULL && p_lf->m_type == pat_trie_leaf_node_type && + synth_e_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()), PB_DS_V2F(r_val))) + { + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_exists(PB_DS_V2F(r_val))); + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return std::make_pair(iterator(p_lf), false); + } + + _GLIBCXX_DEBUG_ONLY(debug_base::check_key_does_not_exist(PB_DS_V2F(r_val))); + + leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); + cond_dealtor cond(p_new_lf); + + new (p_new_lf) leaf(r_val); + apply_update(p_new_lf, (node_update* )this); + cond.set_call_destructor(); + split_join_branch_bag bag; + bag.add_branch(); + m_p_head->m_p_parent = rec_join(m_p_head->m_p_parent, p_new_lf, 0, bag); + m_p_head->m_p_parent->m_p_parent = m_p_head; + cond.set_no_action_dtor(); + ++m_size; + update_min_max_for_inserted_leaf(p_new_lf); + _GLIBCXX_DEBUG_ONLY(debug_base::insert_new(PB_DS_V2F(r_val));) + _GLIBCXX_DEBUG_ONLY(assert_valid();) + return std::make_pair(point_iterator(p_new_lf), true); +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::size_type +PB_DS_CLASS_C_DEC:: +keys_diff_ind(typename e_access_traits::const_iterator b_l, typename e_access_traits::const_iterator e_l, typename e_access_traits::const_iterator b_r, typename e_access_traits::const_iterator e_r) +{ + size_type diff_pos = 0; + while (b_l != e_l) + { + if (b_r == e_r) + return (diff_pos); + if (e_access_traits::e_pos(*b_l) != e_access_traits::e_pos(*b_r)) + return (diff_pos); + ++b_l; + ++b_r; + ++diff_pos; + } + _GLIBCXX_DEBUG_ASSERT(b_r != e_r); + return diff_pos; +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::internal_node_pointer +PB_DS_CLASS_C_DEC:: +insert_branch(node_pointer p_l, node_pointer p_r, split_join_branch_bag& r_bag) +{ + typename synth_e_access_traits::const_iterator left_b_it = pref_begin(p_l); + typename synth_e_access_traits::const_iterator left_e_it = pref_end(p_l); + typename synth_e_access_traits::const_iterator right_b_it = pref_begin(p_r); + typename synth_e_access_traits::const_iterator right_e_it = pref_end(p_r); + + const size_type diff_ind = keys_diff_ind(left_b_it, left_e_it, + right_b_it, right_e_it); + + internal_node_pointer p_new_nd = r_bag.get_branch(); + new (p_new_nd) internal_node(diff_ind, left_b_it); + p_new_nd->add_child(p_l, left_b_it, left_e_it, this); + p_new_nd->add_child(p_r, right_b_it, right_e_it, this); + p_l->m_p_parent = p_new_nd; + p_r->m_p_parent = p_new_nd; + _GLIBCXX_DEBUG_ONLY(p_new_nd->assert_valid(this);) + return (p_new_nd); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +update_min_max_for_inserted_leaf(leaf_pointer p_new_lf) +{ + if (m_p_head->m_p_min == m_p_head || + synth_e_access_traits::cmp_keys(PB_DS_V2F(p_new_lf->value()), + PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value()))) + m_p_head->m_p_min = p_new_lf; + + if (m_p_head->m_p_max == m_p_head || + synth_e_access_traits::cmp_keys(PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_max)->value()), PB_DS_V2F(p_new_lf->value()))) + m_p_head->m_p_max = p_new_lf; +} diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/internal_node.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/internal_node.hpp new file mode 100644 index 000000000..bf2f42916 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/internal_node.hpp @@ -0,0 +1,599 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 2009 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file internal_node.hpp + * Contains an internal PB_DS_BASE_C_DEC for a patricia tree. + */ + +#ifndef PB_DS_PAT_TRIE_INTERNAL_NODE_HPP +#define PB_DS_PAT_TRIE_INTERNAL_NODE_HPP + +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { +#define PB_DS_CLASS_T_DEC \ + template<typename Type_Traits, typename E_Access_Traits, \ + typename Metadata, typename Allocator> + +#define PB_DS_CLASS_C_DEC \ + pat_trie_internal_node<Type_Traits, E_Access_Traits, Metadata, Allocator> + +#define PB_DS_BASE_C_DEC \ + pat_trie_node_base<Type_Traits, E_Access_Traits, Metadata, Allocator> + +#define PB_DS_LEAF_C_DEC \ + pat_trie_leaf<Type_Traits, E_Access_Traits, Metadata, Allocator> + + template<typename Type_Traits, + typename E_Access_Traits, + typename Metadata, + typename Allocator> + struct pat_trie_internal_node : public PB_DS_BASE_C_DEC + { + private: + typedef PB_DS_BASE_C_DEC base_type; + typedef Type_Traits type_traits; + typedef typename type_traits::value_type value_type; + typedef typename Allocator::size_type size_type; + + typedef E_Access_Traits e_access_traits; + typedef typename e_access_traits::const_iterator const_e_iterator; + typedef typename Allocator::template rebind<e_access_traits>::other access_rebind; + typedef typename access_rebind::const_pointer const_e_access_traits_pointer; + + typedef typename Allocator::template rebind<base_type>::other base_rebind; + typedef typename base_rebind::pointer node_pointer; + typedef typename base_rebind::const_pointer const_node_pointer; + + typedef PB_DS_LEAF_C_DEC leaf; + typedef typename Allocator::template rebind<leaf>::other leaf_rebind; + typedef typename leaf_rebind::pointer leaf_pointer; + typedef typename leaf_rebind::const_pointer const_leaf_pointer; + + typedef typename Allocator::template rebind<pat_trie_internal_node>::other internal_node_rebind; + typedef typename internal_node_rebind::pointer internal_node_pointer; + typedef typename internal_node_rebind::const_pointer const_internal_node_pointer; + +#ifdef _GLIBCXX_DEBUG + typedef typename base_type::subtree_debug_info subtree_debug_info; + + virtual subtree_debug_info + assert_valid_imp(const_e_access_traits_pointer) const; +#endif + + inline size_type + get_pref_pos(const_e_iterator, const_e_iterator, + const_e_access_traits_pointer) const; + + public: + typedef typename Allocator::template rebind<node_pointer>::other node_pointer_rebind; + typedef typename node_pointer_rebind::pointer node_pointer_pointer; + typedef typename node_pointer_rebind::reference node_pointer_reference; + + enum + { + arr_size = E_Access_Traits::max_size + 1 + }; + PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2); + +#include <ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp> +#include <ext/pb_ds/detail/pat_trie_/child_iterator.hpp> + + pat_trie_internal_node(size_type, const const_e_iterator); + + void + update_prefixes(const_e_access_traits_pointer); + + const_iterator + begin() const; + + iterator + begin(); + + const_iterator + end() const; + + iterator + end(); + + inline node_pointer + get_child_node(const_e_iterator, const_e_iterator, + const_e_access_traits_pointer); + + inline const_node_pointer + get_child_node(const_e_iterator, const_e_iterator, + const_e_access_traits_pointer) const; + + inline iterator + get_child_it(const_e_iterator, const_e_iterator, + const_e_access_traits_pointer); + + inline node_pointer + get_lower_bound_child_node(const_e_iterator, const_e_iterator, + size_type, const_e_access_traits_pointer); + + inline node_pointer + add_child(node_pointer, const_e_iterator, const_e_iterator, + const_e_access_traits_pointer); + + inline const_node_pointer + get_join_child(const_node_pointer, const_e_access_traits_pointer) const; + + inline node_pointer + get_join_child(node_pointer, const_e_access_traits_pointer); + + void + remove_child(node_pointer p_nd); + + iterator + remove_child(iterator it); + + void + replace_child(node_pointer, const_e_iterator, const_e_iterator, + const_e_access_traits_pointer); + + inline const_e_iterator + pref_b_it() const; + + inline const_e_iterator + pref_e_it() const; + + inline size_type + get_e_ind() const; + + bool + should_be_mine(const_e_iterator, const_e_iterator, size_type, + const_e_access_traits_pointer) const; + + leaf_pointer + leftmost_descendant(); + + const_leaf_pointer + leftmost_descendant() const; + + leaf_pointer + rightmost_descendant(); + + const_leaf_pointer + rightmost_descendant() const; + +#ifdef _GLIBCXX_DEBUG + size_type + e_ind() const; +#endif + + private: + pat_trie_internal_node(const pat_trie_internal_node&); + + size_type + get_begin_pos() const; + + const size_type m_e_ind; + const_e_iterator m_pref_b_it; + const_e_iterator m_pref_e_it; + node_pointer m_a_p_children[arr_size]; + static leaf_rebind s_leaf_alloc; + static internal_node_rebind s_internal_node_alloc; + }; + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::leaf_rebind + PB_DS_CLASS_C_DEC::s_leaf_alloc; + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::internal_node_rebind + PB_DS_CLASS_C_DEC::s_internal_node_alloc; + + PB_DS_CLASS_T_DEC + inline typename PB_DS_CLASS_C_DEC::size_type + PB_DS_CLASS_C_DEC:: + get_pref_pos(const_e_iterator b_it, const_e_iterator e_it, + const_e_access_traits_pointer p_traits) const + { + if (static_cast<size_t>(std::distance(b_it, e_it)) <= m_e_ind) + return 0; + std::advance(b_it, m_e_ind); + return 1 + p_traits->e_pos(*b_it); + } + + PB_DS_CLASS_T_DEC + PB_DS_CLASS_C_DEC:: + pat_trie_internal_node(size_type len, const const_e_iterator it) : + PB_DS_BASE_C_DEC(pat_trie_internal_node_type), + m_e_ind(len), m_pref_b_it(it), m_pref_e_it(it) + { + std::advance(m_pref_e_it, m_e_ind); + std::fill(m_a_p_children, m_a_p_children + arr_size, + static_cast<node_pointer>(NULL)); + } + + PB_DS_CLASS_T_DEC + void + PB_DS_CLASS_C_DEC:: + update_prefixes(const_e_access_traits_pointer p_traits) + { + node_pointer p_first = *begin(); + if (p_first->m_type == pat_trie_leaf_node_type) + { + const_leaf_pointer p = static_cast<const_leaf_pointer>(p_first); + m_pref_b_it = p_traits->begin(e_access_traits::extract_key(p->value())); + } + else + { + _GLIBCXX_DEBUG_ASSERT(p_first->m_type == pat_trie_internal_node_type); + m_pref_b_it = static_cast<internal_node_pointer>(p_first)->pref_b_it(); + } + m_pref_e_it = m_pref_b_it; + std::advance(m_pref_e_it, m_e_ind); + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::const_iterator + PB_DS_CLASS_C_DEC:: + begin() const + { + typedef node_pointer_pointer pointer_type; + pointer_type p = const_cast<pointer_type>(m_a_p_children); + return const_iterator(p + get_begin_pos(), p + arr_size); + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::iterator + PB_DS_CLASS_C_DEC:: + begin() + { + return iterator(m_a_p_children + get_begin_pos(), + m_a_p_children + arr_size); + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::const_iterator + PB_DS_CLASS_C_DEC:: + end() const + { + typedef node_pointer_pointer pointer_type; + pointer_type p = const_cast<pointer_type>(m_a_p_children) + arr_size; + return const_iterator(p, p); + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::iterator + PB_DS_CLASS_C_DEC:: + end() + { return iterator(m_a_p_children + arr_size, m_a_p_children + arr_size); } + + PB_DS_CLASS_T_DEC + inline typename PB_DS_CLASS_C_DEC::node_pointer + PB_DS_CLASS_C_DEC:: + get_child_node(const_e_iterator b_it, const_e_iterator e_it, + const_e_access_traits_pointer p_traits) + { + const size_type i = get_pref_pos(b_it, e_it, p_traits); + _GLIBCXX_DEBUG_ASSERT(i < arr_size); + return m_a_p_children[i]; + } + + PB_DS_CLASS_T_DEC + inline typename PB_DS_CLASS_C_DEC::iterator + PB_DS_CLASS_C_DEC:: + get_child_it(const_e_iterator b_it, const_e_iterator e_it, + const_e_access_traits_pointer p_traits) + { + const size_type i = get_pref_pos(b_it, e_it, p_traits); + _GLIBCXX_DEBUG_ASSERT(i < arr_size); + _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i] != NULL); + return iterator(m_a_p_children + i, m_a_p_children + i); + } + + PB_DS_CLASS_T_DEC + inline typename PB_DS_CLASS_C_DEC::const_node_pointer + PB_DS_CLASS_C_DEC:: + get_child_node(const_e_iterator b_it, const_e_iterator e_it, + const_e_access_traits_pointer p_traits) const + { return const_cast<node_pointer>(get_child_node(b_it, e_it, p_traits)); } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::node_pointer + PB_DS_CLASS_C_DEC:: + get_lower_bound_child_node(const_e_iterator b_it, const_e_iterator e_it, + size_type checked_ind, + const_e_access_traits_pointer p_traits) + { + if (!should_be_mine(b_it, e_it, checked_ind, p_traits)) + { + if (p_traits->cmp_prefixes(b_it, e_it, m_pref_b_it, m_pref_e_it, true)) + return leftmost_descendant(); + return rightmost_descendant(); + } + + size_type i = get_pref_pos(b_it, e_it, p_traits); + _GLIBCXX_DEBUG_ASSERT(i < arr_size); + + if (m_a_p_children[i] != NULL) + return m_a_p_children[i]; + + while (++i < arr_size) + if (m_a_p_children[i] != NULL) + { + if (m_a_p_children[i]->m_type == pat_trie_leaf_node_type) + return m_a_p_children[i]; + + _GLIBCXX_DEBUG_ASSERT(m_a_p_children[i]->m_type == pat_trie_internal_node_type); + + return static_cast<internal_node_pointer>(m_a_p_children[i])->leftmost_descendant(); + } + + return rightmost_descendant(); + } + + PB_DS_CLASS_T_DEC + inline typename PB_DS_CLASS_C_DEC::node_pointer + PB_DS_CLASS_C_DEC:: + add_child(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, + const_e_access_traits_pointer p_traits) + { + const size_type i = get_pref_pos(b_it, e_it, p_traits); + _GLIBCXX_DEBUG_ASSERT(i < arr_size); + if (m_a_p_children[i] == NULL) + { + m_a_p_children[i] = p_nd; + p_nd->m_p_parent = this; + return p_nd; + } + return m_a_p_children[i]; + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::const_node_pointer + PB_DS_CLASS_C_DEC:: + get_join_child(const_node_pointer p_nd, const_e_access_traits_pointer p_traits) const + { + node_pointer p = const_cast<node_pointer>(p_nd); + return const_cast<internal_node_pointer>(this)->get_join_child(p, p_traits); + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::node_pointer + PB_DS_CLASS_C_DEC:: + get_join_child(node_pointer p_nd, const_e_access_traits_pointer p_traits) + { + size_type i; + const_e_iterator b_it; + const_e_iterator e_it; + if (p_nd->m_type == pat_trie_leaf_node_type) + { + typename Type_Traits::const_key_reference r_key = + e_access_traits::extract_key(static_cast<const_leaf_pointer>(p_nd)->value()); + + b_it = p_traits->begin(r_key); + e_it = p_traits->end(r_key); + } + else + { + b_it = static_cast<internal_node_pointer>(p_nd)->pref_b_it(); + e_it = static_cast<internal_node_pointer>(p_nd)->pref_e_it(); + } + i = get_pref_pos(b_it, e_it, p_traits); + _GLIBCXX_DEBUG_ASSERT(i < arr_size); + return m_a_p_children[i]; + } + + PB_DS_CLASS_T_DEC + void + PB_DS_CLASS_C_DEC:: + remove_child(node_pointer p_nd) + { + size_type i = 0; + for (; i < arr_size; ++i) + if (m_a_p_children[i] == p_nd) + { + m_a_p_children[i] = NULL; + return; + } + _GLIBCXX_DEBUG_ASSERT(i != arr_size); + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::iterator + PB_DS_CLASS_C_DEC:: + remove_child(iterator it) + { + iterator ret = it; + ++ret; + * it.m_p_p_cur = NULL; + return ret; + } + + PB_DS_CLASS_T_DEC + void + PB_DS_CLASS_C_DEC:: + replace_child(node_pointer p_nd, const_e_iterator b_it, + const_e_iterator e_it, + const_e_access_traits_pointer p_traits) + { + const size_type i = get_pref_pos(b_it, e_it, p_traits); + _GLIBCXX_DEBUG_ASSERT(i < arr_size); + m_a_p_children[i] = p_nd; + p_nd->m_p_parent = this; + } + + PB_DS_CLASS_T_DEC + inline typename PB_DS_CLASS_C_DEC::const_e_iterator + PB_DS_CLASS_C_DEC:: + pref_b_it() const + { return m_pref_b_it; } + + PB_DS_CLASS_T_DEC + inline typename PB_DS_CLASS_C_DEC::const_e_iterator + PB_DS_CLASS_C_DEC:: + pref_e_it() const + { return m_pref_e_it; } + + PB_DS_CLASS_T_DEC + inline typename PB_DS_CLASS_C_DEC::size_type + PB_DS_CLASS_C_DEC:: + get_e_ind() const + { return m_e_ind; } + + PB_DS_CLASS_T_DEC + bool + PB_DS_CLASS_C_DEC:: + should_be_mine(const_e_iterator b_it, const_e_iterator e_it, + size_type checked_ind, + const_e_access_traits_pointer p_traits) const + { + if (m_e_ind == 0) + return true; + + const size_type num_es = std::distance(b_it, e_it); + if (num_es < m_e_ind) + return false; + + const_e_iterator key_b_it = b_it; + std::advance(key_b_it, checked_ind); + const_e_iterator key_e_it = b_it; + std::advance(key_e_it, m_e_ind); + + const_e_iterator value_b_it = m_pref_b_it; + std::advance(value_b_it, checked_ind); + const_e_iterator value_e_it = m_pref_b_it; + std::advance(value_e_it, m_e_ind); + + return p_traits->equal_prefixes(key_b_it, key_e_it, value_b_it, + value_e_it); + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::leaf_pointer + PB_DS_CLASS_C_DEC:: + leftmost_descendant() + { + node_pointer p_pot =* begin(); + if (p_pot->m_type == pat_trie_leaf_node_type) + return (static_cast<leaf_pointer>(p_pot)); + _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type); + return static_cast<internal_node_pointer>(p_pot)->leftmost_descendant(); + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::const_leaf_pointer + PB_DS_CLASS_C_DEC:: + leftmost_descendant() const + { + return const_cast<internal_node_pointer>(this)->leftmost_descendant(); + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::leaf_pointer + PB_DS_CLASS_C_DEC:: + rightmost_descendant() + { + const size_type num_children = std::distance(begin(), end()); + _GLIBCXX_DEBUG_ASSERT(num_children >= 2); + + iterator it = begin(); + std::advance(it, num_children - 1); + node_pointer p_pot =* it; + if (p_pot->m_type == pat_trie_leaf_node_type) + return static_cast<leaf_pointer>(p_pot); + _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == pat_trie_internal_node_type); + return static_cast<internal_node_pointer>(p_pot)->rightmost_descendant(); + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::const_leaf_pointer + PB_DS_CLASS_C_DEC:: + rightmost_descendant() const + { + return const_cast<internal_node_pointer>(this)->rightmost_descendant(); + } + +#ifdef _GLIBCXX_DEBUG + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::size_type + PB_DS_CLASS_C_DEC:: + e_ind() const + { return m_e_ind; } +#endif + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::size_type + PB_DS_CLASS_C_DEC:: + get_begin_pos() const + { + size_type i; + for (i = 0; i < arr_size && m_a_p_children[i] == NULL; ++i) + ; + return i; + } + +#ifdef _GLIBCXX_DEBUG + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::subtree_debug_info + PB_DS_CLASS_C_DEC:: + assert_valid_imp(const_e_access_traits_pointer p_traits) const + { + _GLIBCXX_DEBUG_ASSERT(base_type::m_type == pat_trie_internal_node_type); + _GLIBCXX_DEBUG_ASSERT(static_cast<size_type>(std::distance(pref_b_it(), pref_e_it())) == m_e_ind); + _GLIBCXX_DEBUG_ASSERT(std::distance(begin(), end()) >= 2); + + for (typename pat_trie_internal_node::const_iterator it = begin(); + it != end(); ++it) + { + const_node_pointer p_nd =* it; + _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent == this); + subtree_debug_info child_ret = p_nd->assert_valid_imp(p_traits); + + _GLIBCXX_DEBUG_ASSERT(static_cast<size_type>(std::distance(child_ret.first, child_ret.second)) >= m_e_ind); + _GLIBCXX_DEBUG_ASSERT(should_be_mine(child_ret.first, child_ret.second, 0, p_traits)); + _GLIBCXX_DEBUG_ASSERT(get_pref_pos(child_ret.first, child_ret.second, p_traits) == static_cast<size_type>(it.m_p_p_cur - m_a_p_children)); + } + return std::make_pair(pref_b_it(), pref_e_it()); + } +#endif + +#undef PB_DS_CLASS_T_DEC +#undef PB_DS_CLASS_C_DEC +#undef PB_DS_BASE_C_DEC +#undef PB_DS_LEAF_C_DEC + + } // namespace detail +} // namespace __gnu_pbds + +#endif diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp new file mode 100644 index 000000000..9902d96db --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_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 iterators_fn_imps.hpp + * Contains an implementation class for bin_search_tree_. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC:: +begin() +{ return iterator(m_p_head->m_p_min); } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_iterator +PB_DS_CLASS_C_DEC:: +begin() const +{ return const_iterator(m_p_head->m_p_min); } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::iterator +PB_DS_CLASS_C_DEC:: +end() +{ return iterator(m_p_head); } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_iterator +PB_DS_CLASS_C_DEC:: +end() const +{ return const_iterator(m_p_head); } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator +PB_DS_CLASS_C_DEC:: +rbegin() const +{ + if (empty()) + return rend(); + return --end(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::reverse_iterator +PB_DS_CLASS_C_DEC:: +rbegin() +{ + if (empty()) + return rend(); + return --end(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::reverse_iterator +PB_DS_CLASS_C_DEC:: +rend() +{ return reverse_iterator(m_p_head); } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_reverse_iterator +PB_DS_CLASS_C_DEC:: +rend() const +{ return const_reverse_iterator(m_p_head); } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_node_iterator +PB_DS_CLASS_C_DEC:: +node_begin() const +{ return const_node_iterator(m_p_head->m_p_parent, this); } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::node_iterator +PB_DS_CLASS_C_DEC:: +node_begin() +{ return node_iterator(m_p_head->m_p_parent, this); } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::const_node_iterator +PB_DS_CLASS_C_DEC:: +node_end() const +{ return const_node_iterator(NULL, this); } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::node_iterator +PB_DS_CLASS_C_DEC:: +node_end() +{ return node_iterator(NULL, this); } + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/leaf.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/leaf.hpp new file mode 100644 index 000000000..91cf14faa --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/leaf.hpp @@ -0,0 +1,171 @@ +// -*- 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 leaf.hpp + * Contains a pat_trie_leaf for a patricia tree. + */ + +#ifndef PB_DS_PAT_TRIE_LEAF_HPP +#define PB_DS_PAT_TRIE_LEAF_HPP + +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { + +#define PB_DS_CLASS_T_DEC \ + template< \ + class Type_Traits, \ + class E_Access_Traits, \ + class Metadata, \ + class Allocator> + +#define PB_DS_CLASS_C_DEC \ + pat_trie_leaf< \ + Type_Traits, \ + E_Access_Traits, \ + Metadata, \ + Allocator> + +#define PB_DS_BASE_C_DEC \ + pat_trie_node_base< \ + Type_Traits, \ + E_Access_Traits, \ + Metadata, \ + Allocator> + +#define PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC \ + pat_trie_subtree_debug_info< \ + Type_Traits, \ + E_Access_Traits, \ + Allocator> + + template<typename Type_Traits, + class E_Access_Traits, + class Metadata, + class Allocator> + struct pat_trie_leaf : public PB_DS_BASE_C_DEC + { + private: + typedef typename Type_Traits::value_type value_type; + + typedef typename Type_Traits::const_reference const_reference; + + typedef typename Type_Traits::reference reference; + + typedef + typename Allocator::template rebind< + E_Access_Traits>::other::const_pointer + const_e_access_traits_pointer; + +#ifdef _GLIBCXX_DEBUG + typedef + typename PB_DS_BASE_C_DEC::subtree_debug_info + subtree_debug_info; +#endif + + typedef PB_DS_BASE_C_DEC base_type; + + public: + pat_trie_leaf(const_reference r_val); + + inline reference + value(); + + inline const_reference + value() const; + +#ifdef _GLIBCXX_DEBUG + virtual subtree_debug_info + assert_valid_imp(const_e_access_traits_pointer p_traits) const; + + virtual + ~pat_trie_leaf(); +#endif + + private: + pat_trie_leaf(const PB_DS_CLASS_C_DEC& other); + + value_type m_value; + }; + + PB_DS_CLASS_T_DEC + PB_DS_CLASS_C_DEC:: + pat_trie_leaf(const_reference r_val) : + PB_DS_BASE_C_DEC(pat_trie_leaf_node_type), m_value(r_val) + { } + + PB_DS_CLASS_T_DEC + inline typename PB_DS_CLASS_C_DEC::reference + PB_DS_CLASS_C_DEC:: + value() + { return m_value; } + + PB_DS_CLASS_T_DEC + inline typename PB_DS_CLASS_C_DEC::const_reference + PB_DS_CLASS_C_DEC:: + value() const + { return m_value; } + +#ifdef _GLIBCXX_DEBUG + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::subtree_debug_info + PB_DS_CLASS_C_DEC:: + assert_valid_imp(const_e_access_traits_pointer p_traits) const + { + _GLIBCXX_DEBUG_ASSERT(base_type::m_type == pat_trie_leaf_node_type); + subtree_debug_info ret; + const_reference r_val = value(); + return std::make_pair(p_traits->begin(p_traits->extract_key(r_val)), + p_traits->end(p_traits->extract_key(r_val))); + } + + PB_DS_CLASS_T_DEC + PB_DS_CLASS_C_DEC:: + ~pat_trie_leaf() { } +#endif + +#undef PB_DS_CLASS_T_DEC +#undef PB_DS_CLASS_C_DEC +#undef PB_DS_BASE_C_DEC +#undef PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC + + } // namespace detail +} // namespace __gnu_pbds + +#endif diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_base.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_base.hpp new file mode 100644 index 000000000..bb13068bc --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_base.hpp @@ -0,0 +1,128 @@ +// -*- 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_base.hpp + * Contains a pat_trie_node_base base for a patricia tree. + */ + +#ifndef PB_DS_PAT_TRIE_NODE_BASE_HPP +#define PB_DS_PAT_TRIE_NODE_BASE_HPP + +#include <ext/pb_ds/detail/pat_trie_/node_metadata_base.hpp> + +namespace __gnu_pbds +{ + namespace detail + { +#define PB_DS_CLASS_T_DEC \ + template<typename Type_Traits, typename E_Access_Traits, \ + typename Metadata, typename Allocator> + +#define PB_DS_CLASS_C_DEC \ + pat_trie_node_base<Type_Traits, E_Access_Traits, Metadata, Allocator> + +#define PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC \ + pat_trie_subtree_debug_info<Type_Traits, E_Access_Traits, Allocator> + + enum pat_trie_node_type + { + pat_trie_internal_node_type, + pat_trie_leaf_node_type, + pat_trie_head_node_type + }; + + template<typename Type_Traits, + typename E_Access_Traits, + typename Metadata, + typename Allocator> + struct pat_trie_node_base : public pat_trie_node_metadata_base< + Metadata, + Allocator> + { + public: + typedef + typename Allocator::template rebind< + pat_trie_node_base>::other::pointer + node_pointer; + + typedef + typename Allocator::template rebind< + E_Access_Traits>::other::const_pointer + const_e_access_traits_pointer; + +#ifdef _GLIBCXX_DEBUG + typedef + std::pair< + typename E_Access_Traits::const_iterator, + typename E_Access_Traits::const_iterator> + subtree_debug_info; +#endif + + pat_trie_node_base(pat_trie_node_type type); + +#ifdef _GLIBCXX_DEBUG + void + assert_valid(const_e_access_traits_pointer p_traits) const; + + virtual subtree_debug_info + assert_valid_imp(const_e_access_traits_pointer p_traits) const = 0; +#endif + + node_pointer m_p_parent; + const pat_trie_node_type m_type; + }; + + PB_DS_CLASS_T_DEC + PB_DS_CLASS_C_DEC:: + pat_trie_node_base(pat_trie_node_type type) : m_type(type) + { } + +#ifdef _GLIBCXX_DEBUG + PB_DS_CLASS_T_DEC + void + PB_DS_CLASS_C_DEC:: + assert_valid(const_e_access_traits_pointer p_traits) const + { assert_valid_imp(p_traits); } +#endif + +#undef PB_DS_CLASS_T_DEC +#undef PB_DS_CLASS_C_DEC +#undef PB_DS_PAT_TRIE_SUBTREE_DEBUG_INFO_C_DEC + + } // namespace detail +} // namespace __gnu_pbds + +#endif diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp new file mode 100644 index 000000000..37250091d --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp @@ -0,0 +1,338 @@ +// -*- 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 pat_trie_. + */ + +#ifndef PB_DS_PAT_TRIE_NODE_ITERATORS_HPP +#define PB_DS_PAT_TRIE_NODE_ITERATORS_HPP + +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { + +#define PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC \ + pat_trie_const_node_it_< \ + Node, \ + Leaf, \ + Head, \ + Internal_Node, \ + Const_Iterator, \ + Iterator, \ + E_Access_Traits, \ + Allocator> + +#define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \ + pat_trie_node_it_< \ + Node, \ + Leaf, \ + Head, \ + Internal_Node, \ + Const_Iterator, \ + Iterator, \ + E_Access_Traits, \ + Allocator> + + // Const node iterator. + template<typename Node, + class Leaf, + class Head, + class Internal_Node, + class Const_Iterator, + class Iterator, + class E_Access_Traits, + class Allocator> + class pat_trie_const_node_it_ + { + protected: + typedef + typename Allocator::template rebind< + Node>::other::pointer + node_pointer; + + typedef + typename Allocator::template rebind< + Leaf>::other::const_pointer + const_leaf_pointer; + + typedef + typename Allocator::template rebind< + Leaf>::other::pointer + leaf_pointer; + + typedef + typename Allocator::template rebind< + Internal_Node>::other::pointer + internal_node_pointer; + + typedef + typename Allocator::template rebind< + Internal_Node>::other::const_pointer + const_internal_node_pointer; + + typedef + typename Allocator::template rebind< + E_Access_Traits>::other::const_pointer + const_e_access_traits_pointer; + + private: + inline typename E_Access_Traits::const_iterator + pref_begin() const + { + if (m_p_nd->m_type == pat_trie_leaf_node_type) + return (m_p_traits->begin( + m_p_traits->extract_key( + static_cast<const_leaf_pointer>(m_p_nd)->value()))); + + _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); + + return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_b_it()); + } + + inline typename E_Access_Traits::const_iterator + pref_end() const + { + if (m_p_nd->m_type == pat_trie_leaf_node_type) + return (m_p_traits->end( + m_p_traits->extract_key( + static_cast<const_leaf_pointer>(m_p_nd)->value()))); + + _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); + + return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_e_it()); + } + + public: + + // Size type. + typedef typename Allocator::size_type size_type; + + // Category. + typedef trivial_iterator_tag iterator_category; + + // Difference type. + typedef trivial_iterator_difference_type difference_type; + + // __Iterator's value type. + typedef Const_Iterator value_type; + + // __Iterator's reference type. + typedef value_type reference; + + // __Iterator's __const reference type. + typedef value_type const_reference; + + // Element access traits. + typedef E_Access_Traits e_access_traits; + + // A key's element __const iterator. + typedef typename e_access_traits::const_iterator const_e_iterator; + + // Metadata type. + typedef typename Node::metadata_type metadata_type; + + // Const metadata reference type. + typedef + typename Allocator::template rebind< + metadata_type>::other::const_reference + const_metadata_reference; + + // Default constructor. + /* + inline + pat_trie_const_node_it_() + */ + inline + pat_trie_const_node_it_(node_pointer p_nd = NULL, + const_e_access_traits_pointer p_traits = NULL) + : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits) + { } + + // Subtree valid prefix. + inline std::pair<const_e_iterator, const_e_iterator> + valid_prefix() const + { return std::make_pair(pref_begin(), pref_end()); } + + // Const access; returns the __const iterator* associated with + // the current leaf. + inline const_reference + operator*() const + { + _GLIBCXX_DEBUG_ASSERT(num_children() == 0); + return Const_Iterator(m_p_nd); + } + + // Metadata access. + inline const_metadata_reference + get_metadata() const + { return m_p_nd->get_metadata(); } + + // Returns the number of children in the corresponding node. + inline size_type + num_children() const + { + if (m_p_nd->m_type == pat_trie_leaf_node_type) + return 0; + _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); + return std::distance(static_cast<internal_node_pointer>(m_p_nd)->begin(), static_cast<internal_node_pointer>(m_p_nd)->end()); + } + + // Returns a __const node __iterator to the corresponding node's + // i-th child. + PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC + get_child(size_type i) const + { + _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type); + typename Internal_Node::iterator it = + static_cast<internal_node_pointer>(m_p_nd)->begin(); + + std::advance(it, i); + return PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC(*it, m_p_traits); + } + + // Compares content to a different iterator object. + inline bool + operator==(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const + { return (m_p_nd == other.m_p_nd); } + + // Compares content (negatively) to a different iterator object. + inline bool + operator!=(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const + { return m_p_nd != other.m_p_nd; } + + private: + + friend class PB_DS_CLASS_C_DEC; + + public: + node_pointer m_p_nd; + + const_e_access_traits_pointer m_p_traits; + }; + + // Node iterator. + template<typename Node, + class Leaf, + class Head, + class Internal_Node, + class Const_Iterator, + class Iterator, + class E_Access_Traits, + class Allocator> + class pat_trie_node_it_ : + public PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC + + { + private: + typedef + typename Allocator::template rebind< + Node>::other::pointer + node_pointer; + + typedef Iterator iterator; + + typedef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC base_type; + + typedef + typename base_type::const_e_access_traits_pointer + const_e_access_traits_pointer; + + typedef typename base_type::internal_node_pointer internal_node_pointer; + + public: + + // Size type. + typedef + typename PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC::size_type + size_type; + + // __Iterator's value type. + typedef Iterator value_type; + + // __Iterator's reference type. + typedef value_type reference; + + // __Iterator's __const reference type. + typedef value_type const_reference; + + // Default constructor. + /* + inline + pat_trie_node_it_() ; + */ + + inline + pat_trie_node_it_(node_pointer p_nd = NULL, const_e_access_traits_pointer p_traits = NULL) : base_type(p_nd, p_traits) + { } + + // Access; returns the iterator* associated with the current leaf. + inline reference + operator*() const + { + _GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0); + return Iterator(base_type::m_p_nd); + + } + + // Returns a node __iterator to the corresponding node's i-th child. + PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC + get_child(size_type i) const + { + _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == pat_trie_internal_node_type); + + typename Internal_Node::iterator it = + static_cast<internal_node_pointer>(base_type::m_p_nd)->begin(); + + std::advance(it, i); + return PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC(*it, base_type::m_p_traits); + } + + private: + friend class PB_DS_CLASS_C_DEC; + }; + +#undef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC +#undef PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC + + } // namespace detail +} // namespace __gnu_pbds + +#endif + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_metadata_base.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_metadata_base.hpp new file mode 100644 index 000000000..36272eda8 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_metadata_base.hpp @@ -0,0 +1,86 @@ +// -*- 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_metadata_base.hpp + * Contains an internal PB_DS_BASE_C_DEC for a patricia tree. + */ + +#ifndef PB_DS_PAT_TRIE_NODE_METADATA_BASE_HPP +#define PB_DS_PAT_TRIE_NODE_METADATA_BASE_HPP + +#include <ext/pb_ds/detail/basic_tree_policy/null_node_metadata.hpp> + +namespace __gnu_pbds +{ + namespace detail + { + + template<typename Metadata, class Allocator> + struct pat_trie_node_metadata_base + { + public: + typedef Metadata metadata_type; + + typedef + typename Allocator::template rebind< + metadata_type>::other::const_reference + const_metadata_reference; + + public: + inline const_metadata_reference + get_metadata() const + { + return (m_metadata); + } + + public: + metadata_type m_metadata; + }; + + template<typename Allocator> + struct pat_trie_node_metadata_base< + null_node_metadata, + Allocator> + { + public: + typedef null_node_metadata metadata_type; + }; + + } // namespace detail +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_PAT_TRIE_NODE_BASE_HPP + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp new file mode 100644 index 000000000..f6f420986 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp @@ -0,0 +1,515 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2007, 2009 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file pat_trie_.hpp + * Contains an implementation class for a patricia tree. + */ + +/** + * This implementation loosely borrows ideas from: + * 1) "Fast Mergeable Integer Maps", Okasaki, Gill 1998 + * 2) "Ptset: Sets of integers implemented as Patricia trees", + * Jean-Christophe Filliatr, 2000 + **/ + +#include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp> +#include <ext/pb_ds/detail/pat_trie_/node_base.hpp> +#include <ext/pb_ds/exception.hpp> +#include <ext/pb_ds/tag_and_trait.hpp> +#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> +#include <ext/pb_ds/detail/types_traits.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 <iterator> +#include <utility> +#include <algorithm> +#include <functional> +#include <assert.h> +#include <list> +#ifdef _GLIBCXX_DEBUG +#include <ext/pb_ds/detail/debug_map_base.hpp> +#endif +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { +#define PB_DS_CLASS_T_DEC \ + template<typename Key, typename Mapped, typename Node_And_It_Traits, \ + typename Allocator> + +#ifdef PB_DS_DATA_TRUE_INDICATOR +#define PB_DS_CLASS_NAME pat_trie_data_ +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR +#define PB_DS_CLASS_NAME pat_trie_no_data_ +#endif + +#define PB_DS_CLASS_C_DEC \ + PB_DS_CLASS_NAME<Key, Mapped, 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, \ + std::less<Key> >, 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 + + /** + * class description = PATRICIA trie implementation."> + **/ + template<typename Key, + typename Mapped, + typename Node_And_It_Traits, + typename Allocator> + class PB_DS_CLASS_NAME : +#ifdef _GLIBCXX_DEBUG + public PB_DS_DEBUG_MAP_BASE_C_DEC, +#endif + public Node_And_It_Traits::synth_e_access_traits, + public Node_And_It_Traits::node_update, + public PB_DS_TYPES_TRAITS_C_DEC + { + private: + typedef PB_DS_TYPES_TRAITS_C_DEC traits_base; + + typedef typename Node_And_It_Traits::synth_e_access_traits synth_e_access_traits; + typedef typename Allocator::template rebind<synth_e_access_traits>::other::const_pointer const_e_access_traits_pointer; + typedef typename synth_e_access_traits::const_iterator const_e_iterator; + + typedef typename Node_And_It_Traits::node node; + typedef typename Allocator::template rebind<node>::other::const_pointer const_node_pointer; + + typedef typename Allocator::template rebind<node>::other::pointer node_pointer; + + typedef typename Node_And_It_Traits::head head; + typedef typename Allocator::template rebind<head>::other head_allocator; + typedef typename head_allocator::pointer head_pointer; + + typedef typename Node_And_It_Traits::leaf leaf; + typedef typename Allocator::template rebind<leaf>::other leaf_allocator; + typedef typename leaf_allocator::const_pointer const_leaf_pointer; + typedef typename leaf_allocator::pointer leaf_pointer; + + typedef typename Node_And_It_Traits::internal_node internal_node; + typedef typename Allocator::template rebind<internal_node>::other internal_node_allocator; + typedef typename internal_node_allocator::const_pointer const_internal_node_pointer; + typedef typename internal_node_allocator::pointer internal_node_pointer; + +#include <ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp> + +#ifdef _GLIBCXX_DEBUG + typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; +#endif + +#include <ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp> + + typedef typename Node_And_It_Traits::null_node_update_pointer null_node_update_pointer; + + public: + typedef pat_trie_tag container_category; + typedef Allocator allocator_type; + typedef typename Allocator::size_type size_type; + typedef typename Allocator::difference_type difference_type; + + typedef typename traits_base::key_type key_type; + typedef typename traits_base::key_pointer key_pointer; + typedef typename traits_base::const_key_pointer const_key_pointer; + typedef typename traits_base::key_reference key_reference; + typedef typename traits_base::const_key_reference const_key_reference; + typedef typename traits_base::mapped_type mapped_type; + typedef typename traits_base::mapped_pointer mapped_pointer; + typedef typename traits_base::const_mapped_pointer const_mapped_pointer; + typedef typename traits_base::mapped_reference mapped_reference; + typedef typename traits_base::const_mapped_reference const_mapped_reference; + typedef typename traits_base::value_type value_type; + typedef typename traits_base::pointer pointer; + typedef typename traits_base::const_pointer const_pointer; + typedef typename traits_base::reference reference; + typedef typename traits_base::const_reference const_reference; + + typedef typename Node_And_It_Traits::const_iterator const_point_iterator; + typedef typename Node_And_It_Traits::iterator point_iterator; + typedef const_point_iterator const_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 typename Node_And_It_Traits::e_access_traits e_access_traits; + typedef typename Node_And_It_Traits::node_update node_update; + + PB_DS_CLASS_NAME(); + + PB_DS_CLASS_NAME(const e_access_traits&); + + PB_DS_CLASS_NAME(const PB_DS_CLASS_C_DEC&); + + void + swap(PB_DS_CLASS_C_DEC&); + + ~PB_DS_CLASS_NAME(); + + inline bool + empty() const; + + inline size_type + size() const; + + inline size_type + max_size() const; + + e_access_traits& + get_e_access_traits(); + + const e_access_traits& + get_e_access_traits() const; + + node_update& + get_node_update(); + + const node_update& + get_node_update() const; + + inline std::pair<point_iterator, bool> + insert(const_reference); + + inline mapped_reference + operator[](const_key_reference r_key) + { +#ifdef PB_DS_DATA_TRUE_INDICATOR + return insert(std::make_pair(r_key, mapped_type())).first->second; +#else + insert(r_key); + return traits_base::s_null_mapped; +#endif + } + + inline point_iterator + find(const_key_reference); + + inline const_point_iterator + find(const_key_reference) const; + + inline point_iterator + lower_bound(const_key_reference); + + inline const_point_iterator + lower_bound(const_key_reference) const; + + inline point_iterator + upper_bound(const_key_reference); + + inline const_point_iterator + upper_bound(const_key_reference) const; + + void + clear(); + + inline bool + erase(const_key_reference); + + inline const_iterator + erase(const_iterator); + +#ifdef PB_DS_DATA_TRUE_INDICATOR + inline iterator + erase(iterator); +#endif + + inline const_reverse_iterator + erase(const_reverse_iterator); + +#ifdef PB_DS_DATA_TRUE_INDICATOR + inline reverse_iterator + erase(reverse_iterator); +#endif + + template<typename Pred> + inline size_type + erase_if(Pred); + + void + join(PB_DS_CLASS_C_DEC&); + + void + split(const_key_reference, PB_DS_CLASS_C_DEC&); + + 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(); + +#ifdef PB_DS_PAT_TRIE_TRACE_ + void + trace() const; +#endif + + protected: + + template<typename It> + void + copy_from_range(It, It); + + void + value_swap(PB_DS_CLASS_C_DEC&); + + node_pointer + recursive_copy_node(const_node_pointer); + + private: + + void + initialize(); + + inline void + apply_update(node_pointer, null_node_update_pointer); + + template<typename Node_Update_> + inline void + apply_update(node_pointer, Node_Update_*); + + bool + join_prep(PB_DS_CLASS_C_DEC&, split_join_branch_bag&); + + void + rec_join_prep(const_node_pointer, const_node_pointer, + split_join_branch_bag&); + + void + rec_join_prep(const_leaf_pointer, const_leaf_pointer, + split_join_branch_bag&); + + void + rec_join_prep(const_leaf_pointer, const_internal_node_pointer, + split_join_branch_bag&); + + void + rec_join_prep(const_internal_node_pointer, const_leaf_pointer, + split_join_branch_bag&); + + void + rec_join_prep(const_internal_node_pointer, const_internal_node_pointer, + split_join_branch_bag&); + + node_pointer + rec_join(node_pointer, node_pointer, size_type, split_join_branch_bag&); + + node_pointer + rec_join(leaf_pointer, leaf_pointer, split_join_branch_bag&); + + node_pointer + rec_join(leaf_pointer, internal_node_pointer, size_type, + split_join_branch_bag&); + + node_pointer + rec_join(internal_node_pointer, leaf_pointer, size_type, + split_join_branch_bag&); + + node_pointer + rec_join(internal_node_pointer, internal_node_pointer, + split_join_branch_bag&); + + size_type + keys_diff_ind(typename e_access_traits::const_iterator, typename e_access_traits::const_iterator, typename e_access_traits::const_iterator, typename e_access_traits::const_iterator); + + internal_node_pointer + insert_branch(node_pointer, node_pointer, split_join_branch_bag&); + + void + update_min_max_for_inserted_leaf(leaf_pointer); + + void + erase_leaf(leaf_pointer); + + inline void + actual_erase_leaf(leaf_pointer); + + void + clear_imp(node_pointer); + + void + erase_fixup(internal_node_pointer); + + void + update_min_max_for_erased_leaf(leaf_pointer); + + static inline const_e_iterator + pref_begin(const_node_pointer); + + static inline const_e_iterator + pref_end(const_node_pointer); + + inline node_pointer + find_imp(const_key_reference); + + inline node_pointer + lower_bound_imp(const_key_reference); + + inline node_pointer + upper_bound_imp(const_key_reference); + + inline static const_leaf_pointer + leftmost_descendant(const_node_pointer); + + inline static leaf_pointer + leftmost_descendant(node_pointer); + + inline static const_leaf_pointer + rightmost_descendant(const_node_pointer); + + inline static leaf_pointer + rightmost_descendant(node_pointer); + +#ifdef _GLIBCXX_DEBUG + void + assert_valid() const; + + void + assert_iterators() const; + + void + assert_reverse_iterators() const; + + static size_type + recursive_count_leafs(const_node_pointer); +#endif + +#ifdef PB_DS_PAT_TRIE_TRACE_ + static void + trace_node(const_node_pointer, size_type); + + template<typename Metadata_> + static void + trace_node_metadata(const_node_pointer, type_to_type<Metadata_>); + + static void + trace_node_metadata(const_node_pointer, type_to_type<null_node_metadata>); +#endif + + leaf_pointer + split_prep(const_key_reference, PB_DS_CLASS_C_DEC&, + split_join_branch_bag&); + + node_pointer + rec_split(node_pointer, const_e_iterator, const_e_iterator, + PB_DS_CLASS_C_DEC&, split_join_branch_bag&); + + void + split_insert_branch(size_type, const_e_iterator, + typename internal_node::iterator, + size_type, split_join_branch_bag&); + + static head_allocator s_head_allocator; + static internal_node_allocator s_internal_node_allocator; + static leaf_allocator s_leaf_allocator; + + head_pointer m_p_head; + size_type m_size; + }; + +#include <ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp> +#include <ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp> +#include <ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp> +#include <ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp> +#include <ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp> +#include <ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp> +#include <ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp> +#include <ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp> +#include <ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp> +#include <ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp> +#include <ext/pb_ds/detail/pat_trie_/update_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 +#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/pat_trie_/point_iterators.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp new file mode 100644 index 000000000..cada9071c --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp @@ -0,0 +1,484 @@ +// -*- 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_PAT_TRIE_FIND_ITERATORS_HPP +#define PB_DS_PAT_TRIE_FIND_ITERATORS_HPP + +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { + +#define PB_DS_CONST_IT_C_DEC \ + pat_trie_const_it_< \ + Type_Traits, \ + Node, \ + Leaf, \ + Head, \ + Internal_Node, \ + Is_Forward_Iterator, \ + Allocator> + +#define PB_DS_CONST_ODIR_IT_C_DEC \ + pat_trie_const_it_< \ + Type_Traits, \ + Node, \ + Leaf, \ + Head, \ + Internal_Node, \ + !Is_Forward_Iterator, \ + Allocator> + +#define PB_DS_IT_C_DEC \ + pat_trie_it_< \ + Type_Traits, \ + Node, \ + Leaf, \ + Head, \ + Internal_Node, \ + Is_Forward_Iterator, \ + Allocator> + +#define PB_DS_ODIR_IT_C_DEC \ + pat_trie_it_< \ + Type_Traits, \ + Node, \ + Leaf, \ + Head, \ + Internal_Node, \ + !Is_Forward_Iterator, \ + Allocator> + + + // Const iterator. + template<typename Type_Traits, + class Node, + class Leaf, + class Head, + class Internal_Node, + bool Is_Forward_Iterator, + class Allocator> + class pat_trie_const_it_ + { + + private: + typedef + typename Allocator::template rebind< + Node>::other::pointer + node_pointer; + + typedef + typename Allocator::template rebind< + Leaf>::other::const_pointer + const_leaf_pointer; + + typedef + typename Allocator::template rebind< + Leaf>::other::pointer + leaf_pointer; + + typedef + typename Allocator::template rebind< + Head>::other::pointer + head_pointer; + + typedef + typename Allocator::template rebind< + Internal_Node>::other::pointer + internal_node_pointer; + + public: + + typedef std::bidirectional_iterator_tag iterator_category; + + typedef typename Allocator::difference_type difference_type; + + typedef typename Type_Traits::value_type value_type; + + typedef typename Type_Traits::pointer pointer; + + typedef typename Type_Traits::const_pointer const_pointer; + + typedef typename Type_Traits::reference reference; + + typedef typename Type_Traits::const_reference const_reference; + + public: + + inline + pat_trie_const_it_(node_pointer p_nd = NULL) : m_p_nd(p_nd) + { } + + inline + pat_trie_const_it_(const PB_DS_CONST_ODIR_IT_C_DEC& other) + : m_p_nd(other.m_p_nd) + { } + + inline + PB_DS_CONST_IT_C_DEC& + operator=(const PB_DS_CONST_IT_C_DEC& other) + { + m_p_nd = other.m_p_nd; + return *this; + } + + inline + PB_DS_CONST_IT_C_DEC& + operator=(const PB_DS_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->m_type == pat_trie_leaf_node_type); + return &static_cast<leaf_pointer>(m_p_nd)->value(); + } + + inline const_reference + operator*() const + { + _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_leaf_node_type); + return static_cast<leaf_pointer>(m_p_nd)->value(); + } + + inline bool + operator==(const PB_DS_CONST_IT_C_DEC& other) const + { return (m_p_nd == other.m_p_nd); } + + inline bool + operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const + { return (m_p_nd == other.m_p_nd); } + + inline bool + operator!=(const PB_DS_CONST_IT_C_DEC& other) const + { return (m_p_nd != other.m_p_nd); } + + inline bool + operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const + { return (m_p_nd != other.m_p_nd); } + + inline PB_DS_CONST_IT_C_DEC& + operator++() + { + inc(integral_constant<int,Is_Forward_Iterator>()); + return *this; + } + + inline PB_DS_CONST_IT_C_DEC + operator++(int) + { + PB_DS_CONST_IT_C_DEC ret_it(m_p_nd); + operator++(); + return ret_it; + } + + inline PB_DS_CONST_IT_C_DEC& + operator--() + { + dec(integral_constant<int,Is_Forward_Iterator>()); + return *this; + } + + inline PB_DS_CONST_IT_C_DEC + operator--(int) + { + PB_DS_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->m_type == pat_trie_head_node_type) + { + m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_min; + return; + } + + node_pointer p_y = m_p_nd->m_p_parent; + while (p_y->m_type != pat_trie_head_node_type && + get_larger_sibling(m_p_nd) == NULL) + { + m_p_nd = p_y; + p_y = p_y->m_p_parent; + } + + if (p_y->m_type == pat_trie_head_node_type) + { + m_p_nd = p_y; + return; + } + m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd)); + } + + inline void + dec(false_type) + { inc(true_type()); } + + void + dec(true_type) + { + if (m_p_nd->m_type == pat_trie_head_node_type) + { + m_p_nd = static_cast<head_pointer>(m_p_nd)->m_p_max; + return; + } + + node_pointer p_y = m_p_nd->m_p_parent; + while (p_y->m_type != pat_trie_head_node_type && + get_smaller_sibling(m_p_nd) == NULL) + { + m_p_nd = p_y; + p_y = p_y->m_p_parent; + } + + if (p_y->m_type == pat_trie_head_node_type) + { + m_p_nd = p_y; + return; + } + m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd)); + } + + inline static node_pointer + get_larger_sibling(node_pointer p_nd) + { + internal_node_pointer p_parent = + static_cast<internal_node_pointer>(p_nd->m_p_parent); + + typename Internal_Node::iterator it = p_parent->begin(); + while (*it != p_nd) + ++it; + + typename Internal_Node::iterator next_it = it; + ++next_it; + return ((next_it == p_parent->end())? NULL :* next_it); + } + + inline static node_pointer + get_smaller_sibling(node_pointer p_nd) + { + internal_node_pointer p_parent = + static_cast<internal_node_pointer>(p_nd->m_p_parent); + + typename Internal_Node::iterator it = p_parent->begin(); + + if (*it == p_nd) + return (NULL); + typename Internal_Node::iterator prev_it; + do + { + prev_it = it; + ++it; + if (*it == p_nd) + return (*prev_it); + } + while (true); + + _GLIBCXX_DEBUG_ASSERT(false); + return (NULL); + } + + inline static leaf_pointer + leftmost_descendant(node_pointer p_nd) + { + if (p_nd->m_type == pat_trie_leaf_node_type) + return static_cast<leaf_pointer>(p_nd); + return static_cast<internal_node_pointer>(p_nd)->leftmost_descendant(); + } + + inline static leaf_pointer + rightmost_descendant(node_pointer p_nd) + { + if (p_nd->m_type == pat_trie_leaf_node_type) + return static_cast<leaf_pointer>(p_nd); + return static_cast<internal_node_pointer>(p_nd)->rightmost_descendant(); + } + + public: + node_pointer m_p_nd; + }; + + // Iterator. + template<typename Type_Traits, + class Node, + class Leaf, + class Head, + class Internal_Node, + bool Is_Forward_Iterator, + class Allocator> + class pat_trie_it_ : + public PB_DS_CONST_IT_C_DEC + + { + private: + typedef + typename Allocator::template rebind< + Node>::other::pointer + node_pointer; + + typedef + typename Allocator::template rebind< + Leaf>::other::const_pointer + const_leaf_pointer; + + typedef + typename Allocator::template rebind< + Leaf>::other::pointer + leaf_pointer; + + typedef + typename Allocator::template rebind< + Head>::other::pointer + head_pointer; + + typedef + typename Allocator::template rebind< + Internal_Node>::other::pointer + internal_node_pointer; + + public: + typedef typename Type_Traits::value_type value_type; + + typedef typename Type_Traits::const_pointer const_pointer; + + typedef typename Type_Traits::pointer pointer; + + typedef typename Type_Traits::const_reference const_reference; + + typedef typename Type_Traits::reference reference; + + inline + pat_trie_it_(node_pointer p_nd = NULL) : PB_DS_CONST_IT_C_DEC((node_pointer)p_nd) + { } + + inline + pat_trie_it_(const PB_DS_ODIR_IT_C_DEC& other) : PB_DS_CONST_IT_C_DEC(other.m_p_nd) + { } + + inline + PB_DS_IT_C_DEC& + operator=(const PB_DS_IT_C_DEC& other) + { + base_it_type::m_p_nd = other.m_p_nd; + return *this; + } + + inline + PB_DS_IT_C_DEC& + operator=(const PB_DS_ODIR_IT_C_DEC& other) + { + base_it_type::m_p_nd = other.m_p_nd; + return *this; + } + + inline pointer + operator->() const + { + _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type); + + return &static_cast<leaf_pointer>(base_it_type::m_p_nd)->value(); + } + + inline reference + operator*() const + { + _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd->m_type == pat_trie_leaf_node_type); + return static_cast<leaf_pointer>(base_it_type::m_p_nd)->value(); + } + + inline PB_DS_IT_C_DEC& + operator++() + { + PB_DS_CONST_IT_C_DEC:: + operator++(); + return *this; + } + + inline PB_DS_IT_C_DEC + operator++(int) + { + PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd); + operator++(); + return ret_it; + } + + inline PB_DS_IT_C_DEC& + operator--() + { + PB_DS_CONST_IT_C_DEC::operator--(); + return *this; + } + + inline PB_DS_IT_C_DEC + operator--(int) + { + PB_DS_IT_C_DEC ret_it(base_it_type::m_p_nd); + operator--(); + return ret_it; + } + + protected: + typedef PB_DS_CONST_IT_C_DEC base_it_type; + + friend class PB_DS_CLASS_C_DEC; + }; + +#undef PB_DS_CONST_IT_C_DEC +#undef PB_DS_CONST_ODIR_IT_C_DEC +#undef PB_DS_IT_C_DEC +#undef PB_DS_ODIR_IT_C_DEC + + } // namespace detail +} // namespace __gnu_pbds + +#endif + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp new file mode 100644 index 000000000..79bfe4283 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp @@ -0,0 +1,63 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file policy_access_fn_imps.hpp + * Contains an implementation class for bin_search_tree_. + */ + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::e_access_traits& +PB_DS_CLASS_C_DEC:: +get_e_access_traits() +{ return *this; } + +PB_DS_CLASS_T_DEC +const typename PB_DS_CLASS_C_DEC::e_access_traits& +PB_DS_CLASS_C_DEC:: +get_e_access_traits() const +{ return *this; } + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::node_update& +PB_DS_CLASS_C_DEC:: +get_node_update() +{ return *this; } + +PB_DS_CLASS_T_DEC +const typename PB_DS_CLASS_C_DEC::node_update& +PB_DS_CLASS_C_DEC:: +get_node_update() const +{ return *this; } diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp new file mode 100644 index 000000000..52edf2506 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp @@ -0,0 +1,103 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file 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(assert_valid(true, true);) + clear_imp(m_p_head->m_p_parent); + m_size = 0; + initialize(); + _GLIBCXX_DEBUG_ONLY(debug_base::clear();) + _GLIBCXX_DEBUG_ONLY(assert_valid(true, true);) +} + +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/pat_trie_/rotate_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp new file mode 100644 index 000000000..c0809fa48 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp @@ -0,0 +1,150 @@ +// -*- 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*/, __gnu_pbds::null_node_update* /*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) +{ + p_update->operator()(& PB_DS_V2F(p_nd->m_value),(p_nd->m_p_left == NULL) ? + NULL : + & PB_DS_V2F(p_nd->m_p_left->m_value),(p_nd->m_p_right == NULL) ? + NULL : + & PB_DS_V2F(p_nd->m_p_right->m_value)); +} + +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*/, __gnu_pbds::null_node_update* /*p_update*/) +{ } + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp new file mode 100644 index 000000000..9779a4bcd --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp @@ -0,0 +1,254 @@ +// -*- 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_fn_imps.hpp + * Contains an implementation class for bin_search_tree_. + */ + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +split(const_key_reference r_key, PB_DS_CLASS_C_DEC& other) +{ + _GLIBCXX_DEBUG_ONLY(assert_valid();); + _GLIBCXX_DEBUG_ONLY(other.assert_valid();); + split_join_branch_bag bag; + leaf_pointer p_split_lf = split_prep(r_key, other, bag); + if (p_split_lf == NULL) + { + _GLIBCXX_DEBUG_ASSERT(bag.empty()); + _GLIBCXX_DEBUG_ONLY(assert_valid();) + _GLIBCXX_DEBUG_ONLY(other.assert_valid();) + return; + } + + _GLIBCXX_DEBUG_ASSERT(!bag.empty()); + other.clear(); + m_p_head->m_p_parent = rec_split(m_p_head->m_p_parent, + pref_begin(p_split_lf), + pref_end(p_split_lf), + other, + bag); + + m_p_head->m_p_parent->m_p_parent = m_p_head; + + other.m_p_head->m_p_max = m_p_head->m_p_max; + m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); + other.m_p_head->m_p_min = + other.leftmost_descendant(other.m_p_head->m_p_parent); + + other.m_size = std::distance(other.PB_DS_CLASS_C_DEC::begin(), + other.PB_DS_CLASS_C_DEC::end()); + m_size -= other.m_size; + _GLIBCXX_DEBUG_ONLY(assert_valid();); + _GLIBCXX_DEBUG_ONLY(other.assert_valid();); +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::leaf_pointer +PB_DS_CLASS_C_DEC:: +split_prep(const_key_reference r_key, PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag) +{ + _GLIBCXX_DEBUG_ASSERT(r_bag.empty()); + if (m_size == 0) + { + other.clear(); + _GLIBCXX_DEBUG_ONLY(assert_valid();); + _GLIBCXX_DEBUG_ONLY(other.assert_valid();); + return (NULL); + } + + if (synth_e_access_traits::cmp_keys(r_key, + PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_min)->value()))) + { + other.clear(); + value_swap(other); + _GLIBCXX_DEBUG_ONLY(assert_valid();); + _GLIBCXX_DEBUG_ONLY(other.assert_valid();); + return (NULL); + } + + if (!synth_e_access_traits::cmp_keys(r_key, + PB_DS_V2F(static_cast<const_leaf_pointer>(m_p_head->m_p_max)->value()))) + { + _GLIBCXX_DEBUG_ONLY(assert_valid();); + _GLIBCXX_DEBUG_ONLY(other.assert_valid();); + return (NULL); + } + + iterator it = lower_bound(r_key); + + if (!synth_e_access_traits::equal_keys(PB_DS_V2F(*it), r_key)) + --it; + + node_pointer p_nd = it.m_p_nd; + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_leaf_node_type); + leaf_pointer p_ret_l = static_cast<leaf_pointer>(p_nd); + while (p_nd->m_type != pat_trie_head_node_type) + { + r_bag.add_branch(); + p_nd = p_nd->m_p_parent; + } + _GLIBCXX_DEBUG_ONLY(debug_base::split(r_key,(synth_e_access_traits& )(*this), other);) + + return (p_ret_l); +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::node_pointer +PB_DS_CLASS_C_DEC:: +rec_split(node_pointer p_nd, const_e_iterator b_it, const_e_iterator e_it, PB_DS_CLASS_C_DEC& other, split_join_branch_bag& r_bag) +{ + if (p_nd->m_type == pat_trie_leaf_node_type) + { + _GLIBCXX_DEBUG_ASSERT(other.m_p_head->m_p_parent == NULL); + return (p_nd); + } + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == pat_trie_internal_node_type); + internal_node_pointer p_internal_nd = static_cast<internal_node_pointer>(p_nd); + + node_pointer p_child_ret = rec_split(p_internal_nd->get_child_node(b_it, e_it, this), b_it, e_it, other, r_bag); + + _GLIBCXX_DEBUG_ONLY(p_child_ret->assert_valid(this);) + p_internal_nd->replace_child(p_child_ret, b_it, e_it, this); + apply_update(p_internal_nd, (node_update* )this); + + typename internal_node::iterator child_it = + p_internal_nd->get_child_it(b_it, e_it, this); + + const size_type lhs_num_children = + std::distance(p_internal_nd->begin(), child_it) + 1; + + _GLIBCXX_DEBUG_ASSERT(lhs_num_children > 0); + + size_type rhs_num_children = + std::distance(p_internal_nd->begin(), p_internal_nd->end()) - + lhs_num_children; + + if (rhs_num_children == 0) + { + apply_update(p_internal_nd, (node_update* )this); + return (p_internal_nd); + } + + ++child_it; + other.split_insert_branch(p_internal_nd->get_e_ind(), + b_it, child_it, rhs_num_children, r_bag); + + child_it = p_internal_nd->get_child_it(b_it, e_it, this); + ++child_it; + while (rhs_num_children != 0) + { + child_it = p_internal_nd->remove_child(child_it); + --rhs_num_children; + } + + apply_update(p_internal_nd, (node_update* )this); + _GLIBCXX_DEBUG_ASSERT(std::distance(p_internal_nd->begin(), + p_internal_nd->end()) >= 1); + + if (std::distance(p_internal_nd->begin(), p_internal_nd->end()) > 1) + { + p_internal_nd->update_prefixes(this); + _GLIBCXX_DEBUG_ONLY(p_internal_nd->assert_valid(this);) + apply_update(p_internal_nd, (node_update* )this); + return (p_internal_nd); + } + + node_pointer p_ret =* p_internal_nd->begin(); + p_internal_nd->~internal_node(); + s_internal_node_allocator.deallocate(p_internal_nd, 1); + apply_update(p_ret, (node_update* )this); + return (p_ret); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +split_insert_branch(size_type e_ind, const_e_iterator b_it, typename internal_node::iterator child_b_it, size_type num_children, split_join_branch_bag& r_bag) +{ +#ifdef _GLIBCXX_DEBUG + if (m_p_head->m_p_parent != NULL) + m_p_head->m_p_parent->assert_valid(this); +#endif + + const size_type total_num_children =((m_p_head->m_p_parent == NULL)? 0 : 1) + num_children; + + if (total_num_children == 0) + { + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == NULL); + return; + } + + if (total_num_children == 1) + { + if (m_p_head->m_p_parent != NULL) + { + _GLIBCXX_DEBUG_ONLY(m_p_head->m_p_parent->assert_valid(this);) + return; + } + + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == NULL); + m_p_head->m_p_parent =* child_b_it; + m_p_head->m_p_parent->m_p_parent = m_p_head; + apply_update(m_p_head->m_p_parent, (node_update* )this); + _GLIBCXX_DEBUG_ONLY(m_p_head->m_p_parent->assert_valid(this);) + return; + } + + _GLIBCXX_DEBUG_ASSERT(total_num_children > 1); + internal_node_pointer p_new_root = r_bag.get_branch(); + new (p_new_root) internal_node(e_ind, b_it); + size_type num_inserted = 0; + while (num_inserted++ < num_children) + { + _GLIBCXX_DEBUG_ONLY((*child_b_it)->assert_valid(this);) + p_new_root->add_child(*child_b_it, pref_begin(*child_b_it), + pref_end(*child_b_it), this); + ++child_b_it; + } + + if (m_p_head->m_p_parent != NULL) + p_new_root->add_child(m_p_head->m_p_parent, + pref_begin(m_p_head->m_p_parent), + pref_end(m_p_head->m_p_parent), this); + + m_p_head->m_p_parent = p_new_root; + p_new_root->m_p_parent = m_p_head; + apply_update(m_p_head->m_p_parent, (node_update* )this); + _GLIBCXX_DEBUG_ONLY(m_p_head->m_p_parent->assert_valid(this);) +} diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp new file mode 100644 index 000000000..9cecae517 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp @@ -0,0 +1,93 @@ +// -*- 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 split_join_branch_bag.hpp + * Contains an implementation class for pat_trie_. + */ + +class split_join_branch_bag +{ +private: + typedef + std::list< + internal_node_pointer, + typename Allocator::template rebind< + internal_node_pointer>::other> + bag_t; + +public: + + void + add_branch() + { + internal_node_pointer p_nd = s_internal_node_allocator.allocate(1); + __try + { + m_bag.push_back(p_nd); + } + __catch(...) + { + s_internal_node_allocator.deallocate(p_nd, 1); + __throw_exception_again; + } + } + + internal_node_pointer + get_branch() + { + _GLIBCXX_DEBUG_ASSERT(!m_bag.empty()); + internal_node_pointer p_nd =* m_bag.begin(); + m_bag.pop_front(); + return p_nd; + } + + ~split_join_branch_bag() + { + while (!m_bag.empty()) + { + internal_node_pointer p_nd =* m_bag.begin(); + s_internal_node_allocator.deallocate(p_nd, 1); + m_bag.pop_front(); + } + } + + inline bool + empty() const + { return m_bag.empty(); } + +private: + bag_t m_bag; +}; diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp new file mode 100644 index 000000000..abf5f1185 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp @@ -0,0 +1,229 @@ +// -*- 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 synth_e_access_traits.hpp + * Contains an implementation class for a patricia tree. + */ + +#ifndef PB_DS_SYNTH_E_ACCESS_TRAITS_HPP +#define PB_DS_SYNTH_E_ACCESS_TRAITS_HPP + +#include <ext/pb_ds/detail/type_utils.hpp> + +namespace __gnu_pbds +{ + namespace detail + { + +#define PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC \ + template<typename Type_Traits, bool Set, class E_Access_Traits> + +#define PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC \ + synth_e_access_traits< \ + Type_Traits, \ + Set, \ + E_Access_Traits> + + template<typename Type_Traits, bool Set, class E_Access_Traits> + struct synth_e_access_traits : public E_Access_Traits + { + + private: + typedef E_Access_Traits base_type; + + typedef Type_Traits type_traits; + + typedef typename type_traits::const_key_reference const_key_reference; + + typedef typename type_traits::const_reference const_reference; + + public: + synth_e_access_traits(); + + synth_e_access_traits(const E_Access_Traits& r_traits); + + inline bool + equal_prefixes(typename base_type::const_iterator b_l, typename base_type::const_iterator e_l, typename base_type::const_iterator b_r, typename base_type::const_iterator e_r, bool compare_after = true) const; + + bool + equal_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const; + + bool + cmp_prefixes(typename base_type::const_iterator b_l, typename base_type::const_iterator e_l, typename base_type::const_iterator b_r, typename base_type::const_iterator e_r, bool compare_after = false) const; + + bool + cmp_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const; + + inline static const_key_reference + extract_key(const_reference r_val); + +#ifdef _GLIBCXX_DEBUG + bool + operator()(const_key_reference r_lhs, const_key_reference r_rhs); +#endif + + private: + inline static const_key_reference + extract_key(const_reference r_val, true_type); + + inline static const_key_reference + extract_key(const_reference r_val, false_type); + + private: + static integral_constant<int,Set> s_set_ind; + }; + + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + integral_constant<int,Set> + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::s_set_ind; + + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: + synth_e_access_traits() + { } + + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: + synth_e_access_traits(const E_Access_Traits& r_traits) : + E_Access_Traits(r_traits) + { } + + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + inline bool + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: + equal_prefixes(typename base_type::const_iterator b_l, typename base_type::const_iterator e_l, typename base_type::const_iterator b_r, typename base_type::const_iterator e_r, bool compare_after /*= false */) const + { + while (b_l != e_l) + { + if (b_r == e_r) + return (false); + if (base_type::e_pos(*b_l) != base_type::e_pos(*b_r)) + return (false); + ++b_l; + ++b_r; + } + return (!compare_after || b_r == e_r); + } + + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + bool + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: + equal_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const + { + return (equal_prefixes(base_type::begin(r_lhs_key), + base_type::end(r_lhs_key), + base_type::begin(r_rhs_key), + base_type::end(r_rhs_key), + true)); + } + + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + bool + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: + cmp_prefixes(typename base_type::const_iterator b_l, typename base_type::const_iterator e_l, typename base_type::const_iterator b_r, typename base_type::const_iterator e_r, bool compare_after /* = false*/) const + { + while (b_l != e_l) + { + if (b_r == e_r) + return (false); + const typename base_type::size_type l_pos = + base_type::e_pos(*b_l); + const typename base_type::size_type r_pos = + base_type::e_pos(*b_r); + if (l_pos != r_pos) + return (l_pos < r_pos); + ++b_l; + ++b_r; + } + + if (!compare_after) + return (false); + return (b_r != e_r); + } + + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + bool + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: + cmp_keys(const_key_reference r_lhs_key, const_key_reference r_rhs_key) const + { + return (cmp_prefixes(base_type::begin(r_lhs_key), + base_type::end(r_lhs_key), + base_type::begin(r_rhs_key), + base_type::end(r_rhs_key), + true)); + } + + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::const_key_reference + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: + extract_key(const_reference r_val) + { + return (extract_key(r_val, s_set_ind)); + } + + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::const_key_reference + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: + extract_key(const_reference r_val, true_type) + { + return (r_val); + } + + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + inline typename PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC::const_key_reference + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: + extract_key(const_reference r_val, false_type) + { + return (r_val.first); + } + +#ifdef _GLIBCXX_DEBUG + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + bool + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: + operator()(const_key_reference r_lhs, const_key_reference r_rhs) + { + return (cmp_keys(r_lhs, r_rhs)); + } +#endif + +#undef PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC +#undef PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC + + } // namespace detail +} // namespace __gnu_pbds + +#endif diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp new file mode 100644 index 000000000..e4b20943b --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp @@ -0,0 +1,113 @@ +// -*- 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 trace_fn_imps.hpp + * Contains an implementation class for pat_trie_. + */ + +#ifdef PB_DS_PAT_TRIE_TRACE_ + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +trace() const +{ + std::cerr << std::endl; + if (m_p_head->m_p_parent == NULL) + return; + trace_node(m_p_head->m_p_parent, 0); + std::cerr << std::endl; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +trace_node(const_node_pointer p_nd, size_type level) +{ + for (size_type i = 0; i < level; ++i) + std::cerr << ' '; + std::cerr << p_nd << " "; + std::cerr << ((p_nd->m_type == pat_trie_leaf_node_type) ? "l " : "i "); + + trace_node_metadata(p_nd, type_to_type<typename node::metadata_type>()); + typename e_access_traits::const_iterator el_it = pref_begin(p_nd); + while (el_it != pref_end(p_nd)) + { + std::cerr <<* el_it; + ++el_it; + } + + if (p_nd->m_type == pat_trie_leaf_node_type) + { + std::cerr << std::endl; + return; + } + + const_internal_node_pointer p_internal = + static_cast<const_internal_node_pointer>(p_nd); + + std::cerr << " " << + static_cast<unsigned long>(p_internal->get_e_ind()) << std::endl; + + const size_type num_children = std::distance(p_internal->begin(), + p_internal->end()); + + for (size_type child_i = 0; child_i < num_children; ++child_i) + { + typename internal_node::const_iterator child_it = + p_internal->begin(); + std::advance(child_it, num_children - child_i - 1); + trace_node(*child_it, level + 1); + } +} + +PB_DS_CLASS_T_DEC +template<typename Metadata_> +void +PB_DS_CLASS_C_DEC:: +trace_node_metadata(const_node_pointer p_nd, type_to_type<Metadata_>) +{ + std::cerr << "(" << static_cast<unsigned long>(p_nd->get_metadata()) << ") "; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +trace_node_metadata(const_node_pointer, type_to_type<null_node_metadata>) +{ } + +#endif + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp new file mode 100644 index 000000000..c8e7f587b --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp @@ -0,0 +1,350 @@ +// -*- C++ -*- + +// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. +// +// This file is part of the GNU ISO C++ Library. This library is free +// software; you can redistribute it and/or modify it under the terms +// of the GNU General Public License as published by the Free Software +// Foundation; either version 3, or (at your option) any later +// version. + +// This library is distributed in the hope that it will be useful, but +// WITHOUT ANY WARRANTY; without even the implied warranty of +// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU +// General Public License for more details. + +// Under Section 7 of GPL version 3, you are granted additional +// permissions described in the GCC Runtime Library Exception, version +// 3.1, as published by the Free Software Foundation. + +// You should have received a copy of the GNU General Public License and +// a copy of the GCC Runtime Library Exception along with this program; +// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see +// <http://www.gnu.org/licenses/>. + +// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. + +// Permission to use, copy, modify, sell, and distribute this software +// is hereby granted without fee, provided that the above copyright +// notice appears in all copies, and that both that copyright notice +// and this permission notice appear in supporting documentation. None +// of the above authors, nor IBM Haifa Research Laboratories, make any +// representation about the suitability of this software for any +// purpose. It is provided "as is" without express or implied +// warranty. + +/** + * @file traits.hpp + * Contains an implementation class for pat_trie_. + */ + +#ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP +#define PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP + +#include <ext/pb_ds/detail/pat_trie_/node_base.hpp> +#include <ext/pb_ds/detail/pat_trie_/head.hpp> +#include <ext/pb_ds/detail/pat_trie_/leaf.hpp> +#include <ext/pb_ds/detail/pat_trie_/internal_node.hpp> +#include <ext/pb_ds/detail/pat_trie_/point_iterators.hpp> +#include <ext/pb_ds/detail/pat_trie_/node_iterators.hpp> +#include <ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp> + +namespace __gnu_pbds +{ + namespace detail + { + + template<typename Key, + typename Mapped, + class E_Access_Traits, + template<typename Const_Node_Iterator, + class Node_Iterator, + class Cmp_Fn_, + class Allocator_> + class Node_Update, + class Allocator> + struct trie_traits< + Key, + Mapped, + E_Access_Traits, + Node_Update, + pat_trie_tag, + Allocator> + { + private: + typedef types_traits< Key, Mapped, Allocator, false> type_traits; + + public: + typedef + typename trie_node_metadata_selector< + Key, + Mapped, + E_Access_Traits, + Node_Update, + Allocator>::type + metadata_type; + + typedef E_Access_Traits e_access_traits; + + typedef + __gnu_pbds::detail::synth_e_access_traits< + type_traits, + false, + e_access_traits> + synth_e_access_traits; + + typedef + pat_trie_node_base< + type_traits, + synth_e_access_traits, + metadata_type, + Allocator> + node; + + typedef + pat_trie_leaf< + type_traits, + synth_e_access_traits, + metadata_type, + Allocator> + leaf; + + typedef + pat_trie_head< + type_traits, + synth_e_access_traits, + metadata_type, + Allocator> + head; + + typedef + pat_trie_internal_node< + type_traits, + synth_e_access_traits, + metadata_type, + Allocator> + internal_node; + + typedef + pat_trie_const_it_< + type_traits, + node, + leaf, + head, + internal_node, + true, + Allocator> + const_iterator; + + typedef + pat_trie_it_< + type_traits, + node, + leaf, + head, + internal_node, + true, + Allocator> + iterator; + + typedef + pat_trie_const_it_< + type_traits, + node, + leaf, + head, + internal_node, + false, + Allocator> + const_reverse_iterator; + + typedef + pat_trie_it_< + type_traits, + node, + leaf, + head, + internal_node, + false, + Allocator> + reverse_iterator; + + typedef + pat_trie_const_node_it_< + node, + leaf, + head, + internal_node, + const_iterator, + iterator, + synth_e_access_traits, + Allocator> + const_node_iterator; + + typedef + pat_trie_node_it_< + node, + leaf, + head, + internal_node, + const_iterator, + iterator, + synth_e_access_traits, + Allocator> + node_iterator; + + typedef + Node_Update< + const_node_iterator, + node_iterator, + E_Access_Traits, + Allocator> + node_update; + + typedef + __gnu_pbds::null_trie_node_update< + const_node_iterator, + node_iterator, + E_Access_Traits, + Allocator>* + null_node_update_pointer; + }; + + template<typename Key, + class E_Access_Traits, + template<typename Const_Node_Iterator, + class Node_Iterator, + class Cmp_Fn_, + class Allocator_> + class Node_Update, + class Allocator> + struct trie_traits< + Key, + null_mapped_type, + E_Access_Traits, + Node_Update, + pat_trie_tag, + Allocator> + { + private: + typedef + types_traits< + Key, + null_mapped_type, + Allocator, + false> + type_traits; + + public: + typedef + typename trie_node_metadata_selector< + Key, + null_mapped_type, + E_Access_Traits, + Node_Update, + Allocator>::type + metadata_type; + + typedef E_Access_Traits e_access_traits; + + typedef + __gnu_pbds::detail::synth_e_access_traits< + type_traits, + true, + e_access_traits> + synth_e_access_traits; + + typedef + pat_trie_node_base< + type_traits, + synth_e_access_traits, + metadata_type, + Allocator> + node; + + typedef + pat_trie_leaf< + type_traits, + synth_e_access_traits, + metadata_type, + Allocator> + leaf; + + typedef + pat_trie_head< + type_traits, + synth_e_access_traits, + metadata_type, + Allocator> + head; + + typedef + pat_trie_internal_node< + type_traits, + synth_e_access_traits, + metadata_type, + Allocator> + internal_node; + + typedef + pat_trie_const_it_< + type_traits, + node, + leaf, + head, + internal_node, + true, + Allocator> + const_iterator; + + typedef const_iterator iterator; + + typedef + pat_trie_const_it_< + type_traits, + node, + leaf, + head, + internal_node, + false, + Allocator> + const_reverse_iterator; + + typedef const_reverse_iterator reverse_iterator; + + typedef + pat_trie_const_node_it_< + node, + leaf, + head, + internal_node, + const_iterator, + iterator, + synth_e_access_traits, + Allocator> + const_node_iterator; + + typedef const_node_iterator node_iterator; + + typedef + Node_Update< + const_node_iterator, + node_iterator, + E_Access_Traits, + Allocator> + node_update; + + typedef + __gnu_pbds::null_trie_node_update< + const_node_iterator, + const_node_iterator, + E_Access_Traits, + Allocator>* + null_node_update_pointer; + }; + + } // namespace detail +} // namespace __gnu_pbds + +#endif // #ifndef PB_DS_PAT_TRIE_NODE_AND_IT_TRAITS_HPP + diff --git a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp new file mode 100644 index 000000000..6d275e731 --- /dev/null +++ b/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp @@ -0,0 +1,55 @@ +// -*- 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 update_fn_imps.hpp + * Contains an implementation class for pat_trie_. + */ + +PB_DS_CLASS_T_DEC +inline void +PB_DS_CLASS_C_DEC:: +apply_update(node_pointer /*p_nd*/, null_node_update_pointer) +{ } + +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, this), + const_node_iterator(NULL, this)); +} |