// Binary Search Tree example by @SleepyRoy

struct Empty {}

struct Node[T] {
	value T
	left  Tree[T]
	right Tree[T]
}

type Tree[T] = Empty | Node[T]

// return size(number of nodes) of BST
fn (tree Tree[T]) size[T]() int {
	return match tree {
		Empty { 0 }
		Node[T] { 1 + tree.left.size() + tree.right.size() }
	}
}

// insert a value to BST
fn (tree Tree[T]) insert[T](x T) Tree[T] {
	return match tree {
		Empty {
			Node[T]{x, tree, tree}
		}
		Node[T] {
			if x == tree.value {
				tree
			} else if x < tree.value {
				Node[T]{
					...tree
					left: tree.left.insert(x)
				}
			} else {
				Node[T]{
					...tree
					right: tree.right.insert(x)
				}
			}
		}
	}
}

// whether able to find a value in BST
fn (tree Tree[T]) search[T](x T) bool {
	return match tree {
		Empty {
			false
		}
		Node[T] {
			if x == tree.value {
				true
			} else if x < tree.value {
				tree.left.search(x)
			} else {
				tree.right.search(x)
			}
		}
	}
}

// find the minimal value of a BST
fn (tree Tree[T]) min[T]() T {
	return match tree {
		Empty {
			T(1e9)
		}
		Node[T] {
			if tree.value < tree.left.min() {
				tree.value
			} else {
				tree.left.min()
			}
		}
	}
}

// delete a value in BST (if nonexistent do nothing)
fn (tree Tree[T]) delete[T](x T) Tree[T] {
	return match tree {
		Empty {
			tree
		}
		Node[T] {
			if tree.left !is Empty && tree.right !is Empty {
				if x < tree.value {
					Node[T]{
						...tree
						left: tree.left.delete(x)
					}
				} else if x > tree.value {
					Node[T]{
						...tree
						right: tree.right.delete(x)
					}
				} else {
					Node[T]{
						...tree
						value: tree.right.min()
						right: tree.right.delete(tree.right.min())
					}
				}
			} else if tree.left !is Empty {
				if x == tree.value {
					tree.left
				} else {
					Node[T]{
						...tree
						left: tree.left.delete(x)
					}
				}
			} else {
				if x == tree.value {
					tree.right
				} else {
					Node[T]{
						...tree
						right: tree.right.delete(x)
					}
				}
			}
		}
	}
}

fn main() {
	mut tree := Tree[f64](Empty{})
	vals := [0.2, 0.0, 0.5, 0.3, 0.6, 0.8, 0.9, 1.0, 0.1, 0.4, 0.7]
	for i in vals {
		tree = tree.insert(i)
	}
	println('[1] after insertion tree size is ${tree.size()}') // 11
	del_vals := [-0.3, 0.0, 0.3, 0.6, 1.0, 1.5]
	for i in del_vals {
		tree = tree.delete(i)
	}
	print('[2] after deletion tree size is ${tree.size()}, ') // 7
	print('and these elements were deleted: ') // 0.0 0.3 0.6 1.0
	for i in vals {
		if !tree.search(i) {
			print('${i} ')
		}
	}
	println('')
}