Where Online Learning is simpler!

The C and C++ Include Header Files

/usr/include/c++/11/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp


$ cat -n /usr/include/c++/11/ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp

     1	// -*- C++ -*-
     2	
     3	// Copyright (C) 2005-2021 Free Software Foundation, Inc.
     4	//
     5	// This file is part of the GNU ISO C++ Library.  This library is free
     6	// software; you can redistribute it and/or modify it under the terms
     7	// of the GNU General Public License as published by the Free Software
     8	// Foundation; either version 3, or (at your option) any later
     9	// version.
    10	
    11	// This library is distributed in the hope that it will be useful, but
    12	// WITHOUT ANY WARRANTY; without even the implied warranty of
    13	// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
    14	// General Public License for more details.
    15	
    16	// Under Section 7 of GPL version 3, you are granted additional
    17	// permissions described in the GCC Runtime Library Exception, version
    18	// 3.1, as published by the Free Software Foundation.
    19	
    20	// You should have received a copy of the GNU General Public License and
    21	// a copy of the GCC Runtime Library Exception along with this program;
    22	// see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
    23	// <http://www.gnu.org/licenses/>.
    24	
    25	// Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
    26	
    27	// Permission to use, copy, modify, sell, and distribute this software
    28	// is hereby granted without fee, provided that the above copyright
    29	// notice appears in all copies, and that both that copyright notice
    30	// and this permission notice appear in supporting documentation. None
    31	// of the above authors, nor IBM Haifa Research Laboratories, make any
    32	// representation about the suitability of this software for any
    33	// purpose. It is provided "as is" without express or implied
    34	// warranty.
    35	
    36	/**
    37	 * @file bin_search_tree_/node_iterators.hpp
    38	 * Contains an implementation class for bin_search_tree_.
    39	 */
    40	
    41	#ifndef PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP
    42	#define PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP
    43	
    44	#include <ext/pb_ds/tag_and_trait.hpp>
    45	
    46	namespace __gnu_pbds
    47	{
    48	  namespace detail
    49	  {
    50	#define PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC \
    51	    bin_search_tree_const_node_it_<Node, Const_Iterator, Iterator, _Alloc>
    52	
    53	    /// Const node iterator.
    54	    template<typename Node,
    55		     class Const_Iterator,
    56		     class Iterator,
    57		     typename _Alloc>
    58	    class bin_search_tree_const_node_it_
    59	    {
    60	    private:
    61	      typedef typename rebind_traits<_Alloc, Node>::pointer node_pointer;
    62	
    63	    public:
    64	      /// Category.
    65	      typedef trivial_iterator_tag iterator_category;
    66	
    67	      /// Difference type.
    68	      typedef trivial_iterator_difference_type difference_type;
    69	
    70	      /// Iterator's value type.
    71	      typedef Const_Iterator value_type;
    72	
    73	      /// Iterator's reference type.
    74	      typedef Const_Iterator reference;
    75	
    76	      /// Iterator's __const reference type.
    77	      typedef Const_Iterator const_reference;
    78	
    79	      /// Metadata type.
    80	      typedef typename Node::metadata_type metadata_type;
    81	
    82	      /// Const metadata reference type.
    83	      typedef typename rebind_traits<_Alloc, metadata_type>::const_reference
    84		metadata_const_reference;
    85	
    86	
    87	      bin_search_tree_const_node_it_(const node_pointer p_nd = 0)
    88	      : m_p_nd(const_cast<node_pointer>(p_nd))
    89	      { }
    90	
    91	      /// Access.
    92	      const_reference
    93	      operator*() const
    94	      { return Const_Iterator(m_p_nd); }
    95	
    96	      /// Metadata access.
    97	      metadata_const_reference
    98	      get_metadata() const
    99	      { return m_p_nd->get_metadata(); }
   100	
   101	      /// Returns the __const node iterator associated with the left node.
   102	      PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
   103	      get_l_child() const
   104	      { return PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_left); }
   105	
   106	      /// Returns the __const node iterator associated with the right node.
   107	      PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
   108	      get_r_child() const
   109	      { return PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(m_p_nd->m_p_right); }
   110	
   111	      /// Compares to a different iterator object.
   112	      bool
   113	      operator==(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC& other) const
   114	      { return m_p_nd == other.m_p_nd; }
   115	
   116	      /// Compares (negatively) to a different iterator object.
   117	      bool
   118	      operator!=(const PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC& other) const
   119	      { return m_p_nd != other.m_p_nd; }
   120	
   121	      node_pointer m_p_nd;
   122	    };
   123	
   124	#define PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC \
   125	    bin_search_tree_node_it_<Node, Const_Iterator, Iterator, _Alloc>
   126	
   127	    /// Node iterator.
   128	    template<typename Node,
   129		     class Const_Iterator,
   130		     class Iterator,
   131		     typename _Alloc>
   132	    class bin_search_tree_node_it_
   133	    : public PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
   134	    {
   135	    private:
   136	      typedef typename rebind_traits<_Alloc, Node>::pointer node_pointer;
   137	
   138	    public:
   139	      /// Iterator's value type.
   140	      typedef Iterator value_type;
   141	
   142	      /// Iterator's reference type.
   143	      typedef Iterator reference;
   144	
   145	      /// Iterator's __const reference type.
   146	      typedef Iterator const_reference;
   147	
   148	      inline
   149	      bin_search_tree_node_it_(const node_pointer p_nd = 0)
   150	      : PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC(const_cast<node_pointer>(p_nd))
   151	      { }
   152	
   153	      /// Access.
   154	      Iterator
   155	      operator*() const
   156	      { return Iterator(PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd); }
   157	
   158	      /// Returns the node iterator associated with the left node.
   159	      PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC
   160	      get_l_child() const
   161	      {
   162		return PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC(
   163							    PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_left);
   164	      }
   165	
   166	      /// Returns the node iterator associated with the right node.
   167	      PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC
   168	      get_r_child() const
   169	      {
   170		return PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC(
   171							    PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC::m_p_nd->m_p_right);
   172	      }
   173	
   174	    };
   175	
   176	#undef PB_DS_TREE_CONST_NODE_ITERATOR_CLASS_C_DEC
   177	#undef PB_DS_TREE_NODE_ITERATOR_CLASS_C_DEC
   178	
   179	  } // namespace detail
   180	} // namespace __gnu_pbds
   181	
   182	#endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_ITERATORS_HPP