Отменить / Повторить, используя Memento: стек, очередь или просто LinkedList?

Question

Что лучше всего при реализации Шаблон Memento (для Undo / Redo)

в коллекции ведьм для хранения сувениров?

В принципе, мне нужно это (c = изменить, u = отменить, r = повторить):

                  0
                  *c
            -1    0
                  *c
      -2    -1    0
                  *c
-3    -2    -1    0
                  <u
      -2    -1    0    1
                  *c
-3    -2    -1    0

Варианты:

• LinkedList - возможно в принципе, возможно, не оптимизировано.
• Очередь - не приспособлен для этой задачи, ИМО.
• Стек - не приспособлен для отмены и повтора;
• Двойной стек - может быть оптимальным, но не может контролировать отмену максимального размера.

Answer 1

Наконец, я использовал LinkedList

Public Sub Add(ByVal item As T)
  If _list.Count > 0 Then
    If Me.IsFull Then
      ' we forgot (delete) the oldest state '
      _list.RemoveFirst()
    End If
    ' remove all the following the current items objects '
    Dim lastNode As LinkedListNode(Of T) = _list.Last
    While Not Object.ReferenceEquals(_currentNode, lastNode)
      _list.RemoveLast()
      lastNode = _list.Last
    End While
  End If

  ' add the new item and point current to it '
  _currentNode = _list.AddLast(item)
End Sub

Answer 2

A двусторонняя очередь предпочтительно используется для эффективной поддержки операций отмены повторения. Когда пользователь вводит слова, узлы вставляются в очередь, а указатель заголовка указывает на текущее местоположение. Когда запускается операция отмены, просто переместите головку на предыдущий узел, а при операции повтора переместите указатель головки на следующую позицию в списке. В случае операции редактирования удалите все узлы справа от головки и вставьте в конец головки. Таким образом, мы можем выполнить отмену повтора за O (1) сложность времени.

Answer 3

Хотите ли вы, чтобы пользователь мог выбрать более одного элемента для отмены или возврата?

Если это так, то вы хотели бы использовать общий список или ObservableCollection (если WPF / Silverlight), чтобы элементы могли отображаться в пользовательском интерфейсе. Вы можете использовать два списка: один для отмены и один для повторения.

Answer 4

Используйте двусвязный список. Когда пользователи используют отмены / повторы, они могут индексировать состояние несколько раз (например, сделать 4 отмены, а затем понять, что они зашли слишком далеко и выполнить повтор). Один стек или очередь не будут поддерживать это.

Два стека будут поддерживать отмену и повтор, но я думаю, что их использование - пустая трата времени. Все повторные сувениры будут удалены, как только пользователь выполнит редактирование (которое создаст новый сувенир). Таким образом, в большинстве случаев приложение не будет напоминать «повторить».

Предполагая, что у вас есть сборка мусора, так как вы пометили его .net: Когда пользователь выполняет редактирование, все, что вам нужно будет сделать с двусвязным списком, - установить ссылку на заголовок связанного списка на текущий сувенир. Если вы используете стек, то вам придется либо создать новый стек, либо вытолкнуть все из него, чтобы gc освободил повторные сувениры.

Answer 5

Когда вы отмените, вы захотите вернуться к последним перезаписанным данным. Так что сувенир, который вы захотите использовать, будет последним добавленным в коллекцию. Так как стеки являются последними в очереди (LIFO), они должны быть идеальными для ваших намерений.

Примечание. Возможно, вы захотите взглянуть на шаблон команды, поскольку он очень полезен для реализации функций отмены.

Редактировать: не заметил, что вы хотите повторить. Если вы вытолкнете что-нибудь из вашего стека, то избавитесь от него, так что он будет бесполезен в ваших целях Связанный список должен работать.