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

class HashDictionary
  def initialize (max_occupancy = 5)
    @max_occupancy = max_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)
    found = find_bin(key).find { |entry| entry.key==key }
    found.value or warn "Key #{key} not found"
  end

  def expand
    @size = @size * 2 + 1                      # 新しい大きさの計算
    @count = 0
    old_table = @table
    init_table                                 # 新しいハッシュ表の作成
    old_table.each do |bin|
      bin.each do |entry|
        insert entry
      end
    end
  end
  
  def insert(entry)
    @count += 1
    expand  if @count > @size*@max_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

if __FILE__ == $0                   ## このファイルが直接 ruby Ahashdictionary.rb
                                    ## として呼び出された場合のみ実行
  class Fixnum                      # HashDictionary に整数を直接追加できる
    def key()  self  end            # ために整数を拡張
    def value()  self  end
  end

  hash_dict = HashDictionary.new(3)
  1000.times do |n|
    #puts
    #hash_dict.print_stats
    r = rand 100000
    #puts "Inserting #{r}"
    hash_dict.insert r
  end

  puts hash_dict.inspect
  hash_dict.print_stats
end