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 15 package com.google.common.collect; 16 17 import static com.google.common.base.Preconditions.checkNotNull; 18 19 import com.google.common.annotations.GwtCompatible; 20 import com.google.common.base.Optional; 21 22 import java.util.NoSuchElementException; 23 24 import javax.annotation.Nullable; 25 26 /** 27 * A {@code BstPath} supporting inorder traversal operations. 28 * 29 * @author Louis Wasserman 30 */ 31 @GwtCompatible 32 final 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
