1 # This file is part of NIT ( http://www.nitlanguage.org ).
3 # Copyright 2014 Julien Pagès <julien.pages@lirmm.fr>
5 # Licensed under the Apache License, Version 2.0 (the "License");
6 # you may not use this file except in compliance with the License.
7 # You may obtain a copy of the License at
9 # http://www.apache.org/licenses/LICENSE-2.0
11 # Unless required by applicable law or agreed to in writing, software
12 # distributed under the License is distributed on an "AS IS" BASIS,
13 # WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
14 # See the License for the specific language governing permissions and
15 # limitations under the License.
17 # Perfect hashing and perfect numbering
18 module perfect_hashing
20 # Class for Perfect Hashing operations with perfect numbering
21 # It also stores the free identifiers for the perfect numbering
24 # Union of interval for implementing perfect numbering
25 # Represents the interval of free identifiers
26 # A null value represents the upper bound of identifier
27 private var interval
= new List[Couple[nullable Int, nullable Int]]
29 # An array used as a temporary Hashtable for
30 # checking there is no collision between identifiers
31 private var tempht
= new Array[nullable Int]
33 # Initialize the structure of free identifiers
36 # By default, all identifiers are available
37 interval
.push
(new Couple[nullable Int, nullable Int](1, null))
40 # Returns a mask composed by discriminants bits
41 # for these given identifiers
42 # The mask + 1 value is the size of the hastable to create
43 fun phand
(ids
: Array[Int]): Int
47 # If ids is null return 1
48 if ids
.length
== 0 then
59 mask
= orMask ^ andMask
61 # Re-initialize the hashtable with null values
62 for i
in [0..(mask
+1)] do tempht
[i
] = null
64 # Optimize the already computed mask
66 var i
= mask
.highest_bit
68 if mask
.getbit
(i
) == 1 then
69 newmask
= mask ^
(1 << i
)
71 # If there is no collision, replace the old mask
72 if phandp
(ids
, newmask
) then
83 # Checks if the mask is a perfect hashing function for
85 fun phandp
(ids
: Array[Int], mask
: Int): Bool
89 if tempht
[hv
] == mask
then
99 # Perfect numbering : give new free identifiers
100 # ids : identifiers to hash (super-classes)
101 # n : number of required free identifiers
102 # idc : This array will be filled with n free identifiers
103 # return the size of hashTable to create for theses identifiers (mask + 1)
104 # var ph = new Perfecthashing
105 # var idc = new Array[Int]
106 # assert ph.pnand([3, 7, 10], 1, idc) == 6
108 # var idc1 = new Array[Int]
109 # assert ph.pnand([3, 7, 10], 1, idc1) == 6
110 # assert idc1[0] == 6
111 fun pnand
(ids
: Array[Int], n
: Int, idc
: Array[Int]): Int
113 var mask
= phand
(ids
) -1
115 while n
+ids
.length
> (1 << mask
.number_bits
(1)) do
116 # When there are not enough 1-bits
117 if mask
.getbit
(i
) == 0 then
118 mask
= mask ^
(1 << i
)
123 # Resetting hashtable
124 for j
in [0..(mask
+1)] do tempht
[j
] = null
126 # Set the temporary hashtable for `compute_least_free_ids`
129 # Fill the given array with n free identifiers
130 compute_least_free_ids
(n
, mask
, idc
)
136 # Compute free identifiers for future perfect numbering
137 # n : number of required ids
138 # mask : perfect hashing parameter
139 # idc : This array will be filled with n free identifiers
140 private fun compute_least_free_ids
(n
: Int, mask
: Int, idc
: Array[Int])
143 idc
.push
(first_valid_id
(mask
))
148 # Returns the first valid free identifier which correspond to this mask
149 private fun first_valid_id
(mask
: Int): Int
151 # Search for the first valid free identifier
152 var inter
= interval
.iterator
155 while inter
.is_ok
and not found
do
156 var i
= inter
.item
.first
.as(not null)
157 while i
!= inter
.item
.second
and not found
do
158 # Tests if this id is free for this mask
161 # If the hashtable if full, push an empty item
162 if hv
>= tempht
.length
then
166 if tempht
[hv
] != mask
then
178 # Updates the structure of union of intervals
179 if id
== inter
.item
.first
then
180 if inter
.item
.first
== inter
.item
.second
then
183 inter
.item
.first
+= 1
186 if id
!= inter
.item
.first
and id
!= inter
.item
.second
then
187 # We need to split in two this interval
188 var last
= inter
.item
.second
189 inter
.item
.second
= id
- 1
192 var p
= new Couple[nullable Int, nullable Int](id
+ 1, last
)
194 inter
.insert_before
(p
)
199 inter
.item
.second
= id
- 1