OrderedDict.swift

protocol OrderedDictType : Indexable, SequenceType, CollectionType, MutableSliceable, RangeReplaceableCollectionType, CustomDebugStringConvertible {
  typealias Value
  typealias Container : MutableSliceable, RangeReplaceableCollectionType
  typealias SubSequence : SequenceType
  typealias Key : Hashable
  var contents: [Key:Value] { get set }
  var keys: Container { get set }
  init(keys: Container, contents: [Key:Value])
}

extension OrderedDictType where Key == Container.Generator.Element {
  var startIndex: Container.Index { return keys.startIndex }
  var endIndex: Container.Index { return keys.endIndex }
  subscript(i: Container.Index) -> (Key, Value) {
    get {
      let k = keys[i]
      return (k, contents[k]!)
    } set {
      let k = keys[i]
      self.keys[i] = newValue.0
      contents.removeValueForKey(k)
      contents[newValue.0] = newValue.1
    }
  }
}

extension OrderedDictType where
  Key == Container.Generator.Element,
  Container.SubSequence.Generator.Element == Key,
  SubSequence : OrderedDictType,
  SubSequence.Container == Container.SubSequence,
  SubSequence.Key == Key, SubSequence.Value == Value,
  SubSequence.Generator.Element == (Key, Value) {
  subscript(idxs: Range<Container.Index>) -> SubSequence {
    get {
      let r = keys[idxs]
      var dict: [Key:Value] = [:]
      for k in r { dict[k] = contents[k] }
      return SubSequence(keys: r, contents: dict)
    } set {
      for (i, (k, v)) in zip(idxs, newValue) {
        let oldK = keys[i]
        keys[i] = k
        contents.removeValueForKey(oldK)
        contents[k] = v
      }
    }
  }
}

extension OrderedDictType where Container.Index.Distance == Int, Key == Container.Generator.Element {
  init<S : SequenceType where S.Generator.Element == (Key, Value)>(_ seq: S) {
    var ks = Container()
    ks.reserveCapacity(seq.underestimateCount())
    var cs: [Key:Value] = [:]
    for (k, v) in seq {
      ks.append(k)
      cs[k] = v
    }
    self.init(keys: ks, contents: cs)
  }
}

extension OrderedDictType where Container.Generator.Element == Key {
  subscript(k: Key) -> Value? {
    get { return contents[k] }
    set { contents[k] = newValue }
  }
  mutating func removevalueForKey(k: Key) -> Value? {
    return contents.removeValueForKey(k)
  }
  var debugDescription: String {
    let debugDesc: Key -> String = { k in
      String(reflecting: k) + ":" + String(reflecting: self.contents[k]!)
    }
    return "[" + ", ".join(keys.map(debugDesc)) + "]"
  }
}

extension OrderedDictType where Container.SubSequence.Generator.Element == Key, Generator.Element == (Key, Value), Container.Generator.Element == Key {
  mutating func replaceRange<C : CollectionType where C.Generator.Element == Generator.Element>(subRange: Range<Container.Index>, with newElements: C) {
    for k in keys[subRange] { contents.removeValueForKey(k) }
    keys.replaceRange(subRange, with: newElements.map { $0.0 })
    for (k, v) in newElements { contents[k] = v }
  }
  init() {
    self.init(keys: Container(), contents: [:])
  }
}

struct OrderedDict<Key : Hashable, Value> : OrderedDictType {
  var keys: [Key]
  var contents: [Key:Value]
  typealias SubSequence = OrderedDictSlice<Key, Value>
}

struct OrderedDictSlice<Key : Hashable, Value> : OrderedDictType {
  var keys: ArraySlice<Key>
  var contents: [Key:Value]
  typealias SubSequence = OrderedDictSlice<Key, Value>
}

struct ContiguousOrderedDict<Key : Hashable, Value> : OrderedDictType {
  var keys: ContiguousArray<Key>
  var contents: [Key:Value]
  typealias SubSequence = OrderedDictSlice<Key, Value>
}