package tree

import (
    "fmt"
    "sort"
)

const TestVersion = 2

type Record struct {
    ID     int
    Parent int
}

type storage []Record

type Node struct {
    ID       int
    Children []*Node
}

//Build function
func Build(records []Record) (*Node, error) {
    if len(records) <= 0 {
        return nil, nil
    }
    sort.Sort(storage(records))
    nodes := make([]*Node, len(records))
    for r, rec := range records {
        nodes[r] = &Node{ID: rec.ID}
        if r == 0 && (rec.ID != 0 || rec.Parent != 0) {
            return nil, fmt.Errorf("oops, smt went wrong %s", rec.String())
        } else if r == 0 {
            continue
        } else if r != rec.ID || rec.ID <= rec.Parent {
            return nil, fmt.Errorf("ooops smt went wrong: %s", rec.String())
        }

        if parent := nodes[rec.Parent]; parent != nil {
            parent.Children = append(parent.Children, nodes[r])
        }
    }

    return nodes[0], nil
}

func (r *Record) String() string {
    return fmt.Sprintf("(%d,%d)", r.ID, r.Parent)
}

func (elem storage) Len() int           { return len(elem) }
func (elem storage) Swap(j, k int)      { elem[j], elem[k] = elem[k], elem[j] }
func (elem storage) Less(j, k int) bool { return elem[j].ID < elem[k].ID }