Creating a Set Type in Swift
// The MIT License (MIT) | |
// | |
// Copyright (c) 2014 Nate Cook | |
// | |
// Permission is hereby granted, free of charge, to any person obtaining a copy | |
// of this software and associated documentation files (the "Software"), to deal | |
// in the Software without restriction, including without limitation the rights | |
// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell | |
// copies of the Software, and to permit persons to whom the Software is | |
// furnished to do so, subject to the following conditions: | |
// | |
// The above copyright notice and this permission notice shall be included in all | |
// copies or substantial portions of the Software. | |
// | |
// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR | |
// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY, | |
// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE | |
// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER | |
// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, | |
// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE | |
// SOFTWARE. | |
import Foundation | |
public struct Set<T: Hashable> : Equatable { | |
typealias Element = T | |
private var contents: [Element: Bool] | |
public init() { | |
self.contents = [Element: Bool]() | |
} | |
public init<S: SequenceType where S.Generator.Element == Element>(_ sequence: S) { | |
self.contents = [Element: Bool]() | |
Swift.map(sequence) { self.contents[$0] = true } | |
} | |
/// The number of elements in the Set. | |
public var count: Int { return contents.count } | |
/// Returns `true` if the Set is empty. | |
public var isEmpty: Bool { return contents.isEmpty } | |
/// The elements of the Set as an array. | |
public var elements: [Element] { return Array(self.contents.keys) } | |
/// Returns `true` if the Set contains `element`. | |
public func contains(element: Element) -> Bool { | |
return contents[element] ?? false | |
} | |
/// Add `newElements` to the Set. | |
public mutating func add(newElements: Element...) { | |
newElements.map { self.contents[$0] = true } | |
} | |
/// Remove `element` from the Set. | |
public mutating func remove(element: Element) -> Element? { | |
return contents.removeValueForKey(element) != nil ? element : nil | |
} | |
/// Removes all elements from the Set. | |
public mutating func removeAll() { | |
contents = [Element: Bool]() | |
} | |
/// Returns a new Set including only those elements `x` where `includeElement(x)` is true. | |
public func filter(includeElement: (T) -> Bool) -> Set<T> { | |
return Set(self.contents.keys.filter(includeElement)) | |
} | |
/// Returns a new Set where each element `x` is transformed by `transform(x)`. | |
public func map<U>(transform: (T) -> U) -> Set<U> { | |
return Set<U>(self.contents.keys.map(transform)) | |
} | |
/// Returns a single value by iteratively combining each element of the Set. | |
public func reduce<U>(var initial: U, combine: (U, T) -> U) -> U { | |
return Swift.reduce(self, initial, combine) | |
} | |
} | |
// MARK: SequenceType | |
extension Set : SequenceType { | |
typealias Generator = MapSequenceGenerator<DictionaryGenerator<T, Bool>, T> | |
/// Creates a generator for the items of the set. | |
public func generate() -> Generator { | |
return contents.keys.generate() | |
} | |
} | |
// MARK: ArrayLiteralConvertible | |
extension Set : ArrayLiteralConvertible { | |
public static func convertFromArrayLiteral(elements: T...) -> Set<T> { | |
return Set(elements) | |
} | |
} | |
// MARK: Set Operations | |
extension Set { | |
/// Returns `true` if the Set has the exact same members as `set`. | |
public func isEqualToSet(set: Set<T>) -> Bool { | |
return self.contents == set.contents | |
} | |
/// Returns `true` if the Set shares any members with `set`. | |
public func intersectsWithSet(set: Set<T>) -> Bool { | |
for elem in self { | |
if set.contains(elem) { | |
return true | |
} | |
} | |
return false | |
} | |
/// Returns `true` if all members of the Set are part of `set`. | |
public func isSubsetOfSet(set: Set<T>) -> Bool { | |
for elem in self { | |
if !set.contains(elem) { | |
return false | |
} | |
} | |
return true | |
} | |
/// Returns `true` if all members of `set` are part of the Set. | |
public func isSupersetOfSet(set: Set<T>) -> Bool { | |
return set.isSubsetOfSet(self) | |
} | |
/// Modifies the Set to add all members of `set`. | |
public mutating func unionSet(set: Set<T>) { | |
for elem in set { | |
self.add(elem) | |
} | |
} | |
/// Modifies the Set to remove any members also in `set`. | |
public mutating func subtractSet(set: Set<T>) { | |
for elem in set { | |
self.remove(elem) | |
} | |
} | |
/// Modifies the Set to include only members that are also in `set`. | |
public mutating func intersectSet(set: Set<T>) { | |
self = self.filter { set.contains($0) } | |
} | |
/// Returns a new Set that contains all the elements of both this set and the set passed in. | |
public func setByUnionWithSet(var set: Set<T>) -> Set<T> { | |
set.extend(self) | |
return set | |
} | |
/// Returns a new Set that contains only the elements in both this set and the set passed in. | |
public func setByIntersectionWithSet(var set: Set<T>) -> Set<T> { | |
set.intersectSet(self) | |
return set | |
} | |
/// Returns a new Set that contains only the elements in this set *not* also in the set passed in. | |
public func setBySubtractingSet(set: Set<T>) -> Set<T> { | |
var newSet = self | |
newSet.subtractSet(set) | |
return newSet | |
} | |
} | |
// MARK: ExtensibleCollectionType | |
extension Set : ExtensibleCollectionType { | |
typealias Index = Int | |
public var startIndex: Int { return 0 } | |
public var endIndex: Int { return self.count } | |
public subscript(i: Int) -> Element { | |
return Array(self.contents.keys)[i] | |
} | |
public mutating func reserveCapacity(n: Int) { | |
// can't really do anything with this | |
} | |
/// Adds newElement to the Set. | |
public mutating func append(newElement: Element) { | |
self.add(newElement) | |
} | |
/// Extends the Set by adding all the elements of `seq`. | |
public mutating func extend<S : SequenceType where S.Generator.Element == Element>(seq: S) { | |
Swift.map(seq) { self.contents[$0] = true } | |
} | |
} | |
// MARK: Printable | |
extension Set : Printable, DebugPrintable { | |
public var description: String { | |
return "Set(\(self.elements))" | |
} | |
public var debugDescription: String { | |
return description | |
} | |
} | |
// MARK: Operators | |
public func +=<T>(inout lhs: Set<T>, rhs: T) { | |
lhs.add(rhs) | |
} | |
public func +=<T>(inout lhs: Set<T>, rhs: Set<T>) { | |
lhs.unionSet(rhs) | |
} | |
public func +<T>(lhs: Set<T>, rhs: Set<T>) -> Set<T> { | |
return lhs.setByUnionWithSet(rhs) | |
} | |
public func ==<T>(lhs: Set<T>, rhs: Set<T>) -> Bool { | |
return lhs.isEqualToSet(rhs) | |
} | |
// MARK: - Tests | |
let vowelSet = Set("aeiou") | |
let alphabetSet = Set("abcdefghijklmnopqrstuvwxyz") | |
let emptySet = Set<Int>() | |
assert(vowelSet.isSubsetOfSet(alphabetSet) == true) | |
assert(vowelSet.isSupersetOfSet(alphabetSet) == false) | |
assert(alphabetSet.isSupersetOfSet(vowelSet) == true) | |
assert(emptySet.isEmpty) | |
assert(vowelSet.count == 5) | |
assert(vowelSet.contains("b") == false) | |
var mutableVowelSet = vowelSet | |
mutableVowelSet.add("a") | |
assert(mutableVowelSet.count == 5) | |
mutableVowelSet += "y" | |
assert(mutableVowelSet.count == 6) | |
mutableVowelSet += Set("åáâäàéêèëíîïìøóôöòúûüù") | |
assert(mutableVowelSet.intersectsWithSet(alphabetSet) == true) | |
assert(mutableVowelSet.isSubsetOfSet(alphabetSet) == false) | |
var newLetterSet = alphabetSet.setByIntersectionWithSet(mutableVowelSet) | |
newLetterSet.remove("y") | |
assert(newLetterSet == vowelSet) | |
let bracketedLetterSet = vowelSet.map { "[\($0)]" } | |
assert(bracketedLetterSet.contains("[a]") == true) | |
// MARK: - Timing | |
func timeBlock(block: () -> Int) -> (Int, NSTimeInterval) { | |
let start = NSDate() | |
let result = block() | |
return (result, NSDate().timeIntervalSinceDate(start)) | |
} | |
var timedSet = Set<Int>() | |
var timedArray = Array<Int>() | |
let (setCreatedCount, setCreatedTime) = timeBlock { | |
for _ in 1...1_000 { | |
let num = Int(arc4random_uniform(1_000)) | |
timedSet.add(num) | |
} | |
return timedSet.count | |
} | |
println("Set added \(setCreatedCount) unique elements in \(setCreatedTime).") | |
let (setMatchedCount, setMatchedTime) = timeBlock { | |
var matchCount = 0 | |
for _ in 1...1_000 { | |
let num = Int(arc4random_uniform(1_000)) | |
if timedSet.contains(num) { | |
++matchCount | |
} | |
} | |
return matchCount | |
} | |
println("Set matched \(setMatchedCount) elements out of 1000 in \(setMatchedTime).") | |
let (arrayCreatedCount, arrayCreatedTime) = timeBlock { | |
for _ in 1...1_000 { | |
let num = Int(arc4random_uniform(1_000)) | |
timedArray.append(num) | |
} | |
return timedArray.count | |
} | |
println("Array added \(arrayCreatedCount) elements in \(arrayCreatedTime).") | |
let (arrayMatchedCount, arrayMatchedTime) = timeBlock { | |
var matchCount = 0 | |
for _ in 1...1_000 { | |
let num = Int(arc4random_uniform(1_000)) | |
if contains(timedArray, num) { | |
++matchCount | |
} | |
} | |
return matchCount | |
} | |
println("Array matched \(arrayMatchedCount) elements out of 1000 in \(arrayMatchedTime).") | |
println() | |
println("Array \(Int(setCreatedTime / arrayCreatedTime))x faster at creation than Set.") | |
println("Set \(Int(arrayMatchedTime / setMatchedTime))x faster at lookup than Array.") | |
/* | |
Set added 637 unique elements in 1.2172309756279. | |
Set matched 650 elements out of 1000 in 0.00271201133728027. | |
Array added 1000 elements in 0.00527894496917725. | |
Array matched 612 elements out of 1000 in 2.09512096643448. | |
Array 230x faster at creation than Set. | |
Set 772x faster at lookup than Array. | |
*/ |
This comment has been minimized.
This comment has been minimized.
Try to rewrite that extension as: extension Set : ArrayLiteralConvertible {
init(arrayLiteral elements: T...) {
self.init(elements)
}
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This comment has been minimized.
This is a great class, but I do not believe it works with the latest Xcode. It looks like they have changed the ArrayLiteralConvertible extension