1/*
2 * Copyright (C) 2012 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 under
12 * the License.
13 */
14
15package com.google.common.collect;
16
17import com.google.caliper.BeforeExperiment;
18import com.google.caliper.Benchmark;
19import com.google.caliper.Param;
20import com.google.common.base.Optional;
21import com.google.common.primitives.Ints;
22
23import java.util.List;
24import java.util.Random;
25
26/**
27 * Benchmarks for the {@code TreeTraverser} and optimized {@code BinaryTreeTraverser} operations on
28 * binary trees.
29 *
30 * @author Louis Wasserman
31 */
32public class BinaryTreeTraverserBenchmark {
33  private static class BinaryNode {
34    final int x;
35    final Optional<BinaryNode> left;
36    final Optional<BinaryNode> right;
37
38    BinaryNode(int x, Optional<BinaryNode> left, Optional<BinaryNode> right) {
39      this.x = x;
40      this.left = left;
41      this.right = right;
42    }
43  }
44
45  enum Topology {
46    BALANCED {
47      @Override
48      Optional<BinaryNode> createTree(int size, Random rng) {
49        if (size == 0) {
50          return Optional.absent();
51        } else {
52          int leftChildSize = (size - 1) / 2;
53          int rightChildSize = size - 1 - leftChildSize;
54          return Optional.of(new BinaryNode(
55              rng.nextInt(), createTree(leftChildSize, rng), createTree(rightChildSize, rng)));
56        }
57      }
58    },
59    ALL_LEFT {
60      @Override
61      Optional<BinaryNode> createTree(int size, Random rng) {
62        Optional<BinaryNode> root = Optional.absent();
63        for (int i = 0; i < size; i++) {
64          root = Optional.of(new BinaryNode(rng.nextInt(), root, Optional.<BinaryNode>absent()));
65        }
66        return root;
67      }
68    },
69    ALL_RIGHT {
70      @Override
71      Optional<BinaryNode> createTree(int size, Random rng) {
72        Optional<BinaryNode> root = Optional.absent();
73        for (int i = 0; i < size; i++) {
74          root = Optional.of(new BinaryNode(rng.nextInt(), Optional.<BinaryNode>absent(), root));
75        }
76        return root;
77      }
78    },
79    RANDOM {
80      /**
81       * Generates a tree with topology selected uniformly at random from the topologies of binary
82       * trees of the specified size.
83       */
84      @Override
85      Optional<BinaryNode> createTree(int size, Random rng) {
86        int[] keys = new int[size];
87        for (int i = 0; i < size; i++) {
88          keys[i] = rng.nextInt();
89        }
90        return createTreap(Ints.asList(keys));
91      }
92
93      // See http://en.wikipedia.org/wiki/Treap for details on the algorithm.
94      private Optional<BinaryNode> createTreap(List<Integer> keys) {
95        if (keys.isEmpty()) {
96          return Optional.absent();
97        }
98        int minIndex = 0;
99        for (int i = 1; i < keys.size(); i++) {
100          if (keys.get(i) < keys.get(minIndex)) {
101            minIndex = i;
102          }
103        }
104        Optional<BinaryNode> leftChild = createTreap(keys.subList(0, minIndex));
105        Optional<BinaryNode> rightChild = createTreap(keys.subList(minIndex + 1, keys.size()));
106        return Optional.of(new BinaryNode(keys.get(minIndex), leftChild, rightChild));
107      }
108    };
109
110    abstract Optional<BinaryNode> createTree(int size, Random rng);
111  }
112
113  private static final BinaryTreeTraverser<BinaryNode> BINARY_VIEWER =
114      new BinaryTreeTraverser<BinaryNode>() {
115
116    @Override
117    public Optional<BinaryNode> leftChild(BinaryNode node) {
118      return node.left;
119    }
120
121    @Override
122    public Optional<BinaryNode> rightChild(BinaryNode node) {
123      return node.right;
124    }
125  };
126
127  private static final TreeTraverser<BinaryNode> VIEWER = new TreeTraverser<BinaryNode>() {
128    @Override
129    public Iterable<BinaryNode> children(BinaryNode root) {
130      return BINARY_VIEWER.children(root);
131    }
132  };
133
134  enum Traversal {
135    PRE_ORDER {
136      @Override
137      <T> Iterable<T> view(T root, TreeTraverser<T> viewer) {
138        return viewer.preOrderTraversal(root);
139      }
140    },
141    POST_ORDER {
142      @Override
143      <T> Iterable<T> view(T root, TreeTraverser<T> viewer) {
144        return viewer.postOrderTraversal(root);
145      }
146    },
147    BREADTH_FIRST {
148      @Override
149      <T> Iterable<T> view(T root, TreeTraverser<T> viewer) {
150        return viewer.breadthFirstTraversal(root);
151      }
152    };
153
154    abstract <T> Iterable<T> view(T root, TreeTraverser<T> viewer);
155  }
156
157  private Iterable<BinaryNode> view;
158
159  @Param
160  Topology topology;
161
162  @Param({"1", "100", "10000", "1000000"})
163  int size;
164
165  @Param
166  Traversal traversal;
167
168  @Param
169  boolean useBinaryTraverser;
170
171  @Param({"1234"})
172  SpecialRandom rng;
173
174  @BeforeExperiment
175  void setUp() {
176    this.view = traversal.view(
177        topology.createTree(size, rng).get(),
178        useBinaryTraverser ? BINARY_VIEWER : VIEWER);
179  }
180
181  @Benchmark int traversal(int reps) {
182    int tmp = 0;
183
184    for (int i = 0; i < reps; i++) {
185      for (BinaryNode node : view) {
186        tmp += node.x;
187      }
188    }
189    return tmp;
190  }
191}
192