ui/accessibility/tree_generator.cc

   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