xref: /external/guava/guava/src/com/google/common/collect/BstInOrderPath.java

/*
 * Copyright (C) 2011 The Guava Authors
 *
 * Licensed 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 com.google.common.collect;

import static com.google.common.base.Preconditions.checkNotNull;

import com.google.common.annotations.GwtCompatible;
import com.google.common.base.Optional;

import java.util.NoSuchElementException;

import javax.annotation.Nullable;

/**
 * A {@code BstPath} supporting inorder traversal operations.
 *
 * @author Louis Wasserman
 */
@GwtCompatible
final class BstInOrderPath<N extends BstNode<?, N>> extends BstPath<N, BstInOrderPath<N>> {
  /**
   * The factory to use to construct {@code BstInOrderPath} values.
   */
  public static <N extends BstNode<?, N>> BstPathFactory<N, BstInOrderPath<N>> inOrderFactory() {
    return new BstPathFactory<N, BstInOrderPath<N>>() {
      @Override
      public BstInOrderPath<N> extension(BstInOrderPath<N> path, BstSide side) {
        return BstInOrderPath.extension(path, side);
      }

      @Override
      public BstInOrderPath<N> initialPath(N root) {
        return new BstInOrderPath<N>(root, null, null);
      }
    };
  }

  private static <N extends BstNode<?, N>> BstInOrderPath<N> extension(
      BstInOrderPath<N> path, BstSide side) {
    checkNotNull(path);
    N tip = path.getTip();
    return new BstInOrderPath<N>(tip.getChild(side), side, path);
  }

  private final BstSide sideExtension;
  private transient Optional<BstInOrderPath<N>> prevInOrder;
  private transient Optional<BstInOrderPath<N>> nextInOrder;

  private BstInOrderPath(
      N tip, @Nullable BstSide sideExtension, @Nullable BstInOrderPath<N> tail) {
    super(tip, tail);
    this.sideExtension = sideExtension;
    assert (sideExtension == null) == (tail == null);
  }

  private Optional<BstInOrderPath<N>> computeNextInOrder(BstSide side) {
    if (getTip().hasChild(side)) {
      BstInOrderPath<N> path = extension(this, side);
      BstSide otherSide = side.other();
      while (path.getTip().hasChild(otherSide)) {
        path = extension(path, otherSide);
      }
      return Optional.of(path);
    } else {
      BstInOrderPath<N> current = this;
      while (current.sideExtension == side) {
        current = current.getPrefix();
      }
      current = current.prefixOrNull();
      return Optional.fromNullable(current);
    }
  }

  private Optional<BstInOrderPath<N>> nextInOrder(BstSide side) {
    Optional<BstInOrderPath<N>> result;
    switch (side) {
      case LEFT:
        result = prevInOrder;
        return (result == null) ? prevInOrder = computeNextInOrder(side) : result;
      case RIGHT:
        result = nextInOrder;
        return (result == null) ? nextInOrder = computeNextInOrder(side) : result;
      default:
        throw new AssertionError();
    }
  }

  /**
   * Returns {@code true} if there is a next path in an in-order traversal in the given direction.
   */
  public boolean hasNext(BstSide side) {
    return nextInOrder(side).isPresent();
  }

  /**
   * Returns the next path in an in-order traversal in the given direction.
   *
   * @throws NoSuchElementException if this would be the last path in an in-order traversal
   */
  public BstInOrderPath<N> next(BstSide side) {
    if (!hasNext(side)) {
      throw new NoSuchElementException();
    }
    return nextInOrder(side).get();
  }

  /**
   * Returns the direction this path went in relative to its tail path, or {@code null} if this
   * path has no tail.
   */
  public BstSide getSideOfExtension() {
    return sideExtension;
  }
}