Ordered dictionary in swift 2

Question

Loosely basing myself on this blog post, I implemented an ordered dictionary. In essence, it's a wrapper struct for a list of tuples with some initialisers and some functions (map, filter, toArray, ...) added to it.

struct OrderedDictionary<KeyType: Hashable, ValueType>: SequenceType
{
    typealias KeyValueType = (key:KeyType, value:ValueType)

    private var tuples: [KeyValueType] = []

    init() {}

    init(_ tupleArgs: KeyValueType...)
    {
        self.init(tupleArgs)
    }

    init(_ tupleArgs: [KeyValueType])
    {
        tuples = tupleArgs
    }

    subscript(key:KeyType) -> ValueType?
    {
        get
        {
            return tuples.filter({ $0.key == key })[0].value
        }

        set(newValue)
        {
            if let val = newValue
            {
                if tuples.contains({ $0.key == key })
                {
                    tuples = tuples.map({ $0.key == key ? ($0.key, val) : $0 })
                }
                else
                {
                    tuples.append((key, val))
                }
            }
            else
            {
                tuples = tuples.filter({ $0.key != key })
            }
        }
    }

    func generate() -> AnyGenerator<KeyValueType>
    {
        var nextIndex = 0
        return anyGenerator({
            if nextIndex >= self.tuples.count
            {
                return nil
            }
            else
            {
                return self.tuples[nextIndex++]
            }
        })
    }

    mutating func insert(tuple: KeyValueType, atIndex index: Int)
    {
        tuples = tuples.filter({ $0.key != tuple.key })
        tuples.insert(tuple, atIndex: index)
    }

    func map<NewKeyType:Hashable, NewValueType>(transform: (KeyValueType) -> (key:NewKeyType, value:NewValueType)) -> OrderedDictionary<NewKeyType, NewValueType>
    {
        return OrderedDictionary<NewKeyType, NewValueType>(tuples.map(transform))
    }

    func filter(includeElement: (KeyValueType) -> Bool) -> OrderedDictionary<KeyType, ValueType>
    {
        return OrderedDictionary(tuples.filter(includeElement))
    }

    func sort(isOrderedBefore: (KeyValueType, KeyValueType) -> Bool) -> OrderedDictionary<KeyType, ValueType>
    {
        return OrderedDictionary(tuples.sort(isOrderedBefore))
    }

    func reverse() -> OrderedDictionary<KeyType, ValueType>
    {
        return OrderedDictionary(tuples.reverse())
    }

    func toArray<T>(transform:((KeyValueType) -> T)) -> [T]
    {
        return tuples.map(transform)
    }

    func toArray() -> [KeyValueType]
    {
        return tuples
    }

    func toDict() -> [KeyType:ValueType]
    {
        var dict: [KeyType:ValueType] = [:]
        for tuple in tuples
        {
            dict[tuple.key] = tuple.value
        }
        return dict
    }
}

Does this look okay? Is it Swift-y enough and are there no major performance issues? I'm a bit worried about the filter, map, reverse and sort functions, but I'm not sure why. I'm also not confident about my use of map in the subscript setter.

Answer 1

Your code looks generally good (with two real problems explained below).

Instead of an empty default array

private var tuples: [KeyValueType] = []

which is overwritten in two of the three init methods, I would initialize the array explicitly:

private var tuples: [KeyValueType]

init() {
    tuples = []
}

but that is perhaps a matter of taste.

The problem with the other two init methods is that they don't check for duplicate keys, e.g. if you call

let od = OrderedDictionary(("foo", 1), ("bar", 2), ("foo", 3))

You either have to add an explicit check (and throw an error or fail if duplicate keys are given), or add the key/value pairs sequentially so that duplicate keys are silently overwritten with the new value:

init(_ tupleArgs: [KeyValueType]) {
    self.init()
    for (key, value) in tupleArgs {
        self[key] = value
    }
}

---

There is a problem in your subscript getter method:

return tuples.filter({ $0.key == key })[0].value 

will crash if there is no key/value tuple for the given key, instead of returning nil, because accessing [0] requires that there is at least one element. This can be fixed as

return tuples.filter({ $0.key == key }).first?.value

because first returns an optional. But this is not very effective. The filter method always traverses the entire array, but only the first (and only) matching tuple is needed. This can be achieved with indexOf:

get {
    if let index = tuples.indexOf({ $0.key == key }) {
        return tuples[index].value
    } else {
        return nil
    }
}

Similarly, in the subscript setter method, it is not effective to call contains first and then map the entire tuple array to a new array. I would implement that as

set(newValue) {
    if let index = tuples.indexOf({ $0.key == key }) {
        if let val = newValue {
            // Update existing value
            tuples[index].value = val
        } else {
            // Remove existing value
            tuples.removeAtIndex(index)
        }
    } else if let val = newValue {
        // Add new value
        tuples.append((key, val))
    }
}

---

The generate method can be simplified considerably, since you are only forwarding the enumeration to the tuples array:

func generate() -> AnyGenerator<KeyValueType> {
    return anyGenerator(tuples.generate())
}

---

The

func toArray<T>(transform:((KeyValueType) -> T)) -> [T]

is not really needed, you'll get the same result already with your map() and toArray() method.

---

You should make your type conform to CustomStringConvertible so that printing an ordered dictionary gives a nice looking result. A simple implementation would be

extension OrderedDictionary : CustomStringConvertible {
    var description: String {
        return "[ "
            + tuples.map({ (key, value) in "\(key) : \(value)"}).joinWithSeparator(", ")
            + "]"
    }
}

---

Creating a new (ordered) dictionary by mapping both keys and values can lead to unexpected results if two keys are mapped to the same new key. E.g. (with the fixed init method from above):

let od1 = OrderedDictionary(("foo", 1), ("bar", 2), ("FOO", 3))
print(od1) // [ foo : 1, bar : 2, FOO : 3]

let od2 = od1.map { (key, value) in (key.uppercaseString, value) }
print(od2) // [ FOO : 3, BAR : 2]

You have to decide if that is wanted. Alternatively, define a map() method which only maps the values but preserves the keys.

---

If you plan to add the code to a framework then you have to annotate the struct itself and all its public methods as public.

---

Some remarks concerning the performance: Each key lookup is done by a linear traversal of the tuples array. For large dictionaries this can become a problem.

The project from the referenced blog post solves this by maintaining both a dictionary (for the key/value pairs) and an array (for the ordered keys). The advantage is that a lookup is fast. But adding a new key or removing a key still requires a linear traversal of the keys array. Whether this is acceptable or not depends on how often keys are added/removed compared to key/value lookups.

One could store the key/value pairs in a tree structure to improve the performance (e.g. AVL tree or a red-black tree). Of course that increases the complexity of the code.