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 namespace ui {
   6
   7 class AXTree;
   8
   9 // A class to create all possible trees with <n> nodes and the ids [1...n].
  10 //
  11 // There are two parts to the algorithm:
  12 //
  13 // The tree structure is formed as follows: without loss of generality,
  14 // the first node becomes the root and the second node becomes its
  15 // child. Thereafter, choose every possible parent for every other node.
  16 //
  17 // So for node i in (3...n), there are (i - 1) possible choices for its
  18 // parent, for a total of (n-1)! (n minus 1 factorial) possible trees.
  19 //
  20 // The second part is the assignment of ids to the nodes in the tree.
  21 // There are exactly n! (n factorial) permutations of the sequence 1...n,
  22 // and each of these is assigned to every node in every possible tree.
  23 //
  24 // The total number of trees returned for a given <n>, then, is
  25 // n! * (n-1)!
  26 //
  27 // n = 2: 2 trees
  28 // n = 3: 12 trees
  29 // n = 4: 144 trees
  30 // n = 5: 2880 trees
  31 //
  32 // This grows really fast! Luckily it's very unlikely that there'd be
  33 // bugs that affect trees with >4 nodes that wouldn't affect a smaller tree
  34 // too.
  35 class TreeGenerator {
  36  public:
  37   TreeGenerator(int node_count);
  38
  39   int UniqueTreeCount() const;
  40
  41   void BuildUniqueTree(int tree_index, AXTree* out_tree) const;
  42
  43  private:
  44   int node_count_;
  45   int unique_tree_count_;
  46 };
  47
  48 }  // namespace ui