a_star: don't crash on deserialization errors and limit static types

[nit.git] / lib / perfect_hashing.nit

diff --git a/lib/perfect_hashing.nit b/lib/perfect_hashing.nit
index a4b8417..d8ab3cb 100644 (file)
--- a/lib/perfect_hashing.nit
+++ b/lib/perfect_hashing.nit
@@ -24,23 +24,21 @@ class Perfecthashing
        # 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](1, null))
-               tempht = new Array[nullable Int]
        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
@@ -54,22 +52,22 @@ class Perfecthashing
                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
@@ -87,14 +85,14 @@ class Perfecthashing
        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
 
@@ -114,15 +112,18 @@ class Perfecthashing
        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
@@ -155,9 +156,9 @@ class Perfecthashing
                        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
@@ -165,7 +166,7 @@ class Perfecthashing
                                if tempht[hv] != mask then
                                        found = true
                                        id = i
-                               end     
+                               end
                                i = i + 1
                        end
 
@@ -181,7 +182,7 @@ class Perfecthashing
                        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