blob: 788352c9fe058e6be2bc4b9c9d6a5c3231e653de (
plain)
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
|
#ifndef ALONE_GRAPH__
#define ALONE_GRAPH__
#include "alone/labeled_edge.hh"
#include "search/rule.hh"
#include "search/types.hh"
#include "search/vertex.hh"
#include "util/exception.hh"
#include <boost/noncopyable.hpp>
#include <boost/pool/object_pool.hpp>
#include <boost/scoped_array.hpp>
namespace alone {
template <class T> class FixedAllocator : boost::noncopyable {
public:
FixedAllocator() : current_(NULL), end_(NULL) {}
void Init(std::size_t count) {
assert(!current_);
array_.reset(new T[count]);
current_ = array_.get();
end_ = current_ + count;
}
T &operator[](std::size_t idx) {
return array_.get()[idx];
}
T *New() {
T *ret = current_++;
UTIL_THROW_IF(ret >= end_, util::Exception, "Allocating past end");
return ret;
}
std::size_t Size() const {
return end_ - array_.get();
}
private:
boost::scoped_array<T> array_;
T *current_, *end_;
};
class Graph : boost::noncopyable {
public:
typedef LabeledEdge Edge;
typedef search::Vertex Vertex;
Graph() {}
void SetCounts(std::size_t vertices, std::size_t edges) {
vertices_.Init(vertices);
edges_.Init(edges);
}
Vertex *NewVertex() {
return vertices_.New();
}
std::size_t VertexSize() const { return vertices_.Size(); }
Vertex &MutableVertex(std::size_t index) {
return vertices_[index];
}
Edge *NewEdge() {
return edges_.New();
}
std::size_t EdgeSize() const { return edges_.Size(); }
void SetRoot(Vertex *root) { root_ = root; }
Vertex &Root() { return *root_; }
private:
FixedAllocator<Vertex> vertices_;
FixedAllocator<Edge> edges_;
Vertex *root_;
};
} // namespace alone
#endif // ALONE_GRAPH__
|
