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)
}
growChildAndRemove grows child 'i' to make sure it's possible to remove an
item from it while keeping it at minItems, then calls remove to actually
remove it.

Most documentation says we have to do two sets of special casing:
1) item is in this node
2) item is in child
In both cases, we need to handle the two subcases:
A) node has enough values that it can spare one
B) node doesn't have enough values
For the latter, we have to check:
a) left sibling has node to spare
b) right sibling has node to spare
c) we must merge
To simplify our code here, we handle cases #1 and #2 the same:
If a node doesn't have enough items, we make sure it does (using a,b,c).
We then simply redo our remove call, and the second time (regardless of
whether we're in case 1 or 2), we'll have enough items and can guarantee
that we hit case A.
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)
}