Padrão de Design para Undo Engine

117

Estou escrevendo uma ferramenta de modelagem estrutural para uma aplicação de engenharia civil. Eu tenho uma classe de modelo enorme que representa todo o edifício, que inclui coleções de nós, elementos de linha, cargas, etc. que também são classes personalizadas.

Já codifiquei um mecanismo de desfazer que salva uma cópia profunda após cada modificação no modelo. Agora comecei a pensar se poderia ter codificado de forma diferente. Em vez de salvar as cópias profundas, talvez eu pudesse salvar uma lista de cada ação do modificador com um modificador reverso correspondente. Para que eu pudesse aplicar os modificadores reversos ao modelo atual para desfazer ou os modificadores para refazer.

Posso imaginar como você executaria comandos simples que alteram as propriedades dos objetos, etc. Mas e os comandos complexos? Como inserir novos objetos de nó no modelo e adicionar alguns objetos de linha que mantêm referências aos novos nós.

Como alguém faria para implementar isso?

Ozgur Ozcitak
fonte
Se eu adicionar o comentário "Desfazer Algorthim", isso fará com que eu possa pesquisar "Desfazer Algoritmo" e encontrar isso? Isso é o que eu procurei e encontrei algo fechado como uma duplicata.
Peter Turner
feno, eu também quero desenvolver desfazer / refazer no aplicativo que estamos desenvolvendo. Nós usamos a estrutura QT4 e precisamos ter muitas ações complexas de desfazer / refazer ... Eu estava me perguntando, você conseguiu usar o Padrão de Comando?
Ashika Umanga Umagiliya
2
@umanga: Funcionou, mas não foi fácil. A parte mais difícil foi acompanhar as referências. Por exemplo, quando um objeto Quadro é excluído, seus objetos filho: Nós, Cargas atuando nele e muitas outras atribuições de usuário precisam ser mantidas para serem reinseridas quando desfeitas. Mas alguns desses objetos filho foram compartilhados com outros objetos, e a lógica de desfazer / refazer tornou-se bastante complexa. Se o modelo não fosse tão grande, eu manteria a abordagem memento; é muito mais fácil de implementar.
Ozgur Ozcitak,
este é um problema divertido de se trabalhar, pense em como os repositórios de código-fonte fazem isso, como o svn (eles mantêm as diferenças entre os commits).
Alex

Respostas:

88

A maioria dos exemplos que vi usa uma variante do Padrão de Comando para isso. Cada ação do usuário que pode ser desfeita obtém sua própria instância de comando com todas as informações para executar a ação e revertê-la. Você pode então manter uma lista de todos os comandos que foram executados e pode revertê-los um por um.

Mendelt
fonte
4
É basicamente assim que funciona o mecanismo de desfazer do Cocoa, NSUndoManager.
amrox
33

Acho que memento e command não são práticos quando você está lidando com um modelo do tamanho e escopo que o OP implica. Eles funcionariam, mas seria muito trabalhoso mantê-los e ampliá-los.

Para esse tipo de problema, acho que você precisa construir um suporte para seu modelo de dados para dar suporte a pontos de verificação diferenciais para cada objeto envolvido no modelo. Já fiz isso uma vez e funcionou muito bem. A maior coisa que você precisa fazer é evitar o uso direto de ponteiros ou referências no modelo.

Cada referência a outro objeto usa algum identificador (como um inteiro). Sempre que o objeto é necessário, você consulta a definição atual do objeto em uma tabela. A tabela contém uma lista vinculada para cada objeto que contém todas as versões anteriores, junto com informações sobre para qual ponto de verificação eles estavam ativos.

Implementar desfazer / refazer é simples: execute sua ação e estabeleça um novo ponto de verificação; reverter todas as versões do objeto para o ponto de verificação anterior.

Requer alguma disciplina no código, mas tem muitas vantagens: você não precisa de cópias profundas, pois está fazendo armazenamento diferencial do estado do modelo; você pode medir a quantidade de memória que deseja usar ( muito importante para coisas como modelos CAD) por número de redos ou memória usada; muito escalonável e de baixa manutenção para as funções que operam no modelo, uma vez que não precisam fazer nada para implementar desfazer / refazer.

Jeff Kotula
fonte
1
Se você usar um banco de dados (por exemplo, sqlite) como formato de arquivo, isso pode ser quase automático
Martin Beckett,
4
Se você aumentar isso rastreando dependências introduzidas por mudanças no modelo, então você poderia potencialmente ter um sistema de árvore de desfazer (ou seja, se eu mudar a largura de uma viga, então vá trabalhar em um componente separado, posso voltar e desfazer a viga muda sem perder as outras coisas). A interface do usuário para isso pode ser um pouco pesada, mas seria muito mais poderosa do que um desfazer linear tradicional.
Sumudu Fernando
Você pode explicar mais essa ideia de id e ponteiros? Certamente um endereço de ponteiro / memória funciona tão bem quanto id?
paulm
@paulm: essencialmente, os dados reais são indexados por (id, versão). Ponteiros referem-se a uma versão particular de um objeto, mas você está procurando se referir ao estado atual de um objeto, seja ele qual for, então você deseja endereçá-lo por id, não por (id, versão). Você poderia reestruturá-lo para armazenar um ponteiro para a tabela (versão => dados) e apenas escolher o mais recente a cada vez, mas isso tende a prejudicar a localidade quando você está persistindo dados, confunde um pouco as preocupações e torna mais difícil fazer alguns tipos de consultas comuns, portanto, não é a maneira como seria feito normalmente.
Chris Morgan
17

Se você está falando GoF, o padrão Memento aborda especificamente desfazer.

Andy Whitfield
fonte
7
Na verdade, não, isso aborda sua abordagem inicial. Ele está pedindo uma abordagem alternativa. O inicial armazenando o estado completo para cada etapa, enquanto o último armazenando apenas os "diffs".
Andrei Rînea
15

Como outros afirmaram, o padrão de comando é um método muito poderoso de implementação de Desfazer / Refazer. Mas há uma vantagem importante que eu gostaria de mencionar no padrão de comando.

Ao implementar desfazer / refazer usando o padrão de comando, você pode evitar grandes quantidades de código duplicado abstraindo (até certo ponto) as operações realizadas nos dados e utilizando essas operações no sistema desfazer / refazer. Por exemplo, em um editor de texto cortar e colar são comandos complementares (além do gerenciamento da área de transferência). Em outras palavras, a operação de desfazer para um corte é colar e a operação de desfazer para uma pasta é cortar. Isso se aplica a operações muito mais simples, como digitar e excluir texto.

A chave aqui é que você pode usar seu sistema desfazer / refazer como o sistema de comando primário para seu editor. Em vez de escrever o sistema como "criar objeto desfazer, modificar o documento", você pode "criar objeto desfazer, executar a operação refazer no objeto desfazer para modificar o documento".

Agora, é verdade que muitas pessoas estão pensando consigo mesmas "Bem, duh, não faz parte do ponto do padrão de comando?" Sim, mas já vi muitos sistemas de comando com dois conjuntos de comandos, um para operações imediatas e outro para desfazer / refazer. Não estou dizendo que não haverá comandos específicos para operações imediatas e desfazer / refazer, mas reduzir a duplicação tornará o código mais sustentável.

Torlack
fonte
1
Nunca pensei pasteem cut^ -1.
Lenar Hoyt
8

Você pode querer consultar o código do Paint.NET para desfazer - eles têm um sistema de desfazer muito bom. Provavelmente é um pouco mais simples do que você precisa, mas pode lhe dar algumas idéias e orientações.

-Adão

Adam Davis
fonte
4
Na verdade, o código do Paint.NET não está mais disponível, mas você pode obter o código
Igor Brejc
7

Este pode ser o caso em que o CSLA é aplicável. Ele foi projetado para fornecer suporte a desfazer complexos para objetos em aplicativos Windows Forms.

Eric Z Beard
fonte
6

Implementei sistemas de desfazer complexos com sucesso usando o padrão Memento - muito fácil e tem a vantagem de fornecer naturalmente um framework Redo também. Um benefício mais sutil é que as ações agregadas também podem estar contidas em um único Desfazer.

Em suma, você tem duas pilhas de objetos memento. Um para Desfazer, o outro para Refazer. Cada operação cria um novo memento, que idealmente serão algumas chamadas para alterar o estado do seu modelo, documento (ou qualquer outro). Isso é adicionado à pilha de desfazer. Quando você faz uma operação desfazer, além de executar a ação Desfazer no objeto Memento para alterar o modelo novamente, você também retira o objeto da pilha Desfazer e empurra-o direto para a pilha Refazer.

Como o método para alterar o estado do seu documento é implementado depende completamente da sua implementação. Se você puder simplesmente fazer uma chamada de API (por exemplo, ChangeColour (r, g, b)), faça uma consulta antes de obter e salvar o estado correspondente. Mas o padrão também suportará cópias profundas, instantâneos de memória, criação de arquivo temporário, etc. - tudo depende de você, pois é simplesmente uma implementação de método virtual.

Para fazer ações agregadas (por exemplo, o usuário Shift-Seleciona uma carga de objetos para fazer uma operação, como excluir, renomear, alterar atributo), seu código cria uma nova pilha de Desfazer como um único memento e passa isso para a operação real para adicione as operações individuais a. Portanto, seus métodos de ação não precisam (a) ter uma pilha global para se preocupar e (b) podem ser codificados da mesma forma, sejam executados isoladamente ou como parte de uma operação agregada.

Muitos sistemas de undo estão apenas na memória, mas você pode persistir na pilha de undo se desejar, eu acho.

Greg Whitfield
fonte
5

Acabei de ler sobre o padrão de comando em meu livro de desenvolvimento ágil - talvez isso tenha potencial?

Você pode fazer com que cada comando implemente a interface de comando (que tem um método Execute ()). Se quiser desfazer, você pode adicionar um método Undo.

mais informações aqui

Dave Arkell
fonte
4

Estou com Mendelt Siebenga sobre o fato de que você deve usar o Padrão de Comando. O padrão que você usou foi o Memento Pattern, que pode e irá se tornar um grande desperdício com o tempo.

Como você está trabalhando em um aplicativo que usa muita memória, deve ser capaz de especificar quanta memória o mecanismo de desfazer pode ocupar, quantos níveis de desfazer são salvos ou algum armazenamento no qual eles serão persistidos. Se você não fizer isso, logo encontrará erros resultantes da falta de memória da máquina.

Aconselho você a verificar se existe um framework que já criou um modelo para undos na linguagem / framework de programação de sua escolha. É bom inventar coisas novas, mas é melhor pegar algo já escrito, depurado e testado em cenários reais. Ajudaria se você adicionasse o que está escrevendo, para que as pessoas possam recomendar estruturas que conheçam.

Omer van Kloeten
fonte
3

Projeto Codeplex :

É uma estrutura simples para adicionar a funcionalidade Desfazer / Refazer aos seus aplicativos, com base no padrão de design clássico de Comando. Ele oferece suporte a ações de fusão, transações aninhadas, execução atrasada (execução no commit de transação de nível superior) e histórico de desfazer não linear possível (onde você pode escolher várias ações para refazer).

sg7
fonte
2

A maioria dos exemplos que li fazem isso usando o padrão de comando ou memento. Mas você também pode fazer isso sem padrões de projeto com um simples desque-estrutura .

Patrik Svensson
fonte
O que você colocaria no deque?
No meu caso, coloquei o estado atual das operações para as quais eu queria desfazer / refazer a funcionalidade. Ao ter dois deques (desfazer / refazer), eu faço o desfazer na fila de desfazer (pop o primeiro item) e o insiro no dequeue de refazer. Se o número de itens no desenfileiramento exceder o tamanho preferido, eu coloco um item da cauda.
Patrik Svensson
2
O que você descreve na verdade é um padrão de design :). O problema com essa abordagem é quando seu estado ocupa muita memória - manter várias dezenas de versões de estado torna-se impraticável ou mesmo impossível.
Igor Brejc
Ou você pode armazenar um par de fechamento representando a operação normal e desfazer.
Xwtek
2

Uma maneira inteligente de lidar com o desfazer, o que tornaria seu software também adequado para colaboração de vários usuários, é implementar uma transformação operacional da estrutura de dados.

Este conceito não é muito popular, mas é bem definido e útil. Se a definição parece muito abstrata para você, este projeto é um exemplo de sucesso de como uma transformação operacional para objetos JSON é definida e implementada em Javascript

danza
fonte
1

Reutilizamos o carregamento de arquivo e salvamos o código de serialização para “objetos” para uma forma conveniente de salvar e restaurar todo o estado de um objeto. Colocamos esses objetos serializados na pilha de desfazer - junto com algumas informações sobre qual operação foi executada e dicas sobre como desfazer essa operação se não houver informações suficientes coletadas dos dados serializados. Desfazer e Refazer muitas vezes é apenas substituir um objeto por outro (em teoria).

Houve muitos MUITOS bugs devido a ponteiros (C ++) para objetos que nunca foram corrigidos conforme você executa algumas sequências de desfazer e refazer estranhas (esses locais não atualizados para “identificadores” mais seguros para desfazer). Bugs nesta área freqüentemente ... ummm ... interessante.

Algumas operações podem ser casos especiais de uso de velocidade / recurso - como dimensionar coisas, mover coisas.

A seleção múltipla também oferece algumas complicações interessantes. Felizmente, já tínhamos um conceito de agrupamento no código. O comentário de Kristopher Johnson sobre os subitens está muito próximo do que fazemos.

Aardvark
fonte
Isso parece cada vez mais impraticável conforme o tamanho do seu modelo aumenta.
Warren P
De que maneira? Esta abordagem continua funcionando sem mudanças conforme novas "coisas" são adicionadas a cada objeto. O desempenho pode ser um problema à medida que a forma serializada dos objetos aumenta de tamanho - mas isso não tem sido um grande problema. O sistema está em desenvolvimento contínuo há mais de 20 anos e está sendo usado por milhares de usuários.
Aardvark
1

Eu tive que fazer isso ao escrever um solucionador para um jogo de quebra-cabeça de salto de pino. Eu tornei cada movimento um objeto de comando que continha informações suficientes para que pudesse ser feito ou desfeito. No meu caso, isso foi tão simples quanto armazenar a posição inicial e a direção de cada movimento. Em seguida, armazenei todos esses objetos em uma pilha para que o programa pudesse desfazer facilmente quantos movimentos fosse necessário enquanto retrocedia.

Bill the Lizard
fonte
1

Você pode tentar a implementação pronta do padrão Desfazer / Refazer no PostSharp. https://www.postsharp.net/model/undo-redo

Ele permite que você adicione a funcionalidade desfazer / refazer ao seu aplicativo sem implementar o padrão por conta própria. Ele usa o padrão Recordable para rastrear as mudanças em seu modelo e funciona com o padrão INotifyPropertyChanged, que também é implementado no PostSharp.

Você recebe controles de IU e pode decidir qual será o nome e a granularidade de cada operação.

Antonín Procházka
fonte
0

Certa vez, trabalhei em um aplicativo em que todas as alterações feitas por um comando no modelo do aplicativo (ou seja, CDocument ... estávamos usando o MFC) eram persistidas no final do comando, atualizando campos em um banco de dados interno mantido dentro do modelo. Portanto, não tivemos que escrever código desfazer / refazer separado para cada ação. A pilha de desfazer simplesmente lembrava as chaves primárias, nomes de campo e valores antigos toda vez que um registro era alterado (no final de cada comando).

Agnel Kurian
fonte
0

A primeira seção de Design Patterns (GoF, 1994) tem um caso de uso para implementar desfazer / refazer como um padrão de design.

Peter Turner
fonte
0

Você pode tornar sua ideia inicial performante.

Use estruturas de dados persistentes e mantenha uma lista de referências ao estado antigo . (Mas isso só funciona realmente se as operações de todos os dados em sua classe de estado forem imutáveis ​​e todas as operações nele retornarem uma nova versão --- mas a nova versão não precisa ser uma cópia profunda, apenas substitua a cópia das partes alteradas -on-write '.)

Matthias
fonte
0

Eu descobri que o padrão de comando é muito útil aqui. Em vez de implementar vários comandos reversos, estou usando rollback com execução atrasada em uma segunda instância da minha API.

Esta abordagem parece razoável se você deseja baixo esforço de implementação e fácil manutenção (e pode pagar a memória extra para a 2ª instância).

Veja aqui um exemplo: https://github.com/thilo20/Undo/

Thilo
fonte
-1

Não sei se isso vai ser útil para você, mas quando tive que fazer algo semelhante em um dos meus projetos, acabei baixando UndoEngine em http://www.undomadeeasy.com - um mecanismo maravilhoso e eu realmente não me importava muito com o que estava sob o capô - simplesmente funcionava.

NativeBreed
fonte
Por favor, poste seus comentários como resposta apenas se você estiver confiante para fornecer soluções! Caso contrário, prefira postar como comentário abaixo da pergunta! (se não permitir agora! por favor, espere até obter boa reputação)
InfantPro'Aravind '11 de
-1

Na minha opinião, o UNDO / REDO poderia ser implementado de 2 maneiras amplamente. 1. Nível de comando (denominado nível de comando Desfazer / Refazer) 2. Nível de documento (denominado Desfazer / Refazer global)

Nível de comando: como muitas respostas apontam, isso é alcançado de forma eficiente usando o padrão Memento. Se o comando também suportar o registro da ação no diário, um refazer será facilmente suportado.

Limitação: Uma vez que o escopo do comando está fora, desfazer / refazer é impossível, o que leva ao nível de documento (global) desfazer / refazer

Acho que seu caso se encaixaria no desfazer / refazer global, pois é adequado para um modelo que envolve muito espaço de memória. Além disso, isso também é adequado para desfazer / refazer seletivamente. Existem dois tipos primitivos

  1. Desfazer / refazer toda a memória
  2. Nível de objeto Desfazer Refazer

Em "Desfazer / Refazer toda a memória", toda a memória é tratada como um dado conectado (como uma árvore, uma lista ou um gráfico) e a memória é gerenciada pelo aplicativo em vez do sistema operacional. Portanto, operadores new e delete se em C ++ estiverem sobrecarregados para conter estruturas mais específicas para implementar efetivamente operações como a. Se algum nó for modificado, b. mantendo e apagando dados, etc., A maneira como funciona é basicamente copiar toda a memória (assumindo que a alocação de memória já está otimizada e gerenciada pelo aplicativo usando algoritmos avançados) e armazená-la em uma pilha. Se a cópia da memória for solicitada, a estrutura da árvore é copiada com base na necessidade de uma cópia superficial ou profunda. Uma cópia profunda é feita apenas para a variável modificada. Uma vez que cada variável é alocada usando alocação personalizada, o aplicativo tem a palavra final quando excluí-lo, se necessário. As coisas se tornam muito interessantes se tivermos que particionar o Desfazer / Refazer quando acontecer que precisamos desfazer / Refazer de maneira programática e seletiva um conjunto de operações. Neste caso, apenas essas novas variáveis, ou variáveis ​​excluídas ou variáveis ​​modificadas recebem um sinalizador para que Desfazer / Refazer apenas desfaça / refaça aquelas coisas da memória se tornam ainda mais interessantes se precisarmos fazer um Desfazer / Refazer parcial dentro de um objeto. Quando for esse o caso, uma ideia mais recente de "Padrão de visitante" é usada. É chamado de "Desfazer / refazer no nível do objeto" ou variáveis ​​excluídas ou modificadas recebem um sinalizador para que Desfazer / Refazer apenas desfaça / refaça as coisas da memória. As coisas se tornam ainda mais interessantes se precisarmos fazer um Desfazer / Refazer parcial dentro de um objeto. Quando for esse o caso, uma ideia mais recente de "Padrão de visitante" é usada. É chamado de "Desfazer / refazer no nível do objeto" ou variáveis ​​excluídas ou modificadas recebem um sinalizador para que Desfazer / Refazer apenas desfaça / refaça as coisas da memória. As coisas se tornam ainda mais interessantes se precisarmos fazer um Desfazer / Refazer parcial dentro de um objeto. Quando for esse o caso, uma ideia mais recente de "Padrão de visitante" é usada. É chamado de "Desfazer / refazer no nível do objeto"

  1. Nível de objeto Desfazer / Refazer: Quando a notificação para desfazer / refazer é chamada, cada objeto implementa uma operação de streaming em que o streamer obtém do objeto os dados antigos / novos que estão programados. Os dados que não podem ser alterados são mantidos inalterados. Cada objeto recebe um streamer como argumento e dentro da chamada UNDo / Redo, ele faz o stream / unstreams dos dados do objeto.

Ambos 1 e 2 podem ter métodos como 1. BeforeUndo () 2. AfterUndo () 3. BeforeRedo () 4. AfterRedo (). Esses métodos devem ser publicados no comando Undo / redo básico (não no comando contextual) para que todos os objetos implementem esses métodos também para obter uma ação específica.

Uma boa estratégia é criar um híbrido de 1 e 2. A beleza é que esses métodos (1 e 2) usam padrões de comando

Parthasarathy SRINIVASAN
fonte