libstdc++
list_update_policy.hpp
Go to the documentation of this file.
00001 // -*- C++ -*-
00002 
00003 // Copyright (C) 2005, 2006, 2007, 2009, 2010
00004 // Free Software Foundation, Inc.
00005 //
00006 // This file is part of the GNU ISO C++ Library.  This library is free
00007 // software; you can redistribute it and/or modify it under the terms
00008 // of the GNU General Public License as published by the Free Software
00009 // Foundation; either version 3, or (at your option) any later
00010 // version.
00011 
00012 // This library is distributed in the hope that it will be useful, but
00013 // WITHOUT ANY WARRANTY; without even the implied warranty of
00014 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00015 // General Public License for more details.
00016 
00017 // Under Section 7 of GPL version 3, you are granted additional
00018 // permissions described in the GCC Runtime Library Exception, version
00019 // 3.1, as published by the Free Software Foundation.
00020 
00021 // You should have received a copy of the GNU General Public License and
00022 // a copy of the GCC Runtime Library Exception along with this program;
00023 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
00024 // <http://www.gnu.org/licenses/>.
00025 
00026 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
00027 
00028 // Permission to use, copy, modify, sell, and distribute this software
00029 // is hereby granted without fee, provided that the above copyright
00030 // notice appears in all copies, and that both that copyright notice
00031 // and this permission notice appear in supporting documentation. None
00032 // of the above authors, nor IBM Haifa Research Laboratories, make any
00033 // representation about the suitability of this software for any
00034 // purpose. It is provided "as is" without express or implied
00035 // warranty.
00036 
00037 /**
00038  * @file list_update_policy.hpp
00039  * Contains policies for list update containers.
00040  */
00041 
00042 #ifndef PB_DS_LU_POLICY_HPP
00043 #define PB_DS_LU_POLICY_HPP
00044 
00045 #include <bits/c++config.h>
00046 #include <cstdlib>
00047 #include <ext/pb_ds/detail/list_update_policy/counter_lu_metadata.hpp>
00048 
00049 namespace __gnu_pbds
00050 {
00051   // A null type that means that each link in a list-based container
00052   // does not actually need metadata.
00053   struct null_lu_metadata
00054   { };
00055 
00056 #define PB_DS_CLASS_T_DEC template<typename Allocator>
00057 #define PB_DS_CLASS_C_DEC move_to_front_lu_policy<Allocator>
00058 
00059   // A list-update policy that unconditionally moves elements to the
00060   // front of the list.
00061   template<typename Allocator = std::allocator<char> >
00062   class move_to_front_lu_policy
00063   {
00064   public:
00065     typedef Allocator allocator_type;
00066       
00067     // Metadata on which this functor operates.
00068     typedef null_lu_metadata metadata_type;
00069       
00070     // Reference to metadata on which this functor operates.
00071     typedef typename allocator_type::template rebind<metadata_type>::other metadata_rebind;
00072     typedef typename metadata_rebind::reference metadata_reference;
00073       
00074     // Creates a metadata object.
00075     metadata_type
00076     operator()() const;
00077       
00078     // Decides whether a metadata object should be moved to the front
00079     // of the list.
00080     inline bool
00081     operator()(metadata_reference r_metadata) const;
00082       
00083   private:
00084     static null_lu_metadata s_metadata;
00085   };
00086   
00087 #include <ext/pb_ds/detail/list_update_policy/mtf_lu_policy_imp.hpp>
00088 
00089 #undef PB_DS_CLASS_T_DEC
00090 #undef PB_DS_CLASS_C_DEC
00091 
00092 #define PB_DS_CLASS_T_DEC template<std::size_t Max_Count, class Allocator>
00093 #define PB_DS_CLASS_C_DEC counter_lu_policy<Max_Count, Allocator>
00094 
00095   // A list-update policy that moves elements to the front of the list
00096   // based on the counter algorithm.
00097   template<std::size_t Max_Count = 5,
00098        typename Allocator = std::allocator<char> >
00099   class counter_lu_policy 
00100   : private detail::counter_lu_policy_base<typename Allocator::size_type>
00101   {
00102   public:
00103     typedef Allocator allocator_type;
00104 
00105     enum
00106       {
00107     max_count = Max_Count
00108       };
00109 
00110     typedef typename allocator_type::size_type size_type;
00111 
00112     // Metadata on which this functor operates.
00113     typedef detail::counter_lu_metadata<size_type> metadata_type;
00114 
00115     // Reference to metadata on which this functor operates.
00116     typedef typename Allocator::template rebind<metadata_type>::other metadata_rebind;
00117     typedef typename metadata_rebind::reference metadata_reference;
00118 
00119     // Creates a metadata object.
00120     metadata_type
00121     operator()() const;
00122 
00123     // Decides whether a metadata object should be moved to the front
00124     // of the list.
00125     bool
00126     operator()(metadata_reference r_metadata) const;
00127 
00128   private:
00129     typedef detail::counter_lu_policy_base<typename Allocator::size_type> base_type;
00130   };
00131 
00132 #include <ext/pb_ds/detail/list_update_policy/counter_lu_policy_imp.hpp>
00133 
00134 #undef PB_DS_CLASS_T_DEC
00135 #undef PB_DS_CLASS_C_DEC
00136 
00137 } // namespace __gnu_pbds
00138 
00139 #endif