]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 | { | |
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 | ||
105 | template<typename Allocator> | |
106 | class algorithm_base:private noncopyable | |
107 | { | |
108 | protected: | |
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 | ||
182 | private: | |
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 | ||
198 | template<typename Node,typename Allocator> | |
199 | class algorithm:private algorithm_base<Allocator> | |
200 | { | |
201 | typedef algorithm_base<Allocator> super; | |
202 | ||
203 | public: | |
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 | ||
228 | private: | |
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 |