Skip to content

Instantly share code, notes, and snippets.

@insanehunter
Created February 21, 2015 14:45
Show Gist options
  • Save insanehunter/8701025cb5d0c081a17f to your computer and use it in GitHub Desktop.
Save insanehunter/8701025cb5d0c081a17f to your computer and use it in GitHub Desktop.
ConstantAccessTimeDictionaryView: Dictionary representation with constant time access to values by keys
public struct ConstantAccessTimeDictionaryView<Key: Hashable, Value> {
public typealias IndexType =
Versioned<_ConstantAccessTimeDictionaryView<Key, Value>.IndexType>
public init(dict: [Key : Value]) {
view = Versioned(_ConstantAccessTimeDictionaryView(dict))
}
public func index(key: Key) -> IndexType? {
return view.value.index(key).map { IndexType($0, version: self.view.version) }
}
public subscript(index: IndexType) -> Value {
get {
assert(index.version == view.version, "Key does't correspond to the view!")
return view.value[index.value]
}
}
private let view: Versioned<_ConstantAccessTimeDictionaryView<Key, Value>>
}
public struct _ConstantAccessTimeDictionaryView<Key: Hashable, Value> {
public typealias IndexType = Int
private init(_ dict: [Key : Value]) {
let (indices, values) = unzip(map(enumerate(dict)) { (i, kv) in
((kv.0, i), kv.1)
})
self.indices = Dictionary.fromPairs(indices)
self.values = values
}
private func index(key: Key) -> IndexType? {
return indices[key]
}
private subscript(index: IndexType) -> Value {
get {
return values[index]
}
}
private let indices: [Key : IndexType]
private let values: [Value]
}
private extension Dictionary {
static func fromPairs(pairs: [(Key, Value)]) -> Dictionary<Key, Value> {
var dict = [Key : Value]()
for (k, v) in pairs {
dict[k] = v
}
return dict
}
}
private func unzip<T, U>(array: Array<(T, U)>) -> ([T], [U]) {
var ts = Array<T>()
var us = Array<U>()
for (t, u) in array {
ts.append(t)
us.append(u)
}
return (ts, us)
}
@insanehunter
Copy link
Author

This structure uses Versioned<T> from this gist

Example usage:

var dict: [String : Any] = ["_first": true, "_last": false, "name": "Something"]
let v = ConstantAccessTimeDictionaryView(dict: dict)
if let key = v.index("name") {
    v[key]
}

@insanehunter
Copy link
Author

Rationale:

Assume you have a dictionary with a set of heavily used keys. Accessing values by those keys may become pretty inefficient, so that's where this class shines - it restructures the dictionary in a way so every key may be converted into an array index and memorized. Accessing the dictionary with a key from another one (say, after mutation) renders in a nice assertion.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment