Improve AXTree unit tests.

ui/accessibility/tree_generator.cc

 // Copyright 2014 The Chromium Authors. All rights reserved.
 // Use of this source code is governed by a BSD-style license that can be
 // found in the LICENSE file.
 
 #include "ui/accessibility/tree_generator.h"
 
 #include "ui/accessibility/ax_serializable_tree.h"
 #include "ui/accessibility/ax_tree.h"
 
 namespace ui {
 
-TreeGenerator::TreeGenerator(int node_count)
-    : node_count_(node_count), unique_tree_count_(1) {
+static int UniqueTreeCountForNodeCount(int node_count,
+                                       bool permutations) {
+  int unique_tree_count = 1;
+
   // (n-1)! for the possible trees.
-  for (int i = 2; i < node_count_; i++)
-    unique_tree_count_ *= i;
+  for (int i = 2; i < node_count; ++i)
+    unique_tree_count *= i;
+
   // n! for the permutations of ids.
-  for (int i = 2; i <= node_count_; i++)
-    unique_tree_count_ *= i;
-};
+  if (permutations)
+    unique_tree_count = unique_tree_count * unique_tree_count * node_count;
+
+  return unique_tree_count;
+}
+
+TreeGenerator::TreeGenerator(int max_node_count, bool permutations)
+    : max_node_count_(max_node_count),
+      permutations_(permutations),
+      total_unique_tree_count_(0) {
+  unique_tree_count_by_size_.push_back(0);
+  for (int i = 1; i <= max_node_count; ++i) {
+    int unique_tree_count = UniqueTreeCountForNodeCount(i, permutations);
+    unique_tree_count_by_size_.push_back(unique_tree_count);
+    total_unique_tree_count_ += unique_tree_count;
+  }
+}
+
+TreeGenerator::~TreeGenerator() {
+}
 
 int TreeGenerator::UniqueTreeCount() const {
-  return unique_tree_count_;
-};
+  return total_unique_tree_count_;
+}
 
 void TreeGenerator::BuildUniqueTree(int tree_index, AXTree* out_tree) const {
+  CHECK_LT(tree_index, total_unique_tree_count_);
+
+  int unique_tree_count_so_far = 0;
+  for (int node_count = 1; node_count <= max_node_count_; ++node_count) {
+    int unique_tree_count = unique_tree_count_by_size_[node_count];
+    if (tree_index - unique_tree_count_so_far < unique_tree_count) {
+      BuildUniqueTreeWithSize(node_count,
+                              tree_index - unique_tree_count_so_far,
+                              out_tree);
+      return;
+    }
+    unique_tree_count_so_far += unique_tree_count;
+  }
+}
+
+void TreeGenerator::BuildUniqueTreeWithSize(
+    int node_count, int tree_index, AXTree* out_tree) const {
   std::vector<int> indices;
   std::vector<int> permuted;
-  CHECK(tree_index <= unique_tree_count_);
+  int unique_tree_count = unique_tree_count_by_size_[node_count];
+  CHECK_LT(tree_index, unique_tree_count);
 
-  // Use the first few bits of |tree_index| to permute the indices.
-  for (int i = 0; i < node_count_; i++)
-    indices.push_back(i + 1);
-  for (int i = 0; i < node_count_; i++) {
-    int p = (node_count_ - i);
-    int index = tree_index % p;
-    tree_index /= p;
-    permuted.push_back(indices[index]);
-    indices.erase(indices.begin() + index);
+  if (permutations_) {
+    // Use the first few bits of |tree_index| to permute the indices.
+    for (int i = 0; i < node_count; ++i)
+      indices.push_back(i + 1);
+    for (int i = 0; i < node_count; ++i) {
+      int p = (node_count - i);
+      int index = tree_index % p;
+      tree_index /= p;
+      permuted.push_back(indices[index]);
+      indices.erase(indices.begin() + index);
+    }
+  } else {
+    for (int i = 0; i < node_count; ++i)
+      permuted.push_back(i + 1);
   }
 
   // Build an AXTreeUpdate. The first two nodes of the tree always
   // go in the same place.
   AXTreeUpdate update;
-  update.nodes.resize(node_count_);
+  update.nodes.resize(node_count);
   update.nodes[0].id = permuted[0];
   update.nodes[0].role = AX_ROLE_ROOT_WEB_AREA;
   update.nodes[0].state = AX_STATE_NONE;
-  update.nodes[0].child_ids.push_back(permuted[1]);
-  update.nodes[1].id = permuted[1];
-  update.nodes[1].state = AX_STATE_NONE;
+  if (node_count > 1) {
+    update.nodes[0].child_ids.push_back(permuted[1]);
+    update.nodes[1].id = permuted[1];
+    update.nodes[1].state = AX_STATE_NONE;
+  }
 
   // The remaining nodes are assigned based on their parent
   // selected from the next bits from |tree_index|.
-  for (int i = 2; i < node_count_; i++) {
+  for (int i = 2; i < node_count; ++i) {
     update.nodes[i].id = permuted[i];
     update.nodes[i].state = AX_STATE_NONE;
     int parent_index = (tree_index % i);
     tree_index /= i;
     update.nodes[parent_index].child_ids.push_back(permuted[i]);
   }
 
   // Unserialize the tree update into the destination tree.
   CHECK(out_tree->Unserialize(update)) << out_tree->error();
 };
 
 }  // namespace ui