diff options
Diffstat (limited to 'gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_')
27 files changed, 0 insertions, 5700 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 deleted file mode 100644 index 15f349efb..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/child_iterator.hpp +++ /dev/null @@ -1,93 +0,0 @@ -// -*- 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 deleted file mode 100644 index 184b98652..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/cond_dtor_entry_dealtor.hpp +++ /dev/null @@ -1,79 +0,0 @@ -// -*- 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 deleted file mode 100644 index bc349cf2d..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/const_child_iterator.hpp +++ /dev/null @@ -1,111 +0,0 @@ -// -*- 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 deleted file mode 100644 index ca38f932a..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp +++ /dev/null @@ -1,214 +0,0 @@ -// -*- 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 deleted file mode 100644 index de7565788..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp +++ /dev/null @@ -1,117 +0,0 @@ -// -*- 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 deleted file mode 100644 index 90988184a..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp +++ /dev/null @@ -1,319 +0,0 @@ -// -*- 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 deleted file mode 100644 index 2552ead8b..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp +++ /dev/null @@ -1,269 +0,0 @@ -// -*- 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 deleted file mode 100644 index 0c7381294..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/head.hpp +++ /dev/null @@ -1,124 +0,0 @@ -// -*- 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 deleted file mode 100644 index 81d7096a9..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp +++ /dev/null @@ -1,58 +0,0 @@ -// -*- 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 deleted file mode 100644 index e6049743f..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp +++ /dev/null @@ -1,465 +0,0 @@ -// -*- 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 deleted file mode 100644 index bf2f42916..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/internal_node.hpp +++ /dev/null @@ -1,599 +0,0 @@ -// -*- 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 deleted file mode 100644 index 9902d96db..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp +++ /dev/null @@ -1,120 +0,0 @@ -// -*- 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 deleted file mode 100644 index 91cf14faa..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/leaf.hpp +++ /dev/null @@ -1,171 +0,0 @@ -// -*- 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 deleted file mode 100644 index bb13068bc..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_base.hpp +++ /dev/null @@ -1,128 +0,0 @@ -// -*- 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 deleted file mode 100644 index 37250091d..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp +++ /dev/null @@ -1,338 +0,0 @@ -// -*- 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 deleted file mode 100644 index 36272eda8..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_metadata_base.hpp +++ /dev/null @@ -1,86 +0,0 @@ -// -*- 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 deleted file mode 100644 index f6f420986..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp +++ /dev/null @@ -1,515 +0,0 @@ -// -*- 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 deleted file mode 100644 index cada9071c..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/point_iterators.hpp +++ /dev/null @@ -1,484 +0,0 @@ -// -*- 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 deleted file mode 100644 index 79bfe4283..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp +++ /dev/null @@ -1,63 +0,0 @@ -// -*- 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 deleted file mode 100644 index 52edf2506..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp +++ /dev/null @@ -1,103 +0,0 @@ -// -*- 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 deleted file mode 100644 index c0809fa48..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp +++ /dev/null @@ -1,150 +0,0 @@ -// -*- 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 deleted file mode 100644 index 9779a4bcd..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp +++ /dev/null @@ -1,254 +0,0 @@ -// -*- 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 deleted file mode 100644 index 9cecae517..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_join_branch_bag.hpp +++ /dev/null @@ -1,93 +0,0 @@ -// -*- 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 deleted file mode 100644 index abf5f1185..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/synth_e_access_traits.hpp +++ /dev/null @@ -1,229 +0,0 @@ -// -*- 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 deleted file mode 100644 index e4b20943b..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp +++ /dev/null @@ -1,113 +0,0 @@ -// -*- 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 deleted file mode 100644 index c8e7f587b..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp +++ /dev/null @@ -1,350 +0,0 @@ -// -*- 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 deleted file mode 100644 index 6d275e731..000000000 --- a/gcc-4.4.3/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp +++ /dev/null @@ -1,55 +0,0 @@ -// -*- 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)); -} |