// Deletes and returns a pointer to a Comparable value from
// the binary tree. If the value was not in the binary tree,
// this function returns nil. Running time is O(h) for a tree of
// height h.
351763
func (b *BinaryTree) Delete(value Comparable) *Comparable {
	// first find the node because of my decision to not allow access to nodes.
	node := b.search(value)
	if node == nil {
		return nil
	}
	if node.left == nil {
		b.transplant(node, node.right)
	} else if node.right == nil {
		b.transplant(node, node.left)
	} else {
		replacement := minimum(node.right)
		if replacement.parent != node {
			b.transplant(replacement, replacement.right) // sever ties
			replacement.right = node.right
		}
		replacement.right.parent = replacement
		replacement.left = node.left
		replacement.left.parent = replacement
		b.transplant(node, replacement)
	}
	return &node.value
}
838282
func (tr *RTree) Remove(min, max []float64, item interface{}) {
	bbox := &treeNode{min: min, max: max}
	tr.remove(bbox, item)
}
542776
func (v *Values) Remove(key Key) (value interface{}, ok bool) {
	v.lock.Lock()
	defer v.lock.Unlock()

	if key.IsEmpty() {
		if v.root.isSet() {
			result := v.root.value
			v.root = newNode()
			return result, true
		}
		return nil, false
	}

	parent, found, _ := v.root.findDescendent(nil, key, false, false)
	if found == nil {
		return nil, false
	}
	var result interface{}
	if found.isSet() {
		result = found.value
	} else {
		result = newValues(found)
	}
	if parent != nil {
		delete(parent.children, key[key.Len()-1])
	}
	return result, true
}
485190
func (pm *pointerMap) consider(v reflect.Value) {
	if v.Kind() == reflect.Invalid {
		return
	}
	// fmt.Printf("Considering [%s] %#v\n\r", v.Type().String(), v.Interface())
	if isPointerValue(v) && v.Pointer() != 0 { // pointer is 0 for unexported fields
		// fmt.Printf("Ptr is %d\n\r", v.Pointer())
		reused := pm.addPointerReturnTrueIfWasReused(v.Pointer())
		if reused {
			// No use descending inside this value, since it have been seen before and all its descendants
			// have been considered
			return
		}
	}

	// Now descend into any children of this value
	switch v.Kind() {
	case reflect.Slice, reflect.Array:
		numEntries := v.Len()
		for i := 0; i < numEntries; i++ {
			pm.consider(v.Index(i))
		}

	case reflect.Interface:
		pm.consider(v.Elem())

	case reflect.Ptr:
		pm.consider(v.Elem())

	case reflect.Map:
		keys := v.MapKeys()
		sort.Sort(mapKeySorter{
			keys:    keys,
			options: &Config,
		})
		for _, key := range keys {
			pm.consider(v.MapIndex(key))
		}

	case reflect.Struct:
		numFields := v.NumField()
		for i := 0; i < numFields; i++ {
			pm.consider(v.Field(i))
		}
	}
}
1001564
func (n *leafPageElement) value() []byte {
	buf := (*[maxAllocSize]byte)(unsafe.Pointer(n))
	return buf[n.pos+n.ksize : n.pos+n.ksize+n.vsize]
}
643752
func (obj *object) Compare(other Value) int {
	o1 := sortOrder(obj)
	o2 := sortOrder(other)
	if o1 < o2 {
		return -1
	} else if o2 < o1 {
		return 1
	}
	a := obj
	b := other.(*object)
	keysA := a.Keys()
	keysB := b.Keys()
	sort.Sort(termSlice(keysA))
	sort.Sort(termSlice(keysB))
	minLen := a.Len()
	if b.Len() < a.Len() {
		minLen = b.Len()
	}
	for i := 0; i < minLen; i++ {
		keysCmp := Compare(keysA[i], keysB[i])
		if keysCmp < 0 {
			return -1
		}
		if keysCmp > 0 {
			return 1
		}
		valA := a.Get(keysA[i])
		valB := b.Get(keysB[i])
		valCmp := Compare(valA, valB)
		if valCmp != 0 {
			return valCmp
		}
	}
	if a.Len() < b.Len() {
		return -1
	}
	if b.Len() < a.Len() {
		return 1
	}
	return 0
}
1115092
func (b *BinaryTree) Successor(target Comparable) *Comparable {
	current := b.search(target)
	if current == nil {
		return nil
	}
	if current.right != nil {
		return &minimum(current.right).value
	}
	if current == b.root { // if root has no right side, at max, no successor
		return nil
	}
	parent := current.parent
	for parent != nil && current == parent.right {
		current = parent
		parent = current.parent
	}
	return &current.value
}
465321
func (tree *MutableTree) remove(key []byte) (value []byte, orphans []*Node, removed bool) {
	if tree.root == nil {
		return nil, nil, false
	}
	newRootHash, newRoot, _, value, orphaned := tree.recursiveRemove(tree.root, key)
	if len(orphaned) == 0 {
		return nil, nil, false
	}

	if newRoot == nil && newRootHash != nil {
		tree.root = tree.ndb.GetNode(newRootHash)
	} else {
		tree.root = newRoot
	}
	return value, orphaned, true
}
661161
func (t *Tree) Clear(value interface{}) {
	t.mutex.Lock()
	defer t.mutex.Unlock()

	t.clear(value, t.root)
}
551375
func (ptree *ptree) Delete(keys ...common.Comparator) {
	ra := newRemoveAction(keys)
	ptree.checkAndRun(ra)
	ra.completer.Wait()
}
306540
func (t *Tree) Remove(ptr interface{}) interface{} {
	if ptr != nil && t.root != nil {
		d := &removeData{ptr, t.compare}
		var shorter bool
		return d.remove(&(t.root), &shorter)
	}

	return nil
}
699447
func (tree *tree) delete(iv Interval) {
	if tree.root == nil {
		return
	}

	tree.resetDummy()
	var (
		dummy                      = tree.dummy
		found, parent, grandParent *node
		last, otherDir, otherLast  int // keeping track of last direction
		id                         = iv.ID()
		dir                        = 1
		node                       = &dummy
		ivLow                      = iv.LowAtDimension(1)
	)

	node.children[1] = tree.root
	for node.children[dir] != nil {
		last = dir
		otherLast = takeOpposite(last)

		grandParent, parent, node = parent, node, node.children[dir]

		dir = compare(node.interval.LowAtDimension(1), ivLow, node.id, id)
		otherDir = takeOpposite(dir)

		if node.id == id {
			found = node
		}

		if !isRed(node) && !isRed(node.children[dir]) {
			if isRed(node.children[otherDir]) {
				parent.children[last] = rotate(node, dir)
				parent = parent.children[last]
			} else if !isRed(node.children[otherDir]) {
				t := parent.children[otherLast]

				if t != nil {
					if !isRed(t.children[otherLast]) && !isRed(t.children[last]) {
						parent.red = false
						node.red = true
						t.red = true
					} else {
						localDir := intFromBool(grandParent.children[1] == parent)

						if isRed(t.children[last]) {
							grandParent.children[localDir] = doubleRotate(
								parent, last,
							)
						} else if isRed(t.children[otherLast]) {
							grandParent.children[localDir] = rotate(
								parent, last,
							)
						}

						node.red = true
						grandParent.children[localDir].red = true
						grandParent.children[localDir].children[0].red = false
						grandParent.children[localDir].children[1].red = false
					}
				}
			}
		}
	}

	if found != nil {
		tree.number--
		found.interval, found.max, found.min, found.id = node.interval, node.max, node.min, node.id
		parentDir := intFromBool(parent.children[1] == node)
		childDir := intFromBool(node.children[0] == nil)

		parent.children[parentDir] = node.children[childDir]
	}

	tree.root = dummy.children[1]
	if tree.root != nil {
		tree.root.red = false
	}
}
945593
func ValueEqual(v1 interface{}, v2 interface{}) bool {
	v1RV := reflect.ValueOf(v1)
	switch v1RV.Kind() {
	case reflect.Func:
		// This is best effort to check if functions match, but it could be wrong
		v2RV := reflect.ValueOf(v2)
		if !v1RV.IsValid() || !v2RV.IsValid() {
			if v1RV.IsValid() != !v2RV.IsValid() {
				return false
			}
			return true
		} else if v1RV.Kind() != v2RV.Kind() {
			return false
		} else if v1RV.Type() != v2RV.Type() {
			return false
		} else if v1RV.Pointer() != v2RV.Pointer() {
			// From reflect: If v's Kind is Func, the returned pointer is an underlying code pointer, but not necessarily enough to identify a single function uniquely.
			return false
		}
		return true
	}
	switch value1 := v1.(type) {
	case error:
		switch value2 := v2.(type) {
		case error:
			return value1.Error() == value2.Error()
		}
	}

	return reflect.DeepEqual(v1, v2)
}
780033
func (t *redBlackTree) Delete(key keytype) bool {
	if t.root == nil {
		return false
	}

	var head = &redBlackNode{red: true} // fake red node to push down
	var node = head
	var parent *redBlackNode  //parent
	var gparent *redBlackNode //grandparent
	var found *redBlackNode

	var dir = true

	node.right = t.root

	for node.Child(dir) != nil {
		last := dir

		// update helpers
		gparent = parent
		parent = node
		node = node.Child(dir)

		cmp := node.key.Compare(key)

		dir = cmp < 0

		// save node if found
		if cmp == 0 {
			found = node
		}

		// pretend to push red node down
		if !isRed(node) && !isRed(node.Child(dir)) {
			if isRed(node.Child(!dir)) {
				sr := singleRotate(node, dir)
				parent.setChild(last, sr)
				parent = sr
			} else {
				sibling := parent.Child(!last)
				if sibling != nil {
					if !isRed(sibling.Child(!last)) && !isRed(sibling.Child(last)) {
						// flip colors
						parent.red = false
						sibling.red, node.red = true, true
					} else {
						dir2 := gparent.right == parent

						if isRed(sibling.Child(last)) {
							gparent.setChild(dir2, doubleRotate(parent, last))
						} else if isRed(sibling.Child(!last)) {
							gparent.setChild(dir2, singleRotate(parent, last))
						}

						gpc := gparent.Child(dir2)
						gpc.red = true
						node.red = true
						gpc.left.red, gpc.right.red = false, false
					}
				}
			}
		}
	}

	// get rid of node if we've found one
	if found != nil {
		found.key = node.key
		found.value = node.value
		parent.setChild(parent.right == node, node.Child(node.left == nil))
		t.size--
	}

	t.root = head.right
	if t.root != nil {
		t.root.red = false
	}

	return found != nil
}
1110067
func (f *Factory) recursiveDelete(n *node) {
	parent := n.parent
	if parent == nil {
		return
	}
	delete(parent.children, n.name)
	if len(parent.children) == 0 {
		f.recursiveDelete(parent)
	}
}
133899
func (b *BinaryTree) Insert(value Comparable) {
	newNode := new(node)
	newNode.value = value
	y := (*node)(nil)
	x := b.root
	for x != nil {
		y = x
		if value.CompareTo(x.value) == -1 { // less
			x = x.left
		} else {
			x = x.right
		}
	}
	newNode.parent = y
	if newNode.parent == nil {
		b.root = newNode
	} else if newNode.value.CompareTo(y.value) == -1 {
		y.left = newNode
	} else {
		y.right = newNode
	}
	b.size++
}
1198979
func CallbackGitTreeWalk(_root *C.char, _entry unsafe.Pointer, ptr unsafe.Pointer) C.int {
	root := C.GoString(_root)
	entry := (*C.git_tree_entry)(_entry)

	if callback, ok := pointerHandles.Get(ptr).(TreeWalkCallback); ok {
		return C.int(callback(root, newTreeEntry(entry)))
	} else {
		panic("invalid treewalk callback")
	}
}