epoc32/include/stdapis/boost/multi_index/detail/rnd_index_ops.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:27:01 +0100
branchSymbian2
changeset 3 e1b950c65cb4
permissions -rw-r--r--
Attempt to represent the S^2->S^3 header reorganisation as a series of "hg rename" operations
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