-
-
Save khanlou/9168759b202bf35b461d6091ab062e89 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
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