ui/accessibility/tree_generator.h

   1 // Copyright 2014 The Chromium Authors. All rights reserved.
   2 // Use of this source code is governed by a BSD-style license that can be
   3 // found in the LICENSE file.
   4
   5 #include <vector>
   6
   7 namespace ui {
   8
   9 class AXTree;
  10
  11 // A class to create all possible trees with up to <n> nodes and the
  12 // ids [1...n].
  13 //
  14 // There are two parts to the algorithm:
  15 //
  16 // The tree structure is formed as follows: without loss of generality,
  17 // the first node becomes the root and the second node becomes its
  18 // child. Thereafter, choose every possible parent for every other node.
  19 //
  20 // So for node i in (3...n), there are (i - 1) possible choices for its
  21 // parent, for a total of (n-1)! (n minus 1 factorial) possible trees.
  22 //
  23 // The second optional part is the assignment of ids to the nodes in the tree.
  24 // There are exactly n! (n factorial) permutations of the sequence 1...n,
  25 // and each of these is assigned to every node in every possible tree.
  26 //
  27 // The total number of trees for a given <n>, including permutations of ids, is
  28 // n! * (n-1)!
  29 //
  30 // n = 2: 2 trees
  31 // n = 3: 12 trees
  32 // n = 4: 144 trees
  33 // n = 5: 2880 trees
  34 //
  35 // Note that the generator returns all trees with sizes *up to* <n>, which
  36 // is a bit larger.
  37 //
  38 // This grows really fast! Still, it's very helpful for exhaustively testing
  39 // tree code on smaller trees at least.
  40 class TreeGenerator {
  41  public:
  42   // Will generate all trees with up to |max_node_count| nodes.
  43   // If |permutations| is true, will return every possible permutation of
  44   // ids, otherwise the root will always have id 1, and so on.
  45   TreeGenerator(int max_node_count, bool permutations);
  46   ~TreeGenerator();
  47
  48   int UniqueTreeCount() const;
  49
  50   void BuildUniqueTree(int tree_index, AXTree* out_tree) const;
  51
  52  private:
  53   void BuildUniqueTreeWithSize(
  54       int node_count, int tree_index, AXTree* out_tree) const;
  55
  56   int max_node_count_;
  57   bool permutations_;
  58   int total_unique_tree_count_;
  59   std::vector<int> unique_tree_count_by_size_;
  60 };
  61
  62 }  // namespace ui