libstdc++-v3/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2024 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_/traits.hpp
  38  * Contains an implementation for bin_search_tree_.
  39  */
  40
  41 #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
  42 #define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
  43
  44 #include <ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp>
  45 #include <ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp>
  46
  47 namespace __gnu_pbds
  48 {
  49   namespace detail
  50   {
  51     /// Binary search tree traits, primary template
  52     /// @ingroup traits
  53     template<typename Key,
  54              typename Mapped,
  55              class Cmp_Fn,
  56              template<typename Node_CItr,
  57                       class Node_Itr,
  58                       class _Cmp_Fn,
  59                       typename _Alloc>
  60              class Node_Update,
  61              class Node,
  62              typename _Alloc>
  63     struct bin_search_tree_traits
  64     {
  65     private:
  66       typedef types_traits<Key, Mapped, _Alloc, false> type_traits;
  67       typedef rebind_traits<_Alloc, Node> node_alloc_traits;
  68
  69     public:
  70       typedef Node node;
  71
  72       typedef
  73       bin_search_tree_const_it_<
  74         typename node_alloc_traits::pointer,
  75         typename type_traits::value_type,
  76         typename type_traits::pointer,
  77         typename type_traits::const_pointer,
  78         typename type_traits::reference,
  79         typename type_traits::const_reference,
  80         true,
  81         _Alloc>
  82       point_const_iterator;
  83
  84       typedef
  85       bin_search_tree_it_<
  86         typename node_alloc_traits::pointer,
  87         typename type_traits::value_type,
  88         typename type_traits::pointer,
  89         typename type_traits::const_pointer,
  90         typename type_traits::reference,
  91         typename type_traits::const_reference,
  92         true,
  93         _Alloc>
  94       point_iterator;
  95
  96       typedef
  97       bin_search_tree_const_it_<
  98         typename node_alloc_traits::pointer,
  99         typename type_traits::value_type,
 100         typename type_traits::pointer,
 101         typename type_traits::const_pointer,
 102         typename type_traits::reference,
 103         typename type_traits::const_reference,
 104         false,
 105         _Alloc>
 106       const_reverse_iterator;
 107
 108       typedef
 109       bin_search_tree_it_<
 110         typename node_alloc_traits::pointer,
 111         typename type_traits::value_type,
 112         typename type_traits::pointer,
 113         typename type_traits::const_pointer,
 114         typename type_traits::reference,
 115         typename type_traits::const_reference,
 116         false,
 117         _Alloc>
 118       reverse_iterator;
 119
 120       /// This is an iterator to an iterator: it iterates over nodes,
 121       /// and de-referencing it returns one of the tree's iterators.
 122       typedef
 123       bin_search_tree_const_node_it_<
 124         Node,
 125         point_const_iterator,
 126         point_iterator,
 127         _Alloc>
 128       node_const_iterator;
 129
 130       typedef
 131       bin_search_tree_node_it_<
 132         Node,
 133         point_const_iterator,
 134         point_iterator,
 135         _Alloc>
 136       node_iterator;
 137
 138       typedef
 139       Node_Update<
 140         node_const_iterator,
 141         node_iterator,
 142         Cmp_Fn,
 143         _Alloc>
 144       node_update;
 145
 146       typedef
 147       __gnu_pbds::null_node_update<
 148         node_const_iterator,
 149         node_iterator,
 150         Cmp_Fn,
 151         _Alloc>*
 152       null_node_update_pointer;
 153     };
 154
 155     /// Specialization.
 156     /// @ingroup traits
 157     template<typename Key,
 158              class Cmp_Fn,
 159              template<typename Node_CItr,
 160                       class Node_Itr,
 161                       class _Cmp_Fn,
 162                       typename _Alloc>
 163              class Node_Update,
 164              class Node,
 165              typename _Alloc>
 166     struct
 167     bin_search_tree_traits<Key, null_type, Cmp_Fn, Node_Update, Node, _Alloc>
 168     {
 169     private:
 170       typedef types_traits<Key, null_type, _Alloc, false> type_traits;
 171       typedef rebind_traits<_Alloc, Node> node_alloc_traits;
 172
 173     public:
 174       typedef Node node;
 175
 176       typedef
 177       bin_search_tree_const_it_<
 178         typename node_alloc_traits::pointer,
 179         typename type_traits::value_type,
 180         typename type_traits::pointer,
 181         typename type_traits::const_pointer,
 182         typename type_traits::reference,
 183         typename type_traits::const_reference,
 184         true,
 185         _Alloc>
 186       point_const_iterator;
 187
 188       typedef point_const_iterator point_iterator;
 189
 190       typedef
 191       bin_search_tree_const_it_<
 192         typename node_alloc_traits::pointer,
 193         typename type_traits::value_type,
 194         typename type_traits::pointer,
 195         typename type_traits::const_pointer,
 196         typename type_traits::reference,
 197         typename type_traits::const_reference,
 198         false,
 199         _Alloc>
 200       const_reverse_iterator;
 201
 202       typedef const_reverse_iterator reverse_iterator;
 203
 204       /// This is an iterator to an iterator: it iterates over nodes,
 205       /// and de-referencing it returns one of the tree's iterators.
 206       typedef
 207       bin_search_tree_const_node_it_<
 208         Node,
 209         point_const_iterator,
 210         point_iterator,
 211         _Alloc>
 212       node_const_iterator;
 213
 214       typedef node_const_iterator node_iterator;
 215
 216       typedef
 217       Node_Update<node_const_iterator, node_iterator, Cmp_Fn, _Alloc>
 218       node_update;
 219
 220       typedef
 221       __gnu_pbds::null_node_update<
 222         node_const_iterator,
 223         node_iterator,
 224         Cmp_Fn,
 225         _Alloc>*
 226       null_node_update_pointer;
 227     };
 228
 229   } // namespace detail
 230 } // namespace __gnu_pbds
 231
 232 #endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP