const std = @import("std");

pub fn Node(T: type) type {
	return struct {
		const Self = @This();

		parents: *std.ArrayList(*Self),
		state: T,
		is_toplevel: bool = false,

		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,
				.is_toplevel = self.is_toplevel,
			};
		}

		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);
			node.is_toplevel = true;
			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;
		}
	};
}