1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/stdapis/boost/pending/bucket_sorter.hpp Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -0,0 +1,134 @@
1.4 +//
1.5 +//=======================================================================
1.6 +// Copyright 1997, 1998, 1999, 2000 University of Notre Dame.
1.7 +// Authors: Andrew Lumsdaine, Lie-Quan Lee, Jeremy G. Siek
1.8 +//
1.9 +// Distributed under the Boost Software License, Version 1.0. (See
1.10 +// accompanying file LICENSE_1_0.txt or copy at
1.11 +// http://www.boost.org/LICENSE_1_0.txt)
1.12 +//=======================================================================
1.13 +//
1.14 +//
1.15 +// Revision History:
1.16 +// 13 June 2001: Changed some names for clarity. (Jeremy Siek)
1.17 +// 01 April 2001: Modified to use new <boost/limits.hpp> header. (JMaddock)
1.18 +//
1.19 +#ifndef BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP
1.20 +#define BOOST_GRAPH_DETAIL_BUCKET_SORTER_HPP
1.21 +
1.22 +#include <vector>
1.23 +#include <cassert>
1.24 +#include <boost/limits.hpp>
1.25 +
1.26 +namespace boost {
1.27 +
1.28 + template <class BucketType, class ValueType, class Bucket,
1.29 + class ValueIndexMap>
1.30 + class bucket_sorter {
1.31 + public:
1.32 + typedef BucketType bucket_type;
1.33 + typedef ValueType value_type;
1.34 + typedef typename std::vector<value_type>::size_type size_type;
1.35 +
1.36 + bucket_sorter(size_type _length, bucket_type _max_bucket,
1.37 + const Bucket& _bucket = Bucket(),
1.38 + const ValueIndexMap& _id = ValueIndexMap())
1.39 + : head(_max_bucket, invalid_value()),
1.40 + next(_length, invalid_value()),
1.41 + prev(_length, invalid_value()),
1.42 + id_to_value(_length),
1.43 + bucket(_bucket), id(_id) { }
1.44 +
1.45 + void remove(const value_type& x) {
1.46 + const size_type i = get(id, x);
1.47 + const size_type& next_node = next[i];
1.48 + const size_type& prev_node = prev[i];
1.49 +
1.50 + //check if i is the end of the bucket list
1.51 + if ( next_node != invalid_value() )
1.52 + prev[next_node] = prev_node;
1.53 + //check if i is the begin of the bucket list
1.54 + if ( prev_node != invalid_value() )
1.55 + next[prev_node] = next_node;
1.56 + else //need update head of current bucket list
1.57 + head[ bucket[x] ] = next_node;
1.58 + }
1.59 +
1.60 + void push(const value_type& x) {
1.61 + id_to_value[get(id, x)] = x;
1.62 + (*this)[bucket[x]].push(x);
1.63 + }
1.64 +
1.65 + void update(const value_type& x) {
1.66 + remove(x);
1.67 + (*this)[bucket[x]].push(x);
1.68 + }
1.69 + // private:
1.70 + // with KCC, the nested stack class is having access problems
1.71 + // despite the friend decl.
1.72 + static size_type invalid_value() {
1.73 + return (std::numeric_limits<size_type>::max)();
1.74 + }
1.75 +
1.76 + typedef typename std::vector<size_type>::iterator Iter;
1.77 + typedef typename std::vector<value_type>::iterator IndexValueMap;
1.78 +
1.79 + public:
1.80 + friend class stack;
1.81 +
1.82 + class stack {
1.83 + public:
1.84 + stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v,
1.85 + const ValueIndexMap& _id)
1.86 + : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v), id(_id) {}
1.87 +
1.88 + // Avoid using default arg for ValueIndexMap so that the default
1.89 + // constructor of the ValueIndexMap is not required if not used.
1.90 + stack(bucket_type _bucket_id, Iter h, Iter n, Iter p, IndexValueMap v)
1.91 + : bucket_id(_bucket_id), head(h), next(n), prev(p), value(v) {}
1.92 +
1.93 + void push(const value_type& x) {
1.94 + const size_type new_head = get(id, x);
1.95 + const size_type current = head[bucket_id];
1.96 + if ( current != invalid_value() )
1.97 + prev[current] = new_head;
1.98 + prev[new_head] = invalid_value();
1.99 + next[new_head] = current;
1.100 + head[bucket_id] = new_head;
1.101 + }
1.102 + void pop() {
1.103 + size_type current = head[bucket_id];
1.104 + size_type next_node = next[current];
1.105 + head[bucket_id] = next_node;
1.106 + if ( next_node != invalid_value() )
1.107 + prev[next_node] = invalid_value();
1.108 + }
1.109 + value_type& top() { return value[ head[bucket_id] ]; }
1.110 + const value_type& top() const { return value[ head[bucket_id] ]; }
1.111 + bool empty() const { return head[bucket_id] == invalid_value(); }
1.112 + private:
1.113 + bucket_type bucket_id;
1.114 + Iter head;
1.115 + Iter next;
1.116 + Iter prev;
1.117 + IndexValueMap value;
1.118 + ValueIndexMap id;
1.119 + };
1.120 +
1.121 + stack operator[](const bucket_type& i) {
1.122 + assert(i < head.size());
1.123 + return stack(i, head.begin(), next.begin(), prev.begin(),
1.124 + id_to_value.begin(), id);
1.125 + }
1.126 + protected:
1.127 + std::vector<size_type> head;
1.128 + std::vector<size_type> next;
1.129 + std::vector<size_type> prev;
1.130 + std::vector<value_type> id_to_value;
1.131 + Bucket bucket;
1.132 + ValueIndexMap id;
1.133 + };
1.134 +
1.135 +}
1.136 +
1.137 +#endif