Skip to content

Instantly share code, notes, and snippets.

@brentdax brentdax/SortedDictionary.swift Secret
Last active Apr 3, 2017

Embed
What would you like to do?
A dictionary that keeps its keys in sorted order and finds keys by binary search. An example of `private` vs. `fileprivate` use.
//
// SortedDictionary.swift
// CollectionKit
//
// Created by Brent Royal-Gordon on 2/7/17.
// Copyright © 2017 Architechies. All rights reserved.
//
public struct SortedDictionary<Key: Comparable, Value> {
public typealias Element = (key: Key, value: Value)
private var _keys: Sorted<[Key]> = []
private var _values: [Value] = []
public var startIndex: Index {
return Index(storageIndex: _keys.startIndex)
}
public var endIndex: Index {
return Index(storageIndex: _keys.endIndex)
}
fileprivate func bound(forKey key: Key) -> Index {
return Index(storageIndex: _keys.bound { $0 >= key })
}
public subscript(i: Index) -> Element {
get {
return (_keys[i.storageIndex], _values[i.storageIndex])
}
set {
let subrange: Range = i.storageIndex ..< index(after: i).storageIndex
let correct = _keys.updateSubrange(subrange, with: newValue.key)
precondition(correct, "i is not correct for key")
_values[i.storageIndex] = newValue.value
}
}
mutating fileprivate func insert(_ pair: Element) -> Element? {
let (subrange, oldKeys) = _keys.insert(pair.key)
let oldElement = oldKeys.first.map { ($0, _values[subrange.lowerBound]) }
_values.replaceSubrange(subrange, with: [pair.value])
return oldElement
}
mutating fileprivate func remove(at i: Index) -> Element {
return (_keys.remove(at: i.storageIndex), _values.remove(at: i.storageIndex))
}
mutating fileprivate func appendPresorted(_ pair: Element) {
if let lastKey = _keys.last {
assert(lastKey < pair.key, "Not presorted")
}
_keys.base.append(pair.key)
_values.append(pair.value)
}
}
extension SortedDictionary {
public var keys: Keys {
get { return .init(base: self) }
}
public var values: Values {
get { return .init(base: self) }
set { self = newValue.base }
}
public struct Keys: RandomAccessCollection {
public let base: SortedDictionary
public typealias Index = SortedDictionary.Index
public typealias IndexDistance = Int
public typealias _Element = Key
public typealias SubSequence = RandomAccessSlice<Keys>
public var startIndex: Index {
return base.startIndex
}
public var endIndex: Index {
return base.endIndex
}
public func _customIndexOfEquatableElement(_ element: Iterator.Element) -> Index?? {
return .some(base.index(forKey: element))
}
public subscript(_ i: Index) -> Key {
get {
return base[i].key
}
}
}
public struct Values: RandomAccessCollection, MutableCollection {
public fileprivate(set) var base: SortedDictionary
public typealias Index = SortedDictionary.Index
public typealias IndexDistance = Int
public typealias _Element = Value
public typealias SubSequence = MutableRandomAccessSlice<Values>
public var startIndex: Index {
return base.startIndex
}
public var endIndex: Index {
return base.endIndex
}
public subscript(_ i: Index) -> Value {
get {
return base[i].value
}
set {
base[i].value = newValue
}
}
public subscript(_ bounds: Range<Index>) -> MutableRandomAccessSlice<Values> {
get {
return MutableRandomAccessSlice(base: self, bounds: bounds)
}
set {
precondition(count == newValue.base.count, "Can't remove keys by slicing")
self = newValue.base
}
}
}
}
extension SortedDictionary {
@discardableResult
public mutating func removeValue(forKey key: Key) -> Value? {
guard let i = keys.index(of: key) else {
return nil
}
return remove(at: i).value
}
@discardableResult
public mutating func updateValue(_ newValue: Value, forKey key: Key) -> Value? {
let pair = (key: key, value: newValue)
return insert(pair)?.value
}
public subscript(_ key: Key) -> Value? {
get {
return keys.index(of: key).map { values[$0] }
}
set {
if let newValue = newValue {
updateValue(newValue, forKey: key)
}
else {
removeValue(forKey: key)
}
}
}
}
extension SortedDictionary: RandomAccessCollection {
public typealias _Element = Element
fileprivate func isKey(_ key: Key, at i: Index) -> Bool {
return i != endIndex && self[i].key == key
}
public func index(forKey key: Key) -> Index? {
let i = bound(forKey: key)
return isKey(key, at: i) ? i : nil
}
public struct Index: Comparable, Hashable, Strideable {
internal let storageIndex: Int
public func advanced(by n: Int) -> Index {
return Index(storageIndex: storageIndex + n)
}
public func distance(to other: Index) -> Int {
return other.storageIndex - storageIndex
}
public static func == (lhs: Index, rhs: Index) -> Bool {
return lhs.storageIndex == rhs.storageIndex
}
public static func < (lhs: Index, rhs: Index) -> Bool {
return lhs.storageIndex < rhs.storageIndex
}
public var hashValue: Int {
return storageIndex.hashValue
}
static func indexRange(from storageIndexRange: Range<Int>) -> Range<Index> {
return Index(storageIndex: storageIndexRange.lowerBound) ..< Index(storageIndex: storageIndexRange.upperBound)
}
static func storageIndexRange(from indexRange: Range<Index>) -> Range<Int> {
return indexRange.lowerBound.storageIndex ..< indexRange.upperBound.storageIndex
}
}
}
extension SortedDictionary {
public init<Elements: Sequence>(_ elements: Elements)
where Elements.Iterator.Element == Element
{
let sortedElements = elements.sorted { $0.key < $1.key }
self.init(presorted: sortedElements)
}
public init(presorted sortedElements: [Element]) {
self.init()
for (key, value) in sortedElements {
let pair = (key: key, value: value)
appendPresorted(pair)
}
}
public init(_ other: SortedDictionary) {
self = other
}
}
extension SortedDictionary {
public subscript(offset i: Int) -> Element {
get { return self[Index(storageIndex: i)] }
}
}
extension SortedDictionary.Keys {
public subscript(offset i: Int) -> Key {
get { return self[Index(storageIndex: i)] }
}
}
extension SortedDictionary.Values {
public subscript(offset i: Int) -> Value {
get { return self[Index(storageIndex: i)] }
set { self[Index(storageIndex: i)] = newValue }
}
}
extension SortedDictionary: ExpressibleByDictionaryLiteral {
public init(dictionaryLiteral elements: (Key, Value)...) {
self.init(elements as [Element])
}
}
extension SortedDictionary: CustomReflectable, CustomDebugStringConvertible {
public var customMirror: Mirror {
let children: [Mirror.Child] = map { pair in
let label: String? = String(reflecting: pair.key)
let value: Any = pair.value
return (label: label, value: value)
}
return Mirror(self, children: children, displayStyle: .dictionary)
}
public var debugDescription: String {
return "[" + map { pair in "\(String(reflecting: pair.key)): \(String(reflecting: pair.value))" }.joined(separator: ", ") + "] as SortedDictonary"
}
}
public func == <Key: Comparable, Value: Equatable> (lhs: SortedDictionary<Key, Value>, rhs: SortedDictionary<Key, Value>) -> Bool {
return lhs.elementsEqual(rhs, by: ==)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.