// Package tree is a tree builder based on IDs.
package tree
import (
	"fmt"
	"sort"
)
// Record represents a message in the DB.
type Record struct {
	ID     int
	Parent int
}
// Node is one node of the tree.
type Node struct {
	ID       int
	Children []*Node
}
// Build returns the root Node of the tree build from records.
func Build(records []Record) (*Node, error) {
	if len(records) == 0 {
		return nil, nil
	}
	// sort records
	sort.Slice(records, func(i, j int) bool {
		if records[i].ID < records[j].ID {
			return true
		}
		return false
	})
	tree := make([]*Node, len(records))
	for i, rd := range records {
		// sanitize input
		if rd.ID == 0 && rd.Parent != 0 {
			return nil, fmt.Errorf("root node's parent must be 0")
		}
		if rd.ID != 0 && rd.Parent >= rd.ID {
			return nil, fmt.Errorf("parent id >= than id for non-root record")
		}
		if rd.ID >= len(records) {
			return nil, fmt.Errorf("missing records")
		}
		if i != rd.ID {
			return nil, fmt.Errorf("duplicate IDs in input")
		}
		tree[i] = &Node{ID: i}
		if i != 0 { // stack overflow otherwise!
			tree[rd.Parent].Children = append(tree[rd.Parent].Children, tree[i])
		}
	}
	return tree[0], nil
}