Re[2]: Undo-redo - как бы вы организовали API?
От: Sinix  
Дата: 14.01.11 01:31
Оценка:
Здравствуйте, Буравчик, Вы писали:

UPD:
S> 1,2 — на одно состояние меньше.
Тут неправ. Чтобы вернуться к пустой коллекции, всё равно придётся вводить состояние, всей разницы — его можно явно не вводить:
stateManager.CurrentChangeSet = ChangeSetKey.Initial;
Re[3]: Undo-redo - как бы вы организовали API?
От: maxkar  
Дата: 14.01.11 11:18
Оценка: 24 (1)
Здравствуйте, Sinix, Вы писали:


S>Первый вариант на порядок проще в использовании, но нифига не интуитивно понятен.

S>
S>      StateManager stateManager = new StateManager();
S>      StatefulCollection<int> values = new StatefulCollection<int>(stateManager);

S>      ChangeSetKey changeSet0 = stateManager.NewChangeSet("adding 0"); // AnnounceChanges?
S>      values.Add(0);

S>      ChangeSetKey changeSet1 = stateManager.NewChangeSet("adding 1");
S>      values.Add(1); // values: { 0, 1 }

S>      stateManager.CurrentChangeSet = changeSet0; // values: { 0 }
S>      stateManager.CurrentChangeSet = changeSet1; // values: { 0, 1 }
S>


S>Вот и думай теперь — или интуитивно понятно и неюзабельно, или WTF и необходимость изучать API, чтобы комфортно пользоваться.


В интуитивную обертку, может быть, и можно завернуть. Но сначала нужно понять, что же именно хочется от API. По всем примерам я видел только перемещение по линейному списку undo/redo. Причем во всех примерах после создания списка изменений коллекция не изменялась. Интересует ситуация, когда продолжается редактирование. Если продолжения редактирования (после перехода к любой точке) нет, то оба способа друг от друга отличаются только тем, где определяется операция и называется отрезок по "точке" в левой или правой его границе. Классический способ — правая граница, ваш — левая. Инициализация (общая для всех примеров):

      StateManager stateManager = new StateManager();
      StatefulCollection<int> values = new StatefulCollection<int>(stateManager);

      ChangeSetKey changeSet0 = stateManager.NewChangeSet("adding 0"); // AnnounceChanges?
      values.Add(0);

      ChangeSetKey changeSet1 = stateManager.NewChangeSet("adding 1");
      values.Add(1); // values: { 0, 1 }


Пример 1: продолжение последнего редактирования
      stateManager.CurrentChangeSet = changeSet0; // values: { 0 }
      stateManager.CurrentChangeSet = changeSet1; // values: { 0, 1 }
      valuse.Add(2); // можно так?
      ChangeSetKey changeSet2 = stateManager.newChangeSet("Adding x");
      values.Add(3);
      stateManager.CurrentChangeSet = changeSet1; // values: ???


Пример 2: продолжение редактирования из середины
      stateManager.CurrentChangeSet = changeSet0; // values: { 0 }
      valuse.Add(2); // можно так?
      ChangeSetKey changeSet2 = stateManager.newChangeSet("Adding x");
      values.Add(3);
      stateManager.CurrentChangeSet = changeSet0; // values: ???
      stateManager.CurrentChangeSet = changeSet1; // а здесь какая-то ошибка должна быть?


Теперь по исходному вопросу. Мне кажется, стоит разделять "явные" и "неявные" состояния. Явные состояния — это "активное" получение состояния, stateManager.getCurrentState(), получение чекпоинтов. Неявные состояния — это ваше "анонсирование" изменений. Т.е. состояние начинается до того, как оно завершилось. Можно назвать это неявное состояние "правкой", в смысле "процесс правки". Вполне возможно оперировать одновременно обоими понятиями:

      StateManager stateManager = new StateManager();
      StatefulCollection<int> values = new StatefulCollection<int>(stateManager);
      Edit edit1 = stateManager.beginEdit("adding 0"); // Announce edit
      values.Add(0);

      Edit edit2 = stateManager.beginEdit("adding 1, 2"); // Announce edit
      values.Add(1);
      Checkpoint checkpoint2_1 = stateManager.getState("state {0, 1}");
      values.Add(2);

      stateManager.ResumeEdit(edit1); // values: {0}, edit: edit1
      stateManager.ResumeEdit(edit2); // values: {0, 1, 2} edit: edit2
      values.Add(3);
      Edit edit3 = stateManager.beginEdit("Last edit");
      values.Add(4);
      stateManager.ResumeEdit(edit2); //values : {0, 1, 2, 3}, Edit имеет "автоматическую" границу
      values.Add(6);
      stateManager.ResumeEdit(edit3); //Ошибка - нельзя делать redo, хвост операции потерян
      Edit curEdit = stateManager.continueFromCheckpoint(checkpoint2_1); // curEdit == edit2, values : {0, 1}
      stateManager.ResumeEdit(edit2); // Неочевидный момент, values = {0, 1, 2, 3}
      Edit curEdit1 = stateManager.continueFromCheckpoint(checkpoint2_1); // curEdit1 == edit2, values : {0, 1}
      values.Add(7);
      stateManager.ResumeEdit(edit1); // values: {0}, edit: edit1
      stateManager.ResumeEdit(edit2); // values: {0, 1, 7} edit: edit2
      stateManager.continueFromCheckpoint(checkpoint2_1); // edit2, values : {0, 1}      
      Edit dummyEdit = stateManager.beginEdit("Dummy edit");
      values.Add(8);
      stateManager.continueFromCheckpoint(checkpoint2_1); // edit2, values : {0, 1}      
      stateManager.ResumeEdit(edit2); // values: {0, 1} edit: edit2
      stateManager.ResumeEdit(dummyEdit); // values: {0, 1, 8} edit: dummyEdit


Edit можно еще назвать EditOperation/EditTransaction/EditProcess, что-то не подберу хорошее имя.

Описание для понимания примерно следующее. Есть timeline всех изменений коллекции. В этом timeline расставлены точки начала правок (Edit). Границы правки — от ее начала до начала следующей правки или до конца timeline. При изменении с какого-то места очевидно, что состояние, идентифицированное "правкой" может измениться, так как изменился timeline. В то же время на timeline вручную могут быть расставлены метки (Checkpoint), они привязаны к той правке, которая была активна на момент их создания. Т.е. если мы взяли checkpoint, начали правку и ничего не изменив создали еще один checkpoint, то два этих checkpoint'а будут в разных правках. Навигация по timeline возможна как по правкам, так и по checkpoint'ам. При перемещении по имени правки переносит нас в точку "конца" правки (мы продолжаем ту правку). Перенос же в checkpoint переносит нас во вполне конкретное место конкретной правки. Ровно туда, где метка поставлена. И ровно в ту правку, в которой поставлена метка. Любое изменение в промежуточной точке делает хвост невалидным и, очевидно, изменяет текущую правку (либо добавляет элемент в конец, либо затирает ховст правки с середины). Если нарисовать картинку с отметками "начало правки" и "checkpoint", вроде бы просто и достаточно интуитивно получается.
Re[4]: Undo-redo - как бы вы организовали API?
От: Sinix  
Дата: 14.01.11 11:37
Оценка:
Здравствуйте, maxkar, Вы писали:

M>По всем примерам я видел только перемещение по линейному списку undo/redo. Причем во всех примерах после создания списка изменений коллекция не изменялась.

Да, при любом изменении redo-состояния убираются. Если мы хотим, чтобы undo-redo всегда оставлял после себя согласованные данные и не кидал никаких исключений, по-другому не выкрутиться.

M>Пример 1: продолжение последнего редактирования

Для прототипов использую подход с анонсированием, поэтгому:
      stateManager.CurrentChangeSet = changeSet0; // values: { 0 }
      stateManager.CurrentChangeSet = changeSet1; // values: { 0, 1 }
      valuse.Add(2); // можно
      ChangeSetKey changeSet2 = stateManager.newChangeSet("Adding x");
      values.Add(3);
      stateManager.CurrentChangeSet = changeSet1; // values: {0, 1, 2}


Пример 2: продолжение редактирования из середины
      stateManager.CurrentChangeSet = changeSet0; // values: { 0 }
      valuse.Add(2); // можно
      ChangeSetKey changeSet2 = stateManager.newChangeSet("Adding x");
      values.Add(3);
      stateManager.CurrentChangeSet = changeSet0; // values: { 0 }
      stateManager.CurrentChangeSet = changeSet1; // InvalidOperationException
M>





M>Теперь по исходному вопросу. Мне кажется, стоит разделять "явные" и "неявные" состояния.

M>Описание для понимания примерно следующее.

Спасибо, подумаю!
Re: Undo-redo - как бы вы организовали API?
От: WolfHound  
Дата: 15.01.11 01:10
Оценка: 8 (1)
Здравствуйте, Sinix, Вы писали:

S>Представим, что нас есть коллекция, имеющая возможность отменять/повторять изменения.

Все твои проблемы от того что ты делаешь все имнперативно.
Если использовать аппликативный подход то эта задача решается на столько тривиально что даже разговаривать не о чем.
Просто в точках Undo/Redo сохраняешь коллекцию и все.

Тебе нужно сделать свою коллекцию не изменяемой. И при добавлении/изменении элементов порождать новую коллекцию.
При правильной структуре данных создание новой коллекции будет от O(1) до O(Log(N)) (и по вычислениям и по памяти) в зависимости от того что за коллекция.
Если скажешь что за коллекция я тебе даже скажу какая структура данных для нее лучше подходит.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[2]: Undo-redo - как бы вы организовали API?
От: Sinix  
Дата: 15.01.11 04:25
Оценка:
Здравствуйте, WolfHound, Вы писали:

S>>Представим, что нас есть коллекция, имеющая возможность отменять/повторять изменения.

WH>Все твои проблемы от того что ты делаешь все имнперативно.
Так язык, и фреймворк — насквозь императивные. И если я начну из себя строить ФП-эльфа в башне из слоновой кости, то пользоваться этим творением смогут только такие же обитатели волшебной страны

WH>Просто в точках Undo/Redo сохраняешь коллекцию и все.

WH>При правильной структуре данных создание новой коллекции будет от O(1) до O(Log(N)) (и по вычислениям и по памяти) в зависимости от того что за коллекция.
Не, будет задница в сравнении с текущим O(1). Типичное количество элементов ~10000, сотни изменений в каждой операции, биндинг коллекций с UI — тут лучше не рыпаться и использовать то, что даёт хоть какие-то шансы на успех всей авантюры

WH>Если скажешь что за коллекция я тебе даже скажу какая структура данных для нее лучше подходит.

Так неизвестно заранее. List, Dictionary, стек, или хеш-сет. Или вообще StatefulValue — зависит от конкретного сценария использования.

В принципе, никто не мешает позднее реализовать immutable-коллекции. Вопрос (пока) в том, как рулить изменением состояния: сдизайнить state manager так, чтобы было удобно всем участникам процесса
Re[3]: Undo-redo - как бы вы организовали API?
От: WolfHound  
Дата: 15.01.11 15:46
Оценка:
Здравствуйте, Sinix, Вы писали:

S>Так язык, и фреймворк — насквозь императивные. И если я начну из себя строить ФП-эльфа в башне из слоновой кости, то пользоваться этим творением смогут только такие же обитатели волшебной страны

И ты своих коллег обезьянками то считаешь?
А может все не так плохо?
Со строками то они разобрались. Или нет?

S>Не, будет задница в сравнении с текущим O(1). Типичное количество элементов ~10000, сотни изменений в каждой операции, биндинг коллекций с UI — тут лучше не рыпаться и использовать то, что даёт хоть какие-то шансы на успех всей авантюры

Ни разу не вижу ни одной проблемы.
Тем более что дело происходит в UI.

S>Так неизвестно заранее. List, Dictionary, стек, или хеш-сет. Или вообще StatefulValue — зависит от конкретного сценария использования.

Тем более нужно использовать не изменяемые коллекции.

S>В принципе, никто не мешает позднее реализовать immutable-коллекции. Вопрос (пока) в том, как рулить изменением состояния: сдизайнить state manager так, чтобы было удобно всем участникам процесса

А зачем вообще нужен state manager если коллекции не изменяемые?
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[4]: Undo-redo - как бы вы организовали API?
От: Sinix  
Дата: 15.01.11 16:13
Оценка:
Здравствуйте, WolfHound, Вы писали:

S>>Так язык, и фреймворк — насквозь императивные. И если я начну из себя строить ФП-эльфа в башне из слоновой кости, то пользоваться этим творением смогут только такие же обитатели волшебной страны

WH>И ты своих коллег обезьянками то считаешь?
Нет. Если используете какую-то платформу и пишете публичное API — будьте любезны следовать общепринятым patterns & practices, или смиритесь с тем, что вас справедливо пошлют. Потому что время, которые разработчики потратят на изучение очередного тру-подхода, и на скрещивание тру-кода с самой платформой ничем не окупится.

WH>Ни разу не вижу ни одной проблемы.

WH>Тем более что дело происходит в UI.
Для начала — забиндьте коллекцию к нескольким контролам. Например, к двум гридам. Вам придётся оборачивать immutable-коллекцию в обёртку, эмулирующую обычные коллекции. Зачем так извращаться на ровном месте —

S>>Так неизвестно заранее. List, Dictionary, стек, или хеш-сет. Или вообще StatefulValue — зависит от конкретного сценария использования.

WH>Тем более нужно использовать не изменяемые коллекции.
Блин! Мне вообще неизвестно, какие коллекции захотят в будущем пользователи моего API и я не собираюсь вводить ограничения только ради абстрактной чистоты идеи. Речь вообще не об этом пока.

S>>В принципе, никто не мешает позднее реализовать immutable-коллекции. Вопрос (пока) в том, как рулить изменением состояния: сдизайнить state manager так, чтобы было удобно всем участникам процесса

WH>А зачем вообще нужен state manager если коллекции не изменяемые?
1. Коллекций может быть с пару десятков. Ссылаться на них будут в нескольких местах.
2. Пользователи хотят централизованно управлять состоянием данных.
Продолжать?
Re[5]: Undo-redo - как бы вы организовали API?
От: WolfHound  
Дата: 15.01.11 17:10
Оценка:
Здравствуйте, Sinix, Вы писали:

S>Нет. Если используете какую-то платформу и пишете публичное API — будьте любезны следовать общепринятым patterns & practices, или смиритесь с тем, что вас справедливо пошлют. Потому что время, которые разработчики потратят на изучение очередного тру-подхода, и на скрещивание тру-кода с самой платформой ничем не окупится.

Оно окупится значительным упрощением разработки и сильно меньшем колличеством багов.
Это проверено на практике не один раз.
И чем сложнее структура данных тем проще и надежнее аппликативный подход.
Императивный нужен только если нужно добтся производительности любой ценой.
10К элементов в ГУИ явно не тот случай.

S>Для начала — забиндьте коллекцию к нескольким контролам. Например, к двум гридам. Вам придётся оборачивать immutable-коллекцию в обёртку, эмулирующую обычные коллекции. Зачем так извращаться на ровном месте —

Извращение на ровном месте это этот твой волшебный стейт манагер который умеет все сразу.

S>Блин! Мне вообще неизвестно, какие коллекции захотят в будущем пользователи моего API и я не собираюсь вводить ограничения только ради абстрактной чистоты идеи. Речь вообще не об этом пока.

Аппликативной можно сделать ЛЮБУЮ коллекцию.

S>1. Коллекций может быть с пару десятков. Ссылаться на них будут в нескольких местах.

S>2. Пользователи хотят централизованно управлять состоянием данных.
S>Продолжать?
Я думаю тебе стоит начать с того что ты пытаешься сделать.
По тому что ты начал с Undo/Redo но сейчас у тебя получается какойто мегафреймворк не ясного назначения.
... << RSDN@Home 1.2.0 alpha 4 rev. 1472>>
Пусть это будет просто:
просто, как только можно,
но не проще.
(C) А. Эйнштейн
Re[6]: Undo-redo - как бы вы организовали API?
От: Sinix  
Дата: 15.01.11 17:48
Оценка: 1 (1)
Здравствуйте, WolfHound, Вы писали:

S>>Нет. Если используете какую-то платформу и пишете публичное API — будьте любезны следовать общепринятым patterns & practices, или смиритесь с тем, что вас справедливо пошлют.

WH>Оно окупится значительным упрощением разработки и сильно меньшем колличеством багов.
WH>Это проверено на практике не один раз.
Для публичного API — нет. Это проверено на практике не один раз. Например, я сейчас подумываю над отказом от собственного легковесного workflow-фреймворка в пользу всем привычных using-scope. Потому что фичи из него — мегаудобны, а вот необходимость писать логику, подстраиваясь под фреймворк — наоборот.

Поймите, как автор публичного фреймворка я не имею никакого морального права навязывать клиентам что-то кроме общепринятых правил. Потому следующий аффтор помешается на AOP и будет использовать аспекты вместо наследования, другой — потребует eval для генерации паролей, а третий — зафанатеет от IOC и протащит за собой какой-нить unity древней версии. Для мелкого кода, с которым будет работать только автор, можно понтоваться как угодно. Для всего остального — будьте любезны шагать в ногу. Игра в "свой лунапарк с го и гейшами" ни к чему хорошему не приводит. Как любимый пример — тонна дистров линуха, каждый — со своей единственно верной идеологией, своими предестями и косяками. И все гордо топчутся на своих закономерных 1% рынка

WH>10К элементов в ГУИ явно не тот случай.

Stateful-коллекции используются не только в UI

S>>Для начала — забиндьте коллекцию к нескольким контролам. Например, к двум гридам. Вам придётся оборачивать immutable-коллекцию в обёртку, эмулирующую обычные коллекции. Зачем так извращаться на ровном месте —


WH>Извращение на ровном месте это этот твой волшебный стейт манагер который умеет все сразу.


Давайте не будем уходить от темы — как бы вы организовали биндинг коллекции к нескольким контролам?

StateManager не несёт в себе никакой логики, кроме уведомления подписчиков о изменении текущего состояния. Если это изврат — что такое System.Transactions/DTC, использующие ровно тот же подход?

WH>По тому что ты начал с Undo/Redo но сейчас у тебя получается какойто мегафреймворк не ясного назначения.

А давайте не будем додумывать друг за друга? Топик заведён для обсуждения совершенно конкретного вопроса; я не собирался холиварить и пиарить что-либо, поэтому ограничился минимумом деталей. Если хочется продолжить — заведите отдельную тему в КСВ.
Re: Undo-redo - как бы вы организовали API?
От: VladD2 Российская Империя www.nemerle.org
Дата: 11.03.11 13:35
Оценка:
Здравствуйте, Sinix, Вы писали:

S>Представим, что нас есть коллекция, имеющая возможность отменять/повторять изменения...

S>Если есть идеи, как организовать это дело покрасивше/попонятней — вэлкам!

Есть два (разумных) способа управлять изменениями в коллекциях:
1. Использовать неизменяемые структуры данных. Этот способ ты почему-то отмел, но он зачастую является самым простым и надежным.
2. Описание изменений как неизменяемых команд и хранение двух списков анду и реду.

Какой выбрать зависит от задачи. Но по сути эти способы эквивалентны по возможностям.

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

Второй подход — это классический паттерн ООП — команда. Я применял его в редакторе кода.
Есть логика намерений и логика обстоятельств, последняя всегда сильнее.
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.