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 java.util.NoSuchElementException;
  
  import static org.apache.cassandra.utils.btree.BTree.size;
  
  public class LeafBTreeSearchIterator<K, V> implements BTreeSearchIterator<K, V>
  {
      private final boolean forwards;
      private final K[] keys;
      private final Comparator<? super K> comparator;
      private int nextPos;
      private final int lowerBound, upperBound; // inclusive
      private boolean hasNext;
      private boolean hasCurrent;
  
      public LeafBTreeSearchIterator(Object[] btree, Comparator<? super K> comparator, BTree.Dir dir)
      {
          this(btree, comparator, dir, 0, size(btree) -1);
      }
  
      LeafBTreeSearchIterator(Object[] btree, Comparator<? super K> comparator, BTree.Dir dir, int lowerBound, int upperBound)
      {
          this.keys = (K[]) btree;
          this.forwards = dir == BTree.Dir.ASC;
          this.comparator = comparator;
          this.lowerBound = lowerBound;
          this.upperBound = upperBound;
          rewind();
      }
  
      public void rewind()
      {
          nextPos = forwards ? lowerBound : upperBound;
          hasNext = nextPos >= lowerBound && nextPos <= upperBound;
      }
  
      public V next()
      {
          if (!hasNext)
              throw new NoSuchElementException();
          final V elem = (V) keys[nextPos];
          nextPos += forwards ? 1 : -1;
          hasNext = nextPos >= lowerBound && nextPos <= upperBound;
          hasCurrent = true;
          return elem;
      }
  
      @Override
      public V peek()
      {
          if (!hasNext)
              throw new NoSuchElementException();
  
          return (V) keys[nextPos];
      }
  
      public boolean hasNext()
      {
          return hasNext;
      }
  
      private int searchNext(K key)
      {
          int lb = forwards ? nextPos : lowerBound; // inclusive
          int ub = forwards ? upperBound : nextPos; // inclusive
  
          return Arrays.binarySearch(keys, lb, ub + 1, key, comparator);
      }
  
      private void updateHasNext()
      {
          hasNext = nextPos >= lowerBound && nextPos <= upperBound;
      }
  
      public V next(K key)
      {
          if (!hasNext)
              return null;
          V result = null;
  
          // first check the current position in case of sequential access
          if (comparator.compare(keys[nextPos], key) == 0)
          {
              hasCurrent = true;
              result = (V) keys[nextPos];
              nextPos += forwards ? 1 : -1;
          }
          updateHasNext();
  
          if (result != null || !hasNext)
              return result;
  
          // otherwise search against the remaining values
          int find = searchNext(key);
          if (find >= 0)
          {
              hasCurrent = true;
              result = (V) keys[find];
              nextPos = find + (forwards ? 1 : -1);
          }
          else
          {
              nextPos = (forwards ? -1 : -2) - find;
              hasCurrent = false;
          }
          updateHasNext();
          return result;
      }
  
      public V current()
      {
          if (!hasCurrent)
              throw new NoSuchElementException();
          int current = forwards ? nextPos - 1 : nextPos + 1;
          return (V) keys[current];
      }
  
      public int indexOfCurrent()
      {
          if (!hasCurrent)
              throw new NoSuchElementException();
          int current = forwards ? nextPos - 1 : nextPos + 1;
          return forwards ? current - lowerBound : upperBound - current;
      }
  }
  