8000 Merge pull request #195 from chris-pilcher/bloom-filter-swift3 · lency/swift-algorithm-club@438f391 · GitHub
[go: up one dir, main page]
Skip to content < 10000 link crossorigin="anonymous" media="all" rel="stylesheet" href="https://github.githubassets.com/assets/keyboard-shortcuts-dialog.f8fba3bd67fe74f9227b.module.css" />

Commit 438f391

Browse files
author
Chris Pilcher
authored
Merge pull request kodecocodes#195 from chris-pilcher/bloom-filter-swift3
Updating Bloom Filter to Swift 3
2 parents c2473df + e6cfec4 commit 438f391

File tree

7 files changed

+80
-72
lines changed

7 files changed

+80
-72
lines changed

‎.travis.yml

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -13,7 +13,7 @@ script:
1313
- xcodebuild test -project ./AVL\ Tree/Tests/Tests.xcodeproj -scheme Tests
1414
- xcodebuild test -project ./Binary\ Search/Tests/Tests.xcodeproj -scheme Tests
1515
# - xcodebuild test -project ./Binary\ Search\ Tree/Solution\ 1/Tests/Tests.xcodeproj -scheme Tests
16-
# - xcodebuild test -project ./Bloom\ Filter/Tests/Tests.xcodeproj -scheme Tests
16+
- xcodebuild test -project ./Bloom\ Filter/Tests/Tests.xcodeproj -scheme Tests
1717
# - xcodebuild test -project ./Bounded\ Priority\ Queue/Tests/Tests.xcodeproj -scheme Tests
1818
# - xcodebuild test -project ./Breadth-First\ Search/Tests/Tests.xcodeproj -scheme Tests
1919
# - xcodebuild test -project ./Bucket\ Sort/Tests/Tests.xcodeproj -scheme Tests

‎Bloom Filter/BloomFilter.playground/Contents.swift

Lines changed: 9 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -1,31 +1,31 @@
11
//: Playground - noun: a place where people can play
22

33
public class BloomFilter<T> {
4-
private var array: [Bool]
5-
private var hashFunctions: [T -> Int]
4+
fileprivate var array: [Bool]
5+
private var hashFunctions: [(T) -> Int]
66

7-
public init(size: Int = 1024, hashFunctions: [T -> Int]) {
8-
self.array = .init(count: size, repeatedValue: false)
7+
public init(size: Int = 1024, hashFunctions: [(T) -> Int]) {
8+
self.array = [Bool](repeating: false, count: size)
99
self.hashFunctions = hashFunctions
1010
}
1111

12-
private func computeHashes(value: T) -> [Int] {
12+
private func computeHashes(_ value: T) -> [Int] {
1313
return hashFunctions.map() { hashFunc in abs(hashFunc(value) % array.count) }
1414
}
1515

16-
public func insert(element: T) {
16+
public func insert(_ element: T) {
1717
for hashValue in computeHashes(element) {
1818
array[hashValue] = true
1919
}
2020
}
2121

22-
public func insert(values: [T]) {
22+
public func insert(_ values: [T]) {
2323
for value in values {
2424
insert(value)
2525
}
2626
}
2727

28-
public func query(value: T) -> Bool {
28+
public func query(_ value: T) -> Bool {
2929
let hashValues = computeHashes(value)
3030

3131
// Map hashes to indices in the Bloom Filter
@@ -37,7 +37,7 @@ public class BloomFilter<T> {
3737
// only that it may be. If the query returns false, however,
3838
// you can be certain that the value was not added.
3939

40-
let exists = results.reduce(true, combine: { $0 && $1 })
40+
let exists = results.reduce(true, { $0 && $1 })
4141
return exists
4242
}
4343

‎Bloom Filter/BloomFilter.swift

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -1,29 +1,29 @@
11
public class BloomFilter<T> {
22
private var array: [Bool]
3-
private var hashFunctions: [T -> Int]
3+
private var hashFunctions: [(T) -> Int]
44

5-
public init(size: Int = 1024, hashFunctions: [T -> Int]) {
6-
self.array = .init(count: size, repeatedValue: false)
5+
public init(size: Int = 1024, hashFunctions: [(T) -> Int]) {
6+
self.array = [Bool](repeating: false, count: size)
77
self.hashFunctions = hashFunctions
88
}
99

10-
private func computeHashes(value: T) -> [Int] {
10+
private func computeHashes(_ value: T) -> [Int] {
1111
return hashFunctions.map() { hashFunc in abs(hashFunc(value) % array.count) }
1212
}
1313

14-
public func insert(element: T) {
14+
public func insert(_ element: T) {
1515
for hashValue in computeHashes(element) {
1616
array[hashValue] = true
1717
}
1818
}
1919

20-
public func insert(values: [T]) {
20+
public func insert(_ values: [T]) {
2121
for value in values {
2222
insert(value)
2323
}
2424
}
2525

26-
public func query(value: T) -> Bool {
26+
public func query(_ value: T) -> Bool {
2727
let hashValues = computeHashes(value)
2828

2929
// Map hashes to indices in the Bloom Filter
@@ -35,7 +35,7 @@ public class BloomFilter<T> {
3535
// only that it may be. If the query returns false, however,
3636
// you can be certain that the value was not added.
3737

38-
let exists = results.reduce(true, combine: { $0 && $1 })
38+
let exists = results.reduce(true, { $0 && $1 })
3939
return exists
4040
}
4141

‎Bloom Filter/README.markdown

Lines changed: 8 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -58,11 +58,11 @@ Performance of a Bloom Filter is **O(k)** where **k** is the number of hashing f
5858

5959
## The code
6060

61-
The code is quite straightforward. The internal bit array is set to a fixed length on initialization, which cannot be mutated once it is initialized.
61+
The code is quite straightforward. The internal bit array is set to a fixed length on initialization, which cannot be mutated once it is initialized.
6262

6363
```swift
64-
public init(size: Int = 1024, hashFunctions: [T -> Int]) {
65-
self.array = .init(count: size, repeatedValue: false)
64+
public init(size: Int = 1024, hashFunctions: [(T) -> Int]) {
65+
self.array = [Bool](repeating: false, count: size)
6666
self.hashFunctions = hashFunctions
6767
}
6868
```
@@ -72,7 +72,7 @@ Several hash functions should be specified at initialization. Which hash functio
7272
Insertion just flips the required bits to `true`:
7373

7474
```swift
75-
public func insert(element: T) {
75+
public func insert(_ element: T) {
7676
for hashValue in computeHashes(element) {
7777
array[hashValue] = true
7878
}
@@ -82,22 +82,22 @@ public func insert(element: T) {
8282
This uses the `computeHashes()` function, which loops through the specified `hashFunctions` and returns an array of indices:
8383

8484
```swift
85-
private func computeHashes(value: T) -> [Int] {
85+
private func computeHashes(_ value: T) -> [Int] {
8686
return hashFunctions.map() { hashFunc in abs(hashFunc(value) % array.count) }
8787
}
8888
```
8989

9090
And querying checks to make sure the bits at the hashed values are `true`:
9191

9292
```swift
93-
public func query(value: T) -> Bool {
93+
public func query(_ value: T) -> Bool {
9494
let hashValues = computeHashes(value)
9595
let results = hashValues.map() { hashValue in array[hashValue] }
96-
let exists = results.reduce(true, combine: { $0 && $1 })
96+
let exists = results.reduce(true, { $0 && $1 })
9797
return exists
9898
}
9999
```
100100

101-
If you're coming from another imperative language, you might notice the unusual syntax in the `exists` assignment. Swift makes use of functional paradigms when it makes code more consise and readable, and in this case `reduce` is a much more consise way to check if all the required bits are `true` than a `for` loop.
101+
If you're coming from another imperative language, you might notice the unusual syntax in the `exists` assignment. Swift makes use of functional paradigms when it makes code more consise and readable, and in this case `reduce` is a much more consise way to check if all the required bits are `true` than a `for` loop.
102102

103103
*Written for Swift Algorithm Club by Jamil Dhanani. Edited by Matthijs Hollemans.*

‎Bloom Filter/Tests/BloomFilterTests.swift

Lines changed: 44 additions & 44 deletions
Original file line numberDiff line numberDiff line change
@@ -1,76 +1,76 @@
11
import XCTest
22

33
/* Two hash functions, adapted from
4-
http://www.cse.yorku.ca/~oz/hash.html */
4+
http://www.cse.yorku.ca/~oz/hash.html */
55

6-
func djb2(x: String) -> Int {
7-
var hash = 5381
6+
func djb2(_ x: String) -> Int {
7+
var hash = 5381
88

9-
for char in x.characters {
10-
hash = ((hash << 5) &+ hash) &+ char.hashValue
11-
}
9+
for char in x.characters {
10+
hash = ((hash << 5) &+ hash) &+ char.hashValue
11+
}
1212

13-
return Int(hash)
13+
return Int(hash)
1414
}
1515

16-
func sdbm(x: String) -> Int {
17-
var hash = 0
16+
func sdbm(_ x: String) -> Int {
17+
var hash = 0
1818

19-
for char in x.characters {
20-
hash = char.hashValue &+ (hash << 6) &+ (hash << 16) &- hash
21-
}
19+
for char in x.characters {
20+
hash = char.hashValue &+ (hash << 6) &+ (hash << 16) &- hash
21+
}
2222

23-
return Int(hash)
23+
return Int(hash)
2424
}
2525

2626

2727
class BloomFilterTests: XCTestCase {
2828

29-
func testSingleHashFunction() {
30-
let bloom = BloomFilter<String>(hashFunctions: [djb2])
29+
func testSingleHashFunction() {
30+
let bloom = BloomFilter<String>(hashFunctions: [djb2])
3131

32-
bloom.insert("Hello world!")
32+
bloom.insert("Hello world!")
3333

34-
let result_good = bloom.query("Hello world!")
35-
let result_bad = bloom.query("Hello world")
34+
let result_good = bloom.query("Hello world!")
35+
let result_bad = bloom.query("Hello world")
3636

37-
XCTAssertTrue(result_good)
38-
XCTAssertFalse(result_bad)
39-
}
37+
XCTAssertTrue(result_good)
38+
XCTAssertFalse(result_bad)
39+
}
4040

41-
func testEmptyFilter() {
42-
let bloom = BloomFilter<String>(hashFunctions: [djb2])
41+
func testEmptyFilter() {
42+
let bloom = BloomFilter<String>(hashFunctions: [djb2])
4343

44-
let empty = bloom.isEmpty()
44+
let empty = bloom.isEmpty()
4545

46-
XCTAssertTrue(empty)
47-
}
46+
XCTAssertTrue(empty)
47+
}
4848

49-
func testMultipleHashFunctions() {
50-
let bloom = BloomFilter<String>(hashFunctions: [djb2, sdbm])
49+
func testMultipleHashFunctions() {
50+
let bloom = BloomFilter<String>(hashFunctions: [djb2, sdbm])
5151

52-
bloom.insert("Hello world!")
52+
bloom.insert("Hello world!")
5353

54-
let result_good = bloom.query("Hello world!")
55-
let result_bad = bloom.query("Hello world")
54+
let result_good = bloom.query("Hello world!")
55+
let result_bad = bloom.query("Hello world")
5656

57-
XCTAssertTrue(result_good)
58-
XCTAssertFalse(result_bad)
59-
}
57+
XCTAssertTrue(result_good)
58+
XCTAssertFalse(result_bad)
59+
}
6060

61-
func testFalsePositive() {
62-
let bloom = BloomFilter<String>(size: 5, hashFunctions: [djb2, sdbm])
61+
func testFalsePositive() {
62+
let bloom = BloomFilter<String>(size: 5, hashFunctions: [djb2, sdbm])
6363

64-
bloom.insert(["hello", "elloh", "llohe", "lohel", "ohell"])
64+
bloom.insert(["hello", "elloh", "llohe", "lohel", "ohell"])
6565

66-
print("Inserted")
66+
print("Inserted")
6767

68-
let query = bloom.query("This wasn't inserted!")
68+
let query = bloom.query("This wasn't inserted!")
6969

70-
// This is true even though we did not insert the value in the Bloom filter;
71-
// the Bloom filter is capable of producing false positives but NOT
72-
// false negatives.
70+
// This is true even though we did not insert the value in the Bloom filter;
71+
// the Bloom filter is capable of producing false positives but NOT
72+
// false negatives.
7373

74-
XCTAssertTrue(query)
75-
}
74+
XCTAssertTrue(query)
75+
}
7676
}

‎Bloom Filter/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
};

‎Bloom Filter/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