/*
 * Licensed to the Apache Software Foundation (ASF) under one
 * or more contributor license agreements.  See the NOTICE file
 * distributed with this work for additional information
 * regarding copyright ownership.  The ASF licenses this file
 * to you under the Apache License, Version 2.0 (the
 * "License"); you may not use this file except in compliance
 * with the License.  You may obtain a copy of the License at
 *
 *    http://www.apache.org/licenses/LICENSE-2.0
 *
 * Unless required by applicable law or agreed to in writing,
 * software distributed under the License is distributed on an
 * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
 * KIND, either express or implied.  See the License for the
 * specific language governing permissions and limitations
 * under the License.
 */
package org.apache.cassandra.utils.btree;

import java.util.Arrays;
import java.util.Comparator;

import static org.apache.cassandra.utils.btree.BTree.*;

Supports two basic operations for moving around a BTree, either forwards or backwards:
moveOne(), and seekTo()
These two methods, along with movement to the start/end, permit us to construct any desired
movement around a btree, without much cognitive burden.
This TreeCursor is (and has its methods) package private. This is to avoid polluting the BTreeSearchIterator
that extends it, and uses its functionality. If this class is useful for wider consumption, a public extension
class can be provided, that just makes all of its methods public.
/**
 * Supports two basic operations for moving around a BTree, either forwards or backwards:
 * moveOne(), and seekTo()
 *
 * These two methods, along with movement to the start/end, permit us to construct any desired
 * movement around a btree, without much cognitive burden.
 *
 * This TreeCursor is (and has its methods) package private. This is to avoid polluting the BTreeSearchIterator
 * that extends it, and uses its functionality. If this class is useful for wider consumption, a public extension
 * class can be provided, that just makes all of its methods public.
 */
class TreeCursor<K> extends NodeCursor<K>
{
    // TODO: spend some time optimising compiler inlining decisions: many of these methods have only one primary call-site

    NodeCursor<K> cur;

    TreeCursor(Comparator<? super K> comparator, Object[] node)
    {
        super(node, null, comparator);
    }

    
Move the cursor to either the first or last item in the btree
Params:
start – true if should move to the first item; false moves to the last/**
     * Move the cursor to either the first or last item in the btree
     * @param start true if should move to the first item; false moves to the last
     */
    void reset(boolean start)
    {
        cur = root();
        root().inChild = false;
        // this is a corrupt position, but we ensure we never use it except to start our search from
        root().position = start ? -1 : getKeyEnd(root().node);
    }

    
move the Cursor one item, either forwards or backwards
Params:
forwards – direction of travel
Returns:
false iff the cursor is exhausted in the direction of travel/**
     * move the Cursor one item, either forwards or backwards
     * @param forwards direction of travel
     * @return false iff the cursor is exhausted in the direction of travel
     */
    int moveOne(boolean forwards)
    {
        NodeCursor<K> cur = this.cur;
        if (cur.isLeaf())
        {
            // if we're a leaf, we try to step forwards inside ourselves
            if (cur.advanceLeafNode(forwards))
                return cur.globalLeafIndex();

            // if we fail, we just find our bounding parent
            this.cur = cur = moveOutOfLeaf(forwards, cur, root());
            return cur.globalIndex();
        }

        // otherwise we descend directly into our next child
        if (forwards)
            ++cur.position;
        cur = cur.descend();

        // and go to its first item
        NodeCursor<K> next;
        while ( null != (next = cur.descendToFirstChild(forwards)) )
            cur = next;

        this.cur = cur;
        return cur.globalLeafIndex();
    }

    
seeks from the current position, forwards or backwards, for the provided key
while the direction could be inferred (or ignored), it is required so that (e.g.) we do not infinitely loop on bad inputs
if there is no such key, it moves to the key that would naturally follow/succeed it (i.e. it behaves as ceil when ascending; floor when descending)
/**
     * seeks from the current position, forwards or backwards, for the provided key
     * while the direction could be inferred (or ignored), it is required so that (e.g.) we do not infinitely loop on bad inputs
     * if there is no such key, it moves to the key that would naturally follow/succeed it (i.e. it behaves as ceil when ascending; floor when descending)
     */
    boolean seekTo(K key, boolean forwards, boolean skipOne)
    {
        NodeCursor<K> cur = this.cur;

        /**
         * decide if we will "try one" value by itself, as a sequential access;
         * we actually *require* that we try the "current key" for any node before we call seekInNode on it.
         *
         * if we are already on a value, we just check it irregardless of if it is a leaf or not;
         * if we are not, we have already excluded it (as we have consumed it), so:
         *    if we are on a branch we consider that good enough;
         *    otherwise, we move onwards one, and we try the new value
         *
         */
        boolean tryOne = !skipOne;
        if ((!tryOne & cur.isLeaf()) && !(tryOne = (cur.advanceLeafNode(forwards) || (cur = moveOutOfLeaf(forwards, cur, null)) != null)))
        {
            // we moved out of the tree; return out-of-bounds
            this.cur = root();
            return false;
        }

        if (tryOne)
        {
            // we're presently on a value we can (and *must*) cheaply test
            K test = cur.value();

            int cmp;
            if (key == test) cmp = 0; // check object identity first, since we utilise that in some places and it's very cheap
            else cmp = comparator.compare(test, key); // order of provision matters for asymmetric comparators
            if (forwards ? cmp >= 0 : cmp <= 0)
            {
                // we've either matched, or excluded the value from being present
                this.cur = cur;
                return cmp == 0;
            }
        }

        // if we failed to match with the cheap test, first look to see if we're even in the correct sub-tree
        while (cur != root())
        {
            NodeCursor<K> bound = cur.boundIterator(forwards);
            if (bound == null)
                break; // we're all that's left

            int cmpbound = comparator.compare(bound.bound(forwards), key); // order of provision matters for asymmetric comparators
            if (forwards ? cmpbound > 0 : cmpbound < 0)
                break; //  already in correct sub-tree

            // bound is on-or-before target, so ascend to that bound and continue looking upwards
            cur = bound;
            cur.safeAdvanceIntoBranchFromChild(forwards);
            if (cmpbound == 0) // it was an exact match, so terminate here
            {
                this.cur = cur;
                return true;
            }
        }

        // we must now be able to find our target in the sub-tree rooted at cur
        boolean match;
        while (!(match = cur.seekInNode(key, forwards)) && !cur.isLeaf())
        {
            cur = cur.descend();
            cur.position = forwards ? -1 : getKeyEnd(cur.node);
        }

        if (!match)
            cur = ensureValidLocation(forwards, cur);

        this.cur = cur;
        assert !cur.inChild;
        return match;
    }

    
ensures a leaf node we have seeked in, is not positioned outside of its bounds,
by moving us into its parents (if any); if it is the root, we're permitted to be out-of-bounds
as this indicates exhaustion
/**
     * ensures a leaf node we have seeked in, is not positioned outside of its bounds,
     * by moving us into its parents (if any); if it is the root, we're permitted to be out-of-bounds
     * as this indicates exhaustion
     */
    private NodeCursor<K> ensureValidLocation(boolean forwards, NodeCursor<K> cur)
    {
        assert cur.isLeaf();
        int position = cur.position;
        // if we're out of bounds of the leaf, move once in direction of travel
        if ((position < 0) | (position >= getLeafKeyEnd(cur.node)))
            cur = moveOutOfLeaf(forwards, cur, root());
        return cur;
    }

    
move out of a leaf node that is currently out of (its own) bounds
Returns:
null if we're now out-of-bounds of the whole tree/**
     * move out of a leaf node that is currently out of (its own) bounds
     * @return null if we're now out-of-bounds of the whole tree
     */
    private <K> NodeCursor<K> moveOutOfLeaf(boolean forwards, NodeCursor<K> cur, NodeCursor<K> ifFail)
    {
        while (true)
        {
            cur = cur.parent;
            if (cur == null)
            {
                root().inChild = false;
                return ifFail;
            }
            if (cur.advanceIntoBranchFromChild(forwards))
                break;
        }
        cur.inChild = false;
        return cur;
    }

    
resets the cursor and seeks to the specified position; does not assume locality or take advantage of the cursor's current position
/**
     * resets the cursor and seeks to the specified position; does not assume locality or take advantage of the cursor's current position
     */
    void seekTo(int index)
    {
        if ((index < 0) | (index >= BTree.size(rootNode())))
        {
            if ((index < -1) | (index > BTree.size(rootNode())))
                throw new IndexOutOfBoundsException(index + " not in range [0.." + BTree.size(rootNode()) + ")");
            reset(index == -1);
            return;
        }

        NodeCursor<K> cur = root();
        assert cur.nodeOffset == 0;
        while (true)
        {
            int relativeIndex = index - cur.nodeOffset; // index within subtree rooted at cur
            Object[] node = cur.node;

            if (cur.isLeaf())
            {
                assert relativeIndex < getLeafKeyEnd(node);
                cur.position = relativeIndex;
                this.cur = cur;
                return;
            }

            int[] sizeMap = getSizeMap(node);
            int boundary = Arrays.binarySearch(sizeMap, relativeIndex);
            if (boundary >= 0)
            {
                // exact match, in this branch node
                assert boundary < sizeMap.length - 1;
                cur.position = boundary;
                cur.inChild = false;
                this.cur = cur;
                return;
            }

            cur.inChild = true;
            cur.position = -1 -boundary;
            cur = cur.descend();
        }
    }

    private NodeCursor<K> root()
    {
        return this;
    }

    Object[] rootNode()
    {
        return this.node;
    }

    K currentValue()
    {
        return cur.value();
    }
}