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 63