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
23namespace boost{
24
25namespace multi_index{
26
27namespace 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
58namespace 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
67struct 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
104template<typename Allocator>
105class algorithm_base:private noncopyable
106{
107protected:
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
181private:
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
197template<typename Node,typename Allocator>
198class algorithm:private algorithm_base<Allocator>
199{
200 typedef algorithm_base<Allocator> super;
201
202public:
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
227private:
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
249