# Union of interval for implementing perfect numbering
# Represents the interval of free identifiers
# A null value represents the upper bound of identifier
- private var interval: List[Couple[nullable Int, nullable Int]]
+ private var interval = new List[Couple[nullable Int, nullable Int]]
- # An array used as a temporary Hashtable for
+ # An array used as a temporary Hashtable for
# checking there is no collision between identifiers
- private var tempht: Array[nullable Int]
+ private var tempht = new Array[nullable Int]
# Initialize the structure of free identifiers
init
do
# By default, all identifiers are available
- interval = new List[Couple[nullable Int, nullable Int]]
- interval.push(new Couple[nullable Int, nullable Int](0, null))
- tempht = new Array[nullable Int]
+ interval.push(new Couple[nullable Int, nullable Int](1, null))
end
-
+
# Returns a mask composed by discriminants bits
- # for these given identifiers
+ # for these given identifiers
# The mask + 1 value is the size of the hastable to create
fun phand(ids: Array[Int]): Int
do
var orMask = 0
var andMask = 0
for i in ids do
- orMask = orMask.bin_or(i)
- andMask = andMask.bin_and(i)
+ orMask |= i
+ andMask &= i
end
- mask = orMask.bin_xor(andMask)
+ mask = orMask ^ andMask
# Re-initialize the hashtable with null values
- for i in [0..mask+1] do tempht[i] = null
+ for i in [0..(mask+1)] do tempht[i] = null
# Optimize the already computed mask
var newmask = 0
var i = mask.highest_bit
while i != 0 do
if mask.getbit(i) == 1 then
- newmask = mask.bin_xor(1.lshift(i))
-
+ newmask = mask ^ (1 << i)
+
# If there is no collision, replace the old mask
if phandp(ids, newmask) then
mask = newmask
fun phandp(ids: Array[Int], mask: Int): Bool
do
for i in ids do
- var hv = i.bin_and(mask)
+ var hv = i & mask
if tempht[hv] == mask then
return false
else
tempht[hv] = mask
end
end
-
+
return true
end
do
var mask = phand(ids) -1
var i = 0
- while n+ids.length > (1.lshift(mask.number_bits(1))) do
+ while n+ids.length > (1 << mask.number_bits(1)) do
# When there are not enough 1-bits
if mask.getbit(i) == 0 then
- mask = mask.bin_xor(1.lshift(i))
+ mask = mask ^ (1 << i)
end
i += 1
end
# Resetting hashtable
+ for j in [0..(mask+1)] do tempht[j] = null
+
+ # Set the temporary hashtable for `compute_least_free_ids`
phandp(ids, mask)
# Fill the given array with n free identifiers
var i = inter.item.first.as(not null)
while i != inter.item.second and not found do
# Tests if this id is free for this mask
- var hv = i.bin_and(mask)
+ var hv = i & mask
- # If the hashtable if full, push an empty item
+ # If the hashtable if full, push an empty item
if hv >= tempht.length then
tempht.push(null)
end
if tempht[hv] != mask then
found = true
id = i
- end
+ end
i = i + 1
end
else
inter.item.first += 1
end
- else
+ else
if id != inter.item.first and id != inter.item.second then
# We need to split in two this interval
var last = inter.item.second