diff options
Diffstat (limited to 'gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_')
17 files changed, 4618 insertions, 0 deletions
diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp new file mode 100644 index 0000000..c67674c --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/constructors_destructor_fn_imps.hpp @@ -0,0 +1,214 @@ + // -*- C++ -*- + +// Copyright (C) 2005-2014 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_/constructors_destructor_fn_imps.hpp + * Contains an implementation class for pat_trie. + */ + +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::inode_allocator +PB_DS_CLASS_C_DEC::s_inode_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_PAT_TRIE_NAME() : + m_p_head(s_head_allocator.allocate(1)), + m_size(0) +{ + initialize(); + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_PAT_TRIE_NAME(const access_traits& r_access_traits) : + synth_access_traits(r_access_traits), + m_p_head(s_head_allocator.allocate(1)), + m_size(0) +{ + initialize(); + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +PB_DS_CLASS_C_DEC:: +PB_DS_PAT_TRIE_NAME(const PB_DS_CLASS_C_DEC& other) : +#ifdef _GLIBCXX_DEBUG + debug_base(other), +#endif + synth_access_traits(other), + node_update(other), + m_p_head(s_head_allocator.allocate(1)), + m_size(0) +{ + initialize(); + m_size = other.m_size; + PB_DS_ASSERT_VALID(other) + if (other.m_p_head->m_p_parent == 0) + { + PB_DS_ASSERT_VALID((*this)) + 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; + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +swap(PB_DS_CLASS_C_DEC& other) +{ + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) + value_swap(other); + std::swap((access_traits& )(*this), (access_traits& )other); + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) +} + +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_PAT_TRIE_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 = 0; + 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(node_const_pointer p_ncp) +{ + _GLIBCXX_DEBUG_ASSERT(p_ncp != 0); + if (p_ncp->m_type == leaf_node) + { + leaf_const_pointer p_other_lf = static_cast<leaf_const_pointer>(p_ncp); + leaf_pointer p_new_lf = s_leaf_allocator.allocate(1); + cond_dealtor cond(p_new_lf); + new (p_new_lf) leaf(p_other_lf->value()); + apply_update(p_new_lf, (node_update*)this); + cond.set_no_action_dtor(); + return (p_new_lf); + } + + _GLIBCXX_DEBUG_ASSERT(p_ncp->m_type == i_node); + node_pointer a_p_children[inode::arr_size]; + size_type child_i = 0; + inode_const_pointer p_icp = static_cast<inode_const_pointer>(p_ncp); + + typename inode::const_iterator child_it = p_icp->begin(); + + inode_pointer p_ret; + __try + { + while (child_it != p_icp->end()) + { + a_p_children[child_i] = recursive_copy_node(*(child_it)); + child_i++; + child_it++; + } + p_ret = s_inode_allocator.allocate(1); + } + __catch(...) + { + while (child_i-- > 0) + clear_imp(a_p_children[child_i]); + __throw_exception_again; + } + + new (p_ret) inode(p_icp->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.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp new file mode 100644 index 0000000..f632531 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/debug_fn_imps.hpp @@ -0,0 +1,115 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/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 char* __file, int __line) const +{ + if (m_p_head->m_p_parent != 0) + m_p_head->m_p_parent->assert_valid(this, __file, __line); + assert_iterators(__file, __line); + assert_reverse_iterators(__file, __line); + if (m_p_head->m_p_parent == 0) + { + PB_DS_DEBUG_VERIFY(m_p_head->m_p_min == m_p_head); + PB_DS_DEBUG_VERIFY(m_p_head->m_p_max == m_p_head); + PB_DS_DEBUG_VERIFY(empty()); + return; + } + + PB_DS_DEBUG_VERIFY(m_p_head->m_p_min->m_type == leaf_node); + PB_DS_DEBUG_VERIFY(m_p_head->m_p_max->m_type == leaf_node); + PB_DS_DEBUG_VERIFY(!empty()); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_iterators(const char* __file, int __line) 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), __file, __line); + PB_DS_DEBUG_VERIFY(lower_bound(PB_DS_V2F(*it)) == it); + PB_DS_DEBUG_VERIFY(--upper_bound(PB_DS_V2F(*it)) == it); + } + PB_DS_DEBUG_VERIFY(calc_size == m_size); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +assert_reverse_iterators(const char* __file, int __line) const +{ + size_type calc_size = 0; + for (const_reverse_iterator it = rbegin(); it != rend(); ++it) + { + ++calc_size; + node_const_pointer p_nd = + const_cast<PB_DS_CLASS_C_DEC*>(this)->find_imp(PB_DS_V2F(*it)); + PB_DS_DEBUG_VERIFY(p_nd == it.m_p_nd); + } + PB_DS_DEBUG_VERIFY(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(node_const_pointer p_nd, const char* __file, int __line) +{ + if (p_nd == 0) + return (0); + if (p_nd->m_type == leaf_node) + return (1); + PB_DS_DEBUG_VERIFY(p_nd->m_type == i_node); + size_type ret = 0; + for (typename inode::const_iterator it = static_cast<inode_const_pointer>(p_nd)->begin(); + it != static_cast<inode_const_pointer>(p_nd)->end(); + ++it) + ret += recursive_count_leafs(*it, __file, __line); + return ret; +} + +#endif diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp new file mode 100644 index 0000000..48907ea --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/erase_fn_imps.hpp @@ -0,0 +1,315 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/erase_fn_imps.hpp + * Contains an implementation class for pat_trie. + */ + +PB_DS_CLASS_T_DEC +inline bool +PB_DS_CLASS_C_DEC:: +erase(key_const_reference r_key) +{ + node_pointer p_nd = find_imp(r_key); + if (p_nd == 0 || p_nd->m_type == i_node) + { + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + return false; + } + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == leaf_node); + if (!synth_access_traits::equal_keys(PB_DS_V2F(reinterpret_cast<leaf_pointer>(p_nd)->value()), r_key)) + { + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + return false; + } + + PB_DS_CHECK_KEY_EXISTS(r_key) + erase_leaf(static_cast<leaf_pointer>(p_nd)); + PB_DS_ASSERT_VALID((*this)) + return true; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +erase_fixup(inode_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 == i_node); + node_pointer p_new_child = *p_nd->begin(); + + typedef inode_pointer inode_ptr; + inode_ptr p_internal = static_cast<inode_ptr>(p_parent); + p_internal->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->~inode(); + s_inode_allocator.deallocate(p_nd, 1); + + if (p_parent == m_p_head) + return; + + _GLIBCXX_DEBUG_ASSERT(p_parent->m_type == i_node); + p_nd = static_cast<inode_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); + PB_DS_ASSERT_NODE_VALID(p_nd) + if (p_nd->m_p_parent->m_type == head_node) + return; + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_p_parent->m_type == i_node); + + p_nd = static_cast<inode_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(debug_base::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() +{ + if (!empty()) + { + clear_imp(m_p_head->m_p_parent); + m_size = 0; + initialize(); + _GLIBCXX_DEBUG_ONLY(debug_base::clear();) + PB_DS_ASSERT_VALID((*this)) + } +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +clear_imp(node_pointer p_nd) +{ + if (p_nd->m_type == i_node) + { + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); + for (typename inode::iterator it = + static_cast<inode_pointer>(p_nd)->begin(); + it != static_cast<inode_pointer>(p_nd)->end(); + ++it) + { + node_pointer p_child =* it; + clear_imp(p_child); + } + s_inode_allocator.deallocate(static_cast<inode_pointer>(p_nd), 1); + return; + } + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == leaf_node); + 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) +{ + PB_DS_ASSERT_VALID((*this)) + + if (it == end()) + return it; + + const_iterator ret_it = it; + ++ret_it; + _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == leaf_node); + erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); + PB_DS_ASSERT_VALID((*this)) + 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) +{ + PB_DS_ASSERT_VALID((*this)) + + if (it == end()) + return it; + iterator ret_it = it; + ++ret_it; + _GLIBCXX_DEBUG_ASSERT(it.m_p_nd->m_type == leaf_node); + erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); + PB_DS_ASSERT_VALID((*this)) + 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) +{ + PB_DS_ASSERT_VALID((*this)) + + 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 == leaf_node); + erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); + PB_DS_ASSERT_VALID((*this)) + 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) +{ + PB_DS_ASSERT_VALID((*this)) + + 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 == leaf_node); + erase_leaf(static_cast<leaf_pointer>(it.m_p_nd)); + PB_DS_ASSERT_VALID((*this)) + 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; + PB_DS_ASSERT_VALID((*this)) + + iterator it = begin(); + while (it != end()) + { + PB_DS_ASSERT_VALID((*this)) + if (pred(*it)) + { + ++num_ersd; + it = erase(it); + } + else + ++it; + } + + PB_DS_ASSERT_VALID((*this)) + 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 == head_node) + { + _GLIBCXX_DEBUG_ASSERT(size() == 1); + clear(); + return; + } + + _GLIBCXX_DEBUG_ASSERT(size() > 1); + _GLIBCXX_DEBUG_ASSERT(p_l->m_p_parent->m_type == i_node); + + inode_pointer p_parent = static_cast<inode_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<leaf_const_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<leaf_const_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.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp new file mode 100644 index 0000000..a5ca850 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/find_fn_imps.hpp @@ -0,0 +1,269 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/find_fn_imps.hpp + * Contains an implementation class for pat_trie. + */ + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_iterator +PB_DS_CLASS_C_DEC:: +find(key_const_reference r_key) +{ + PB_DS_ASSERT_VALID((*this)) + node_pointer p_nd = find_imp(r_key); + + if (p_nd == 0 || p_nd->m_type != leaf_node) + { + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + return end(); + } + + if (synth_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_nd)->value()), r_key)) + { + PB_DS_CHECK_KEY_EXISTS(r_key) + return iterator(p_nd); + } + + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + return end(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_const_iterator +PB_DS_CLASS_C_DEC:: +find(key_const_reference r_key) const +{ + PB_DS_ASSERT_VALID((*this)) + + node_const_pointer p_nd = const_cast<PB_DS_CLASS_C_DEC* >(this)->find_imp(r_key); + + if (p_nd == 0 || p_nd->m_type != leaf_node) + { + PB_DS_CHECK_KEY_DOES_NOT_EXIST(r_key) + return end(); + } + + if (synth_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(p_nd)->value()), r_key)) + { + PB_DS_CHECK_KEY_EXISTS(r_key) + return const_iterator(const_cast<node_pointer>(p_nd)); + } + + PB_DS_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(key_const_reference r_key) +{ + if (empty()) + return 0; + + typename synth_access_traits::const_iterator b_it = + synth_access_traits::begin(r_key); + typename synth_access_traits::const_iterator e_it = + synth_access_traits::end(r_key); + + node_pointer p_nd = m_p_head->m_p_parent; + _GLIBCXX_DEBUG_ASSERT(p_nd != 0); + + while (p_nd->m_type != leaf_node) + { + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); + node_pointer p_next_nd = static_cast<inode_pointer>(p_nd)->get_child_node(b_it, e_it, this); + + if (p_next_nd == 0) + 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(key_const_reference r_key) +{ + if (empty()) + return (m_p_head); + + node_pointer p_nd = m_p_head->m_p_parent; + _GLIBCXX_DEBUG_ASSERT(p_nd != 0); + + typename PB_DS_CLASS_C_DEC::a_const_iterator b_it = + synth_access_traits::begin(r_key); + + typename PB_DS_CLASS_C_DEC::a_const_iterator e_it = + synth_access_traits::end(r_key); + + size_type checked_ind = 0; + while (true) + { + if (p_nd->m_type == leaf_node) + { + if (!synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_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 == i_node); + const size_type new_checked_ind = + static_cast<inode_pointer>(p_nd)->get_e_ind(); + + p_nd = + static_cast<inode_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(key_const_reference r_key) +{ return point_iterator(lower_bound_imp(r_key)); } + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::point_const_iterator +PB_DS_CLASS_C_DEC:: +lower_bound(key_const_reference r_key) const +{ + return point_const_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(key_const_reference r_key) +{ + point_iterator l_bound_it = lower_bound(r_key); + + _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || + !synth_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), + r_key)); + + if (l_bound_it == end() || + synth_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::point_const_iterator +PB_DS_CLASS_C_DEC:: +upper_bound(key_const_reference r_key) const +{ + point_const_iterator l_bound_it = lower_bound(r_key); + + _GLIBCXX_DEBUG_ASSERT(l_bound_it == end() || + !synth_access_traits::cmp_keys(PB_DS_V2F(*l_bound_it), + r_key)); + + if (l_bound_it == end() || + synth_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::a_const_iterator +PB_DS_CLASS_C_DEC:: +pref_begin(node_const_pointer p_nd) +{ + if (p_nd->m_type == leaf_node) + return (synth_access_traits::begin(PB_DS_V2F(static_cast<leaf_const_pointer>(p_nd)->value()))); + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); + return static_cast<inode_const_pointer>(p_nd)->pref_b_it(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::a_const_iterator +PB_DS_CLASS_C_DEC:: +pref_end(node_const_pointer p_nd) +{ + if (p_nd->m_type == leaf_node) + return (synth_access_traits::end(PB_DS_V2F(static_cast<leaf_const_pointer>(p_nd)->value()))); + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); + return static_cast<inode_const_pointer>(p_nd)->pref_e_it(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::leaf_const_pointer +PB_DS_CLASS_C_DEC:: +leftmost_descendant(node_const_pointer p_nd) +{ + if (p_nd->m_type == leaf_node) + return static_cast<leaf_const_pointer>(p_nd); + return static_cast<inode_const_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 == leaf_node) + return static_cast<leaf_pointer>(p_nd); + return static_cast<inode_pointer>(p_nd)->leftmost_descendant(); +} + +PB_DS_CLASS_T_DEC +inline typename PB_DS_CLASS_C_DEC::leaf_const_pointer +PB_DS_CLASS_C_DEC:: +rightmost_descendant(node_const_pointer p_nd) +{ + if (p_nd->m_type == leaf_node) + return static_cast<leaf_const_pointer>(p_nd); + return static_cast<inode_const_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 == leaf_node) + return static_cast<leaf_pointer>(p_nd); + return static_cast<inode_pointer>(p_nd)->rightmost_descendant(); +} + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp new file mode 100644 index 0000000..505b054 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/info_fn_imps.hpp @@ -0,0 +1,58 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/info_fn_imps.hpp + * Contains an implementation class for pat_trie. + */ + +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_inode_allocator.max_size(); } + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp new file mode 100644 index 0000000..e22b81c --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/insert_join_fn_imps.hpp @@ -0,0 +1,472 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/insert_join_fn_imps.hpp + * Contains an implementation class for pat_trie. + */ + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +join(PB_DS_CLASS_C_DEC& other) +{ + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) + branch_bag bag; + if (!join_prep(other, bag)) + { + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) + 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(); + PB_DS_ASSERT_VALID(other) + 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); + PB_DS_ASSERT_VALID((*this)) +} + +PB_DS_CLASS_T_DEC +bool +PB_DS_CLASS_C_DEC:: +join_prep(PB_DS_CLASS_C_DEC& other, branch_bag& r_bag) +{ + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) + if (other.m_size == 0) + return false; + + if (m_size == 0) + { + value_swap(other); + return false; + } + + const bool greater = + synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value()), + PB_DS_V2F(static_cast<leaf_const_pointer>(other.m_p_head->m_p_min)->value())); + + const bool lesser = + synth_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_pointer>(other.m_p_head->m_p_max)->value()), + PB_DS_V2F(static_cast<leaf_const_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, false);) + return true; +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rec_join_prep(node_const_pointer p_l, node_const_pointer p_r, + branch_bag& r_bag) +{ + if (p_l->m_type == leaf_node) + { + if (p_r->m_type == leaf_node) + { + rec_join_prep(static_cast<leaf_const_pointer>(p_l), + static_cast<leaf_const_pointer>(p_r), r_bag); + return; + } + + _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node); + rec_join_prep(static_cast<leaf_const_pointer>(p_l), + static_cast<inode_const_pointer>(p_r), r_bag); + return; + } + + _GLIBCXX_DEBUG_ASSERT(p_l->m_type == i_node); + if (p_r->m_type == leaf_node) + { + rec_join_prep(static_cast<inode_const_pointer>(p_l), + static_cast<leaf_const_pointer>(p_r), r_bag); + return; + } + + _GLIBCXX_DEBUG_ASSERT(p_r->m_type == i_node); + + rec_join_prep(static_cast<inode_const_pointer>(p_l), + static_cast<inode_const_pointer>(p_r), r_bag); +} + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rec_join_prep(leaf_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/, + branch_bag& r_bag) +{ r_bag.add_branch(); } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rec_join_prep(leaf_const_pointer /*p_l*/, inode_const_pointer /*p_r*/, + branch_bag& r_bag) +{ r_bag.add_branch(); } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rec_join_prep(inode_const_pointer /*p_l*/, leaf_const_pointer /*p_r*/, + branch_bag& r_bag) +{ r_bag.add_branch(); } + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +rec_join_prep(inode_const_pointer p_l, inode_const_pointer p_r, + branch_bag& r_bag) +{ + if (p_l->get_e_ind() == p_r->get_e_ind() && + synth_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 inode::const_iterator it = p_r->begin(); + it != p_r->end(); ++ it) + { + node_const_pointer p_l_join_child = p_l->get_join_child(*it, this); + if (p_l_join_child != 0) + 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)) + { + node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this); + if (p_r_join_child != 0) + 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)) + { + node_const_pointer p_r_join_child = p_r->get_join_child(p_l, this); + if (p_r_join_child != 0) + 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, + branch_bag& r_bag) +{ + _GLIBCXX_DEBUG_ASSERT(p_r != 0); + if (p_l == 0) + { + apply_update(p_r, (node_update*)this); + return (p_r); + } + + if (p_l->m_type == leaf_node) + { + if (p_r->m_type == leaf_node) + { + 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 == i_node); + node_pointer p_ret = rec_join(static_cast<leaf_pointer>(p_l), + static_cast<inode_pointer>(p_r), + checked_ind, r_bag); + apply_update(p_ret, (node_update*)this); + return p_ret; + } + + _GLIBCXX_DEBUG_ASSERT(p_l->m_type == i_node); + if (p_r->m_type == leaf_node) + { + node_pointer p_ret = rec_join(static_cast<inode_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 == i_node); + node_pointer p_ret = rec_join(static_cast<inode_pointer>(p_l), + static_cast<inode_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, branch_bag& r_bag) +{ + _GLIBCXX_DEBUG_ASSERT(p_r != 0); + if (p_l == 0) + return (p_r); + node_pointer p_ret = insert_branch(p_l, p_r, r_bag); + _GLIBCXX_DEBUG_ASSERT(PB_DS_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, inode_pointer p_r, size_type checked_ind, + branch_bag& r_bag) +{ +#ifdef _GLIBCXX_DEBUG + const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l); + const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r); +#endif + + _GLIBCXX_DEBUG_ASSERT(p_r != 0); + node_pointer p_ret = rec_join(p_r, p_l, checked_ind, r_bag); + _GLIBCXX_DEBUG_ASSERT(PB_DS_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(inode_pointer p_l, leaf_pointer p_r, size_type checked_ind, branch_bag& r_bag) +{ + _GLIBCXX_DEBUG_ASSERT(p_l != 0); + _GLIBCXX_DEBUG_ASSERT(p_r != 0); + +#ifdef _GLIBCXX_DEBUG + const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l); + const size_type rhs_leafs = PB_DS_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); + PB_DS_ASSERT_NODE_VALID(p_ret) + _GLIBCXX_DEBUG_ASSERT(PB_DS_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); + } + + PB_DS_ASSERT_NODE_VALID(p_l) + _GLIBCXX_DEBUG_ASSERT(PB_DS_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(inode_pointer p_l, inode_pointer p_r, + branch_bag& r_bag) +{ + _GLIBCXX_DEBUG_ASSERT(p_l != 0); + _GLIBCXX_DEBUG_ASSERT(p_r != 0); + +#ifdef _GLIBCXX_DEBUG + const size_type lhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_l); + const size_type rhs_leafs = PB_DS_RECURSIVE_COUNT_LEAFS(p_r); +#endif + + if (p_l->get_e_ind() == p_r->get_e_ind() && + synth_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 inode::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->~inode(); + s_inode_allocator.deallocate(p_r, 1); + PB_DS_ASSERT_NODE_VALID(p_l) + _GLIBCXX_DEBUG_ASSERT(PB_DS_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); + PB_DS_ASSERT_NODE_VALID(p_l) + 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); + + PB_DS_ASSERT_NODE_VALID(p_r) + _GLIBCXX_DEBUG_ASSERT(PB_DS_RECURSIVE_COUNT_LEAFS(p_r) == lhs_leafs + rhs_leafs); + return p_r; + } + + node_pointer p_ret = insert_branch(p_l, p_r, r_bag); + PB_DS_ASSERT_NODE_VALID(p_ret) + _GLIBCXX_DEBUG_ASSERT(PB_DS_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 != 0 && p_lf->m_type == leaf_node && + synth_access_traits::equal_keys(PB_DS_V2F(static_cast<leaf_pointer>(p_lf)->value()), PB_DS_V2F(r_val))) + { + PB_DS_CHECK_KEY_EXISTS(PB_DS_V2F(r_val)) + PB_DS_ASSERT_VALID((*this)) + return std::make_pair(iterator(p_lf), false); + } + + PB_DS_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(); + 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));) + PB_DS_ASSERT_VALID((*this)) + 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 access_traits::const_iterator b_l, + typename access_traits::const_iterator e_l, + typename access_traits::const_iterator b_r, + typename 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 (access_traits::e_pos(*b_l) != 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::inode_pointer +PB_DS_CLASS_C_DEC:: +insert_branch(node_pointer p_l, node_pointer p_r, branch_bag& r_bag) +{ + typename synth_access_traits::const_iterator left_b_it = pref_begin(p_l); + typename synth_access_traits::const_iterator left_e_it = pref_end(p_l); + typename synth_access_traits::const_iterator right_b_it = pref_begin(p_r); + typename synth_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); + + inode_pointer p_new_nd = r_bag.get_branch(); + new (p_new_nd) inode(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; + PB_DS_ASSERT_NODE_VALID(p_new_nd) + 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_access_traits::cmp_keys(PB_DS_V2F(p_new_lf->value()), + PB_DS_V2F(static_cast<leaf_const_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_access_traits::cmp_keys(PB_DS_V2F(static_cast<leaf_const_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.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp new file mode 100644 index 0000000..97de417 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/iterators_fn_imps.hpp @@ -0,0 +1,120 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/iterators_fn_imps.hpp + * Contains an implementation class for pat_trie. + */ + +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::node_const_iterator +PB_DS_CLASS_C_DEC:: +node_begin() const +{ return node_const_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::node_const_iterator +PB_DS_CLASS_C_DEC:: +node_end() const +{ return node_const_iterator(0, 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(0, this); } + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp new file mode 100644 index 0000000..7a498bf --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_.hpp @@ -0,0 +1,596 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/pat_trie_.hpp + * Contains an implementation class for a patricia tree. + */ + +#include <iterator> +#include <utility> +#include <algorithm> +#include <functional> +#include <assert.h> +#include <list> +#include <ext/pb_ds/exception.hpp> +#include <ext/pb_ds/tag_and_trait.hpp> +#include <ext/pb_ds/tree_policy.hpp> +#include <ext/pb_ds/detail/cond_dealtor.hpp> +#include <ext/pb_ds/detail/type_utils.hpp> +#include <ext/pb_ds/detail/types_traits.hpp> +#include <ext/pb_ds/detail/eq_fn/eq_by_less.hpp> +#include <ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp> +#include <ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp> +#ifdef _GLIBCXX_DEBUG +#include <ext/pb_ds/detail/debug_map_base.hpp> +#endif +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { +#ifdef PB_DS_DATA_TRUE_INDICATOR +#define PB_DS_PAT_TRIE_NAME pat_trie_map +#endif + +#ifdef PB_DS_DATA_FALSE_INDICATOR +#define PB_DS_PAT_TRIE_NAME pat_trie_set +#endif + +#define PB_DS_CLASS_T_DEC \ + template<typename Key, typename Mapped, typename Node_And_It_Traits, \ + typename _Alloc> + +#define PB_DS_CLASS_C_DEC \ + PB_DS_PAT_TRIE_NAME<Key, Mapped, Node_And_It_Traits, _Alloc> + +#define PB_DS_PAT_TRIE_TRAITS_BASE \ + types_traits<Key, Mapped, _Alloc, false> + +#ifdef _GLIBCXX_DEBUG +#define PB_DS_DEBUG_MAP_BASE_C_DEC \ + debug_map_base<Key, eq_by_less<Key, std::less<Key> >, \ + typename _Alloc::template rebind<Key>::other::const_reference> +#endif + + + /** + * @brief PATRICIA trie. + * @ingroup branch-detail + * + * 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 + */ + template<typename Key, typename Mapped, typename Node_And_It_Traits, + typename _Alloc> + class PB_DS_PAT_TRIE_NAME : +#ifdef _GLIBCXX_DEBUG + public PB_DS_DEBUG_MAP_BASE_C_DEC, +#endif + public Node_And_It_Traits::synth_access_traits, + public Node_And_It_Traits::node_update, + public PB_DS_PAT_TRIE_TRAITS_BASE, + public pat_trie_base + { + private: + typedef pat_trie_base base_type; + typedef PB_DS_PAT_TRIE_TRAITS_BASE traits_base; + typedef Node_And_It_Traits traits_type; + + typedef typename traits_type::synth_access_traits synth_access_traits; + typedef typename synth_access_traits::const_iterator a_const_iterator; + + typedef typename traits_type::node node; + typedef typename _Alloc::template rebind<node> __rebind_n; + typedef typename __rebind_n::other::const_pointer node_const_pointer; + typedef typename __rebind_n::other::pointer node_pointer; + + typedef typename traits_type::head head; + typedef typename _Alloc::template rebind<head> __rebind_h; + typedef typename __rebind_h::other head_allocator; + typedef typename head_allocator::pointer head_pointer; + + typedef typename traits_type::leaf leaf; + typedef typename _Alloc::template rebind<leaf> __rebind_l; + typedef typename __rebind_l::other leaf_allocator; + typedef typename leaf_allocator::pointer leaf_pointer; + typedef typename leaf_allocator::const_pointer leaf_const_pointer; + + typedef typename traits_type::inode inode; + typedef typename inode::iterator inode_iterator; + typedef typename _Alloc::template rebind<inode> __rebind_in; + typedef typename __rebind_in::other __rebind_ina; + typedef typename __rebind_in::other inode_allocator; + typedef typename __rebind_ina::pointer inode_pointer; + typedef typename __rebind_ina::const_pointer inode_const_pointer; + + + /// Conditional deallocator. + class cond_dealtor + { + protected: + leaf_pointer m_p_nd; + bool m_no_action_dtor; + bool m_call_destructor; + + public: + cond_dealtor(leaf_pointer p_nd) + : m_p_nd(p_nd), m_no_action_dtor(false), m_call_destructor(false) + { } + + void + set_no_action_dtor() + { m_no_action_dtor = true; } + + void + set_call_destructor() + { m_call_destructor = true; } + + ~cond_dealtor() + { + if (m_no_action_dtor) + return; + + if (m_call_destructor) + m_p_nd->~leaf(); + + s_leaf_allocator.deallocate(m_p_nd, 1); + } + }; + + + /// Branch bag, for split-join. + class branch_bag + { + private: + typedef inode_pointer __inp; + typedef typename _Alloc::template rebind<__inp>::other __rebind_inp; + +#ifdef _GLIBCXX_DEBUG + typedef std::_GLIBCXX_STD_C::list<__inp, __rebind_inp> bag_type; +#else + typedef std::list<__inp, __rebind_inp> bag_type; +#endif + + bag_type m_bag; + public: + void + add_branch() + { + inode_pointer p_nd = s_inode_allocator.allocate(1); + __try + { + m_bag.push_back(p_nd); + } + __catch(...) + { + s_inode_allocator.deallocate(p_nd, 1); + __throw_exception_again; + } + } + + inode_pointer + get_branch() + { + _GLIBCXX_DEBUG_ASSERT(!m_bag.empty()); + inode_pointer p_nd = *m_bag.begin(); + m_bag.pop_front(); + return p_nd; + } + + ~branch_bag() + { + while (!m_bag.empty()) + { + inode_pointer p_nd = *m_bag.begin(); + s_inode_allocator.deallocate(p_nd, 1); + m_bag.pop_front(); + } + } + + inline bool + empty() const + { return m_bag.empty(); } + }; + +#ifdef _GLIBCXX_DEBUG + typedef PB_DS_DEBUG_MAP_BASE_C_DEC debug_base; +#endif + + typedef typename traits_type::null_node_update_pointer null_node_update_pointer; + + public: + typedef pat_trie_tag container_category; + typedef _Alloc allocator_type; + typedef typename _Alloc::size_type size_type; + typedef typename _Alloc::difference_type difference_type; + + typedef typename traits_base::key_type key_type; + typedef typename traits_base::key_pointer key_pointer; + typedef typename traits_base::key_const_pointer key_const_pointer; + typedef typename traits_base::key_reference key_reference; + typedef typename traits_base::key_const_reference key_const_reference; + typedef typename traits_base::mapped_type mapped_type; + typedef typename traits_base::mapped_pointer mapped_pointer; + typedef typename traits_base::mapped_const_pointer mapped_const_pointer; + typedef typename traits_base::mapped_reference mapped_reference; + typedef typename traits_base::mapped_const_reference mapped_const_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 traits_type::access_traits access_traits; + typedef typename traits_type::const_iterator point_const_iterator; + typedef typename traits_type::iterator point_iterator; + typedef point_const_iterator const_iterator; + typedef point_iterator iterator; + + typedef typename traits_type::reverse_iterator reverse_iterator; + typedef typename traits_type::const_reverse_iterator const_reverse_iterator; + typedef typename traits_type::node_const_iterator node_const_iterator; + typedef typename traits_type::node_iterator node_iterator; + typedef typename traits_type::node_update node_update; + + PB_DS_PAT_TRIE_NAME(); + + PB_DS_PAT_TRIE_NAME(const access_traits&); + + PB_DS_PAT_TRIE_NAME(const PB_DS_CLASS_C_DEC&); + + void + swap(PB_DS_CLASS_C_DEC&); + + ~PB_DS_PAT_TRIE_NAME(); + + inline bool + empty() const; + + inline size_type + size() const; + + inline size_type + max_size() const; + + access_traits& + get_access_traits(); + + const access_traits& + get_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[](key_const_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_type; +#endif + } + + inline point_iterator + find(key_const_reference); + + inline point_const_iterator + find(key_const_reference) const; + + inline point_iterator + lower_bound(key_const_reference); + + inline point_const_iterator + lower_bound(key_const_reference) const; + + inline point_iterator + upper_bound(key_const_reference); + + inline point_const_iterator + upper_bound(key_const_reference) const; + + void + clear(); + + inline bool + erase(key_const_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(key_const_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; + + /// Returns a const node_iterator corresponding to the node at the + /// root of the tree. + inline node_const_iterator + node_begin() const; + + /// Returns a node_iterator corresponding to the node at the + /// root of the tree. + inline node_iterator + node_begin(); + + /// Returns a const node_iterator corresponding to a node just + /// after a leaf of the tree. + inline node_const_iterator + node_end() const; + + /// Returns a node_iterator corresponding to a node just + /// after a leaf of the tree. + 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(node_const_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&, branch_bag&); + + void + rec_join_prep(node_const_pointer, node_const_pointer, branch_bag&); + + void + rec_join_prep(leaf_const_pointer, leaf_const_pointer, branch_bag&); + + void + rec_join_prep(leaf_const_pointer, inode_const_pointer, branch_bag&); + + void + rec_join_prep(inode_const_pointer, leaf_const_pointer, branch_bag&); + + void + rec_join_prep(inode_const_pointer, inode_const_pointer, branch_bag&); + + node_pointer + rec_join(node_pointer, node_pointer, size_type, branch_bag&); + + node_pointer + rec_join(leaf_pointer, leaf_pointer, branch_bag&); + + node_pointer + rec_join(leaf_pointer, inode_pointer, size_type, branch_bag&); + + node_pointer + rec_join(inode_pointer, leaf_pointer, size_type, branch_bag&); + + node_pointer + rec_join(inode_pointer, inode_pointer, branch_bag&); + + size_type + keys_diff_ind(typename access_traits::const_iterator, + typename access_traits::const_iterator, + typename access_traits::const_iterator, + typename access_traits::const_iterator); + + inode_pointer + insert_branch(node_pointer, node_pointer, 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(inode_pointer); + + void + update_min_max_for_erased_leaf(leaf_pointer); + + static inline a_const_iterator + pref_begin(node_const_pointer); + + static inline a_const_iterator + pref_end(node_const_pointer); + + inline node_pointer + find_imp(key_const_reference); + + inline node_pointer + lower_bound_imp(key_const_reference); + + inline node_pointer + upper_bound_imp(key_const_reference); + + inline static leaf_const_pointer + leftmost_descendant(node_const_pointer); + + inline static leaf_pointer + leftmost_descendant(node_pointer); + + inline static leaf_const_pointer + rightmost_descendant(node_const_pointer); + + inline static leaf_pointer + rightmost_descendant(node_pointer); + +#ifdef _GLIBCXX_DEBUG + void + assert_valid(const char*, int) const; + + void + assert_iterators(const char*, int) const; + + void + assert_reverse_iterators(const char*, int) const; + + static size_type + recursive_count_leafs(node_const_pointer, const char*, int); +#endif + +#ifdef PB_DS_PAT_TRIE_TRACE_ + static void + trace_node(node_const_pointer, size_type); + + template<typename Metadata_> + static void + trace_node_metadata(node_const_pointer, type_to_type<Metadata_>); + + static void + trace_node_metadata(node_const_pointer, type_to_type<null_type>); +#endif + + leaf_pointer + split_prep(key_const_reference, PB_DS_CLASS_C_DEC&, branch_bag&); + + node_pointer + rec_split(node_pointer, a_const_iterator, a_const_iterator, + PB_DS_CLASS_C_DEC&, branch_bag&); + + void + split_insert_branch(size_type, a_const_iterator, inode_iterator, + size_type, branch_bag&); + + static head_allocator s_head_allocator; + static inode_allocator s_inode_allocator; + static leaf_allocator s_leaf_allocator; + + head_pointer m_p_head; + size_type m_size; + }; + +#define PB_DS_ASSERT_NODE_VALID(X) \ + _GLIBCXX_DEBUG_ONLY(X->assert_valid(this, __FILE__, __LINE__);) + +#define PB_DS_RECURSIVE_COUNT_LEAFS(X) \ + recursive_count_leafs(X, __FILE__, __LINE__) + +#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_RECURSIVE_COUNT_LEAFS +#undef PB_DS_ASSERT_NODE_VALID +#undef PB_DS_CLASS_C_DEC +#undef PB_DS_CLASS_T_DEC +#undef PB_DS_PAT_TRIE_NAME +#undef PB_DS_PAT_TRIE_TRAITS_BASE +#undef PB_DS_DEBUG_MAP_BASE_C_DEC + } // namespace detail +} // namespace __gnu_pbds diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp new file mode 100644 index 0000000..c14b1bc --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/pat_trie_base.hpp @@ -0,0 +1,1361 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/pat_trie_base.hpp + * Contains the base class for a patricia tree. + */ + +#ifndef PB_DS_PAT_TRIE_BASE +#define PB_DS_PAT_TRIE_BASE + +#include <debug/debug.h> + +namespace __gnu_pbds +{ + namespace detail + { + /// Base type for PATRICIA trees. + struct pat_trie_base + { + /** + * @brief Three types of nodes. + * + * i_node is used by _Inode, leaf_node by _Leaf, and head_node by _Head. + */ + enum node_type + { + i_node, + leaf_node, + head_node + }; + + /// Metadata base primary template. + template<typename Metadata, typename _Alloc> + struct _Metadata + { + typedef Metadata metadata_type; + typedef _Alloc allocator_type; + typedef typename _Alloc::template rebind<Metadata> __rebind_m; + typedef typename __rebind_m::other::const_reference const_reference; + + const_reference + get_metadata() const + { return m_metadata; } + + metadata_type m_metadata; + }; + + /// Specialization for null metadata. + template<typename _Alloc> + struct _Metadata<null_type, _Alloc> + { + typedef null_type metadata_type; + typedef _Alloc allocator_type; + }; + + + /// Node base. + template<typename _ATraits, typename Metadata> + struct _Node_base + : public Metadata + { + private: + typedef typename Metadata::allocator_type _Alloc; + + public: + typedef _Alloc allocator_type; + typedef _ATraits access_traits; + typedef typename _ATraits::type_traits type_traits; + typedef typename _Alloc::template rebind<_Node_base> __rebind_n; + typedef typename __rebind_n::other::pointer node_pointer; + + node_pointer m_p_parent; + const node_type m_type; + + _Node_base(node_type type) : m_type(type) + { } + + typedef typename _Alloc::template rebind<_ATraits> __rebind_at; + typedef typename __rebind_at::other::const_pointer a_const_pointer; + typedef typename _ATraits::const_iterator a_const_iterator; + +#ifdef _GLIBCXX_DEBUG + typedef std::pair<a_const_iterator, a_const_iterator> node_debug_info; + + void + assert_valid(a_const_pointer p_traits, + const char* __file, int __line) const + { assert_valid_imp(p_traits, __file, __line); } + + virtual node_debug_info + assert_valid_imp(a_const_pointer, const char*, int) const = 0; +#endif + }; + + + /// Head node for PATRICIA tree. + template<typename _ATraits, typename Metadata> + struct _Head + : public _Node_base<_ATraits, Metadata> + { + typedef _Node_base<_ATraits, Metadata> base_type; + typedef typename base_type::type_traits type_traits; + typedef typename base_type::node_pointer node_pointer; + + node_pointer m_p_min; + node_pointer m_p_max; + + _Head() : base_type(head_node) { } + +#ifdef _GLIBCXX_DEBUG + typedef typename base_type::node_debug_info node_debug_info; + typedef typename base_type::a_const_pointer a_const_pointer; + + virtual node_debug_info + assert_valid_imp(a_const_pointer, const char* __file, int __line) const + { + _GLIBCXX_DEBUG_VERIFY_AT(false, + _M_message("Assertion from %1;:%2;") + ._M_string(__FILE__)._M_integer(__LINE__), + __file, __line); + return node_debug_info(); + } +#endif + }; + + + /// Leaf node for PATRICIA tree. + template<typename _ATraits, typename Metadata> + struct _Leaf + : public _Node_base<_ATraits, Metadata> + { + typedef _Node_base<_ATraits, Metadata> base_type; + typedef typename base_type::type_traits type_traits; + typedef typename type_traits::value_type value_type; + typedef typename type_traits::reference reference; + typedef typename type_traits::const_reference const_reference; + + private: + value_type m_value; + + _Leaf(const _Leaf&); + + public: + _Leaf(const_reference other) + : base_type(leaf_node), m_value(other) { } + + reference + value() + { return m_value; } + + const_reference + value() const + { return m_value; } + +#ifdef _GLIBCXX_DEBUG + typedef typename base_type::node_debug_info node_debug_info; + typedef typename base_type::a_const_pointer a_const_pointer; + + virtual node_debug_info + assert_valid_imp(a_const_pointer p_traits, + const char* __file, int __line) const + { + PB_DS_DEBUG_VERIFY(base_type::m_type == leaf_node); + node_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))); + } + + virtual + ~_Leaf() { } +#endif + }; + + + /// Internal node type, PATRICIA tree. + template<typename _ATraits, typename Metadata> + struct _Inode + : public _Node_base<_ATraits, Metadata> + { + typedef _Node_base<_ATraits, Metadata> base_type; + typedef typename base_type::type_traits type_traits; + typedef typename base_type::access_traits access_traits; + typedef typename type_traits::value_type value_type; + typedef typename base_type::allocator_type _Alloc; + typedef _Alloc allocator_type; + typedef typename _Alloc::size_type size_type; + + private: + typedef typename base_type::a_const_pointer a_const_pointer; + typedef typename base_type::a_const_iterator a_const_iterator; + + typedef typename base_type::node_pointer node_pointer; + typedef typename _Alloc::template rebind<base_type> __rebind_n; + typedef typename __rebind_n::other::const_pointer node_const_pointer; + + typedef _Leaf<_ATraits, Metadata> leaf; + typedef typename _Alloc::template rebind<leaf>::other __rebind_l; + typedef typename __rebind_l::pointer leaf_pointer; + typedef typename __rebind_l::const_pointer leaf_const_pointer; + + typedef typename _Alloc::template rebind<_Inode>::other __rebind_in; + typedef typename __rebind_in::pointer inode_pointer; + typedef typename __rebind_in::const_pointer inode_const_pointer; + + inline size_type + get_pref_pos(a_const_iterator, a_const_iterator, a_const_pointer) const; + + public: + typedef typename _Alloc::template rebind<node_pointer>::other __rebind_np; + typedef typename __rebind_np::pointer node_pointer_pointer; + typedef typename __rebind_np::reference node_pointer_reference; + + enum + { + arr_size = _ATraits::max_size + 1 + }; + PB_DS_STATIC_ASSERT(min_arr_size, arr_size >= 2); + + + /// Constant child iterator. + struct const_iterator + { + node_pointer_pointer m_p_p_cur; + node_pointer_pointer m_p_p_end; + + typedef std::forward_iterator_tag iterator_category; + typedef typename _Alloc::difference_type difference_type; + typedef node_pointer value_type; + typedef node_pointer_pointer pointer; + typedef node_pointer_reference reference; + + const_iterator(node_pointer_pointer p_p_cur = 0, + node_pointer_pointer p_p_end = 0) + : m_p_p_cur(p_p_cur), m_p_p_end(p_p_end) + { } + + bool + operator==(const const_iterator& other) const + { return m_p_p_cur == other.m_p_p_cur; } + + bool + operator!=(const const_iterator& other) const + { return m_p_p_cur != other.m_p_p_cur; } + + const_iterator& + operator++() + { + do + ++m_p_p_cur; + while (m_p_p_cur != m_p_p_end && *m_p_p_cur == 0); + return *this; + } + + 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; + } + + node_const_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 != 0); } +#endif + }; + + + /// Child iterator. + struct iterator : public const_iterator + { + public: + typedef std::forward_iterator_tag iterator_category; + typedef typename _Alloc::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 = 0, + node_pointer_pointer p_p_end = 0) + : const_iterator(p_p_cur, p_p_end) { } + + bool + operator==(const iterator& other) const + { return const_iterator::m_p_p_cur == other.m_p_p_cur; } + + bool + operator!=(const iterator& other) const + { return const_iterator::m_p_p_cur != other.m_p_p_cur; } + + iterator& + operator++() + { + const_iterator::operator++(); + return *this; + } + + 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; + } + }; + + + _Inode(size_type, const a_const_iterator); + + void + update_prefixes(a_const_pointer); + + const_iterator + begin() const; + + iterator + begin(); + + const_iterator + end() const; + + iterator + end(); + + inline node_pointer + get_child_node(a_const_iterator, a_const_iterator, a_const_pointer); + + inline node_const_pointer + get_child_node(a_const_iterator, a_const_iterator, a_const_pointer) const; + + inline iterator + get_child_it(a_const_iterator, a_const_iterator, a_const_pointer); + + inline node_pointer + get_lower_bound_child_node(a_const_iterator, a_const_iterator, + size_type, a_const_pointer); + + inline node_pointer + add_child(node_pointer, a_const_iterator, a_const_iterator, + a_const_pointer); + + inline node_const_pointer + get_join_child(node_const_pointer, a_const_pointer) const; + + inline node_pointer + get_join_child(node_pointer, a_const_pointer); + + void + remove_child(node_pointer); + + void + remove_child(iterator); + + void + replace_child(node_pointer, a_const_iterator, a_const_iterator, + a_const_pointer); + + inline a_const_iterator + pref_b_it() const; + + inline a_const_iterator + pref_e_it() const; + + bool + should_be_mine(a_const_iterator, a_const_iterator, size_type, + a_const_pointer) const; + + leaf_pointer + leftmost_descendant(); + + leaf_const_pointer + leftmost_descendant() const; + + leaf_pointer + rightmost_descendant(); + + leaf_const_pointer + rightmost_descendant() const; + +#ifdef _GLIBCXX_DEBUG + typedef typename base_type::node_debug_info node_debug_info; + + virtual node_debug_info + assert_valid_imp(a_const_pointer, const char*, int) const; +#endif + + size_type + get_e_ind() const + { return m_e_ind; } + + private: + _Inode(const _Inode&); + + size_type + get_begin_pos() const; + + static __rebind_l s_leaf_alloc; + static __rebind_in s_inode_alloc; + + const size_type m_e_ind; + a_const_iterator m_pref_b_it; + a_const_iterator m_pref_e_it; + node_pointer m_a_p_children[arr_size]; + }; + +#define PB_DS_CONST_IT_C_DEC \ + _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator> + +#define PB_DS_CONST_ODIR_IT_C_DEC \ + _CIter<Node, Leaf, Head, Inode, !Is_Forward_Iterator> + +#define PB_DS_IT_C_DEC \ + _Iter<Node, Leaf, Head, Inode, Is_Forward_Iterator> + +#define PB_DS_ODIR_IT_C_DEC \ + _Iter<Node, Leaf, Head, Inode, !Is_Forward_Iterator> + + + /// Const iterator. + template<typename Node, typename Leaf, typename Head, typename Inode, + bool Is_Forward_Iterator> + class _CIter + { + public: + // These types are all the same for the first four template arguments. + typedef typename Node::allocator_type allocator_type; + typedef typename Node::type_traits type_traits; + + typedef std::bidirectional_iterator_tag iterator_category; + typedef typename allocator_type::difference_type difference_type; + typedef typename type_traits::value_type value_type; + typedef typename type_traits::pointer pointer; + typedef typename type_traits::reference reference; + typedef typename type_traits::const_pointer const_pointer; + typedef typename type_traits::const_reference const_reference; + + typedef allocator_type _Alloc; + typedef typename _Alloc::template rebind<Node> __rebind_n; + typedef typename __rebind_n::other::pointer node_pointer; + typedef typename _Alloc::template rebind<Leaf> __rebind_l; + typedef typename __rebind_l::other::pointer leaf_pointer; + typedef typename __rebind_l::other::const_pointer leaf_const_pointer; + typedef typename _Alloc::template rebind<Head> __rebind_h; + typedef typename __rebind_h::other::pointer head_pointer; + + typedef typename _Alloc::template rebind<Inode> __rebind_in; + typedef typename __rebind_in::other::pointer inode_pointer; + typedef typename Inode::iterator inode_iterator; + + node_pointer m_p_nd; + + _CIter(node_pointer p_nd = 0) : m_p_nd(p_nd) + { } + + _CIter(const PB_DS_CONST_ODIR_IT_C_DEC& other) + : m_p_nd(other.m_p_nd) + { } + + _CIter& + operator=(const _CIter& other) + { + m_p_nd = other.m_p_nd; + return *this; + } + + _CIter& + operator=(const PB_DS_CONST_ODIR_IT_C_DEC& other) + { + m_p_nd = other.m_p_nd; + return *this; + } + + const_pointer + operator->() const + { + _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node); + return &static_cast<leaf_pointer>(m_p_nd)->value(); + } + + const_reference + operator*() const + { + _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == leaf_node); + return static_cast<leaf_pointer>(m_p_nd)->value(); + } + + bool + operator==(const _CIter& other) const + { return m_p_nd == other.m_p_nd; } + + bool + operator==(const PB_DS_CONST_ODIR_IT_C_DEC& other) const + { return m_p_nd == other.m_p_nd; } + + bool + operator!=(const _CIter& other) const + { return m_p_nd != other.m_p_nd; } + + bool + operator!=(const PB_DS_CONST_ODIR_IT_C_DEC& other) const + { return m_p_nd != other.m_p_nd; } + + _CIter& + operator++() + { + inc(integral_constant<int, Is_Forward_Iterator>()); + return *this; + } + + _CIter + operator++(int) + { + _CIter ret_it(m_p_nd); + operator++(); + return ret_it; + } + + _CIter& + operator--() + { + dec(integral_constant<int, Is_Forward_Iterator>()); + return *this; + } + + _CIter + operator--(int) + { + _CIter ret_it(m_p_nd); + operator--(); + return ret_it; + } + + protected: + void + inc(false_type) + { dec(true_type()); } + + void + inc(true_type) + { + if (m_p_nd->m_type == head_node) + { + 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 != head_node && get_larger_sibling(m_p_nd) == 0) + { + m_p_nd = p_y; + p_y = p_y->m_p_parent; + } + + if (p_y->m_type == head_node) + { + m_p_nd = p_y; + return; + } + m_p_nd = leftmost_descendant(get_larger_sibling(m_p_nd)); + } + + void + dec(false_type) + { inc(true_type()); } + + void + dec(true_type) + { + if (m_p_nd->m_type == head_node) + { + 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 != head_node && get_smaller_sibling(m_p_nd) == 0) + { + m_p_nd = p_y; + p_y = p_y->m_p_parent; + } + + if (p_y->m_type == head_node) + { + m_p_nd = p_y; + return; + } + m_p_nd = rightmost_descendant(get_smaller_sibling(m_p_nd)); + } + + static node_pointer + get_larger_sibling(node_pointer p_nd) + { + inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent); + + inode_iterator it = p_parent->begin(); + while (*it != p_nd) + ++it; + + inode_iterator next_it = it; + ++next_it; + return (next_it == p_parent->end())? 0 : *next_it; + } + + static node_pointer + get_smaller_sibling(node_pointer p_nd) + { + inode_pointer p_parent = static_cast<inode_pointer>(p_nd->m_p_parent); + + inode_iterator it = p_parent->begin(); + if (*it == p_nd) + return 0; + + inode_iterator prev_it; + do + { + prev_it = it; + ++it; + if (*it == p_nd) + return *prev_it; + } + while (true); + + _GLIBCXX_DEBUG_ASSERT(false); + return 0; + } + + static leaf_pointer + leftmost_descendant(node_pointer p_nd) + { + if (p_nd->m_type == leaf_node) + return static_cast<leaf_pointer>(p_nd); + return static_cast<inode_pointer>(p_nd)->leftmost_descendant(); + } + + static leaf_pointer + rightmost_descendant(node_pointer p_nd) + { + if (p_nd->m_type == leaf_node) + return static_cast<leaf_pointer>(p_nd); + return static_cast<inode_pointer>(p_nd)->rightmost_descendant(); + } + }; + + + /// Iterator. + template<typename Node, typename Leaf, typename Head, typename Inode, + bool Is_Forward_Iterator> + class _Iter + : public _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator> + { + public: + typedef _CIter<Node, Leaf, Head, Inode, Is_Forward_Iterator> + base_type; + typedef typename base_type::allocator_type allocator_type; + typedef typename base_type::type_traits type_traits; + typedef typename type_traits::value_type value_type; + typedef typename type_traits::pointer pointer; + typedef typename type_traits::reference reference; + + typedef typename base_type::node_pointer node_pointer; + typedef typename base_type::leaf_pointer leaf_pointer; + typedef typename base_type::leaf_const_pointer leaf_const_pointer; + typedef typename base_type::head_pointer head_pointer; + typedef typename base_type::inode_pointer inode_pointer; + + _Iter(node_pointer p_nd = 0) + : base_type(p_nd) { } + + _Iter(const PB_DS_ODIR_IT_C_DEC& other) + : base_type(other.m_p_nd) { } + + _Iter& + operator=(const _Iter& other) + { + base_type::m_p_nd = other.m_p_nd; + return *this; + } + + _Iter& + operator=(const PB_DS_ODIR_IT_C_DEC& other) + { + base_type::m_p_nd = other.m_p_nd; + return *this; + } + + pointer + operator->() const + { + _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node); + return &static_cast<leaf_pointer>(base_type::m_p_nd)->value(); + } + + reference + operator*() const + { + _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == leaf_node); + return static_cast<leaf_pointer>(base_type::m_p_nd)->value(); + } + + _Iter& + operator++() + { + base_type::operator++(); + return *this; + } + + _Iter + operator++(int) + { + _Iter ret(base_type::m_p_nd); + operator++(); + return ret; + } + + _Iter& + operator--() + { + base_type::operator--(); + return *this; + } + + _Iter + operator--(int) + { + _Iter ret(base_type::m_p_nd); + operator--(); + return ret; + } + }; + +#undef PB_DS_CONST_ODIR_IT_C_DEC +#undef PB_DS_ODIR_IT_C_DEC + + +#define PB_DS_PAT_TRIE_NODE_CONST_ITERATOR_C_DEC \ + _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc> + +#define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC \ + _Node_iter<Node, Leaf, Head, Inode, _CIterator, Iterator, _ATraits, _Alloc> + + /// Node const iterator. + template<typename Node, + typename Leaf, + typename Head, + typename Inode, + typename _CIterator, + typename Iterator, + typename _Alloc> + class _Node_citer + { + protected: + typedef typename _Alloc::template rebind<Node> __rebind_n; + typedef typename __rebind_n::other::pointer node_pointer; + + typedef typename _Alloc::template rebind<Leaf> __rebind_l; + typedef typename __rebind_l::other::pointer leaf_pointer; + typedef typename __rebind_l::other::const_pointer leaf_const_pointer; + + typedef typename _Alloc::template rebind<Inode> __rebind_in; + typedef typename __rebind_in::other::pointer inode_pointer; + typedef typename __rebind_in::other::const_pointer inode_const_pointer; + + typedef typename Node::a_const_pointer a_const_pointer; + typedef typename Node::a_const_iterator a_const_iterator; + + private: + a_const_iterator + pref_begin() const + { + if (m_p_nd->m_type == leaf_node) + { + leaf_const_pointer lcp = static_cast<leaf_const_pointer>(m_p_nd); + return m_p_traits->begin(m_p_traits->extract_key(lcp->value())); + } + _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); + return static_cast<inode_const_pointer>(m_p_nd)->pref_b_it(); + } + + a_const_iterator + pref_end() const + { + if (m_p_nd->m_type == leaf_node) + { + leaf_const_pointer lcp = static_cast<leaf_const_pointer>(m_p_nd); + return m_p_traits->end(m_p_traits->extract_key(lcp->value())); + } + _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); + return static_cast<inode_const_pointer>(m_p_nd)->pref_e_it(); + } + + public: + typedef trivial_iterator_tag iterator_category; + typedef trivial_iterator_difference_type difference_type; + typedef typename _Alloc::size_type size_type; + + typedef _CIterator value_type; + typedef value_type reference; + typedef value_type const_reference; + + /// Metadata type. + typedef typename Node::metadata_type metadata_type; + + /// Const metadata reference type. + typedef typename _Alloc::template rebind<metadata_type> __rebind_m; + typedef typename __rebind_m::other __rebind_ma; + typedef typename __rebind_ma::const_reference metadata_const_reference; + + inline + _Node_citer(node_pointer p_nd = 0, a_const_pointer p_traits = 0) + : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits) + { } + + /// Subtree valid prefix. + std::pair<a_const_iterator, a_const_iterator> + valid_prefix() const + { return std::make_pair(pref_begin(), pref_end()); } + + /// Const access; returns the __const iterator* associated with + /// the current leaf. + const_reference + operator*() const + { + _GLIBCXX_DEBUG_ASSERT(num_children() == 0); + return _CIterator(m_p_nd); + } + + /// Metadata access. + metadata_const_reference + get_metadata() const + { return m_p_nd->get_metadata(); } + + /// Returns the number of children in the corresponding node. + size_type + num_children() const + { + if (m_p_nd->m_type == leaf_node) + return 0; + _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); + inode_pointer inp = static_cast<inode_pointer>(m_p_nd); + return std::distance(inp->begin(), inp->end()); + } + + /// Returns a __const node __iterator to the corresponding node's + /// i-th child. + _Node_citer + get_child(size_type i) const + { + _GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == i_node); + inode_pointer inp = static_cast<inode_pointer>(m_p_nd); + typename Inode::iterator it = inp->begin(); + std::advance(it, i); + return _Node_citer(*it, m_p_traits); + } + + /// Compares content to a different iterator object. + bool + operator==(const _Node_citer& other) const + { return m_p_nd == other.m_p_nd; } + + /// Compares content (negatively) to a different iterator object. + bool + operator!=(const _Node_citer& other) const + { return m_p_nd != other.m_p_nd; } + + node_pointer m_p_nd; + a_const_pointer m_p_traits; + }; + + + /// Node iterator. + template<typename Node, + typename Leaf, + typename Head, + typename Inode, + typename _CIterator, + typename Iterator, + typename _Alloc> + class _Node_iter + : public _Node_citer<Node, Leaf, Head, Inode, _CIterator, Iterator, _Alloc> + { + private: + typedef _Node_citer<Node, Leaf, Head, Inode, + _CIterator, Iterator, _Alloc> base_type; + typedef typename _Alloc::template rebind<Node> __rebind_n; + typedef typename __rebind_n::other::pointer node_pointer; + typedef typename base_type::inode_pointer inode_pointer; + typedef typename base_type::a_const_pointer a_const_pointer; + typedef Iterator iterator; + + public: + typedef typename base_type::size_type size_type; + + typedef Iterator value_type; + typedef value_type reference; + typedef value_type const_reference; + + _Node_iter(node_pointer p_nd = 0, a_const_pointer p_traits = 0) + : base_type(p_nd, p_traits) + { } + + /// Access; returns the iterator* associated with the current leaf. + 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. + _Node_iter + get_child(size_type i) const + { + _GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == i_node); + + typename Inode::iterator it = + static_cast<inode_pointer>(base_type::m_p_nd)->begin(); + + std::advance(it, i); + return _Node_iter(*it, base_type::m_p_traits); + } + }; + }; + + +#define PB_DS_CLASS_T_DEC \ + template<typename _ATraits, typename Metadata> + +#define PB_DS_CLASS_C_DEC \ + pat_trie_base::_Inode<_ATraits, Metadata> + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::__rebind_l + PB_DS_CLASS_C_DEC::s_leaf_alloc; + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::__rebind_in + PB_DS_CLASS_C_DEC::s_inode_alloc; + + PB_DS_CLASS_T_DEC + inline typename PB_DS_CLASS_C_DEC::size_type + PB_DS_CLASS_C_DEC:: + get_pref_pos(a_const_iterator b_it, a_const_iterator e_it, + a_const_pointer p_traits) const + { + if (static_cast<std::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:: + _Inode(size_type len, const a_const_iterator it) + : base_type(i_node), 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>(0)); + } + + PB_DS_CLASS_T_DEC + void + PB_DS_CLASS_C_DEC:: + update_prefixes(a_const_pointer p_traits) + { + node_pointer p_first = *begin(); + if (p_first->m_type == leaf_node) + { + leaf_const_pointer p = static_cast<leaf_const_pointer>(p_first); + m_pref_b_it = p_traits->begin(access_traits::extract_key(p->value())); + } + else + { + inode_pointer p = static_cast<inode_pointer>(p_first); + _GLIBCXX_DEBUG_ASSERT(p_first->m_type == i_node); + m_pref_b_it = p->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(a_const_iterator b_it, a_const_iterator e_it, + a_const_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(a_const_iterator b_it, a_const_iterator e_it, + a_const_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] != 0); + return iterator(m_a_p_children + i, m_a_p_children + i); + } + + PB_DS_CLASS_T_DEC + inline typename PB_DS_CLASS_C_DEC::node_const_pointer + PB_DS_CLASS_C_DEC:: + get_child_node(a_const_iterator b_it, a_const_iterator e_it, + a_const_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(a_const_iterator b_it, a_const_iterator e_it, + size_type checked_ind, + a_const_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] != 0) + return m_a_p_children[i]; + + while (++i < arr_size) + if (m_a_p_children[i] != 0) + { + const node_type& __nt = m_a_p_children[i]->m_type; + node_pointer ret = m_a_p_children[i]; + + if (__nt == leaf_node) + return ret; + + _GLIBCXX_DEBUG_ASSERT(__nt == i_node); + inode_pointer inp = static_cast<inode_pointer>(ret); + return inp->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, a_const_iterator b_it, a_const_iterator e_it, + a_const_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] == 0) + { + 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::node_const_pointer + PB_DS_CLASS_C_DEC:: + get_join_child(node_const_pointer p_nd, + a_const_pointer p_tr) const + { + node_pointer p = const_cast<node_pointer>(p_nd); + return const_cast<inode_pointer>(this)->get_join_child(p, p_tr); + } + + 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, a_const_pointer p_traits) + { + size_type i; + a_const_iterator b_it; + a_const_iterator e_it; + if (p_nd->m_type == leaf_node) + { + leaf_const_pointer p = static_cast<leaf_const_pointer>(p_nd); + + typedef typename type_traits::key_const_reference kcr; + kcr r_key = access_traits::extract_key(p->value()); + b_it = p_traits->begin(r_key); + e_it = p_traits->end(r_key); + } + else + { + b_it = static_cast<inode_pointer>(p_nd)->pref_b_it(); + e_it = static_cast<inode_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] = 0; + return; + } + _GLIBCXX_DEBUG_ASSERT(i != arr_size); + } + + PB_DS_CLASS_T_DEC + void + PB_DS_CLASS_C_DEC:: + remove_child(iterator it) + { *it.m_p_p_cur = 0; } + + PB_DS_CLASS_T_DEC + void + PB_DS_CLASS_C_DEC:: + replace_child(node_pointer p_nd, a_const_iterator b_it, + a_const_iterator e_it, + a_const_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::a_const_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::a_const_iterator + PB_DS_CLASS_C_DEC:: + pref_e_it() const + { return m_pref_e_it; } + + PB_DS_CLASS_T_DEC + bool + PB_DS_CLASS_C_DEC:: + should_be_mine(a_const_iterator b_it, a_const_iterator e_it, + size_type checked_ind, + a_const_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; + + a_const_iterator key_b_it = b_it; + std::advance(key_b_it, checked_ind); + a_const_iterator key_e_it = b_it; + std::advance(key_e_it, m_e_ind); + + a_const_iterator value_b_it = m_pref_b_it; + std::advance(value_b_it, checked_ind); + a_const_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 == leaf_node) + return (static_cast<leaf_pointer>(p_pot)); + _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node); + return static_cast<inode_pointer>(p_pot)->leftmost_descendant(); + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::leaf_const_pointer + PB_DS_CLASS_C_DEC:: + leftmost_descendant() const + { return const_cast<inode_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 == leaf_node) + return static_cast<leaf_pointer>(p_pot); + _GLIBCXX_DEBUG_ASSERT(p_pot->m_type == i_node); + return static_cast<inode_pointer>(p_pot)->rightmost_descendant(); + } + + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::leaf_const_pointer + PB_DS_CLASS_C_DEC:: + rightmost_descendant() const + { return const_cast<inode_pointer>(this)->rightmost_descendant(); } + + 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 = 0; + for (; i < arr_size && m_a_p_children[i] == 0; ++i) + ; + return i; + } + +#ifdef _GLIBCXX_DEBUG + PB_DS_CLASS_T_DEC + typename PB_DS_CLASS_C_DEC::node_debug_info + PB_DS_CLASS_C_DEC:: + assert_valid_imp(a_const_pointer p_traits, + const char* __file, int __line) const + { + PB_DS_DEBUG_VERIFY(base_type::m_type == i_node); + PB_DS_DEBUG_VERIFY(static_cast<size_type>(std::distance(pref_b_it(), pref_e_it())) == m_e_ind); + PB_DS_DEBUG_VERIFY(std::distance(begin(), end()) >= 2); + + for (typename _Inode::const_iterator it = begin(); it != end(); ++it) + { + node_const_pointer p_nd = *it; + PB_DS_DEBUG_VERIFY(p_nd->m_p_parent == this); + node_debug_info child_ret = p_nd->assert_valid_imp(p_traits, + __file, __line); + + PB_DS_DEBUG_VERIFY(static_cast<size_type>(std::distance(child_ret.first, child_ret.second)) >= m_e_ind); + PB_DS_DEBUG_VERIFY(should_be_mine(child_ret.first, child_ret.second, 0, p_traits)); + PB_DS_DEBUG_VERIFY(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 + } // namespace detail +} // namespace __gnu_pbds + +#endif diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp new file mode 100644 index 0000000..56f7616 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/policy_access_fn_imps.hpp @@ -0,0 +1,63 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/policy_access_fn_imps.hpp + * Contains an implementation class for pat_trie. + */ + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::access_traits& +PB_DS_CLASS_C_DEC:: +get_access_traits() +{ return *this; } + +PB_DS_CLASS_T_DEC +const typename PB_DS_CLASS_C_DEC::access_traits& +PB_DS_CLASS_C_DEC:: +get_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.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp new file mode 100644 index 0000000..38d6062 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/r_erase_fn_imps.hpp @@ -0,0 +1,103 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/r_erase_fn_imps.hpp + * Contains an implementation class for pat_trie. + */ + +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(debug_base::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 == 0) + 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.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp new file mode 100644 index 0000000..f240bfa --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/rotate_fn_imps.hpp @@ -0,0 +1,150 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/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 != 0) + 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 != 0) + 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 == 0) ? + 0 : + & PB_DS_V2F(p_nd->m_p_left->m_value),(p_nd->m_p_right == 0) ? + 0 : + & 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.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp new file mode 100644 index 0000000..56a79d4 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/split_fn_imps.hpp @@ -0,0 +1,250 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/split_fn_imps.hpp + * Contains an implementation class for pat_trie. + */ + +PB_DS_CLASS_T_DEC +void +PB_DS_CLASS_C_DEC:: +split(key_const_reference r_key, PB_DS_CLASS_C_DEC& other) +{ + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) + branch_bag bag; + leaf_pointer p_split_lf = split_prep(r_key, other, bag); + if (p_split_lf == 0) + { + _GLIBCXX_DEBUG_ASSERT(bag.empty()); + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) + 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; + + head_pointer __ohead = other.m_p_head; + __ohead->m_p_max = m_p_head->m_p_max; + m_p_head->m_p_max = rightmost_descendant(m_p_head->m_p_parent); + __ohead->m_p_min = other.leftmost_descendant(__ohead->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; + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) +} + +PB_DS_CLASS_T_DEC +typename PB_DS_CLASS_C_DEC::leaf_pointer +PB_DS_CLASS_C_DEC:: +split_prep(key_const_reference r_key, PB_DS_CLASS_C_DEC& other, + branch_bag& r_bag) +{ + _GLIBCXX_DEBUG_ASSERT(r_bag.empty()); + if (m_size == 0) + { + other.clear(); + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) + return 0; + } + + if (synth_access_traits::cmp_keys(r_key, + PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_min)->value()))) + { + other.clear(); + value_swap(other); + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) + return 0; + } + + if (!synth_access_traits::cmp_keys(r_key, + PB_DS_V2F(static_cast<leaf_const_pointer>(m_p_head->m_p_max)->value()))) + { + PB_DS_ASSERT_VALID((*this)) + PB_DS_ASSERT_VALID(other) + return 0; + } + + iterator it = lower_bound(r_key); + + if (!synth_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 == leaf_node); + leaf_pointer p_ret_l = static_cast<leaf_pointer>(p_nd); + while (p_nd->m_type != head_node) + { + r_bag.add_branch(); + p_nd = p_nd->m_p_parent; + } + _GLIBCXX_DEBUG_ONLY(debug_base::split(r_key,(synth_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, a_const_iterator b_it, a_const_iterator e_it, + PB_DS_CLASS_C_DEC& other, branch_bag& r_bag) +{ + if (p_nd->m_type == leaf_node) + { + _GLIBCXX_DEBUG_ASSERT(other.m_p_head->m_p_parent == 0); + return p_nd; + } + + _GLIBCXX_DEBUG_ASSERT(p_nd->m_type == i_node); + inode_pointer p_ind = static_cast<inode_pointer>(p_nd); + + node_pointer pfirst = p_ind->get_child_node(b_it, e_it, this); + node_pointer p_child_ret = rec_split(pfirst, b_it, e_it, other, r_bag); + PB_DS_ASSERT_NODE_VALID(p_child_ret) + p_ind->replace_child(p_child_ret, b_it, e_it, this); + apply_update(p_ind, (node_update*)this); + + inode_iterator child_it = p_ind->get_child_it(b_it, e_it, this); + const size_type lhs_dist = std::distance(p_ind->begin(), child_it); + const size_type lhs_num_children = lhs_dist + 1; + _GLIBCXX_DEBUG_ASSERT(lhs_num_children > 0); + + const size_type rhs_dist = std::distance(p_ind->begin(), p_ind->end()); + size_type rhs_num_children = rhs_dist - lhs_num_children; + if (rhs_num_children == 0) + { + apply_update(p_ind, (node_update*)this); + return p_ind; + } + + other.split_insert_branch(p_ind->get_e_ind(), b_it, child_it, + rhs_num_children, r_bag); + + child_it = p_ind->get_child_it(b_it, e_it, this); + while (rhs_num_children != 0) + { + ++child_it; + p_ind->remove_child(child_it); + --rhs_num_children; + } + apply_update(p_ind, (node_update*)this); + + const size_type int_dist = std::distance(p_ind->begin(), p_ind->end()); + _GLIBCXX_DEBUG_ASSERT(int_dist >= 1); + if (int_dist > 1) + { + p_ind->update_prefixes(this); + PB_DS_ASSERT_NODE_VALID(p_ind) + apply_update(p_ind, (node_update*)this); + return p_ind; + } + + node_pointer p_ret = *p_ind->begin(); + p_ind->~inode(); + s_inode_allocator.deallocate(p_ind, 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, a_const_iterator b_it, + inode_iterator child_b_it, + size_type num_children, branch_bag& r_bag) +{ +#ifdef _GLIBCXX_DEBUG + if (m_p_head->m_p_parent != 0) + PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) +#endif + + const size_type start = m_p_head->m_p_parent == 0 ? 0 : 1; + const size_type total_num_children = start + num_children; + if (total_num_children == 0) + { + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == 0); + return; + } + + if (total_num_children == 1) + { + if (m_p_head->m_p_parent != 0) + { + PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) + return; + } + + _GLIBCXX_DEBUG_ASSERT(m_p_head->m_p_parent == 0); + ++child_b_it; + 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); + PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) + return; + } + + _GLIBCXX_DEBUG_ASSERT(total_num_children > 1); + inode_pointer p_new_root = r_bag.get_branch(); + new (p_new_root) inode(e_ind, b_it); + size_type num_inserted = 0; + while (num_inserted++ < num_children) + { + ++child_b_it; + PB_DS_ASSERT_NODE_VALID((*child_b_it)) + p_new_root->add_child(*child_b_it, pref_begin(*child_b_it), + pref_end(*child_b_it), this); + } + + if (m_p_head->m_p_parent != 0) + 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); + PB_DS_ASSERT_NODE_VALID(m_p_head->m_p_parent) +} diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp new file mode 100644 index 0000000..10615e2 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp @@ -0,0 +1,218 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/synth_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, typename _ATraits> + +#define PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC \ + synth_access_traits<Type_Traits, Set, _ATraits> + + /// Synthetic element access traits. + template<typename Type_Traits, bool Set, typename _ATraits> + struct synth_access_traits : public _ATraits + { + typedef _ATraits base_type; + typedef typename base_type::const_iterator const_iterator; + typedef Type_Traits type_traits; + typedef typename type_traits::const_reference const_reference; + typedef typename type_traits::key_const_reference key_const_reference; + + synth_access_traits(); + + synth_access_traits(const base_type&); + + inline bool + equal_prefixes(const_iterator, const_iterator, const_iterator, + const_iterator, bool compare_after = true) const; + + bool + equal_keys(key_const_reference, key_const_reference) const; + + bool + cmp_prefixes(const_iterator, const_iterator, const_iterator, + const_iterator, bool compare_after = false) const; + + bool + cmp_keys(key_const_reference, key_const_reference) const; + + inline static key_const_reference + extract_key(const_reference); + +#ifdef _GLIBCXX_DEBUG + bool + operator()(key_const_reference, key_const_reference); +#endif + + private: + inline static key_const_reference + extract_key(const_reference, true_type); + + inline static key_const_reference + extract_key(const_reference, false_type); + + 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_access_traits() + { } + + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: + synth_access_traits(const _ATraits& r_traits) + : _ATraits(r_traits) + { } + + PB_DS_SYNTH_E_ACCESS_TRAITS_T_DEC + inline bool + PB_DS_SYNTH_E_ACCESS_TRAITS_C_DEC:: + equal_prefixes(const_iterator b_l, const_iterator e_l, const_iterator b_r, + 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(key_const_reference r_lhs_key, + key_const_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(const_iterator b_l, const_iterator e_l, const_iterator b_r, + 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(key_const_reference r_lhs_key, + key_const_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::key_const_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::key_const_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::key_const_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()(key_const_reference r_lhs, key_const_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.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp new file mode 100644 index 0000000..73d98f4 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/trace_fn_imps.hpp @@ -0,0 +1,111 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/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 == 0) + 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(node_const_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 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; + } + + inode_const_pointer p_internal = static_cast<inode_const_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 inode::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(node_const_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(node_const_pointer, type_to_type<null_type>) +{ } + +#endif + diff --git a/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp new file mode 100644 index 0000000..65bfee2 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/traits.hpp @@ -0,0 +1,148 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/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_/pat_trie_base.hpp> +#include <ext/pb_ds/detail/pat_trie_/synth_access_traits.hpp> + +namespace __gnu_pbds +{ + namespace detail + { + /// Specialization. + /// @ingroup traits + template<typename Key, + typename Mapped, + typename _ATraits, + template<typename Node_CItr, + typename Node_Itr, + typename Cmp_Fn_, + typename _Alloc_> + class Node_Update, + typename _Alloc> + struct trie_traits<Key, Mapped, _ATraits, Node_Update, pat_trie_tag, _Alloc> + { + private: + typedef pat_trie_base base_type; + typedef types_traits<Key, Mapped, _Alloc, false> type_traits; + + public: + typedef typename trie_node_metadata_dispatch<Key, Mapped, _ATraits, Node_Update, _Alloc>::type metadata_type; + typedef base_type::_Metadata<metadata_type, _Alloc> metadata; + typedef _ATraits access_traits; + + /// Type for synthesized traits. + typedef __gnu_pbds::detail::synth_access_traits<type_traits, false, access_traits> synth_access_traits; + + typedef base_type::_Node_base<synth_access_traits, metadata> node; + typedef base_type::_Head<synth_access_traits, metadata> head; + typedef base_type::_Leaf<synth_access_traits, metadata> leaf; + typedef base_type::_Inode<synth_access_traits, metadata> inode; + + typedef base_type::_Iter<node, leaf, head, inode, true> iterator; + typedef base_type::_CIter<node, leaf, head, inode, true> const_iterator; + typedef base_type::_Iter<node, leaf, head, inode, false> reverse_iterator; + typedef base_type::_CIter<node, leaf, head, inode, false> const_reverse_iterator; + + /// This is an iterator to an iterator: it iterates over nodes, + /// and de-referencing it returns one of the tree's iterators. + typedef base_type::_Node_citer<node, leaf, head, inode, const_iterator, iterator, _Alloc> node_const_iterator; + + typedef base_type::_Node_iter<node, leaf, head, inode, const_iterator, iterator, _Alloc> node_iterator; + + /// Type for node update. + typedef Node_Update<node_const_iterator, node_iterator, _ATraits, _Alloc> node_update; + + typedef null_node_update<node_const_iterator, node_iterator, _ATraits, _Alloc>* null_node_update_pointer; + }; + + + /// Specialization. + /// @ingroup traits + template<typename Key, + typename _ATraits, + template<typename Node_CItr, + typename Node_Itr, + typename Cmp_Fn_, + typename _Alloc_> + class Node_Update, + typename _Alloc> + struct trie_traits<Key, null_type, _ATraits, Node_Update, pat_trie_tag, _Alloc> + { + private: + typedef pat_trie_base base_type; + typedef types_traits<Key, null_type, _Alloc, false> type_traits; + + public: + typedef typename trie_node_metadata_dispatch<Key, null_type, _ATraits, Node_Update, _Alloc>::type metadata_type; + typedef base_type::_Metadata<metadata_type, _Alloc> metadata; + typedef _ATraits access_traits; + + /// Type for synthesized traits. + typedef __gnu_pbds::detail::synth_access_traits<type_traits, true, access_traits> synth_access_traits; + + typedef base_type::_Node_base<synth_access_traits, metadata> node; + typedef base_type::_Head<synth_access_traits, metadata> head; + typedef base_type::_Leaf<synth_access_traits, metadata> leaf; + typedef base_type::_Inode<synth_access_traits, metadata> inode; + + typedef base_type::_CIter<node, leaf, head, inode, true> const_iterator; + typedef const_iterator iterator; + typedef base_type::_CIter<node, leaf, head, inode, false> const_reverse_iterator; + typedef const_reverse_iterator reverse_iterator; + + /// This is an iterator to an iterator: it iterates over nodes, + /// and de-referencing it returns one of the tree's iterators. + typedef base_type::_Node_citer<node, leaf, head, inode, const_iterator, iterator, _Alloc> node_const_iterator; + + typedef node_const_iterator node_iterator; + + /// Type for node update. + typedef Node_Update<node_const_iterator, node_iterator, _ATraits, _Alloc> node_update; + + typedef null_node_update<node_const_iterator, node_const_iterator, _ATraits, _Alloc>* 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.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp new file mode 100644 index 0000000..8b4e532 --- /dev/null +++ b/gcc-4.9/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/update_fn_imps.hpp @@ -0,0 +1,55 @@ +// -*- C++ -*- + +// Copyright (C) 2005-2014 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_/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, 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_*) +{ + Node_Update_::operator()(node_iterator(p_nd, this), + node_const_iterator(0, this)); +} |