ContiguousList.swift

struct ContiguousList<Element> {
  private var revContents: [Element]
}

struct ContiguousListIndex {
  private let revd: Int
}

extension ContiguousListIndex : Equatable, ForwardIndexType {
  func successor() -> ContiguousListIndex {
    return ContiguousListIndex(revd: revd.predecessor())
  }
}

func == (lhs: ContiguousListIndex, rhs: ContiguousListIndex) -> Bool {
  return lhs.revd == rhs.revd
}
func < (lhs: ContiguousListIndex, rhs: ContiguousListIndex) -> Bool {
  return lhs.revd > rhs.revd
}
func > (lhs: ContiguousListIndex, rhs: ContiguousListIndex) -> Bool {
  return lhs.revd < rhs.revd
}

extension ContiguousListIndex : BidirectionalIndexType {
  func predecessor() -> ContiguousListIndex {
    return ContiguousListIndex(revd: revd.successor())
  }
}

extension ContiguousListIndex : RandomAccessIndexType {
  func distanceTo(other: ContiguousListIndex) -> Int {
    return revd - other.revd
  }
  func advancedBy(n: Int) -> ContiguousListIndex {
    return ContiguousListIndex(revd: revd - n)
  }
}

extension ContiguousList : Indexable {
  var endIndex: ContiguousListIndex {
    return ContiguousListIndex(revd: revContents.startIndex.predecessor())
  }
  var startIndex: ContiguousListIndex {
    return ContiguousListIndex(revd: revContents.endIndex.predecessor())
  }
  var count: Int {
    return revContents.count
  }
  subscript(idx: ContiguousListIndex) -> Element {
    get { return revContents[idx.revd] }
    set { revContents[idx.revd] = newValue }
  }
}

extension ContiguousList : SequenceType {
  func generate() -> IndexingGenerator<ContiguousList> {
    return IndexingGenerator(self)
  }
}

extension ContiguousList : ArrayLiteralConvertible {
  init(arrayLiteral: Element...) {
    revContents = arrayLiteral.reverse()
  }
}

extension ContiguousList {
  mutating func removeFirst() -> Element {
    return revContents.removeLast()
  }
  var first: Element? {
    return revContents.last
  }
  var last: Element? {
    return revContents.first
  }
  var isEmpty: Bool {
    return revContents.isEmpty
  }
}

struct ContiguousListSlice<Element> {
  private var revContents: ArraySlice<Element>
}

extension ContiguousListSlice : Indexable {
  var endIndex: ContiguousListIndex {
    return ContiguousListIndex(revd: revContents.startIndex.predecessor())
  }
  var startIndex: ContiguousListIndex {
    return ContiguousListIndex(revd: revContents.endIndex.predecessor())
  }
  var count: Int {
    return revContents.count
  }
  subscript(idx: ContiguousListIndex) -> Element {
    get { return revContents[idx.revd] }
    set { revContents[idx.revd] = newValue }
  }
}

extension ContiguousListSlice : SequenceType {
  func generate() -> IndexingGenerator<ContiguousListSlice> {
    return IndexingGenerator(self)
  }
}

extension ContiguousListSlice : ArrayLiteralConvertible {
  init(arrayLiteral: Element...) {
    revContents = ArraySlice(arrayLiteral.reverse())
  }
}

extension ContiguousListSlice {
  mutating func removeFirst() -> Element {
    return revContents.removeLast()
  }
  var first: Element? {
    return revContents.last
  }
  var last: Element? {
    return revContents.first
  }
  var isEmpty: Bool {
    return revContents.isEmpty
  }
}

extension ContiguousList : CollectionType {
  subscript(idxs: Range<ContiguousListIndex>) -> ContiguousListSlice<Element> {
    get {
      return ContiguousListSlice(revContents:
        revContents[idxs.endIndex.revd.successor()..<idxs.startIndex.revd.successor()]
      )
    } set {
      revContents[idxs.endIndex.revd.successor()..<idxs.startIndex.revd.successor()] =
        newValue.revContents
    }
  }
}

extension ContiguousListSlice : CollectionType {
  subscript(idxs: Range<ContiguousListIndex>) -> ContiguousListSlice<Element> {
    get {
      return ContiguousListSlice(revContents:
        revContents[idxs.endIndex.revd.successor()..<idxs.startIndex.revd.successor()]
      )
    } set {
      revContents[idxs.endIndex.revd.successor()..<idxs.startIndex.revd.successor()] =
        newValue.revContents
    }
  }
}

extension ContiguousList {
  init() {
    revContents = []
  }
}

extension ContiguousListSlice {
  init() {
    revContents = []
  }
}

extension ContiguousList {
  init<S : SequenceType where S.Generator.Element == Element>(seq: S) {
    revContents = seq.reverse()
  }
}

extension ContiguousListSlice {
  init<S : SequenceType where S.Generator.Element == Element>(seq: S) {
    revContents = ArraySlice(seq.reverse())
  }
}

extension ContiguousList {
  mutating func prepend(with: Element) {
    revContents.append(with)
  }
}

extension ContiguousListSlice {
  mutating func prepend(with: Element) {
    revContents.append(with)
  }
}

extension ContiguousList {
  mutating func reserveCapacity(n: Int) {
    revContents.reserveCapacity(n)
  }
}

extension ContiguousListSlice {
  mutating func reserveCapacity(n: Int) {
    revContents.reserveCapacity(n)
  }
}

extension ContiguousList {
  subscript(idx: Int) -> Element {
    get { return revContents[revContents.endIndex.predecessor() - idx] }
    set { revContents[revContents.endIndex.predecessor() - idx] = newValue }
  }
}

extension ContiguousList {
  subscript(idxs: Range<Int>) -> ContiguousListSlice<Element> {
    get {
      let str = revContents.endIndex - idxs.endIndex
      let end = revContents.endIndex - idxs.startIndex
      return ContiguousListSlice(revContents: revContents[str..<end] )
    } set {
      let str = revContents.endIndex - idxs.endIndex
      let end = revContents.endIndex - idxs.startIndex
      revContents[str..<end] = newValue.revContents
    }
  }
}

extension ContiguousListSlice {
  subscript(idx: Int) -> Element {
    get { return revContents[revContents.endIndex.predecessor() - idx] }
    set { revContents[revContents.endIndex.predecessor() - idx] = newValue }
  }
}

extension ContiguousListSlice {
  subscript(idxs: Range<Int>) -> ContiguousListSlice<Element> {
    get {
      let str = revContents.endIndex - idxs.endIndex
      let end = revContents.endIndex - idxs.startIndex
      return ContiguousListSlice(revContents: revContents[str..<end] )
    } set {
      let str = revContents.endIndex - idxs.endIndex
      let end = revContents.endIndex - idxs.startIndex
      revContents[str..<end] = newValue.revContents
    }
  }
}

extension ContiguousList {
  func reverse() -> [Element] {
    return revContents
  }
}

extension ContiguousListSlice {
  func reverse() -> ArraySlice<Element> {
    return revContents
  }
}

struct ContiguousDeque<Element> {
  private var front: ContiguousList<Element> { didSet { check() } }
  private var back : ContiguousList<Element> { didSet { check() } }
  private init(_ front: ContiguousList<Element>, _ back: ContiguousList<Element>) {
    (self.front, self.back) = (front, back)
    check()
  }
}

extension ContiguousDeque {
  mutating func check() {
    switch (front.count, back.count) {
    case (0, 0), (1, 0), (0, 1): return
    case (_, 0):
      let nFront = front.removeFirst()
      back = ContiguousList(revContents: front.revContents.reverse())
      front = ContiguousList(revContents: [nFront])
    case (0, _):
      let nBack = back.removeFirst()
      front = ContiguousList(revContents: back.revContents.reverse())
      back = ContiguousList(revContents: [nBack])
    default:
      return
    }
  }
}

extension ContiguousDeque {
  private init(balancedFront: ContiguousList<Element>, balancedBack: ContiguousList<Element>) {
    (front, back) = (balancedFront, balancedBack)
  }
}

extension ContiguousDeque {
  init(array: [Element]) {
    let half = array.endIndex / 2
    front = ContiguousList(seq: array[0..<half])
    back = ContiguousList(seq: array[half..<array.endIndex].reverse())
  }
}

extension ContiguousDeque : ArrayLiteralConvertible {
  init(arrayLiteral: Element...) {
    self.init(array: arrayLiteral)
  }
}

extension ContiguousDeque {
  init<S : SequenceType where S.Generator.Element == Element>(_ seq: S) {
    self.init(array: Array(seq))
  }
}

struct ContiguousDequeGenerator<Element> : GeneratorType, SequenceType {
  private var front: IndexingGenerator<ContiguousList<Element>>?
  private var back : IndexingGenerator<[Element]>
  mutating func next() -> Element? {
    return front?.next() ?? {
      front = nil
      return back.next()
    }()
  }
  func generate() -> ContiguousDequeGenerator {
    return self
  }
}

extension ContiguousDeque : SequenceType {
  func generate() -> ContiguousDequeGenerator<Element> {
    return ContiguousDequeGenerator(front: front.generate(), back: back.reverse().generate())
  }
}

extension ContiguousDeque {
  var first: Element? {
    return front.first
  }
  var last: Element? {
    return back.first
  }
}

extension ContiguousDeque {
  func reverse() -> ContiguousDeque<Element> {
    return ContiguousDeque(balancedFront: back, balancedBack: front)
  }
}