PeristentVector.go

package main

import (
  "fmt"
)

type Vector struct {
	cnt, shift int
	root       node
	tail       List
}

type IPersistentVector interface {
	Nth(i int) interface{}
}

type List []interface{}

type node struct {
	List
}

const (
	DEFAULT_NODE_SIZE int = 32 //Default number of nodes in the vector
)

// Returns a default size empty node.
func emptynode() node {
	return node{make(List, DEFAULT_NODE_SIZE)}
}

// Returns the counter.
func (v *Vector) Counter() int {
	return v.cnt
}

func newVector() *Vector {
	return &Vector{cnt: 0, shift: 5, root: emptynode(), tail: make(List, 1)}
}
func (v *Vector) tailoff() (result int) {
	if v.cnt < 32 {
		result = 0
	} else {
		result = ((v.cnt - 1) >> 5) << 5
	}
	return
}

func (v *Vector) arrayfor(i int) (list List) {
	if i >= 0 && i < v.cnt+1 {
		if i >= v.tailoff() {
			return v.tail
		}
		nodeitem := v.root
		for level := uint(v.shift); level > 0; level -= 5 {
			nodeitem = nodeitem.List[(i>>level)&0x01f].(node)
		}
		return nodeitem.List
	}
	panic("Argument out of range")
}
func (v *Vector) Nth(i int) interface{} {
	return v.arrayfor(i)[i&0x01f]
}

func (vect *Vector) Cons(element interface{}) *Vector {
	if (vect.cnt - vect.tailoff()) < 32 {
		newTail := make(List, len(vect.tail)+1)
		copy(newTail, vect.tail)
		newTail[len(vect.tail)] = element
		return &Vector{cnt: vect.cnt + 1, shift: vect.shift, root: vect.root, tail: newTail}
	}
	return newVector()
}
func main() {
	v := newVector()
	h := v.Cons(200)
	var g *Vector
	g = h.Cons(300).Cons(400)
	fmt.Println(h.Nth(1))
	fmt.Println(g.Nth(2))
}