ceph/src/boost/libs/multi_index/include/boost/multi_index/detail/index_matcher.hpp

   1 /* Copyright 2003-2015 Joaquin M Lopez Munoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/multi_index for library home page.
   7  */
   8
   9 #ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP
  11
  12 #if defined(_MSC_VER)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  17 #include <algorithm>
  18 #include <boost/noncopyable.hpp>
  19 #include <boost/multi_index/detail/auto_space.hpp>
  20 #include <boost/multi_index/detail/raw_ptr.hpp>
  21 #include <cstddef>
  22 #include <functional>
  23
  24 namespace boost{
  25
  26 namespace multi_index{
  27
  28 namespace detail{
  29
  30 /* index_matcher compares a sequence of elements against a
  31  * base sequence, identifying those elements that belong to the
  32  * longest subsequence which is ordered with respect to the base.
  33  * For instance, if the base sequence is:
  34  *
  35  *   0 1 2 3 4 5 6 7 8 9
  36  *
  37  * and the compared sequence (not necesarilly the same length):
  38  *
  39  *   1 4 2 3 0 7 8 9
  40  *
  41  * the elements of the longest ordered subsequence are:
  42  *
  43  *   1 2 3 7 8 9
  44  *
  45  * The algorithm for obtaining such a subsequence is called
  46  * Patience Sorting, described in ch. 1 of:
  47  *   Aldous, D., Diaconis, P.: "Longest increasing subsequences: from
  48  *   patience sorting to the Baik-Deift-Johansson Theorem", Bulletin
  49  *   of the American Mathematical Society, vol. 36, no 4, pp. 413-432,
  50  *   July 1999.
  51  *   http://www.ams.org/bull/1999-36-04/S0273-0979-99-00796-X/
  52  *   S0273-0979-99-00796-X.pdf
  53  *
  54  * This implementation is not fully generic since it assumes that
  55  * the sequences given are pointed to by index iterators (having a
  56  * get_node() memfun.)
  57  */
  58
  59 namespace index_matcher{
  60
  61 /* The algorithm stores the nodes of the base sequence and a number
  62  * of "piles" that are dynamically updated during the calculation
  63  * stage. From a logical point of view, nodes form an independent
  64  * sequence from piles. They are stored together so as to minimize
  65  * allocated memory.
  66  */
  67
  68 struct entry
  69 {
  70   entry(void* node_,std::size_t pos_=0):node(node_),pos(pos_){}
  71
  72   /* node stuff */
  73
  74   void*       node;
  75   std::size_t pos;
  76   entry*      previous;
  77   bool        ordered;
  78
  79   struct less_by_node
  80   {
  81     bool operator()(
  82       const entry& x,const entry& y)const
  83     {
  84       return std::less<void*>()(x.node,y.node);
  85     }
  86   };
  87
  88   /* pile stuff */
  89
  90   std::size_t pile_top;
  91   entry*      pile_top_entry;
  92
  93   struct less_by_pile_top
  94   {
  95     bool operator()(
  96       const entry& x,const entry& y)const
  97     {
  98       return x.pile_top<y.pile_top;
  99     }
 100   };
 101 };
 102
 103 /* common code operating on void *'s */
 104
 105 template<typename Allocator>
 106 class algorithm_base:private noncopyable
 107 {
 108 protected:
 109   algorithm_base(const Allocator& al,std::size_t size):
 110     spc(al,size),size_(size),n_(0),sorted(false)
 111   {
 112   }
 113
 114   void add(void* node)
 115   {
 116     entries()[n_]=entry(node,n_);
 117     ++n_;
 118   }
 119
 120   void begin_algorithm()const
 121   {
 122     if(!sorted){
 123       std::sort(entries(),entries()+size_,entry::less_by_node());
 124       sorted=true;
 125     }
 126     num_piles=0;
 127   }
 128
 129   void add_node_to_algorithm(void* node)const
 130   {
 131     entry* ent=
 132       std::lower_bound(
 133         entries(),entries()+size_,
 134         entry(node),entry::less_by_node()); /* localize entry */
 135     ent->ordered=false;
 136     std::size_t n=ent->pos;                 /* get its position */
 137
 138     entry dummy(0);
 139     dummy.pile_top=n;
 140
 141     entry* pile_ent=                        /* find the first available pile */
 142       std::lower_bound(                     /* to stack the entry            */
 143         entries(),entries()+num_piles,
 144         dummy,entry::less_by_pile_top());
 145
 146     pile_ent->pile_top=n;                   /* stack the entry */
 147     pile_ent->pile_top_entry=ent;
 148
 149     /* if not the first pile, link entry to top of the preceding pile */
 150     if(pile_ent>&entries()[0]){
 151       ent->previous=(pile_ent-1)->pile_top_entry;
 152     }
 153
 154     if(pile_ent==&entries()[num_piles]){    /* new pile? */
 155       ++num_piles;
 156     }
 157   }
 158
 159   void finish_algorithm()const
 160   {
 161     if(num_piles>0){
 162       /* Mark those elements which are in their correct position, i.e. those
 163        * belonging to the longest increasing subsequence. These are those
 164        * elements linked from the top of the last pile.
 165        */
 166
 167       entry* ent=entries()[num_piles-1].pile_top_entry;
 168       for(std::size_t n=num_piles;n--;){
 169         ent->ordered=true;
 170         ent=ent->previous;
 171       }
 172     }
 173   }
 174
 175   bool is_ordered(void * node)const
 176   {
 177     return std::lower_bound(
 178       entries(),entries()+size_,
 179       entry(node),entry::less_by_node())->ordered;
 180   }
 181
 182 private:
 183   entry* entries()const{return raw_ptr<entry*>(spc.data());}
 184
 185   auto_space<entry,Allocator> spc;
 186   std::size_t                 size_;
 187   std::size_t                 n_;
 188   mutable bool                sorted;
 189   mutable std::size_t         num_piles;
 190 };
 191
 192 /* The algorithm has three phases:
 193  *   - Initialization, during which the nodes of the base sequence are added.
 194  *   - Execution.
 195  *   - Results querying, through the is_ordered memfun.
 196  */
 197
 198 template<typename Node,typename Allocator>
 199 class algorithm:private algorithm_base<Allocator>
 200 {
 201   typedef algorithm_base<Allocator> super;
 202
 203 public:
 204   algorithm(const Allocator& al,std::size_t size):super(al,size){}
 205
 206   void add(Node* node)
 207   {
 208     super::add(node);
 209   }
 210
 211   template<typename IndexIterator>
 212   void execute(IndexIterator first,IndexIterator last)const
 213   {
 214     super::begin_algorithm();
 215
 216     for(IndexIterator it=first;it!=last;++it){
 217       add_node_to_algorithm(get_node(it));
 218     }
 219
 220     super::finish_algorithm();
 221   }
 222
 223   bool is_ordered(Node* node)const
 224   {
 225     return super::is_ordered(node);
 226   }
 227
 228 private:
 229   void add_node_to_algorithm(Node* node)const
 230   {
 231     super::add_node_to_algorithm(node);
 232   }
 233
 234   template<typename IndexIterator>
 235   static Node* get_node(IndexIterator it)
 236   {
 237     return static_cast<Node*>(it.get_node());
 238   }
 239 };
 240
 241 } /* namespace multi_index::detail::index_matcher */
 242
 243 } /* namespace multi_index::detail */
 244
 245 } /* namespace multi_index */
 246
 247 } /* namespace boost */
 248
 249 #endif