1 files changed, 97 insertions, 0 deletions
diff --git a/include/frozen/random.h b/include/frozen/random.h
new file mode 100644
index 0000000..727133b
--- /dev/null
+++ b/include/frozen/random.h
@@ -0,0 +1,97 @@
+/*
+ * Frozen
+ * Copyright 2016 QuarksLab
+ *
+ * Licensed to the Apache Software Foundation (ASF) under one
+ * or more contributor license agreements.  See the NOTICE file
+ * distributed with this work for additional information
+ * regarding copyright ownership.  The ASF licenses this file
+ * to you under the Apache License, Version 2.0 (the
+ * "License"); you may not use this file except in compliance
+ * with the License.  You may obtain a copy of the License at
+ *
+ *   http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing,
+ * software distributed under the License is distributed on an
+ * "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
+ * KIND, either express or implied.  See the License for the
+ * specific language governing permissions and limitations
+ * under the License.
+ */
+
+#ifndef FROZEN_LETITGO_RANDOM_H
+#define FROZEN_LETITGO_RANDOM_H
+
+#include "frozen/bits/algorithms.h"
+#include "frozen/bits/version.h"
+
+#include <cstdint>
+#include <type_traits>
+
+namespace frozen {
+template <class UIntType, UIntType a, UIntType c, UIntType m>
+class linear_congruential_engine {
+
+  static_assert(std::is_unsigned<UIntType>::value,
+                "UIntType must be an unsigned integral type");
+
+  template<class T>
+  static constexpr UIntType modulo(T val, std::integral_constant<UIntType, 0>) {
+    return static_cast<UIntType>(val);
+  }
+
+  template<class T, UIntType M>
+  static constexpr UIntType modulo(T val, std::integral_constant<UIntType, M>) {
+    // the static cast below may end up doing a truncation
+    return static_cast<UIntType>(val % M);
+  }
+
+public:
+  using result_type = UIntType;
+  static constexpr result_type multiplier = a;
+  static constexpr result_type increment = c;
+  static constexpr result_type modulus = m;
+  static constexpr result_type default_seed = 1u;
+
+  linear_congruential_engine() = default;
+  constexpr linear_congruential_engine(result_type s) { seed(s); }
+
+  void seed(result_type s = default_seed) { state_ = s; }
+  constexpr result_type operator()() {
+	  using uint_least_t = bits::select_uint_least_t<bits::log(a) + bits::log(m) + 4>;
+    uint_least_t tmp = static_cast<uint_least_t>(multiplier) * state_ + increment;
+
+    state_ = modulo(tmp, std::integral_constant<UIntType, modulus>());
+    return state_;
+  }
+  constexpr void discard(unsigned long long n) {
+    while (n--)
+      operator()();
+  }
+  static constexpr result_type min() { return increment == 0u ? 1u : 0u; }
+  static constexpr result_type max() { return modulus - 1u; }
+  friend constexpr bool operator==(linear_congruential_engine const &self,
+                                   linear_congruential_engine const &other) {
+    return self.state_ == other.state_;
+  }
+  friend constexpr bool operator!=(linear_congruential_engine const &self,
+                                   linear_congruential_engine const &other) {
+    return !(self == other);
+  }
+
+private:
+  result_type state_ = default_seed;
+};
+
+using minstd_rand0 =
+    linear_congruential_engine<std::uint_fast32_t, 16807, 0, 2147483647>;
+using minstd_rand =
+    linear_congruential_engine<std::uint_fast32_t, 48271, 0, 2147483647>;
+
+// This generator is used by default in unordered frozen containers
+using default_prg_t = minstd_rand;
+
+} // namespace frozen
+
+#endif