williamr@2
|
1 |
/* Copyright 2003-2005 Joaquín M López Muñoz.
|
williamr@2
|
2 |
* Distributed under the Boost Software License, Version 1.0.
|
williamr@2
|
3 |
* (See accompanying file LICENSE_1_0.txt or copy at
|
williamr@2
|
4 |
* http://www.boost.org/LICENSE_1_0.txt)
|
williamr@2
|
5 |
*
|
williamr@2
|
6 |
* See http://www.boost.org/libs/multi_index for library home page.
|
williamr@2
|
7 |
*/
|
williamr@2
|
8 |
|
williamr@2
|
9 |
#ifndef BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP
|
williamr@2
|
10 |
#define BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_HPP
|
williamr@2
|
11 |
|
williamr@2
|
12 |
#if defined(_MSC_VER)&&(_MSC_VER>=1200)
|
williamr@2
|
13 |
#pragma once
|
williamr@2
|
14 |
#endif
|
williamr@2
|
15 |
|
williamr@2
|
16 |
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
|
williamr@2
|
17 |
#include <algorithm>
|
williamr@2
|
18 |
#include <boost/noncopyable.hpp>
|
williamr@2
|
19 |
#include <boost/multi_index/detail/auto_space.hpp>
|
williamr@2
|
20 |
#include <cstddef>
|
williamr@2
|
21 |
#include <functional>
|
williamr@2
|
22 |
|
williamr@2
|
23 |
namespace boost{
|
williamr@2
|
24 |
|
williamr@2
|
25 |
namespace multi_index{
|
williamr@2
|
26 |
|
williamr@2
|
27 |
namespace detail{
|
williamr@2
|
28 |
|
williamr@2
|
29 |
/* index_matcher compares a sequence of elements against a
|
williamr@2
|
30 |
* base sequence, identifying those elements that belong to the
|
williamr@2
|
31 |
* longest subsequence which is ordered with respect to the base.
|
williamr@2
|
32 |
* For instance, if the base sequence is:
|
williamr@2
|
33 |
*
|
williamr@2
|
34 |
* 0 1 2 3 4 5 6 7 8 9
|
williamr@2
|
35 |
*
|
williamr@2
|
36 |
* and the compared sequence (not necesarilly the same length):
|
williamr@2
|
37 |
*
|
williamr@2
|
38 |
* 1 4 2 3 0 7 8 9
|
williamr@2
|
39 |
*
|
williamr@2
|
40 |
* the elements of the longest ordered subsequence are:
|
williamr@2
|
41 |
*
|
williamr@2
|
42 |
* 1 2 3 7 8 9
|
williamr@2
|
43 |
*
|
williamr@2
|
44 |
* The algorithm for obtaining such a subsequence is called
|
williamr@2
|
45 |
* Patience Sorting, described in ch. 1 of:
|
williamr@2
|
46 |
* Aldous, D., Diaconis, P.: "Longest increasing subsequences: from
|
williamr@2
|
47 |
* patience sorting to the Baik-Deift-Johansson Theorem", Bulletin
|
williamr@2
|
48 |
* of the American Mathematical Society, vol. 36, no 4, pp. 413-432,
|
williamr@2
|
49 |
* July 1999.
|
williamr@2
|
50 |
* http://www.ams.org/bull/1999-36-04/S0273-0979-99-00796-X/
|
williamr@2
|
51 |
* S0273-0979-99-00796-X.pdf
|
williamr@2
|
52 |
*
|
williamr@2
|
53 |
* This implementation is not fully generic since it assumes that
|
williamr@2
|
54 |
* the sequences given are pointed to by index iterators (having a
|
williamr@2
|
55 |
* get_node() memfun.)
|
williamr@2
|
56 |
*/
|
williamr@2
|
57 |
|
williamr@2
|
58 |
namespace index_matcher{
|
williamr@2
|
59 |
|
williamr@2
|
60 |
/* The algorithm stores the nodes of the base sequence and a number
|
williamr@2
|
61 |
* of "piles" that are dynamically updated during the calculation
|
williamr@2
|
62 |
* stage. From a logical point of view, nodes form an independent
|
williamr@2
|
63 |
* sequence from piles. They are stored together so as to minimize
|
williamr@2
|
64 |
* allocated memory.
|
williamr@2
|
65 |
*/
|
williamr@2
|
66 |
|
williamr@2
|
67 |
struct entry
|
williamr@2
|
68 |
{
|
williamr@2
|
69 |
entry(void* node_,std::size_t pos_=0):node(node_),pos(pos_){}
|
williamr@2
|
70 |
|
williamr@2
|
71 |
/* node stuff */
|
williamr@2
|
72 |
|
williamr@2
|
73 |
void* node;
|
williamr@2
|
74 |
std::size_t pos;
|
williamr@2
|
75 |
entry* previous;
|
williamr@2
|
76 |
bool ordered;
|
williamr@2
|
77 |
|
williamr@2
|
78 |
struct less_by_node
|
williamr@2
|
79 |
{
|
williamr@2
|
80 |
bool operator()(
|
williamr@2
|
81 |
const entry& x,const entry& y)const
|
williamr@2
|
82 |
{
|
williamr@2
|
83 |
return std::less<void*>()(x.node,y.node);
|
williamr@2
|
84 |
}
|
williamr@2
|
85 |
};
|
williamr@2
|
86 |
|
williamr@2
|
87 |
/* pile stuff */
|
williamr@2
|
88 |
|
williamr@2
|
89 |
std::size_t pile_top;
|
williamr@2
|
90 |
entry* pile_top_entry;
|
williamr@2
|
91 |
|
williamr@2
|
92 |
struct less_by_pile_top
|
williamr@2
|
93 |
{
|
williamr@2
|
94 |
bool operator()(
|
williamr@2
|
95 |
const entry& x,const entry& y)const
|
williamr@2
|
96 |
{
|
williamr@2
|
97 |
return x.pile_top<y.pile_top;
|
williamr@2
|
98 |
}
|
williamr@2
|
99 |
};
|
williamr@2
|
100 |
};
|
williamr@2
|
101 |
|
williamr@2
|
102 |
/* common code operating on void *'s */
|
williamr@2
|
103 |
|
williamr@2
|
104 |
template<typename Allocator>
|
williamr@2
|
105 |
class algorithm_base:private noncopyable
|
williamr@2
|
106 |
{
|
williamr@2
|
107 |
protected:
|
williamr@2
|
108 |
algorithm_base(const Allocator& al,std::size_t size):
|
williamr@2
|
109 |
spc(al,size),size_(size),n(0),sorted(false)
|
williamr@2
|
110 |
{
|
williamr@2
|
111 |
}
|
williamr@2
|
112 |
|
williamr@2
|
113 |
void add(void* node)
|
williamr@2
|
114 |
{
|
williamr@2
|
115 |
entries()[n]=entry(node,n);
|
williamr@2
|
116 |
++n;
|
williamr@2
|
117 |
}
|
williamr@2
|
118 |
|
williamr@2
|
119 |
void begin_algorithm()const
|
williamr@2
|
120 |
{
|
williamr@2
|
121 |
if(!sorted){
|
williamr@2
|
122 |
std::sort(entries(),entries()+size_,entry::less_by_node());
|
williamr@2
|
123 |
sorted=true;
|
williamr@2
|
124 |
}
|
williamr@2
|
125 |
num_piles=0;
|
williamr@2
|
126 |
}
|
williamr@2
|
127 |
|
williamr@2
|
128 |
void add_node_to_algorithm(void* node)const
|
williamr@2
|
129 |
{
|
williamr@2
|
130 |
entry* ent=
|
williamr@2
|
131 |
std::lower_bound(
|
williamr@2
|
132 |
entries(),entries()+size_,
|
williamr@2
|
133 |
entry(node),entry::less_by_node()); /* localize entry */
|
williamr@2
|
134 |
ent->ordered=false;
|
williamr@2
|
135 |
std::size_t n=ent->pos; /* get its position */
|
williamr@2
|
136 |
|
williamr@2
|
137 |
entry dummy(0);
|
williamr@2
|
138 |
dummy.pile_top=n;
|
williamr@2
|
139 |
|
williamr@2
|
140 |
entry* pile_ent= /* find the first available pile */
|
williamr@2
|
141 |
std::lower_bound( /* to stack the entry */
|
williamr@2
|
142 |
entries(),entries()+num_piles,
|
williamr@2
|
143 |
dummy,entry::less_by_pile_top());
|
williamr@2
|
144 |
|
williamr@2
|
145 |
pile_ent->pile_top=n; /* stack the entry */
|
williamr@2
|
146 |
pile_ent->pile_top_entry=ent;
|
williamr@2
|
147 |
|
williamr@2
|
148 |
/* if not the first pile, link entry to top of the preceding pile */
|
williamr@2
|
149 |
if(pile_ent>&entries()[0]){
|
williamr@2
|
150 |
ent->previous=(pile_ent-1)->pile_top_entry;
|
williamr@2
|
151 |
}
|
williamr@2
|
152 |
|
williamr@2
|
153 |
if(pile_ent==&entries()[num_piles]){ /* new pile? */
|
williamr@2
|
154 |
++num_piles;
|
williamr@2
|
155 |
}
|
williamr@2
|
156 |
}
|
williamr@2
|
157 |
|
williamr@2
|
158 |
void finish_algorithm()const
|
williamr@2
|
159 |
{
|
williamr@2
|
160 |
if(num_piles>0){
|
williamr@2
|
161 |
/* Mark those elements which are in their correct position, i.e. those
|
williamr@2
|
162 |
* belonging to the longest increasing subsequence. These are those
|
williamr@2
|
163 |
* elements linked from the top of the last pile.
|
williamr@2
|
164 |
*/
|
williamr@2
|
165 |
|
williamr@2
|
166 |
entry* ent=entries()[num_piles-1].pile_top_entry;
|
williamr@2
|
167 |
for(std::size_t n=num_piles;n--;){
|
williamr@2
|
168 |
ent->ordered=true;
|
williamr@2
|
169 |
ent=ent->previous;
|
williamr@2
|
170 |
}
|
williamr@2
|
171 |
}
|
williamr@2
|
172 |
}
|
williamr@2
|
173 |
|
williamr@2
|
174 |
bool is_ordered(void * node)const
|
williamr@2
|
175 |
{
|
williamr@2
|
176 |
return std::lower_bound(
|
williamr@2
|
177 |
entries(),entries()+size_,
|
williamr@2
|
178 |
entry(node),entry::less_by_node())->ordered;
|
williamr@2
|
179 |
}
|
williamr@2
|
180 |
|
williamr@2
|
181 |
private:
|
williamr@2
|
182 |
entry* entries()const{return spc.data();}
|
williamr@2
|
183 |
|
williamr@2
|
184 |
auto_space<entry,Allocator> spc;
|
williamr@2
|
185 |
std::size_t size_;
|
williamr@2
|
186 |
std::size_t n;
|
williamr@2
|
187 |
mutable bool sorted;
|
williamr@2
|
188 |
mutable std::size_t num_piles;
|
williamr@2
|
189 |
};
|
williamr@2
|
190 |
|
williamr@2
|
191 |
/* The algorithm has three phases:
|
williamr@2
|
192 |
* - Initialization, during which the nodes of the base sequence are added.
|
williamr@2
|
193 |
* - Execution.
|
williamr@2
|
194 |
* - Results querying, through the is_ordered memfun.
|
williamr@2
|
195 |
*/
|
williamr@2
|
196 |
|
williamr@2
|
197 |
template<typename Node,typename Allocator>
|
williamr@2
|
198 |
class algorithm:private algorithm_base<Allocator>
|
williamr@2
|
199 |
{
|
williamr@2
|
200 |
typedef algorithm_base<Allocator> super;
|
williamr@2
|
201 |
|
williamr@2
|
202 |
public:
|
williamr@2
|
203 |
algorithm(const Allocator& al,std::size_t size):super(al,size){}
|
williamr@2
|
204 |
|
williamr@2
|
205 |
void add(Node* node)
|
williamr@2
|
206 |
{
|
williamr@2
|
207 |
super::add(node);
|
williamr@2
|
208 |
}
|
williamr@2
|
209 |
|
williamr@2
|
210 |
template<typename IndexIterator>
|
williamr@2
|
211 |
void execute(IndexIterator first,IndexIterator last)const
|
williamr@2
|
212 |
{
|
williamr@2
|
213 |
super::begin_algorithm();
|
williamr@2
|
214 |
|
williamr@2
|
215 |
for(IndexIterator it=first;it!=last;++it){
|
williamr@2
|
216 |
add_node_to_algorithm(get_node(it));
|
williamr@2
|
217 |
}
|
williamr@2
|
218 |
|
williamr@2
|
219 |
super::finish_algorithm();
|
williamr@2
|
220 |
}
|
williamr@2
|
221 |
|
williamr@2
|
222 |
bool is_ordered(Node* node)const
|
williamr@2
|
223 |
{
|
williamr@2
|
224 |
return super::is_ordered(node);
|
williamr@2
|
225 |
}
|
williamr@2
|
226 |
|
williamr@2
|
227 |
private:
|
williamr@2
|
228 |
void add_node_to_algorithm(Node* node)const
|
williamr@2
|
229 |
{
|
williamr@2
|
230 |
super::add_node_to_algorithm(node);
|
williamr@2
|
231 |
}
|
williamr@2
|
232 |
|
williamr@2
|
233 |
template<typename IndexIterator>
|
williamr@2
|
234 |
static Node* get_node(IndexIterator it)
|
williamr@2
|
235 |
{
|
williamr@2
|
236 |
return static_cast<Node*>(it.get_node());
|
williamr@2
|
237 |
}
|
williamr@2
|
238 |
};
|
williamr@2
|
239 |
|
williamr@2
|
240 |
} /* namespace multi_index::detail::index_matcher */
|
williamr@2
|
241 |
|
williamr@2
|
242 |
} /* namespace multi_index::detail */
|
williamr@2
|
243 |
|
williamr@2
|
244 |
} /* namespace multi_index */
|
williamr@2
|
245 |
|
williamr@2
|
246 |
} /* namespace boost */
|
williamr@2
|
247 |
|
williamr@2
|
248 |
#endif
|