Short memo

short_memo.rb

require 'set'

# A short buffer that can tell you if you've encountered a value recently
# without taking up too much memory.
# It keeps track of the n last items you've met

class ShortMemo
  def initialize(max_size: 10, reset_when_met: false)
    @max_size = max_size
    @reset_when_met = reset_when_met
    @queue = []
    @set = Set.new
  end

  def met?(item)
    if @set.member?(item)
      self.reset if @reset_when_met
      true
    else
      if @queue.size == @max_size
        out = @queue.pop
        @set.delete(out)
      end
      @set.add(item)
      @queue.unshift(item)
      false
    end
  end

  def reset
    @queue = []
    @set = Set.new
  end
end

short_memo_spec.rb

RSpec.describe ShortMemo do
  subject(:memo) do
    described_class.new(
      max_size: max_size,
      reset_when_met: reset_when_met,
    )
  end
  let(:max_size) { 3 }
  let(:reset_when_met) { false }

  describe "#met?" do
    context "when object was never met" do
      it "returns false and adds the object to memo" do
        expect(memo.met?("1")).to be_falsey
        expect(memo.met?("2")).to be_falsey
        expect(memo.met?("3")).to be_falsey
        expect(memo.met?("4")).to be_falsey
      end
    end

    context "when object was met recently (max_size times ago or less)" do
      context "when not reset_when_met" do
        let(:reset_when_met) { false }
        it "just returns true" do
          memo.met?("1")
          memo.met?("2")
          memo.met?("3")
          expect(memo.met?("1")).to be_truthy
          expect(memo.met?("1")).to be_truthy
          expect(memo.met?("2")).to be_truthy
        end
      end

      context "when reset_when_met" do
        let(:reset_when_met) { true }
        it "returns true and resets the memo" do
          memo.met?("1")
          memo.met?("2")
          memo.met?("3")
          expect(memo.met?("1")).to be_truthy
          expect(memo.met?("1")).to be_falsey
          expect(memo.met?("2")).to be_falsey
        end
      end
    end

    context "when object was met long ago (more than max_size)" do
      it "returns false" do
        memo.met?("1")
        memo.met?("2")
        memo.met?("3")
        memo.met?("4")
        expect(memo.met?("1")).to be_falsey
      end
    end
  end

  context "#reset" do
    it "empties the memo" do
      memo.met?("1")
      memo.reset
      expect(memo.met?("1")).to be_falsey
    end
  end
end