#
# Simple implementation of a CuckooHash
# Copyright Chris TenHarmsel <chris@tenharmsel.com>
# Posted on http://www.staticmethod.net
#
class CuckooHash

  # Initialize some starting values
  def initialize(startingSize)
    @size = startingSize
    @storage = Array.new(@size)
    @primes = [1091, 1151, 1229, 1277, 1289, 1301, 1319, 1427, 1451, 1481, 1487, 1607, 1619, 1667, 1697, 1721, 1787, 1871, 1877, 1931]
    @primeOne = [1091, 1151];
    @primeTwo = [1229, 1277];
  end

  # Prints some simple stats about the current map
  def stats
    puts "Size: #{@size}"
    puts "Count: #{@storage.compact.size}"
    puts "PrimeOne: #{@primeOne[0]}, #{@primeOne[1]}; PrimeTwo: #{@primeTwo[0]}, #{@primeTwo[1]}"
  end

  # Internal hashing method, called by two separate hashing methods with different seeds
  def hash(primeOne, primeTwo, word)
    hash = 0;
    word.each_byte do |char|
      hash = (hash * primeOne) + char
      primeOne *= primeTwo
    end
    return hash % (@size-1)
  end

  # First hash method
  def hashOne(word)
    return hash(@primeOne[0], @primeOne[1], word)
  end

  # Second hash Method
  def hashTwo(word)
    return hash(@primeTwo[0], @primeTwo[1], word)
  end

  # Inserts a word into the hash
  def insert(word)
    h1 = hashOne(word)
    h2 = hashTwo(word)
    return true if(@storage[h1] == word || @storage[h2] == word)
    
    # Wasn't found, find a place for it
    pos = h1
    100.times do
      if (@storage[pos].nil?)
        @storage[pos] = word;
        return
      end
      
      # put word in it's place, save what _was_ there
      y = @storage[pos];
      @storage[pos] = word
      word = y

      # If the last position we examined is the new item's hashOne,
      # try it's hashTwo
      pos = hashTwo(word) if(pos == hashOne(word))
      # Loop, trying to place the new word
      
    end
    # This means we didn't find a new spot for all the words 
    rehash();
    insert(word);
  end

  # Simple rehash method
  def rehash
    # get the current values
    vals = @storage.compact
    
    # increase the size of the storage if the load is larger than 0.6
    if((vals.size.to_f / @size.to_f) > 0.5)
      @size *= 2 
    end

    # Reset the storage
    @storage = Array.new(@size)
    
    # Change the prime values
    @primeOne[0] = @primes[(rand * @primes.size).floor];
    @primeOne[1] = @primes[(rand * @primes.size).floor];
    @primeTwo[0] = @primes[(rand * @primes.size).floor];
    @primeTwo[1] = @primes[(rand * @primes.size).floor];

    # Re-insert the values into the new storage
    vals.each do |val|
      insert(val)
    end
  end

  # Checks if a value is in the hash
  def lookup(val)
    # Uncomment the following line if you want to see a "." every time we need to look
    # at the second spot
    putc "." if(@storage[hashOne(val)] != val)
    return (@storage[hashOne(val)] == val) || (@storage[hashTwo(val)] == val)
  end
end


foo = CuckooHash.new(40000)
words = %w{ one two three four five six seven eight nine ten}

# Insert 100 items
800.times do |i|
  words.each do |word|
    foo.insert("#{word}-#{i}")
  end
end

# Look for the 100 items
allFound = true
800.times do |i|
  words.each do |word|
    allFound = allFound && foo.lookup("#{word}-#{i}")
  end
end


puts "All Found: #{allFound}"
foo.stats