Undo/Redo с использованием Memento: Stack, Queue или просто LinkedList?

Question

Что лучше всего при внедрении Memento pattern (for Undo/Redo)

в коллекции ведьм, чтобы сохранить память?

В принципе, мне нужно это (C = изменение, и = расстегнуть, г = повтор):

    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

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

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

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

Answer 3

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

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

Answer 4

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

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

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