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 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 47namespace __gnu_pbds 48{ 49 namespace detail 50 { 51 52 template<typename Key, 53 typename Mapped, 54 class Cmp_Fn, 55 template<typename Const_Node_Iterator, 56 class Node_Iterator, 57 class Cmp_Fn, 58 class Allocator> 59 class Node_Update, 60 class Node, 61 class Allocator> 62 struct bin_search_tree_traits 63 { 64 private: 65 typedef 66 types_traits< 67 Key, 68 Mapped, 69 Allocator, 70 false> 71 type_traits; 72 73 public: 74 typedef Node node; 75 76 typedef 77 bin_search_tree_const_it_< 78 typename Allocator::template rebind< 79 node>::other::pointer, 80 typename type_traits::value_type, 81 typename type_traits::pointer, 82 typename type_traits::const_pointer, 83 typename type_traits::reference, 84 typename type_traits::const_reference, 85 true, 86 Allocator> 87 const_point_iterator; 88 89 typedef 90 bin_search_tree_it_< 91 typename Allocator::template rebind< 92 node>::other::pointer, 93 typename type_traits::value_type, 94 typename type_traits::pointer, 95 typename type_traits::const_pointer, 96 typename type_traits::reference, 97 typename type_traits::const_reference, 98 true, 99 Allocator> 100 point_iterator; 101 102 typedef 103 bin_search_tree_const_it_< 104 typename Allocator::template rebind< 105 node>::other::pointer, 106 typename type_traits::value_type, 107 typename type_traits::pointer, 108 typename type_traits::const_pointer, 109 typename type_traits::reference, 110 typename type_traits::const_reference, 111 false, 112 Allocator> 113 const_reverse_iterator; 114 115 typedef 116 bin_search_tree_it_< 117 typename Allocator::template rebind< 118 node>::other::pointer, 119 typename type_traits::value_type, 120 typename type_traits::pointer, 121 typename type_traits::const_pointer, 122 typename type_traits::reference, 123 typename type_traits::const_reference, 124 false, 125 Allocator> 126 reverse_iterator; 127 128 typedef 129 bin_search_tree_const_node_it_< 130 Node, 131 const_point_iterator, 132 point_iterator, 133 Allocator> 134 const_node_iterator; 135 136 typedef 137 bin_search_tree_node_it_< 138 Node, 139 const_point_iterator, 140 point_iterator, 141 Allocator> 142 node_iterator; 143 144 typedef 145 Node_Update< 146 const_node_iterator, 147 node_iterator, 148 Cmp_Fn, 149 Allocator> 150 node_update; 151 152 typedef 153 __gnu_pbds::null_tree_node_update< 154 const_node_iterator, 155 node_iterator, 156 Cmp_Fn, 157 Allocator>* 158 null_node_update_pointer; 159 }; 160 161 template<typename Key, 162 class Cmp_Fn, 163 template<typename Const_Node_Iterator, 164 class Node_Iterator, 165 class Cmp_Fn, 166 class Allocator> 167 class Node_Update, 168 class Node, 169 class Allocator> 170 struct bin_search_tree_traits< 171 Key, 172 null_mapped_type, 173 Cmp_Fn, 174 Node_Update, 175 Node, 176 Allocator> 177 { 178 private: 179 typedef 180 types_traits< 181 Key, 182 null_mapped_type, 183 Allocator, 184 false> 185 type_traits; 186 187 public: 188 typedef Node node; 189 190 typedef 191 bin_search_tree_const_it_< 192 typename Allocator::template rebind< 193 node>::other::pointer, 194 typename type_traits::value_type, 195 typename type_traits::pointer, 196 typename type_traits::const_pointer, 197 typename type_traits::reference, 198 typename type_traits::const_reference, 199 true, 200 Allocator> 201 const_point_iterator; 202 203 typedef const_point_iterator point_iterator; 204 205 typedef 206 bin_search_tree_const_it_< 207 typename Allocator::template rebind< 208 node>::other::pointer, 209 typename type_traits::value_type, 210 typename type_traits::pointer, 211 typename type_traits::const_pointer, 212 typename type_traits::reference, 213 typename type_traits::const_reference, 214 false, 215 Allocator> 216 const_reverse_iterator; 217 218 typedef const_reverse_iterator reverse_iterator; 219 220 typedef 221 bin_search_tree_const_node_it_< 222 Node, 223 const_point_iterator, 224 point_iterator, 225 Allocator> 226 const_node_iterator; 227 228 typedef const_node_iterator node_iterator; 229 230 typedef 231 Node_Update< 232 const_node_iterator, 233 node_iterator, 234 Cmp_Fn, 235 Allocator> 236 node_update; 237 238 typedef 239 __gnu_pbds::null_tree_node_update< 240 const_node_iterator, 241 node_iterator, 242 Cmp_Fn, 243 Allocator>* 244 null_node_update_pointer; 245 }; 246 247 } // namespace detail 248} // namespace __gnu_pbds 249 250#endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP 251