Add a UniqueVector class to GN

tools/gn/uniquify_unittest.cc

+// Copyright (c) 2013 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 <algorithm>
+
+#include "base/time/time.h"
+#include "testing/gtest/include/gtest/gtest.h"
+#include "tools/gn/uniquify.h"
+
+namespace {
+
+template<typename T>
+bool RunTest(const std::vector<T>& input, const std::vector<T>& expected) {
+  std::vector<T> result = input;
+  UniquifyBruteForce(&result);
+  if (result.size() != expected.size())
+    return false;
+  if (!std::equal(result.begin(), result.end(), expected.begin()))
+    return false;
+
+  result = input;
+  UniquifyHash(&result);
+  if (result.size() != expected.size())
+    return false;
+  if (!std::equal(result.begin(), result.end(), expected.begin()))
+    return false;
+
+  return true;
+}
+
+}  // namespace
+
+TEST(Uniquify, Empty) {
+  std::vector<int> empty;
+  EXPECT_TRUE(RunTest(empty, empty));
+}
+
+TEST(Uniquify, OneElt) {
+  std::vector<void*> one;
+  one.push_back(&one);
+  EXPECT_TRUE(RunTest(one, one));
+}
+
+TEST(Uniquify, AllSame) {
+  std::vector<void*> input;
+  for (int i = 0; i < 100; i++)
+    input.push_back(&input);
+  std::vector<void*> expected;
+  expected.push_back(&input);
+  EXPECT_TRUE(RunTest(input, expected));
+}
+
+TEST(Uniquify, AllUnique) {
+  std::vector<int> vals;
+  for (int i = 0; i < 100; i++)
+    vals.push_back(i);
+  EXPECT_TRUE(RunTest(vals, vals));
+}
+
+TEST(Uniquify, Various) {
+  std::vector<int> input;
+  input.push_back(0);
+  input.push_back(1);
+  input.push_back(2);
+  input.push_back(1);
+  input.push_back(1);
+  input.push_back(0);
+  input.push_back(7);
+  input.push_back(0);
+
+  std::vector<int> output;
+  output.push_back(0);
+  output.push_back(1);
+  output.push_back(2);
+  output.push_back(7);
+  EXPECT_TRUE(RunTest(input, output));
+}
+
+/* Performance test for measuring relative performance of brute-force and

[viettrungluu, 2013/10/08 23:39:41]

I wish it were easier to add perf tests (and monitoring of perf tests) to the
bots and such.

Arguably, this should be in a separate perf test target, and kept compiling at
least. <shrug>

+   hashing for strings over containers of different lengths. This was used
+   to pick the array size below which brute-force is faster.
+TEST(Uniquify, Perf) {
+  // Length of the strings we're using.
+  const size_t kStrLen = 32;
+
+  // This loop tries input vectors of different lengths.
+  for (size_t vec_len = 1; vec_len < 256; vec_len += 2) {
+    std::vector<std::string> strs;
+    for (size_t cur_str_i = 0; cur_str_i < vec_len; cur_str_i++) {
+      // Make a unique string.
+      std::string str;
+      str.push_back(static_cast<char>(cur_str_i % 255));
+      str.push_back(static_cast<char>(cur_str_i / 255));
+      for (size_t str_i = 1; str_i < kStrLen; str_i++)
+        str.push_back('a');
+      strs.push_back(str);
+    }
+
+    const size_t kIters = 1000;  // Number of times to run algorithm.
+    base::TimeTicks brute_begin = base::TimeTicks::Now();
+    for (size_t i = 0; i < kIters; i++)
+      UniquifyBruteForce(&strs);
+    base::TimeTicks mid = base::TimeTicks::Now();
+    for (size_t i = 0; i < kIters; i++)
+      UniquifyHash(&strs);
+    base::TimeTicks end = base::TimeTicks::Now();
+
+    printf("%d: brute = %f, hash = %f\n",
+           vec_len,
+           (mid - brute_begin).InMillisecondsF(),
+           (end - mid).InMillisecondsF());
+  }
+}
+*/