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 49
