lib/perfect_hashing.nit

   1 # This file is part of NIT ( http://www.nitlanguage.org ).
   2 #
   3 # Copyright 2014 Julien Pagès <julien.pages@lirmm.fr>
   4 #
   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
   8 #
   9 #     http://www.apache.org/licenses/LICENSE-2.0
  10 #
  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.
  16
  17 # Perfect hashing and perfect numbering
  18 module perfect_hashing
  19
  20 # Class for Perfect Hashing operations with perfect numbering
  21 # It also stores the free identifiers for the perfect numbering
  22 class Perfecthashing
  23
  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]]
  28
  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]
  32
  33         # Initialize the structure of free identifiers
  34         init
  35         do
  36                 # By default, all identifiers are available
  37                 interval.push(new Couple[nullable Int, nullable Int](1, null))
  38         end
  39
  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
  44         do
  45                 var mask = 1
  46
  47                 # If ids is null return 1
  48                 if ids.length == 0 then
  49                         return mask
  50                 end
  51
  52                 var orMask = 0
  53                 var andMask = 0
  54                 for i in ids do
  55                         orMask = orMask.bin_or(i)
  56                         andMask = andMask.bin_and(i)
  57                 end
  58
  59                 mask = orMask.bin_xor(andMask)
  60
  61                 # Re-initialize the hashtable with null values
  62                 for i in [0..(mask+1)] do tempht[i] = null
  63
  64                 # Optimize the already computed mask
  65                 var newmask = 0
  66                 var i = mask.highest_bit
  67                 while i != 0 do
  68                         if mask.getbit(i) == 1 then
  69                                 newmask = mask.bin_xor(1.lshift(i))
  70
  71                                 # If there is no collision, replace the old mask
  72                                 if phandp(ids, newmask) then
  73                                         mask = newmask
  74                                 end
  75                         end
  76
  77                         i -= 1
  78                 end
  79
  80                 return mask + 1
  81         end
  82
  83         # Checks if the mask is a perfect hashing function for
  84         # these identifiers
  85         fun phandp(ids: Array[Int], mask: Int): Bool
  86         do
  87                 for i in ids do
  88                         var hv = i.bin_and(mask)
  89                         if tempht[hv] == mask then
  90                                 return false
  91                         else
  92                                 tempht[hv] = mask
  93                         end
  94                 end
  95
  96                 return true
  97         end
  98
  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
 107         #     assert idc[0] == 4
 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
 112         do
 113                 var mask = phand(ids) -1
 114                 var i = 0
 115                 while n+ids.length > (1.lshift(mask.number_bits(1))) do
 116                         # When there are not enough 1-bits
 117                         if mask.getbit(i) == 0 then
 118                                 mask = mask.bin_xor(1.lshift(i))
 119                         end
 120                         i += 1
 121                 end
 122
 123                 # Resetting hashtable
 124                 for j in [0..(mask+1)] do tempht[j] = null
 125
 126                 # Set the temporary hashtable for `compute_least_free_ids`
 127                 phandp(ids, mask)
 128
 129                 # Fill the given array with n free identifiers
 130                 compute_least_free_ids(n, mask, idc)
 131
 132                 return mask + 1
 133         end
 134
 135
 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])
 141         do
 142                 while n != 0 do
 143                         idc.push(first_valid_id(mask))
 144                         n = n - 1
 145                 end
 146         end
 147
 148         # Returns the first valid free identifier which correspond to this mask
 149         private fun first_valid_id(mask: Int): Int
 150         do
 151                 # Search for the first valid free identifier
 152                 var inter = interval.iterator
 153                 var found = false
 154                 var id = 0
 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
 159                                 var hv = i.bin_and(mask)
 160
 161                                 # If the hashtable if full, push an empty item
 162                                 if hv >= tempht.length then
 163                                         tempht.push(null)
 164                                 end
 165
 166                                 if tempht[hv] != mask then
 167                                         found = true
 168                                         id = i
 169                                 end
 170                                 i = i + 1
 171                         end
 172
 173                         if not found then
 174                                 inter.next
 175                         end
 176                 end
 177
 178                 # Updates the structure of union of intervals
 179                 if id == inter.item.first then
 180                         if inter.item.first == inter.item.second then
 181                                 inter.delete
 182                         else
 183                                 inter.item.first += 1
 184                         end
 185                 else
 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
 190                                 inter.next
 191
 192                                 var p = new Couple[nullable Int, nullable Int](id + 1, last)
 193                                 if inter.is_ok then
 194                                         inter.insert_before(p)
 195                                 else
 196                                         interval.push(p)
 197                                 end
 198                         else
 199                                 inter.item.second = id - 1
 200                         end
 201                 end
 202
 203                 return id
 204         end
 205 end