package bst

import (
	"fmt"
	"reflect"
)

type Node struct {
	e     interface{}
	left  *Node
	right *Node
}

type Bst struct {
	root *Node
	size int64
}

func New() *Bst {
	return new(Bst)
}

func (b *Bst) GetSize() int64 {
	return b.size
}

func (b *Bst) IsEmpty() bool {
	return b.size == 0
}

func (b *Bst) Add(e interface{}) {
	b.root = b.add(b.root, e)
	// fmt.Println(b.size)
}

// func (b *Bst) add(e interface{}, root *Node) *Node {
// 	if root == nil {
// 		b.size++
// 		return &Node{e: e}
// 	}

// 	if Compare(e, root.e) > 0 {
// 		root.left = b.add(e, root.left)
// 	} else if Compare(e, root.e) < 0 {
// 		root.right = b.add(e, root.right)
// 	}
// 	return root
// }

func (b *Bst) add(n *Node, e interface{}) *Node {
	if n == nil {
		b.size++
		return &Node{e: e}
	}

	// 递归调用
	if Compare(e, n.e) < 0 {
		n.left = b.add(n.left, e)
	} else if Compare(e, n.e) > 0 {
		n.right = b.add(n.right, e)
	}
	return n
}

func (b *Bst) GetList() {
	// fmt.Println(b.root)
	b.getList(b.root)
}

func (b *Bst) getList(root *Node) {
	if root == nil {
		return
	}
	b.getList(root.left)
	fmt.Println(root.e)
	b.getList(root.right)
}

func (b *Bst) Contains(e interface{}) bool {

	return b.contains(b.root, e)
}

func (b *Bst) contains(root *Node, e interface{}) bool {
	if root == nil {
		return false
	}

	if Compare(root.e, e) > 0 {
		return b.contains(root.left, e)
	} else if Compare(root.e, e) < 0 {
		return b.contains(root.right, e)
	} else {
		return true
	}
}

func (b *Bst) Remove(e interface{}) {
	b.root = b.remove(b.root, e)
}

func (b *Bst) remove(root *Node, e interface{}) *Node {
	if root == nil {
		return nil
	}

	if Compare(root.e, e) > 0 {
		root.left = b.remove(root.left, e)
	} else if Compare(root.e, e) < 0 {
		root.right = b.remove(root.right, e)
	} else {
		if root.left != nil && root.right == nil {
			b.size--
			return root.left

		} else if root.left == nil && root.right != nil {
			b.size--
			return root.right
		} else if root.left == nil && root.right == nil {
			return nil
		} else {
			ret := root.right
			for ret.left != nil {
				ret = ret.left
			}
			ret.left = root.left
			ret.right = root.right
			b.size--
		}
	}
	return root
}

func (b *Bst) Minimum() interface{} {
	if b.size == 0 {
		panic("BST is empty!")
	}
	return b.minimum(b.root).e
}

func (b *Bst) minimum(n *Node) *Node {
	if n.left == nil {
		return n
	}
	return b.minimum(n.left)
}

func (b *Bst) Maxmum() interface{} {
	if b.size == 0 {
		panic("BST is empty!")
	}
	return b.maximum(b.root).e
}

func (b *Bst) maximum(n *Node) *Node {
	if n.right == nil {
		return n
	}
	return b.maximum(n.right)
}

// func (b *Bst) Maximum() interface{} {
// 	if b.size == 0 {
// 		panic("BST is empty!")
// 	}
// 	return maximum(b.root).e
// }

// // 返回以 Node 为根的二分搜索树的最大值所在的节点
// func maximum(n *Node) *Node {
// 	if n.right == nil {
// 		return n
// 	}
// 	return maximum(n.right)
// }

func Compare(a interface{}, b interface{}) int {
	aType := reflect.TypeOf(a).String()
	bType := reflect.TypeOf(b).String()

	if aType != bType {
		panic("cannot compare different type params")
	}

	switch a.(type) {
	case int:
		if a.(int) > b.(int) {
			return 1
		} else if a.(int) < b.(int) {
			return -1
		} else {
			return 0
		}
	case string:
		if a.(string) > b.(string) {
			return 1
		} else if a.(string) < b.(string) {
			return -1
		} else {
			return 0
		}
	case float64:
		if a.(float64) > b.(float64) {
			return 1
		} else if a.(float64) < b.(float64) {
			return -1
		} else {
			return 0
		}
	default:
		panic("unsupported type params")
	}

}