Chris@101: /* Copyright 2003-2013 Joaquin M Lopez Munoz.
Chris@16:  * Distributed under the Boost Software License, Version 1.0.
Chris@16:  * (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:  * http://www.boost.org/LICENSE_1_0.txt)
Chris@16:  *
Chris@16:  * See http://www.boost.org/libs/multi_index for library home page.
Chris@16:  */
Chris@16: 
Chris@16: #ifndef BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP
Chris@16: #define BOOST_MULTI_INDEX_DETAIL_SEQ_INDEX_OPS_HPP
Chris@16: 
Chris@101: #if defined(_MSC_VER)
Chris@16: #pragma once
Chris@16: #endif
Chris@16: 
Chris@16: #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
Chris@16: #include <boost/detail/no_exceptions_support.hpp>
Chris@16: #include <boost/multi_index/detail/seq_index_node.hpp>
Chris@16: #include <boost/limits.hpp>
Chris@16: #include <boost/type_traits/aligned_storage.hpp>
Chris@16: #include <boost/type_traits/alignment_of.hpp> 
Chris@16: #include <cstddef>
Chris@16: 
Chris@16: namespace boost{
Chris@16: 
Chris@16: namespace multi_index{
Chris@16: 
Chris@16: namespace detail{
Chris@16: 
Chris@16: /* Common code for sequenced_index memfuns having templatized and
Chris@16:  * non-templatized versions.
Chris@16:  */
Chris@16: 
Chris@16: template <typename SequencedIndex,typename Predicate>
Chris@16: void sequenced_index_remove(SequencedIndex& x,Predicate pred)
Chris@16: {
Chris@16:   typedef typename SequencedIndex::iterator iterator;
Chris@16:   iterator first=x.begin(),last=x.end();
Chris@16:   while(first!=last){
Chris@16:     if(pred(*first))x.erase(first++);
Chris@16:     else ++first;
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: template <typename SequencedIndex,class BinaryPredicate>
Chris@16: void sequenced_index_unique(SequencedIndex& x,BinaryPredicate binary_pred)
Chris@16: {
Chris@16:   typedef typename SequencedIndex::iterator iterator;
Chris@16:   iterator first=x.begin();
Chris@16:   iterator last=x.end();
Chris@16:   if(first!=last){
Chris@16:     for(iterator middle=first;++middle!=last;middle=first){
Chris@16:       if(binary_pred(*middle,*first))x.erase(middle);
Chris@16:       else first=middle;
Chris@16:     }
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: template <typename SequencedIndex,typename Compare>
Chris@16: void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp)
Chris@16: {
Chris@16:   typedef typename SequencedIndex::iterator iterator;
Chris@16:   if(&x!=&y){
Chris@16:     iterator first0=x.begin(),last0=x.end();
Chris@16:     iterator first1=y.begin(),last1=y.end();
Chris@16:     while(first0!=last0&&first1!=last1){
Chris@16:       if(comp(*first1,*first0))x.splice(first0,y,first1++);
Chris@16:       else ++first0;
Chris@16:     }
Chris@16:     x.splice(last0,y,first1,last1);
Chris@16:   }
Chris@16: }
Chris@16: 
Chris@16: /* sorting  */
Chris@16: 
Chris@16: /* auxiliary stuff */
Chris@16: 
Chris@16: template<typename Node,typename Compare>
Chris@16: void sequenced_index_collate(
Chris@16:   BOOST_DEDUCED_TYPENAME Node::impl_type* x,
Chris@16:   BOOST_DEDUCED_TYPENAME Node::impl_type* y,
Chris@101:   Compare comp)
Chris@16: {
Chris@16:   typedef typename Node::impl_type    impl_type;
Chris@16:   typedef typename Node::impl_pointer impl_pointer;
Chris@16: 
Chris@16:   impl_pointer first0=x->next();
Chris@16:   impl_pointer last0=x;
Chris@16:   impl_pointer first1=y->next();
Chris@16:   impl_pointer last1=y;
Chris@16:   while(first0!=last0&&first1!=last1){
Chris@16:     if(comp(
Chris@16:         Node::from_impl(first1)->value(),Node::from_impl(first0)->value())){
Chris@16:       impl_pointer tmp=first1->next();
Chris@16:       impl_type::relink(first0,first1);
Chris@16:       first1=tmp;
Chris@16:     }
Chris@16:     else first0=first0->next();
Chris@16:   }
Chris@16:   impl_type::relink(last0,first1,last1);
Chris@16: }
Chris@16: 
Chris@16: /* Some versions of CGG require a bogus typename in counter_spc
Chris@16:  * inside sequenced_index_sort if the following is defined
Chris@16:  * also inside sequenced_index_sort.
Chris@16:  */
Chris@16: 
Chris@16: BOOST_STATIC_CONSTANT(
Chris@16:   std::size_t,
Chris@16:   sequenced_index_sort_max_fill=
Chris@16:     (std::size_t)std::numeric_limits<std::size_t>::digits+1);
Chris@16: 
Chris@16: template<typename Node,typename Compare>
Chris@16: void sequenced_index_sort(Node* header,Compare comp)
Chris@16: {
Chris@16:   /* Musser's mergesort, see http://www.cs.rpi.edu/~musser/gp/List/lists1.html.
Chris@16:    * The implementation is a little convoluted: in the original code
Chris@16:    * counter elements and carry are std::lists: here we do not want
Chris@16:    * to use multi_index instead, so we do things at a lower level, managing
Chris@16:    * directly the internal node representation.
Chris@16:    * Incidentally, the implementations I've seen of this algorithm (SGI,
Chris@16:    * Dinkumware, STLPort) are not exception-safe: this is. Moreover, we do not
Chris@16:    * use any dynamic storage.
Chris@16:    */
Chris@16: 
Chris@16:   if(header->next()==header->impl()||
Chris@16:      header->next()->next()==header->impl())return;
Chris@16: 
Chris@16:   typedef typename Node::impl_type      impl_type;
Chris@16:   typedef typename Node::impl_pointer   impl_pointer;
Chris@16: 
Chris@16:   typedef typename aligned_storage<
Chris@16:     sizeof(impl_type),
Chris@16:     alignment_of<impl_type>::value
Chris@16:   >::type                               carry_spc_type;
Chris@16:   carry_spc_type                        carry_spc;
Chris@16:   impl_type&                            carry=
Chris@16:     *static_cast<impl_type*>(static_cast<void*>(&carry_spc));
Chris@16:   typedef typename aligned_storage<
Chris@16:     sizeof(
Chris@16:       impl_type
Chris@16:         [sequenced_index_sort_max_fill]),
Chris@16:     alignment_of<
Chris@16:       impl_type
Chris@16:         [sequenced_index_sort_max_fill]
Chris@16:     >::value
Chris@16:   >::type                               counter_spc_type;
Chris@16:   counter_spc_type                      counter_spc;
Chris@16:   impl_type*                            counter=
Chris@16:     static_cast<impl_type*>(static_cast<void*>(&counter_spc));
Chris@16:   std::size_t                           fill=0;
Chris@16: 
Chris@16:   carry.prior()=carry.next()=static_cast<impl_pointer>(&carry);
Chris@16:   counter[0].prior()=counter[0].next()=static_cast<impl_pointer>(&counter[0]);
Chris@16: 
Chris@16:   BOOST_TRY{
Chris@16:     while(header->next()!=header->impl()){
Chris@16:       impl_type::relink(carry.next(),header->next());
Chris@16:       std::size_t i=0;
Chris@16:       while(i<fill&&counter[i].next()!=static_cast<impl_pointer>(&counter[i])){
Chris@16:         sequenced_index_collate<Node>(&carry,&counter[i++],comp);
Chris@16:       }
Chris@16:       impl_type::swap(
Chris@16:         static_cast<impl_pointer>(&carry),
Chris@16:         static_cast<impl_pointer>(&counter[i]));
Chris@16:       if(i==fill){
Chris@16:         ++fill;
Chris@16:         counter[fill].prior()=counter[fill].next()=
Chris@16:           static_cast<impl_pointer>(&counter[fill]);
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     for(std::size_t i=1;i<fill;++i){
Chris@16:       sequenced_index_collate<Node>(&counter[i],&counter[i-1],comp);
Chris@16:     }
Chris@16:     impl_type::swap(
Chris@16:       header->impl(),static_cast<impl_pointer>(&counter[fill-1]));
Chris@16:   }
Chris@16:   BOOST_CATCH(...)
Chris@16:   {
Chris@16:     impl_type::relink(
Chris@16:       header->impl(),carry.next(),static_cast<impl_pointer>(&carry));
Chris@16:     for(std::size_t i=0;i<=fill;++i){
Chris@16:       impl_type::relink(
Chris@16:         header->impl(),counter[i].next(),
Chris@16:         static_cast<impl_pointer>(&counter[i]));
Chris@16:     }
Chris@16:     BOOST_RETHROW;
Chris@16:   }
Chris@16:   BOOST_CATCH_END
Chris@16: }
Chris@16: 
Chris@16: } /* namespace multi_index::detail */
Chris@16: 
Chris@16: } /* namespace multi_index */
Chris@16: 
Chris@16: } /* namespace boost */
Chris@16: 
Chris@16: #endif