// predecessor will find the node equal to or immediately less
// than the provided key.
973266
func (xft *XFastTrie) predecessor(key uint64) *node {
	if xft.root == nil || xft.max == nil { // no successor if no nodes
		return nil
	}

	if key >= xft.max.entry.Key() {
		return xft.max
	}

	if key < xft.min.entry.Key() {
		return nil
	}

	n := xft.layers[xft.bits-1][key]
	if n != nil {
		return n
	}

	layer, n := binarySearchHashMaps(xft.layers, key)
	if n == nil && layer > 1 {
		return nil
	} else if n == nil {
		n = xft.root
	}

	if isInternal(n.children[0]) && isLeaf(n.children[1]) {
		return n.children[1].children[0]
	}
	return n.children[0]
}
616896
func (e *ItemElement) Prev() *ItemElement {
	if p := e.prev; e.list != nil && p != &e.list.root {
		return p
	}
	return nil
}
60632
func (r Root) FindPrevElementSibling() Root {
	prevSibling := r.Pointer.PrevSibling
	if prevSibling == nil {
		if debug {
			panic("No previous element sibling found")
		}
		return Root{nil, "", errors.New("no previous element sibling found")}
	}
	if prevSibling.Type == html.ElementNode {
		return Root{prevSibling, prevSibling.Data, nil}
	}
	p := Root{prevSibling, prevSibling.Data, nil}
	return p.FindPrevElementSibling()
}
626934
func (iter *Iterator) Prev() bool {
	if iter.isNew {
		return iter.Last()
	}

	if iter.node == nil {
		return false
	}

	// Reseek the previous key without allowing for an exact match if a
	// force seek was requested.  This results in the key smaller than the
	// previous one or an exhausted iterator if there is no such key.
	if seekKey := iter.seekKey; seekKey != nil {
		iter.seekKey = nil
		return iter.seek(seekKey, false, false)
	}

	// When there is no left node walk the parents until the parent's left
	// node is not equal to the previous child.  This will be the previous
	// node.
	for iter.node.left == nil {
		parent := iter.parents.Pop()
		for parent != nil && parent.left == iter.node {
			iter.node = parent
			parent = iter.parents.Pop()
		}
		iter.node = parent
		return iter.limitIterator()
	}

	// There is a left node, so the previous node is the right-most node
	// down the left sub-tree.
	iter.parents.Push(iter.node)
	iter.node = iter.node.left
	for node := iter.node.right; node != nil; node = node.right {
		iter.parents.Push(iter.node)
		iter.node = node
	}
	return iter.limitIterator()
}
900065
func (n *node) findDescendent(parent *node, key Key, canChange, hasChanged bool) (foundParent *node, found *node, changed bool) {
	//if there is no more key to look into, then return parent, n, and hasChanged.
	if key.IsEmpty() {
		return parent, n, hasChanged
	}
	//find the child at the next part in key, possibly creating or changing with canChange.
	child, changed := n.findChild(key[0], canChange)
	if child == nil {
		return parent, nil, changed
	}
	//recurse into children.
	return child.findDescendent(n, key[1:], canChange, changed || hasChanged)
}
1086675
func (xft *XFastTrie) walkUpNode(root, node, predecessor, successor *node) {
	n := node.parent
	for n != nil && n != root {
		if !isInternal(n.children[1]) && n.children[1] != successor && n.children[1] != node {
			n.children[1] = successor
		}
		if !isInternal(n.children[0]) && n.children[0] != predecessor && n.children[0] != node {
			n.children[0] = predecessor
		}
		n = n.parent
	}
}
885637
func (bldr *iisQueryBuilder) Ancestor(parentKey *datastore.Key) *iisQueryBuilder {
	bldr.q = bldr.q.Ancestor(parentKey)
	if bldr.plugin != nil {
		bldr.plugin.Ancestor(parentKey)
	}
	return bldr
}
245433
func (c *Cursor) First() (key []byte, value []byte) {
	_assert(c.bucket.tx.db != nil, "tx closed")
	c.stack = c.stack[:0]
	p, n := c.bucket.pageNode(c.bucket.root)
	c.stack = append(c.stack, elemRef{page: p, node: n, index: 0})
	c.first()

	// If we land on an empty page then move to the next value.
	// https://github.com/boltdb/bolt/issues/450
	if c.stack[len(c.stack)-1].count() == 0 {
		c.next()
	}

	k, v, flags := c.keyValue()
	if (flags & uint32(bucketLeafFlag)) != 0 {
		return k, nil
	}
	return k, v

}
84097
func (n *rootNode) Get(key string) (inner Node) {

	// the child key path
	path := n.keyPath(key)

	// if there is previous error, inherit
	if err := n.ParseError(); err != nil {
		return &rootNode{
			path: path,
			err:  err,
		}
	}

	if err := n.genMapBuf(); err != nil {
		if err == ErrorNotObject {
			path = n.path // fallback to the parent entity
		}
		inner = &rootNode{
			path: path,
			err: Error{
				Path: "json" + path,
				Err:  err,
			},
		}
	} else if val, ok := n.mapBuf[key]; !ok {
		inner = &rootNode{
			path: path,
			err: Error{
				Path: "json" + path,
				Err:  ErrorUndefined,
			},
		}
	} else {
		val.path = path
		inner = &val
	}
	return
}
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
	}
}
209870
func (s *Selection) BeforeNodes(ns ...*html.Node) *Selection {
	return s.manipulateNodes(ns, false, func(sn *html.Node, n *html.Node) {
		if sn.Parent != nil {
			sn.Parent.InsertBefore(n, sn)
		}
	})
}
756049
func (c *cursor) Prev() bool {
	// Ensure transaction state is valid.
	if err := c.bucket.tx.checkClosed(); err != nil {
		return false
	}

	// Nothing to return if cursor is exhausted.
	if c.currentIter == nil {
		return false
	}

	// Move the current iterator to the previous entry and choose the
	// iterator that is both valid and has the larger key.
	c.currentIter.Prev()
	return c.chooseIterator(false)
}
454156
func (t *PrimaryTree) First() (k uint64, v SecondaryLayer) {
	if q := t.first; q != nil {
		q := &q.d[0]
		k, v = q.k, q.v
	}
	return
}
530543
func (l *Slog) ProtoLevel() *Slog {
	l = l.copy()
	l.Log.Priority = ProtoPrio
	return l
}
469297
func (t *Mutable) Delete(key []byte) {
	// Find the node for the key along with its parent.  There is nothing to
	// do if the key does not exist.
	node, parent := t.get(key)
	if node == nil {
		return
	}

	// When the only node in the tree is the root node and it is the one
	// being deleted, there is nothing else to do besides removing it.
	if parent == nil && node.left == nil && node.right == nil {
		t.root = nil
		t.count = 0
		t.totalSize = 0
		return
	}

	// Perform rotations to move the node to delete to a leaf position while
	// maintaining the min-heap.
	var isLeft bool
	var child *treapNode
	for node.left != nil || node.right != nil {
		// Choose the child with the higher priority.
		if node.left == nil {
			child = node.right
			isLeft = false
		} else if node.right == nil {
			child = node.left
			isLeft = true
		} else if node.left.priority >= node.right.priority {
			child = node.left
			isLeft = true
		} else {
			child = node.right
			isLeft = false
		}

		// Rotate left or right depending on which side the child node
		// is on.  This has the effect of moving the node to delete
		// towards the bottom of the tree while maintaining the
		// min-heap.
		if isLeft {
			child.right, node.left = node, child.right
		} else {
			child.left, node.right = node, child.left
		}
		t.relinkGrandparent(child, node, parent)

		// The parent for the node to delete is now what was previously
		// its child.
		parent = child
	}

	// Delete the node, which is now a leaf node, by disconnecting it from
	// its parent.
	if parent.right == node {
		parent.right = nil
	} else {
		parent.left = nil
	}
	t.count--
	t.totalSize -= nodeSize(node)
}
1364875
func (lru *LRUCache) Oldest() (oldest time.Time) {
	lru.mu.Lock()
	defer lru.mu.Unlock()
	if lastElem := lru.list.Back(); lastElem != nil {
		oldest = lastElem.Value.(*entry).timeAccessed
	}
	return
}
1007667
func (n *node) next() *node {
	if len(n.forward) == 0 {
		return nil
	}
	return n.forward[0]
}