Create a gist now

Instantly share code, notes, and snippets.

@khanlou /Dictionary.swift Secret
Last active Nov 7, 2016

What would you like to do?
struct Placeholder<Key, Value> where Key: Equatable, Key: Hashable {
var values: [(Key, Value)] = []
func firstValue(matchingKey key: Key) -> Value? {
return values.lazy.filter({ $0.0 == key }).first?.1
}
mutating func removeValue(key: Key) {
values = values.filter({ $0.0 != key })
}
}
struct Dictionary<Key, Value> where Key: Equatable, Key: Hashable {
fileprivate var storage = Array<Placeholder<Key, Value>>(repeating: Placeholder<Key, Value>(), count: 2)
private let maxLoadFactor = 0.7
private var size: Int {
return storage.count
}
var count: Int {
return storage.flatMap({ $0.values }).count
}
var currentLoadFactor: Double {
return Double(count) / Double(size)
}
mutating func set(key: Key, value: Value) {
remove(key: key)
let position = abs(key.hashValue) % size
storage[position].values.append((key, value))
resizeIfNeeded()
}
mutating func resizeIfNeeded() {
if currentLoadFactor > maxLoadFactor {
let oldDictionary = self
storage = Array<Placeholder<Key, Value>>(repeating: Placeholder<Key, Value>(), count: size*2)
for (key, value) in oldDictionary {
self[key] = value
}
}
}
mutating func remove(key: Key) {
let position = abs(key.hashValue) % size
storage[position].removeValue(key: key)
}
func get(key: Key) -> Value? {
let position = abs(key.hashValue) % size
return storage[position].firstValue(matchingKey: key)
}
subscript(key: Key) -> Value? {
get {
return get(key: key)
}
set {
if let value = newValue {
set(key: key, value: value)
} else {
remove(key: key)
}
}
}
}
extension Dictionary: Sequence {
typealias Iterator = AnyIterator<(Key, Value)>
func makeIterator() -> Dictionary.Iterator {
var storageIterator = storage.makeIterator()
var currentIterator: AnyIterator<(Key, Value)>?
return AnyIterator({
if let next = currentIterator?.next() {
return next
}
if let nextPlaceholder = storageIterator.next() {
currentIterator = AnyIterator(nextPlaceholder.values.makeIterator())
}
return currentIterator?.next()
})
}
}
var dictionary = Dictionary<String, String>()
dictionary["there"] = "asdf"
dictionary["1232"] = "asd2f"
for pair in dictionary {
print(pair)
}
dictionary.count
dictionary["1232"]
dictionary["1232"] = nil
dictionary["1232"]
dictionary["there"]
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment