comments

First – thanks for doing this, and for a very interesting task! I would’ve
submitted earlier, except I was moving over the weekend and was able to sit
down to this problem only two hours ago.

I decided to store edits rather than snapshots; I’m not sure how strict you are
about edits only to the four methods, but I renamed @snapshots and @reverted to
@undos and @redos for clarity.

My first approach was to store a ‘reverse’ call (e.g.,
{method: :split!, args: [position, text.size]}
for the add_text method), but while this works beautifully for undo, it doesn’t
for redo (for obvious reasons). I ended up storing a bit more agnostic
edit/position/text triples. I think in reality I’d rather do them as Structs
for clarity and possible future extends, but I didn’t want to add new classes
at this point.

I increment the add_text’s position to be positive, assuming it’s not smaller than
-contents.size – but if it were the original insert would throw an exception anyway.

The @redos.clear calls are added for behavioural compatibility with the
original version; the test passes without them, but it does not attempt redos
which do not follow an undo.

I don’t like the case constructs and the fact that they are so similar (and
make the whole undo/redo methods so symmetric); I toyed with the idea of storing
blocks that would do the Right Thing™ when called, but decided this is
something I’d introduce when I had a third editing action.

Memory gains are huge when the edits are (on average) much smaller than the size of
the document; performance-wise this approach is of course slower than just returning
the top-of-the-stack document, but in practice shouldn’t matter with most real-life
document and edit sizes.

lib_text_edit_naive.rb

module TextEditor
  class Document
    def initialize
      @contents = ""
      @undos = []
      @redos = []
    end
    
    attr_reader :contents

    def add_text(text, position=-1)
      position += contents.size + 1 if position < 0
      contents.insert(position, text)
      @undos << {edit: :add, position: position, text: text}
      @redos.clear
    end

    def remove_text(first=0, last=contents.length)
      text = contents.slice!(first...last)
      @undos << {edit: :remove, position: first, text: text}
      @redos.clear
    end

    def undo
      return if @undos.empty?

      action = @undos.pop

      case action[:edit]
      when :add    then contents.slice! action[:position], action[:text].size
      when :remove then contents.insert action[:position], action[:text]
      end

      @redos << action
    end

    def redo
      return if @redos.empty?

      action = @redos.pop

      case action[:edit]
      when :add    then contents.insert action[:position], action[:text]
      when :remove then contents.slice! action[:position], action[:text].size
      end

      @undos << action
    end

  end
end

memory usage

Starting Memory:
 total            24264K
Adding 100 characters, 1 at a time
Current memory footprint:
 total            24396K
Adding 1000 characters, 1 at a time
Current memory footprint:
 total            24804K
Adding 10000 characters, 1 at a time
Current memory footprint:
 total            28084K
Adding 100000 characters, 1 at a time
Current memory footprint:
 total            70492K
Took 7.534805521s to run