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_SEQ_INDEX_OPS_HPP
10 #define BOOST_MULTI_INDEX_DETAIL_SEQ_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 */
17 #include <boost/detail/no_exceptions_support.hpp>
18 #include <boost/multi_index/detail/seq_index_node.hpp>
19 #include <boost/limits.hpp>
20 #include <boost/type_traits/aligned_storage.hpp>
21 #include <boost/type_traits/alignment_of.hpp>
26 namespace multi_index{
30 /* Common code for sequenced_index memfuns having templatized and
31 * non-templatized versions.
34 template <typename SequencedIndex,typename Predicate>
35 void sequenced_index_remove(SequencedIndex& x,Predicate pred)
37 typedef typename SequencedIndex::iterator iterator;
38 iterator first=x.begin(),last=x.end();
40 if(pred(*first))x.erase(first++);
45 template <typename SequencedIndex,class BinaryPredicate>
46 void sequenced_index_unique(SequencedIndex& x,BinaryPredicate binary_pred)
48 typedef typename SequencedIndex::iterator iterator;
49 iterator first=x.begin();
50 iterator last=x.end();
52 for(iterator middle=first;++middle!=last;middle=first){
53 if(binary_pred(*middle,*first))x.erase(middle);
59 template <typename SequencedIndex,typename Compare>
60 void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp)
62 typedef typename SequencedIndex::iterator iterator;
64 iterator first0=x.begin(),last0=x.end();
65 iterator first1=y.begin(),last1=y.end();
66 while(first0!=last0&&first1!=last1){
67 if(comp(*first1,*first0))x.splice(first0,y,first1++);
70 x.splice(last0,y,first1,last1);
78 template<typename Node,typename Compare>
79 void sequenced_index_collate(
80 BOOST_DEDUCED_TYPENAME Node::impl_type* x,
81 BOOST_DEDUCED_TYPENAME Node::impl_type* y,
83 BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
85 typedef typename Node::impl_type impl_type;
86 typedef typename Node::impl_pointer impl_pointer;
88 impl_pointer first0=x->next();
90 impl_pointer first1=y->next();
92 while(first0!=last0&&first1!=last1){
94 Node::from_impl(first1)->value(),Node::from_impl(first0)->value())){
95 impl_pointer tmp=first1->next();
96 impl_type::relink(first0,first1);
99 else first0=first0->next();
101 impl_type::relink(last0,first1,last1);
104 /* Some versions of CGG require a bogus typename in counter_spc
105 * inside sequenced_index_sort if the following is defined
106 * also inside sequenced_index_sort.
109 BOOST_STATIC_CONSTANT(
111 sequenced_index_sort_max_fill=
112 (std::size_t)std::numeric_limits<std::size_t>::digits+1);
114 template<typename Node,typename Compare>
115 void sequenced_index_sort(Node* header,Compare comp)
117 /* Musser's mergesort, see http://www.cs.rpi.edu/~musser/gp/List/lists1.html.
118 * The implementation is a little convoluted: in the original code
119 * counter elements and carry are std::lists: here we do not want
120 * to use multi_index instead, so we do things at a lower level, managing
121 * directly the internal node representation.
122 * Incidentally, the implementations I've seen of this algorithm (SGI,
123 * Dinkumware, STLPort) are not exception-safe: this is. Moreover, we do not
124 * use any dynamic storage.
127 if(header->next()==header->impl()||
128 header->next()->next()==header->impl())return;
130 typedef typename Node::impl_type impl_type;
131 typedef typename Node::impl_pointer impl_pointer;
133 typedef typename aligned_storage<
135 alignment_of<impl_type>::value
136 >::type carry_spc_type;
137 carry_spc_type carry_spc;
139 *static_cast<impl_type*>(static_cast<void*>(&carry_spc));
140 typedef typename aligned_storage<
143 [sequenced_index_sort_max_fill]),
146 [sequenced_index_sort_max_fill]
148 >::type counter_spc_type;
149 counter_spc_type counter_spc;
151 static_cast<impl_type*>(static_cast<void*>(&counter_spc));
154 carry.prior()=carry.next()=static_cast<impl_pointer>(&carry);
155 counter[0].prior()=counter[0].next()=static_cast<impl_pointer>(&counter[0]);
158 while(header->next()!=header->impl()){
159 impl_type::relink(carry.next(),header->next());
161 while(i<fill&&counter[i].next()!=static_cast<impl_pointer>(&counter[i])){
162 sequenced_index_collate<Node>(&carry,&counter[i++],comp);
165 static_cast<impl_pointer>(&carry),
166 static_cast<impl_pointer>(&counter[i]));
169 counter[fill].prior()=counter[fill].next()=
170 static_cast<impl_pointer>(&counter[fill]);
174 for(std::size_t i=1;i<fill;++i){
175 sequenced_index_collate<Node>(&counter[i],&counter[i-1],comp);
178 header->impl(),static_cast<impl_pointer>(&counter[fill-1]));
183 header->impl(),carry.next(),static_cast<impl_pointer>(&carry));
184 for(std::size_t i=0;i<=fill;++i){
186 header->impl(),counter[i].next(),
187 static_cast<impl_pointer>(&counter[i]));
194 } /* namespace multi_index::detail */
196 } /* namespace multi_index */
198 } /* namespace boost */