boost/multi_index/detail/rnd_index_ops.hpp
/* Copyright 2003-2005 Joaqu�n M L�pez Mu�oz.
* Distributed under the Boost Software License, Version 1.0.
* (See accompanying file LICENSE_1_0.txt or copy at
* http://www.boost.org/LICENSE_1_0.txt)
*
* See http://www.boost.org/libs/multi_index for library home page.
*/
#ifndef BOOST_MULTI_INDEX_DETAIL_RND_INDEX_OPS_HPP
#define BOOST_MULTI_INDEX_DETAIL_RND_INDEX_OPS_HPP
#if defined(_MSC_VER)&&(_MSC_VER>=1200)
#pragma once
#endif
#include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
#include <algorithm>
#include <boost/multi_index/detail/rnd_index_ptr_array.hpp>
#include <functional>
namespace boost{
namespace multi_index{
namespace detail{
/* Common code for random_access_index memfuns having templatized and
* non-templatized versions.
*/
template<typename Node,typename Allocator,typename Predicate>
Node* random_access_index_remove(
random_access_index_ptr_array<Allocator>& ptrs,Predicate pred
BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
{
typedef typename Node::value_type value_type;
random_access_index_node_impl** first=ptrs.begin(),
** res=first,
** last=ptrs.end();
for(;first!=last;++first){
if(!pred(
const_cast<const value_type&>(Node::from_impl(*first)->value()))){
if(first!=res){
std::swap(*first,*res);
(*first)->up()=first;
(*res)->up()=res;
}
++res;
}
}
return Node::from_impl(*res);
}
template<typename Node,typename Allocator,class BinaryPredicate>
Node* random_access_index_unique(
random_access_index_ptr_array<Allocator>& ptrs,BinaryPredicate binary_pred
BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
{
typedef typename Node::value_type value_type;
random_access_index_node_impl** first=ptrs.begin(),
** res=first,
** last=ptrs.end();
if(first!=last){
for(;++first!=last;){
if(!binary_pred(
const_cast<const value_type&>(Node::from_impl(*res)->value()),
const_cast<const value_type&>(Node::from_impl(*first)->value()))){
++res;
if(first!=res){
std::swap(*first,*res);
(*first)->up()=first;
(*res)->up()=res;
}
}
}
++res;
}
return Node::from_impl(*res);
}
template<typename Node,typename Allocator,typename Compare>
void random_access_index_inplace_merge(
const Allocator& al,
random_access_index_ptr_array<Allocator>& ptrs,
random_access_index_node_impl** first1,Compare comp
BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
{
typedef typename Node::value_type value_type;
auto_space<random_access_index_node_impl*,Allocator> spc(al,ptrs.size());
random_access_index_node_impl** first0=ptrs.begin(),
** last0=first1,
** last1=ptrs.end(),
** out=spc.data();
while(first0!=last0&&first1!=last1){
if(comp(
const_cast<const value_type&>(Node::from_impl(*first1)->value()),
const_cast<const value_type&>(Node::from_impl(*first0)->value()))){
*out++=*first1++;
}
else{
*out++=*first0++;
}
}
std::copy(first0,last0,out);
std::copy(first1,last1,out);
first1=ptrs.begin();
out=spc.data();
while(first1!=last1){
*first1=*out++;
(*first1)->up()=first1;
++first1;
}
}
/* sorting */
/* auxiliary stuff */
template<typename Node,typename Compare>
struct random_access_index_sort_compare:
std::binary_function<
const typename Node::value_type*,const typename Node::value_type*,bool>
{
random_access_index_sort_compare(Compare comp_=Compare()):comp(comp_){}
bool operator()(
random_access_index_node_impl* x,
random_access_index_node_impl* y)const
{
typedef typename Node::value_type value_type;
return comp(
const_cast<const value_type&>(Node::from_impl(x)->value()),
const_cast<const value_type&>(Node::from_impl(y)->value()));
}
private:
Compare comp;
};
template<typename Node,typename Allocator,class Compare>
void random_access_index_sort(
const Allocator& al,
random_access_index_ptr_array<Allocator>& ptrs,
Compare comp
BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
{
/* The implementation is extremely simple: an auxiliary
* array of pointers is sorted using stdlib facilities and
* then used to rearrange the index. This is suboptimal
* in space and time, but has some advantages over other
* possible approaches:
* - Use std::stable_sort() directly on ptrs using some
* special iterator in charge of maintaining pointers
* and up() pointers in sync: we cannot guarantee
* preservation of the container invariants in the face of
* exceptions, if, for instance, std::stable_sort throws
* when ptrs transitorily contains duplicate elements.
* - Rewrite the internal algorithms of std::stable_sort
* adapted for this case: besides being a fair amount of
* work, making a stable sort compatible with Boost.MultiIndex
* invariants (basically, no duplicates or missing elements
* even if an exception is thrown) is complicated, error-prone
* and possibly won't perform much better than the
* solution adopted.
*/
typedef typename Node::value_type value_type;
typedef random_access_index_sort_compare<
Node,Compare> ptr_compare;
random_access_index_node_impl** first=ptrs.begin();
random_access_index_node_impl** last=ptrs.end();
auto_space<
random_access_index_node_impl*,
Allocator> spc(al,ptrs.size());
random_access_index_node_impl** buf=spc.data();
std::copy(first,last,buf);
std::stable_sort(buf,buf+ptrs.size(),ptr_compare(comp));
while(first!=last){
*first=*buf++;
(*first)->up()=first;
++first;
}
}
} /* namespace multi_index::detail */
} /* namespace multi_index */
} /* namespace boost */
#endif