Skip to content

Instantly share code, notes, and snippets.

@andelf
Last active August 29, 2015 14:02
Show Gist options
  • Save andelf/156ae406790a8de4fa3d to your computer and use it in GitHub Desktop.
Save andelf/156ae406790a8de4fa3d to your computer and use it in GitHub Desktop.
Generic Hash Set in Swift
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 }
}
// 重载 for-in
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 {
for (k, _) in a._map {
if !b._map[k] {
return false
}
}
return false
}
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
}
}
@assignment func +=<T, C : Collection where C.GeneratorType.Element == T>(inout lhs: HashSet<T>, rhs: C) {
for i in rhs {
lhs += 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
}
println("========================================")
var s: HashSet<Int> = [1,23, 34, 45, 65, 10023,67]
println("s = \(s)")
s += 100
println("s = \(s)")
s += [23, 34, 45, 56, 999, 888, 777]
println("s = \(s)")
var s2: HashSet<Int> = [1314212, 452345, 2345234, 324523 ,2345, 1]
println("++ = \(s + s2)")
println("-- = \(s - s2)")
@devios1
Copy link

devios1 commented Jul 9, 2014

Thanks for this. The += operator on line 71 gives me an ambiguity error on Collection. Not sure how to resolve it. Commenting out the function compiles fine.

@devios1
Copy link

devios1 commented Jul 11, 2014

Also, the == operator doesn't appear to be properly implemented. This should do it:

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
}

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment