1 /* Copyright 2003-2007 Joaquín M López Muñoz.
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)
6 * See http://www.boost.org/libs/multi_index for library home page.
9 #ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_OPS_HPP
10 #define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_OPS_HPP
12 #if defined(_MSC_VER)&&(_MSC_VER>=1200)
16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
18 #include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
23 namespace multi_index{
27 /* Common code for random_access_index memfuns having templatized and
28 * non-templatized versions.
31 template<typename Node,typename Allocator,typename Predicate>
32 Node* random_access_index_remove(
33 random_access_index_ptr_array<Allocator>& ptrs,Predicate pred
34 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
36 typedef typename Node::value_type value_type;
37 typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
39 impl_ptr_pointer first=ptrs.begin(),
42 for(;first!=last;++first){
44 const_cast<const value_type&>(Node::from_impl(*first)->value()))){
46 std::swap(*first,*res);
53 return Node::from_impl(*res);
56 template<typename Node,typename Allocator,class BinaryPredicate>
57 Node* random_access_index_unique(
58 random_access_index_ptr_array<Allocator>& ptrs,BinaryPredicate binary_pred
59 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
61 typedef typename Node::value_type value_type;
62 typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
64 impl_ptr_pointer first=ptrs.begin(),
70 const_cast<const value_type&>(Node::from_impl(*res)->value()),
71 const_cast<const value_type&>(Node::from_impl(*first)->value()))){
74 std::swap(*first,*res);
82 return Node::from_impl(*res);
85 template<typename Node,typename Allocator,typename Compare>
86 void random_access_index_inplace_merge(
88 random_access_index_ptr_array<Allocator>& ptrs,
89 BOOST_DEDUCED_TYPENAME Node::impl_ptr_pointer first1,Compare comp
90 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
92 typedef typename Node::value_type value_type;
93 typedef typename Node::impl_pointer impl_pointer;
94 typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
96 auto_space<impl_pointer,Allocator> spc(al,ptrs.size());
98 impl_ptr_pointer first0=ptrs.begin(),
102 while(first0!=last0&&first1!=last1){
104 const_cast<const value_type&>(Node::from_impl(*first1)->value()),
105 const_cast<const value_type&>(Node::from_impl(*first0)->value()))){
112 std::copy(&*first0,&*last0,&*out);
113 std::copy(&*first1,&*last1,&*out);
117 while(first1!=last1){
119 (*first1)->up()=first1;
126 /* auxiliary stuff */
128 template<typename Node,typename Compare>
129 struct random_access_index_sort_compare:
130 std::binary_function<
131 typename Node::impl_pointer,
132 typename Node::impl_pointer,bool>
134 random_access_index_sort_compare(Compare comp_=Compare()):comp(comp_){}
137 typename Node::impl_pointer x,typename Node::impl_pointer y)const
139 typedef typename Node::value_type value_type;
142 const_cast<const value_type&>(Node::from_impl(x)->value()),
143 const_cast<const value_type&>(Node::from_impl(y)->value()));
150 template<typename Node,typename Allocator,class Compare>
151 void random_access_index_sort(
153 random_access_index_ptr_array<Allocator>& ptrs,
155 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
157 /* The implementation is extremely simple: an auxiliary
158 * array of pointers is sorted using stdlib facilities and
159 * then used to rearrange the index. This is suboptimal
160 * in space and time, but has some advantages over other
161 * possible approaches:
162 * - Use std::stable_sort() directly on ptrs using some
163 * special iterator in charge of maintaining pointers
164 * and up() pointers in sync: we cannot guarantee
165 * preservation of the container invariants in the face of
166 * exceptions, if, for instance, std::stable_sort throws
167 * when ptrs transitorily contains duplicate elements.
168 * - Rewrite the internal algorithms of std::stable_sort
169 * adapted for this case: besides being a fair amount of
170 * work, making a stable sort compatible with Boost.MultiIndex
171 * invariants (basically, no duplicates or missing elements
172 * even if an exception is thrown) is complicated, error-prone
173 * and possibly won't perform much better than the
177 typedef typename Node::value_type value_type;
178 typedef typename Node::impl_pointer impl_pointer;
179 typedef typename Node::impl_ptr_pointer impl_ptr_pointer;
180 typedef random_access_index_sort_compare<
181 Node,Compare> ptr_compare;
183 impl_ptr_pointer first=ptrs.begin();
184 impl_ptr_pointer last=ptrs.end();
187 Allocator> spc(al,ptrs.size());
188 impl_ptr_pointer buf=spc.data();
190 std::copy(&*first,&*last,&*buf);
191 std::stable_sort(&*buf,&*buf+ptrs.size(),ptr_compare(comp));
195 (*first)->up()=first;
200 } /* namespace multi_index::detail */
202 } /* namespace multi_index */
204 } /* namespace boost */