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
}
get finds the given key in the subtree and returns it.
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)
}