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>
random_access_index_remove(random_access_index_ptr_array<Allocator> & ptrs,Predicate pred)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>
random_access_index_unique(random_access_index_ptr_array<Allocator> & ptrs,BinaryPredicate binary_pred)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>
random_access_index_inplace_merge(const Allocator & al,random_access_index_ptr_array<Allocator> & ptrs,BOOST_DEDUCED_TYPENAME Node::impl_ptr_pointer first1,Compare comp)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
random_access_index_sort_compareboost::multi_index::detail::random_access_index_sort_compare131 random_access_index_sort_compare(Compare comp_=Compare()):comp(comp_){}
132
operator ()boost::multi_index::detail::random_access_index_sort_compare133 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>
random_access_index_sort(const Allocator & al,random_access_index_ptr_array<Allocator> & ptrs,Compare comp)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
204