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