// RUN: %target-run-stdlib-swift
// REQUIRES: executable_test

import StdlibUnittest
import StdlibCollectionUnittest
import SwiftShims // for swift_stdlib_random

let RandomTests = TestSuite("Random")

// _fill(bytes:)

extension RandomNumberGenerator {
  func _fill(bytes buffer: UnsafeMutableRawBufferPointer) {
    guard let start = buffer.baseAddress else { return }
    swift_stdlib_random(start, buffer.count)
  }
}

RandomTests.test("_fill(bytes:)") {
  for count in [100, 1000] {
    var bytes1 = [UInt8](repeating: 0, count: count)
    var bytes2 = [UInt8](repeating: 0, count: count)
    let zeros = [UInt8](repeating: 0, count: count)
    expectEqual(bytes1, bytes2)
    expectEqual(bytes1, zeros)
    expectEqual(bytes2, zeros)
    
    var g = SystemRandomNumberGenerator()
    bytes1.withUnsafeMutableBytes { g._fill(bytes: $0) }
    expectNotEqual(bytes1, bytes2)
    expectNotEqual(bytes1, zeros)
    
    bytes2.withUnsafeMutableBytes { g._fill(bytes: $0) }
    expectNotEqual(bytes1, bytes2)
    expectNotEqual(bytes2, zeros)
  }
}

// Basic random numbers

RandomTests.test("basic random numbers") {
  let randomNumber1 = Int.random(in: .min ... .max)
  let randomNumber2 = Int.random(in: .min ... .max)
  expectNotEqual(randomNumber1, randomNumber2)

  let randomDouble1 = Double.random(in: 0 ..< 1)
  expectTrue(randomDouble1 < 1 && randomDouble1 >= 0)
  let randomDouble2 = Double.random(in: 0 ..< 1)
  expectTrue(randomDouble2 < 1 && randomDouble2 >= 0)
  expectNotEqual(randomDouble1, randomDouble2)
}

// Random integers in ranges

func integerRangeTest<T: FixedWidthInteger>(_ type: T.Type) {
    
  func testRange(_ range: Range<T>, iterations: Int = 1_000) {
    var integerSet: Set<T> = []
    for _ in 0 ..< iterations {
      let random = T.random(in: range)
      expectTrue(range.contains(random))
      integerSet.insert(random)
    }
    expectEqual(integerSet, Set(range))
  }
    
  func testClosedRange(_ range: ClosedRange<T>, iterations: Int = 1_000) {
    var integerSet: Set<T> = []
    for _ in 0 ..< iterations {
      let random = T.random(in: range)
      expectTrue(range.contains(random))
      integerSet.insert(random)
    }
    expectEqual(integerSet, Set(range))
  }
  
  // min open range
  testRange(T.min ..< (T.min + 10))
  
  // min closed range
  testClosedRange(T.min ... (T.min + 10))
  
  // max open range
  testRange((T.max - 10) ..< T.max)
  
  // max closed range
  testClosedRange((T.max - 10) ... T.max)
  
  // Test full ranges for Int8 and UInt8
  if T.bitWidth == 8 {
    let fullIterations = 10_000
    
    // full open range
    testRange(T.min ..< T.max, iterations: fullIterations)
    
    // full closed range
    testClosedRange(T.min ... T.max, iterations: fullIterations)
  }
}

RandomTests.test("random integers in ranges") {
  integerRangeTest(Int8.self)
  integerRangeTest(Int16.self)
  integerRangeTest(Int32.self)
  integerRangeTest(Int64.self)
  integerRangeTest(UInt8.self)
  integerRangeTest(UInt16.self)
  integerRangeTest(UInt32.self)
  integerRangeTest(UInt64.self)
}

// Random floating points in ranges

func floatingPointRangeTest<T: BinaryFloatingPoint>(_ type: T.Type) 
  where T.RawSignificand: FixedWidthInteger {
  
  let testRange = 0 ..< 1_000
  
  // open range
  let openRange: Range<T> = 0.0 ..< 10.0
  for _ in testRange {
    let random = T.random(in: openRange)
    expectTrue(openRange.contains(random))
  }
  
  // closed range
  let closedRange: ClosedRange<T> = 0.0 ... 10.0
  for _ in testRange {
    let random = T.random(in: closedRange)
    expectTrue(closedRange.contains(random))
  }
}

RandomTests.test("random floating points in ranges") {
  floatingPointRangeTest(Float.self)
  floatingPointRangeTest(Double.self)
#if !os(Windows) && (arch(i386) || arch(x86_64))
  floatingPointRangeTest(Float80.self)
#endif
}

// Random Elements from collection

RandomTests.test("random elements from collection") {
  // Non-empty collection
  var elementSet: Set<String> = []
  let greetings = ["hello", "hi", "hey", "hola", "what's up"]
  for _ in 0 ..< 1_000 {
    let randomGreeting = greetings.randomElement()
    expectNotNil(randomGreeting)
    expectTrue(greetings.contains(randomGreeting!))
    elementSet.insert(randomGreeting!)
  }
  expectEqual(elementSet, Set(greetings))
  
  // Empty collection
  let emptyArray: [String] = []
  for _ in 0 ..< 1_000 {
    let randomElement = emptyArray.randomElement()
    expectNil(randomElement)
  }
}

// Shuffle

RandomTests.test("shuffling") {
  let alphabet = ["a", "b", "c", "d", "e", "f", "g", "h", "i", "j", "k", "l",
                  "m", "n", "o", "p", "q", "r", "s", "t", "u", "v", "w", "x",
                  "y", "z"]
  var oldAlphabet = MinimalSequence(elements: alphabet)
  for _ in 0 ..< 1_000 {
    let newAlphabet = alphabet.shuffled()
    expectTrue(alphabet.elementsEqual(newAlphabet.sorted()))
    expectFalse(oldAlphabet.elementsEqual(newAlphabet))
    oldAlphabet = MinimalSequence(elements: newAlphabet)
  }
}

// Different RNGS

public struct LCRNG: RandomNumberGenerator {
  private var state: UInt64
  private static let m: UInt64 = 1 << 48
  private static let a: UInt64 = 25214903917
  private static let c: UInt64 = 11

  public init(seed: UInt64) {
    self.state = seed
  }
  
  private mutating func next() -> UInt32 {
    state = (LCRNG.a &* state &+ LCRNG.c) % LCRNG.m
    return UInt32(truncatingIfNeeded: state >> 15)
  }
  
  public mutating func next() -> UInt64 {
    return UInt64(next() as UInt32) << 32 | UInt64(next() as UInt32)
  }
}

RandomTests.test("different random number generators") {
  // 0 = first pass array, 1 = second pass array
  var intPasses: [[Int]] = [[], []]
  var doublePasses: [[Double]] = [[], []]
  var boolPasses: [[Bool]] = [[], []]
  var collectionPasses: [[Int]] = [[], []]
  var shufflePasses: [[[Int]]] = [[], []]
  
  for i in 0 ..< 2 {
    let seed: UInt64 = 1234567890
    var rng = LCRNG(seed: seed)
    
    for _ in 0 ..< 1_000 {
      let randomInt = Int.random(in: 0 ... 100, using: &rng)
      intPasses[i].append(randomInt)
      
      let randomDouble = Double.random(in: 0 ..< 1, using: &rng)
      doublePasses[i].append(randomDouble)
      
      let randomBool = Bool.random(using: &rng)
      boolPasses[i].append(randomBool)
      
      let randomIntFromCollection = Array(0 ... 100).randomElement(using: &rng)
      expectNotNil(randomIntFromCollection)
      collectionPasses[i].append(randomIntFromCollection!)
      
      let randomShuffledCollection = Array(0 ... 100).shuffled(using: &rng)
      shufflePasses[i].append(randomShuffledCollection)
    }
  }
  
  expectEqual(intPasses[0], intPasses[1])
  expectEqual(doublePasses[0], doublePasses[1])
  expectEqual(boolPasses[0], boolPasses[1])
  expectEqual(collectionPasses[0], collectionPasses[1])
  expectEqual(shufflePasses[0], shufflePasses[1])
}

// Random floating points with max values (SR-8178)

var lcrng = LCRNG(seed: 1234567890)

public struct RotatingRNG: RandomNumberGenerator {
  public let rotation: [() -> UInt64] = [
    { return .min },
    { return .max },
    { return lcrng.next() }
  ]
  public var rotationIndex = 0
  
  public mutating func next() -> UInt64 {
    if rotationIndex == rotation.count {
      rotationIndex = 0
    }
    
    defer {
      rotationIndex += 1
    }
    
    return rotation[rotationIndex]()
  }
}

func floatingPointRangeMaxTest<T: BinaryFloatingPoint>(_ type: T.Type)
  where T.RawSignificand: FixedWidthInteger {
  
  let testRange = 0 ..< 1_000
  
  var rng = RotatingRNG()
  let ranges: [Range<T>] = [0 ..< 1, 1 ..< 2, 10 ..< 11, 0 ..< 10]
  for range in ranges {
    for _ in testRange {
      let random = T.random(in: range, using: &rng)
      expectTrue(range.contains(random))
      expectTrue(range.lowerBound <= random)
      expectTrue(random < range.upperBound)
    }
  }
}

RandomTests.test("random floating point range maxes") {
  floatingPointRangeMaxTest(Float.self)
  floatingPointRangeMaxTest(Double.self)
#if !os(Windows) && (arch(i386) || arch(x86_64))
  floatingPointRangeMaxTest(Float80.self)
#endif
}

// Uniform Distribution

func chi2Test(_ samples: [Double]) -> Bool {
  precondition(samples.count == 50, "confidence interval requires 50 samples")
  let expected = samples.reduce(0, +) / Double(samples.count)
  // Right tail for 0.0001% (1e-6) with a degree of freedom of (50 -
  // 1).  With hundreds of builds a day, this has to be very low to not get too
  // many spurious failures, but obvious problems should still be detected
  // (e.g. an off-by-one that means samples[0] == 0 will result in chi2 =
  // (0-expected)**2/expected + ... > expected, so as long as we've generated
  // more than samples.count * cvHigh (~5500) values, we'll catch it).
  let cvHigh = 111.1
  let chi2 = samples.map {
    (($0 - expected) * ($0 - expected)) / expected
  }.reduce(0, +)

  if chi2 > cvHigh {
    return false
  } else {
    return true
  }
}

RandomTests.test("uniform distribution") {
  let upperBound = 50
  let numberOfTrials = 500_000
  var array = [Double](repeating: 0.0, count: upperBound)
  for _ in 0 ..< numberOfTrials {
    let randomIndex = Int.random(in: 0 ..< upperBound)
    array[randomIndex] += 1.0
  }
  
  expectTrue(chi2Test(array))
}

runAllTests()