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
|
/*
This source file is part of the Swift.org open source project
Copyright (c) 2014 - 2017 Apple Inc. and the Swift project authors
Licensed under Apache License v2.0 with Runtime Library Exception
See http://swift.org/LICENSE.txt for license information
See http://swift.org/CONTRIBUTORS.txt for Swift project authors
*/
/// An ordered set is an ordered collection of instances of `Element` in which
/// uniqueness of the objects is guaranteed.
public struct OrderedSet<E: Hashable>: Equatable, Collection {
public typealias Element = E
public typealias Index = Int
#if swift(>=4.1.50)
public typealias Indices = Range<Int>
#else
public typealias Indices = CountableRange<Int>
#endif
private var array: [Element]
private var set: Set<Element>
/// Creates an empty ordered set.
public init() {
self.array = []
self.set = Set()
}
/// Creates an ordered set with the contents of `array`.
///
/// If an element occurs more than once in `element`, only the first one
/// will be included.
public init(_ array: [Element]) {
self.init()
for element in array {
append(element)
}
}
// MARK: Working with an ordered set
/// The number of elements the ordered set stores.
public var count: Int { return array.count }
/// Returns `true` if the set is empty.
public var isEmpty: Bool { return array.isEmpty }
/// Returns the contents of the set as an array.
public var contents: [Element] { return array }
/// Returns `true` if the ordered set contains `member`.
public func contains(_ member: Element) -> Bool {
return set.contains(member)
}
/// Adds an element to the ordered set.
///
/// If it already contains the element, then the set is unchanged.
///
/// - returns: True if the item was inserted.
@discardableResult
public mutating func append(_ newElement: Element) -> Bool {
let inserted = set.insert(newElement).inserted
if inserted {
array.append(newElement)
}
return inserted
}
/// Remove and return the element at the beginning of the ordered set.
public mutating func removeFirst() -> Element {
let firstElement = array.removeFirst()
set.remove(firstElement)
return firstElement
}
/// Remove and return the element at the end of the ordered set.
public mutating func removeLast() -> Element {
let lastElement = array.removeLast()
set.remove(lastElement)
return lastElement
}
/// Remove all elements.
public mutating func removeAll(keepingCapacity keepCapacity: Bool) {
array.removeAll(keepingCapacity: keepCapacity)
set.removeAll(keepingCapacity: keepCapacity)
}
/// Remove the given element.
///
/// - returns: An element equal to member if member is contained in the set; otherwise, nil.
@discardableResult
public mutating func remove(_ element: Element) -> Element? {
let _removedElement = set.remove(element)
guard let removedElement = _removedElement else { return nil }
let idx = array.firstIndex(of: element)!
array.remove(at: idx)
return removedElement
}
}
extension OrderedSet: ExpressibleByArrayLiteral {
/// Create an instance initialized with `elements`.
///
/// If an element occurs more than once in `element`, only the first one
/// will be included.
public init(arrayLiteral elements: Element...) {
self.init(elements)
}
}
extension OrderedSet: RandomAccessCollection {
public var startIndex: Int { return contents.startIndex }
public var endIndex: Int { return contents.endIndex }
public subscript(index: Int) -> Element {
return contents[index]
}
}
public func == <T>(lhs: OrderedSet<T>, rhs: OrderedSet<T>) -> Bool {
return lhs.contents == rhs.contents
}
extension OrderedSet: Hashable where Element: Hashable { }
extension OrderedSet: Sendable where Element: Sendable { }
|
