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