class LiveSearch

  class HashFO < Hash
    # special hash that stores at most <size> keys
    # drops oldest keys first

    class KeyFO < Array
      def << arg
        # this is to ease the process of pushing a key to the front
        # and making sure there are no duplicates
        delete arg
        super
      end
    end

    attr_accessor :size, :keyfo

    def initialize size=10
      self.size = size
      self.keyfo = KeyFO.new
    end

    def []= *args
      key = args.first
      keyfo << key
      while keyfo.length > size # get rid of old keys
        delete keyfo.shift
      end
      super
    end

    def refresh key
      # again, make it easy to lengthen a keys lifespan
      keyfo << key if has_key? key
      self[key]
    end

    alias store []=
  end
  # END HashFO
  
  attr_accessor :list, :search_proc

  def initialize list, &s_proc
    # search is a proc for finding a regexp within list
    # should take 2 args (listitem, regexp)
    @list = list
    @search_proc = s_proc || Proc.new do |i,r|
      r.match i.to_s
    end # default search proc

    @results = HashFO.new 10
    # increasing this only helps how far back in the string changes will
    # start requiring global searches again
  end
  
  def _find str, l=nil
    l ||= list
    l.select {|i| search_proc.call i, /#{str}/i}
  end
  def _results_from_store words
    # fetch results from the @results hash if there, otherwise generate them
    word_str = words.join " "
    if @results[word_str]
      return @results.refresh(word_str)
    end
    if 1 >= words.length
      # chop off last letter and see if that's in the hash
      tmp = word_str[/(.*).$/,1]
      if @results[tmp]
        # it's there and apparently useful, make it live longer
        r = @results.refresh(tmp)
        # search for word_str in previous results
        @results[word_str] = _find word_str, r
      else
        # no previous results, search from global list
        @results[word_str] = _find word_str
      end
      return @results[word_str]
    else
      # more than one word, break it up
      # this helps when a letter other than the _last_ letter of the
      # search string changes
      last = words.pop
      tmp = _results_from_store(words)
      return @results[word_str] = _find(last, tmp)
    end
  end

  def search str
    words = str.split

    _results_from_store words
  end
end