content: /*
   * 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.
   */
  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
       * @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
       * @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)
       */
      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
       */
      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
       * @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
       */
      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 = sizeMap(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();
      }
  }
  