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                 phandp(ids, mask)
 125
 126                 # Fill the given array with n free identifiers
 127                 compute_least_free_ids(n, mask, idc)
 128
 129                 return mask + 1
 130         end
 131
 132
 133         # Compute free identifiers for future perfect numbering
 134         # n : number of required ids
 135         # mask : perfect hashing parameter
 136         # idc : This array will be filled with n free identifiers
 137         private fun compute_least_free_ids(n: Int, mask: Int, idc: Array[Int])
 138         do
 139                 while n != 0 do
 140                         idc.push(first_valid_id(mask))
 141                         n = n - 1
 142                 end
 143         end
 144
 145         # Returns the first valid free identifier which correspond to this mask
 146         private fun first_valid_id(mask: Int): Int
 147         do
 148                 # Search for the first valid free identifier
 149                 var inter = interval.iterator
 150                 var found = false
 151                 var id = 0
 152                 while inter.is_ok and not found do
 153                         var i = inter.item.first.as(not null)
 154                         while i != inter.item.second and not found do
 155                                 # Tests if this id is free for this mask
 156                                 var hv = i.bin_and(mask)
 157
 158                                 # If the hashtable if full, push an empty item
 159                                 if hv >= tempht.length then
 160                                         tempht.push(null)
 161                                 end
 162
 163                                 if tempht[hv] != mask then
 164                                         found = true
 165                                         id = i
 166                                 end
 167                                 i = i + 1
 168                         end
 169
 170                         if not found then
 171                                 inter.next
 172                         end
 173                 end
 174
 175                 # Updates the structure of union of intervals
 176                 if id == inter.item.first then
 177                         if inter.item.first == inter.item.second then
 178                                 inter.delete
 179                         else
 180                                 inter.item.first += 1
 181                         end
 182                 else
 183                         if id != inter.item.first and id != inter.item.second then
 184                                 # We need to split in two this interval
 185                                 var last = inter.item.second
 186                                 inter.item.second = id - 1
 187                                 inter.next
 188
 189                                 var p = new Couple[nullable Int, nullable Int](id + 1, last)
 190                                 if inter.is_ok then
 191                                         inter.insert_before(p)
 192                                 else
 193                                         interval.push(p)
 194                                 end
 195                         else
 196                                 inter.item.second = id - 1
 197                         end
 198                 end
 199
 200                 return id
 201         end
 202 end