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