Generic Hash Set in Swift

HashSet.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)")

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.

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
}