X-Git-Url: http://wagnertech.de/git?a=blobdiff_plain;f=i686-linux-gnu-4.7%2Fusr%2Finclude%2Fc%2B%2B%2F4.7%2Fext%2Fpb_ds%2Fdetail%2Fbin_search_tree_%2Fpoint_iterators.hpp;fp=i686-linux-gnu-4.7%2Fusr%2Finclude%2Fc%2B%2B%2F4.7%2Fext%2Fpb_ds%2Fdetail%2Fbin_search_tree_%2Fpoint_iterators.hpp;h=d99924878c301d390d110a39ce792ba8e9bc6cbc;hb=94df942c2c7bd3457276fe5b7367623cbb8c1302;hp=0000000000000000000000000000000000000000;hpb=4dd7d9155a920895ff7b1cb6b9c9c676aa62000a;p=cross.git
diff --git a/i686-linux-gnu-4.7/usr/include/c++/4.7/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp b/i686-linux-gnu-4.7/usr/include/c++/4.7/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp
new file mode 100644
index 0000000..d999248
--- /dev/null
+++ b/i686-linux-gnu-4.7/usr/include/c++/4.7/ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp
@@ -0,0 +1,367 @@
+// -*- C++ -*-
+
+// Copyright (C) 2005, 2006, 2009, 2010 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
+// .
+
+// 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 bin_search_tree_/point_iterators.hpp
+ * Contains an implementation class for bin_search_tree_.
+ */
+
+#ifndef PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
+#define PB_DS_BIN_SEARCH_TREE_FIND_ITERATORS_HPP
+
+#include
+#include
+
+namespace __gnu_pbds
+{
+ namespace detail
+ {
+
+#define PB_DS_TREE_CONST_IT_C_DEC \
+ bin_search_tree_const_it_< \
+ Node_Pointer, \
+ Value_Type, \
+ Pointer, \
+ Const_Pointer, \
+ Reference, \
+ Const_Reference, \
+ Is_Forward_Iterator, \
+ _Alloc>
+
+#define PB_DS_TREE_CONST_ODIR_IT_C_DEC \
+ bin_search_tree_const_it_< \
+ Node_Pointer, \
+ Value_Type, \
+ Pointer, \
+ Const_Pointer, \
+ Reference, \
+ Const_Reference, \
+ !Is_Forward_Iterator, \
+ _Alloc>
+
+#define PB_DS_TREE_IT_C_DEC \
+ bin_search_tree_it_< \
+ Node_Pointer, \
+ Value_Type, \
+ Pointer, \
+ Const_Pointer, \
+ Reference, \
+ Const_Reference, \
+ Is_Forward_Iterator, \
+ _Alloc>
+
+#define PB_DS_TREE_ODIR_IT_C_DEC \
+ bin_search_tree_it_< \
+ Node_Pointer, \
+ Value_Type, \
+ Pointer, \
+ Const_Pointer, \
+ Reference, \
+ Const_Reference, \
+ !Is_Forward_Iterator, \
+ _Alloc>
+
+ /// Const iterator.
+ template
+ class bin_search_tree_const_it_
+ {
+ public:
+ typedef std::bidirectional_iterator_tag iterator_category;
+ typedef typename _Alloc::difference_type difference_type;
+ typedef Value_Type value_type;
+ typedef Pointer pointer;
+ typedef Const_Pointer const_pointer;
+ typedef Reference reference;
+ typedef Const_Reference const_reference;
+
+ inline
+ bin_search_tree_const_it_(const Node_Pointer p_nd = 0)
+ : m_p_nd(const_cast(p_nd))
+ { }
+
+ inline
+ bin_search_tree_const_it_(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other)
+ : m_p_nd(other.m_p_nd)
+ { }
+
+ inline
+ PB_DS_TREE_CONST_IT_C_DEC&
+ operator=(const PB_DS_TREE_CONST_IT_C_DEC& other)
+ {
+ m_p_nd = other.m_p_nd;
+ return *this;
+ }
+
+ inline
+ PB_DS_TREE_CONST_IT_C_DEC&
+ operator=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other)
+ {
+ m_p_nd = other.m_p_nd;
+ return *this;
+ }
+
+ inline const_pointer
+ operator->() const
+ {
+ _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
+ return &m_p_nd->m_value;
+ }
+
+ inline const_reference
+ operator*() const
+ {
+ _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
+ return m_p_nd->m_value;
+ }
+
+ inline bool
+ operator==(const PB_DS_TREE_CONST_IT_C_DEC & other) const
+ { return m_p_nd == other.m_p_nd; }
+
+ inline bool
+ operator==(const PB_DS_TREE_CONST_ODIR_IT_C_DEC & other) const
+ { return m_p_nd == other.m_p_nd; }
+
+ inline bool
+ operator!=(const PB_DS_TREE_CONST_IT_C_DEC& other) const
+ { return m_p_nd != other.m_p_nd; }
+
+ inline bool
+ operator!=(const PB_DS_TREE_CONST_ODIR_IT_C_DEC& other) const
+ { return m_p_nd != other.m_p_nd; }
+
+ inline PB_DS_TREE_CONST_IT_C_DEC&
+ operator++()
+ {
+ _GLIBCXX_DEBUG_ASSERT(m_p_nd != 0);
+ inc(integral_constant());
+ return *this;
+ }
+
+ inline PB_DS_TREE_CONST_IT_C_DEC
+ operator++(int)
+ {
+ PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
+ operator++();
+ return ret_it;
+ }
+
+ inline PB_DS_TREE_CONST_IT_C_DEC&
+ operator--()
+ {
+ dec(integral_constant());
+ return *this;
+ }
+
+ inline PB_DS_TREE_CONST_IT_C_DEC
+ operator--(int)
+ {
+ PB_DS_TREE_CONST_IT_C_DEC ret_it(m_p_nd);
+ operator--();
+ return ret_it;
+ }
+
+ protected:
+ inline void
+ inc(false_type)
+ { dec(true_type()); }
+
+ void
+ inc(true_type)
+ {
+ if (m_p_nd->special()&&
+ m_p_nd->m_p_parent->m_p_parent == m_p_nd)
+ {
+ m_p_nd = m_p_nd->m_p_left;
+ return;
+ }
+
+ if (m_p_nd->m_p_right != 0)
+ {
+ m_p_nd = m_p_nd->m_p_right;
+ while (m_p_nd->m_p_left != 0)
+ m_p_nd = m_p_nd->m_p_left;
+ return;
+ }
+
+ Node_Pointer p_y = m_p_nd->m_p_parent;
+ while (m_p_nd == p_y->m_p_right)
+ {
+ m_p_nd = p_y;
+ p_y = p_y->m_p_parent;
+ }
+
+ if (m_p_nd->m_p_right != p_y)
+ m_p_nd = p_y;
+ }
+
+ inline void
+ dec(false_type)
+ { inc(true_type()); }
+
+ void
+ dec(true_type)
+ {
+ if (m_p_nd->special() && m_p_nd->m_p_parent->m_p_parent == m_p_nd)
+ {
+ m_p_nd = m_p_nd->m_p_right;
+ return;
+ }
+
+ if (m_p_nd->m_p_left != 0)
+ {
+ Node_Pointer p_y = m_p_nd->m_p_left;
+ while (p_y->m_p_right != 0)
+ p_y = p_y->m_p_right;
+ m_p_nd = p_y;
+ return;
+ }
+
+ Node_Pointer p_y = m_p_nd->m_p_parent;
+ while (m_p_nd == p_y->m_p_left)
+ {
+ m_p_nd = p_y;
+ p_y = p_y->m_p_parent;
+ }
+ if (m_p_nd->m_p_left != p_y)
+ m_p_nd = p_y;
+ }
+
+ public:
+ Node_Pointer m_p_nd;
+ };
+
+ /// Iterator.
+ template
+ class bin_search_tree_it_ : public PB_DS_TREE_CONST_IT_C_DEC
+ {
+ public:
+ inline
+ bin_search_tree_it_(const Node_Pointer p_nd = 0)
+ : PB_DS_TREE_CONST_IT_C_DEC((Node_Pointer)p_nd)
+ { }
+
+ inline
+ bin_search_tree_it_(const PB_DS_TREE_ODIR_IT_C_DEC& other)
+ : PB_DS_TREE_CONST_IT_C_DEC(other.m_p_nd)
+ { }
+
+ inline
+ PB_DS_TREE_IT_C_DEC&
+ operator=(const PB_DS_TREE_IT_C_DEC& other)
+ {
+ base_it_type::m_p_nd = other.m_p_nd;
+ return *this;
+ }
+
+ inline
+ PB_DS_TREE_IT_C_DEC&
+ operator=(const PB_DS_TREE_ODIR_IT_C_DEC& other)
+ {
+ base_it_type::m_p_nd = other.m_p_nd;
+ return *this;
+ }
+
+ inline typename PB_DS_TREE_CONST_IT_C_DEC::pointer
+ operator->() const
+ {
+ _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0);
+ return &base_it_type::m_p_nd->m_value;
+ }
+
+ inline typename PB_DS_TREE_CONST_IT_C_DEC::reference
+ operator*() const
+ {
+ _GLIBCXX_DEBUG_ASSERT(base_it_type::m_p_nd != 0);
+ return base_it_type::m_p_nd->m_value;
+ }
+
+ inline PB_DS_TREE_IT_C_DEC&
+ operator++()
+ {
+ PB_DS_TREE_CONST_IT_C_DEC:: operator++();
+ return *this;
+ }
+
+ inline PB_DS_TREE_IT_C_DEC
+ operator++(int)
+ {
+ PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
+ operator++();
+ return ret_it;
+ }
+
+ inline PB_DS_TREE_IT_C_DEC&
+ operator--()
+ {
+ PB_DS_TREE_CONST_IT_C_DEC:: operator--();
+ return *this;
+ }
+
+ inline PB_DS_TREE_IT_C_DEC
+ operator--(int)
+ {
+ PB_DS_TREE_IT_C_DEC ret_it(base_it_type::m_p_nd);
+ operator--();
+ return ret_it;
+ }
+
+ protected:
+ typedef PB_DS_TREE_CONST_IT_C_DEC base_it_type;
+ };
+
+#undef PB_DS_TREE_CONST_IT_C_DEC
+#undef PB_DS_TREE_CONST_ODIR_IT_C_DEC
+#undef PB_DS_TREE_IT_C_DEC
+#undef PB_DS_TREE_ODIR_IT_C_DEC
+
+ } // namespace detail
+} // namespace __gnu_pbds
+
+#endif