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
: 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
: Array[nullable Int]
33 # Initialize the structure of free identifiers
36 # By default, all identifiers are available
37 interval
= new List[Couple[nullable Int, nullable Int]]
38 interval
.push
(new Couple[nullable Int, nullable Int](0, null))
39 tempht
= new Array[nullable Int]
42 # Returns a mask composed by discriminants bits
43 # for these given identifiers
44 # The mask + 1 value is the size of the hastable to create
45 fun phand
(ids
: Array[Int]): Int
49 # If ids is null return 1
50 if ids
.length
== 0 then
57 orMask
= orMask
.bin_or
(i
)
58 andMask
= andMask
.bin_and
(i
)
61 mask
= orMask
.bin_xor
(andMask
)
63 # Re-initialize the hashtable with null values
64 for i
in [0..mask
+1] do tempht
[i
] = null
66 # Optimize the already computed mask
68 var i
= mask
.highest_bit
70 if mask
.getbit
(i
) == 1 then
71 newmask
= mask
.bin_xor
(1.lshift
(i
))
73 # If there is no collision, replace the old mask
74 if phandp
(ids
, newmask
) then
85 # Checks if the mask is a perfect hashing function for
87 fun phandp
(ids
: Array[Int], mask
: Int): Bool
90 var hv
= i
.bin_and
(mask
)
91 if tempht
[hv
] == mask
then
101 # Perfect numbering : give new free identifiers
102 # ids : identifiers to hash (super-classes)
103 # n : number of required free identifiers
104 # idc : This array will be filled with n free identifiers
105 # return the size of hashTable to create for theses identifiers (mask + 1)
106 # var ph = new Perfecthashing
107 # var idc = new Array[Int]
108 # assert ph.pnand([3, 7, 10], 1, idc) == 6
110 # var idc1 = new Array[Int]
111 # assert ph.pnand([3, 7, 10], 1, idc1) == 6
112 # assert idc1[0] == 6
113 fun pnand
(ids
: Array[Int], n
: Int, idc
: Array[Int]): Int
115 var mask
= phand
(ids
) -1
117 while n
+ids
.length
> (1.lshift
(mask
.number_bits
(1))) do
118 # When there are not enough 1-bits
119 if mask
.getbit
(i
) == 0 then
120 mask
= mask
.bin_xor
(1.lshift
(i
))
125 # Resetting hashtable
128 # Fill the given array with n free identifiers
129 compute_least_free_ids
(n
, mask
, idc
)
135 # Compute free identifiers for future perfect numbering
136 # n : number of required ids
137 # mask : perfect hashing parameter
138 # idc : This array will be filled with n free identifiers
139 private fun compute_least_free_ids
(n
: Int, mask
: Int, idc
: Array[Int])
142 idc
.push
(first_valid_id
(mask
))
147 # Returns the first valid free identifier which correspond to this mask
148 private fun first_valid_id
(mask
: Int): Int
150 # Search for the first valid free identifier
151 var inter
= interval
.iterator
154 while inter
.is_ok
and not found
do
155 var i
= inter
.item
.first
.as(not null)
156 while i
!= inter
.item
.second
and not found
do
157 # Tests if this id is free for this mask
158 var hv
= i
.bin_and
(mask
)
160 # If the hashtable if full, push an empty item
161 if hv
>= tempht
.length
then
165 if tempht
[hv
] != mask
then
177 # Updates the structure of union of intervals
178 if id
== inter
.item
.first
then
179 if inter
.item
.first
== inter
.item
.second
then
182 inter
.item
.first
+= 1
185 if id
!= inter
.item
.first
and id
!= inter
.item
.second
then
186 # We need to split in two this interval
187 var last
= inter
.item
.second
188 inter
.item
.second
= id
- 1
191 var p
= new Couple[nullable Int, nullable Int](id
+ 1, last
)
193 inter
.insert_before
(p
)
198 inter
.item
.second
= id
- 1