contrib/libstdc++/include/ext/pb_ds/detail/bin_search_tree_/traits.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005, 2006 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 2, 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 // You should have received a copy of the GNU General Public License
  17 // along with this library; see the file COPYING.  If not, write to
  18 // the Free Software Foundation, 59 Temple Place - Suite 330, Boston,
  19 // MA 02111-1307, USA.
  20
  21 // As a special exception, you may use this file as part of a free
  22 // software library without restriction.  Specifically, if other files
  23 // instantiate templates or use macros or inline functions from this
  24 // file, or you compile this file and link it with other files to
  25 // produce an executable, this file does not by itself cause the
  26 // resulting executable to be covered by the GNU General Public
  27 // License.  This exception does not however invalidate any other
  28 // reasons why the executable file might be covered by the GNU General
  29 // Public License.
  30
  31 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  32
  33 // Permission to use, copy, modify, sell, and distribute this software
  34 // is hereby granted without fee, provided that the above copyright
  35 // notice appears in all copies, and that both that copyright notice
  36 // and this permission notice appear in supporting documentation. None
  37 // of the above authors, nor IBM Haifa Research Laboratories, make any
  38 // representation about the suitability of this software for any
  39 // purpose. It is provided "as is" without express or implied
  40 // warranty.
  41
  42 /**
  43  * @file traits.hpp
  44  * Contains an implementation for bin_search_tree_.
  45  */
  46
  47 #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
  48 #define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
  49
  50 #include <ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp>
  51 #include <ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp>
  52
  53 namespace pb_ds
  54 {
  55   namespace detail
  56   {
  57
  58     template<typename Key,
  59              typename Mapped,
  60              class Cmp_Fn,
  61              template<typename Const_Node_Iterator,
  62                       class Node_Iterator,
  63                       class Cmp_Fn,
  64                       class Allocator>
  65     class Node_Update,
  66              class Node,
  67              class Allocator>
  68     struct bin_search_tree_traits
  69     {
  70     private:
  71       typedef
  72       types_traits<
  73       Key,
  74       Mapped,
  75       Allocator,
  76       false>
  77       type_traits;
  78
  79     public:
  80       typedef Node node;
  81
  82       typedef
  83       bin_search_tree_const_it_<
  84         typename Allocator::template rebind<
  85         node>::other::pointer,
  86         typename type_traits::value_type,
  87         typename type_traits::pointer,
  88         typename type_traits::const_pointer,
  89         typename type_traits::reference,
  90         typename type_traits::const_reference,
  91         true,
  92         Allocator>
  93       const_point_iterator;
  94
  95       typedef
  96       bin_search_tree_it_<
  97         typename Allocator::template rebind<
  98         node>::other::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         true,
 105         Allocator>
 106       point_iterator;
 107
 108       typedef
 109       bin_search_tree_const_it_<
 110         typename Allocator::template rebind<
 111         node>::other::pointer,
 112         typename type_traits::value_type,
 113         typename type_traits::pointer,
 114         typename type_traits::const_pointer,
 115         typename type_traits::reference,
 116         typename type_traits::const_reference,
 117         false,
 118         Allocator>
 119       const_reverse_iterator;
 120
 121       typedef
 122       bin_search_tree_it_<
 123         typename Allocator::template rebind<
 124         node>::other::pointer,
 125         typename type_traits::value_type,
 126         typename type_traits::pointer,
 127         typename type_traits::const_pointer,
 128         typename type_traits::reference,
 129         typename type_traits::const_reference,
 130         false,
 131         Allocator>
 132       reverse_iterator;
 133
 134       typedef
 135       bin_search_tree_const_node_it_<
 136         Node,
 137         const_point_iterator,
 138         point_iterator,
 139         Allocator>
 140       const_node_iterator;
 141
 142       typedef
 143       bin_search_tree_node_it_<
 144         Node,
 145         const_point_iterator,
 146         point_iterator,
 147         Allocator>
 148       node_iterator;
 149
 150       typedef
 151       Node_Update<
 152         const_node_iterator,
 153         node_iterator,
 154         Cmp_Fn,
 155         Allocator>
 156       node_update;
 157
 158       typedef
 159       pb_ds::null_tree_node_update<
 160         const_node_iterator,
 161         node_iterator,
 162         Cmp_Fn,
 163         Allocator>*
 164       null_node_update_pointer;
 165     };
 166
 167     template<typename Key,
 168              class Cmp_Fn,
 169              template<typename Const_Node_Iterator,
 170                       class Node_Iterator,
 171                       class Cmp_Fn,
 172                       class Allocator>
 173     class Node_Update,
 174              class Node,
 175              class Allocator>
 176     struct bin_search_tree_traits<
 177       Key,
 178       null_mapped_type,
 179       Cmp_Fn,
 180       Node_Update,
 181       Node,
 182       Allocator>
 183     {
 184     private:
 185       typedef
 186       types_traits<
 187       Key,
 188       null_mapped_type,
 189       Allocator,
 190       false>
 191       type_traits;
 192
 193     public:
 194       typedef Node node;
 195
 196       typedef
 197       bin_search_tree_const_it_<
 198         typename Allocator::template rebind<
 199         node>::other::pointer,
 200         typename type_traits::value_type,
 201         typename type_traits::pointer,
 202         typename type_traits::const_pointer,
 203         typename type_traits::reference,
 204         typename type_traits::const_reference,
 205         true,
 206         Allocator>
 207       const_point_iterator;
 208
 209       typedef const_point_iterator point_iterator;
 210
 211       typedef
 212       bin_search_tree_const_it_<
 213         typename Allocator::template rebind<
 214         node>::other::pointer,
 215         typename type_traits::value_type,
 216         typename type_traits::pointer,
 217         typename type_traits::const_pointer,
 218         typename type_traits::reference,
 219         typename type_traits::const_reference,
 220         false,
 221         Allocator>
 222       const_reverse_iterator;
 223
 224       typedef const_reverse_iterator reverse_iterator;
 225
 226       typedef
 227       bin_search_tree_const_node_it_<
 228         Node,
 229         const_point_iterator,
 230         point_iterator,
 231         Allocator>
 232       const_node_iterator;
 233
 234       typedef const_node_iterator node_iterator;
 235
 236       typedef
 237       Node_Update<
 238         const_node_iterator,
 239         node_iterator,
 240         Cmp_Fn,
 241         Allocator>
 242       node_update;
 243
 244       typedef
 245       pb_ds::null_tree_node_update<
 246         const_node_iterator,
 247         node_iterator,
 248         Cmp_Fn,
 249         Allocator>*
 250       null_node_update_pointer;
 251     };
 252
 253   } // namespace detail
 254 } // namespace pb_ds
 255
 256 #endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP