Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
`BitSet / BitVector / BitArray` using `UnsafeMutablePointer` instead of `Array<T>`
import XCTest
import Foundation
final class Ref {
var value : UnsafeMutablePointer<Int>
init(_ v : UnsafeMutablePointer<Int>) {value = v}
deinit {
self.value.deallocate()
// guard let x = (self.value as? UnsafeMutablePointer<Int>)?.deallocate() else { return }
// x.deallocate()
}
}
struct BitSet {
var rawValue: UnsafeMutablePointer<Int> { return self.ref.value }
// var rawValue: Array<Int>
var wordCount: Int
var ref: Ref
init(_ wordCount: Int = 99) {
self.wordCount = wordCount
self.ref = Ref(UnsafeMutablePointer<Int>.allocate(capacity: self.wordCount))
// self.rawValue = Array.init(repeating: 0, count: 99)
// self.rawValue.reserveCapacity(99)
}
public func contains(_ value: Int) -> Bool {
let index = value >> 6
guard index < self.wordCount else { return false }
return self.rawValue[index] & (1 << (Int(value & 63))) != 0
}
mutating func insert(_ value: Int, at index: Int) {
self.rawValue[index] = value
}
mutating func add(_ value: Int) {
if isKnownUniquelyReferenced(&self.ref) == false {
let newdata = UnsafeMutablePointer<Int>.allocate(capacity: self.wordCount)
newdata.initialize(from: self.rawValue, count: self.wordCount)
self.ref = Ref(newdata)
}
let index = value >> 6
if index >= self.wordCount {
let newCapacity = (index * 3)
let newdata = UnsafeMutablePointer<Int>.allocate(capacity: newCapacity)
newdata.initialize(from: self.rawValue, count: self.wordCount)
self.ref.value = newdata
// self.rawValue = self.rawValue + Array<Int>.init(repeating: 0, count: newCapacity)
self.wordCount = newCapacity
}
self.rawValue[index] |= 1 << (Int64(value & 63))
}
func intersection(_ other: BitSet) -> BitSet {
let mincount = Swift.min(self.wordCount, other.wordCount)
var bitSet = BitSet(mincount)
(0..<mincount).forEach {
let mask = self.rawValue[$0] & other.rawValue[$0]
bitSet.insert(mask, at: $0)
}
return bitSet
}
// self.rawValue[index] & (1 << (Int(value & 63))) != 0
func forEach(_ handler: (Int) -> Void) {
let endIndex = self.wordCount * 63
(0..<endIndex).forEach {
if self.contains($0) {
handler($0)
}
}
}
func confirm(_ cond: Bool, _ value: Int) {
print("Should be \(cond) \(self.contains(value))")
}
}
let fullList = (0...1000000)
let list = fullList.filter { $0 % 50 != 0 }
class BitsetTests: XCTestCase {
func testIndexSetInsert() {
var sets = IndexSet()
measure {
list.forEach {
sets.insert($0)
}
}
}
func testBitVectorInsert() {
var sets = BitSet()
measure {
list.forEach {
sets.add($0)
}
}
}
func testIndexContains() {
var sets = IndexSet()
list.forEach {
sets.insert($0)
}
measure {
list.forEach {
_ = sets.contains($0)
}
}
}
func testBitVectorContains() {
var sets = BitSet()
list.forEach {
sets.add($0)
}
measure {
list.forEach {
_ = sets.contains($0)
}
}
}
func testIndexSetIntersect() {
var first = IndexSet()
var second = IndexSet()
list.forEach {
first.insert($0)
}
fullList.forEach {
second.insert($0)
}
measure {
_ = first.intersection(second)
}
}
func testBitVectorIntersect() {
var first = BitSet()
var second = BitSet()
list.forEach {
first.add($0)
}
fullList.forEach {
second.add($0)
}
measure {
_ = first.intersection(second)
}
}
func testIndexSetIterator() {
var first = IndexSet()
var second = IndexSet()
list.forEach {
first.insert($0)
}
fullList.forEach {
second.insert($0)
}
let intersection = first.intersection(second)
measure {
intersection.forEach {
_ = $0
}
}
}
func testBitVectorIterate() {
var first = BitSet()
var second = BitSet()
list.forEach {
first.add($0)
}
fullList.forEach {
second.add($0)
}
let intersection = first.intersection(second)
measure {
intersection.forEach {
_ = $0
}
}
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.