Last active
July 16, 2021 14:21
-
-
Save chen-hongzhi/ac8d4bed42e32ff0fe46 to your computer and use it in GitHub Desktop.
An implementation of a Set collection in Swift
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| // | |
| // Set.swift | |
| // Hover | |
| // | |
| // Created by Chen Hongzhi on 7/12/14. | |
| // Copyright (c) 2014 One Artisan. All rights reserved. | |
| // | |
| import Foundation | |
| public protocol Set { | |
| typealias Element : Equatable | |
| var count: Int { get } | |
| var isEmpty: Bool { get } | |
| func member(element: Element) -> Element? | |
| func contains(element: Element) -> Bool | |
| mutating func add(element: Element) | |
| mutating func remove(element: Element) | |
| mutating func removeAll(#keepCapacity: Bool) | |
| } | |
| public struct HashSet<T : Hashable> : Set { | |
| public typealias Element = T | |
| private var bucket: [T:Int] = [:] | |
| private let counted: Bool | |
| public init() { | |
| counted = false | |
| } | |
| public init(counted: Bool) { | |
| self.counted = counted | |
| } | |
| public init<S : Sequence where S.GeneratorType.Element == T>(_ sequence: S) { | |
| counted = false | |
| extend(sequence) | |
| } | |
| public init<S : Sequence where S.GeneratorType.Element == T>(_ sequence: S, counted: Bool) { | |
| self.counted = counted | |
| extend(sequence) | |
| } | |
| } | |
| public extension HashSet { | |
| var count: Int { | |
| return bucket.count | |
| } | |
| var isEmpty: Bool { | |
| return bucket.count == 0 | |
| } | |
| func member(element: T) -> T? { | |
| return bucket[element] != nil ? element : nil | |
| } | |
| func contains(element: T) -> Bool { | |
| return bucket[element] != nil | |
| } | |
| func isSubsetOf(other: HashSet<T>) -> Bool { | |
| if count > other.count { | |
| return false | |
| } | |
| for elem in self { | |
| if !other.bucket[elem] { | |
| return false | |
| } | |
| } | |
| return true | |
| } | |
| func isSupersetOf(other: HashSet<T>) -> Bool { | |
| if count < other.count { | |
| return false | |
| } | |
| for elem in other { | |
| if !bucket[elem] { | |
| return false | |
| } | |
| } | |
| return true | |
| } | |
| func countOf(element: T) -> Int { | |
| if let count = bucket[element] { | |
| return count | |
| } | |
| return 0 | |
| } | |
| } | |
| public extension HashSet { | |
| mutating func add(element: T) { | |
| if !counted { | |
| bucket[element] = 1 | |
| } else if let count = bucket[element] { | |
| bucket[element] = count + 1 | |
| } else { | |
| bucket[element] = 1 | |
| } | |
| } | |
| mutating func remove(element: T) { | |
| if !counted { | |
| bucket[element] = nil | |
| } else if let count = bucket[element] { | |
| if count > 1 { | |
| bucket[element] = count - 1 | |
| } else { | |
| bucket[element] = nil | |
| } | |
| } | |
| } | |
| mutating func removeAll(#keepCapacity: Bool) { | |
| bucket.removeAll(keepCapacity: keepCapacity) | |
| } | |
| mutating func extend<S: Sequence where S.GeneratorType.Element == T>(sequence: S) { | |
| var generator = sequence.generate() | |
| while let (element: T) = generator.next() { | |
| add(element) | |
| } | |
| } | |
| } | |
| public extension HashSet { | |
| func filter(includeElement: (T) -> Bool) -> HashSet<T> { | |
| var newSet = HashSet() | |
| for key in bucket.keys { | |
| if includeElement(key) { | |
| newSet.add(key) | |
| } | |
| } | |
| return newSet | |
| } | |
| func intersect<S : Sequence where S.GeneratorType.Element == T>(other: S) -> HashSet<T> { | |
| return filter { Swift.contains(other, $0) } | |
| } | |
| func minus<S : Sequence where S.GeneratorType.Element == T>(other: S) -> HashSet<T> { | |
| return filter { !Swift.contains(other, $0) } | |
| } | |
| func union<S : Sequence where S.GeneratorType.Element == T>(other: S) -> HashSet<T> { | |
| var copy = self | |
| copy.extend(other) | |
| return copy | |
| } | |
| } | |
| public extension HashSet { | |
| func all() -> [T] { | |
| return [T](bucket.keys) | |
| } | |
| func any() -> T? { | |
| if isEmpty { | |
| return nil | |
| } | |
| let rand = Int(arc4random_uniform(UInt32(count))) | |
| return bucket.keys[advance(bucket.keys.startIndex, rand)] | |
| } | |
| } | |
| extension HashSet : Printable, Sequence, ArrayLiteralConvertible {} | |
| public extension HashSet { | |
| var description: String { | |
| return Array(bucket.keys).description | |
| } | |
| func generate() -> GeneratorOf<T> { | |
| var generator = bucket.keys.generate() | |
| return GeneratorOf { generator.next() } | |
| } | |
| static func convertFromArrayLiteral(elements: T...) -> HashSet<T> { | |
| return self(elements) | |
| } | |
| } | |
| public func ^<T>(lhs: HashSet<T>, rhs: HashSet<T>) -> HashSet<T> { | |
| return lhs.intersect(rhs) | |
| } | |
| public func +<T>(lhs: HashSet<T>, rhs: HashSet<T>) -> HashSet<T> { | |
| return lhs.union(rhs) | |
| } | |
| public func -<T>(lhs: HashSet<T>, rhs: HashSet<T>) -> HashSet<T> { | |
| return lhs.minus(rhs) | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment