Algorithm.swift

// -*- swift -*-
// RUN: %target-run-simple-swift
// REQUIRES: executable_test

import StdlibUnittest
import StdlibCollectionUnittest
import SwiftPrivate


var Algorithm = TestSuite("Algorithm")

// FIXME(prext): remove this conformance.
extension String.UnicodeScalarView : Equatable {}

// FIXME(prext): remove this function.
public func == (
  lhs: String.UnicodeScalarView, rhs: String.UnicodeScalarView) -> Bool {
  return Array(lhs) == Array(rhs)
}

// FIXME(prext): move this struct to the point of use.
Algorithm.test("min,max") {
  // Identities are unique in this set.
  let a1 = MinimalComparableValue(0, identity: 1)
  let a2 = MinimalComparableValue(0, identity: 2)
  let a3 = MinimalComparableValue(0, identity: 3)
  let b1 = MinimalComparableValue(1, identity: 4)
  let b2 = MinimalComparableValue(1, identity: 5)
  let b3 = MinimalComparableValue(1, identity: 6)
  let c1 = MinimalComparableValue(2, identity: 7)
  let c2 = MinimalComparableValue(2, identity: 8)
  let c3 = MinimalComparableValue(2, identity: 9)

  // 2-arg min()
  expectEqual(a1.identity, min(a1, b1).identity)
  expectEqual(a1.identity, min(b1, a1).identity)
  expectEqual(a1.identity, min(a1, a2).identity)

  // 2-arg max()
  expectEqual(c1.identity, max(c1, b1).identity)
  expectEqual(c1.identity, max(b1, c1).identity)
  expectEqual(c1.identity, max(c2, c1).identity)

  // 3-arg min()
  expectEqual(a1.identity, min(a1, b1, c1).identity)
  expectEqual(a1.identity, min(b1, a1, c1).identity)
  expectEqual(a1.identity, min(c1, b1, a1).identity)
  expectEqual(a1.identity, min(c1, a1, b1).identity)
  expectEqual(a1.identity, min(a1, a2, a3).identity)
  expectEqual(a1.identity, min(a1, a2, b1).identity)
  expectEqual(a1.identity, min(a1, b1, a2).identity)
  expectEqual(a1.identity, min(b1, a1, a2).identity)
 
  // 3-arg max()
  expectEqual(c1.identity, max(c1, b1, a1).identity)
  expectEqual(c1.identity, max(a1, c1, b1).identity)
  expectEqual(c1.identity, max(b1, a1, c1).identity)
  expectEqual(c1.identity, max(b1, c1, a1).identity)
  expectEqual(c1.identity, max(c3, c2, c1).identity)
  expectEqual(c1.identity, max(c2, c1, b1).identity)
  expectEqual(c1.identity, max(c2, b1, c1).identity)
  expectEqual(c1.identity, max(b1, c2, c1).identity)
  
  // 4-arg min()
  expectEqual(a1.identity, min(a1, b1, a2, b2).identity)
  expectEqual(a1.identity, min(b1, a1, a2, b2).identity)
  expectEqual(a1.identity, min(c1, b1, b2, a1).identity)
  expectEqual(a1.identity, min(c1, b1, a1, a2).identity)
  
  // 4-arg max()
  expectEqual(c1.identity, max(c2, b1, c1, b2).identity)
  expectEqual(c1.identity, max(b1, c2, c1, b2).identity)
  expectEqual(c1.identity, max(a1, b1, b2, c1).identity)
  expectEqual(c1.identity, max(a1, b1, c2, c1).identity)
}

Algorithm.test("sorted/strings") {
  expectEqual(
    ["Banana", "apple", "cherry"],
    ["apple", "Banana", "cherry"].sorted())

  let s = ["apple", "Banana", "cherry"].sorted() {
    $0.characters.count > $1.characters.count
  }
  expectEqual(["Banana", "cherry", "apple"], s)
}

// A wrapper around Array<T> that disables any type-specific algorithm
// optimizations and forces bounds checking on.
struct A<T> : MutableCollection, RandomAccessCollection {
  typealias Indices = CountableRange<Int>

  init(_ a: Array<T>) {
    impl = a
  }

  var startIndex: Int {
    return 0
  }

  var endIndex: Int {
    return impl.count
  }

  func makeIterator() -> Array<T>.Iterator {
    return impl.makeIterator()
  }

  subscript(i: Int) -> T {
    get {
      expectTrue(i >= 0 && i < impl.count)
      return impl[i]
    }
    set (x) {
      expectTrue(i >= 0 && i < impl.count)
      impl[i] = x
    }
  }

  subscript(r: Range<Int>) -> Array<T>.SubSequence {
    get {
      expectTrue(r.lowerBound >= 0 && r.lowerBound <= impl.count)
      expectTrue(r.upperBound >= 0 && r.upperBound <= impl.count)
      return impl[r]
    }
    set (x) {
      expectTrue(r.lowerBound >= 0 && r.lowerBound <= impl.count)
      expectTrue(r.upperBound >= 0 && r.upperBound <= impl.count)
      impl[r] = x
    }
  }

  var impl: Array<T>
}

func randomArray() -> A<Int> {
  let count = Int(rand32(exclusiveUpperBound: 50))
  return A(randArray(count))
}

Algorithm.test("invalidOrderings") {
  withInvalidOrderings {
    var a = randomArray()
    _blackHole(a.sorted(by: $0))
  }
  withInvalidOrderings {
    var a: A<Int>
    a = randomArray()
    let lt = $0
    let first = a.first
    _ = a.partition(by: { !lt($0, first!) })
  }
  /*
  // FIXME: Disabled due to <rdar://problem/17734737> Unimplemented:
  // abstraction difference in l-value
  withInvalidOrderings {
    var a = randomArray()
    var pred = $0
    _insertionSort(&a, a.indices, &pred)
  }
  */
}

// The routine is based on http://www.cs.dartmouth.edu/~doug/mdmspe.pdf
func makeQSortKiller(_ len: Int) -> [Int] {
  var candidate: Int = 0
  var keys = [Int: Int]()
  func Compare(_ x: Int, y : Int) -> Bool {
    if keys[x] == nil && keys[y] == nil {
      if (x == candidate) {
        keys[x] = keys.count
      } else {
        keys[y] = keys.count
      }
    }
    if keys[x] == nil {
      candidate = x
      return true
    }
    if keys[y] == nil {
      candidate = y
      return false
    }
    return keys[x]! > keys[y]!
  }

  var ary = [Int](repeating: 0, count: len)
  var ret = [Int](repeating: 0, count: len)
  for i in 0..<len { ary[i] = i }
  ary = ary.sorted(by: Compare)
  for i in 0..<len {
    ret[ary[i]] = i
  }
  return ret
}

Algorithm.test("sorted/complexity") {
  var ary: [Int] = []

  // Check performance of sorting an array of repeating values.
  var comparisons_100 = 0
  ary = [Int](repeating: 0, count: 100)
  ary.sort { comparisons_100 += 1; return $0 < $1 }
  var comparisons_1000 = 0
  ary = [Int](repeating: 0, count: 1000)
  ary.sort { comparisons_1000 += 1; return $0 < $1 }
  expectTrue(comparisons_1000/comparisons_100 < 20)

  // Try to construct 'bad' case for quicksort, on which the algorithm
  // goes quadratic.
  comparisons_100 = 0
  ary = makeQSortKiller(100)
  ary.sort { comparisons_100 += 1; return $0 < $1 }
  comparisons_1000 = 0
  ary = makeQSortKiller(1000)
  ary.sort { comparisons_1000 += 1; return $0 < $1 }
  expectTrue(comparisons_1000/comparisons_100 < 20)
}

Algorithm.test("sorted/return type") {
  let x: Array = ([5, 4, 3, 2, 1] as ArraySlice).sorted()
}

Algorithm.test("sort3/simple")
  .forEach(in: [
    [1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]
  ]) {
    var input = $0
    _sort3(&input, 0, 1, 2)
    expectEqual([1, 2, 3], input)
}

func isSorted<T>(_ a: [T], by areInIncreasingOrder: (T, T) -> Bool) -> Bool {
  return !a.dropFirst().enumerated().contains(where: { (offset, element) in
    areInIncreasingOrder(element, a[offset])
  })
}

Algorithm.test("sort3/stable")
  .forEach(in: [
    [1, 1, 2], [1, 2, 1], [2, 1, 1], [1, 2, 2], [2, 1, 2], [2, 2, 1], [1, 1, 1]
  ]) {
    // decorate with offset, but sort by value
    var input = Array($0.enumerated())
    _sort3(&input, 0, 1, 2) { $0.element < $1.element }
    // offsets should still be ordered for equal values
    expectTrue(isSorted(input) {
      if $0.element == $1.element {
        return $0.offset < $1.offset
      }
      return $0.element < $1.element
    })
}

runAllTests()