Swifty BiMap / Two way / One to One Dictionary (双向映射)

README.md

bimap

Probably the first Swifty BiMap / Two-way / One to One Dictionary that has a unified solution even works when Key and Value are of the same type

也许是第一个 使用 Swift 实现的，支持键值为同一类型，且最接近普通字典的双向映射

Prologue

Because it is "one to one", each item can only appear once, either in keys or values. If you find that inconvenient, and you just want to access the key of given value, use line 11 to 43 in AZTwoWayDictionary.swift, the extension on Dictionary instead.

func key(forValue value: Value) -> Key?
mutating func updateKey(_ key: Key, forValue value: Value) -> Key?

Usage

AZBiMap and AZTwoWayDictionary are exactly the same thing.

Of course, both Key and Value have to conform to the Hashable protocol.

Initialize

Use dictionary literals to initialize.

var map: AZTwoWayDictionary<String, Int> = ["Foo":0,"Bar":1]

Newer value/key overwrites previous ones.

var map: AZBiMap<String, Int> = ["Hi":1,"Hello":2,"Hi":3]
print(map)
// Prints "["Hi": 3, "Hello": 2]"

When key and value are of the same type, it is your responsibility to keep their role correct, because there is no way for the dictionary to tell if it is a key or a value.

var kvSame: AZBiMap<String, String> = ["Hi": "Hello", "Hello": "H"]
print(kvSame)
// Prints "["H": "Hello"]"

Get

Everything feels the same as of a normal dictionary, except that you can pass a value into subscript and get its key.

// map = ["Hi": 3, "Hello": 2]
print(map["Hi"])
// Prints "Optional(3)"
print(map[2])
// Prints "Optional("Hello")"

Set

You can add or update a pair by assign new value/key to it

Notice: assigning nil as the value does not remove the key-value pair

// map = ["Hi": 3, "Hello": 2]
map["Hi"] = 4
print(map)
// Prints "["Hi": 4, "Hello": 2]"
map[3]="Bonjour"
print(map)
// Prints "["Hi": 4, "Bonjour": 3, "Hello": 2]"

If both key and value already exists, nothing happens. Because you can either combine them into one, or remove either of them.

// map = ["Hi": 4, "Bonjour": 3, "Hello": 2]
map["Hi"]=2 // Nothing happens
// Find this candidate: ["Hi": 4, "Bonjour": 3, "Hello": 2]
// Find this candidate: ["Hi": 2, "Bonjour": 3]
// Find this candidate: ["Bonjour": 3, "Hello": 2]

Remove

To remove a key-value pair, remove(_:Any?) accepts both key/value to identify the pair. And you also have removeValue(forKey:Key), removeKey(forValue:Value), and removeAll().

map.remove(4)
print(map)
// Prints "["Bonjour": 3, "Hello": 2]"

Iterate

As long as you keeps line 293 to 481 in AZTwoWayDictionary.swift, the extension that makes this conforms to Collection, it's the same as dealing with a normal dictionary.

Credit

The example in this project which demonstrates how this works is originally written by Liuliet.Lee in English-MorseCode-Translator under MIT License.

AZTwoWayDictionary.swift

//
//  AZBiDictionary.swift
//  Bimap
//
//  Created by Apollo Zhu on 10/26/16.
//

import Foundation

extension Dictionary {
    /// Accesses the key associated with the given value.
    ///
    /// - parameter value: The value to find in the dictionary.
    ///
    /// - returns: The key associated with `value` if `value` is in the dictionary,
    ///     or `nil` otherwise.
    public func key(forValue value: Value) -> Key? {
        return (self as NSDictionary).allKeys(for: value).first as! Key?
    }

    /// Updates the key stored in the dictionary for the given value,
    /// or adds a new key-value pair if the value does not exist.
    ///
    /// - requires: Foundation
    ///
    /// - parameter key: The new key for the value.
    /// - parameter value:  The value to associate with `key`.
    ///     If `value` already exists in the dictionary, `key` replaces the existing associated key.
    ///     Otherwise, the `(key, value)` pair is added.
    ///
    /// - returns: The key that was replaced, or `nil` if a new key-value pair was added.
    public mutating func updateKey(_ key: Key, forValue value: Value) -> Key? {
        let previousKey = self.key(forValue: value)
        if let previousKey = previousKey {
            if let index = index(forKey: previousKey) {
                self.remove(at: index)
            }
        }
        self[key] = value
        return previousKey
    }
}

public typealias AZBiMap<Key: Hashable, Value: Hashable> = AZTwoWayDictionary<Key,Value>

/// A dictionary whose elements are key-value, and value-key pairs at the same time
/// Becuase you can use key/value to find associated value/key, 
/// so each item can only appear once, either in `keys` or `values`.
/// If you do need to have key/value that appear to be value/key,
/// use `key(forValue:)` and `updateKey(_:forValue:)` on normal dictionary instead.
///
/// Difference between `AZBiMap` and `AZTwoWayDictionary`
/// =====================================================
///
/// They are exactly the same thing. Pick the name you like.
///
/// Initialization
/// ============
/// Create a new TwoWayDictionary/BiMap by using a dictionary literal.
/// Notice that you can't switch the order of key,value at this point
///
///     var valid: AZTwoWayDictionary<String,Int> = ["Foo":0,"Bar":1]
///     var invalid: AZBiMap<String,Int> = ["Foo":0,1:"Bar"] // Invalid
///
/// Newer pairs will overwrite previous ones
///
///     var map: AZBiMap<String,Int> = ["Hi":1,"Hello":2,"Hi":3]
///     print(map)
///     // Prints "["Hi": 3, "Hello": 2]"
///
/// More importantly, if the the Key and the Value is of the same type, key and value may switch their role
///
///     var kvSame: AZBiMap<String,String> = ["Hi":"Hello","Hello":"H"]
///     print(kvSame)
///     // Prints "["H": "Hello"]"
///
/// Both Key and Value has to be any type that conforms to the `Hashable` protocol,
/// including all of Swift's basic types. You can use your own custom types
/// by making them conform to the `Hashable` protocol.
///
/// Getting, Setting, and Removing Dictionary Values
/// =====================================
///
/// You may access key/value with subscript by passing corresponding value/key
/// through subscripting, just like you used to do with dictionary:
///
///     print(map["Hi"])
///     // Prints "Optional(3)"
///     print(map[2])
///     // Prints "Optional("Hello")"
///
/// Update an existing value/key by assigning a new value/key to a key/value that already
/// exists in the dictionary, otherwise a new key-value pair will be add to dictionary, if appropriate.
/// Notice that assign `nil` will not remove a key-value pair.
///
///     map["Hi"] = 4
///     print(map)
///     // Prints "["Hi": 4, "Hello": 2]"
///     map[3]="Bonjour"
///     print(map)
///     // Prints "["Hi": 4, "Bonjour": 3, "Hello": 2]"
///
/// You may find this weird at first, but it makes sense.
/// The following does nothing because the result is indeterminate
/// There is no obvious way to treat this, you can combine ["Hi":4,"Hello":2] to ["Hi":2],
/// you can remove "Hi" and/or "Hello", etc.
///
///     map["Hi"]=2 // Do nothing
///
/// To remove a key-value pair, `remove(_:Any?)` accepts both key/value to identify the pair,
/// while `removeValue(forKey:Key)` and `removeKey(forValue:Value)` only accpets key/value.
/// Use `removeAll()` to remove everything in the dictionary
///
///     map.remove(4)
///     print(map)
///     // Prints "["Bonjour": 3, "Hello": 2]"
///
/// Iterating Over the Contents of a Dictionary
/// ===========================================
///
/// If you decided to keep `extension AZTwoWayDictionary: Collection`,
/// you can deal with it as normally Dictionary
public struct AZTwoWayDictionary<Key: Hashable, Value: Hashable>: ExpressibleByDictionaryLiteral {

    /// Internal dictionary
    fileprivate var _dict = [Key:Value]()
    /// If `Key` and `Value` has the same type
    fileprivate let isKVOfSameType: Bool

    /// The element type of a dictionary: a tuple containing an individual key-value pair.
    public typealias Element = (key: Key, value: Value)
    /// A collection containing just the keys of the dictionary.
    ///
    /// When iterated over, keys appear in this collection in the same order as they
    /// occur in the dictionary's key-value pairs. Each key in the keys
    /// collection has a unique value.
    public var keys    : LazyMapCollection<Dictionary<Key,Value>,Key>   { return _dict.keys }
    /// A collection containing just the values of the dictionary.
    ///
    /// When iterated over, values appear in this collection in the same order as they
    /// occur in the dictionary's key-value pairs.
    public var values  : LazyMapCollection<Dictionary<Key,Value>,Value> { return _dict.values }
    /// A Boolean value indicating whether the dictionary is empty.
    ///
    /// Dictionaries are empty when created with an initializer or an empty
    /// dictionary literal.
    public var isEmpty : Bool { return _dict.isEmpty }
    /// The number of key-value pairs in the dictionary.
    public var count   : Int { return _dict.count }

    /// Creates an empty dictionary.
    public init() {
        isKVOfSameType = Key.self == Value.self
    }

    public init(dictionaryLiteral elements: (Key, Value)...){
        self.init()
        _ = elements.map { set($0.0, $0.1) }
    }

    /// Accesses the value/key associated with the given key/value for reading and writing.
    ///
    /// This subscript returns the value/key for the given key/value if the key/value
    /// is found in the dictionary, or `nil` if the key/value is not found.
    ///
    /// When approprate, if you assign a value/key for a key/value and that key/value already exists,
    /// the dictionary overwrites the existing value/key,
    /// or the key and value are added as a new key-value pair.
    ///
    /// If you assign `nil` as the value for the given id, nothing happens.
    ///
    /// - parameter id: The key/value to find in the dictionary.
    /// - returns: The value/key associated with `id` if `id` is in the dictionary as Key or Value;
    ///   otherwise, `nil`.
    public subscript(id: Any?) -> Any? {
        get { return get(id) }
        set { set(id, newValue) }
    }

    /// Updates the key/value stored in the dictionary for the given value/key,
    /// or adds a new key-value pair if the key does not exist.
    ///
    /// - parameter id: The new value for the key.
    /// - parameter val:  The key to associate with `value`.
    ///     If `key` already exists in the dictionary, `value` replaces the existing associated value.
    ///     Otherwise, the `(key, value)` pair is added.
    internal mutating func set(_ id: Any?, _ val: Any?) {
        guard let id = id, let val = val, id is AnyHashable && val is AnyHashable else { return }
        if isKVOfSameType {
            guard id is Key && id as! Key != val as! Key && !keys.contains(val as! Key) && !values.contains(val as! Value) else { return }
            if values.contains(id as! Value) {
                _ = _dict.updateKey(val as! Key, forValue: id as! Value)
            } else {
                _dict[id as! Key] = val as? Value
            }
        } else {
            switch id.self {
            case is Key where val is Value && !values.contains(val as! Value):
                _dict[id as! Key] = val as? Value
            case is Value where val is Key && !keys.contains(val as! Key):
                _ = _dict.updateKey(val as! Key, forValue: id as! Value)
            default:
                break
            }
        }
    }

    /// Get key/value associated with id
    ///
    /// - parameter id: key/value to find its associated value/key
    ///
    /// - returns: value/key associated with given `id` as value/key
    internal func get(_ id: Any?) -> Any? {
        guard let id = id, id is AnyHashable else { return nil }
        var result: Any? = nil
        if id is Key {
            result = _dict[id as! Key]
        }
        if id is Value {
            result = _dict.key(forValue: id as! Value) ?? result
        }
        return result
    }

    /// Set or add new key-value pair
    ///
    /// - parameter val: new value/key for given `id`
    /// - parameter id:  identifier used to find key-value pair
    ///
    /// - returns: previous value/key associated with given `id`
    public mutating func update(_ val: Any?, for id: Any?) -> Any? {
        defer { set(id, val) }
        return get(id)
    }

    /// Removes the given key and its associated value from the dictionary if the key is found in it.
    ///
    /// - parameter key: The key to remove along with its associated value.
    ///
    /// - returns: The value that was removed, or `nil` otherwise.
    public mutating func remove(_ id: Any?) -> Any? {
        guard let id = id, id is AnyHashable else { return nil }
        var previous: Any? = nil
        if id is Key {
            previous = _dict.removeValue(forKey: id as! Key)
        }
        if id is Value {
            if let key = self[id as! Value] {
                previous = _dict.removeValue(forKey: key as! Key) ?? previous
            }
        }
        return previous
    }

    /// Removes all key-value pairs from the dictionary.
    public mutating func removeAll() {
        _dict.removeAll()
    }

    /// Removes the given key and its associated value from the dictionary if the key is found in it.
    ///
    /// - parameter key: The key to remove along with its associated value.
    ///
    /// - returns: The value that was removed, or `nil` otherwise.
    public mutating func removeValue(forKey key: Key) -> Value? {
        return remove(key) as! Value?
    }

    /// Removes the given value and its associated key from the dictionary if the value is found in it.
    ///
    /// - parameter value: The value to remove along with its associated key.
    ///
    /// - returns: The key that was removed, or `nil` otherwise.
    public mutating func removeKey(forValue value: Value) -> Key? {
        return remove(value) as! Key?
    }

    /// Generates and returns a new `AZTwoWayDictionary` with value as key
    ///
    /// - important: Inversed dictionary is not cached
    ///
    /// - returns: New `AZTwoWayDictionary` with Value and Key inversed
    public func inversed() -> AZTwoWayDictionary<Value,Key> {
        var inversedDict = AZTwoWayDictionary<Value,Key>()
        var innerDict = [Value:Key]()
        _dict.forEach { innerDict[$0.value] = $0.key }
        inversedDict._dict = innerDict
        return inversedDict
    }
}

extension AZTwoWayDictionary: Collection {
    // MARK: Index
    public typealias Index = DictionaryIndex<Key, Value>
    public var startIndex: Index {
        return _dict.startIndex
    }
    public var endIndex: Index {
        return _dict.endIndex
    }
    public func index(after i: Index) -> Index {
        return _dict.index(after: i)
    }
    public func index(forKey key: Key) -> Index? {
        return _dict.index(forKey: key)
    }
    /// Returns the index for the given value.
    ///
    /// If the given value is found in the dictionary, this method returns an index
    /// into the dictionary that corresponds with the key-value pair.
    ///
    /// - parameter value: The value to find in the dictionary.
    /// - returns: The index for `value` and its associated key if `value` is in
    ///   the dictionary; otherwise, `nil`.
    public func index(forValue value: Value) -> Index? {
        if let key = self[value] as! Key? {
            return index(forKey: key)
        }
        return nil
    }
    public func index(where predicate: (Key, Value) throws -> Bool) rethrows -> Index? {
        do {
            return try _dict.index(where: predicate)
        } catch {
            throw error
        }
    }

    // MARK: Slice
    public func prefix(_ maxLength: Int) -> Slice<Dictionary<Key, Value>> {
        return _dict.prefix(maxLength)
    }
    public func suffix(_ maxLength: Int) -> Slice<Dictionary<Key, Value>> {
        return _dict.suffix(maxLength)
    }
    public func prefix(upTo end: Index) -> Slice<Dictionary<Key, Value>> {
        return _dict.prefix(upTo: end)
    }
    public func suffix(from start: Index) -> Slice<Dictionary<Key, Value>>{
        return _dict.suffix(from: start)
    }
    public func prefix(through position: Index) -> Slice<Dictionary<Key, Value>> {
        return _dict.prefix(through: position)
    }

    // MARK: Property
    public var indices: DefaultIndices<Dictionary<Key, Value>> {
        return _dict.indices
    }
    public var lazy: LazySequence<Dictionary<Key, Value>> {
        return _dict.lazy
    }
    public var underestimatedCount: Int {
        return _dict.underestimatedCount
    }

    // MARK: Accessor
    public subscript(position: Index) -> (key: Key, value: Value) {
        return _dict[position]
    }
    public subscript(bounds: ClosedRange<Index>) -> Slice<Dictionary<Key, Value>> {
        return _dict[bounds]
    }
    public func first(where predicate: (Key, Value) throws -> Bool) rethrows -> (key: Key, value: Value)? {
        return _dict.first
    }
    public func starts<PossiblePrefix>(with possiblePrefix: PossiblePrefix, by areEquivalent: ((key: Key, value: Value), (key: Key, value: Value)) throws -> Bool) rethrows -> Bool where PossiblePrefix : Sequence, PossiblePrefix.Iterator.Element == (key: Key, value: Value) {
        do {
            return try _dict.starts(with: possiblePrefix, by: areEquivalent)
        } catch {
            throw error
        }
    }
    public func elementsEqual<OtherSequence>(_ other: OtherSequence, by areEquivalent: ((key: Key, value: Value), (key: Key, value: Value)) throws -> Bool) rethrows -> Bool where OtherSequence : Sequence, OtherSequence.Iterator.Element == (key: Key, value: Value) {
        do {
            return try _dict.elementsEqual(other, by: areEquivalent)
        } catch {
            throw error
        }
    }
    public func lexicographicallyPrecedes<OtherSequence>(_ other: OtherSequence, by areInIncreasingOrder: ((key: Key, value: Value), (key: Key, value: Value)) throws -> Bool) rethrows -> Bool where OtherSequence : Sequence, OtherSequence.Iterator.Element == (key: Key, value: Value) {
        do {
            return try _dict.lexicographicallyPrecedes(other, by: areInIncreasingOrder)
        } catch {
            throw error
        }
    }
    public func contains(where predicate: (Key, Value) throws -> Bool) rethrows -> Bool {
        do {
            return try _dict.contains(where: predicate)
        } catch {
            throw error
        }
    }

    // MARK: Modify
    public mutating func remove(at index: Index) -> (key: Key, value: Value) {
        return _dict.remove(at: index)
    }
    public mutating func popFirst() -> (key: Key, value: Value)? {
        return _dict.popFirst()
    }
    public func dropFirst(_ n: Int) -> Slice<Dictionary<Key, Value>> {
        return _dict.dropFirst(n)
    }
    public func dropLast(_ n: Int) -> Slice<Dictionary<Key, Value>> {
        return _dict.dropLast(n)
    }
    public func dropFirst() -> Slice<Dictionary<Key, Value>> {
        return _dict.dropFirst()
    }
    public func dropLast() -> Slice<Dictionary<Key, Value>> {
        return _dict.dropLast()
    }

    // MARK: Transform
    public func sorted(by areInIncreasingOrder: ((key: Key, value: Value), (key: Key, value: Value)) -> Bool) -> [(key: Key, value: Value)] {
        return _dict.sorted(by: areInIncreasingOrder)
    }
    public func enumerated() -> EnumeratedSequence<Dictionary<Key, Value>> {
        return _dict.enumerated()
    }
    public func reversed() -> [(key: Key, value: Value)] {
        return _dict.reversed()
    }
    public func split(maxSplits: Int = .max, omittingEmptySubsequences: Bool = true, whereSeparator isSeparator: (Key, Value) throws -> Bool) rethrows -> [Slice<Dictionary<Key, Value>>] {
        do {
            return try _dict.split(maxSplits: maxSplits, omittingEmptySubsequences: omittingEmptySubsequences, whereSeparator: isSeparator)
        } catch {
            throw error
        }
    }

    // MARK: Iterate
    public func makeIterator() -> DictionaryIterator<Key, Value> {
        return _dict.makeIterator()
    }
    public func map<T>(_ transform: (Key, Value) throws -> T) rethrows -> [T] {
        do {
            return try _dict.map(transform)
        } catch {
            throw error
        }
    }
    public func filter(_ isIncluded: (Key, Value) throws -> Bool) rethrows -> [(key: Key, value: Value)] {
        do {
            return try _dict.filter(isIncluded)
        } catch {
            throw error
        }
    }
    public func forEach(_ body: (Key, Value) throws -> Void) rethrows {
        do {
            try _dict.forEach(body)
        } catch {
            throw error
        }
    }
    public func reduce<Result>(_ initialResult: Result, _ nextPartialResult: (Result, (key: Key, value: Value)) throws -> Result) rethrows -> Result {
        do {
            return try _dict.reduce(initialResult, nextPartialResult)
        } catch {
            throw error
        }
    }
    public func flatMap<SegmentOfResult : Sequence>(_ transform: (Key, Value) throws -> SegmentOfResult) rethrows -> [SegmentOfResult.Iterator.Element] {
        do {
            return try _dict.flatMap(transform)
        } catch {
            throw error
        }
    }
    public func flatMap<ElementOfResult>(_ transform: (Key, Value) throws -> ElementOfResult?) rethrows -> [ElementOfResult] {
        do {
            return try _dict.flatMap(transform)
        } catch {
            throw error
        }
    }
}

extension AZTwoWayDictionary : CustomStringConvertible, CustomDebugStringConvertible {
    /// A string that represents the contents of the dictionary.
    public var description: String { return _dict.description }
    /// A string that represents the contents of the dictionary, suitable for
    /// debugging.
    public var debugDescription: String { return "AZTwoWayDictionary(Bimap):\n\tContent: \(_dict.description)\n\tIs Key and Value of Same Type: \(isKVOfSameType)\n" }
}

main.swift

//
//  main.swift
//  BimapExample
//
//  Created by Apollo Zhu on 10/27/16.
//

/// Original written by @LiulietLee, 
/// published as https://github.com/LiulietLee/English-MorseCode-Translator
/// Adapted to use AZBiMap to demostrate its usage
class LLMorseCodeTranslator {
    let dict: AZBiMap<String, String> = [
        "a": ".-",
        "b": "-...",
        "c": "-.-.",
        "d": "-..",
        "e": ".",
        "f": "..-.",
        "g": "--.",
        "h": "....",
        "i": "..",
        "j": ".---",
        "k": "-.-",
        "l": ".-..",
        "m": "--",
        "n": "-.",
        "o": "---",
        "p": ".--.",
        "q": "--.-",
        "r": ".-.",
        "s": "...",
        "t": "-",
        "u": "..-",
        "v": "...-",
        "w": ".--",
        "x": "-..-",
        "y": "-.--",
        "z": "--..",
        "1": ".----",
        "2": "..---",
        "3": "...--",
        "4": "....-",
        "5": ".....",
        "6": "-....",
        "7": "--...",
        "8": "---..",
        "9": "----.",
        "0": "-----"
    ]

    public func englishToMorse(input: String) -> String {
        let arrayOfString = Array(input.characters)
        let translatedString = arrayOfString.reduce("") { $0 + ($1 == " " ? " " : (dict[String($1).lowercased()] as? String ?? "⊠")) + " "}
        return translatedString
    }

    func morseToEnglish(input: String) -> String {
        let arrayOfCode = spliteMorse(code: input)
        let translatedString = arrayOfCode.reduce("") { $0 +  ($1 == "  " ? " " : (dict[$1] as? String ?? "⊠"))}
        return translatedString
    }

    private func spliteMorse(code: String) -> [String] {
        var splitedCode = [String]()
        var temp = ""
        for single in code.characters {
            switch single {
            case ".", "-":
                temp += String(single)
            default:
                if temp != "" {
                    splitedCode += [temp]
                    temp = ""
                } else {
                    splitedCode += ["  "]
                }
            }
        }
        if temp != "" { splitedCode += [temp] }
        return splitedCode
    }
}

let translator = LLMorseCodeTranslator()
let code = translator.englishToMorse(input: "SOS!")
print(code, "<--->", translator.morseToEnglish(input: code))