Contents

package tree

import (
	"fmt"
	"sort"
)

const testVersion = 4

type Record struct {
	ID, Parent int
}

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

type NodeSlice []*Node

func (n NodeSlice) Len() int           { return len(n) }
func (n NodeSlice) Swap(i, j int)      { n[i], n[j] = n[j], n[i] }
func (n NodeSlice) Less(i, j int) bool { return n[i].ID < n[j].ID }

func Build(records []Record) (*Node, error) {
	if len(records) == 0 {
		return nil, nil
	}

	// At the end of this function this will hold: nodes[i].ID == i
	nodes := make([]Node, len(records))
	parents := make([]*Node, len(records))
	seen := make([]bool, len(records))

	for _, record := range records {
		if record.ID >= len(records) {
			return nil, fmt.Errorf("Too high id %d", record.ID)
		}
		if record.ID != 0 && record.ID <= record.Parent {
			return nil, fmt.Errorf("Record %d has self or later parent %d", record.ID, record.Parent)
		}
		if seen[record.ID] {
			return nil, fmt.Errorf("Record with id %d occurs multiple times", record.ID)
		}
		seen[record.ID] = true
		if record.ID != 0 {
			parents[record.ID] = &nodes[record.Parent]
		} else if record.Parent != 0 {
			return nil, fmt.Errorf("Root node has non-0 parent %d", record.Parent)
		}
	}

	for i := 1; i < len(nodes); i++ {
		parents[i].Children = append(parents[i].Children, &nodes[i])
	}

	for i, node := range nodes {
		// The ID field isn't actually used in this function, so we can delay
		// setting it to an opportune moment.
		nodes[i].ID = i
		sort.Sort(NodeSlice(node.Children))
	}
	return &nodes[0], nil
}

Version data entries

274 entries across 274 versions & 1 rubygems

Version	Path
trackler-2.2.1.56	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.55	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.54	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.53	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.52	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.51	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.50	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.49	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.48	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.47	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.46	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.45	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.44	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.43	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.42	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.41	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.40	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.39	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.38	tracks/go/exercises/tree-building/example.go
trackler-2.2.1.37	tracks/go/exercises/tree-building/example.go