epoc32/include/stdapis/boost/multi_index/detail/seq_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-2006 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_SEQ_INDEX_OPS_HPP
williamr@2
    10
#define BOOST_MULTI_INDEX_DETAIL_SEQ_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 <boost/detail/no_exceptions_support.hpp>
williamr@2
    18
#include <boost/multi_index/detail/seq_index_node.hpp>
williamr@2
    19
#include <boost/limits.hpp>
williamr@2
    20
#include <boost/type_traits/aligned_storage.hpp>
williamr@2
    21
#include <boost/type_traits/alignment_of.hpp> 
williamr@2
    22
#include <cstddef>
williamr@2
    23
williamr@2
    24
namespace boost{
williamr@2
    25
williamr@2
    26
namespace multi_index{
williamr@2
    27
williamr@2
    28
namespace detail{
williamr@2
    29
williamr@2
    30
/* Common code for sequenced_index memfuns having templatized and
williamr@2
    31
 * non-templatized versions.
williamr@2
    32
 */
williamr@2
    33
williamr@2
    34
template <typename SequencedIndex,typename Predicate>
williamr@2
    35
void sequenced_index_remove(SequencedIndex& x,Predicate pred)
williamr@2
    36
{
williamr@2
    37
  typedef typename SequencedIndex::iterator iterator;
williamr@2
    38
  iterator first=x.begin(),last=x.end();
williamr@2
    39
  while(first!=last){
williamr@2
    40
    if(pred(*first))x.erase(first++);
williamr@2
    41
    else ++first;
williamr@2
    42
  }
williamr@2
    43
}
williamr@2
    44
williamr@2
    45
template <typename SequencedIndex,class BinaryPredicate>
williamr@2
    46
void sequenced_index_unique(SequencedIndex& x,BinaryPredicate binary_pred)
williamr@2
    47
{
williamr@2
    48
  typedef typename SequencedIndex::iterator iterator;
williamr@2
    49
  iterator first=x.begin();
williamr@2
    50
  iterator last=x.end();
williamr@2
    51
  if(first!=last){
williamr@2
    52
    for(iterator middle=first;++middle!=last;middle=first){
williamr@2
    53
      if(binary_pred(*middle,*first))x.erase(middle);
williamr@2
    54
      else first=middle;
williamr@2
    55
    }
williamr@2
    56
  }
williamr@2
    57
}
williamr@2
    58
williamr@2
    59
template <typename SequencedIndex,typename Compare>
williamr@2
    60
void sequenced_index_merge(SequencedIndex& x,SequencedIndex& y,Compare comp)
williamr@2
    61
{
williamr@2
    62
  typedef typename SequencedIndex::iterator iterator;
williamr@2
    63
  if(&x!=&y){
williamr@2
    64
    iterator first0=x.begin(),last0=x.end();
williamr@2
    65
    iterator first1=y.begin(),last1=y.end();
williamr@2
    66
    while(first0!=last0&&first1!=last1){
williamr@2
    67
      if(comp(*first1,*first0))x.splice(first0,y,first1++);
williamr@2
    68
      else ++first0;
williamr@2
    69
    }
williamr@2
    70
    x.splice(last0,y,first1,last1);
williamr@2
    71
  }
williamr@2
    72
}
williamr@2
    73
williamr@2
    74
/* sorting  */
williamr@2
    75
williamr@2
    76
/* auxiliary stuff */
williamr@2
    77
williamr@2
    78
template<typename Node,typename Compare>
williamr@2
    79
void sequenced_index_collate(
williamr@2
    80
  sequenced_index_node_impl* x,sequenced_index_node_impl* y,Compare comp
williamr@2
    81
  BOOST_APPEND_EXPLICIT_TEMPLATE_TYPE(Node))
williamr@2
    82
{
williamr@2
    83
  sequenced_index_node_impl* first0=x->next();
williamr@2
    84
  sequenced_index_node_impl* last0=x;
williamr@2
    85
  sequenced_index_node_impl* first1=y->next();
williamr@2
    86
  sequenced_index_node_impl* last1=y;
williamr@2
    87
  while(first0!=last0&&first1!=last1){
williamr@2
    88
    if(comp(
williamr@2
    89
        Node::from_impl(first1)->value(),Node::from_impl(first0)->value())){
williamr@2
    90
      sequenced_index_node_impl* tmp=first1->next();
williamr@2
    91
      sequenced_index_node_impl::relink(first0,first1);
williamr@2
    92
      first1=tmp;
williamr@2
    93
    }
williamr@2
    94
    else first0=first0->next();
williamr@2
    95
  }
williamr@2
    96
  sequenced_index_node_impl::relink(last0,first1,last1);
williamr@2
    97
}
williamr@2
    98
williamr@2
    99
/* Some versions of CGG require a bogus typename in counter_spc
williamr@2
   100
 * inside sequenced_index_sort if the following is defined
williamr@2
   101
 * also inside sequenced_index_sort.
williamr@2
   102
 */
williamr@2
   103
williamr@2
   104
BOOST_STATIC_CONSTANT(
williamr@2
   105
  std::size_t,
williamr@2
   106
  sequenced_index_sort_max_fill=
williamr@2
   107
    (std::size_t)std::numeric_limits<std::size_t>::digits+1);
williamr@2
   108
williamr@2
   109
template<typename Node,typename Compare>
williamr@2
   110
void sequenced_index_sort(Node* header,Compare comp)
williamr@2
   111
{
williamr@2
   112
  /* Musser's mergesort, see http://www.cs.rpi.edu/~musser/gp/List/lists1.html.
williamr@2
   113
   * The implementation is a little convoluted: in the original code
williamr@2
   114
   * counter elements and carry are std::lists: here we do not want
williamr@2
   115
   * to use multi_index instead, so we do things at a lower level, managing
williamr@2
   116
   * directly the internal node representation.
williamr@2
   117
   * Incidentally, the implementations I've seen of this algorithm (SGI,
williamr@2
   118
   * Dinkumware, STLPort) are not exception-safe: this is. Moreover, we do not
williamr@2
   119
   * use any dynamic storage.
williamr@2
   120
   */
williamr@2
   121
williamr@2
   122
  if(header->next()==header->impl()||
williamr@2
   123
     header->next()->next()==header->impl())return;
williamr@2
   124
williamr@2
   125
  aligned_storage<
williamr@2
   126
    sizeof(sequenced_index_node_impl),
williamr@2
   127
    alignment_of<
williamr@2
   128
    sequenced_index_node_impl>::value
williamr@2
   129
  >::type                                   carry_spc;
williamr@2
   130
  sequenced_index_node_impl&                carry=
williamr@2
   131
    *static_cast<sequenced_index_node_impl*>(static_cast<void*>(&carry_spc));
williamr@2
   132
  aligned_storage<
williamr@2
   133
    sizeof(
williamr@2
   134
      sequenced_index_node_impl
williamr@2
   135
        [sequenced_index_sort_max_fill]),
williamr@2
   136
    alignment_of<
williamr@2
   137
      sequenced_index_node_impl
williamr@2
   138
        [sequenced_index_sort_max_fill]
williamr@2
   139
    >::value
williamr@2
   140
  >::type                                   counter_spc;
williamr@2
   141
  sequenced_index_node_impl*                counter=
williamr@2
   142
    static_cast<sequenced_index_node_impl*>(static_cast<void*>(&counter_spc));
williamr@2
   143
  std::size_t                               fill=0;
williamr@2
   144
williamr@2
   145
  carry.prior()=carry.next()=&carry;
williamr@2
   146
  counter[0].prior()=counter[0].next()=&counter[0];
williamr@2
   147
williamr@2
   148
  BOOST_TRY{
williamr@2
   149
    while(header->next()!=header->impl()){
williamr@2
   150
      sequenced_index_node_impl::relink(carry.next(),header->next());
williamr@2
   151
      std::size_t i=0;
williamr@2
   152
      while(i<fill&&counter[i].next()!=&counter[i]){
williamr@2
   153
        sequenced_index_collate<Node>(&carry,&counter[i++],comp);
williamr@2
   154
      }
williamr@2
   155
      sequenced_index_node_impl::swap(&carry,&counter[i]);
williamr@2
   156
      if(i==fill){
williamr@2
   157
        ++fill;
williamr@2
   158
        counter[fill].prior()=counter[fill].next()=&counter[fill];
williamr@2
   159
      }
williamr@2
   160
    }
williamr@2
   161
williamr@2
   162
    for(std::size_t i=1;i<fill;++i){
williamr@2
   163
      sequenced_index_collate<Node>(&counter[i],&counter[i-1],comp);
williamr@2
   164
    }
williamr@2
   165
    sequenced_index_node_impl::swap(header->impl(),&counter[fill-1]);
williamr@2
   166
  }
williamr@2
   167
  BOOST_CATCH(...)
williamr@2
   168
  {
williamr@2
   169
    sequenced_index_node_impl::relink(header->impl(),carry.next(),&carry);
williamr@2
   170
    for(std::size_t i=0;i<=fill;++i){
williamr@2
   171
      sequenced_index_node_impl::relink(
williamr@2
   172
        header->impl(),counter[i].next(),&counter[i]);
williamr@2
   173
    }
williamr@2
   174
    BOOST_RETHROW;
williamr@2
   175
  }
williamr@2
   176
  BOOST_CATCH_END
williamr@2
   177
}
williamr@2
   178
williamr@2
   179
} /* namespace multi_index::detail */
williamr@2
   180
williamr@2
   181
} /* namespace multi_index */
williamr@2
   182
williamr@2
   183
} /* namespace boost */
williamr@2
   184
williamr@2
   185
#endif