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.base.Optional;
     21 
     22 import junit.framework.TestCase;
     23 
     24 import java.util.Arrays;
     25 import java.util.List;
     26 
     27 import javax.annotation.Nullable;
     28 
     29 /**
     30  * Tests for {@code TreeTraverser}.
     31  *
     32  * @author Louis Wasserman
     33  */
     34 @GwtCompatible(emulated = true)
     35 public 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