Ruby Trie

trie.rb

class Trie
  include Enumerable

  def initialize
    @leaf, @children = false, {}
  end

  def <<(value)
    add_enum(value_to_enum(value))
  end

  def include?(value)
    include_enum?(value_to_enum(value))
  end

  def each
    return enum_for(:each) unless block_given?

    children.each do |key, child|
      yield key if child.leaf?
      child.each { |suffix| yield key + suffix }
    end
  end

  protected
  attr_writer :leaf

  def leaf?
    @leaf
  end

  def add_enum(enum)
    begin
      child = children[enum.next] ||= self.class.new
      child.add_enum(enum)
    rescue StopIteration
      self.leaf = true
    end
    self
  end

  def include_enum?(enum)
    children.fetch(enum.next).include_enum?(enum)
  rescue StopIteration
    leaf?
  rescue KeyError
    false
  end

  private

  attr_reader :children

  def value_to_enum(value)
    value.each
  end
end

class StringTrie < Trie
  private

  def value_to_enum(value)
    value.each_char
  end
end