epoc32/include/stdapis/boost/pending/bucket_sorter.hpp
author William Roberts <williamr@symbian.org>
Wed, 31 Mar 2010 12:33:34 +0100
branchSymbian3
changeset 4 837f303aceeb
permissions -rw-r--r--
Current Symbian^3 public API header files (from PDK 3.0.h)
This is the epoc32/include tree with the "platform" subtrees removed, and
all but a selected few mbg and rsg files removed.
williamr@2
     1
//
williamr@2
     2
//=======================================================================
williamr@2
     3
// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
williamr@2
     4
// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
williamr@2
     5
//
williamr@2
     6
// Distributed under the Boost Software License, Version 1.0. (See
williamr@2
     7
// accompanying file LICENSE_1_0.txt or copy at
williamr@2
     8
// http://www.boost.org/LICENSE_1_0.txt)
williamr@2
     9
//=======================================================================
williamr@2
    10
//
williamr@2
    11
//
williamr@2
    12
// Revision History:
williamr@2
    13
//   13 June 2001: Changed some names for clarity. (Jeremy Siek)
williamr@2
    14
//   01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
williamr@2
    15
//
williamr@2
    16
#ifndef BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP
williamr@2
    17
#define BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP
williamr@2
    18
williamr@2
    19
#include <vector>
williamr@2
    20
#include <cassert>
williamr@2
    21
#include <boost/limits.hpp>
williamr@2
    22
williamr@2
    23
namespace boost {
williamr@2
    24
williamr@2
    25
  template <class BucketType, class ValueType, class Bucket, 
williamr@2
    26
            class ValueIndexMap>
williamr@2
    27
  class bucket_sorter {
williamr@2
    28
  public:
williamr@2
    29
    typedef BucketType bucket_type;
williamr@2
    30
    typedef ValueType value_type;
williamr@2
    31
    typedef typename std::vector<value_type>::size_type size_type;
williamr@2
    32
    
williamr@2
    33
    bucket_sorter(size_type _length, bucket_type _max_bucket, 
williamr@2
    34
                  const Bucket& _bucket = Bucket(), 
williamr@2
    35
                  const ValueIndexMap& _id = ValueIndexMap()) 
williamr@2
    36
      : head(_max_bucket, invalid_value()),
williamr@2
    37
        next(_length, invalid_value()), 
williamr@2
    38
        prev(_length, invalid_value()),
williamr@2
    39
        id_to_value(_length),
williamr@2
    40
        bucket(_bucket), id(_id) { }
williamr@2
    41
    
williamr@2
    42
    void remove(const value_type& x) {
williamr@2
    43
      const size_type i = get(id, x);
williamr@2
    44
      const size_type& next_node = next[i];
williamr@2
    45
      const size_type& prev_node = prev[i];
williamr@2
    46
    
williamr@2
    47
      //check if i is the end of the bucket list 
williamr@2
    48
      if ( next_node != invalid_value() )
williamr@2
    49
        prev[next_node] = prev_node; 
williamr@2
    50
      //check if i is the begin of the bucket list
williamr@2
    51
      if ( prev_node != invalid_value() )
williamr@2
    52
        next[prev_node] = next_node;
williamr@2
    53
      else //need update head of current bucket list
williamr@2
    54
        head[ bucket[x] ] = next_node;
williamr@2
    55
    }
williamr@2
    56
williamr@2
    57
    void push(const value_type& x) {
williamr@2
    58
      id_to_value[get(id, x)] = x;
williamr@2
    59
      (*this)[bucket[x]].push(x);
williamr@2
    60
    }
williamr@2
    61
    
williamr@2
    62
    void update(const value_type& x) {
williamr@2
    63
      remove(x);
williamr@2
    64
      (*this)[bucket[x]].push(x);
williamr@2
    65
    }
williamr@2
    66
    //  private: 
williamr@2
    67
    //    with KCC, the nested stack class is having access problems
williamr@2
    68
    //    despite the friend decl.
williamr@2
    69
    static size_type invalid_value() {
williamr@2
    70
      return (std::numeric_limits<size_type>::max)();
williamr@2
    71
    }
williamr@2
    72
    
williamr@2
    73
    typedef typename std::vector<size_type>::iterator Iter;
williamr@2
    74
    typedef typename std::vector<value_type>::iterator IndexValueMap;
williamr@2
    75
    
williamr@2
    76
  public:
williamr@2
    77
    friend class stack;
williamr@2
    78
williamr@2
    79
    class stack {
williamr@2
    80
    public:
williamr@2
    81
      stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v,
williamr@2
    82
            const ValueIndexMap& _id)
williamr@2
    83
      : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v), id(_id) {}
williamr@2
    84
williamr@2
    85
      // Avoid using default arg for ValueIndexMap so that the default
williamr@2
    86
      // constructor of the ValueIndexMap is not required if not used.
williamr@2
    87
      stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v)
williamr@2
    88
        : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v) {}
williamr@2
    89
      
williamr@2
    90
      void push(const value_type& x) {
williamr@2
    91
        const size_type new_head = get(id, x);
williamr@2
    92
        const size_type current = head[bucket_id];
williamr@2
    93
        if ( current != invalid_value() )
williamr@2
    94
          prev[current] = new_head;
williamr@2
    95
        prev[new_head] = invalid_value();
williamr@2
    96
        next[new_head] = current;
williamr@2
    97
        head[bucket_id] = new_head;
williamr@2
    98
      }
williamr@2
    99
      void pop() {
williamr@2
   100
        size_type current = head[bucket_id];
williamr@2
   101
        size_type next_node = next[current];
williamr@2
   102
        head[bucket_id] = next_node;
williamr@2
   103
        if ( next_node != invalid_value() )
williamr@2
   104
          prev[next_node] = invalid_value();
williamr@2
   105
      }
williamr@2
   106
      value_type& top() { return value[ head[bucket_id] ]; }
williamr@2
   107
      const value_type& top() const { return value[ head[bucket_id] ]; }
williamr@2
   108
      bool empty() const { return head[bucket_id] == invalid_value(); }
williamr@2
   109
    private:
williamr@2
   110
      bucket_type bucket_id;
williamr@2
   111
      Iter head;
williamr@2
   112
      Iter next;
williamr@2
   113
      Iter prev;
williamr@2
   114
      IndexValueMap value;
williamr@2
   115
      ValueIndexMap id;
williamr@2
   116
    };
williamr@2
   117
    
williamr@2
   118
    stack operator[](const bucket_type& i) {
williamr@2
   119
      assert(i < head.size());
williamr@2
   120
      return stack(i, head.begin(), next.begin(), prev.begin(),
williamr@2
   121
                   id_to_value.begin(), id);
williamr@2
   122
    }
williamr@2
   123
  protected:
williamr@2
   124
    std::vector<size_type>   head;
williamr@2
   125
    std::vector<size_type>   next;
williamr@2
   126
    std::vector<size_type>   prev;
williamr@2
   127
    std::vector<value_type>  id_to_value;
williamr@2
   128
    Bucket bucket;
williamr@2
   129
    ValueIndexMap id;
williamr@2
   130
  };
williamr@2
   131
  
williamr@2
   132
}
williamr@2
   133
williamr@2
   134
#endif