boost_ext/boost/multi_index/detail/index_matcher.hpp

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