Skip to content

Instantly share code, notes, and snippets.

@devios1
Forked from andelf/HashSet.swift
Last active January 26, 2017 16:12
Show Gist options
  • Save devios1/d8914833912c1aae15e2 to your computer and use it in GitHub Desktop.
Save devios1/d8914833912c1aae15e2 to your computer and use it in GitHub Desktop.
Modified version of andelf/HashSet.swift that includes a proper == implementation as well as -=.
import Foundation
struct HashSet<T : Hashable> {
typealias Element = T
var _map: Dictionary<T, ()> = [:]
var count: Int {
return _map.count
}
var isEmpty: Bool {
return self.count == 0
}
var hashValue: Int {
return reduce(_map.keys, 0) { $0.hashValue ^ $1.hashValue }
}
func generate() -> IndexingGenerator<Array<T>> {
return ([] + _map.keys).generate()
}
subscript (i: T) -> Bool {
return self._map[i].getLogicValue()
}
}
extension HashSet : ArrayLiteralConvertible {
static func convertFromArrayLiteral(elements: T...) -> HashSet<T> {
var ret: Dictionary<T, ()> = [:]
for e in elements {
ret[e] = ()
}
return HashSet(_map: ret)
}
}
extension HashSet : Printable, DebugPrintable {
var description: String {
return ([] + _map.keys).description
}
var debugDescription: String {
return ([] + _map.keys).debugDescription
}
}
func ==<T>(a: HashSet<T>, b: HashSet<T>) -> Bool {
if a.count != b.count {
return false
}
for (k, _) in a._map {
if !b._map[k] {
return false
}
}
return true
}
extension HashSet : Equatable {}
extension HashSet : Sequence {}
extension HashSet : Hashable {}
@assignment @transparent func +=<T>(inout s: HashSet<T>, i: T) {
s._map[i] = ()
}
@assignment func +=<T, S : Sequence where S.GeneratorType.Element == T>(inout lhs: HashSet<T>, rhs: S) {
for i in rhs {
lhs += i
}
}
// this is causing an ambiguity error on Collection in Xcode6-Beta3
//@assignment func +=<T, C : Collection where C.GeneratorType.Element == T>(inout lhs: HashSet<T>, rhs: C) {
// for i in rhs {
// lhs += i
// }
//}
@assignment @transparent func -=<T>(inout s: HashSet<T>, i: T) {
s._map.removeValueForKey(i)
}
@assignment func -=<T, S : Sequence where S.GeneratorType.Element == T>(inout lhs: HashSet<T>, rhs: S) {
for i in rhs {
lhs._map.removeValueForKey(i)
}
}
func +<T>(lhs: HashSet<T>, rhs: HashSet<T>) -> HashSet<T> {
var ret = HashSet<T>()
for i in lhs {
ret += i
}
for i in rhs {
ret += i
}
return ret
}
func -<T>(lhs: HashSet<T>, rhs: HashSet<T>) -> HashSet<T> {
var ret = HashSet<T>()
for i in lhs { // in lhs
if !rhs._map[i] { // not in rhs
ret += i
}
}
return ret
}
func ^<T>(lhs: HashSet<T>, rhs: HashSet<T>) -> HashSet<T> {
var ret = HashSet<T>()
for i in lhs { // in lhs
if rhs._map[i] { // not in rhs
ret += i
}
}
return ret
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment