deck.swift

public enum Queue<Element> {
  case Nil
  indirect case Cons(head: Element, tail: Queue<Element>)
}

infix operator |> {
associativity right
precedence 100
}

public func |> <T>(lhs: T, rhs: Queue<T>) -> Queue<T> {
  return .Cons(head: lhs, tail: rhs)
}

extension Queue {
  private func rev(other: Queue<Element>) -> Queue<Element> {
    switch self {
    case .Nil: return other
    case let .Cons(head, tail): return tail.rev(head |> other)
    }
  }
  internal func reverse() -> Queue<Element> {
    return self.rev(.Nil)
  }
}

extension Queue : Indexable {
  public var startIndex: Int { return 0 }
  public var endIndex: Int {
    switch self {
    case .Nil: return 0
    case .Cons(_, let tail): return tail.endIndex.successor()
    }
  }
  
  public func with(val: Element, atIndex n: Int) -> Queue<Element> {
    switch (n, self) {
    case (0, .Cons(_, let tail)): return val |> tail
    case (_, let .Cons(head, tail)): return head |> tail.with(val, atIndex: n - 1)
    case (_, .Nil): fatalError("Index out of range")
    }
  }
  public subscript(n: Int) -> Element {
    get {
      switch (n, self) {
      case (0, .Cons(let head, _)): return head
      case (_, .Cons(_, let tail)): return tail[n - 1]
      case (_, .Nil): fatalError("Index out of range")
      }
    } set {
      self = with(newValue, atIndex: n)
    }
  }
}

public struct Deque<Element> {
  private var front: Queue<Element> { didSet { check() } }
  private var back : Queue<Element> { didSet { check() } }
  private var fCount, bCount: Int
  
  public init() {
    front = .Nil
    back  = .Nil
    fCount = 0
    bCount = 0
  }
}

extension Deque {
  private init(front: Queue<Element>, back: Queue<Element>, fCount: Int, bCount: Int) {
    self.front = front
    self.back  = back
    self.fCount = fCount
    self.bCount = bCount
  }
  private init(front: [Element], noReverseBack: [Element]) {
    self.front = Queue(front)
    self.back = Queue(noReverseBack)
    fCount = front.count
    bCount = noReverseBack.count
    check()
  }
}

extension Deque {
  private mutating func check() {
    if fCount == 1 || bCount == 1 { return }
    switch (front, back) {
    case (.Nil, let .Cons(head, tail)):
      front = tail.reverse()
      back = [head]
      (fCount, bCount) = (bCount - 1, 1)
    case (let .Cons(head, tail), .Nil):
      back = tail.reverse()
      front = [head]
      (bCount, fCount) = (fCount - 1, 1)
    default:
      return
    }
  }
}

extension Deque {
  public mutating func cons(with: Element) {
    ++fCount
    front = with |> front
  }
  public mutating func snoc(with: Element) {
    ++bCount
    back = with |> front
  }
}

public struct QueueGenerator<Element> : GeneratorType {
  private var queue: Queue<Element>
  public mutating func next() -> Element? {
    switch queue {
    case .Nil: return nil
    case let .Cons(head, tail):
      queue = tail
      return head
    }
  }
}

extension Queue : SequenceType {
  public func generate() -> QueueGenerator<Element> {
    return QueueGenerator(queue: self)
  }
}

public struct DequeGenerator<Element> : GeneratorType {
  private var front, back: Queue<Element>
  public mutating func next() -> Element? {
    switch (front, back) {
    case (let .Cons(head, tail), _):
      front = tail
      return head
    case (_, let .Cons(head, tail)):
      back = tail
      return head
    default:
      return nil
    }
  }
}

extension DequeGenerator : SequenceType {
  public func generate() -> DequeGenerator {
    return self
  }
}

extension Deque : SequenceType {
  public func generate() -> DequeGenerator<Element> {
    return DequeGenerator(front: front, back: back.reverse())
  }
}

extension Deque : CustomDebugStringConvertible {
  public var debugDescription: String {
    
    return "[\(fCount), \(bCount)]: " +
      ", ".join(front.map { String(reflecting: $0) }) + " | " +
      ", ".join(back.reverse().map { String(reflecting: $0) })
  }
}

extension Queue {
  init<G : GeneratorType where G.Element == Element>(var gen: G) {
    self = gen.next().map{ $0 |> Queue(gen: gen) } ?? .Nil
  }
  init<S : SequenceType where S.Generator.Element == Element>(_ seq: S) {
    self = Queue(gen: seq.generate())
  }
}

extension Queue : ArrayLiteralConvertible {
  public init(arrayLiteral: Element...) {
    self = Queue(gen: arrayLiteral.generate())
  }
}

extension Deque {
  public init(ar: [Element]) {
    fCount = ar.endIndex / 2
    front = Queue(ar[0..<fCount])
    bCount = ar.endIndex - fCount
    back  = Queue(ar[fCount..<ar.endIndex].reverse())
  }
}

extension Deque : ArrayLiteralConvertible {
  public init(arrayLiteral: Element...) {
    self = Deque(ar: arrayLiteral)
  }
}

extension Deque {
  public mutating func removeLast() -> Element? {
    switch back {
    case .Nil: return nil
    case let .Cons(head, tail):
      --bCount
      back = tail
      return head
    }
  }
  public mutating func removeFirst() -> Element? {
    switch front {
    case .Nil: return nil
    case let .Cons(head, tail):
      --fCount
      front = tail
      return head
    }
  }
}

extension Deque {
  public var first: Element? {
    switch front {
    case .Nil: return nil
    case .Cons(let head, _): return head
    }
  }
  public var last: Element? {
    switch back {
    case .Nil: return nil
    case .Cons(let head, _): return head
    }
  }
}

extension Deque {
  public var tail: Deque<Element> {
    switch front {
    case .Nil: return Deque()
    case .Cons(_, let tail):
      var ret = Deque(front: tail, back: back, fCount: fCount - 1, bCount: bCount)
      ret.check()
      return ret
    }
  }
  public var initial: Deque<Element> {
    switch back {
    case .Nil: return Deque()
    case .Cons(_, let tail):
      var ret = Deque(front: front, back: tail, fCount: fCount, bCount: bCount - 1)
      ret.check()
      return ret
    }
  }
}

extension Deque : Indexable {
  public var startIndex: Int { return 0 }
  public var count     : Int { return fCount + bCount }
  public var endIndex  : Int { return count }
  public subscript(n: Int) -> Element {
    get { return n < fCount ? front[n] : back[bCount - (n - fCount) - 1] }
    set(v) { n < fCount ? (front[n] = v) : (back[bCount - (n - fCount) - 1] = v) }
  }
}

extension Queue {
  public func map<T>(@noescape transform: (Element) -> T) -> Queue<T> {
    switch self {
    case .Nil: return .Nil
    case let .Cons(head, tail): return transform(head) |> tail.map(transform)
    }
  }
}

extension Deque {
  public func map<T>(@noescape transform: Element -> T) -> Deque<T> {
    return Deque<T>(
      front: front.map(transform),
      back: back.map(transform),
      fCount: fCount, bCount: bCount
    )
  }
}
extension Deque {
  public func flatMap<S : SequenceType>(@noescape transform: Element -> S) -> Deque<S.Generator.Element> {
    let frontAr: [S.Generator.Element] = front.flatMap(transform)
    let backAr : [S.Generator.Element] = back .flatMap(transform)
    return Deque<S.Generator.Element>(front: frontAr, noReverseBack: backAr)
  }
  public func flatMap<T>(@noescape transform: Element -> T?) -> Deque<T> {
    let frontAr: [T] = front.flatMap(transform)
    let backAr : [T] = back .flatMap(transform)
    return Deque<T>(front: frontAr, noReverseBack: backAr)
  }
}

public extension Queue {
  public func appended(with: Element) -> Queue<Element> {
    switch self {
    case .Nil: return [with]
    case let .Cons(head, tail): return head |> tail.appended(with)
    }
  }
  public func extended(with: Queue<Element>) -> Queue<Element> {
    switch self {
    case .Nil: return with
    case let .Cons(head, tail): return head |> tail.extended(with)
    }
  }
  public func extended<
    S : SequenceType where S.Generator.Element == Element
    >(with: S) -> Queue<Element> {
      return extended(Queue(with))
  }
}

public extension Queue {
  public func flatMap<S : SequenceType>(@noescape transform: (Element -> S)) -> Queue<S.Generator.Element> {
    switch self {
    case .Nil: return .Nil
    case let .Cons(head, tail):
      return Queue<S.Generator.Element>(transform(head))
        .extended(tail.flatMap(transform))
    }
  }
  public func flatMap<T>(@noescape transform: (Element -> Queue<T>)) -> Queue<T> {
    switch self {
    case .Nil: return .Nil
    case let .Cons(head, tail): return transform(head).extended(tail.flatMap(transform))
    }
  }
  public func flatMap<T>(@noescape transform: Element -> T?) -> Queue<T> {
    switch self {
    case .Nil: return .Nil
    case let .Cons(head, tail): return transform(head).map{ $0 |> tail.flatMap(transform)} ?? tail.flatMap(transform)
    }
  }
}