1 /* Copyright 2003-2013 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 <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 { entryboost::multi_index::detail::index_matcher::entry69 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 { operator ()boost::multi_index::detail::index_matcher::entry::less_by_node80 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 { operator ()boost::multi_index::detail::index_matcher::entry::less_by_pile_top94 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: algorithm_base(const Allocator & al,std::size_t size)108 algorithm_base(const Allocator& al,std::size_t size): 109 spc(al,size),size_(size),n_(0),sorted(false) 110 { 111 } 112 add(void * node)113 void add(void* node) 114 { 115 entries()[n_]=entry(node,n_); 116 ++n_; 117 } 118 begin_algorithm() const119 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 add_node_to_algorithm(void * node) const128 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 finish_algorithm() const158 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 is_ordered(void * node) const174 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: entries() const182 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: algorithm(const Allocator & al,std::size_t size)203 algorithm(const Allocator& al,std::size_t size):super(al,size){} 204 add(Node * node)205 void add(Node* node) 206 { 207 super::add(node); 208 } 209 210 template<typename IndexIterator> execute(IndexIterator first,IndexIterator last) const211 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 is_ordered(Node * node) const222 bool is_ordered(Node* node)const 223 { 224 return super::is_ordered(node); 225 } 226 227 private: add_node_to_algorithm(Node * node) const228 void add_node_to_algorithm(Node* node)const 229 { 230 super::add_node_to_algorithm(node); 231 } 232 233 template<typename IndexIterator> get_node(IndexIterator it)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 249