Somewhat complete ordered dictionary implementation

OrderedDictionary.swift

struct OrderedDictionary<Key : Hashable, Value> {
    typealias Element = (key: Key, value: Value)

    private var dictionary = [Key: Value]()
    private var orderedKeys = [Key]()

    var count: Int {
        return self.orderedKeys.count
    }

    var keys: [Key] {
        return self.orderedKeys
    }

    var values: [Value] {
        return self.orderedKeys.map {
            self.dictionary[$0]!
        }
    }

    subscript(key: Key) -> Value? {
        get {
            return self.dictionary[key]
        }
        set {
            if let value = newValue {
                self.updateValue(value, forKey: key)
            } else {
                self.removeValueForKey(key)
            }
        }
    }

    mutating func removeLast() -> Element {
        let key = self.orderedKeys.removeLast()
        let value = self.dictionary.removeValueForKey(key)!
        return (key, value)
    }

    mutating func removeValueForKey(key: Key) -> Value? {
        // TODO: guard … else return nil
        if let index = find(self.orderedKeys, key) {
            self.orderedKeys.removeAtIndex(index)
            return self.removeValueForKey(key)
        }
        return nil
    }

    mutating func updateValue(value: Value, forKey key: Key) -> Value? {
        let oldValue = self.dictionary[key]
        if oldValue == nil {
            self.orderedKeys.append(key)
        }
        self.dictionary[key] = value
        return oldValue
    }
}

extension OrderedDictionary : DictionaryLiteralConvertible {
    init(dictionaryLiteral elements: (Key, Value)...) {
        for (key, value) in elements {
            self[key] = value
        }
    }
}

extension OrderedDictionary : SequenceType {
    typealias Generator = GeneratorOf<Element>

    func generate() -> Generator {
        var next = 0
        return GeneratorOf {
            if (next >= self.orderedKeys.count) {
                return nil
            }
            let key = self.orderedKeys[next++]
            return (key, self.dictionary[key]!)
        }
    }
}

extension OrderedDictionary : MutableCollectionType {
    typealias Index = Int

    var startIndex: Index {
        return 0
    }

    var endIndex: Index {
        return self.count
    }

    subscript(position: Index) -> Element {
        get {
            let key = self.orderedKeys[position]
            return (key, self.dictionary[key]!)
        }
        set {
            self.removeAtIndex(position)
            self.insert(newValue, atIndex: position)
        }
    }
}

extension OrderedDictionary : MutableSliceable {
    typealias SubSlice = ArraySlice<Element>

    subscript(range: Range<Index>) -> SubSlice {
        get {
            let items = self.orderedKeys[range].map { ($0, self.dictionary[$0]!) }
            return SubSlice(items)
        }
        set {
            self.replaceRange(range, with: newValue)
        }
    }
}

extension OrderedDictionary : RangeReplaceableCollectionType {
    mutating func append(newElement: Element) {
        self.insert(newElement, atIndex: self.endIndex)
    }

    mutating func extend<S : SequenceType where S.Generator.Element == Element>(newElements: S) {
        for newElement in newElements {
            self.append(newElement)
        }
    }

    mutating func insert(newElement: Element, atIndex i: Index) {
        self.splice([newElement], atIndex: i)
    }

    mutating func removeAll(keepCapacity: Bool = false) {
        self.dictionary.removeAll(keepCapacity: keepCapacity)
        self.orderedKeys.removeAll(keepCapacity: keepCapacity)
    }

    mutating func removeAtIndex(index: Index) -> Element {
        let key = self.orderedKeys.removeAtIndex(index)
        let value = self.dictionary.removeValueForKey(key)!
        return (key, value)
    }

    mutating func removeRange(subRange: Range<Index>) {
        let keys = self.orderedKeys[subRange]
        self.orderedKeys.removeRange(subRange)
        for key in keys {
            self.dictionary.removeValueForKey(key)
        }
    }

    mutating func replaceRange<C : CollectionType where C.Generator.Element == Element>(subRange: Range<Index>, with newElements: C) {
        self.removeRange(subRange)
        self.splice(newElements, atIndex: subRange.startIndex)
    }

    mutating func reserveCapacity(minimumCapacity: Index.Distance) {
        self.orderedKeys.reserveCapacity(minimumCapacity)
    }

    mutating func splice<C : CollectionType where C.Generator.Element == Element>(newElements: C, atIndex i: Index) {
        // TODO: Optimize.
        var index = i
        for element in newElements {
            if let _ = self.dictionary.updateValue(element.value, forKey: element.key) {
                // The key being added already existed, so remove it from its current position.
                let existingIndex = find(self.orderedKeys, element.key)!
                self.orderedKeys.removeAtIndex(existingIndex)
                if existingIndex < i {
                    index--
                }
            }
            self.orderedKeys.insert(element.key, atIndex: index++)
        }
    }
}