| /* |
| * 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.truth.Truth.assertThat; |
| |
| import com.google.common.annotations.GwtCompatible; |
| import com.google.common.base.Optional; |
| |
| import junit.framework.TestCase; |
| |
| import java.util.Arrays; |
| import java.util.List; |
| |
| import javax.annotation.Nullable; |
| |
| /** |
| * Tests for {@code TreeTraverser}. |
| * |
| * @author Louis Wasserman |
| */ |
| @GwtCompatible(emulated = true) |
| public class TreeTraverserTest extends TestCase { |
| private static final class Tree { |
| final char value; |
| final List<Tree> children; |
| |
| public Tree(char value, Tree... children) { |
| this.value = value; |
| this.children = Arrays.asList(children); |
| } |
| } |
| |
| private static final class BinaryTree { |
| final char value; |
| @Nullable |
| final BinaryTree left; |
| @Nullable |
| final BinaryTree right; |
| |
| private BinaryTree(char value, BinaryTree left, BinaryTree right) { |
| this.value = value; |
| this.left = left; |
| this.right = right; |
| } |
| } |
| |
| private static final TreeTraverser<Tree> ADAPTER = new TreeTraverser<Tree>() { |
| @Override |
| public Iterable<Tree> children(Tree node) { |
| return node.children; |
| } |
| }; |
| |
| private static final BinaryTreeTraverser<BinaryTree> BIN_ADAPTER = |
| new BinaryTreeTraverser<BinaryTree>() { |
| |
| @Override |
| public Optional<BinaryTree> leftChild(BinaryTree node) { |
| return Optional.fromNullable(node.left); |
| } |
| |
| @Override |
| public Optional<BinaryTree> rightChild(BinaryTree node) { |
| return Optional.fromNullable(node.right); |
| } |
| }; |
| |
| // h |
| // / | \ |
| // / e \ |
| // d g |
| // /|\ | |
| // / | \ f |
| // a b c |
| static final Tree a = new Tree('a'); |
| static final Tree b = new Tree('b'); |
| static final Tree c = new Tree('c'); |
| static final Tree d = new Tree('d', a, b, c); |
| static final Tree e = new Tree('e'); |
| static final Tree f = new Tree('f'); |
| static final Tree g = new Tree('g', f); |
| static final Tree h = new Tree('h', d, e, g); |
| |
| // d |
| // / \ |
| // b e |
| // / \ \ |
| // a c f |
| // / |
| // g |
| static final BinaryTree ba = new BinaryTree('a', null, null); |
| static final BinaryTree bc = new BinaryTree('c', null, null); |
| static final BinaryTree bb = new BinaryTree('b', ba, bc); |
| static final BinaryTree bg = new BinaryTree('g', null, null); |
| static final BinaryTree bf = new BinaryTree('f', bg, null); |
| static final BinaryTree be = new BinaryTree('e', null, bf); |
| static final BinaryTree bd = new BinaryTree('d', bb, be); |
| |
| static String iterationOrder(Iterable<Tree> iterable) { |
| StringBuilder builder = new StringBuilder(); |
| for (Tree t : iterable) { |
| builder.append(t.value); |
| } |
| return builder.toString(); |
| } |
| |
| static String binaryIterationOrder(Iterable<BinaryTree> iterable) { |
| StringBuilder builder = new StringBuilder(); |
| for (BinaryTree t : iterable) { |
| builder.append(t.value); |
| } |
| return builder.toString(); |
| } |
| |
| public void testPreOrder() { |
| assertThat(iterationOrder(ADAPTER.preOrderTraversal(h))).isEqualTo("hdabcegf"); |
| assertThat(binaryIterationOrder(BIN_ADAPTER.preOrderTraversal(bd))).isEqualTo("dbacefg"); |
| } |
| |
| public void testPostOrder() { |
| assertThat(iterationOrder(ADAPTER.postOrderTraversal(h))).isEqualTo("abcdefgh"); |
| assertThat(binaryIterationOrder(BIN_ADAPTER.postOrderTraversal(bd))).isEqualTo("acbgfed"); |
| } |
| |
| public void testBreadthOrder() { |
| assertThat(iterationOrder(ADAPTER.breadthFirstTraversal(h))).isEqualTo("hdegabcf"); |
| assertThat(binaryIterationOrder(BIN_ADAPTER.breadthFirstTraversal(bd))).isEqualTo("dbeacfg"); |
| } |
| |
| public void testInOrder() { |
| assertThat(binaryIterationOrder(BIN_ADAPTER.inOrderTraversal(bd))).isEqualTo("abcdegf"); |
| } |
| } |
| |