libstdc++
|
00001 // -*- C++ -*- 00002 00003 // Copyright (C) 2005, 2006, 2009 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the terms 00007 // of the GNU General Public License as published by the Free Software 00008 // Foundation; either version 3, or (at your option) any later 00009 // version. 00010 00011 // This library is distributed in the hope that it will be useful, but 00012 // WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU 00014 // General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL. 00026 00027 // Permission to use, copy, modify, sell, and distribute this software 00028 // is hereby granted without fee, provided that the above copyright 00029 // notice appears in all copies, and that both that copyright notice 00030 // and this permission notice appear in supporting documentation. None 00031 // of the above authors, nor IBM Haifa Research Laboratories, make any 00032 // representation about the suitability of this software for any 00033 // purpose. It is provided "as is" without express or implied 00034 // warranty. 00035 00036 /** 00037 * @file ov_tree_map_/traits.hpp 00038 * Contains an implementation class for ov_tree_. 00039 */ 00040 00041 #ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP 00042 #define PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP 00043 00044 #include <ext/pb_ds/detail/ov_tree_map_/node_iterators.hpp> 00045 00046 namespace __gnu_pbds 00047 { 00048 namespace detail 00049 { 00050 /// Tree traits. 00051 /// @ingroup traits 00052 template<typename Key, 00053 typename Mapped, 00054 class Cmp_Fn, 00055 template<typename Node_CItr, 00056 class Node_Itr, 00057 class Cmp_Fn_, 00058 typename _Alloc_> 00059 class Node_Update, 00060 typename _Alloc> 00061 struct tree_traits< 00062 Key, 00063 Mapped, 00064 Cmp_Fn, 00065 Node_Update, 00066 ov_tree_tag, 00067 _Alloc> 00068 { 00069 private: 00070 typedef 00071 typename types_traits< 00072 Key, 00073 Mapped, 00074 _Alloc, 00075 false>::value_type 00076 value_type; 00077 00078 public: 00079 typedef 00080 typename tree_node_metadata_dispatch< 00081 Key, 00082 Mapped, 00083 Cmp_Fn, 00084 Node_Update, 00085 _Alloc>::type 00086 metadata_type; 00087 00088 /// This is an iterator to an iterator: it iterates over nodes, 00089 /// and de-referencing it returns one of the tree's iterators. 00090 typedef 00091 ov_tree_node_const_it_< 00092 value_type, 00093 metadata_type, 00094 _Alloc> 00095 node_const_iterator; 00096 00097 typedef 00098 ov_tree_node_it_< 00099 value_type, 00100 metadata_type, 00101 _Alloc> 00102 node_iterator; 00103 00104 typedef 00105 Node_Update< 00106 node_const_iterator, 00107 node_iterator, 00108 Cmp_Fn, 00109 _Alloc> 00110 node_update; 00111 00112 typedef 00113 __gnu_pbds::null_node_update< 00114 node_const_iterator, 00115 node_iterator, 00116 Cmp_Fn, 00117 _Alloc>* 00118 null_node_update_pointer; 00119 }; 00120 00121 00122 /// Specialization. 00123 /// @ingroup traits 00124 template<typename Key, 00125 class Cmp_Fn, 00126 template<typename Node_CItr, 00127 class Node_Itr, 00128 class Cmp_Fn_, 00129 typename _Alloc_> 00130 class Node_Update, 00131 typename _Alloc> 00132 struct tree_traits< 00133 Key, 00134 null_type, 00135 Cmp_Fn, 00136 Node_Update, 00137 ov_tree_tag, 00138 _Alloc> 00139 { 00140 private: 00141 typedef 00142 typename types_traits< 00143 Key, 00144 null_type, 00145 _Alloc, 00146 false>::value_type 00147 value_type; 00148 00149 public: 00150 typedef 00151 typename tree_node_metadata_dispatch< 00152 Key, 00153 null_type, 00154 Cmp_Fn, 00155 Node_Update, 00156 _Alloc>::type 00157 metadata_type; 00158 00159 /// This is an iterator to an iterator: it iterates over nodes, 00160 /// and de-referencing it returns one of the tree's iterators. 00161 typedef 00162 ov_tree_node_const_it_< 00163 value_type, 00164 metadata_type, 00165 _Alloc> 00166 node_const_iterator; 00167 00168 typedef node_const_iterator node_iterator; 00169 00170 typedef 00171 Node_Update< 00172 node_const_iterator, 00173 node_const_iterator, 00174 Cmp_Fn, 00175 _Alloc> 00176 node_update; 00177 00178 typedef 00179 __gnu_pbds::null_node_update< 00180 node_const_iterator, 00181 node_iterator, 00182 Cmp_Fn, 00183 _Alloc>* 00184 null_node_update_pointer; 00185 }; 00186 } // namespace detail 00187 } // namespace __gnu_pbds 00188 00189 #endif // #ifndef PB_DS_OV_TREE_NODE_AND_IT_TRAITS_HPP 00190