1/*
2 * Copyright (C) 2011 The Guava Authors
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License"); you may not use this file except
5 * in compliance with the License. You may obtain a copy of the License at
6 *
7 * http://www.apache.org/licenses/LICENSE-2.0
8 *
9 * Unless required by applicable law or agreed to in writing, software distributed under the
10 * License is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either
11 * express or implied. See the License for the specific language governing permissions and
12 * limitations under the License.
13 */
14
15package com.google.common.collect;
16
17import static com.google.common.base.Preconditions.checkNotNull;
18
19import com.google.common.annotations.GwtCompatible;
20import com.google.common.base.Optional;
21
22import java.util.NoSuchElementException;
23
24import javax.annotation.Nullable;
25
26/**
27 * A {@code BstPath} supporting inorder traversal operations.
28 *
29 * @author Louis Wasserman
30 */
31@GwtCompatible
32final class BstInOrderPath<N extends BstNode<?, N>> extends BstPath<N, BstInOrderPath<N>> {
33  /**
34   * The factory to use to construct {@code BstInOrderPath} values.
35   */
36  public static <N extends BstNode<?, N>> BstPathFactory<N, BstInOrderPath<N>> inOrderFactory() {
37    return new BstPathFactory<N, BstInOrderPath<N>>() {
38      @Override
39      public BstInOrderPath<N> extension(BstInOrderPath<N> path, BstSide side) {
40        return BstInOrderPath.extension(path, side);
41      }
42
43      @Override
44      public BstInOrderPath<N> initialPath(N root) {
45        return new BstInOrderPath<N>(root, null, null);
46      }
47    };
48  }
49
50  private static <N extends BstNode<?, N>> BstInOrderPath<N> extension(
51      BstInOrderPath<N> path, BstSide side) {
52    checkNotNull(path);
53    N tip = path.getTip();
54    return new BstInOrderPath<N>(tip.getChild(side), side, path);
55  }
56
57  private final BstSide sideExtension;
58  private transient Optional<BstInOrderPath<N>> prevInOrder;
59  private transient Optional<BstInOrderPath<N>> nextInOrder;
60
61  private BstInOrderPath(
62      N tip, @Nullable BstSide sideExtension, @Nullable BstInOrderPath<N> tail) {
63    super(tip, tail);
64    this.sideExtension = sideExtension;
65    assert (sideExtension == null) == (tail == null);
66  }
67
68  private Optional<BstInOrderPath<N>> computeNextInOrder(BstSide side) {
69    if (getTip().hasChild(side)) {
70      BstInOrderPath<N> path = extension(this, side);
71      BstSide otherSide = side.other();
72      while (path.getTip().hasChild(otherSide)) {
73        path = extension(path, otherSide);
74      }
75      return Optional.of(path);
76    } else {
77      BstInOrderPath<N> current = this;
78      while (current.sideExtension == side) {
79        current = current.getPrefix();
80      }
81      current = current.prefixOrNull();
82      return Optional.fromNullable(current);
83    }
84  }
85
86  private Optional<BstInOrderPath<N>> nextInOrder(BstSide side) {
87    Optional<BstInOrderPath<N>> result;
88    switch (side) {
89      case LEFT:
90        result = prevInOrder;
91        return (result == null) ? prevInOrder = computeNextInOrder(side) : result;
92      case RIGHT:
93        result = nextInOrder;
94        return (result == null) ? nextInOrder = computeNextInOrder(side) : result;
95      default:
96        throw new AssertionError();
97    }
98  }
99
100  /**
101   * Returns {@code true} if there is a next path in an in-order traversal in the given direction.
102   */
103  public boolean hasNext(BstSide side) {
104    return nextInOrder(side).isPresent();
105  }
106
107  /**
108   * Returns the next path in an in-order traversal in the given direction.
109   *
110   * @throws NoSuchElementException if this would be the last path in an in-order traversal
111   */
112  public BstInOrderPath<N> next(BstSide side) {
113    if (!hasNext(side)) {
114      throw new NoSuchElementException();
115    }
116    return nextInOrder(side).get();
117  }
118
119  /**
120   * Returns the direction this path went in relative to its tail path, or {@code null} if this
121   * path has no tail.
122   */
123  public BstSide getSideOfExtension() {
124    return sideExtension;
125  }
126}
127