williamr@2
|
1 |
/* Copyright 2003-2006 Joaquín M López Muñoz.
|
williamr@2
|
2 |
* Distributed under the Boost Software License, Version 1.0.
|
williamr@2
|
3 |
* (See accompanying file LICENSE_1_0.txt or copy at
|
williamr@2
|
4 |
* http://www.boost.org/LICENSE_1_0.txt)
|
williamr@2
|
5 |
*
|
williamr@2
|
6 |
* See http://www.boost.org/libs/multi_index for library home page.
|
williamr@2
|
7 |
*/
|
williamr@2
|
8 |
|
williamr@2
|
9 |
#ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP
|
williamr@2
|
10 |
#define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP
|
williamr@2
|
11 |
|
williamr@2
|
12 |
#if defined(_MSC_VER)&&(_MSC_VER>=1200)
|
williamr@2
|
13 |
#pragma once
|
williamr@2
|
14 |
#endif
|
williamr@2
|
15 |
|
williamr@2
|
16 |
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
|
williamr@2
|
17 |
#include <boost/detail/no_exceptions_support.hpp>
|
williamr@2
|
18 |
#include <boost/multi_index/detail/seq_index_node.hpp>
|
williamr@2
|
19 |
#include <boost/limits.hpp>
|
williamr@2
|
20 |
#include <boost/type_traits/aligned_storage.hpp>
|
williamr@2
|
21 |
#include <boost/type_traits/alignment_of.hpp>
|
williamr@2
|
22 |
#include <cstddef>
|
williamr@2
|
23 |
|
williamr@2
|
24 |
namespace boost{
|
williamr@2
|
25 |
|
williamr@2
|
26 |
namespace multi_index{
|
williamr@2
|
27 |
|
williamr@2
|
28 |
namespace detail{
|
williamr@2
|
29 |
|
williamr@2
|
30 |
/* Common code for sequenced_index memfuns having templatized and
|
williamr@2
|
31 |
* non-templatized versions.
|
williamr@2
|
32 |
*/
|
williamr@2
|
33 |
|
williamr@2
|
34 |
template <typename SequencedIndex,typename Predicate>
|
williamr@2
|
35 |
void sequenced_index_remove(SequencedIndex& x,Predicate pred)
|
williamr@2
|
36 |
{
|
williamr@2
|
37 |
typedef typename SequencedIndex::iterator iterator;
|
williamr@2
|
38 |
iterator first=x.begin(),last=x.end();
|
williamr@2
|
39 |
while(first!=last){
|
williamr@2
|
40 |
if(pred(*first))x.erase(first++);
|
williamr@2
|
41 |
else ++first;
|
williamr@2
|
42 |
}
|
williamr@2
|
43 |
}
|
williamr@2
|
44 |
|
williamr@2
|
45 |
template <typename SequencedIndex,class BinaryPredicate>
|
williamr@2
|
46 |
void sequenced_index_unique(SequencedIndex& x,BinaryPredicate binary_pred)
|
williamr@2
|
47 |
{
|
williamr@2
|
48 |
typedef typename SequencedIndex::iterator iterator;
|
williamr@2
|
49 |
iterator first=x.begin();
|
williamr@2
|
50 |
iterator last=x.end();
|
williamr@2
|
51 |
if(first!=last){
|
williamr@2
|
52 |
for(iterator middle=first;++middle!=last;middle=first){
|
williamr@2
|
53 |
if(binary_pred(*middle,*first))x.erase(middle);
|
williamr@2
|
54 |
else first=middle;
|
williamr@2
|
55 |
}
|
williamr@2
|
56 |
}
|
williamr@2
|
57 |
}
|
williamr@2
|
58 |
|
williamr@2
|
59 |
template <typename SequencedIndex,typename Compare>
|
williamr@2
|
60 |
void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp)
|
williamr@2
|
61 |
{
|
williamr@2
|
62 |
typedef typename SequencedIndex::iterator iterator;
|
williamr@2
|
63 |
if(&x!=&y){
|
williamr@2
|
64 |
iterator first0=x.begin(),last0=x.end();
|
williamr@2
|
65 |
iterator first1=y.begin(),last1=y.end();
|
williamr@2
|
66 |
while(first0!=last0&&first1!=last1){
|
williamr@2
|
67 |
if(comp(*first1,*first0))x.splice(first0,y,first1++);
|
williamr@2
|
68 |
else ++first0;
|
williamr@2
|
69 |
}
|
williamr@2
|
70 |
x.splice(last0,y,first1,last1);
|
williamr@2
|
71 |
}
|
williamr@2
|
72 |
}
|
williamr@2
|
73 |
|
williamr@2
|
74 |
/* sorting */
|
williamr@2
|
75 |
|
williamr@2
|
76 |
/* auxiliary stuff */
|
williamr@2
|
77 |
|
williamr@2
|
78 |
template<typename Node,typename Compare>
|
williamr@2
|
79 |
void sequenced_index_collate(
|
williamr@2
|
80 |
sequenced_index_node_impl* x,sequenced_index_node_impl* y,Compare comp
|
williamr@2
|
81 |
BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
|
williamr@2
|
82 |
{
|
williamr@2
|
83 |
sequenced_index_node_impl* first0=x->next();
|
williamr@2
|
84 |
sequenced_index_node_impl* last0=x;
|
williamr@2
|
85 |
sequenced_index_node_impl* first1=y->next();
|
williamr@2
|
86 |
sequenced_index_node_impl* last1=y;
|
williamr@2
|
87 |
while(first0!=last0&&first1!=last1){
|
williamr@2
|
88 |
if(comp(
|
williamr@2
|
89 |
Node::from_impl(first1)->value(),Node::from_impl(first0)->value())){
|
williamr@2
|
90 |
sequenced_index_node_impl* tmp=first1->next();
|
williamr@2
|
91 |
sequenced_index_node_impl::relink(first0,first1);
|
williamr@2
|
92 |
first1=tmp;
|
williamr@2
|
93 |
}
|
williamr@2
|
94 |
else first0=first0->next();
|
williamr@2
|
95 |
}
|
williamr@2
|
96 |
sequenced_index_node_impl::relink(last0,first1,last1);
|
williamr@2
|
97 |
}
|
williamr@2
|
98 |
|
williamr@2
|
99 |
/* Some versions of CGG require a bogus typename in counter_spc
|
williamr@2
|
100 |
* inside sequenced_index_sort if the following is defined
|
williamr@2
|
101 |
* also inside sequenced_index_sort.
|
williamr@2
|
102 |
*/
|
williamr@2
|
103 |
|
williamr@2
|
104 |
BOOST_STATIC_CONSTANT(
|
williamr@2
|
105 |
std::size_t,
|
williamr@2
|
106 |
sequenced_index_sort_max_fill=
|
williamr@2
|
107 |
(std::size_t)std::numeric_limits<std::size_t>::digits+1);
|
williamr@2
|
108 |
|
williamr@2
|
109 |
template<typename Node,typename Compare>
|
williamr@2
|
110 |
void sequenced_index_sort(Node* header,Compare comp)
|
williamr@2
|
111 |
{
|
williamr@2
|
112 |
/* Musser's mergesort, see http://www.cs.rpi.edu/~musser/gp/List/lists1.html.
|
williamr@2
|
113 |
* The implementation is a little convoluted: in the original code
|
williamr@2
|
114 |
* counter elements and carry are std::lists: here we do not want
|
williamr@2
|
115 |
* to use multi_index instead, so we do things at a lower level, managing
|
williamr@2
|
116 |
* directly the internal node representation.
|
williamr@2
|
117 |
* Incidentally, the implementations I've seen of this algorithm (SGI,
|
williamr@2
|
118 |
* Dinkumware, STLPort) are not exception-safe: this is. Moreover, we do not
|
williamr@2
|
119 |
* use any dynamic storage.
|
williamr@2
|
120 |
*/
|
williamr@2
|
121 |
|
williamr@2
|
122 |
if(header->next()==header->impl()||
|
williamr@2
|
123 |
header->next()->next()==header->impl())return;
|
williamr@2
|
124 |
|
williamr@2
|
125 |
aligned_storage<
|
williamr@2
|
126 |
sizeof(sequenced_index_node_impl),
|
williamr@2
|
127 |
alignment_of<
|
williamr@2
|
128 |
sequenced_index_node_impl>::value
|
williamr@2
|
129 |
>::type carry_spc;
|
williamr@2
|
130 |
sequenced_index_node_impl& carry=
|
williamr@2
|
131 |
*static_cast<sequenced_index_node_impl*>(static_cast<void*>(&carry_spc));
|
williamr@2
|
132 |
aligned_storage<
|
williamr@2
|
133 |
sizeof(
|
williamr@2
|
134 |
sequenced_index_node_impl
|
williamr@2
|
135 |
[sequenced_index_sort_max_fill]),
|
williamr@2
|
136 |
alignment_of<
|
williamr@2
|
137 |
sequenced_index_node_impl
|
williamr@2
|
138 |
[sequenced_index_sort_max_fill]
|
williamr@2
|
139 |
>::value
|
williamr@2
|
140 |
>::type counter_spc;
|
williamr@2
|
141 |
sequenced_index_node_impl* counter=
|
williamr@2
|
142 |
static_cast<sequenced_index_node_impl*>(static_cast<void*>(&counter_spc));
|
williamr@2
|
143 |
std::size_t fill=0;
|
williamr@2
|
144 |
|
williamr@2
|
145 |
carry.prior()=carry.next()=&carry;
|
williamr@2
|
146 |
counter[0].prior()=counter[0].next()=&counter[0];
|
williamr@2
|
147 |
|
williamr@2
|
148 |
BOOST_TRY{
|
williamr@2
|
149 |
while(header->next()!=header->impl()){
|
williamr@2
|
150 |
sequenced_index_node_impl::relink(carry.next(),header->next());
|
williamr@2
|
151 |
std::size_t i=0;
|
williamr@2
|
152 |
while(i<fill&&counter[i].next()!=&counter[i]){
|
williamr@2
|
153 |
sequenced_index_collate<Node>(&carry,&counter[i++],comp);
|
williamr@2
|
154 |
}
|
williamr@2
|
155 |
sequenced_index_node_impl::swap(&carry,&counter[i]);
|
williamr@2
|
156 |
if(i==fill){
|
williamr@2
|
157 |
++fill;
|
williamr@2
|
158 |
counter[fill].prior()=counter[fill].next()=&counter[fill];
|
williamr@2
|
159 |
}
|
williamr@2
|
160 |
}
|
williamr@2
|
161 |
|
williamr@2
|
162 |
for(std::size_t i=1;i<fill;++i){
|
williamr@2
|
163 |
sequenced_index_collate<Node>(&counter[i],&counter[i-1],comp);
|
williamr@2
|
164 |
}
|
williamr@2
|
165 |
sequenced_index_node_impl::swap(header->impl(),&counter[fill-1]);
|
williamr@2
|
166 |
}
|
williamr@2
|
167 |
BOOST_CATCH(...)
|
williamr@2
|
168 |
{
|
williamr@2
|
169 |
sequenced_index_node_impl::relink(header->impl(),carry.next(),&carry);
|
williamr@2
|
170 |
for(std::size_t i=0;i<=fill;++i){
|
williamr@2
|
171 |
sequenced_index_node_impl::relink(
|
williamr@2
|
172 |
header->impl(),counter[i].next(),&counter[i]);
|
williamr@2
|
173 |
}
|
williamr@2
|
174 |
BOOST_RETHROW;
|
williamr@2
|
175 |
}
|
williamr@2
|
176 |
BOOST_CATCH_END
|
williamr@2
|
177 |
}
|
williamr@2
|
178 |
|
williamr@2
|
179 |
} /* namespace multi_index::detail */
|
williamr@2
|
180 |
|
williamr@2
|
181 |
} /* namespace multi_index */
|
williamr@2
|
182 |
|
williamr@2
|
183 |
} /* namespace boost */
|
williamr@2
|
184 |
|
williamr@2
|
185 |
#endif
|