Moving RandomSample to base.

3 files changed, 33 insertions, 0 deletions

diff --git a/base/base.pro b/base/base.pro
index 7eda31055f..71073004a6 100644
--- a/base/base.pro
+++ b/base/base.pro
@@ -18,6 +18,7 @@ SOURCES += \
     logging.cpp \
     lower_case.cpp \
     normalize_unicode.cpp \
+    random.cpp \
     shared_buffer_manager.cpp \
     src_point.cpp \
     string_format.cpp \
@@ -59,6 +60,7 @@ HEADERS += \
     mutex.hpp \
     newtype.hpp \
     observer_list.hpp \
+    random.hpp \
     range_iterator.hpp \
     ref_counted.hpp \
     regexp.hpp \
diff --git a/base/random.cpp b/base/random.cpp
new file mode 100644
index 0000000000..a6decf8498
--- /dev/null
+++ b/base/random.cpp
@@ -0,0 +1,22 @@
+#include "base/random.hpp"
+
+#include <algorithm>
+#include <numeric>
+
+namespace my
+{
+std::vector<size_t> RandomSample(size_t n, size_t k, std::minstd_rand & rng)
+{
+  std::vector<size_t> result(std::min(k, n));
+  std::iota(result.begin(), result.end(), 0);
+
+  for (size_t i = k; i < n; ++i)
+  {
+    size_t const j = rng() % (i + 1);
+    if (j < k)
+      result[j] = i;
+  }
+
+  return result;
+}
+}  // my
diff --git a/base/random.hpp b/base/random.hpp
new file mode 100644
index 0000000000..b17189e36c
--- /dev/null
+++ b/base/random.hpp
@@ -0,0 +1,9 @@
+#pragma once
+
+#include <random>
+#include <vector>
+
+namespace my
+{
+std::vector<size_t> RandomSample(size_t n, size_t k, std::minstd_rand & rng);
+}  // my