Home | History | Annotate | Download | only in collect 
      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 
     15 package com.google.common.collect;
     16 
     17 import static com.google.common.truth.Truth.assertThat;
     18 
     19 import com.google.common.annotations.GwtCompatible;
     20 import com.google.common.annotations.GwtIncompatible;
     21 import com.google.common.base.Optional;
     22 import com.google.common.testing.NullPointerTester;
     23 
     24 import junit.framework.TestCase;
     25 
     26 import java.util.Arrays;
     27 import java.util.List;
     28 
     29 import javax.annotation.Nullable;
     30 
     31 /**
     32  * Tests for {@code TreeTraverser}.
     33  *
     34  * @author Louis Wasserman
     35  */
     36 @GwtCompatible(emulated = true)
     37 public 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