libstdc++
list_update_policy.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 list_update_policy.hpp
00038  * Contains policies for list update containers.
00039  */
00040 
00041 #ifndef PB_DS_LU_POLICY_HPP
00042 #define PB_DS_LU_POLICY_HPP
00043 
00044 #include <bits/c++config.h>
00045 #include <cstdlib>
00046 #include <ext/pb_ds/detail/list_update_policy/lu_counter_metadata.hpp>
00047 #include <ext/pb_ds/tag_and_trait.hpp>
00048 
00049 namespace __gnu_pbds
00050 {
00051   /**
00052    *  A list-update policy that unconditionally moves elements to the
00053    *  front of the list. A null type means that each link in a
00054    *  list-based container does not actually need metadata.
00055    */
00056  template<typename _Alloc = std::allocator<char> >
00057    class lu_move_to_front_policy
00058    {
00059    public:
00060      typedef _Alloc                                     allocator_type;
00061 
00062      /// Metadata on which this functor operates.
00063      typedef null_type                                  metadata_type;
00064 
00065    private:
00066      typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
00067 
00068    public:
00069      /// Reference to metadata on which this functor operates.
00070      typedef typename __rebind_m::other::reference      metadata_reference;
00071 
00072      /// Creates a metadata object.
00073      metadata_type
00074      operator()() const
00075      { return s_metadata; }
00076 
00077      /// Decides whether a metadata object should be moved to the front
00078      /// of the list.
00079      inline bool
00080      operator()(metadata_reference r_metadata) const
00081      { return true; }
00082 
00083    private:
00084      static null_type                                   s_metadata;
00085    };
00086 
00087   /**
00088    *  A list-update policy that moves elements to the front of the
00089    *  list based on the counter algorithm.
00090    */
00091   template<std::size_t Max_Count = 5, typename _Alloc = std::allocator<char> >
00092     class lu_counter_policy
00093     : private detail::lu_counter_policy_base<typename _Alloc::size_type>
00094     {
00095     public:
00096       typedef _Alloc                                    allocator_type;
00097       typedef typename allocator_type::size_type        size_type;
00098 
00099       enum
00100         {
00101           /// When some element is accessed this number of times, it
00102           /// will be moved to the front of the list.
00103           max_count = Max_Count
00104         };
00105 
00106       /// Metadata on which this functor operates.
00107       typedef detail::lu_counter_metadata<size_type>    metadata_type;
00108 
00109     private:
00110       typedef detail::lu_counter_policy_base<size_type>         base_type;
00111       typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
00112 
00113     public:
00114       /// Reference to metadata on which this functor operates.
00115       typedef typename __rebind_m::other::reference     metadata_reference;
00116 
00117       /// Creates a metadata object.
00118       metadata_type
00119       operator()() const
00120       { return base_type::operator()(max_count); }
00121 
00122       /// Decides whether a metadata object should be moved to the front
00123       /// of the list.
00124       bool
00125       operator()(metadata_reference r_data) const
00126       { return base_type::operator()(r_data, max_count); }
00127     };
00128 } // namespace __gnu_pbds
00129 
00130 #endif