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
24namespace boost{
25
26namespace multi_index{
27
28namespace 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
59namespace 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
68struct 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
105template<typename Allocator>
106class algorithm_base:private noncopyable
107{
108protected:
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
182private:
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
198template<typename Node,typename Allocator>
199class algorithm:private algorithm_base<Allocator>
200{
201 typedef algorithm_base<Allocator> super;
202
203public:
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
228private:
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
250