CountedSet.swift

public struct CountedSet<Element : Hashable> : Hashable, CollectionType, ArrayLiteralConvertible {

    public typealias Index = SetIndex<Element>
    public typealias Generator = SetGenerator<Element>
    private var backingSet = Set<Element>()
    private var countMapping = [Int: UInt]()

    private var debugCountMapping: [Element : UInt] {
        var result = [Element : UInt]()
        backingSet.forEach { element in
            result[element] = countForElement(element)
        }
        return result
    }

    public mutating func insert(member: Element) {
        backingSet.insert(member)
        let count = countMapping[member.hashValue] ?? 0
        countMapping[member.hashValue] = count + 1
    }

    public mutating func remove(member: Element) -> Element? {
        guard let element = backingSet.remove(member) else { return nil }
        let count = countMapping[element.hashValue] ?? 0
        countMapping[element.hashValue] = max(count - 1, 0)
        return element
    }

    public func countForElement(member: Element) -> UInt? {
        return countMapping[member.hashValue]
    }

    public var hashValue: Int {
        return backingSet.hashValue + Int(countMapping.values.reduce(0, combine: <<))
    }

    public init(arrayLiteral elements: Element...) {
        elements.forEach { insert($0) }
    }

    public func generate() -> Generator {
        return backingSet.generate()
    }

    public var startIndex: Index {
        return backingSet.startIndex
    }

    public var endIndex: Index {
        return backingSet.endIndex
    }

    public subscript(position: Index) -> Generator.Element {
        return backingSet[position]
    }
}

public func ==<Element>(lhs: CountedSet<Element>, rhs: CountedSet<Element>) -> Bool {
    return lhs.backingSet == rhs.backingSet && lhs.countMapping == rhs.countMapping
}