]>
Commit | Line | Data |
---|---|---|
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_RND_INDEX_OPS_HPP | |
10 | #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_OPS_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/multi_index/detail/rnd_index_ptr_array.hpp> | |
19 | ||
20 | namespace boost{ | |
21 | ||
22 | namespace multi_index{ | |
23 | ||
24 | namespace detail{ | |
25 | ||
26 | /* Common code for random_access_index memfuns having templatized and | |
27 | * non-templatized versions. | |
28 | */ | |
29 | ||
30 | template<typename Node,typename Allocator,typename Predicate> | |
31 | Node* random_access_index_remove( | |
32 | random_access_index_ptr_array<Allocator>& ptrs,Predicate pred) | |
33 | { | |
34 | typedef typename Node::value_type value_type; | |
35 | typedef typename Node::impl_ptr_pointer impl_ptr_pointer; | |
36 | ||
37 | impl_ptr_pointer first=ptrs.begin(), | |
38 | res=first, | |
39 | last=ptrs.end(); | |
40 | for(;first!=last;++first){ | |
41 | if(!pred( | |
42 | const_cast<const value_type&>(Node::from_impl(*first)->value()))){ | |
43 | if(first!=res){ | |
44 | std::swap(*first,*res); | |
45 | (*first)->up()=first; | |
46 | (*res)->up()=res; | |
47 | } | |
48 | ++res; | |
49 | } | |
50 | } | |
51 | return Node::from_impl(*res); | |
52 | } | |
53 | ||
54 | template<typename Node,typename Allocator,class BinaryPredicate> | |
55 | Node* random_access_index_unique( | |
56 | random_access_index_ptr_array<Allocator>& ptrs,BinaryPredicate binary_pred) | |
57 | { | |
58 | typedef typename Node::value_type value_type; | |
59 | typedef typename Node::impl_ptr_pointer impl_ptr_pointer; | |
60 | ||
61 | impl_ptr_pointer first=ptrs.begin(), | |
62 | res=first, | |
63 | last=ptrs.end(); | |
64 | if(first!=last){ | |
65 | for(;++first!=last;){ | |
66 | if(!binary_pred( | |
67 | const_cast<const value_type&>(Node::from_impl(*res)->value()), | |
68 | const_cast<const value_type&>(Node::from_impl(*first)->value()))){ | |
69 | ++res; | |
70 | if(first!=res){ | |
71 | std::swap(*first,*res); | |
72 | (*first)->up()=first; | |
73 | (*res)->up()=res; | |
74 | } | |
75 | } | |
76 | } | |
77 | ++res; | |
78 | } | |
79 | return Node::from_impl(*res); | |
80 | } | |
81 | ||
82 | template<typename Node,typename Allocator,typename Compare> | |
83 | void random_access_index_inplace_merge( | |
84 | const Allocator& al, | |
85 | random_access_index_ptr_array<Allocator>& ptrs, | |
86 | BOOST_DEDUCED_TYPENAME Node::impl_ptr_pointer first1,Compare comp) | |
87 | { | |
88 | typedef typename Node::value_type value_type; | |
89 | typedef typename Node::impl_pointer impl_pointer; | |
90 | typedef typename Node::impl_ptr_pointer impl_ptr_pointer; | |
91 | ||
92 | auto_space<impl_pointer,Allocator> spc(al,ptrs.size()); | |
93 | ||
94 | impl_ptr_pointer first0=ptrs.begin(), | |
95 | last0=first1, | |
96 | last1=ptrs.end(), | |
97 | out=spc.data(); | |
98 | while(first0!=last0&&first1!=last1){ | |
99 | if(comp( | |
100 | const_cast<const value_type&>(Node::from_impl(*first1)->value()), | |
101 | const_cast<const value_type&>(Node::from_impl(*first0)->value()))){ | |
102 | *out++=*first1++; | |
103 | } | |
104 | else{ | |
105 | *out++=*first0++; | |
106 | } | |
107 | } | |
108 | std::copy(&*first0,&*last0,&*out); | |
109 | std::copy(&*first1,&*last1,&*out); | |
110 | ||
111 | first1=ptrs.begin(); | |
112 | out=spc.data(); | |
113 | while(first1!=last1){ | |
114 | *first1=*out++; | |
115 | (*first1)->up()=first1; | |
116 | ++first1; | |
117 | } | |
118 | } | |
119 | ||
120 | /* sorting */ | |
121 | ||
122 | /* auxiliary stuff */ | |
123 | ||
124 | template<typename Node,typename Compare> | |
125 | struct random_access_index_sort_compare | |
126 | { | |
127 | typedef typename Node::impl_pointer first_argument_type; | |
128 | typedef typename Node::impl_pointer second_argument_type; | |
129 | typedef bool result_type; | |
130 | ||
131 | random_access_index_sort_compare(Compare comp_=Compare()):comp(comp_){} | |
132 | ||
133 | bool operator()( | |
134 | typename Node::impl_pointer x,typename Node::impl_pointer y)const | |
135 | { | |
136 | typedef typename Node::value_type value_type; | |
137 | ||
138 | return comp( | |
139 | const_cast<const value_type&>(Node::from_impl(x)->value()), | |
140 | const_cast<const value_type&>(Node::from_impl(y)->value())); | |
141 | } | |
142 | ||
143 | private: | |
144 | Compare comp; | |
145 | }; | |
146 | ||
147 | template<typename Node,typename Allocator,class Compare> | |
148 | void random_access_index_sort( | |
149 | const Allocator& al, | |
150 | random_access_index_ptr_array<Allocator>& ptrs, | |
151 | Compare comp) | |
152 | { | |
153 | /* The implementation is extremely simple: an auxiliary | |
154 | * array of pointers is sorted using stdlib facilities and | |
155 | * then used to rearrange the index. This is suboptimal | |
156 | * in space and time, but has some advantages over other | |
157 | * possible approaches: | |
158 | * - Use std::stable_sort() directly on ptrs using some | |
159 | * special iterator in charge of maintaining pointers | |
160 | * and up() pointers in sync: we cannot guarantee | |
161 | * preservation of the container invariants in the face of | |
162 | * exceptions, if, for instance, std::stable_sort throws | |
163 | * when ptrs transitorily contains duplicate elements. | |
164 | * - Rewrite the internal algorithms of std::stable_sort | |
165 | * adapted for this case: besides being a fair amount of | |
166 | * work, making a stable sort compatible with Boost.MultiIndex | |
167 | * invariants (basically, no duplicates or missing elements | |
168 | * even if an exception is thrown) is complicated, error-prone | |
169 | * and possibly won't perform much better than the | |
170 | * solution adopted. | |
171 | */ | |
172 | ||
173 | if(ptrs.size()<=1)return; | |
174 | ||
175 | typedef typename Node::impl_pointer impl_pointer; | |
176 | typedef typename Node::impl_ptr_pointer impl_ptr_pointer; | |
177 | typedef random_access_index_sort_compare< | |
178 | Node,Compare> ptr_compare; | |
179 | ||
180 | impl_ptr_pointer first=ptrs.begin(); | |
181 | impl_ptr_pointer last=ptrs.end(); | |
182 | auto_space< | |
183 | impl_pointer, | |
184 | Allocator> spc(al,ptrs.size()); | |
185 | impl_ptr_pointer buf=spc.data(); | |
186 | ||
187 | std::copy(&*first,&*last,&*buf); | |
188 | std::stable_sort(&*buf,&*buf+ptrs.size(),ptr_compare(comp)); | |
189 | ||
190 | while(first!=last){ | |
191 | *first=*buf++; | |
192 | (*first)->up()=first; | |
193 | ++first; | |
194 | } | |
195 | } | |
196 | ||
197 | } /* namespace multi_index::detail */ | |
198 | ||
199 | } /* namespace multi_index */ | |
200 | ||
201 | } /* namespace boost */ | |
202 | ||
203 | #endif |