package quadtree

// MakeFromArray construit un quadtree représentant un terrain
// étant donné un tableau représentant ce terrain.
// Note : marche pour les terrains rectangulaires, avec simplification
func MakeFromArray(floorContent [][]int) (q Quadtree) {

	// Cas de bases //
	if len(floorContent) == 0 {
		return Quadtree{width: 0, height: 0, root: &node{topLeftX: 0, topLeftY: 0, width: 0, height: 0, isLeaf: true, content: -2}}
	}
	if len(floorContent[0]) == 0 {
		return Quadtree{width: 0, height: 0, root: &node{topLeftX: 0, topLeftY: 0, width: 0, height: len(floorContent), isLeaf: true, content: -2}}
	}
	if len(floorContent) == 1 && len(floorContent[0]) == 1 {
		return Quadtree{width: 1, height: 1, root: &node{topLeftX: 0, topLeftY: 0, width: 1, height: 1, isLeaf: true, content: floorContent[0][0]}}
	}

	// Initialisation du quadtree q //
	q = Quadtree{width: len(floorContent[0]), height: len(floorContent), root: nil}

	// Division de floorContent en 4 parties //
	topLeft := [][]int{}
	bottomLeft := [][]int{}
	topRight := [][]int{}
	bottomRight := [][]int{}
	middle_height := q.height / 2
	middle_width := q.width / 2

	for i := 0; i < middle_height; i++ {
		topLeft = append(topLeft, floorContent[i][:q.width/2])
		topRight = append(topRight, floorContent[i][q.width/2:])
	}
	for i := middle_height; i < len(floorContent); i++ {
		bottomLeft = append(bottomLeft, floorContent[i][:q.width/2])
		bottomRight = append(bottomRight, floorContent[i][q.width/2:])
	}

	// Création des 4 noeuds //
	topLeftN := MakeNode(topLeft, 0, 0)
	topRightN := MakeNode(topRight, 0, middle_width)
	bottomLeftN := MakeNode(bottomLeft, middle_height, 0)
	bottomRightN := MakeNode(bottomRight, middle_height, middle_width)

	// Vérifications des simplifications //
	if topLeftN.isLeaf && topRightN.isLeaf && bottomLeftN.isLeaf && bottomRightN.isLeaf && topLeftN.content == topRightN.content && topLeftN.content == bottomLeftN.content && topLeftN.content == bottomRightN.content {
		q.root = &node{topLeftX: 0, topLeftY: 0, width: len(floorContent[0]), height: len(floorContent), isLeaf: true, content: topLeftN.content}
		return Quadtree{width: len(floorContent[0]), height: len(floorContent), root: q.root}
	}

	// S'il n'y a pas de simplifications possibles //
	q.root = &node{topLeftX: 0, topLeftY: 0, width: len(floorContent[0]), height: len(floorContent),
		topLeftNode:     topLeftN,
		topRightNode:    topRightN,
		bottomLeftNode:  bottomLeftN,
		bottomRightNode: bottomRightN,
	}

	// Retour du quadtree complet //
	return Quadtree{width: len(floorContent[0]), height: len(floorContent), root: q.root}
}

func MakeNode(floorContent [][]int, Origine_y, Origine_x int) (n *node) {

	// Cas de bases //
	if len(floorContent) == 0 {
		return &node{topLeftX: Origine_x, topLeftY: Origine_y, width: 0, height: 0, isLeaf: true, content: -2}
	}
	if len(floorContent[0]) == 0 {
		return &node{topLeftX: Origine_x, topLeftY: Origine_y, width: 0, height: 0, isLeaf: true, content: -2}
	}
	if len(floorContent) == 1 && len(floorContent[0]) == 1 {
		return &node{topLeftX: Origine_x, topLeftY: Origine_y, width: 1, height: 1, isLeaf: true, content: floorContent[0][0]}
	}

	// Division de floorContent en 4 parties //
	topLeft := [][]int{}
	bottomLeft := [][]int{}
	topRight := [][]int{}
	bottomRight := [][]int{}
	middle_height := len(floorContent) / 2
	middle_width := len(floorContent[0]) / 2

	for i := 0; i < middle_height; i++ {
		topLeft = append(topLeft, floorContent[i][:len(floorContent[0])/2])
		topRight = append(topRight, floorContent[i][len(floorContent[0])/2:])
	}
	for i := middle_height; i < len(floorContent); i++ {
		bottomLeft = append(bottomLeft, floorContent[i][:len(floorContent[0])/2])
		bottomRight = append(bottomRight, floorContent[i][len(floorContent[0])/2:])
	}

	// Création des 4 sous-noeuds //
	topLeftN := MakeNode(topLeft, Origine_y, Origine_x)
	topRightN := MakeNode(topRight, Origine_y, Origine_x+middle_width)
	bottomLeftN := MakeNode(bottomLeft, Origine_y+middle_height, Origine_x)
	bottomRightN := MakeNode(bottomRight, Origine_y+middle_height, Origine_x+middle_width)

	// Vérifications des simplifications //
	if topLeftN.isLeaf && topRightN.isLeaf && bottomLeftN.isLeaf && bottomRightN.isLeaf && topLeftN.content == topRightN.content && topLeftN.content == bottomLeftN.content && topLeftN.content == bottomRightN.content {
		return &node{topLeftX: Origine_x, topLeftY: Origine_y, width: len(floorContent[0]), height: len(floorContent), isLeaf: true, content: topLeftN.content}
	}

	// S'il n'y a pas de simplification possibles //
	return &node{topLeftX: Origine_x, topLeftY: Origine_y, width: len(floorContent[0]), height: len(floorContent),
		topLeftNode:     topLeftN,
		topRightNode:    topRightN,
		bottomLeftNode:  bottomLeftN,
		bottomRightNode: bottomRightN,
	}
}
