8000 Migrated over to Swift 3 · lina1/swift-algorithm-club@3945383 · GitHub
[go: up one dir, main page]
Skip to content

Commit 3945383

Browse files
kelvinlauKLkelvinlauKL
committed
Migrated over to Swift 3
1 parent 9035cdd commit 3945383

File tree

5 files changed

+61
-53
lines changed

5 files changed

+61
-53
lines changed

‎Heap/Heap.swift

Lines changed: 28 additions & 28 deletions
Original file line numberDiff line numberDiff line change
@@ -8,14 +8,14 @@ public struct Heap<T> {
88
var elements = [T]()
99

1010
/** Determines whether this is a max-heap (>) or min-heap (<). */
11-
private var isOrderedBefore: (T, T) -> Bool
11+
fileprivate var isOrderedBefore: (T, T) -> Bool
1212

1313
/**
1414
* Creates an empty heap.
1515
* The sort function determines whether this is a min-heap or max-heap.
1616
* For integers, > makes a max-heap, < makes a min-heap.
1717
*/
18-
public init(sort: (T, T) -> Bool) {
18+
public init(sort: @escaping (T, T) -> Bool) {
1919
self.isOrderedBefore = sort
2020
}
2121

@@ -24,9 +24,9 @@ public struct Heap<T> {
2424
* the elements are inserted into the heap in the order determined by the
2525
* sort function.
2626
*/
27-
public init(array: [T], sort: (T, T) -> Bool) {
27+
public init(array: [T], sort: @escaping (T, T) -> Bool) {
2828
self.isOrderedBefore = sort
29-
buildHeap(array)
29+
buildHeap(fromArray: array)
3030
}
3131

3232
/*
@@ -43,9 +43,9 @@ public struct Heap<T> {
4343
* Converts an array to a max-heap or min-heap in a bottom-up manner.
4444
* Performance: This runs pretty much in O(n).
4545
*/
46-
private mutating func buildHeap(array: [T]) {
46+
fileprivate mutating func buildHeap(fromArray array: [T]) {
4747
elements = array
48-
for i in (elements.count/2 - 1).stride(through: 0, by: -1) {
48+
for i in stride(from: (elements.count/2 - 1), through: 0, by: -1) {
4949
shiftDown(index: i, heapSize: elements.count)
5050
}
5151
}
@@ -62,7 +62,7 @@ public struct Heap<T> {
6262
* Returns the index of the parent of the element at index i.
6363
* The element at index 0 is the root of the tree and has no parent.
6464
*/
65-
@inline(__always) func indexOfParent(i: Int) -> Int {
65+
@inline(__always) func parentIndex(ofIndex i: Int) -> Int {
6666
return (i - 1) / 2
6767
}
6868

@@ -71,7 +71,7 @@ public struct Heap<T> {
7171
* Note that this index can be greater than the heap size, in which case
7272
* there is no left child.
7373
*/
74-
@inline(__always) func indexOfLeftChild(i: Int) -> Int {
74+
@inline(__always) func leftChildIndex(ofIndex i: Int) -> Int {
7575
return 2*i + 1
7676
}
7777

@@ -80,7 +80,7 @@ public struct Heap<T> {
8080
* Note that this index can be greater than the heap size, in which case
8181
* there is no right child.
8282
*/
83-
@inline(__always) func indexOfRightChild(i: Int) -> Int {
83+
@inline(__always) func rightChildIndex(ofIndex i: Int) -> Int {
8484
return 2*i + 2
8585
}
8686

@@ -96,12 +96,12 @@ public struct Heap<T> {
9696
* Adds a new value to the heap. This reorders the heap so that the max-heap
9797
* or min-heap property still holds. Performance: O(log n).
9898
*/
99-
public mutating func insert(value: T) {
99+
public mutating func insert(_ value: T) {
100100
elements.append(value)
101101
shiftUp(index: elements.count - 1)
102102
}
103103

104-
public mutating func insert<S: SequenceType where S.Generator.Element == T>(sequence: S) {
104+
public mutating func insert<S: Sequence>(_ sequence: S) where S.Iterator.Element == T {
105105
for value in sequence {
106106
insert(value)
107107
}
@@ -123,7 +123,7 @@ public struct Heap<T> {
123123
* Removes the root node from the heap. For a max-heap, this is the maximum
124124
* value; for a min-heap it is the minimum value. Performance: O(log n).
125125
*/
126-
public mutating func remove() -> T? {
126+
@discardableResult public mutating func remove() -> T? {
127127
if elements.isEmpty {
128128
return nil
129129
} else if elements.count == 1 {
@@ -142,14 +142,14 @@ public struct Heap<T> {
142142
* Removes an arbitrary node from the heap. Performance: O(log n). You need
143143
* to know the node's index, which may actually take O(n) steps to find.
144144
*/
145-
public mutating func removeAtIndex(i: Int) -> T? {
146-
guard i < elements.count else { return nil }
145+
public mutating func removeAt(index: Int) -> T? {
146+
guard index < elements.count else { return nil }
147147

148148
let size = elements.count - 1
149-
if i != size {
150-
swap(&elements[i], &elements[size])
151-
shiftDown(index: i, heapSize: size)
152-
shiftUp(index: i)
149+
if index != size {
150+
swap(&elements[index], &elements[size])
151+
shiftDown(index: index, heapSize: size)
152+
shiftUp(index: index)
153153
}
154154
return elements.removeLast()
155155
}
@@ -158,15 +158,15 @@ public struct Heap<T> {
158158
* Takes a child node and looks at its parents; if a parent is not larger
159159
* (max-heap) or not smaller (min-heap) than the child, we exchange them.
160160
*/
161-
mutating func shiftUp(index index: Int) {
161+
mutating func shiftUp(index: Int) {
162162
var childIndex = index
163163
let child = elements[childIndex]
164-
var parentIndex = indexOfParent(childIndex)
164+
var parentIndex = self.parentIndex(ofIndex: childIndex)
165165

166166
while childIndex > 0 && isOrderedBefore(child, elements[parentIndex]) {
167167
elements[childIndex] = elements[parentIndex]
168168
childIndex = parentIndex
169-
parentIndex = indexOfParent(childIndex)
169+
parentIndex = self.parentIndex(ofIndex: childIndex)
170170
}
171171

172172
elements[childIndex] = child
@@ -180,11 +180,11 @@ public struct Heap<T> {
180180
* Looks at a parent node and makes sure it is still larger (max-heap) or
181181
* smaller (min-heap) than its childeren.
182182
*/
183-
mutating func shiftDown(index index: Int, heapSize: Int) {
183+
mutating func shiftDown(index: Int, heapSize: Int) {
184184
var parentIndex = index
185185

186186
while true {
187-
let leftChildIndex = indexOfLeftChild(parentIndex)
187+
let leftChildIndex = self.leftChildIndex(ofIndex: parentIndex)
188188
let rightChildIndex = leftChildIndex + 1
189189

190190
// Figure out which comes first if we order them by the sort function:
@@ -212,16 +212,16 @@ extension Heap where T: Equatable {
212212
/**
213213
* Searches the heap for the given element. Performance: O(n).
214214
*/
215-
public func indexOf(element: T) -> Int? {
216-
return indexOf(element, 0)
215+
public func index(of element: T) -> Int? {
216+
return index(of: element, 0)
217217
}
218218

219-
private func indexOf(element: T, _ i: Int) -> Int? {
219+
fileprivate func index(of element: T, _ i: Int) -> Int? {
220220
if i >= count { return nil }
221221
if isOrderedBefore(element, elements[i]) { return nil }
222222
if element == elements[i] { return i }
223-
if let j = indexOf(element, indexOfLeftChild(i)) { return j }
224-
if let j = indexOf(element, indexOfRightChild(i)) { return j }
223+
if let j = index(of: element, self.leftChildIndex(ofIndex: i)) { return j }
224+
if let j = index(of: element, self.rightChildIndex(ofIndex: i)) { return j }
225225
return nil
226226
}
227227
}

‎Heap/README.markdown

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -260,7 +260,7 @@ It can be convenient to convert an array into a heap. This just shuffles the arr
260260
In code it would look like this:
261261

262262
```swift
263-
private mutating func buildHeap(array: [T]) {
263+
private mutating func buildHeap(fromArray array: [T]) {
264264
for value in array {
265265
insert(value)
266266
}
@@ -274,7 +274,7 @@ If you didn't gloss over the math section, you'd have seen that for any heap the
274274
In code:
275275

276276
```swift
277-
private mutating func buildHeap(array: [T]) {
277+
private mutating func buildHeap(fromArray array: [T]) {
278278
elements = array
279279
for i in (elements.count/2 - 1).stride(through: 0, by: -1) {
280280
shiftDown(index: i, heapSize: elements.count)

‎Heap/Tests/HeapTests.swift

Lines changed: 21 additions & 21 deletions
Original file line numberDiff line numberDiff line change
@@ -7,38 +7,38 @@ import XCTest
77

88
class HeapTests: XCTestCase {
99

10-
private func verifyMaxHeap(h: Heap<Int>) -> Bool {
10+
fileprivate func verifyMaxHeap(_ h: Heap<Int>) -> Bool {
1111
for i in 0..<h.count {
12-
let left = h.indexOfLeftChild(i)
13-
let right = h.indexOfRightChild(i)
14-
let parent = h.indexOfParent(i)
12+
let left = h.leftChildIndex(ofIndex: i)
13+
let right = h.rightChildIndex(ofIndex: i)
14+
let parent = h.parentIndex(ofIndex: i)
1515
if left < h.count && h.elements[i] < h.elements[left] { return false }
1616
if right < h.count && h.elements[i] < h.elements[right] { return false }
1717
if i > 0 && h.elements[parent] < h.elements[i] { return false }
1818
}
1919
return true
2020
}
2121

22-
private func verifyMinHeap(h: Heap<Int>) -> Bool {
22+
fileprivate func verifyMinHeap(_ h: Heap<Int>) -> Bool {
2323
for i in 0..<h.count {
24-
let left = h.indexOfLeftChild(i)
25-
let right = h.indexOfRightChild(i)
26-
let parent = h.indexOfParent(i)
24+
let left = h.leftChildIndex(ofIndex: i)
25+
let right = h.rightChildIndex(ofIndex: i)
26+
let parent = h.parentIndex(ofIndex: i)
2727
if left < h.count && h.elements[i] > h.elements[left] { return false }
2828
if right < h.count && h.elements[i] > h.elements[right] { return false }
2929
if i > 0 && h.elements[parent] > h.elements[i] { return false }
3030
}
3131
return true
3232
}
3333

34-
private func isPermutation(array1: [Int], _ array2: [Int]) -> Bool {
34+
fileprivate func isPermutation(_ array1: [Int], _ array2: [Int]) -> Bool {
3535
var a1 = array1
3636
var a2 = array2
3737
if a1.count != a2.count { return false }
3838
while a1.count > 0 {
39-
if let i = a2.indexOf(a1[0]) {
40-
a1.removeAtIndex(0)
41-
a2.removeAtIndex(i)
39+
if let i = a2.index(of: a1[0]) {
40+
a1.remove(at: 0)
41+
a2.remove(at: i)
4242
} else {
4343
return false
4444
}
@@ -161,7 +161,7 @@ class HeapTests: XCTestCase {
161161
XCTAssertEqual(heap.elements, [1, 1, 1, 1, 1])
162162
}
163163

164-
private func randomArray(n: Int) -> [Int] {
164+
fileprivate func randomArray(_ n: Int) -> [Int] {
165165
var a = [Int]()
166166
for _ in 0..<n {
167167
a.append(Int(arc4random()))
@@ -197,27 +197,27 @@ class HeapTests: XCTestCase {
197197
XCTAssertEqual(h.elements, [100, 50, 70, 10, 20, 60, 65])
198198

199199
//test index out of bounds
200-
let v = h.removeAtIndex(10)
200+
let v = h.removeAt(index: 10)
201201
XCTAssertEqual(v, nil)
202202
XCTAssertTrue(verifyMaxHeap(h))
203203
XCTAssertEqual(h.elements, [100, 50, 70, 10, 20, 60, 65])
204204

205-
let v1 = h.removeAtIndex(5)
205+
let v1 = h.removeAt(index: 5)
206206
XCTAssertEqual(v1, 60)
207207
XCTAssertTrue(verifyMaxHeap(h))
208208
XCTAssertEqual(h.elements, [100, 50, 70, 10, 20, 65])
209209

210-
let v2 = h.removeAtIndex(4)
210+
let v2 = h.removeAt(index: 4)
211211
XCTAssertEqual(v2, 20)
212212
XCTAssertTrue(verifyMaxHeap(h))
213213
XCTAssertEqual(h.elements, [100, 65, 70, 10, 50])
214214

215-
let v3 = h.removeAtIndex(4)
215+
let v3 = h.removeAt(index: 4)
216216
XCTAssertEqual(v3, 50)
217217
XCTAssertTrue(verifyMaxHeap(h))
218218
XCTAssertEqual(h.elements, [100, 65, 70, 10])
219219

220-
let v4 = h.removeAtIndex(0)
220+
let v4 = h.removeAt(index: 0)
221221
XCTAssertEqual(v4, 100)
222222
XCTAssertTrue(verifyMaxHeap(h))
223223
XCTAssertEqual(h.elements, [70, 65, 10])
@@ -270,9 +270,9 @@ class HeapTests: XCTestCase {
270270
let m = (n + 1)/2
271271
for k in 1...m {
272272
let i = Int(arc4random_uniform(UInt32(n - k + 1)))
273-
let v = h.removeAtIndex(i)!
274-
let j = a.indexOf(v)!
275-
a.removeAtIndex(j)
273+
let v = h.removeAt(index: i)!
274+
let j = a.index(of: v)!
275+
a.remove(at: j)
276276

277277
XCTAssertTrue(verifyMaxHeap(h))
278278
XCTAssertEqual(h.count, a.count)

‎Heap/Tests/Tests.xcodeproj/project.pbxproj

Lines changed: 9 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -83,11 +83,12 @@
8383
isa = PBXProject;
8484
attributes = {
8585
LastSwiftUpdateCheck = 0720;
86-
LastUpgradeCheck = 0720;
86+
LastUpgradeCheck = 0800;
8787
ORGANIZATIONNAME = "Swift Algorithm Club";
8888
TargetAttributes = {
8989
7B2BBC7F1C779D720067B71D = {
9090
CreatedOnToolsVersion = 7.2;
91+
LastSwiftMigration = 0800;
9192
};
9293
};
9394
};
@@ -145,8 +146,10 @@
145146
CLANG_WARN_DIRECT_OBJC_ISA_USAGE = YES_ERROR;
146147
CLANG_WARN_EMPTY_BODY = YES;
147148
CLANG_WARN_ENUM_CONVERSION = YES;
149+
CLANG_WARN_INFINITE_RECURSION = YES;
148150
CLANG_WARN_INT_CONVERSION = YES;
149151
CLANG_WARN_OBJC_ROOT_CLASS = YES_ERROR;
152+
CLANG_WARN_SUSPICIOUS_MOVE = YES;
150153
CLANG_WARN_UNREACHABLE_CODE = YES;
151154
CLANG_WARN__DUPLICATE_METHOD_MATCH = YES;
152155
CODE_SIGN_IDENTITY = "-";
@@ -189,8 +192,10 @@
189192
CLANG_WARN_DIRECT_OBJC_ISA_USAGE = YES_ERROR;
190193
CLANG_WARN_EMPTY_BODY = YES;
191194
CLANG_WARN_ENUM_CONVERSION = YES;
195+
CLANG_WARN_INFINITE_RECURSION = YES;
192196
CLANG_WARN_INT_CONVERSION = YES;
193197
CLANG_WARN_OBJC_ROOT_CLASS = YES_ERROR;
198+
CLANG_WARN_SUSPICIOUS_MOVE = YES;
194199
CLANG_WARN_UNREACHABLE_CODE = YES;
195200
CLANG_WARN__DUPLICATE_METHOD_MATCH = YES;
196201
CODE_SIGN_IDENTITY = "-";
@@ -209,6 +214,7 @@
209214
MACOSX_DEPLOYMENT_TARGET = 10.11;
210215
MTL_ENABLE_DEBUG_INFO = NO;
211216
SDKROOT = macosx;
217+
SWIFT_OPTIMIZATION_LEVEL = "-Owholemodule";
212218
};
213219
name = Release;
214220
};
@@ -220,6 +226,7 @@
220226
LD_RUNPATH_SEARCH_PATHS = "$(inherited) @executable_path/../Frameworks @loader_path/../Frameworks";
221227
PRODUCT_BUNDLE_IDENTIFIER = swift.algorithm.club.Tests;
222228
PRODUCT_NAME = "$(TARGET_NAME)";
229+
SWIFT_VERSION = 3.0;
223230
};
224231
name = Debug;
225232
};
@@ -231,6 +238,7 @@
231238
LD_RUNPATH_SEARCH_PATHS = "$(inherited) @executable_path/../Frameworks @loader_path/../Frameworks";
232239
PRODUCT_BUNDLE_IDENTIFIER = swift.algorithm.club.Tests;
233240
PRODUCT_NAME = "$(TARGET_NAME)";
241+
SWIFT_VERSION = 3.0;
234242
};
235243
name = Release;
236244
};

‎Heap/Tests/Tests.xcodeproj/xcshareddata/xcschemes/Tests.xcscheme

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,6 @@
11
<?xml version="1.0" encoding="UTF-8"?>
22
<Scheme
3-
LastUpgradeVersion = "0720"
3+
LastUpgradeVersion = "0800"
44
version = "1.3">
55
<BuildAction
66
parallelizeBuildables = "YES"

0 commit comments

Comments
 (0)
0