/* Copyright 2003-2009 Joaquin M Lopez Munoz. | |
* 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; | |
typedef typename Node::impl_ptr_pointer impl_ptr_pointer; | |
impl_ptr_pointer 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; | |
typedef typename Node::impl_ptr_pointer impl_ptr_pointer; | |
impl_ptr_pointer 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, | |
BOOST_DEDUCED_TYPENAME Node::impl_ptr_pointer first1,Compare comp | |
BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node)) | |
{ | |
typedef typename Node::value_type value_type; | |
typedef typename Node::impl_pointer impl_pointer; | |
typedef typename Node::impl_ptr_pointer impl_ptr_pointer; | |
auto_space<impl_pointer,Allocator> spc(al,ptrs.size()); | |
impl_ptr_pointer 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< | |
typename Node::impl_pointer, | |
typename Node::impl_pointer,bool> | |
{ | |
random_access_index_sort_compare(Compare comp_=Compare()):comp(comp_){} | |
bool operator()( | |
typename Node::impl_pointer x,typename Node::impl_pointer 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. | |
*/ | |
if(ptrs.size()<=1)return; | |
typedef typename Node::value_type value_type; | |
typedef typename Node::impl_pointer impl_pointer; | |
typedef typename Node::impl_ptr_pointer impl_ptr_pointer; | |
typedef random_access_index_sort_compare< | |
Node,Compare> ptr_compare; | |
impl_ptr_pointer first=ptrs.begin(); | |
impl_ptr_pointer last=ptrs.end(); | |
auto_space< | |
impl_pointer, | |
Allocator> spc(al,ptrs.size()); | |
impl_ptr_pointer 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 |