На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
Модераторы: Qraizer, Hsilgos
  
> Undo - Redo
    Программа использует одну структуру данных. Действия пользователя так или иначе ее изменяют.
    У меня есть реализованная версия своего велосипеда Undo - Redo. Опишу принцип.

    1. Есть массив текущих структур ELEMENT element[1000]
    2. Есть массив сохраняемых структур ELEMENT stepelement[50][1000]
    3. Переменные
    step[0] // текущий шаг
    step[1] // граница для redo
    step[2] // граница для undo
    ExpandedWrap disabled
      struct ELEMENT
      {
         double coord[3][20];
         // ...
      };
      extern ELEMENT element[1000];
      extern int step[3];
      extern ELEMENT stepelement[50][1000]; // где 50 это максимальное число шагов Undo (и Redo если пользователь выполнил 50 Undo подряд)
      extern int stepelementubound[50];

    Реализация происходит следующим образом есть функция DataSet() которая вызывается в местах где нужно запомнить состоятие программы. Ее действие: увеличивает step[0] и записывает текущую структуру в массив структур. И есть функция DataGet() которая считывает текущую структуру из массива структур.
    Undo() / Redo() - уменьшает / увеличивает текущий шаг и вызывает DataGet(). Небольшой нюанс при достижении границы нужно "закольцевать" счетчики.
    Всё как бы работает.

    Вопрос: Есть ли способ сделать Undo - Redo проще, или порекомендуйте какие-нибудь примеры или статьи на эту тему.
    Сообщение отредактировано: Mr.Brooks -
      Ну... насколько мне известно, стараются сделать хранение истории эффективнее. Поэтому хранят не состояния объектов, а действия, приведшие к изменению состояния. Конкретно вот их и пишут в очередь redo, а в стек undo – соответственно обратные действия, т.е. нейтрализующие изменения. Например. Изменение значения поля someField, равное someValue, на newValue будет отражена в стеке undo – функтором, меняющим поле someField на someValue, а при его достижении – в очереди redo функтором, меняющим его на newValue. Операции Undo() и Redo() соответственно манипулируют головами и хвостами. И ещё redo сбрасывается, когда после Undo() действия Redo() не были востребованы.
      Но это всё вопрос оптимизации, а не простоты. Зато этот патерн оказывается полезным и для других применений, помимо undo/redo. Например, при создании списка действий без их исполнения с последующей пакетной его имплементацией. Подобные вещи востребованы для гарантий транзакционной целостности группы операций, например. Partition manager-ом пользовался?
      Сообщение отредактировано: Qraizer -
        Цитата Qraizer @
        а действия, приведшие к изменению состояния. Конкретно вот их и пишут в очередь redo, а в стек undo – соответственно обратные действия, т.е. нейтрализующие изменения.

        Только только об этом читал :)
        Паттерн проектирования называется Command. Именно экземпляры этих классов собираются в очередь.
        В каждом экземпляре реализованы две виртуальные функции Execute и UnExecute.
          Qraizer, прочитал, и ничего не понял. Перечитал ещё раз. Оказалось, ты просто некоторые детали опустил.

          Перескажу всё своими словами.
          Когда мы что-то меняем, мы пишем в стек Undo информацию, необходимую для отмены сделанного изменения. Обычно это какая-то функция с необходимыми для выполнения отмены данными. Удобно объединить эту в функтор.
          Для примера рассмотрим текстовый редактор (простейший, проще даже виндового нотепада, который умеет только вставлять вводимые символы в позицию курсора, и удалять куски текста).
          При вводе символов пишем в стек сколько символов вставлено, в какой строке и с какой позиции, какие именно символы вставлены можно не писать. По "Undo" эти символы будут удалены из текста.
          При удалении символов пишем в стек в каком месте, и какие именно символы мы удалили. По Undo эти символы надо будет вставить в текст.

          Команда "Undo" забирает из стека Undo порцию данных, выполняет отмену и пишет в стек ReDo информацию, необходимую для восстановления изменения.
          Если команда "Undo" удалила символы, то в стек Redo записывается позиция и удалённые символы (которые в данном случае можно получить из имеющегося текста).
          Если команда "Undo" вставила символы, то в стек Redo запиcывается позиция и количество вставлнных символов

          Команда "ReDo" действует в точности так же, как и "Undo", с той лишь разницей, что информацию берёт из стека ReDo, а данные для своей отмены заносит в "Undo"

          Так что фактически "Undo" и "ReDo" имеет смысл реализовывать одной процедурой, просто поменяв местами стеки, передавая их как параметры.

          Ну, и как написал Qraizer, когда мы вносим изменение сами, надо не забыть очистить стек ReDo. Ну и при загрузке файла надо почистить оба стека. Некоторые редакторы чистят оба стека также при сохранении. А некоторые не чистят.
          В некоторых программах ограничивают размер стека Undo (ReDo и так не может стать больше чем Undo), отбрасывая самые ранние записи, расположенные у самого дна.
            Нашел информацию что undo - redo возможно сделать двумя способами:
            1. Команда - антикоманда.
            2. Записывать переменные (делать точки восстановления)

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

            ExpandedWrap disabled
                
              struct ELEMENT
              {
                  double coord[3][20];
                  char name[256];
                  int type;
                  // ... и таких полей штук 50
              };
               
              extern ELEMENT element[1000];
              extern int step[3];
              extern ELEMENT stepelement[50][1000];
              extern int stepelementubound[50];
               
              void DataGet()
              {
                  int i, k, n;
                  k = e::step[0];
                  n = e::stepelementubound[k];
                  for (i=0; i<n; i++)
                  {
                      e::element[i] = e::stepelement[k][i];
                  }
                  e::elementubound = n;
              }
               
              void DataRedo(HWND hwnd)
              {
                  int m;
                  m = 50;
                  if (e::step[0] != e::step[1])
                  {
                      e::step[0]++;
                  }
                  if (e::step[0] == m)
                  {
                      e::step[0] = 0;
                  }
                  DataGet();
                  DataStepEnable(hwnd);
                  DataRefresh(hwnd);
              }
               
              void DataSet(HWND hwnd)
              {
                  int i, k, n, m;
                  m = 50;
                  e::step[0]++;
                  if (e::step[0] > e::step[1])
                  {
                      e::step[1] = e::step[0];
                  }
                  if (e::step[0] == m)
                  {
                      e::step[0] = 0;
                  }
                  if (e::step[1] == m)
                  {
                      e::step[1] = 0;
                  }
                  if (e::step[1] == e::step[2])
                  {
                      e::step[2]++;
                  }
                  if (e::step[2] == m)
                  {
                      e::step[2] = 0;
                  }
                  k = e::step[0];
                  n = e::elementubound;
                  for (i=0; i<n; i++)
                  {
                      e::stepelement[k][i] = e::element[i];
                  }
                  e::stepelementubound[k] = n;
                  DataStepEnable(hwnd);
              }
               
              void DataUndo(HWND hwnd)
              {
                  int m;
                  m = 50;
                  if (e::step[0] != e::step[2])
                  {
                      e::step[0]--;
                  }
                  if (e::step[0] == -1)
                  {
                      e::step[0] = m - 1;
                  }
                  DataGet();
                  DataStepEnable(hwnd);
                  DataRefresh(hwnd);
              }


            Маленький вопрос в рамках этой темы: чем плох массив струкрур stepelement[50][1000];
            Как не программист по образованию, я не вижу подводных камней, но может они здесь есть ?

            Всем спасибо.
            Сообщение отредактировано: Mr.Brooks -
              Цитата Mr.Brooks @
              я не вижу подводных камней, но может они здесь есть ?

              Подводные камни есть - во втором случая обычно будет нерациональное использование ресурсов, перерасход. Представь что у тебя в переменной 1GB массив, и ты произвел команду "инвертировать первую половину по xor 0x55. Используя первый подход тебе нужно повторить эту же операцию еще раз и получишь откат. Во втором случае + 1GB для бэкапа переменной вынь да положь!
                Цитата Mr.Brooks @
                Маленький вопрос в рамках этой темы: чем плох массив струкрур stepelement[50][1000];

                Не знаю всех особенностей твоей программы, но всё-таки использование
                массивов не рационально.
                Если он большой, значит тратим ресурсы зря.
                Если это обычный массив - а вдруг его не хватит ?
                ---
                Полагаю, что лучше использовать, например, список.
                Тогда он вырастет до нужных размеров и всё.
                  Цитата
                  Не знаю всех особенностей твоей программы

                  Это кинематическая схема из максимум 1000 эл каждый имеет страницу свойств. А дальше расчет - чистая математика, вывод результатов.
                  Цитата
                  Если это обычный массив - а вдруг его не хватит ?

                  Проверку делаю при добавлении или вставке, если больше чем массив - сообщение, и добавить невозможно.
                  Цитата
                  Полагаю, что лучше использовать, например, список.

                  Я уже просматриваю разные варианты и список в том числе. Но есть у меня одна идея, а что если "заархивировать" структуру перед ее сохранением,
                  сделаю следующее - склею её в строку. А когда нужно разрежу и воосстановлю в структуру. По моим подсчетам выйгрыш в 20 раз.
                  В С# есть такие замечательные вещи .ToString() .Join() .Split() думаю и здесь нужно такие сделать.
                  Сообщение отредактировано: Mr.Brooks -
                    В общем, Mr.Brooks, если резюмировать, кроме как к объёму хранимых данных, претензий у нас нет. :)
                      Недостаток первого способа в том, что каждая команда должна уметь делать свой откат (и тоже командой, которая это умеет).
                      Во втором случае сами команды делать ничего по откатам делать не должны, но тратится очень много ресурсов.

                      Второй способ выгоден, если состояние системы меняется очень сильно - к примеру, почти все элементы меняют своё состояние.
                      Вообще-то есть вариант второго способа, запоминать в контрольных точках не состояние всей системы, а только её изменение. Если изменения затрагивают не всю систему, а только часть, это позволяет заметно сократить объём памяти.

                      Можно совмещать эти способы. В случае больших изменений сохранять состояние, а в случае мелких сохранять изменение или команду.
                      0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                      0 пользователей:


                      Рейтинг@Mail.ru
                      [ Script execution time: 0,0417 ]   [ 17 queries used ]   [ Generated: 28.03.24, 12:54 GMT ]