mirror of
https://github.com/apple/swift-collections
synced 2026-11-22 04:20:40 +00:00
137 lines
5.1 KiB
Swift
137 lines
5.1 KiB
Swift
//===----------------------------------------------------------------------===//
|
|
//
|
|
// This source file is part of the Swift Collections open source project
|
|
//
|
|
// Copyright (c) 2022 - 2026 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
|
|
//
|
|
// SPDX-License-Identifier: Apache-2.0 WITH Swift-exception
|
|
//
|
|
//===----------------------------------------------------------------------===//
|
|
|
|
#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 item: An element to look for in the set.
|
|
///
|
|
/// - Returns: `true` if `item` 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 = unsafe _root.insert(.top, (newMember, ()), hash)
|
|
if unsafe r.inserted {
|
|
_invalidateIndices()
|
|
return (true, newMember)
|
|
}
|
|
return unsafe _UnsafeHandle.read(r.leaf) {
|
|
unsafe (false, $0[item: r.slot].key)
|
|
}
|
|
}
|
|
|
|
@discardableResult
|
|
@inlinable
|
|
internal mutating func _insert(_ newMember: __owned Element) -> Bool {
|
|
let hash = _Hash(newMember)
|
|
let r = unsafe _root.insert(.top, (newMember, ()), hash)
|
|
return unsafe 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 = unsafe _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 = unsafe _root.updateValue(.top, forKey: newMember, hash) {
|
|
unsafe $0.initialize(to: (newMember, ()))
|
|
}
|
|
if unsafe r.inserted { return nil }
|
|
return unsafe _UnsafeHandle.update(r.leaf) {
|
|
let p = unsafe $0.itemPtr(at: r.slot)
|
|
let old = unsafe p.move().key
|
|
unsafe p.initialize(to: (newMember, ()))
|
|
return old
|
|
}
|
|
}
|
|
}
|