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 static int UniqueTreeCountForNodeCount(int node_count,
  13                                        bool permutations) {
  14   int unique_tree_count = 1;
  15
  16   // (n-1)! for the possible trees.
  17   for (int i = 2; i < node_count; ++i)
  18     unique_tree_count *= i;
  19
  20   // n! for the permutations of ids.
  21   if (permutations)
  22     unique_tree_count = unique_tree_count * unique_tree_count * node_count;
  23
  24   return unique_tree_count;
  25 }
  26
  27 TreeGenerator::TreeGenerator(int max_node_count, bool permutations)
  28     : max_node_count_(max_node_count),
  29       permutations_(permutations),
  30       total_unique_tree_count_(0) {
  31   unique_tree_count_by_size_.push_back(0);
  32   for (int i = 1; i <= max_node_count; ++i) {
  33     int unique_tree_count = UniqueTreeCountForNodeCount(i, permutations);
  34     unique_tree_count_by_size_.push_back(unique_tree_count);
  35     total_unique_tree_count_ += unique_tree_count;
  36   }
  37 }
  38
  39 TreeGenerator::~TreeGenerator() {
  40 }
  41
  42 int TreeGenerator::UniqueTreeCount() const {
  43   return total_unique_tree_count_;
  44 }
  45
  46 void TreeGenerator::BuildUniqueTree(int tree_index, AXTree* out_tree) const {
  47   CHECK_LT(tree_index, total_unique_tree_count_);
  48
  49   int unique_tree_count_so_far = 0;
  50   for (int node_count = 1; node_count <= max_node_count_; ++node_count) {
  51     int unique_tree_count = unique_tree_count_by_size_[node_count];
  52     if (tree_index - unique_tree_count_so_far < unique_tree_count) {
  53       BuildUniqueTreeWithSize(node_count,
  54                               tree_index - unique_tree_count_so_far,
  55                               out_tree);
  56       return;
  57     }
  58     unique_tree_count_so_far += unique_tree_count;
  59   }
  60 }
  61
  62 void TreeGenerator::BuildUniqueTreeWithSize(
  63     int node_count, int tree_index, AXTree* out_tree) const {
  64   std::vector<int> indices;
  65   std::vector<int> permuted;
  66   int unique_tree_count = unique_tree_count_by_size_[node_count];
  67   CHECK_LT(tree_index, unique_tree_count);
  68
  69   if (permutations_) {
  70     // Use the first few bits of |tree_index| to permute the indices.
  71     for (int i = 0; i < node_count; ++i)
  72       indices.push_back(i + 1);
  73     for (int i = 0; i < node_count; ++i) {
  74       int p = (node_count - i);
  75       int index = tree_index % p;
  76       tree_index /= p;
  77       permuted.push_back(indices[index]);
  78       indices.erase(indices.begin() + index);
  79     }
  80   } else {
  81     for (int i = 0; i < node_count; ++i)
  82       permuted.push_back(i + 1);
  83   }
  84
  85   // Build an AXTreeUpdate. The first two nodes of the tree always
  86   // go in the same place.
  87   AXTreeUpdate update;
  88   update.nodes.resize(node_count);
  89   update.nodes[0].id = permuted[0];
  90   update.nodes[0].role = AX_ROLE_ROOT_WEB_AREA;
  91   update.nodes[0].state = AX_STATE_NONE;
  92   if (node_count > 1) {
  93     update.nodes[0].child_ids.push_back(permuted[1]);
  94     update.nodes[1].id = permuted[1];
  95     update.nodes[1].state = AX_STATE_NONE;
  96   }
  97
  98   // The remaining nodes are assigned based on their parent
  99   // selected from the next bits from |tree_index|.
 100   for (int i = 2; i < node_count; ++i) {
 101     update.nodes[i].id = permuted[i];
 102     update.nodes[i].state = AX_STATE_NONE;
 103     int parent_index = (tree_index % i);
 104     tree_index /= i;
 105     update.nodes[parent_index].child_ids.push_back(permuted[i]);
 106   }
 107
 108   // Unserialize the tree update into the destination tree.
 109   CHECK(out_tree->Unserialize(update)) << out_tree->error();
 110 };
 111
 112 }  // namespace ui