boost_ext/boost/multi_index/detail/rnd_index_ops.hpp

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