# A BKTree implementation
#
# See `add` to insert a new word.
# See `search` to find matches from a `key`.
class BKTree

	# Default tolerance used to find matches
	#
	# Default is `2`.
	var default_tolerance = 2 is writable

	# Tree root
	private var root: nullable BKNode = null

	# Add a `key` in the tree
	fun add(key: String) do
		var root = self.root
		if root == null then
			self.root = new BKNode(key)
			return
		end

		var node = root
		var dist = node.key.levenshtein_distance(key)

		while node.has_key(dist) do
			if dist == 0 then return
			node = node[dist]
			dist = node.key.levenshtein_distance(key)
		end
		node[dist] = new BKNode(key)
	end

	# Search `key` with a distance of `tolerance` in `self`.
	#
	# If `tolerance` is null, the use `default_tolerance` instead.
	fun search(key: String, tolerance: nullable Int): Array[BKMatch] do
		var res = new Array[BKMatch]
		var root = self.root
		if root != null then
			if tolerance == null then tolerance = self.default_tolerance
			search_recursive(root, res, key, tolerance)
		end
		default_comparator.sort(res)
		return res
	end

	private fun search_recursive(node: BKNode, res: Array[BKMatch], key: String, tolerance: Int) do
		var dist = node.key.levenshtein_distance(key)
		var min = dist - tolerance
		var max = dist + tolerance

		if dist < tolerance then
			res.add new BKMatch(dist, node.key)
		end

		for odist, child in node do
			if odist < min or odist > max then continue
			search_recursive(child, res, key, tolerance)
		end
	end
end