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
|
const std = @import("std");
pub fn Node(T: type) type {
return struct {
const Self = @This();
parents: *std.ArrayList(*Self),
state: T,
pub fn init(state: T, allocator: std.mem.Allocator) !Self {
const parents = try allocator.create(std.ArrayList(*Self));
parents.* = std.ArrayList(*Self).init(allocator);
return Self {
.state = state,
.parents = parents,
};
}
pub fn clone(self: *Self, state: T) !Self {
return Self {
.parents = self.parents,
.state = state,
};
}
pub fn push(self: *Self, state: T) !Self {
const parents = try self.parents.allocator.create(std.ArrayList(*Self));
parents.* = std.ArrayList(*Self).init(self.parents.allocator);
var other = Self {
.parents = parents,
.state = state,
};
try other.parents.append(self);
return other;
}
pub fn format(
self: *const Self,
comptime fmt: []const u8,
options: std.fmt.FormatOptions,
writer: anytype,
) !void {
_ = fmt;
_ = options;
try writer.print("Node {{ {} }}", .{self.state});
}
};
}
pub fn Graph(T: type) type {
return struct {
const Self = @This();
allocator: std.mem.Allocator,
number_of_nodes: usize = 0,
number_of_clones: usize = 0,
pub fn init(allocator: std.mem.Allocator) Self {
return Self { .allocator = allocator };
}
pub fn push(self: *Self, node: *Node(T), state: T) !*Node(T) {
self.number_of_nodes += 1;
const child = try self.allocator.create(Node(T));
child.* = try node.push(state);
return child;
}
pub fn add_toplevel(self: *Self, state: T) !*Node(T) {
self.number_of_nodes += 1;
const node = try self.allocator.create(Node(T));
node.* = try Node(T).init(state, self.allocator);
return node;
}
pub fn clone(self: *Self, node: *Node(T), state: T) !*Node(T) {
self.number_of_nodes += 1;
self.number_of_clones += 1;
const sibling = try self.allocator.create(Node(T));
sibling.* = try node.clone(state);
return sibling;
}
};
}
|
