// RUN: %target-run-simple-swift | %FileCheck %s
// REQUIRES: executable_test

// Generate all possible permutes.
func _permuteInternal(
  _ elem: Int, _ size: Int,
  _ perm: inout [Int], _ visited: inout [Bool],
  _ verify: ([Int]) -> Void
) {
  if (elem == size) {
    verify(perm)
    return
  }

  for i in 0..<size {
    if (visited[i]) {
      continue
    }
    visited[i] = true
    perm[elem] = i
    _permuteInternal(elem + 1, size, &perm, &visited, verify)
    visited[i] = false
  }
}

// Convenience wrapper for the permute method.
func permute(_ size: Int, _ verify: ([Int]) -> Void) {
  var perm = [Int](repeating: 0, count: size)
  var visited = [Bool](repeating: false, count: size)
  _permuteInternal(0, size, &perm, &visited, verify)
}


// A simple random number generator.
func randomize(_ size: Int, _ verify: ([Int]) -> Void) {
  var arr : [Int] = []
  var N = 1
  var M = 1
  for _ in 0..<size {
    N = N * 19 % 1024
    M = (N + M) % size
    arr.append(N)
    if (M % 3 == 0) {
      arr.append(M)
    }
  }
  verify(arr)
}

// Verify the permute method itself:
let printer: ([Int]) -> Void = {
  var output = ""
  var prefix = ""
  for x in $0 {
    output += "\(prefix)\(x)"
    prefix = ", "
  }
  print("[\(output)]")
}
//CHECK: [0, 1, 2]
//CHECK: [0, 2, 1]
//CHECK: [1, 0, 2]
//CHECK: [1, 2, 0]
//CHECK: [2, 0, 1]
//CHECK: [2, 1, 0]
permute(3, printer)

let sort_verifier: ([Int]) -> Void = {
    var y = $0.sorted()
    for i in 0..<y.count - 1 {
    if (y[i] > y[i+1]) {
        print("Error: \(y)")
        return
      }
    }
}

//CHECK-NOT: Error!
permute(2, sort_verifier)
permute(6, sort_verifier)
permute(7, sort_verifier)
//CHECK: Test1 - Done
print("Test1 - Done")

let partition_verifier: ([Int]) -> Void = {
    var y = $0
    // partition(by:) returns the index to the pivot value.
    let first = y.first
    let idx = y.partition(by: { $0 >= first! })

    // Check that all of the elements in the first partition are smaller than
    // the pivot value.
    for i in 0..<idx {
      if y[i] >= first! {
        print("Error!")
        return
      }
    }
    // Check that all of the elements in the second partition are greater or
    // equal to the pivot value.
    for i in idx..<y.count - 1 {
      if y[i] < first! {
        print("Error!")
        return
      }
    }
}

// FIXME(prext): remove partition() together with the function when
// protocol extensions land.  These tests have been migrated to the new API.
permute(2, partition_verifier)
permute(6, partition_verifier)
permute(7, partition_verifier)
//CHECK-NOT: Error!
//CHECK: Test2 - Done
print("Test2 - Done")


randomize(70, sort_verifier)
randomize(700, sort_verifier)
randomize(1900, sort_verifier)
//CHECK-NOT: Error!
//CHECK: Test3 - Done
print("Test3 - Done")