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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2014 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 bin_search_tree_traits<
 170       Key,
 171       null_type,
 172       Cmp_Fn,
 173       Node_Update,
 174       Node,
 175       _Alloc>
 176     {
 177     private:
 178       typedef types_traits<Key, null_type, _Alloc, false> type_traits;
 179
 180     public:
 181       typedef Node node;
 182
 183       typedef
 184       bin_search_tree_const_it_<
 185         typename _Alloc::template rebind<
 186         node>::other::pointer,
 187         typename type_traits::value_type,
 188         typename type_traits::pointer,
 189         typename type_traits::const_pointer,
 190         typename type_traits::reference,
 191         typename type_traits::const_reference,
 192         true,
 193         _Alloc>
 194       point_const_iterator;
 195
 196       typedef point_const_iterator point_iterator;
 197
 198       typedef
 199       bin_search_tree_const_it_<
 200         typename _Alloc::template rebind<
 201         node>::other::pointer,
 202         typename type_traits::value_type,
 203         typename type_traits::pointer,
 204         typename type_traits::const_pointer,
 205         typename type_traits::reference,
 206         typename type_traits::const_reference,
 207         false,
 208         _Alloc>
 209       const_reverse_iterator;
 210
 211       typedef const_reverse_iterator reverse_iterator;
 212
 213       /// This is an iterator to an iterator: it iterates over nodes,
 214       /// and de-referencing it returns one of the tree's iterators.
 215       typedef
 216       bin_search_tree_const_node_it_<
 217         Node,
 218         point_const_iterator,
 219         point_iterator,
 220         _Alloc>
 221       node_const_iterator;
 222
 223       typedef node_const_iterator node_iterator;
 224
 225       typedef
 226       Node_Update<node_const_iterator, node_iterator, Cmp_Fn, _Alloc>
 227       node_update;
 228
 229       typedef
 230       __gnu_pbds::null_node_update<
 231         node_const_iterator,
 232         node_iterator,
 233         Cmp_Fn,
 234         _Alloc>*
 235       null_node_update_pointer;
 236     };
 237
 238   } // namespace detail
 239 } // namespace __gnu_pbds
 240
 241 #endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP