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

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006, 2009 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     template<typename Key,
  53              typename Mapped,
  54              class Cmp_Fn,
  55              template<typename Node_CItr,
  56                       class Node_Itr,
  57                       class Cmp_Fn,
  58                       typename _Alloc>
  59     class Node_Update,
  60              class Node,
  61              typename _Alloc>
  62     struct bin_search_tree_traits
  63     {
  64     private:
  65       typedef types_traits<Key, Mapped, _Alloc, false> type_traits;
  66
  67     public:
  68       typedef Node node;
  69
  70       typedef
  71       bin_search_tree_const_it_<
  72         typename _Alloc::template rebind<
  73         node>::other::pointer,
  74         typename type_traits::value_type,
  75         typename type_traits::pointer,
  76         typename type_traits::const_pointer,
  77         typename type_traits::reference,
  78         typename type_traits::const_reference,
  79         true,
  80         _Alloc>
  81       point_const_iterator;
  82
  83       typedef
  84       bin_search_tree_it_<
  85         typename _Alloc::template rebind<
  86         node>::other::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 _Alloc::template rebind<
  99         node>::other::pointer,
 100         typename type_traits::value_type,
 101         typename type_traits::pointer,
 102         typename type_traits::const_pointer,
 103         typename type_traits::reference,
 104         typename type_traits::const_reference,
 105         false,
 106         _Alloc>
 107       const_reverse_iterator;
 108
 109       typedef
 110       bin_search_tree_it_<
 111         typename _Alloc::template rebind<
 112         node>::other::pointer,
 113         typename type_traits::value_type,
 114         typename type_traits::pointer,
 115         typename type_traits::const_pointer,
 116         typename type_traits::reference,
 117         typename type_traits::const_reference,
 118         false,
 119         _Alloc>
 120       reverse_iterator;
 121
 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     template<typename Key,
 157              class Cmp_Fn,
 158              template<typename Node_CItr,
 159                       class Node_Itr,
 160                       class Cmp_Fn,
 161                       typename _Alloc>
 162     class Node_Update,
 163              class Node,
 164              typename _Alloc>
 165     struct bin_search_tree_traits<
 166       Key,
 167       null_type,
 168       Cmp_Fn,
 169       Node_Update,
 170       Node,
 171       _Alloc>
 172     {
 173     private:
 174       typedef types_traits<Key, null_type, _Alloc, false> type_traits;
 175
 176     public:
 177       typedef Node node;
 178
 179       typedef
 180       bin_search_tree_const_it_<
 181         typename _Alloc::template rebind<
 182         node>::other::pointer,
 183         typename type_traits::value_type,
 184         typename type_traits::pointer,
 185         typename type_traits::const_pointer,
 186         typename type_traits::reference,
 187         typename type_traits::const_reference,
 188         true,
 189         _Alloc>
 190       point_const_iterator;
 191
 192       typedef point_const_iterator point_iterator;
 193
 194       typedef
 195       bin_search_tree_const_it_<
 196         typename _Alloc::template rebind<
 197         node>::other::pointer,
 198         typename type_traits::value_type,
 199         typename type_traits::pointer,
 200         typename type_traits::const_pointer,
 201         typename type_traits::reference,
 202         typename type_traits::const_reference,
 203         false,
 204         _Alloc>
 205       const_reverse_iterator;
 206
 207       typedef const_reverse_iterator reverse_iterator;
 208
 209       typedef
 210       bin_search_tree_const_node_it_<
 211         Node,
 212         point_const_iterator,
 213         point_iterator,
 214         _Alloc>
 215       node_const_iterator;
 216
 217       typedef node_const_iterator node_iterator;
 218
 219       typedef
 220       Node_Update<node_const_iterator, node_iterator, Cmp_Fn, _Alloc>
 221       node_update;
 222
 223       typedef
 224       __gnu_pbds::null_node_update<
 225         node_const_iterator,
 226         node_iterator,
 227         Cmp_Fn,
 228         _Alloc>*
 229       null_node_update_pointer;
 230     };
 231
 232   } // namespace detail
 233 } // namespace __gnu_pbds
 234
 235 #endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP