epoc32/include/stdapis/boost/multi_index/detail/index_matcher.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_INDEX_MATCHER_HPP
williamr@2
    10
#define BOOST_MULTI_INDEX_DETAIL_INDEX_MATCHER_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/noncopyable.hpp>
williamr@2
    19
#include <boost/multi_index/detail/auto_space.hpp>
williamr@2
    20
#include <cstddef>
williamr@2
    21
#include <functional>
williamr@2
    22
williamr@2
    23
namespace boost{
williamr@2
    24
williamr@2
    25
namespace multi_index{
williamr@2
    26
williamr@2
    27
namespace detail{
williamr@2
    28
williamr@2
    29
/* index_matcher compares a sequence of elements against a
williamr@2
    30
 * base sequence, identifying those elements that belong to the
williamr@2
    31
 * longest subsequence which is ordered with respect to the base.
williamr@2
    32
 * For instance, if the base sequence is:
williamr@2
    33
 *
williamr@2
    34
 *   0 1 2 3 4 5 6 7 8 9
williamr@2
    35
 *
williamr@2
    36
 * and the compared sequence (not necesarilly the same length):
williamr@2
    37
 *
williamr@2
    38
 *   1 4 2 3 0 7 8 9
williamr@2
    39
 *
williamr@2
    40
 * the elements of the longest ordered subsequence are:
williamr@2
    41
 *
williamr@2
    42
 *   1 2 3 7 8 9
williamr@2
    43
 * 
williamr@2
    44
 * The algorithm for obtaining such a subsequence is called
williamr@2
    45
 * Patience Sorting, described in ch. 1 of:
williamr@2
    46
 *   Aldous, D., Diaconis, P.: "Longest increasing subsequences: from
williamr@2
    47
 *   patience sorting to the Baik-Deift-Johansson Theorem", Bulletin
williamr@2
    48
 *   of the American Mathematical Society, vol. 36, no 4, pp. 413-432,
williamr@2
    49
 *   July 1999.
williamr@2
    50
 *   http://www.ams.org/bull/1999-36-04/S0273-0979-99-00796-X/
williamr@2
    51
 *   S0273-0979-99-00796-X.pdf
williamr@2
    52
 *
williamr@2
    53
 * This implementation is not fully generic since it assumes that
williamr@2
    54
 * the sequences given are pointed to by index iterators (having a
williamr@2
    55
 * get_node() memfun.)
williamr@2
    56
 */
williamr@2
    57
williamr@2
    58
namespace index_matcher{
williamr@2
    59
williamr@2
    60
/* The algorithm stores the nodes of the base sequence and a number
williamr@2
    61
 * of "piles" that are dynamically updated during the calculation
williamr@2
    62
 * stage. From a logical point of view, nodes form an independent
williamr@2
    63
 * sequence from piles. They are stored together so as to minimize
williamr@2
    64
 * allocated memory.
williamr@2
    65
 */
williamr@2
    66
williamr@2
    67
struct entry
williamr@2
    68
{
williamr@2
    69
  entry(void* node_,std::size_t pos_=0):node(node_),pos(pos_){}
williamr@2
    70
williamr@2
    71
  /* node stuff */
williamr@2
    72
williamr@2
    73
  void*       node;
williamr@2
    74
  std::size_t pos;
williamr@2
    75
  entry*      previous;
williamr@2
    76
  bool        ordered;
williamr@2
    77
williamr@2
    78
  struct less_by_node
williamr@2
    79
  {
williamr@2
    80
    bool operator()(
williamr@2
    81
      const entry& x,const entry& y)const
williamr@2
    82
    {
williamr@2
    83
      return std::less<void*>()(x.node,y.node);
williamr@2
    84
    }
williamr@2
    85
  };
williamr@2
    86
williamr@2
    87
  /* pile stuff */
williamr@2
    88
williamr@2
    89
  std::size_t pile_top;
williamr@2
    90
  entry*      pile_top_entry;
williamr@2
    91
williamr@2
    92
  struct less_by_pile_top
williamr@2
    93
  {
williamr@2
    94
    bool operator()(
williamr@2
    95
      const entry& x,const entry& y)const
williamr@2
    96
    {
williamr@2
    97
      return x.pile_top<y.pile_top;
williamr@2
    98
    }
williamr@2
    99
  };
williamr@2
   100
};
williamr@2
   101
williamr@2
   102
/* common code operating on void *'s */
williamr@2
   103
williamr@2
   104
template<typename Allocator>
williamr@2
   105
class algorithm_base:private noncopyable
williamr@2
   106
{
williamr@2
   107
protected:
williamr@2
   108
  algorithm_base(const Allocator& al,std::size_t size):
williamr@2
   109
    spc(al,size),size_(size),n(0),sorted(false)
williamr@2
   110
  {
williamr@2
   111
  }
williamr@2
   112
williamr@2
   113
  void add(void* node)
williamr@2
   114
  {
williamr@2
   115
    entries()[n]=entry(node,n);
williamr@2
   116
    ++n;
williamr@2
   117
  }
williamr@2
   118
williamr@2
   119
  void begin_algorithm()const
williamr@2
   120
  {
williamr@2
   121
    if(!sorted){
williamr@2
   122
      std::sort(entries(),entries()+size_,entry::less_by_node());
williamr@2
   123
      sorted=true;
williamr@2
   124
    }
williamr@2
   125
    num_piles=0;
williamr@2
   126
  }
williamr@2
   127
williamr@2
   128
  void add_node_to_algorithm(void* node)const
williamr@2
   129
  {
williamr@2
   130
    entry* ent=
williamr@2
   131
      std::lower_bound(
williamr@2
   132
        entries(),entries()+size_,
williamr@2
   133
        entry(node),entry::less_by_node()); /* localize entry */
williamr@2
   134
    ent->ordered=false;
williamr@2
   135
    std::size_t n=ent->pos;                 /* get its position */
williamr@2
   136
williamr@2
   137
    entry dummy(0);
williamr@2
   138
    dummy.pile_top=n;
williamr@2
   139
williamr@2
   140
    entry* pile_ent=                        /* find the first available pile */
williamr@2
   141
      std::lower_bound(                     /* to stack the entry            */
williamr@2
   142
        entries(),entries()+num_piles,
williamr@2
   143
        dummy,entry::less_by_pile_top());
williamr@2
   144
williamr@2
   145
    pile_ent->pile_top=n;                   /* stack the entry */
williamr@2
   146
    pile_ent->pile_top_entry=ent;        
williamr@2
   147
williamr@2
   148
    /* if not the first pile, link entry to top of the preceding pile */
williamr@2
   149
    if(pile_ent>&entries()[0]){ 
williamr@2
   150
      ent->previous=(pile_ent-1)->pile_top_entry;
williamr@2
   151
    }
williamr@2
   152
williamr@2
   153
    if(pile_ent==&entries()[num_piles]){    /* new pile? */
williamr@2
   154
      ++num_piles;
williamr@2
   155
    }
williamr@2
   156
  }
williamr@2
   157
williamr@2
   158
  void finish_algorithm()const
williamr@2
   159
  {
williamr@2
   160
    if(num_piles>0){
williamr@2
   161
      /* Mark those elements which are in their correct position, i.e. those
williamr@2
   162
       * belonging to the longest increasing subsequence. These are those
williamr@2
   163
       * elements linked from the top of the last pile.
williamr@2
   164
       */
williamr@2
   165
williamr@2
   166
      entry* ent=entries()[num_piles-1].pile_top_entry;
williamr@2
   167
      for(std::size_t n=num_piles;n--;){
williamr@2
   168
        ent->ordered=true;
williamr@2
   169
        ent=ent->previous;
williamr@2
   170
      }
williamr@2
   171
    }
williamr@2
   172
  }
williamr@2
   173
williamr@2
   174
  bool is_ordered(void * node)const
williamr@2
   175
  {
williamr@2
   176
    return std::lower_bound(
williamr@2
   177
      entries(),entries()+size_,
williamr@2
   178
      entry(node),entry::less_by_node())->ordered;
williamr@2
   179
  }
williamr@2
   180
williamr@2
   181
private:
williamr@2
   182
  entry* entries()const{return spc.data();}
williamr@2
   183
williamr@2
   184
  auto_space<entry,Allocator> spc;
williamr@2
   185
  std::size_t                 size_;
williamr@2
   186
  std::size_t                 n;
williamr@2
   187
  mutable bool                sorted;
williamr@2
   188
  mutable std::size_t         num_piles;
williamr@2
   189
};
williamr@2
   190
williamr@2
   191
/* The algorithm has three phases:
williamr@2
   192
 *   - Initialization, during which the nodes of the base sequence are added.
williamr@2
   193
 *   - Execution.
williamr@2
   194
 *   - Results querying, through the is_ordered memfun.
williamr@2
   195
 */
williamr@2
   196
williamr@2
   197
template<typename Node,typename Allocator>
williamr@2
   198
class algorithm:private algorithm_base<Allocator>
williamr@2
   199
{
williamr@2
   200
  typedef algorithm_base<Allocator> super;
williamr@2
   201
williamr@2
   202
public:
williamr@2
   203
  algorithm(const Allocator& al,std::size_t size):super(al,size){}
williamr@2
   204
williamr@2
   205
  void add(Node* node)
williamr@2
   206
  {
williamr@2
   207
    super::add(node);
williamr@2
   208
  }
williamr@2
   209
williamr@2
   210
  template<typename IndexIterator>
williamr@2
   211
  void execute(IndexIterator first,IndexIterator last)const
williamr@2
   212
  {
williamr@2
   213
    super::begin_algorithm();
williamr@2
   214
williamr@2
   215
    for(IndexIterator it=first;it!=last;++it){
williamr@2
   216
      add_node_to_algorithm(get_node(it));
williamr@2
   217
    }
williamr@2
   218
williamr@2
   219
    super::finish_algorithm();
williamr@2
   220
  }
williamr@2
   221
williamr@2
   222
  bool is_ordered(Node* node)const
williamr@2
   223
  {
williamr@2
   224
    return super::is_ordered(node);
williamr@2
   225
  }
williamr@2
   226
williamr@2
   227
private:
williamr@2
   228
  void add_node_to_algorithm(Node* node)const
williamr@2
   229
  {
williamr@2
   230
    super::add_node_to_algorithm(node);
williamr@2
   231
  }
williamr@2
   232
williamr@2
   233
  template<typename IndexIterator>
williamr@2
   234
  static Node* get_node(IndexIterator it)
williamr@2
   235
  {
williamr@2
   236
    return static_cast<Node*>(it.get_node());
williamr@2
   237
  }
williamr@2
   238
};
williamr@2
   239
williamr@2
   240
} /* namespace multi_index::detail::index_matcher */
williamr@2
   241
williamr@2
   242
} /* namespace multi_index::detail */
williamr@2
   243
williamr@2
   244
} /* namespace multi_index */
williamr@2
   245
williamr@2
   246
} /* namespace boost */
williamr@2
   247
williamr@2
   248
#endif