libstdc++
ov_tree_map_/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 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