libstdc++
traits.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005-2015 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 bin_search_tree_/traits.hpp
00038  * Contains an implementation for bin_search_tree_.
00039  */
00040 
00041 #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
00042 #define PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP
00043 
00044 #include <ext/pb_ds/detail/bin_search_tree_/point_iterators.hpp>
00045 #include <ext/pb_ds/detail/bin_search_tree_/node_iterators.hpp>
00046 
00047 namespace __gnu_pbds
00048 {
00049   namespace detail
00050   {
00051     /// Binary search tree traits, primary template
00052     /// @ingroup traits
00053     template<typename Key,
00054              typename Mapped,
00055              class Cmp_Fn,
00056              template<typename Node_CItr,
00057                       class Node_Itr,
00058                       class _Cmp_Fn,
00059                       typename _Alloc>
00060              class Node_Update,
00061              class Node,
00062              typename _Alloc>
00063     struct bin_search_tree_traits
00064     {
00065     private:
00066       typedef types_traits<Key, Mapped, _Alloc, false> type_traits;
00067 
00068     public:
00069       typedef Node node;
00070 
00071       typedef
00072       bin_search_tree_const_it_<
00073         typename _Alloc::template rebind<
00074         node>::other::pointer,
00075         typename type_traits::value_type,
00076         typename type_traits::pointer,
00077         typename type_traits::const_pointer,
00078         typename type_traits::reference,
00079         typename type_traits::const_reference,
00080         true,
00081         _Alloc>
00082       point_const_iterator;
00083 
00084       typedef
00085       bin_search_tree_it_<
00086         typename _Alloc::template rebind<
00087         node>::other::pointer,
00088         typename type_traits::value_type,
00089         typename type_traits::pointer,
00090         typename type_traits::const_pointer,
00091         typename type_traits::reference,
00092         typename type_traits::const_reference,
00093         true,
00094         _Alloc>
00095       point_iterator;
00096 
00097       typedef
00098       bin_search_tree_const_it_<
00099         typename _Alloc::template rebind<
00100         node>::other::pointer,
00101         typename type_traits::value_type,
00102         typename type_traits::pointer,
00103         typename type_traits::const_pointer,
00104         typename type_traits::reference,
00105         typename type_traits::const_reference,
00106         false,
00107         _Alloc>
00108       const_reverse_iterator;
00109 
00110       typedef
00111       bin_search_tree_it_<
00112         typename _Alloc::template rebind<
00113         node>::other::pointer,
00114         typename type_traits::value_type,
00115         typename type_traits::pointer,
00116         typename type_traits::const_pointer,
00117         typename type_traits::reference,
00118         typename type_traits::const_reference,
00119         false,
00120         _Alloc>
00121       reverse_iterator;
00122 
00123       /// This is an iterator to an iterator: it iterates over nodes,
00124       /// and de-referencing it returns one of the tree's iterators.
00125       typedef
00126       bin_search_tree_const_node_it_<
00127         Node,
00128         point_const_iterator,
00129         point_iterator,
00130         _Alloc>
00131       node_const_iterator;
00132 
00133       typedef
00134       bin_search_tree_node_it_<
00135         Node,
00136         point_const_iterator,
00137         point_iterator,
00138         _Alloc>
00139       node_iterator;
00140 
00141       typedef
00142       Node_Update<
00143         node_const_iterator,
00144         node_iterator,
00145         Cmp_Fn,
00146         _Alloc>
00147       node_update;
00148 
00149       typedef
00150       __gnu_pbds::null_node_update<
00151         node_const_iterator,
00152         node_iterator,
00153         Cmp_Fn,
00154         _Alloc>* 
00155       null_node_update_pointer;
00156     };
00157 
00158     /// Specialization.
00159     /// @ingroup traits
00160     template<typename Key,
00161              class Cmp_Fn,
00162              template<typename Node_CItr,
00163                       class Node_Itr,
00164                       class _Cmp_Fn,
00165                       typename _Alloc>
00166              class Node_Update,
00167              class Node,
00168              typename _Alloc>
00169     struct bin_search_tree_traits<
00170       Key,
00171       null_type,
00172       Cmp_Fn,
00173       Node_Update,
00174       Node,
00175       _Alloc>
00176     {
00177     private:
00178       typedef types_traits<Key, null_type, _Alloc, false> type_traits;
00179 
00180     public:
00181       typedef Node node;
00182 
00183       typedef
00184       bin_search_tree_const_it_<
00185         typename _Alloc::template rebind<
00186         node>::other::pointer,
00187         typename type_traits::value_type,
00188         typename type_traits::pointer,
00189         typename type_traits::const_pointer,
00190         typename type_traits::reference,
00191         typename type_traits::const_reference,
00192         true,
00193         _Alloc>
00194       point_const_iterator;
00195 
00196       typedef point_const_iterator point_iterator;
00197 
00198       typedef
00199       bin_search_tree_const_it_<
00200         typename _Alloc::template rebind<
00201         node>::other::pointer,
00202         typename type_traits::value_type,
00203         typename type_traits::pointer,
00204         typename type_traits::const_pointer,
00205         typename type_traits::reference,
00206         typename type_traits::const_reference,
00207         false,
00208         _Alloc>
00209       const_reverse_iterator;
00210 
00211       typedef const_reverse_iterator reverse_iterator;
00212 
00213       /// This is an iterator to an iterator: it iterates over nodes,
00214       /// and de-referencing it returns one of the tree's iterators.
00215       typedef
00216       bin_search_tree_const_node_it_<
00217         Node,
00218         point_const_iterator,
00219         point_iterator,
00220         _Alloc>
00221       node_const_iterator;
00222 
00223       typedef node_const_iterator node_iterator;
00224 
00225       typedef
00226       Node_Update<node_const_iterator, node_iterator, Cmp_Fn, _Alloc>
00227       node_update;
00228 
00229       typedef
00230       __gnu_pbds::null_node_update<
00231         node_const_iterator,
00232         node_iterator,
00233         Cmp_Fn,
00234         _Alloc>* 
00235       null_node_update_pointer;
00236     };
00237 
00238   } // namespace detail
00239 } // namespace __gnu_pbds
00240 
00241 #endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP