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 License
10 * is distributed on an "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express
11 * or implied.  See the License for the specific language governing permissions and limitations
12 * under the License.
13 */
14
15package com.google.common.collect;
16
17import static com.google.common.truth.Truth.assertThat;
18
19import com.google.common.annotations.GwtCompatible;
20import com.google.common.annotations.GwtIncompatible;
21import com.google.common.base.Optional;
22import com.google.common.testing.NullPointerTester;
23
24import junit.framework.TestCase;
25
26import java.util.Arrays;
27import java.util.List;
28
29import javax.annotation.Nullable;
30
31/**
32 * Tests for {@code TreeTraverser}.
33 *
34 * @author Louis Wasserman
35 */
36@GwtCompatible(emulated = true)
37public class TreeTraverserTest extends TestCase {
38  private static final class Tree {
39    final char value;
40    final List<Tree> children;
41
42    public Tree(char value, Tree... children) {
43      this.value = value;
44      this.children = Arrays.asList(children);
45    }
46  }
47
48  private static final class BinaryTree {
49    final char value;
50    @Nullable
51    final BinaryTree left;
52    @Nullable
53    final BinaryTree right;
54
55    private BinaryTree(char value, BinaryTree left, BinaryTree right) {
56      this.value = value;
57      this.left = left;
58      this.right = right;
59    }
60  }
61
62  private static final TreeTraverser<Tree> ADAPTER = new TreeTraverser<Tree>() {
63    @Override
64    public Iterable<Tree> children(Tree node) {
65      return node.children;
66    }
67  };
68
69  private static final BinaryTreeTraverser<BinaryTree> BIN_ADAPTER =
70      new BinaryTreeTraverser<BinaryTree>() {
71
72    @Override
73    public Optional<BinaryTree> leftChild(BinaryTree node) {
74      return Optional.fromNullable(node.left);
75    }
76
77    @Override
78    public Optional<BinaryTree> rightChild(BinaryTree node) {
79      return Optional.fromNullable(node.right);
80    }
81  };
82
83  //        h
84  //      / | \
85  //     /  e  \
86  //    d       g
87  //   /|\      |
88  //  / | \     f
89  // a  b  c
90  static final Tree a = new Tree('a');
91  static final Tree b = new Tree('b');
92  static final Tree c = new Tree('c');
93  static final Tree d = new Tree('d', a, b, c);
94  static final Tree e = new Tree('e');
95  static final Tree f = new Tree('f');
96  static final Tree g = new Tree('g', f);
97  static final Tree h = new Tree('h', d, e, g);
98
99  //      d
100  //     / \
101  //    b   e
102  //   / \   \
103  //  a   c   f
104  //         /
105  //        g
106  static final BinaryTree ba = new BinaryTree('a', null, null);
107  static final BinaryTree bc = new BinaryTree('c', null, null);
108  static final BinaryTree bb = new BinaryTree('b', ba, bc);
109  static final BinaryTree bg = new BinaryTree('g', null, null);
110  static final BinaryTree bf = new BinaryTree('f', bg, null);
111  static final BinaryTree be = new BinaryTree('e', null, bf);
112  static final BinaryTree bd = new BinaryTree('d', bb, be);
113
114  static String iterationOrder(Iterable<Tree> iterable) {
115    StringBuilder builder = new StringBuilder();
116    for (Tree t : iterable) {
117      builder.append(t.value);
118    }
119    return builder.toString();
120  }
121
122  static String binaryIterationOrder(Iterable<BinaryTree> iterable) {
123    StringBuilder builder = new StringBuilder();
124    for (BinaryTree t : iterable) {
125      builder.append(t.value);
126    }
127    return builder.toString();
128  }
129
130  public void testPreOrder() {
131    assertThat(iterationOrder(ADAPTER.preOrderTraversal(h))).isEqualTo("hdabcegf");
132    assertThat(binaryIterationOrder(BIN_ADAPTER.preOrderTraversal(bd))).isEqualTo("dbacefg");
133  }
134
135  public void testPostOrder() {
136    assertThat(iterationOrder(ADAPTER.postOrderTraversal(h))).isEqualTo("abcdefgh");
137    assertThat(binaryIterationOrder(BIN_ADAPTER.postOrderTraversal(bd))).isEqualTo("acbgfed");
138  }
139
140  public void testBreadthOrder() {
141    assertThat(iterationOrder(ADAPTER.breadthFirstTraversal(h))).isEqualTo("hdegabcf");
142    assertThat(binaryIterationOrder(BIN_ADAPTER.breadthFirstTraversal(bd))).isEqualTo("dbeacfg");
143  }
144
145  public void testInOrder() {
146    assertThat(binaryIterationOrder(BIN_ADAPTER.inOrderTraversal(bd))).isEqualTo("abcdegf");
147  }
148
149  @GwtIncompatible("NullPointerTester")
150  public void testNulls() {
151    NullPointerTester tester = new NullPointerTester();
152    tester.testAllPublicInstanceMethods(ADAPTER);
153    tester.testAllPublicInstanceMethods(BIN_ADAPTER);
154  }
155}
156