0001    //
0002    //  shuffle.swift
0003    //
0004    //  Created by Guillaume Lessard on 2014-08-28.
0005    //  Copyright (c) 2014 Guillaume Lessard. All rights reserved.
0006    //
0007    //  https://github.com/glessard/shuffle
0008    //  https://gist.github.com/glessard/7140fe885af3eb874e11
0009    //
0010    
0011    #if os(Linux)
0012    import func Glibc.random
0013    #else
0014    import func Darwin.C.stdlib.arc4random_uniform
0015    #endif
0016    
0017    /// Get a sequence/generator that will return a collection's elements in a random order.
0018    /// The input collection is not modified.
0019    ///
0020    /// - parameter c: The collection to be shuffled
0021    /// - returns: A sequence of of `c`'s elements, lazily shuffled.
0022    
0023    public func shuffle<C: CollectionType>(c: C) -> ShuffledSequence<C>
0024    {
0025      return ShuffledSequence(c)
0026    }
0027    
0028    public extension CollectionType
0029    {
0030      /// Get a sequence/generator that will return a collection's elements in a random order.
0031      /// The input collection is not modified.
0032      ///
0033      /// - returns: A sequence of of `self`'s elements, lazily shuffled.
0034    
0035      public func shuffled() -> ShuffledSequence<Self>
0036      {
0037        return ShuffledSequence(self)
0038      }
0039    }
0040    
0041    
0042    /// A stepwise implementation of the Knuth Shuffle (a.k.a. Fisher-Yates Shuffle).
0043    /// The input collection is not modified: the shuffling itself is done
0044    /// using an adjunct array of indices.
0045    
0046    public struct ShuffledSequence
shuffle.swift:23
public func shuffle<C: CollectionType>(c: C) -> ShuffledSequence<C>
shuffle.swift:25
  return ShuffledSequence(c)
shuffle.swift:35
  public func shuffled() -> ShuffledSequence<Self>
shuffle.swift:37
    return ShuffledSequence(self)
<C
shuffle.swift:48
  public let collection: C
shuffle.swift:52
  private var i: [C.Index]
shuffle.swift:54
  public init(_ input: C)
shuffle.swift:61
  public mutating func next() -> C.Generator.Element?
: CollectionType>: SequenceType, GeneratorType
0047    {
0048      public let collection
shuffle.swift:56
    collection = input
shuffle.swift:82
      return collection[i[step]]
: C
0049      public let count
shuffle.swift:58
    count = i.count
shuffle.swift:66
    if step < count
shuffle.swift:72
      let j = step + Int(arc4random_uniform(UInt32(count-step)))
: Int
0050    
0051      public private(set) var step
shuffle.swift:64
    step += 1
shuffle.swift:66
    if step < count
shuffle.swift:72
      let j = step + Int(arc4random_uniform(UInt32(count-step)))
shuffle.swift:72
      let j = step + Int(arc4random_uniform(UInt32(count-step)))
shuffle.swift:76
      if j != step // swap 2beta6 calls `fatalError` if the two items are identical.
shuffle.swift:78
        swap(&i[j], &i[step])
shuffle.swift:82
      return collection[i[step]]
 = -1
0052      private var i
shuffle.swift:57
    i = Array(input.indices)
shuffle.swift:58
    count = i.count
shuffle.swift:78
        swap(&i[j], &i[step])
shuffle.swift:78
        swap(&i[j], &i[step])
shuffle.swift:82
      return collection[i[step]]
: [C.Index]
0053    
0054      public init
shuffle.swift:25
  return ShuffledSequence(c)
shuffle.swift:37
    return ShuffledSequence(self)
(_ input: C)
0055      {
0056        collection = input
0057        i = Array(input.indices)
0058        count = i.count
0059      }
0060    
0061      public mutating func next() -> C.Generator.Element?
0062      {
0063        // current position in the array
0064        step += 1
0065    
0066        if step < count
0067        {
0068          // select a random Index from the rest of the array
0069    #if os(Linux)
0070          let j = step + Int(random() % (count-step))
0071    #else
0072          let j = step + Int(arc4random_uniform(UInt32(count-step)))
0073    #endif
0074    
0075          // swap that Index with the Index present at the current step in the array
0076          if j != step // swap 2beta6 calls `fatalError` if the two items are identical.
0077          {
0078            swap(&i[j], &i[step])
0079          }
0080    
0081          // return the new random Index.
0082          return collection[i[step]]
0083        }
0084    
0085        return nil
0086      }
0087    }
0088    
0089    
0090    /// A stepwise (lazy-ish) implementation of the Knuth Shuffle (a.k.a. Fisher-Yates Shuffle),
0091    /// using a sequence of indices for the input. Elements (indices) from
0092    /// the input sequence are returned in a random order until exhaustion.
0093    
0094    public struct IndexShuffler
shuffleinplace.swift:70
    for (i, j) in zip(indices, IndexShuffler(indices))
<I
shuffle.swift:98
  private var i: [I]
shuffle.swift:100
  public init<S: SequenceType where S.Generator.Element == I>(_ input: S)
shuffle.swift:105
  public init(_ input: Array<I>)
shuffle.swift:111
  public mutating func next() -> I?
: ForwardIndexType>: SequenceType, GeneratorType
0095    {
0096      public let count
shuffle.swift:108
    count = input.count
shuffle.swift:116
    if step < count
shuffle.swift:122
      let j = step + Int(arc4random_uniform(UInt32(count-step)))
: Int
0097      public private(set) var step
shuffle.swift:114
    step += 1
shuffle.swift:116
    if step < count
shuffle.swift:122
      let j = step + Int(arc4random_uniform(UInt32(count-step)))
shuffle.swift:122
      let j = step + Int(arc4random_uniform(UInt32(count-step)))
shuffle.swift:126
      if j != step // swap 2beta6 calls `fatalError` if the two items are identical.
shuffle.swift:128
        swap(&i[j], &i[step])
shuffle.swift:132
      return i[step]
 = -1
0098      private var i
shuffle.swift:107
    i = input
shuffle.swift:128
        swap(&i[j], &i[step])
shuffle.swift:128
        swap(&i[j], &i[step])
shuffle.swift:132
      return i[step]
: [I]
0099    
0100      public init
shuffleinplace.swift:70
    for (i, j) in zip(indices, IndexShuffler(indices))
<S: SequenceType where S.Generator.Element == I>(_ input: S)
0101      {
0102        self.init(Array(input))
0103      }
0104    
0105      public init
shuffle.swift:102
    self.init(Array(input))
(_ input: Array<I>)
0106      {
0107        i = input
0108        count = input.count
0109      }
0110    
0111      public mutating func next() -> I?
0112      {
0113        // current position in the array
0114        step += 1
0115    
0116        if step < count
0117        {
0118          // select a random Index from the rest of the array
0119    #if os(Linux)
0120          let j = step + Int(random() % (count-step))
0121    #else
0122          let j = step + Int(arc4random_uniform(UInt32(count-step)))
0123    #endif
0124    
0125          // swap that Index with the Index present at the current step in the array
0126          if j != step // swap 2beta6 calls `fatalError` if the two items are identical.
0127          {
0128            swap(&i[j], &i[step])
0129          }
0130    
0131          // return the new random Index.
0132          return i[step]
0133        }
0134    
0135        return nil
0136      }
0137    }
0138