class Hamster::Trie

def delete(key)

Returns a copy of self with the given key (and associated value) deleted. If not found, returns self. 
def delete(key)
  find_and_delete(key) || Trie.new(@significant_bits)
end

def delete_at(index = @entries.index { |e| e })

Returns a replacement instance after removing the specified entry. If empty, returns nil 
def delete_at(index = @entries.index { |e| e })
  yield(@entries[index]) if block_given?
  if size > 1
    entries = @entries.dup
    child = @children[index]
    if child
      children = @children.dup
      children[index] = child.delete_at do |entry|
        entries[index] = entry
      end
    else
      entries[index] = nil
    end
    self.class.new(@significant_bits, entries, children || @children)
  end
end

def each

Calls block once for each entry in the trie, passing the key-value pair as parameters. 
def each
  @entries.each { |entry| yield(entry) if entry }
  @children.each do |child|
    child.each { |entry| yield(entry) } if child
  end
  nil
end

def empty?

Returns true if the trie contains no key-value pairs. 
def empty?
  size == 0
end

def eql?(other)

Returns true if . eql? is synonymous with == 
def eql?(other)
  # return true if other.equal?(self)
  return false unless other.is_a?(self.class) && other.size == size
  each do |entry|
    return false unless other.include?(entry.key, entry.value)
  end
  true
end

def filter 

def filter
  reduce(self) { |trie, entry| yield(entry) ? trie : trie.delete(entry.key) }
end

def find_and_delete(key)

If empty, returns nil.
If not found, returns self.
Returns a replacement instance after removing the specified key. 
def find_and_delete(key)
  index = index_for(key)
  entry = @entries[index]
  if entry && entry.key.eql?(key)
    return delete_at(index)
  else
    child = @children[index]
    if child
      copy = child.find_and_delete(key)
      if !copy.equal?(child)
        children = @children.dup
        children[index] = copy
        return self.class.new(@significant_bits, @entries, children)
      end
    end
  end
  self
end

def get(key)

Retrieves the entry corresponding to the given key. If not found, returns nil. 
def get(key)
  index = index_for(key)
  entry = @entries[index]
  if entry && entry.key.eql?(key)
    entry
  else
    child = @children[index]
    if child
      child.get(key)
    end
  end
end

def has_key?(key)

Returns true if the given key is present in the trie. 
def has_key?(key)
  !! get(key)
end

def include?(key, value) 

def include?(key, value)
  entry = get(key)
  entry && value.eql?(entry.value)
end

def index_for(key) 

def index_for(key)
  (key.hash.abs >> @significant_bits) & 31
end

def initialize(significant_bits = 0, entries = [], children = []) 

def initialize(significant_bits = 0, entries = [], children = [])
  @significant_bits = significant_bits
  @entries = entries
  @children = children
end

def put(key, value)

Returns a copy of self with the given value associated with the key. 
def put(key, value)
  index = index_for(key)
  entry = @entries[index]
  if !entry || entry.key.eql?(key)
    entries = @entries.dup
    entries[index] = Entry.new(key, value)
    self.class.new(@significant_bits, entries, @children)
  else
    children = @children.dup
    child = children[index]
    children[index] = if child
      child.put(key, value)
    else
      self.class.new(@significant_bits + 5).put!(key, value)
    end
    self.class.new(@significant_bits, @entries, children)
  end
end

def put!(key, value)

Returns self after overwriting the element associated with the specified key. 
def put!(key, value)
  @entries[index_for(key)] = Entry.new(key, value)
  self
end

def reduce(memo) 

def reduce(memo)
  each { |entry| memo = yield(memo, entry) }
  memo
end

def size

Returns the number of key-value pairs in the trie. 
def size
  reduce(0) { |memo, item| memo.succ }
end