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
10namespace ui {
11
12TreeGenerator::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
22int TreeGenerator::UniqueTreeCount() const {
23  return unique_tree_count_;
24};
25
26void 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