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 "ui/accessibility/tree_generator.h" 6 7 #include "ui/accessibility/ax_serializable_tree.h" 8 #include "ui/accessibility/ax_tree.h" 9 10 namespace ui { 11 12 TreeGenerator::TreeGenerator(int node_count) 13 : node_count_(node_count), unique_tree_count_(1) { 14 // (n-1)! for the possible trees. 15 for (int i = 2; i < node_count_; i++) 16 unique_tree_count_ *= i; 17 // n! for the permutations of ids. 18 for (int i = 2; i <= node_count_; i++) 19 unique_tree_count_ *= i; 20 }; 21 22 int TreeGenerator::UniqueTreeCount() const { 23 return unique_tree_count_; 24 }; 25 26 void TreeGenerator::BuildUniqueTree(int tree_index, AXTree* out_tree) const { 27 std::vector<int> indices; 28 std::vector<int> permuted; 29 CHECK(tree_index <= unique_tree_count_); 30 31 // Use the first few bits of |tree_index| to permute the indices. 32 for (int i = 0; i < node_count_; i++) 33 indices.push_back(i + 1); 34 for (int i = 0; i < node_count_; i++) { 35 int p = (node_count_ - i); 36 int index = tree_index % p; 37 tree_index /= p; 38 permuted.push_back(indices[index]); 39 indices.erase(indices.begin() + index); 40 } 41 42 // Build an AXTreeUpdate. The first two nodes of the tree always 43 // go in the same place. 44 AXTreeUpdate update; 45 update.nodes.resize(node_count_); 46 update.nodes[0].id = permuted[0]; 47 update.nodes[0].role = AX_ROLE_ROOT_WEB_AREA; 48 update.nodes[0].state = AX_STATE_NONE; 49 update.nodes[0].child_ids.push_back(permuted[1]); 50 update.nodes[1].id = permuted[1]; 51 update.nodes[1].state = AX_STATE_NONE; 52 53 // The remaining nodes are assigned based on their parent 54 // selected from the next bits from |tree_index|. 55 for (int i = 2; i < node_count_; i++) { 56 update.nodes[i].id = permuted[i]; 57 update.nodes[i].state = AX_STATE_NONE; 58 int parent_index = (tree_index % i); 59 tree_index /= i; 60 update.nodes[parent_index].child_ids.push_back(permuted[i]); 61 } 62 63 // Unserialize the tree update into the destination tree. 64 CHECK(out_tree->Unserialize(update)) << out_tree->error(); 65 }; 66 67 } // namespace ui 68
