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
|
//===----------------------------------------------------------------------===//
//
// 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
extension BitSet {
/// Returns a Boolean value that indicates whether this bit 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*.
///
/// let a: BitSet = [1, 2, 3, 4]
/// let b: BitSet = [1, 2, 4]
/// let c: BitSet = [0, 1]
/// a.isStrictSubset(of: a) // false
/// b.isStrictSubset(of: a) // true
/// c.isStrictSubset(of: a) // false
///
/// - Parameter other: Another bit set.
///
/// - Returns: `true` if the set is a strict subset of `other`;
/// otherwise, `false`.
///
/// - Complexity: O(*max*), where *max* is the largest item in `self`.
public func isStrictSubset(of other: Self) -> Bool {
self._read { first in
other._read { second in
let w1 = first._words
let w2 = second._words
if w1.count > w2.count {
return false
}
var strict = w1.count < w2.count
for i in 0 ..< w1.count {
if !w1[i].subtracting(w2[i]).isEmpty {
return false
}
strict = strict || w1[i] != w2[i]
}
return strict
}
}
}
/// Returns a Boolean value that indicates whether this bit 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*.
///
/// - Parameter other: A counted bit set.
///
/// - Returns: `true` if the set is a strict subset of `other`;
/// otherwise, `false`.
///
/// - Complexity: O(*max*), where *max* is the largest item in `self`.
public func isStrictSubset(of other: BitSet.Counted) -> Bool {
isStrictSubset(of: other._bits)
}
/// Returns a Boolean value that indicates whether this 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*.
///
/// let b: BitSet = [0, 1, 2]
/// let c: BitSet = [2, 3, 4]
/// b.isStrictSubset(of: -10 ..< 4) // true
/// c.isStrictSubset(of: -10 ..< 4) // false
///
/// - Parameter other: An arbitrary range of integers.
///
/// - Returns: `true` if the set is a strict subset of `other`;
/// otherwise, `false`.
///
/// - Complexity: O(*max*), where *max* is the largest item in `self`.
public func isStrictSubset(of other: Range<Int>) -> Bool {
isSubset(of: other) && !isSuperset(of: other)
}
/// Returns a Boolean value that indicates whether this bit set is a strict
/// subset of the values in a given sequence of integers.
///
/// 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*.
///
/// let a = [1, 2, 3, 4, -10]
/// let b: BitSet = [1, 2, 4]
/// let c: BitSet = [0, 1]
/// b.isStrictSubset(of: a) // true
/// c.isStrictSubset(of: a) // false
///
/// - Parameter other: A sequence of arbitrary integers.
///
/// - Returns: `true` if the set is a strict subset of `other`;
/// otherwise, `false`.
///
/// - Complexity: O(*max*) + *k*, where *max* is the largest item in `self`,
/// and *k* is the complexity of iterating over all elements in `other`.
@inlinable
public func isStrictSubset(of other: some Sequence<Int>) -> Bool {
if let other = _specialize(other, for: BitSet.self) {
return isStrictSubset(of: other)
}
if let other = _specialize(other, for: BitSet.Counted.self) {
return isStrictSubset(of: other)
}
if let other = _specialize(other, for: Range<Int>.self) {
return isStrictSubset(of: other)
}
if isEmpty {
var it = other.makeIterator()
return it.next() != nil
}
let selfCount = self.count
return _UnsafeHandle.withTemporaryBitSet(
wordCount: _storage.count
) { seen in
var strict = false
var it = other.makeIterator()
var c = 0
while let i = it.next() {
guard self.contains(i) else {
strict = true
continue
}
if seen.insert(UInt(i)) {
c &+= 1
if c == selfCount {
while !strict, let i = it.next() {
strict = !self.contains(i)
}
return strict
}
}
}
assert(c < selfCount)
return false
}
}
}
|
