libstdc++-v3/include/ext/pb_ds/list_update_policy.hpp

   1 // -*- C++ -*-
   2
   3 // Copyright (C) 2005-2014 Free Software Foundation, Inc.
   4 //
   5 // This file is part of the GNU ISO C++ Library.  This library is free
   6 // software; you can redistribute it and/or modify it under the terms
   7 // of the GNU General Public License as published by the Free Software
   8 // Foundation; either version 3, or (at your option) any later
   9 // version.
  10
  11 // This library is distributed in the hope that it will be useful, but
  12 // WITHOUT ANY WARRANTY; without even the implied warranty of
  13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
  14 // General Public License for more details.
  15
  16 // Under Section 7 of GPL version 3, you are granted additional
  17 // permissions described in the GCC Runtime Library Exception, version
  18 // 3.1, as published by the Free Software Foundation.
  19
  20 // You should have received a copy of the GNU General Public License and
  21 // a copy of the GCC Runtime Library Exception along with this program;
  22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
  23 // <http://www.gnu.org/licenses/>.
  24
  25 // Copyright (C) 2004 Ami Tavory and Vladimir Dreizin, IBM-HRL.
  26
  27 // Permission to use, copy, modify, sell, and distribute this software
  28 // is hereby granted without fee, provided that the above copyright
  29 // notice appears in all copies, and that both that copyright notice
  30 // and this permission notice appear in supporting documentation. None
  31 // of the above authors, nor IBM Haifa Research Laboratories, make any
  32 // representation about the suitability of this software for any
  33 // purpose. It is provided "as is" without express or implied
  34 // warranty.
  35
  36 /**
  37  * @file list_update_policy.hpp
  38  * Contains policies for list update containers.
  39  */
  40
  41 #ifndef PB_DS_LU_POLICY_HPP
  42 #define PB_DS_LU_POLICY_HPP
  43
  44 #include <bits/c++config.h>
  45 #include <cstdlib>
  46 #include <ext/pb_ds/detail/list_update_policy/lu_counter_metadata.hpp>
  47 #include <ext/pb_ds/tag_and_trait.hpp>
  48
  49 namespace __gnu_pbds
  50 {
  51   /**
  52    *  A list-update policy that unconditionally moves elements to the
  53    *  front of the list. A null type means that each link in a
  54    *  list-based container does not actually need metadata.
  55    */
  56  template<typename _Alloc = std::allocator<char> >
  57    class lu_move_to_front_policy
  58    {
  59    public:
  60      typedef _Alloc                                     allocator_type;
  61
  62      /// Metadata on which this functor operates.
  63      typedef null_type                                  metadata_type;
  64
  65    private:
  66      typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
  67
  68    public:
  69      /// Reference to metadata on which this functor operates.
  70      typedef typename __rebind_m::other::reference      metadata_reference;
  71
  72      /// Creates a metadata object.
  73      metadata_type
  74      operator()() const
  75      { return s_metadata; }
  76
  77      /// Decides whether a metadata object should be moved to the front
  78      /// of the list.
  79      inline bool
  80      operator()(metadata_reference r_metadata) const
  81      { return true; }
  82
  83    private:
  84      static null_type                                   s_metadata;
  85    };
  86
  87   /**
  88    *  A list-update policy that moves elements to the front of the
  89    *  list based on the counter algorithm.
  90    */
  91   template<std::size_t Max_Count = 5, typename _Alloc = std::allocator<char> >
  92     class lu_counter_policy
  93     : private detail::lu_counter_policy_base<typename _Alloc::size_type>
  94     {
  95     public:
  96       typedef _Alloc                                    allocator_type;
  97       typedef typename allocator_type::size_type        size_type;
  98
  99       enum
 100         {
 101           /// When some element is accessed this number of times, it
 102           /// will be moved to the front of the list.
 103           max_count = Max_Count
 104         };
 105
 106       /// Metadata on which this functor operates.
 107       typedef detail::lu_counter_metadata<size_type>    metadata_type;
 108
 109     private:
 110       typedef detail::lu_counter_policy_base<size_type>         base_type;
 111       typedef typename _Alloc::template rebind<metadata_type> __rebind_m;
 112
 113     public:
 114       /// Reference to metadata on which this functor operates.
 115       typedef typename __rebind_m::other::reference     metadata_reference;
 116
 117       /// Creates a metadata object.
 118       metadata_type
 119       operator()() const
 120       { return base_type::operator()(max_count); }
 121
 122       /// Decides whether a metadata object should be moved to the front
 123       /// of the list.
 124       bool
 125       operator()(metadata_reference r_data) const
 126       { return base_type::operator()(r_data, max_count); }
 127     };
 128 } // namespace __gnu_pbds
 129
 130 #endif