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
|
//===----------------------------------------------------------------------===//
//
// This source file is part of the Swift Collections open source project
//
// Copyright (c) 2022 - 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 TreeSet: SetAlgebra {
/// Returns a Boolean value that indicates whether the given element exists
/// in the set.
///
/// - Parameter element: An element to look for in the set.
///
/// - Returns: `true` if `element` exists in the set; otherwise, `false`.
///
/// - Complexity: This operation is expected to perform O(1) hashing and
/// comparison operations on average, provided that `Element` implements
/// high-quality hashing.
@inlinable
public func contains(_ item: Element) -> Bool {
_root.containsKey(.top, item, _Hash(item))
}
/// Insert a new member to this set, if the set doesn't already contain it.
///
/// Inserting a new member invalidates all existing indices of the collection.
///
/// - Parameter newMember: The element to insert into the set.
///
/// - Returns: `(true, newMember)` if `newMember` was not contained in the
/// set. If an element equal to `newMember` was already contained in the
/// set, the method returns `(false, oldMember)`, where `oldMember` is the
/// element that was equal to `newMember`. In some cases, `oldMember` may
/// be distinguishable from `newMember` by identity comparison or some
/// other means.
///
/// - Complexity: This operation is expected to copy at most O(log(`count`))
/// existing members and to perform at most O(1) hashing/comparison
/// operations on the `Element` type, as long as `Element` properly
/// implements hashing.
@discardableResult
@inlinable
public mutating func insert(
_ newMember: __owned Element
) -> (inserted: Bool, memberAfterInsert: Element) {
defer { _fixLifetime(self) }
let hash = _Hash(newMember)
let r = _root.insert(.top, (newMember, ()), hash)
if r.inserted {
_invalidateIndices()
return (true, newMember)
}
return _UnsafeHandle.read(r.leaf) {
(false, $0[item: r.slot].key)
}
}
@discardableResult
@inlinable
internal mutating func _insert(_ newMember: __owned Element) -> Bool {
let hash = _Hash(newMember)
let r = _root.insert(.top, (newMember, ()), hash)
return r.inserted
}
/// Removes the given element from the set.
///
/// Removing an existing member invalidates all existing indices of the
/// collection.
///
/// - Parameter member: The element of the set to remove.
///
/// - Returns: The element equal to `member` if `member` is contained in the
/// set; otherwise, `nil`. In some cases, the returned element may be
/// distinguishable from `newMember` by identity comparison or some other
/// means.
///
/// - Complexity: This operation is expected to copy at most O(log(`count`))
/// existing members and to perform at most O(1) hashing/comparison
/// operations on the `Element` type, as long as `Element` properly
/// implements hashing.
@discardableResult
@inlinable
public mutating func remove(_ member: Element) -> Element? {
let hash = _Hash(member)
guard let r = _root.remove(.top, member, hash) else { return nil }
_invalidateIndices()
assert(r.remainder == nil)
return r.removed.key
}
/// Inserts the given element into the set unconditionally.
///
/// If an element equal to `newMember` is already contained in the set,
/// `newMember` replaces the existing element.
///
/// If `newMember` was not already a member, it gets inserted.
///
/// - Parameter newMember: An element to insert into the set.
///
/// - Returns: The original member equal to `newMember` if the set already
/// contained such a member; otherwise, `nil`. In some cases, the returned
/// element may be distinguishable from `newMember` by identity comparison
/// or some other means.
///
/// - Complexity: This operation is expected to copy at most O(log(`count`))
/// existing members and to perform at most O(1) hashing/comparison
/// operations on the `Element` type, as long as `Element` properly
/// implements hashing.
@discardableResult
@inlinable
public mutating func update(with newMember: __owned Element) -> Element? {
defer { _fixLifetime(self) }
let hash = _Hash(newMember)
let r = _root.updateValue(.top, forKey: newMember, hash) {
$0.initialize(to: (newMember, ()))
}
if r.inserted { return nil }
return _UnsafeHandle.update(r.leaf) {
let p = $0.itemPtr(at: r.slot)
let old = p.move().key
p.initialize(to: (newMember, ()))
return old
}
}
}
|
