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 #ifndef UI_ACCESSIBILITY_TREE_GENERATOR_H_
6 #define UI_ACCESSIBILITY_TREE_GENERATOR_H_
7 
8 #include <vector>
9 
10 #include "ui/accessibility/ax_tree_update_forward.h"
11 
12 namespace ui {
13 
14 class AXTree;
15 
16 // A class to create all possible trees with up to <n> nodes and the
17 // ids [1...n].
18 //
19 // There are two parts to the algorithm:
20 //
21 // The tree structure is formed as follows: without loss of generality,
22 // the first node becomes the root and the second node becomes its
23 // child. Thereafter, choose every possible parent for every other node.
24 //
25 // So for node i in (3...n), there are (i - 1) possible choices for its
26 // parent, for a total of (n-1)! (n minus 1 factorial) possible trees.
27 //
28 // The second optional part is the assignment of ids to the nodes in the tree.
29 // There are exactly n! (n factorial) permutations of the sequence 1...n,
30 // and each of these is assigned to every node in every possible tree.
31 //
32 // The total number of trees for a given <n>, including permutations of ids, is
33 // n! * (n-1)!
34 //
35 // n = 2: 2 trees
36 // n = 3: 12 trees
37 // n = 4: 144 trees
38 // n = 5: 2880 trees
39 //
40 // Note that the generator returns all trees with sizes *up to* <n>, which
41 // is a bit larger.
42 //
43 // This grows really fast! Still, it's very helpful for exhaustively testing
44 // tree code on smaller trees at least.
45 class TreeGenerator {
46  public:
47   // Will generate all trees with up to |max_node_count| nodes.
48   // If |permutations| is true, will return every possible permutation of
49   // ids, otherwise the root will always have id 1, and so on.
50   TreeGenerator(int max_node_count, bool permutations);
51   ~TreeGenerator();
52 
53   // Build all unique trees (no nodes ignored).
54   int UniqueTreeCount() const;
55   void BuildUniqueTree(int tree_index, AXTree* out_tree) const;
56 
57   // Support for returning every permutation of ignored nodes
58   // (other than the root, which is never ignored) per unique tree.
59   int IgnoredPermutationCountPerUniqueTree(int tree_index) const;
60   void BuildUniqueTreeWithIgnoredNodes(int tree_index,
61                                        int ignored_index,
62                                        AXTree* out_tree) const;
63 
64  private:
65   void BuildUniqueTreeUpdate(int tree_index,
66                              AXTreeUpdate* out_tree_update) const;
67   void BuildUniqueTreeUpdateWithSize(int node_count,
68                                      int tree_index,
69                                      AXTreeUpdate* out_tree_update) const;
70 
71   int max_node_count_;
72   bool permutations_;
73   int total_unique_tree_count_;
74   std::vector<int> unique_tree_count_by_size_;
75 };
76 
77 }  // namespace ui
78 
79 #endif  // UI_ACCESSIBILITY_TREE_GENERATOR_H_
80