func (self *AvlNode) Remove(key types.Hashable) (_ *AvlNode, value interface{}, err error) {
	if self == nil {
		return nil, nil, errors.NotFound(key)
	}

	if self.key.Equals(key) {
		if self.left != nil && self.right != nil {
			if self.left.Size() < self.right.Size() {
				lmd := self.right.lmd()
				lmd.left = self.left
				return self.right, self.value, nil
			} else {
				rmd := self.left.rmd()
				rmd.right = self.right
				return self.left, self.value, nil
			}
		} else if self.left == nil {
			return self.right, self.value, nil
		} else if self.right == nil {
			return self.left, self.value, nil
		} else {
			return nil, self.value, nil
		}
	}
	if key.Less(self.key) {
		self.left, value, err = self.left.Remove(key)
	} else {
		self.right, value, err = self.right.Remove(key)
	}
	if err != nil {
		return self.balance(), value, err
	}
	return self, value, err
}

/* a pure leaf split has two cases:
 *  1) the inserted key is less than the current pure block.
 *     - a new block should be created before the current block
 *     - the key should be put in it
 *  2) the inserted key is greater than or equal to the pure block.
 *     - the end of run of pure blocks should be found
 *     - if the key is equal to pure block and the last block is not full insert
 *       the new kv
 *     - else split by making a new block after the last block in the run
 *       and putting the new key there.
 *     - always return the current block as "a" and the new block as "b"
 */
func (self *BpNode) pure_leaf_split(key types.Hashable, value interface{}) (a, b *BpNode, err error) {
	if self.Internal() || !self.Pure() {
		return nil, nil, errors.BpTreeError("Expected a pure leaf node")
	}
	if key.Less(self.keys[0]) {
		a = NewLeaf(self.NodeSize(), self.no_dup)
		b = self
		if err := a.put_kv(key, value); err != nil {
			return nil, nil, err
		}
		insert_linked_list_node(a, b.prev, b)
		return a, b, nil
	} else {
		a = self
		e := self.find_end_of_pure_run()
		if e.keys[0].Equals(key) && !e.Full() {
			if err := e.put_kv(key, value); err != nil {
				return nil, nil, err
			}
			return a, nil, nil
		} else {
			b = NewLeaf(self.NodeSize(), self.no_dup)
			if err := b.put_kv(key, value); err != nil {
				return nil, nil, err
			}
			insert_linked_list_node(b, e, e.next)
			if e.keys[0].Equals(key) {
				return a, nil, nil
			}
			return a, b, nil
		}
	}
}

func (self *ImmutableAvlNode) Put(key types.Hashable, value interface{}) (_ *ImmutableAvlNode, updated bool) {
	if self == nil {
		return &ImmutableAvlNode{key: key, value: value, height: 1}, false
	}

	self = self.Copy()

	if self.key.Equals(key) {
		self.value = value
		return self, true
	}

	if key.Less(self.key) {
		self.left, updated = self.left.Put(key, value)
	} else {
		self.right, updated = self.right.Put(key, value)
	}
	self.height = max(self.left.Height(), self.right.Height()) + 1

	if !updated {
		self.height += 1
		return self.balance(), updated
	}
	return self, updated
}

func (self *AvlNode) Get(key types.Hashable) (value interface{}, err error) {
	if self == nil {
		return nil, errors.NotFound(key)
	}
	if self.key.Equals(key) {
		return self.value, nil
	} else if key.Less(self.key) {
		return self.left.Get(key)
	} else {
		return self.right.Get(key)
	}
}

func (self *AvlNode) Has(key types.Hashable) (has bool) {
	if self == nil {
		return false
	}
	if self.key.Equals(key) {
		return true
	} else if key.Less(self.key) {
		return self.left.Has(key)
	} else {
		return self.right.Has(key)
	}
}

func (self *BpNode) forward(from, to types.Hashable) (li loc_iterator) {
	j, l := self.get_start(from)
	end := false
	j--
	li = func() (i int, leaf *BpNode, next loc_iterator) {
		j, l, end = next_location(j, l)
		if end || to.Less(l.keys[j]) {
			return -1, nil, nil
		}
		return j, l, li
	}
	return li
}

func (self *BpTree) Range(from, to types.Hashable) (kvi types.KVIterator) {
	var li loc_iterator
	if !to.Less(from) {
		li = self.root.forward(from, to)
	} else {
		li = self.root.backward(from, to)
	}
	kvi = func() (key types.Hashable, value interface{}, next types.KVIterator) {
		var i int
		var leaf *BpNode
		i, leaf, li = li()
		if li == nil {
			return nil, nil, nil
		}
		return leaf.keys[i], leaf.values[i], kvi
	}
	return kvi
}

/* On split
 * - first assert that the key to be inserted is not already in the block.
 * - Make a new block
 * - balance the two blocks.
 * - insert the new key/pointer combo into the correct block
 */
func (self *BpNode) internal_split(key types.Hashable, ptr *BpNode) (a, b *BpNode, err error) {
	if !self.Internal() {
		return nil, nil, errors.BpTreeError("Expected a internal node")
	}
	if self.has(key) {
		return nil, nil, errors.BpTreeError("Tried to split an internal block on duplicate key")
	}
	a = self
	b = NewInternal(self.NodeSize())
	balance_nodes(a, b)
	if key.Less(b.keys[0]) {
		if err := a.put_kp(key, ptr); err != nil {
			return nil, nil, err
		}
	} else {
		if err := b.put_kp(key, ptr); err != nil {
			return nil, nil, err
		}
	}
	return a, b, nil
}

func (s *Sorted) Find(item types.Hashable) (int, bool, error) {
	var l int = 0
	var r int = s.Size() - 1
	var m int
	for l <= r {
		m = ((r - l) >> 1) + l
		im, err := s.list.Get(m)
		if err != nil {
			return -1, false, err
		}
		if item.Less(im) {
			r = m - 1
		} else if item.Equals(im) {
			for j := m; j > 0; j-- {
				ij_1, err := s.list.Get(j - 1)
				if err != nil {
					return -1, false, err
				}
				if !item.Equals(ij_1) {
					return j, true, nil
				}
			}
			return 0, true, nil
		} else {
			l = m + 1
		}
	}
	return l, false, nil
}

/* on leaf split if the block is pure then it will defer to pure_leaf_split
 * else
 *    - a new block will be made and inserted after this one
 *    - the two blocks will be balanced with balanced_nodes
 *    - if the key is less than b.keys[0] it will go in a else b
 */
func (self *BpNode) leaf_split(key types.Hashable, value interface{}) (a, b *BpNode, err error) {
	if self.Internal() {
		return nil, nil, errors.BpTreeError("Expected a leaf node")
	}
	if self.Pure() {
		return self.pure_leaf_split(key, value)
	}
	a = self
	b = NewLeaf(self.NodeSize(), self.no_dup)
	insert_linked_list_node(b, a, a.next)
	balance_nodes(a, b)
	if key.Less(b.keys[0]) {
		if err := a.put_kv(key, value); err != nil {
			return nil, nil, err
		}
	} else {
		if err := b.put_kv(key, value); err != nil {
			return nil, nil, err
		}
	}
	return a, b, nil
}

func (self *ImmutableAvlNode) Remove(key types.Hashable) (_ *ImmutableAvlNode, value interface{}, err error) {
	if self == nil {
		return nil, nil, errors.NotFound(key)
	}

	if self.key.Equals(key) {
		if self.left != nil && self.right != nil {
			var new_root *ImmutableAvlNode
			if self.left.Size() < self.right.Size() {
				self, new_root = self.pop_node(self.right.lmd())
			} else {
				self, new_root = self.pop_node(self.left.rmd())
			}
			new_root.left = self.left
			new_root.right = self.right
			return new_root, self.value, nil
		} else if self.left == nil {
			return self.right, self.value, nil
		} else if self.right == nil {
			return self.left, self.value, nil
		} else {
			return nil, self.value, nil
		}
	}

	self = self.Copy()

	if key.Less(self.key) {
		self.left, value, err = self.left.Remove(key)
	} else {
		self.right, value, err = self.right.Remove(key)
	}
	self.height = max(self.left.Height(), self.right.Height()) + 1
	if err != nil {
		return self.balance(), value, err
	}
	return self, value, err
}

func (self *BpNode) find(key types.Hashable) (int, bool) {
	var l int = 0
	var r int = len(self.keys) - 1
	var m int
	for l <= r {
		m = ((r - l) >> 1) + l
		if key.Less(self.keys[m]) {
			r = m - 1
		} else if key.Equals(self.keys[m]) {
			for j := m; j >= 0; j-- {
				if j == 0 || !key.Equals(self.keys[j-1]) {
					return j, true
				}
			}
		} else {
			l = m + 1
		}
	}
	return l, false
}