libstdc++
bin_search_tree_/traits.hpp
Go to the documentation of this file.
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 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