Tree DSL

tree.go

package tree

import "errors"

const (
	InstrBranch = Instruction('B')
	InstrRemove = Instruction('R')
	InstrLeaf   = Instruction('L')
)

type Node struct {
	Value      interface{}
	id         uint64
	leftChild  *Node
	rightChild *Node

	// pointer to this node's pointer in its parent, i.e. either &parent.leftChild or &parent.rightChild
	childSlot **Node
}

func (n *Node) childIDs() (left, right uint64) {
	if n == nil {
		panic(errors.New("childIDs called on a nil Node"))
	}

	if n.id == 0 {
		return 1, 2
	}
	return n.id * 2, n.id*2 + 1
}

func (n *Node) Remove() {
	if n == nil {
		return
	}

	n.leftChild.Remove()
	n.rightChild.Remove()

	// setting whatever n.childSlot points to to nil we remove this Node from either one of the parent's child node fields
	if (n.childSlot) != nil {
		*n.childSlot = nil
	}
}

func (n *Node) Branch() {
	leftID, rightID := n.childIDs()
	n.leftChild, n.rightChild = &Node{id: leftID, childSlot: &n.leftChild}, &Node{id: rightID, childSlot: &n.rightChild}
}

// Consume reads Instructions and constructs a graph using them. It'll return any instructions it couldn't execute
func (n *Node) Consume(is ...Instruction) Instructions {
	if len(is) == 0 {
		return is
	}
	insts := Instructions(is)
	head := insts.Head()
	tail := insts.Tail()
	_ = tail
	switch head {
	case InstrRemove:
		n.Remove()
	case InstrBranch:
		n.Branch()
		tail = n.leftChild.Consume(tail...)
		tail = n.rightChild.Consume(tail...)
	case InstrLeaf:
		// NOTE: No-op but here to have "introns" in the genome
	}

	return tail
}

type Instruction uint8

func (i Instruction) String() string {
	return string(i)
}

type Instructions []Instruction

func (is Instructions) Head() Instruction {
	if len(is) == 0 {
		panic(errors.New("can't get Head from empty slice"))
	}
	return is[0]
}

func (is Instructions) Tail() Instructions {
	if len(is) == 0 {
		return is
	}
	return is[1:]
}