Skip to content

Instantly share code, notes, and snippets.

@beccadax

beccadax/BitSet.swift

Last active May 13, 2016
Embed
What would you like to do?
Minimal BitSet type capable of handling integer-based RawRepresentable enums. Does not implement all of Set's functionality, but the skeleton is here.
// This is basically a polymorphic constant.
// We don't base it on sizeof(IntMax) because that returns Int, which we may not be able to convert to the correct IntegerType.
private func intMaxBitSize<T: IntegerType>() -> T {
return 63
}
public struct BitSet<T: RawRepresentable where T.RawValue: IntegerType>: RawRepresentable {
private(set) public var rawValue: IntMax = 0
public init() {}
public init?(rawValue: IntMax) {
self.rawValue = rawValue
}
private func maskFor(element: T) -> IntMax {
let offset = element.rawValue.toIntMax()
precondition(offset < intMaxBitSize(), "Element \(element)'s raw value too large to fit in a BitSet")
return 1 << offset
}
public mutating func insert(element: T) {
rawValue |= maskFor(element)
}
public mutating func remove(element: T) {
rawValue &= ~maskFor(element)
}
public func contains(element: T) -> Bool {
return rawValue & maskFor(element) != 0
}
}
private func first<Seq: SequenceType>(seq: Seq) -> Seq.Generator.Element? {
var generator = seq.generate()
return generator.next()
}
public struct BitSetIndex<T: RawRepresentable where T.RawValue: IntegerType>: ForwardIndexType {
private var rawValue: T.RawValue?
private var bitSet: BitSet<T>
private init(bitSet: BitSet<T>, firstRawValue: T.RawValue?) {
self.bitSet = bitSet
if let firstRawValue = firstRawValue {
let possibleRawValues = lazy(firstRawValue..<intMaxBitSize())
let presentRawValues = possibleRawValues.filter { bitSet.rawValue.toIntMax() & (1 << $0.toIntMax()) != 0 }
self.rawValue = first(presentRawValues)
}
}
private init(bitSet: BitSet<T>) {
self.init(bitSet: bitSet, firstRawValue: 0)
}
public func successor() -> BitSetIndex {
return BitSetIndex(bitSet: bitSet, firstRawValue: rawValue! + 1)
}
}
public func == <T: RawRepresentable where T.RawValue: IntegerType>(lhs: BitSetIndex<T>, rhs: BitSetIndex<T>) -> Bool {
return lhs.bitSet == rhs.bitSet && lhs.rawValue == rhs.rawValue
}
extension BitSet: Equatable {}
public func == <T: RawRepresentable where T.RawValue: IntegerType>(lhs: BitSet<T>, rhs: BitSet<T>) -> Bool {
return lhs.rawValue == rhs.rawValue
}
extension BitSet: CollectionType, ArrayLiteralConvertible {
public init(arrayLiteral elements: T...) {
elements.map(insert)
}
public var startIndex: BitSetIndex<T> {
return BitSetIndex(bitSet: self)
}
public var endIndex: BitSetIndex<T> {
return BitSetIndex(bitSet: self, firstRawValue: nil)
}
public subscript (index: BitSetIndex<T>) -> T {
precondition(index.bitSet == self, "Indexed one bit set with an index from another bit set")
precondition(index.rawValue != nil, "Indexed a bit set with its end index")
// If we've gotten here, the index must exist in this bitset, so we can just construct the matching element and go home.
return T(rawValue: index.rawValue!)!
}
public func generate() -> IndexingGenerator<BitSet> {
return IndexingGenerator(self)
}
}
public func toSet<T: Hashable, RawRepresentable where T.RawValue: IntegerType>(bitSet: BitSet<T>) -> Set<T> {
var set = Set<T>()
map(bitSet, set.insert)
return set
}
public func toBitSet<T: Hashable, RawRepresentable where T.RawValue: IntegerType>(set: Set<T>) -> BitSet<T> {
var bitSet = BitSet<T>()
map(set, bitSet.insert)
return bitSet
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment