metrics: Add RandomSelector, a class that randomly selects items with odds

chrome/browser/metrics/random_selector.cc

+// Copyright 2015 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 "chrome/browser/metrics/random_selector.h"

[Alexei Svitkine (slow), 2015/09/11 21:00:54]

I'm not convinced of this living in chrome/browser/metrics. This directory is
already pretty crowded.

However, I see that the code that will be using it - perf_provider.cc - is in
the same directory. How about making a new-subdirectory under
chrome/browser/metrics - chrome/browser/metrics/perf/ and moving all of these
files there? (Probably in a separate CL that can land before this one.)

[dhsharp, 2015/09/11 22:53:25]

Works for me. Will work on that. (Not sure if you noticed I raised this question
in my review email.)

+
+#include <string>
+#include <vector>
+
+#include <base/logging.h>

[Alexei Svitkine (slow), 2015/09/11 21:00:54]

Nit: "'s for project includes.

[dhsharp, 2015/09/11 22:53:25]

Oops. Done.

+#include <base/rand_util.h>
+#include <base/strings/string_number_conversions.h>
+#include <base/strings/string_split.h>
+#include <base/strings/string_util.h>
+
+namespace metrics {
+
+RandomSelector::RandomSelector() {}
+
+RandomSelector::~RandomSelector() {}
+
+double RandomSelector::SumOdds(const std::vector<OddsAndValue>& odds) {
+  double sum = 0.0;
+  for (const auto& odd : odds) {
+    sum += odd.weight;
+  }
+  return sum;
+}
+
+void RandomSelector::SetOdds(const std::vector<OddsAndValue>& odds) {
+  odds_ = odds;
+  sum_of_odds_ = SumOdds(odds_);
+}
+
+const std::vector<std::string>& RandomSelector::GetNext() {
+  // Get a random double between 0 and the sum.
+  double random = RandDoubleUpTo(sum_of_odds_);
+  // Figure out what it belongs to.
+  return GetKeyOf(random);
+}
+
+double RandomSelector::RandDoubleUpTo(double max) {
+  CHECK_GT(max, 0.0);
+  return max * base::RandDouble();
+}
+
+const std::vector<std::string>& RandomSelector::GetKeyOf(double value) {
+  double current = 0.0;
+  for (const auto& odd : odds_) {
+    current += odd.weight;
+    if (value < current) {
+      return odd.value;
+    }
+  }
+  NOTREACHED() << "Invalid value for key: " << value;
+  static const std::vector<std::string> kEmptyVector;
+  return kEmptyVector;
+}
+
+}  // namespace metrics