oops/rbtree.oops at compiler · tristanmcd130/oops · GitHub

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
export empty

trait RBTree
	def member(x)
		match self
			case E{} then false
			case T{color: _, left: a, value: y, right: b} then
				if x < y then
					a.member(x)
				elseif x == y then
					true
				else
					b.member(x)
				end
		end
	end
	def insert(x)
		def ins(t)
			match t
				case E{} then T{color: "R", left: E{}, value: x, right: E{}}
				case T{color: color, left: a, value: y, right: b} then
					if x < y then
						T{color: color, left: ins(a), value: y, right: b}.balance()
					elseif x == y then
						t
					else
						T{color: color, left: a, value: y, right: ins(b)}.balance()
					end
			end
		end
		def make_black(t)
			match t
				case T{left: a, value: y, right: b} then T{color: "B", left: a, value: y, right: b}
			end
		end
		make_black(ins(self))
	end
	def balance()
		match self
			case T{color: "B", left: T{color: "R", left: T{color: "R", left: a, value: x, right: b}, value: y, right: c}, value: z, right: d}
				or T{color: "B", left: T{color: "R", left: a, value: x, right: T{color: "R", left: b, value: y, right: c}}, value: z, right: d}
				or T{color: "B", left: a, value: x, right: T{color: "R", left: T{color: "R", left: b, value: y, right: c}, value: z, right: d}}
				or T{color: "B", left: a, value: x, right: T{color: "R", left: b, value: y, right: T{color: "R", left: c, value: z, right: d}}} then T{color: "R", left: T{color: "B", left: a, value: x, right: b}, value: y, right: T{color: "B", left: c, value: z, right: d}}
			case _ then self
		end
	end
	def to_string()
		match self
			case E{} then ""
			case T{color: color, left: a, value: y, right: b} then "{0}[{1}{0} {2} {3}{0}][0m".format([if color == "R" then "[91m" else "[90m" end, a, y, b])
		end
	end
end

struct E end
impl RBTree for E end

struct T
	color
	left
	value
	right
end
impl RBTree for T end

def empty()
	E{}
end

print(Range{start: 1, stop: 1000}.fold(fun(x, y) x.insert(y) end, empty()))