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
00170     bin_search_tree_traits<Key, null_type, Cmp_Fn, Node_Update, Node, _Alloc>
00171     {
00172     private:
00173       typedef types_traits<Key, null_type, _Alloc, false> type_traits;
00174 
00175     public:
00176       typedef Node node;
00177 
00178       typedef
00179       bin_search_tree_const_it_<
00180         typename _Alloc::template rebind<
00181         node>::other::pointer,
00182         typename type_traits::value_type,
00183         typename type_traits::pointer,
00184         typename type_traits::const_pointer,
00185         typename type_traits::reference,
00186         typename type_traits::const_reference,
00187         true,
00188         _Alloc>
00189       point_const_iterator;
00190 
00191       typedef point_const_iterator point_iterator;
00192 
00193       typedef
00194       bin_search_tree_const_it_<
00195         typename _Alloc::template rebind<
00196         node>::other::pointer,
00197         typename type_traits::value_type,
00198         typename type_traits::pointer,
00199         typename type_traits::const_pointer,
00200         typename type_traits::reference,
00201         typename type_traits::const_reference,
00202         false,
00203         _Alloc>
00204       const_reverse_iterator;
00205 
00206       typedef const_reverse_iterator reverse_iterator;
00207 
00208       /// This is an iterator to an iterator: it iterates over nodes,
00209       /// and de-referencing it returns one of the tree's iterators.
00210       typedef
00211       bin_search_tree_const_node_it_<
00212         Node,
00213         point_const_iterator,
00214         point_iterator,
00215         _Alloc>
00216       node_const_iterator;
00217 
00218       typedef node_const_iterator node_iterator;
00219 
00220       typedef
00221       Node_Update<node_const_iterator, node_iterator, Cmp_Fn, _Alloc>
00222       node_update;
00223 
00224       typedef
00225       __gnu_pbds::null_node_update<
00226         node_const_iterator,
00227         node_iterator,
00228         Cmp_Fn,
00229         _Alloc>* 
00230       null_node_update_pointer;
00231     };
00232 
00233   } // namespace detail
00234 } // namespace __gnu_pbds
00235 
00236 #endif // #ifndef PB_DS_BIN_SEARCH_TREE_NODE_AND_IT_TRAITS_HPP