71 lines
1.8 KiB
Swift
71 lines
1.8 KiB
Swift
//
|
|
// Copyright 2020 Signal Messenger, LLC
|
|
// SPDX-License-Identifier: AGPL-3.0-only
|
|
//
|
|
|
|
import Foundation
|
|
|
|
public struct OrderedSet<Element> where Element: Hashable {
|
|
public private(set) var orderedMembers: [Element] = []
|
|
public private(set) var unorderedMembers: Set<Element> = []
|
|
|
|
/// - Complexity: O(n)
|
|
public init(_ members: [Element]) {
|
|
unorderedMembers = []
|
|
orderedMembers = []
|
|
|
|
for element in members {
|
|
append(element)
|
|
}
|
|
}
|
|
|
|
/// - Complexity: O(1) on average
|
|
@discardableResult
|
|
public mutating func append(_ element: Element) -> (Bool, Element) {
|
|
let (wasInserted, elementAfterInsert) = unorderedMembers.insert(element)
|
|
|
|
if wasInserted {
|
|
orderedMembers.append(element)
|
|
}
|
|
|
|
return (wasInserted, elementAfterInsert)
|
|
}
|
|
|
|
/// - Complexity: O(n)
|
|
public mutating func remove(_ element: Element) {
|
|
if let removedMember = unorderedMembers.remove(element) {
|
|
orderedMembers.removeAll(where: { $0 == removedMember })
|
|
}
|
|
}
|
|
|
|
/// - Complexity: O(1)
|
|
public func contains(_ element: Element) -> Bool {
|
|
return unorderedMembers.contains(element)
|
|
}
|
|
|
|
/// - Complexity: O(1)
|
|
public var isEmpty: Bool {
|
|
return unorderedMembers.isEmpty
|
|
}
|
|
|
|
/// - Complexity: O(1)
|
|
public var count: Int {
|
|
return unorderedMembers.count
|
|
}
|
|
|
|
/// - Complexity: O(1)
|
|
public var first: Element? {
|
|
return orderedMembers.first
|
|
}
|
|
|
|
// TODO: I only implemented the minimum API that I needed. There's lots more that could
|
|
// reasonably be added to an OrderedSet (union, etc.)
|
|
}
|
|
|
|
extension OrderedSet: ExpressibleByArrayLiteral {
|
|
public typealias ArrayLiteralElement = Element
|
|
public init(arrayLiteral elements: Element...) {
|
|
self.init(elements)
|
|
}
|
|
}
|