]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
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 |