# encoding: UTF-8
#
# ハッシュ表 (激突の場合、チェイン法使用)
#

class HashDictionary
  def initialize(occupancy)
    @occupancy = occupancy                     # (最大) 占有率
    @count = 0                                 # 保存されている項目の数
    @size = 1                                  # ハッシュ表の大きさ
    init_table
  end
  
  def init_table
    @table = Array.new(@size) { [] }           # ハッシュ表そのもの
  end                                          # 簡単のため、連結リストの代わり配列を使用
   
  def hash_function(key)                       # ハッシュ関数
    key.hash % @size                           # Ruby のハッシュ関数を再利用
  end
  
  def find_bin(key)                            # ハッシュ表の場所の特定
    @table[hash_function(key)]
  end
  
  def find(key)
    find_bin(key).each do |entry|
      return entry.value  if entry.key == key
    end
    warn "Key #{key} not found"
  end

  def expand
    @size = @size * 2 + 1                      # 新しい大きさの計算
    old_table = @table
    init_table                                 # 新しいハッシュ表の作成
    old_table.each do |bin|
      bin.each do |entry|
        @count -= 1                            # 項目の数の調整
        insert entry
      end
    end
  end
  
  def insert(entry)
    @count += 1
    expand  if @count > @size*@occupancy
    find_bin(entry.key) << entry               # 項目の追加
  end
  
  def delete(key)
    find_bin(key).delete_if { |entry| entry.key==key and @count-=1 }
  end
  
  
  
  def print_stats
    puts
    puts "Number of entries: #{@count}"
    puts "Number of bins: #{@size}"
    puts "Average bin size: #{@count.to_f / @size}"
    @table.group_by { |bin| bin.size }.sort.each do |size, bins|
      puts "Number of bins of size #{size}: #{bins.size}"
    end
  end
end