Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

130 lines (115 sloc) 2.843 kb
lomask(n::Integer) = lomask(uint32(n))
lomask(n::Uint32) = ((1<<n)-1)
himask(n::Integer) = himask(uint32(n))
himask(n::Uint32) = (~lomask(32-n))
# This appears to be actually the same speed as the one below
#start(s::IntSet) = IntSet(s)
#done(s::IntSet, i) = isempty(i)
#function next(s::IntSet, i)
# #n = ccall(:bitvector_next, Int64, (Ptr{Uint32}, Uint64, Uint64),
# # s.bits, uint64(first), uint64(s.limit))
# #return (n, n+1)
# n = bitvector_next(i.bits, uint64(0), uint64(i.limit))::Int64
# del(i, n)
# return (n, i)
#end
start(s::IntSet) = int64(0)
done(s::IntSet, i) = (next(s,i)[1] >= s.limit)
function next(s::IntSet, i)
n = bitvector_next(s.bits, uint64(i), uint64(s.limit))
(n, n+1)
end
function bitvector_next(b::Array{Uint32,1}, n0::Uint64, n::Uint64)
local w::Uint32
i = n0>>5
nb = n0&31
nw = (n+31)>>5
if i < nw-1 || (n&31)==0
w = b[i+1]>>nb
else
w = (b[i+1]&lomask(n&31))>>nb
end
if w != 0
nxt = int64(trailing_zeros(w) + n0)
return nxt
end
if i == nw-1
nxt = int64(n)
return nxt
end
i += 1
while i < nw-1
w = b[i+1]
if w != 0
nxt = int64(trailing_zeros(w) + i<<5)
return nxt
end
i += 1
end
w = b[i+1]
nb = n & 31
i = int64(trailing_zeros(w))
if nb == 0
nxt = int64(i + (n-32))
return nxt
end
if i >= nb
nxt = int64(n)
return nxt
end
nxt = int64(i + (n-nb))
return nxt
end
function isempty(s::IntSet)
!bitvector_any1(s.bits, uint64(0), uint64(s.limit))
end
function bitvector_any1(b::Array{Uint32,1}, offs::Uint64, nbits::Uint64)
local nw::Uint32, tail::Uint32, mask::Uint32
if (nbits == 0)
return false;
end
nw = (offs+nbits+31)>>5;
if (nw == 1)
if (nbits == 32)
mask = (uint32(0xffffffff)<<offs)
else
mask = (lomask(nbits)<<offs)
end
if ((b[1] & mask) != 0)
return true
end
return false
end
mask = ~lomask(offs)
if ((b[1] & mask) != 0)
return true
end
for i = 1:nw-1
if (b[i+1] != 0)
return true
end
end
tail = (offs+nbits)&31
if (tail==0)
if (b[nw] != 0)
return true
end
else
mask = lomask(tail);
if ((b[nw] & mask) != 0)
return true
end
end
return false
end
function choose(s::IntSet)
n = bitvector_next(s.bits, uint64(0), uint64(s.limit))::Int64
if n >= s.limit
error("choose: set is empty")
end
return n
end
length(s::IntSet) = numel(s)
numel(s::IntSet) =
int32(ccall(:bitvector_count, Uint64, (Ptr{Uint32}, Uint64, Uint64),
s.bits, 0, s.limit))
Jump to Line
Something went wrong with that request. Please try again.