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