multi_index/detail/index_matcher.hpp

0001 /* Copyright 2003-2022 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/multi_index for library home page.
0007  */
0008
0009 #ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP
0010 #define BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP
0011
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015
0016 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
0017 #include <algorithm>
0018 #include <boost/core/noncopyable.hpp>
0019 #include <boost/multi_index/detail/auto_space.hpp>
0020 #include <boost/multi_index/detail/raw_ptr.hpp>
0021 #include <cstddef>
0022 #include <functional>
0023
0024 namespace boost{
0025
0026 namespace multi_index{
0027
0028 namespace detail{
0029
0030 /* index_matcher compares a sequence of elements against a
0031  * base sequence, identifying those elements that belong to the
0032  * longest subsequence which is ordered with respect to the base.
0033  * For instance, if the base sequence is:
0034  *
0035  *   0 1 2 3 4 5 6 7 8 9
0036  *
0037  * and the compared sequence (not necesarilly the same length):
0038  *
0039  *   1 4 2 3 0 7 8 9
0040  *
0041  * the elements of the longest ordered subsequence are:
0042  *
0043  *   1 2 3 7 8 9
0044  *
0045  * The algorithm for obtaining such a subsequence is called
0046  * Patience Sorting, described in ch. 1 of:
0047  *   Aldous, D., Diaconis, P.: "Longest increasing subsequences: from
0048  *   patience sorting to the Baik-Deift-Johansson Theorem", Bulletin
0049  *   of the American Mathematical Society, vol. 36, no 4, pp. 413-432,
0050  *   July 1999.
0051  *   http://www.ams.org/bull/1999-36-04/S0273-0979-99-00796-X/
0052  *   S0273-0979-99-00796-X.pdf
0053  *
0054  * This implementation is not fully generic since it assumes that
0055  * the sequences given are pointed to by index iterators (having a
0056  * get_node() memfun.)
0057  */
0058
0059 namespace index_matcher{
0060
0061 /* The algorithm stores the nodes of the base sequence and a number
0062  * of "piles" that are dynamically updated during the calculation
0063  * stage. From a logical point of view, nodes form an independent
0064  * sequence from piles. They are stored together so as to minimize
0065  * allocated memory.
0066  */
0067
0068 struct entry
0069 {
0070   entry(void* node_,std::size_t pos_=0):node(node_),pos(pos_){}
0071
0072   /* node stuff */
0073
0074   void*       node;
0075   std::size_t pos;
0076   entry*      previous;
0077   bool        ordered;
0078
0079   struct less_by_node
0080   {
0081     bool operator()(
0082       const entry& x,const entry& y)const
0083     {
0084       return std::less<void*>()(x.node,y.node);
0085     }
0086   };
0087
0088   /* pile stuff */
0089
0090   std::size_t pile_top;
0091   entry*      pile_top_entry;
0092
0093   struct less_by_pile_top
0094   {
0095     bool operator()(
0096       const entry& x,const entry& y)const
0097     {
0098       return x.pile_top<y.pile_top;
0099     }
0100   };
0101 };
0102
0103 /* common code operating on void *'s */
0104
0105 template<typename Allocator>
0106 class algorithm_base:private noncopyable
0107 {
0108 protected:
0109   algorithm_base(const Allocator& al,std::size_t size):
0110     spc(al,size),size_(size),n_(0),sorted(false)
0111   {
0112   }
0113
0114   void add(void* node)
0115   {
0116     entries()[n_]=entry(node,n_);
0117     ++n_;
0118   }
0119
0120   void begin_algorithm()const
0121   {
0122     if(!sorted){
0123       std::sort(entries(),entries()+size_,entry::less_by_node());
0124       sorted=true;
0125     }
0126     num_piles=0;
0127   }
0128
0129   void add_node_to_algorithm(void* node)const
0130   {
0131     entry* ent=
0132       std::lower_bound(
0133         entries(),entries()+size_,
0134         entry(node),entry::less_by_node()); /* localize entry */
0135     ent->ordered=false;
0136     std::size_t n=ent->pos;                 /* get its position */
0137
0138     entry dummy(0);
0139     dummy.pile_top=n;
0140
0141     entry* pile_ent=                        /* find the first available pile */
0142       std::lower_bound(                     /* to stack the entry            */
0143         entries(),entries()+num_piles,
0144         dummy,entry::less_by_pile_top());
0145
0146     pile_ent->pile_top=n;                   /* stack the entry */
0147     pile_ent->pile_top_entry=ent;
0148
0149     /* if not the first pile, link entry to top of the preceding pile */
0150     if(pile_ent>&entries()[0]){
0151       ent->previous=(pile_ent-1)->pile_top_entry;
0152     }
0153
0154     if(pile_ent==&entries()[num_piles]){    /* new pile? */
0155       ++num_piles;
0156     }
0157   }
0158
0159   void finish_algorithm()const
0160   {
0161     if(num_piles>0){
0162       /* Mark those elements which are in their correct position, i.e. those
0163        * belonging to the longest increasing subsequence. These are those
0164        * elements linked from the top of the last pile.
0165        */
0166
0167       entry* ent=entries()[num_piles-1].pile_top_entry;
0168       for(std::size_t n=num_piles;n--;){
0169         ent->ordered=true;
0170         ent=ent->previous;
0171       }
0172     }
0173   }
0174
0175   bool is_ordered(void * node)const
0176   {
0177     return std::lower_bound(
0178       entries(),entries()+size_,
0179       entry(node),entry::less_by_node())->ordered;
0180   }
0181
0182 private:
0183   entry* entries()const{return raw_ptr<entry*>(spc.data());}
0184
0185   auto_space<entry,Allocator> spc;
0186   std::size_t                 size_;
0187   std::size_t                 n_;
0188   mutable bool                sorted;
0189   mutable std::size_t         num_piles;
0190 };
0191
0192 /* The algorithm has three phases:
0193  *   - Initialization, during which the nodes of the base sequence are added.
0194  *   - Execution.
0195  *   - Results querying, through the is_ordered memfun.
0196  */
0197
0198 template<typename Node,typename Allocator>
0199 class algorithm:private algorithm_base<Allocator>
0200 {
0201   typedef algorithm_base<Allocator> super;
0202
0203 public:
0204   algorithm(const Allocator& al,std::size_t size):super(al,size){}
0205
0206   void add(Node* node)
0207   {
0208     super::add(node);
0209   }
0210
0211   template<typename IndexIterator>
0212   void execute(IndexIterator first,IndexIterator last)const
0213   {
0214     super::begin_algorithm();
0215
0216     for(IndexIterator it=first;it!=last;++it){
0217       add_node_to_algorithm(get_node(it));
0218     }
0219
0220     super::finish_algorithm();
0221   }
0222
0223   bool is_ordered(Node* node)const
0224   {
0225     return super::is_ordered(node);
0226   }
0227
0228 private:
0229   void add_node_to_algorithm(Node* node)const
0230   {
0231     super::add_node_to_algorithm(node);
0232   }
0233
0234   template<typename IndexIterator>
0235   static Node* get_node(IndexIterator it)
0236   {
0237     return static_cast<Node*>(it.get_node());
0238   }
0239 };
0240
0241 } /* namespace multi_index::detail::index_matcher */
0242
0243 } /* namespace multi_index::detail */
0244
0245 } /* namespace multi_index */
0246
0247 } /* namespace boost */
0248
0249 #endif