lib/perfect_hashing/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 |= i
  56                         andMask &= i
  57                 end
  58
  59                 mask = orMask ^ 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 ^ (1 << 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 & 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         #
 105         #     var ph = new Perfecthashing
 106         #     var idc = new Array[Int]
 107         #     assert ph.pnand([3, 7, 10], 1, idc) == 6
 108         #     assert idc[0] == 4
 109         #     var idc1 = new Array[Int]
 110         #     assert ph.pnand([3, 7, 10], 1, idc1) == 6
 111         #     assert idc1[0] == 6
 112         fun pnand(ids: Array[Int], n: Int, idc: Array[Int]): Int
 113         do
 114                 var mask = phand(ids) -1
 115                 var i = 0
 116                 while n+ids.length > (1 << mask.number_bits(1)) do
 117                         # When there are not enough 1-bits
 118                         if mask.getbit(i) == 0 then
 119                                 mask = mask ^ (1 << i)
 120                         end
 121                         i += 1
 122                 end
 123
 124                 # Resetting hashtable
 125                 for j in [0..(mask+1)] do tempht[j] = null
 126
 127                 # Set the temporary hashtable for `compute_least_free_ids`
 128                 phandp(ids, mask)
 129
 130                 # Fill the given array with n free identifiers
 131                 compute_least_free_ids(n, mask, idc)
 132
 133                 return mask + 1
 134         end
 135
 136
 137         # Compute free identifiers for future perfect numbering
 138         # n : number of required ids
 139         # mask : perfect hashing parameter
 140         # idc : This array will be filled with n free identifiers
 141         private fun compute_least_free_ids(n: Int, mask: Int, idc: Array[Int])
 142         do
 143                 while n != 0 do
 144                         idc.push(first_valid_id(mask))
 145                         n = n - 1
 146                 end
 147         end
 148
 149         # Returns the first valid free identifier which correspond to this mask
 150         private fun first_valid_id(mask: Int): Int
 151         do
 152                 # Search for the first valid free identifier
 153                 var inter = interval.iterator
 154                 var found = false
 155                 var id = 0
 156                 while inter.is_ok and not found do
 157                         var i = inter.item.first.as(not null)
 158                         while i != inter.item.second and not found do
 159                                 # Tests if this id is free for this mask
 160                                 var hv = i & mask
 161
 162                                 # If the hashtable if full, push an empty item
 163                                 if hv >= tempht.length then
 164                                         tempht.push(null)
 165                                 end
 166
 167                                 if tempht[hv] != mask then
 168                                         found = true
 169                                         id = i
 170                                 end
 171                                 i = i + 1
 172                         end
 173
 174                         if not found then
 175                                 inter.next
 176                         end
 177                 end
 178
 179                 # Updates the structure of union of intervals
 180                 if id == inter.item.first then
 181                         if inter.item.first == inter.item.second then
 182                                 inter.delete
 183                         else
 184                                 inter.item.first += 1
 185                         end
 186                 else
 187                         if id != inter.item.first and id != inter.item.second then
 188                                 # We need to split in two this interval
 189                                 var last = inter.item.second
 190                                 inter.item.second = id - 1
 191                                 inter.next
 192
 193                                 var p = new Couple[nullable Int, nullable Int](id + 1, last)
 194                                 if inter.is_ok then
 195                                         inter.insert_before(p)
 196                                 else
 197                                         interval.push(p)
 198                                 end
 199                         else
 200                                 inter.item.second = id - 1
 201                         end
 202                 end
 203
 204                 return id
 205         end
 206 end