# Abstract node structure used in `Tree` implementation
#
# Nodes are defined recursively each node (except the root one) pointing to a parent.
# Nodes can be used to store data with the `TreeNode::value` attribute.
#
# Formal parameters:
# * `K`: key type (a `Comparable` one so nodes can be sorted by their keys)
# * `E`: value type (to store your data)
abstract class TreeNode[K: Comparable, E]
	super Comparable

	# TreeNode type
	type N: TreeNode[K, E]

	# `key` for this node
	var key: K

	# `value` stored in the node
	var value: E

	# Direct parent of this node (`null` if the node is root)
	#
	# See `Tree::root`.
	var parent: nullable N = null is writable

	# Depth in tree (length of the path from `self` to `root`)
	fun depth: Int do
		var node = parent
		var i = 0
		while node != null do
			node = node.parent
			i += 1
		end
		return i
	end

	redef fun to_s do return "\{{value or else ""}\}"

	# Return dot representation of this node
	#
	# See `Tree::show_dot`.
	fun to_dot: String do
		var res = new FlatBuffer
		res.append "\"{self}\";\n"
		if parent != null then res.append "\"{parent.as(not null)}\" -> \"{self}\"[dir=back];\n"
		return res.to_s
	end

	redef type OTHER: N

	# Nodes equality is done on `value` equality
	#
	# Redefine this method to change the default behavior.
	redef fun ==(o) do
		if not o isa N then return false
		return self.value == o.value
	end

	# Nodes ordering is based on the `key`
	redef fun <(o) do return self.key < o.key
end