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 { entryboost::multi_index::detail::index_matcher::entry70 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 { operator ()boost::multi_index::detail::index_matcher::entry::less_by_node81 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 { operator ()boost::multi_index::detail::index_matcher::entry::less_by_pile_top95 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: algorithm_base(const Allocator & al,std::size_t size)109 algorithm_base(const Allocator& al,std::size_t size): 110 spc(al,size),size_(size),n_(0),sorted(false) 111 { 112 } 113 add(void * node)114 void add(void* node) 115 { 116 entries()[n_]=entry(node,n_); 117 ++n_; 118 } 119 begin_algorithm() const120 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 add_node_to_algorithm(void * node) const129 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 finish_algorithm() const159 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 is_ordered(void * node) const175 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: entries() const183 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: algorithm(const Allocator & al,std::size_t size)204 algorithm(const Allocator& al,std::size_t size):super(al,size){} 205 add(Node * node)206 void add(Node* node) 207 { 208 super::add(node); 209 } 210 211 template<typename IndexIterator> execute(IndexIterator first,IndexIterator last) const212 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 is_ordered(Node * node) const223 bool is_ordered(Node* node)const 224 { 225 return super::is_ordered(node); 226 } 227 228 private: add_node_to_algorithm(Node * node) const229 void add_node_to_algorithm(Node* node)const 230 { 231 super::add_node_to_algorithm(node); 232 } 233 234 template<typename IndexIterator> get_node(IndexIterator it)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 250