1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
|
//===------------------------- Multidictionary.swift ----------------------===//
//
// This source file is part of the Swift.org open source project
//
// Copyright (c) 2020-2021 Apple Inc. and the Swift project authors
// Licensed under Apache License v2.0 with Runtime Library Exception
//
// See https://swift.org/LICENSE.txt for license information
// See https://swift.org/CONTRIBUTORS.txt for the list of Swift project authors
//
//===----------------------------------------------------------------------===//
/// A collection that associates keys with one or more values.
@_spi(Testing) public struct Multidictionary<Key: Hashable, Value: Hashable>: Collection, Equatable {
private var forwardDictionary: Dictionary<Key, Set<Value>> = [:]
/// Reverse index used to make value removal more efficient.
private var reverseIndex: Dictionary<Value, Set<Key>> = [:]
public typealias Element = (Key, Set<Value>)
public typealias Index = Dictionary<Key, Set<Value>>.Index
public init() {}
/// The number of key-value pairs in this multi-dictionary.
public var count: Int {
self.forwardDictionary.count
}
/// The position of the first element in a nonempty multi-dictionary.
public var startIndex: Index {
self.forwardDictionary.startIndex
}
/// The collection’s “past the end” position—that is, the position one greater
/// than the last valid subscript argument.
public var endIndex: Index {
self.forwardDictionary.endIndex
}
/// Returns the index for the given key.
///
/// - Parameter key: The key to find in the multi-dictionary.
/// - Returns: The index for key and its associated value if key is in the
/// multi-dictionary; otherwise, nil.
public func index(forKey key: Key) -> Dictionary<Key, Set<Value>>.Index? {
self.forwardDictionary.index(forKey: key)
}
/// Computes the position immediately after the given index.
///
/// - Parameter i: A valid index of the collection. i must be less than endIndex.
/// - Returns: The position immediately after the given index.
@_spi(Testing) public func index(after i: Dictionary<Key, Set<Value>>.Index) -> Dictionary<Key, Set<Value>>.Index {
self.forwardDictionary.index(after: i)
}
@_spi(Testing) public subscript(position: Dictionary<Key, Set<Value>>.Index) -> (Key, Set<Value>) {
self.forwardDictionary[position]
}
/// A collection containing just the keys of this multi-dictionary.
public var keys: Dictionary<Key, Set<Value>>.Keys {
return self.forwardDictionary.keys
}
/// A collection containing just the values of this multi-dictionary.
public var values: Dictionary<Key, Set<Value>>.Values {
return self.forwardDictionary.values
}
/// Accesses the values associated with the given key for reading and writing.
public subscript(key: Key) -> Set<Value>? {
self.forwardDictionary[key]
}
/// Accesses the values associated with the given key for reading and writing.
///
/// If this multi-dictionary doesn’t contain the given key, accesses the
/// provided default value as if the key and default value existed in
/// this multi-dictionary.
public subscript(key: Key, default defaultValues: @autoclosure () -> Set<Value>) -> Set<Value> {
self.forwardDictionary[key, default: defaultValues()]
}
/// Returns a set of keys that the given value is associated with.
///
/// - Parameter v: The value to search for among the key-value associations in
/// this dictionary.
/// - Returns: The set of keys associated with the given value.
public func keysContainingValue(_ v: Value) -> Set<Key> {
return self.reverseIndex[v] ?? []
}
/// Inserts the given value in the set of values associated with the given key.
///
/// - Parameters:
/// - v: The value to insert.
/// - key: The key used to associate the given value with a set of elements.
/// - Returns: `true` if the value was not previously associated with any
/// other values for the given key. Else, returns `false.
@discardableResult
public mutating func insertValue(_ v: Value, forKey key: Key) -> Bool {
let inserted1 = self.reverseIndex[v, default: []].insert(key).inserted
let inserted2 = self.forwardDictionary[key, default: []].insert(v).inserted
assert(inserted1 == inserted2)
return inserted1
}
/// Removes the given value from the set of values associated with the given key.
///
/// - Parameters:
/// - v: The value to remove.
/// - key: The key used to associate the given value with a set of elements.
/// - Returns: The removed element, if any.
@discardableResult
public mutating func removeValue(_ v: Value, forKey key: Key) -> Value? {
let removedKey = self.reverseIndex[v]?.remove(key)
let removedVal = self.forwardDictionary[key]?.remove(v)
assert((removedKey == nil && removedVal == nil) ||
(removedKey != nil && removedVal != nil))
return removedVal
}
/// Removes all occurrences of the given value from all entries in this
/// multi-dictionary.
///
/// - Note: If this value is used as a key, this function does not erase its
/// entries from the underlying dictionary.
///
/// - Parameter v: The value to remove.
public mutating func removeOccurrences(of v: Value) {
for k in self.reverseIndex.removeValue(forKey: v) ?? [] {
self.forwardDictionary[k]!.remove(v)
}
assert(expensivelyCheckThatValueIsRemoved(v))
}
/// For assertions. Returns true `v` is removed from all `forwardDictionary` values.
private func expensivelyCheckThatValueIsRemoved(_ v: Value) -> Bool {
if self.reverseIndex[v] != nil {
return false
}
return !self.forwardDictionary.values.contains(where: { $0.contains(v) })
}
}
|
