newtree

type Element struct {
	Val []byte
	Ptr int64
	Tmp interface{}
}

type Elements []Element

type IBase interface {
	Page() int
	PageAlloc() (int64, error)
	PageRead(id int64) (bufferex.Binary, error)
	PageWrite(id int64, b []byte) error
	PageFree(id int64) error
	HeadAlloc() (int64, error)
	HeadRead(id int64) (bufferex.Binary, error)
	HeadWrite(id int64, b []byte) error
	HeadFree(id int64) error
}

type ReadAlloc struct {
	P int
	F file.File
}

type Root struct {
	Ptr   int64
	Depth uint32
}

type Tree struct {
	IBase
	Ops TreeOps
}

type TreeOps interface {
	Consistent(p []byte, q interface{}) bool

	Union(P Elements) []byte

	Penalty(E1, E2 []byte) float64

	// The FirstSplit functions covers three cases.
	// Given FirstSplit(P,maxsize) -> A,B
	//
	// - Case 1: P is small enough to fit in maxsize.
	//           In this case, return P,nil
	// - Case 2: P is small enough so that A and B can fit in maxsize each.
	//           In this case, split P into A and B evenly.
	// - Case 3: P is so large, that eighter only A or B can fit in maxsize.
	//           In this case, return A,B so that A fits in maxsize.
	//
	// Given FirstSplit(P,maxsize) -> A,B   and .Sort() is implemented
	//       P is sorted and A and B are assumed to be sorted.
	FirstSplit(P Elements, maxsize int) (Elements, Elements)

	Sort(E Elements)
}

type WriteAlloc struct {
	ReadAlloc
	A *file.Allocator
}