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
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2021 - 2024 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
//
//===----------------------------------------------------------------------===//
#if !COLLECTIONS_SINGLE_MODULE
import InternalCollectionsUtilities
#endif
// `OrderedSet` does not directly conform to `SetAlgebra` because its definition
// of equality conflicts with `SetAlgebra` requirements. However, it still
// implements most `SetAlgebra` requirements (except `insert`, which is replaced
// by `append`).
//
// `OrderedSet` also provides an `unordered` view that explicitly conforms to
// `SetAlgebra`. That view implements `Equatable` by ignoring element order,
// so it can satisfy `SetAlgebra` requirements.
extension OrderedSet {
/// Returns a Boolean value that indicates whether the set is a strict subset
/// of the given set.
///
/// Set *A* is a strict subset of another set *B* if every member of *A* is
/// also a member of *B* and *B* contains at least one element that is not a
/// member of *A*. (Ignoring the order the elements appear in the sets.)
///
/// let a: OrderedSet = [1, 2, 3, 4]
/// let b: OrderedSet = [4, 2, 1]
/// b.isStrictSubset(of: a) // true
///
/// - Parameter other: Another set.
///
/// - Returns: `true` if `self` is a strict subset of `other`; otherwise,
/// `false`.
///
/// - Complexity: Expected to be O(`self.count`) on average, if `Element`
/// implements high-quality hashing.
@inlinable
public func isStrictSubset(of other: Self) -> Bool {
self.count < other.count && self.isSubset(of: other)
}
// Generalizations
/// Returns a Boolean value that indicates whether the set is a strict subset
/// of the given set.
///
/// Set *A* is a strict subset of another set *B* if every member of *A* is
/// also a member of *B* and *B* contains at least one element that is not a
/// member of *A*. (Ignoring the order the elements appear in the sets.)
///
/// let a: OrderedSet = [1, 2, 3, 4]
/// let b: OrderedSet = [4, 2, 1]
/// b.isStrictSubset(of: a.unordered) // true
///
/// - Parameter other: Another set.
///
/// - Returns: `true` if `self` is a strict subset of `other`; otherwise,
/// `false`.
///
/// - Complexity: Expected to be O(`self.count`) on average, if `Element`
/// implements high-quality hashing.
@inlinable
@inline(__always)
public func isStrictSubset(of other: UnorderedView) -> Bool {
isStrictSubset(of: other._base)
}
/// Returns a Boolean value that indicates whether the set is a strict subset
/// of the given set.
///
/// Set *A* is a strict subset of another set *B* if every member of *A* is
/// also a member of *B* and *B* contains at least one element that is not a
/// member of *A*. (Ignoring the order the elements appear in the sets.)
///
/// let a: Set = [1, 2, 3, 4]
/// let b: OrderedSet = [4, 2, 1]
/// b.isStrictSubset(of: a) // true
///
/// - Parameter other: Another set.
///
/// - Returns: `true` if `self` is a strict subset of `other`; otherwise,
/// `false`.
///
/// - Complexity: Expected to be O(`self.count`) on average, if `Element`
/// implements high-quality hashing.
@inlinable
public func isStrictSubset(of other: Set<Element>) -> Bool {
self.count < other.count && self.isSubset(of: other)
}
/// Returns a Boolean value that indicates whether the set is a strict subset
/// of the given sequence.
///
/// Set *A* is a strict subset of another set *B* if every member of *A* is
/// also a member of *B* and *B* contains at least one element that is not a
/// member of *A*. (Ignoring the order the elements appear in the sets.)
///
/// let a: Array = [1, 2, 3, 4]
/// let b: OrderedSet = [4, 2, 1]
/// b.isStrictSubset(of: a) // true
///
/// - Parameter other: A finite sequence of elements.
///
/// - Returns: `true` if `self` is a strict subset of `other`; otherwise,
/// `false`.
///
/// - Complexity: Expected to be O(`self.count` + *n*) on average, where *n*
/// is the number of elements in `other`, if `Element` implements
/// high-quality hashing.
@inlinable
public func isStrictSubset(
of other: some Sequence<Element>
) -> Bool {
if let other = _specialize(other, for: Self.self) {
return self.isStrictSubset(of: other)
}
if let other = _specialize(other, for: Set<Element>.self) {
return self.isStrictSubset(of: other)
}
var it = self.makeIterator()
guard let first = it.next() else {
return other.contains(where: { _ in true })
}
if let match = other._customContainsEquatableElement(first) {
// Fast path: the sequence has fast containment checks.
guard match else { return false }
while let item = it.next() {
guard other.contains(item) else { return false }
}
return !other.allSatisfy { self.contains($0) }
}
return _UnsafeBitSet.withTemporaryBitSet(capacity: count) { seen in
// Mark elements in `self` that we've seen in `other`.
var isKnownStrict = false
var c = 0
for item in other {
if let index = _find(item).index {
if seen.insert(index) {
c &+= 1
if c == self.count, isKnownStrict {
// We've seen enough.
return true
}
}
} else {
if !isKnownStrict, c == self.count { return true }
isKnownStrict = true
}
}
return false
}
}
}
|
