1116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Copyright 2014 The Chromium Authors. All rights reserved. 2116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// Use of this source code is governed by a BSD-style license that can be 3116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch// found in the LICENSE file. 4116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 5116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "ui/accessibility/tree_generator.h" 6116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 7116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "ui/accessibility/ax_serializable_tree.h" 8116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch#include "ui/accessibility/ax_tree.h" 9116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 10116680a4aac90f2aa7413d9095a592090648e557Ben Murdochnamespace ui { 11116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 12116680a4aac90f2aa7413d9095a592090648e557Ben MurdochTreeGenerator::TreeGenerator(int node_count) 13116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch : node_count_(node_count), unique_tree_count_(1) { 14116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // (n-1)! for the possible trees. 15116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (int i = 2; i < node_count_; i++) 16116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch unique_tree_count_ *= i; 17116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // n! for the permutations of ids. 18116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (int i = 2; i <= node_count_; i++) 19116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch unique_tree_count_ *= i; 20116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch}; 21116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 22116680a4aac90f2aa7413d9095a592090648e557Ben Murdochint TreeGenerator::UniqueTreeCount() const { 23116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch return unique_tree_count_; 24116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch}; 25116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 26116680a4aac90f2aa7413d9095a592090648e557Ben Murdochvoid TreeGenerator::BuildUniqueTree(int tree_index, AXTree* out_tree) const { 27116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch std::vector<int> indices; 28116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch std::vector<int> permuted; 29116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch CHECK(tree_index <= unique_tree_count_); 30116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 31116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Use the first few bits of |tree_index| to permute the indices. 32116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (int i = 0; i < node_count_; i++) 33116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch indices.push_back(i + 1); 34116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (int i = 0; i < node_count_; i++) { 35116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int p = (node_count_ - i); 36116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int index = tree_index % p; 37116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch tree_index /= p; 38116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch permuted.push_back(indices[index]); 39116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch indices.erase(indices.begin() + index); 40116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 41116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 42116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Build an AXTreeUpdate. The first two nodes of the tree always 43116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // go in the same place. 44116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch AXTreeUpdate update; 45116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch update.nodes.resize(node_count_); 46116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch update.nodes[0].id = permuted[0]; 47116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch update.nodes[0].role = AX_ROLE_ROOT_WEB_AREA; 48116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch update.nodes[0].state = AX_STATE_NONE; 49116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch update.nodes[0].child_ids.push_back(permuted[1]); 50116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch update.nodes[1].id = permuted[1]; 51116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch update.nodes[1].state = AX_STATE_NONE; 52116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 53116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // The remaining nodes are assigned based on their parent 54116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // selected from the next bits from |tree_index|. 55116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch for (int i = 2; i < node_count_; i++) { 56116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch update.nodes[i].id = permuted[i]; 57116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch update.nodes[i].state = AX_STATE_NONE; 58116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch int parent_index = (tree_index % i); 59116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch tree_index /= i; 60116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch update.nodes[parent_index].child_ids.push_back(permuted[i]); 61116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch } 62116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 63116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch // Unserialize the tree update into the destination tree. 64116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch CHECK(out_tree->Unserialize(update)) << out_tree->error(); 65116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch}; 66116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch 67116680a4aac90f2aa7413d9095a592090648e557Ben Murdoch} // namespace ui 68