X-Git-Url: https://oss.titaniummirror.com/gitweb/?a=blobdiff_plain;f=libstdc%2B%2B-v3%2Finclude%2Fext%2Fpb_ds%2Fdetail%2Fpat_trie_%2Fnode_iterators.hpp;fp=libstdc%2B%2B-v3%2Finclude%2Fext%2Fpb_ds%2Fdetail%2Fpat_trie_%2Fnode_iterators.hpp;h=37250091d00afd9e9f8646a47db75b3883ea65b6;hb=6fed43773c9b0ce596dca5686f37ac3fc0fa11c0;hp=0000000000000000000000000000000000000000;hpb=27b11d56b743098deb193d510b337ba22dc52e5c;p=msp430-gcc.git

diff --git a/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp
new file mode 100644
index 00000000..37250091
--- /dev/null
+++ b/libstdc++-v3/include/ext/pb_ds/detail/pat_trie_/node_iterators.hpp
@@ -0,0 +1,338 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc.
+//
+// This file is part of the GNU ISO C++ Library.  This library is free
+// software; you can redistribute it and/or modify it under the terms
+// of the GNU General Public License as published by the Free Software
+// Foundation; either version 3, or (at your option) any later
+// version.
+
+// This library is distributed in the hope that it will be useful, but
+// WITHOUT ANY WARRANTY; without even the implied warranty of
+// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
+// General Public License for more details.
+
+// Under Section 7 of GPL version 3, you are granted additional
+// permissions described in the GCC Runtime Library Exception, version
+// 3.1, as published by the Free Software Foundation.
+
+// You should have received a copy of the GNU General Public License and
+// a copy of the GCC Runtime Library Exception along with this program;
+// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
+// <http://www.gnu.org/licenses/>.
+
+// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
+
+// Permission to use, copy, modify, sell, and distribute this software
+// is hereby granted without fee, provided that the above copyright
+// notice appears in all copies, and that both that copyright notice
+// and this permission notice appear in supporting documentation. None
+// of the above authors, nor IBM Haifa Research Laboratories, make any
+// representation about the suitability of this software for any
+// purpose. It is provided "as is" without express or implied
+// warranty.
+
+/**
+ * @file node_iterators.hpp
+ * Contains an implementation class for pat_trie_.
+ */
+
+#ifndef PB_DS_PAT_TRIE_NODE_ITERATORS_HPP
+#define PB_DS_PAT_TRIE_NODE_ITERATORS_HPP
+
+#include <debug/debug.h>
+
+namespace __gnu_pbds
+{
+  namespace detail
+  {
+
+#define PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC			\
+    pat_trie_const_node_it_<						\
+							Node,		\
+							Leaf,		\
+							Head,		\
+							Internal_Node,	\
+							Const_Iterator,	\
+							Iterator,	\
+							E_Access_Traits, \
+							Allocator>
+
+#define PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC			\
+    pat_trie_node_it_<						\
+					Node,			\
+					Leaf,			\
+					Head,			\
+					Internal_Node,		\
+					Const_Iterator,		\
+					Iterator,		\
+					E_Access_Traits,	\
+					Allocator>
+
+    // Const node iterator.
+    template<typename Node,
+	     class Leaf,
+	     class Head,
+	     class Internal_Node,
+	     class Const_Iterator,
+	     class Iterator,
+	     class E_Access_Traits,
+	     class Allocator>
+    class pat_trie_const_node_it_
+    {
+    protected:
+      typedef
+      typename Allocator::template rebind<
+      Node>::other::pointer
+      node_pointer;
+
+      typedef
+      typename Allocator::template rebind<
+	Leaf>::other::const_pointer
+      const_leaf_pointer;
+
+      typedef
+      typename Allocator::template rebind<
+	Leaf>::other::pointer
+      leaf_pointer;
+
+      typedef
+      typename Allocator::template rebind<
+	Internal_Node>::other::pointer
+      internal_node_pointer;
+
+      typedef
+      typename Allocator::template rebind<
+	Internal_Node>::other::const_pointer
+      const_internal_node_pointer;
+
+      typedef
+      typename Allocator::template rebind<
+	E_Access_Traits>::other::const_pointer
+      const_e_access_traits_pointer;
+
+    private:
+      inline typename E_Access_Traits::const_iterator
+      pref_begin() const
+      {
+	if (m_p_nd->m_type == pat_trie_leaf_node_type)
+	  return (m_p_traits->begin(
+				    m_p_traits->extract_key(
+							    static_cast<const_leaf_pointer>(m_p_nd)->value())));
+
+	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
+
+	return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_b_it());
+      }
+
+      inline typename E_Access_Traits::const_iterator
+      pref_end() const
+      {
+	if (m_p_nd->m_type == pat_trie_leaf_node_type)
+	  return (m_p_traits->end(
+				  m_p_traits->extract_key(
+							  static_cast<const_leaf_pointer>(m_p_nd)->value())));
+
+	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
+
+	return (static_cast<const_internal_node_pointer>(m_p_nd)->pref_e_it());
+      }
+
+    public:
+
+      // Size type.
+      typedef typename Allocator::size_type size_type;
+
+      // Category.
+      typedef trivial_iterator_tag iterator_category;
+
+      // Difference type.
+      typedef trivial_iterator_difference_type difference_type;
+
+      // __Iterator's value type.
+      typedef Const_Iterator value_type;
+
+      // __Iterator's reference type.
+      typedef value_type reference;
+
+      // __Iterator's __const reference type.
+      typedef value_type const_reference;
+
+      // Element access traits.
+      typedef E_Access_Traits e_access_traits;
+
+      // A key's element __const iterator.
+      typedef typename e_access_traits::const_iterator const_e_iterator;
+
+      // Metadata type.
+      typedef typename Node::metadata_type metadata_type;
+
+      // Const metadata reference type.
+      typedef
+      typename Allocator::template rebind<
+	metadata_type>::other::const_reference
+      const_metadata_reference;
+
+      // Default constructor.
+      /*
+	inline
+	pat_trie_const_node_it_()
+      */
+      inline
+      pat_trie_const_node_it_(node_pointer p_nd = NULL,  
+			      const_e_access_traits_pointer p_traits = NULL) 
+      : m_p_nd(const_cast<node_pointer>(p_nd)), m_p_traits(p_traits)
+      { }
+
+      // Subtree valid prefix.
+      inline std::pair<const_e_iterator, const_e_iterator>
+      valid_prefix() const
+      { return std::make_pair(pref_begin(), pref_end()); }
+
+      // Const access; returns the __const iterator* associated with
+      // the current leaf.
+      inline const_reference
+      operator*() const
+      {
+	_GLIBCXX_DEBUG_ASSERT(num_children() == 0);
+	return Const_Iterator(m_p_nd);
+      }
+
+      // Metadata access.
+      inline const_metadata_reference
+      get_metadata() const
+      { return m_p_nd->get_metadata(); }
+
+      // Returns the number of children in the corresponding node.
+      inline size_type
+      num_children() const
+      {
+	if (m_p_nd->m_type == pat_trie_leaf_node_type)
+	  return 0;
+	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
+	return std::distance(static_cast<internal_node_pointer>(m_p_nd)->begin(),  static_cast<internal_node_pointer>(m_p_nd)->end());
+      }
+
+      // Returns a __const node __iterator to the corresponding node's
+      // i-th child.
+      PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
+      get_child(size_type i) const
+      {
+	_GLIBCXX_DEBUG_ASSERT(m_p_nd->m_type == pat_trie_internal_node_type);
+	typename Internal_Node::iterator it =
+	  static_cast<internal_node_pointer>(m_p_nd)->begin();
+
+	std::advance(it, i);
+	return PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC(*it, m_p_traits);
+      }
+
+      // Compares content to a different iterator object.
+      inline bool
+      operator==(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const
+      { return (m_p_nd == other.m_p_nd); }
+
+      // Compares content (negatively) to a different iterator object.
+      inline bool
+      operator!=(const PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC& other) const
+      { return m_p_nd != other.m_p_nd; }
+
+    private:
+
+      friend class PB_DS_CLASS_C_DEC;
+
+    public:
+      node_pointer m_p_nd;
+
+      const_e_access_traits_pointer m_p_traits;
+    };
+
+    // Node iterator.
+    template<typename Node,
+	     class Leaf,
+	     class Head,
+	     class Internal_Node,
+	     class Const_Iterator,
+	     class Iterator,
+	     class E_Access_Traits,
+	     class Allocator>
+    class pat_trie_node_it_ : 
+      public PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
+
+    {
+    private:
+      typedef
+      typename Allocator::template rebind<
+      Node>::other::pointer
+      node_pointer;
+
+      typedef Iterator iterator;
+
+      typedef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC base_type;
+
+      typedef
+      typename base_type::const_e_access_traits_pointer
+      const_e_access_traits_pointer;
+
+      typedef typename base_type::internal_node_pointer internal_node_pointer;
+
+    public:
+
+      // Size type.
+      typedef
+      typename PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC::size_type
+      size_type;
+
+      // __Iterator's value type.
+      typedef Iterator value_type;
+
+      // __Iterator's reference type.
+      typedef value_type reference;
+
+      // __Iterator's __const reference type.
+      typedef value_type const_reference;
+
+      // Default constructor.
+      /*
+	inline
+	pat_trie_node_it_() ;
+      */
+
+      inline
+      pat_trie_node_it_(node_pointer p_nd = NULL,  const_e_access_traits_pointer p_traits = NULL) : base_type(p_nd, p_traits)
+      { }
+
+      // Access; returns the iterator*  associated with the current leaf.
+      inline reference
+      operator*() const
+      {
+	_GLIBCXX_DEBUG_ASSERT(base_type::num_children() == 0);
+	return Iterator(base_type::m_p_nd);
+
+      }
+
+      // Returns a node __iterator to the corresponding node's i-th child.
+      PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC
+      get_child(size_type i) const
+      {
+	_GLIBCXX_DEBUG_ASSERT(base_type::m_p_nd->m_type == pat_trie_internal_node_type);
+
+	typename Internal_Node::iterator it =
+	  static_cast<internal_node_pointer>(base_type::m_p_nd)->begin();
+
+	std::advance(it, i);
+	return PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC(*it, base_type::m_p_traits);
+      }
+
+    private:
+      friend class PB_DS_CLASS_C_DEC;
+    };
+
+#undef PB_DS_PAT_TRIE_CONST_NODE_ITERATOR_C_DEC
+#undef PB_DS_PAT_TRIE_NODE_ITERATOR_C_DEC
+
+  } // namespace detail
+} // namespace __gnu_pbds
+
+#endif 
+