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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2016 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
  68     public:
  69       typedef Node node;
  70
  71       typedef
  72       bin_search_tree_const_it_<
  73         typename _Alloc::template rebind<
  74         node>::other::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 _Alloc::template rebind<
  87         node>::other::pointer,
  88         typename type_traits::value_type,
  89         typename type_traits::pointer,
  90         typename type_traits::const_pointer,
  91         typename type_traits::reference,
  92         typename type_traits::const_reference,
  93         true,
  94         _Alloc>
  95       point_iterator;
  96
  97       typedef
  98       bin_search_tree_const_it_<
  99         typename _Alloc::template rebind<
 100         node>::other::pointer,
 101         typename type_traits::value_type,
 102         typename type_traits::pointer,
 103         typename type_traits::const_pointer,
 104         typename type_traits::reference,
 105         typename type_traits::const_reference,
 106         false,
 107         _Alloc>
 108       const_reverse_iterator;
 109
 110       typedef
 111       bin_search_tree_it_<
 112         typename _Alloc::template rebind<
 113         node>::other::pointer,
 114         typename type_traits::value_type,
 115         typename type_traits::pointer,
 116         typename type_traits::const_pointer,
 117         typename type_traits::reference,
 118         typename type_traits::const_reference,
 119         false,
 120         _Alloc>
 121       reverse_iterator;
 122
 123       /// This is an iterator to an iterator: it iterates over nodes,
 124       /// and de-referencing it returns one of the tree's iterators.
 125       typedef
 126       bin_search_tree_const_node_it_<
 127         Node,
 128         point_const_iterator,
 129         point_iterator,
 130         _Alloc>
 131       node_const_iterator;
 132
 133       typedef
 134       bin_search_tree_node_it_<
 135         Node,
 136         point_const_iterator,
 137         point_iterator,
 138         _Alloc>
 139       node_iterator;
 140
 141       typedef
 142       Node_Update<
 143         node_const_iterator,
 144         node_iterator,
 145         Cmp_Fn,
 146         _Alloc>
 147       node_update;
 148
 149       typedef
 150       __gnu_pbds::null_node_update<
 151         node_const_iterator,
 152         node_iterator,
 153         Cmp_Fn,
 154         _Alloc>*
 155       null_node_update_pointer;
 156     };
 157
 158     /// Specialization.
 159     /// @ingroup traits
 160     template<typename Key,
 161              class Cmp_Fn,
 162              template<typename Node_CItr,
 163                       class Node_Itr,
 164                       class _Cmp_Fn,
 165                       typename _Alloc>
 166              class Node_Update,
 167              class Node,
 168              typename _Alloc>
 169     struct
 170     bin_search_tree_traits<Key, null_type, Cmp_Fn, Node_Update, Node, _Alloc>
 171     {
 172     private:
 173       typedef types_traits<Key, null_type, _Alloc, false> type_traits;
 174
 175     public:
 176       typedef Node node;
 177
 178       typedef
 179       bin_search_tree_const_it_<
 180         typename _Alloc::template rebind<
 181         node>::other::pointer,
 182         typename type_traits::value_type,
 183         typename type_traits::pointer,
 184         typename type_traits::const_pointer,
 185         typename type_traits::reference,
 186         typename type_traits::const_reference,
 187         true,
 188         _Alloc>
 189       point_const_iterator;
 190
 191       typedef point_const_iterator point_iterator;
 192
 193       typedef
 194       bin_search_tree_const_it_<
 195         typename _Alloc::template rebind<
 196         node>::other::pointer,
 197         typename type_traits::value_type,
 198         typename type_traits::pointer,
 199         typename type_traits::const_pointer,
 200         typename type_traits::reference,
 201         typename type_traits::const_reference,
 202         false,
 203         _Alloc>
 204       const_reverse_iterator;
 205
 206       typedef const_reverse_iterator reverse_iterator;
 207
 208       /// This is an iterator to an iterator: it iterates over nodes,
 209       /// and de-referencing it returns one of the tree's iterators.
 210       typedef
 211       bin_search_tree_const_node_it_<
 212         Node,
 213         point_const_iterator,
 214         point_iterator,
 215         _Alloc>
 216       node_const_iterator;
 217
 218       typedef node_const_iterator node_iterator;
 219
 220       typedef
 221       Node_Update<node_const_iterator, node_iterator, Cmp_Fn, _Alloc>
 222       node_update;
 223
 224       typedef
 225       __gnu_pbds::null_node_update<
 226         node_const_iterator,
 227         node_iterator,
 228         Cmp_Fn,
 229         _Alloc>*
 230       null_node_update_pointer;
 231     };
 232
 233   } // namespace detail
 234 } // namespace __gnu_pbds
 235
 236 #endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP