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