mruhist.rb

#
# An Array-like class that's used for a very specific purpose: the `out[]` array
# in Pry. MRU stands for most-recently-used.)
#
# It acts like an array with a maximum size -- if you try to add more elements than
# the maximum, the elements at the beginning of the array are discarded.
#
# Also, it keeps track of which entries are most recently accessed, and throws
# out only the oldest entries.
#
# Note: Doesn't have slicing support.
#
class MRUHistory
  
  attr_reader :max_size
  
  def initialize(max_size=20)
    @max_size   = max_size
    @entries    = {} # the key is the array index, and the value is the array value
    @ordering   = [] # the MRU ordering of @entries' keys 
    @next_index = 0  # the index to assign to a newly appended element
  end
  
  #
  # Sanity-check (for testing purposes.)
  #
  def sanity_check
    raise "Entries and order are differing lengths: #{@entries.inspect}, #{@ordering.inspect}" unless @entries.size == @ordering.size
    raise "@ordering and @entries.keys are not identical: #{@entries.inspect}, #{@ordering.inspect}" unless @ordering.sort == @entries.keys.sort
  end
  
  #
  # Append an element to the array (automatically removing old entries if the array has reached
  # its maximum size).
  # 
  def <<(value)
    #sanity_check
    
    @entries[@next_index] = value
    @ordering << @next_index
    
    @next_index += 1
    
    overflow = @entries.size - max_size
    if overflow > 0
      @ordering[0...overflow].each { |key| @entries.delete(key) }
      @ordering[0...overflow] = [] # remove entries
    end
  end
  
  #
  # Reorder the array so this key is at the "top" (end). (If the key doesn't exist yet,
  # it's added to the end.)
  #
  def push_to_top(key)
    if index = @ordering.index(key)
      @ordering << @ordering[index]
      @ordering.delete_at(index)
    else
      sanity_check
    end
  end
  
  #
  # Access a value in the array and update the MRU ordering.
  # (Return `nil` if this entry was discarded or doesn't exist.)
  #
  def [](key)
    #sanity_check
    if value = @entries[key]
      push_to_top(key) # maintain MRU ordering
      value
    else
      nil
    end
  end
  
  
  ## Array-like accessors
  
  include Enumerable
  
  def each(&block)
    @ordering.each do |key|
      yield @entries[value]
    end
  end
  
  def to_a
    @ordering.map{ |key| @entries[key] }
  end

  def size
    @entries.size
  end


  ## Array-like comparisons  
  
  include Comparable
  
  def <=>(other)
    to_a <=> other
  end
  
end

mruhist_spec.rb

$: << "."

require 'mruhist'

describe MRUHistory do
  
  before :each do
    @h = MRUHistory.new(4)
  end
  
  it "does everything!" do

    @h << "blah"
    @h << "whee"
    @h << "what"
    @h.should == ["blah", "whee", "what"]

    @h[0].should == "blah"
    @h[1].should == "whee"
    @h[2].should == "what"
    @h[0]
    @h.should == ["whee", "what", "blah"]
    
    @h << "extra"
    @h << "extra"
    @h << "extra"
    @h << "extra"
    @h << "extra"
    @h << "extra"
    
    @h.should == ["extra"] * 4
    @h.size.should == 4
    
  end  

end