func (t *bTree) minItems() int {
	return t.degree - 1
}
minItems returns the min number of items to allow per node (ignored for the
root node).
package btree
import (
	"fmt"
	"github.com/ahrtr/gocontainer/collection"
	"github.com/ahrtr/gocontainer/utils"
	"io"
	"sort"
	"strings"
	"sync"
)
type Interface interface {
	collection.Interface
	WithComparator(c utils.Comparator) Interface
	Clone() Interface
	ReplaceOrInsert(item interface{}) interface{}
	Delete(item interface{}) interface{}
	DeleteMin() interface{}
	DeleteMax() interface{}
	AscendRange(greaterOrEqual, lessThan interface{}, iterator ItemIterator)
	AscendLessThan(pivot interface{}, iterator ItemIterator)
	AscendGreaterOrEqual(pivot interface{}, iterator ItemIterator)
	Ascend(iterator ItemIterator)
	DescendRange(lessOrEqual, greaterThan interface{}, iterator ItemIterator)
	DescendLessOrEqual(pivot interface{}, iterator ItemIterator)
	DescendGreaterThan(pivot interface{}, iterator ItemIterator)
	Descend(iterator ItemIterator)
	Get(key interface{}) interface{}
	Min() interface{}
	Max() interface{}
	Has(key interface{}) bool
}
const (
	DefaultFreeListSize = 32
)
var (
	nilItems    = make(items, 16)
	nilChildren = make(children, 16)
)
type FreeList struct {
	mu       sync.Mutex
	freelist []*node
}
func NewFreeList(size int) *FreeList {
	return &FreeList{freelist: make([]*node, 0, size)}
}
func (f *FreeList) newNode() (n *node) {
	f.mu.Lock()
	index := len(f.freelist) - 1
	if index < 0 {
		f.mu.Unlock()
		return new(node)
	}
	n = f.freelist[index]
	f.freelist[index] = nil
	f.freelist = f.freelist[:index]
	f.mu.Unlock()
	return
}
func (f *FreeList) freeNode(n *node) (out bool) {
	f.mu.Lock()
	if len(f.freelist) < cap(f.freelist) {
		f.freelist = append(f.freelist, n)
		out = true
	}
	f.mu.Unlock()
	return
}
type ItemIterator func(i interface{}) bool
func New(degree int) Interface {
	return NewWithFreeList(degree, NewFreeList(DefaultFreeListSize))
}
func NewWithFreeList(degree int, f *FreeList) Interface {
	if degree <= 1 {
		panic("bad degree")
	}
	return &bTree{
		degree: degree,
		cow:    &copyOnWriteContext{freelist: f},
	}
}
func (t *bTree) WithComparator(c utils.Comparator) Interface {
	t.cmp = c
	return t
}
type items []interface{}
func (s *items) insertAt(index int, item interface{}) {
	*s = append(*s, nil)
	if index < len(*s) {
		copy((*s)[index+1:], (*s)[index:])
	}
	(*s)[index] = item
}
func (s *items) removeAt(index int) interface{} {
	item := (*s)[index]
	copy((*s)[index:], (*s)[index+1:])
	(*s)[len(*s)-1] = nil
	*s = (*s)[:len(*s)-1]
	return item
}
func (s *items) pop() (out interface{}) {
	index := len(*s) - 1
	out = (*s)[index]
	(*s)[index] = nil
	*s = (*s)[:index]
	return
}
func (s *items) truncate(index int) {
	var toClear items
	*s, toClear = (*s)[:index], (*s)[index:]
	for len(toClear) > 0 {
		toClear = toClear[copy(toClear, nilItems):]
	}
}
func (s items) find(item interface{}, cmp utils.Comparator) (index int, found bool) {
	i := sort.Search(len(s), func(i int) bool {
		return lessThan(item, s[i], cmp)
	})
	if i > 0 && !lessThan(s[i-1], item, cmp) {
		return i - 1, true
	}
	return i, false
}
type children []*node
func (s *children) insertAt(index int, n *node) {
	*s = append(*s, nil)
	if index < len(*s) {
		copy((*s)[index+1:], (*s)[index:])
	}
	(*s)[index] = n
}
func (s *children) removeAt(index int) *node {
	n := (*s)[index]
	copy((*s)[index:], (*s)[index+1:])
	(*s)[len(*s)-1] = nil
	*s = (*s)[:len(*s)-1]
	return n
}
func (s *children) pop() (out *node) {
	index := len(*s) - 1
	out = (*s)[index]
	(*s)[index] = nil
	*s = (*s)[:index]
	return
}
func (s *children) truncate(index int) {
	var toClear children
	*s, toClear = (*s)[:index], (*s)[index:]
	for len(toClear) > 0 {
		toClear = toClear[copy(toClear, nilChildren):]
	}
}
type node struct {
	items    items
	children children
	cow      *copyOnWriteContext
}
func (n *node) mutableFor(cow *copyOnWriteContext) *node {
	if n.cow == cow {
		return n
	}
	out := cow.newNode()
	if cap(out.items) >= len(n.items) {
		out.items = out.items[:len(n.items)]
	} else {
		out.items = make(items, len(n.items), cap(n.items))
	}
	copy(out.items, n.items)
	if cap(out.children) >= len(n.children) {
		out.children = out.children[:len(n.children)]
	} else {
		out.children = make(children, len(n.children), cap(n.children))
	}
	copy(out.children, n.children)
	return out
}
func (n *node) mutableChild(i int) *node {
	c := n.children[i].mutableFor(n.cow)
	n.children[i] = c
	return c
}
func (n *node) split(i int) (interface{}, *node) {
	item := n.items[i]
	next := n.cow.newNode()
	next.items = append(next.items, n.items[i+1:]...)
	n.items.truncate(i)
	if len(n.children) > 0 {
		next.children = append(next.children, n.children[i+1:]...)
		n.children.truncate(i + 1)
	}
	return item, next
}
func (n *node) maybeSplitChild(i, maxItems int) bool {
	if len(n.children[i].items) < maxItems {
		return false
	}
	first := n.mutableChild(i)
	item, second := first.split(maxItems / 2)
	n.items.insertAt(i, item)
	n.children.insertAt(i+1, second)
	return true
}
func (n *node) insert(item interface{}, maxItems int, cmp utils.Comparator) interface{} {
	i, found := n.items.find(item, cmp)
	if found {
		out := n.items[i]
		n.items[i] = item
		return out
	}
	if len(n.children) == 0 {
		n.items.insertAt(i, item)
		return nil
	}
	if n.maybeSplitChild(i, maxItems) {
		inTree := n.items[i]
		switch {
		case lessThan(item, inTree, cmp):
		case lessThan(inTree, item, cmp):
			i++  
		default:
			out := n.items[i]
			n.items[i] = item
			return out
		}
	}
	return n.mutableChild(i).insert(item, maxItems, cmp)
}
func (n *node) get(key interface{}, cmp utils.Comparator) interface{} {
	i, found := n.items.find(key, cmp)
	if found {
		return n.items[i]
	} else if len(n.children) > 0 {
		return n.children[i].get(key, cmp)
	}
	return nil
}
func min(n *node) interface{} {
	if n == nil {
		return nil
	}
	for len(n.children) > 0 {
		n = n.children[0]
	}
	if len(n.items) == 0 {
		return nil
	}
	return n.items[0]
}
func max(n *node) interface{} {
	if n == nil {
		return nil
	}
	for len(n.children) > 0 {
		n = n.children[len(n.children)-1]
	}
	if len(n.items) == 0 {
		return nil
	}
	return n.items[len(n.items)-1]
}
type toRemove int
const (
	removeItem toRemove = iota  
	removeMin                   
	removeMax                   
)
func (n *node) remove(item interface{}, minItems int, typ toRemove, cmp utils.Comparator) interface{} {
	var i int
	var found bool
	switch typ {
	case removeMax:
		if len(n.children) == 0 {
			return n.items.pop()
		}
		i = len(n.items)
	case removeMin:
		if len(n.children) == 0 {
			return n.items.removeAt(0)
		}
		i = 0
	case removeItem:
		i, found = n.items.find(item, cmp)
		if len(n.children) == 0 {
			if found {
				return n.items.removeAt(i)
			}
			return nil
		}
	default:
		panic("invalid type")
	}
	if len(n.children[i].items) <= minItems {
		return n.growChildAndRemove(i, item, minItems, typ, cmp)
	}
	child := n.mutableChild(i)
	if found {
		out := n.items[i]
		n.items[i] = child.remove(nil, minItems, removeMax, cmp)
		return out
	}
	return child.remove(item, minItems, typ, cmp)
}
func (n *node) growChildAndRemove(i int, item interface{}, minItems int, typ toRemove, cmp utils.Comparator) interface{} {
	if i > 0 && len(n.children[i-1].items) > minItems {
		child := n.mutableChild(i)
		stealFrom := n.mutableChild(i - 1)
		stolenItem := stealFrom.items.pop()
		child.items.insertAt(0, n.items[i-1])
		n.items[i-1] = stolenItem
		if len(stealFrom.children) > 0 {
			child.children.insertAt(0, stealFrom.children.pop())
		}
	} else if i < len(n.items) && len(n.children[i+1].items) > minItems {
		child := n.mutableChild(i)
		stealFrom := n.mutableChild(i + 1)
		stolenItem := stealFrom.items.removeAt(0)
		child.items = append(child.items, n.items[i])
		n.items[i] = stolenItem
		if len(stealFrom.children) > 0 {
			child.children = append(child.children, stealFrom.children.removeAt(0))
		}
	} else {
		if i >= len(n.items) {
			i--
		}
		child := n.mutableChild(i)
		mergeItem := n.items.removeAt(i)
		mergeChild := n.children.removeAt(i + 1)
		child.items = append(child.items, mergeItem)
		child.items = append(child.items, mergeChild.items...)
		child.children = append(child.children, mergeChild.children...)
		n.cow.freeNode(mergeChild)
	}
	return n.remove(item, minItems, typ, cmp)
}
type direction int
const (
	descend = direction(-1)
	ascend  = direction(+1)
)
func (n *node) iterate(dir direction, start, stop interface{}, includeStart bool, hit bool, iter ItemIterator, cmp utils.Comparator) (bool, bool) {
	var ok, found bool
	var index int
	switch dir {
	case ascend:
		if start != nil {
			index, _ = n.items.find(start, cmp)
		}
		for i := index; i < len(n.items); i++ {
			if len(n.children) > 0 {
				if hit, ok = n.children[i].iterate(dir, start, stop, includeStart, hit, iter, cmp); !ok {
					return hit, false
				}
			}
			if !includeStart && !hit && start != nil && !lessThan(start, n.items[i], cmp) {
				hit = true
				continue
			}
			hit = true
			if stop != nil && !lessThan(n.items[i], stop, cmp) {
				return hit, false
			}
			if !iter(n.items[i]) {
				return hit, false
			}
		}
		if len(n.children) > 0 {
			if hit, ok = n.children[len(n.children)-1].iterate(dir, start, stop, includeStart, hit, iter, cmp); !ok {
				return hit, false
			}
		}
	case descend:
		if start != nil {
			index, found = n.items.find(start, cmp)
			if !found {
				index = index - 1
			}
		} else {
			index = len(n.items) - 1
		}
		for i := index; i >= 0; i-- {
			if start != nil && !lessThan(n.items[i], start, cmp) {
				if !includeStart || hit || lessThan(start, n.items[i], cmp) {
					continue
				}
			}
			if len(n.children) > 0 {
				if hit, ok = n.children[i+1].iterate(dir, start, stop, includeStart, hit, iter, cmp); !ok {
					return hit, false
				}
			}
			if stop != nil && !lessThan(stop, n.items[i], cmp) {
				return hit, false  
			}
			hit = true
			if !iter(n.items[i]) {
				return hit, false
			}
		}
		if len(n.children) > 0 {
			if hit, ok = n.children[0].iterate(dir, start, stop, includeStart, hit, iter, cmp); !ok {
				return hit, false
			}
		}
	}
	return hit, true
}
func (n *node) print(w io.Writer, level int) {
	fmt.Fprintf(w, "%sNODE:%v\n", strings.Repeat("  ", level), n.items)
	for _, c := range n.children {
		c.print(w, level+1)
	}
}
type bTree struct {
	degree int
	length int
	root   *node
	cmp    utils.Comparator
	cow    *copyOnWriteContext
}
type copyOnWriteContext struct {
	freelist *FreeList
}
func (t *bTree) Clone() Interface {
	cow1, cow2 := *t.cow, *t.cow
	out := *t
	t.cow = &cow1
	out.cow = &cow2
	return &out
}
func (t *bTree) maxItems() int {
	return t.degree*2 - 1
}