Pola Desain untuk Mesin Undo

117

Saya sedang menulis alat pemodelan struktural untuk aplikasi teknik sipil. Saya memiliki satu kelas model besar yang mewakili seluruh bangunan, yang mencakup kumpulan node, elemen garis, beban, dll. Yang juga merupakan kelas khusus.

Saya telah membuat kode mesin undo yang menyimpan salinan dalam setelah setiap modifikasi model. Sekarang saya mulai berpikir apakah saya bisa membuat kode berbeda. Alih-alih menyimpan deep-copy, saya mungkin bisa menyimpan daftar setiap tindakan pengubah dengan pengubah terbalik yang sesuai. Sehingga saya bisa menerapkan pengubah terbalik ke model saat ini untuk dibatalkan, atau pengubah untuk mengulang.

Saya bisa membayangkan bagaimana Anda akan menjalankan perintah sederhana yang mengubah properti objek, dll. Tapi bagaimana dengan perintah yang rumit? Seperti memasukkan objek node baru ke model dan menambahkan beberapa objek garis yang menyimpan referensi ke node baru.

Bagaimana cara menerapkannya?

Ozgur Ozcitak
sumber
Jika saya menambahkan komentar "Urungkan Algoritme", apakah itu akan membuatnya jadi saya dapat menelusuri "Batalkan Algoritme" dan menemukan ini? Itulah yang saya cari dan saya menemukan sesuatu yang ditutup sebagai duplikat.
Peter Turner
hay, saya juga ingin mengembangkan undo / redo dalam aplikasi yang sedang kita kembangkan. Kita menggunakan framework QT4 dan perlu banyak tindakan undo / redo yang kompleks .. Saya ingin tahu, apakah Anda berhasil menggunakan Command-Pattern?
Ashika Umanga Umagiliya
2
@umanga: Berhasil tetapi tidak mudah. Bagian tersulit adalah melacak referensi. Misalnya, saat objek Frame dihapus, objek turunannya: Node, Beban yang bekerja padanya, dan banyak tugas pengguna lainnya perlu disimpan untuk dimasukkan kembali saat dibatalkan. Tetapi beberapa dari objek anak ini dibagikan dengan objek lain, dan logika undo / redo menjadi cukup kompleks. Jika modelnya tidak terlalu besar, saya akan tetap menggunakan pendekatan kenang-kenangan; jauh lebih mudah untuk diterapkan.
Ozgur Ozcitak
ini adalah masalah yang menyenangkan untuk dikerjakan, pikirkan tentang bagaimana repo kode sumber melakukannya, seperti svn (mereka menjaga perbedaan antara komit).
Alex

Jawaban:

88

Sebagian besar contoh yang pernah saya lihat menggunakan varian dari Pola Perintah untuk ini. Setiap tindakan pengguna yang tidak dapat dibatalkan mendapatkan contoh perintahnya sendiri dengan semua informasi untuk menjalankan tindakan dan memutarnya kembali. Anda kemudian dapat mempertahankan daftar semua perintah yang telah dijalankan dan Anda dapat mengembalikannya satu per satu.

Mendelt
sumber
4
Ini pada dasarnya adalah cara kerja mesin undo di Cocoa, NSUndoManager.
amrox
33

Saya pikir baik kenang-kenangan dan perintah tidak praktis ketika Anda berurusan dengan model ukuran dan ruang lingkup yang tersirat OP. Mereka akan bekerja, tetapi akan banyak pekerjaan yang harus dipertahankan dan dikembangkan.

Untuk jenis masalah ini, saya pikir Anda perlu membangun dukungan untuk model data Anda untuk mendukung pos pemeriksaan diferensial untuk setiap objek yang terlibat dalam model. Saya telah melakukan ini sekali dan berhasil dengan sangat baik. Hal terbesar yang harus Anda lakukan adalah menghindari penggunaan petunjuk atau referensi secara langsung dalam model.

Setiap referensi ke objek lain menggunakan beberapa pengenal (seperti integer). Setiap kali objek diperlukan, Anda mencari definisi objek saat ini dari tabel. Tabel berisi daftar tertaut untuk setiap objek yang berisi semua versi sebelumnya, bersama dengan informasi mengenai pos pemeriksaan mana mereka aktif.

Menerapkan undo / redo sederhana: Lakukan tindakan Anda dan buat pos pemeriksaan baru; kembalikan semua versi objek ke pos pemeriksaan sebelumnya.

Dibutuhkan beberapa disiplin dalam kode, tetapi memiliki banyak keuntungan: Anda tidak memerlukan salinan dalam karena Anda melakukan penyimpanan diferensial dari status model; Anda dapat mengukur jumlah memori yang ingin Anda gunakan ( sangat penting untuk hal-hal seperti model CAD) menurut jumlah pengulangan atau memori yang digunakan; sangat skalabel dan rendah pemeliharaan untuk fungsi yang beroperasi pada model karena mereka tidak perlu melakukan apa pun untuk mengimplementasikan undo / redo.

Jeff Kotula
sumber
1
Jika Anda menggunakan database (misalnya sqlite) sebagai format file Anda, ini bisa hampir otomatis
Martin Beckett
4
Jika Anda menambah ini dengan melacak dependensi yang diperkenalkan oleh perubahan pada model, maka Anda berpotensi memiliki sistem undo tree (yaitu jika saya mengubah lebar girder, kemudian melakukan beberapa pekerjaan pada komponen terpisah, saya dapat kembali dan membatalkan girder berubah tanpa kehilangan barang lainnya). UI untuk itu mungkin sedikit sulit tetapi akan jauh lebih kuat daripada pengurungan linier tradisional.
Sumudu Fernando
Bisakah Anda menjelaskan ide id vs petunjuk ini lebih lanjut? Tentunya pointer / alamat memori bekerja sebaik id?
paulm
@paulm: pada dasarnya data aktual diindeks oleh (id, versi). Pointer merujuk ke versi tertentu dari suatu objek, tetapi Anda ingin merujuk ke status objek saat ini, apa pun itu, jadi Anda ingin menanganinya dengan id, bukan dengan (id, version). Anda bisa merestrukturnya sehingga Anda menyimpan pointer ke tabel (version => data) dan hanya memilih yang terbaru setiap kali, tetapi itu cenderung merusak lokalitas saat Anda menyimpan data, sedikit membingungkan, dan membuatnya lebih sulit untuk melakukan beberapa jenis kueri umum, jadi ini bukan cara yang biasanya dilakukan.
Chris Morgan
17

Jika Anda berbicara tentang GoF, pola Memento secara khusus membahas pembatalan.

Andy Whitfield
sumber
7
Tidak juga, ini membahas pendekatan awalnya. Dia meminta pendekatan alternatif. Yang awal menyimpan status penuh untuk setiap langkah sedangkan yang terakhir hanya menyimpan "diffs".
Andrei Rînea
15

Seperti yang dinyatakan orang lain, pola perintah adalah metode yang sangat ampuh untuk mengimplementasikan Undo / Redo. Tetapi ada keuntungan penting yang ingin saya sampaikan pada pola perintah.

Saat mengimplementasikan undo / redo menggunakan pola perintah, Anda dapat menghindari kode duplikat dalam jumlah besar dengan mengabstraksi (pada tingkat tertentu) operasi yang dilakukan pada data dan memanfaatkan operasi tersebut dalam sistem undo / redo. Misalnya dalam editor teks potong dan tempel adalah perintah pelengkap (selain dari pengelolaan papan klip). Dengan kata lain, operasi urungkan untuk pemotongan adalah tempel dan operasi urung untuk tempel dipotong. Ini berlaku untuk operasi yang lebih sederhana seperti mengetik dan menghapus teks.

Kuncinya di sini adalah Anda dapat menggunakan sistem undo / redo sebagai sistem perintah utama untuk editor Anda. Alih-alih menulis sistem seperti "buat objek urung, ubah dokumen" Anda bisa "buat objek urung, jalankan operasi pengulangan pada objek urung untuk mengubah dokumen".

Sekarang, harus diakui, banyak orang yang berpikir sendiri, "Ya, bukankah itu bagian dari inti dari pola perintah?" Ya, tetapi saya telah melihat terlalu banyak sistem perintah yang memiliki dua set perintah, satu untuk operasi langsung dan satu lagi untuk undo / redo. Saya tidak mengatakan bahwa tidak akan ada perintah yang khusus untuk operasi langsung dan undo / redo, tetapi mengurangi duplikasi akan membuat kode lebih mudah dipelihara.

Torlack
sumber
1
Saya tidak pernah berpikir pastesebagai cut^ -1.
Lenar Hoyt
8

Anda mungkin ingin merujuk ke kode Paint.NET untuk pembatalan mereka - mereka memiliki sistem pembatalan yang sangat bagus. Ini mungkin sedikit lebih sederhana daripada yang Anda butuhkan, tetapi mungkin memberi Anda beberapa ide dan pedoman.

-Adam

Adam Davis
sumber
4
Sebenarnya, kode Paint.NET tidak lagi tersedia, tetapi Anda bisa mendapatkan yang bercabang code.google.com/p/paint-mono
Igor Brejc
7

Ini mungkin kasus di mana CSLA berlaku. Ini dirancang untuk memberikan dukungan pembatalan yang kompleks ke objek dalam aplikasi Windows Forms.

Eric Z Beard
sumber
6

Saya telah mengimplementasikan sistem pembatalan yang kompleks dengan sukses menggunakan pola Memento - sangat mudah, dan juga memiliki keuntungan menyediakan kerangka kerja Redo secara alami. Manfaat yang lebih halus adalah bahwa tindakan agregat juga dapat dimasukkan dalam satu Urung.

Singkatnya, Anda memiliki dua tumpukan benda kenang-kenangan. Satu untuk Urungkan, yang lainnya untuk Ulangi. Setiap operasi membuat kenang-kenangan baru, yang idealnya berupa beberapa panggilan untuk mengubah status model, dokumen (atau apa pun) Anda. Ini akan ditambahkan ke undo stack. Saat Anda melakukan operasi pembatalan, selain menjalankan tindakan Urungkan pada objek Memento untuk mengubah model kembali, Anda juga mengeluarkan objek dari tumpukan Urungkan dan mendorongnya ke kanan ke tumpukan Ulangi.

Bagaimana metode untuk mengubah status dokumen Anda diimplementasikan bergantung sepenuhnya pada implementasi Anda. Jika Anda dapat membuat panggilan API (mis. ChangeColour (r, g, b)), awali dengan kueri untuk mendapatkan dan menyimpan status terkait. Tetapi polanya juga akan mendukung pembuatan salinan dalam, snapshot memori, pembuatan file temp, dll - semuanya terserah Anda karena ini hanyalah implementasi metode virtual.

Untuk melakukan tindakan agregat (misalnya, pengguna Shift-Memilih beban objek untuk melakukan operasi, seperti menghapus, mengganti nama, mengubah atribut), kode Anda membuat tumpukan Urungkan baru sebagai kenang-kenangan tunggal, dan meneruskannya ke operasi aktual ke tambahkan operasi individu ke. Jadi, metode tindakan Anda tidak perlu (a) memiliki tumpukan global yang perlu dikhawatirkan dan (b) dapat diberi kode yang sama baik dijalankan secara terpisah atau sebagai bagian dari satu operasi agregat.

Banyak sistem pembatalan hanya dalam memori, tetapi Anda dapat mempertahankan pembatalan tumpukan jika Anda mau, saya kira.

Greg Whitfield
sumber
5

Baru saja membaca tentang pola perintah di buku pengembangan tangkas saya - mungkin itu punya potensi?

Anda dapat membuat setiap perintah mengimplementasikan antarmuka perintah (yang memiliki metode Execute ()). Jika Anda ingin membatalkan, Anda dapat menambahkan metode Urung.

info lebih lanjut di sini

Dave Arkell
sumber
4

Saya dengan Mendelt Siebenga pada fakta bahwa Anda harus menggunakan Pola Perintah. Pola yang Anda gunakan adalah Pola Memento, yang dapat dan akan menjadi sangat boros seiring waktu.

Karena Anda sedang mengerjakan aplikasi intensif memori, Anda harus dapat menentukan berapa banyak memori yang boleh digunakan oleh mesin pembatalan, berapa banyak tingkat pembatalan yang disimpan atau beberapa penyimpanan yang akan dipertahankan. Jika Anda tidak melakukan ini, Anda akan segera menghadapi kesalahan akibat mesin kehabisan memori.

Saya akan menyarankan Anda memeriksa apakah ada kerangka kerja yang sudah membuat model untuk undos dalam bahasa pemrograman / kerangka pilihan Anda. Sangat menyenangkan untuk menemukan hal-hal baru, tetapi lebih baik mengambil sesuatu yang sudah ditulis, di-debug, dan diuji dalam skenario nyata. Akan membantu jika Anda menambahkan apa yang Anda tulis ini, sehingga orang dapat merekomendasikan kerangka kerja yang mereka ketahui.

Omer van Kloeten
sumber
3

Proyek Codeplex :

Ini adalah kerangka kerja sederhana untuk menambahkan fungsionalitas Urungkan / Ulangi ke aplikasi Anda, berdasarkan pola desain Perintah klasik. Ini mendukung tindakan penggabungan, transaksi bersarang, eksekusi tertunda (eksekusi pada komitmen transaksi tingkat atas) dan kemungkinan riwayat pembatalan non-linier (di mana Anda dapat memiliki pilihan beberapa tindakan untuk diulang).

sg7
sumber
2

Kebanyakan contoh yang saya baca melakukannya dengan menggunakan perintah atau pola kenang-kenangan. Tetapi Anda juga dapat melakukannya tanpa pola desain dengan struktur deque sederhana .

Patrik Svensson
sumber
Apa yang akan Anda masukkan ke dalam deque?
Dalam kasus saya, saya menempatkan keadaan operasi saat ini yang saya inginkan untuk membatalkan / mengulang fungsi. Dengan memiliki dua deques (undo / redo) saya membatalkan pada antrian undo (pop item pertama) dan memasukkannya ke dalam redo dequeue. Jika jumlah item di antrean melebihi ukuran yang diinginkan, saya meletuskan item di bagian ekor.
Patrik Svensson
2
Apa yang Anda gambarkan sebenarnya adalah pola desain :). Masalah dengan pendekatan ini adalah ketika negara Anda membutuhkan banyak memori - menyimpan beberapa lusin versi negara kemudian menjadi tidak praktis atau bahkan tidak mungkin.
Igor Brejc
Atau Anda bisa menyimpan sepasang closure yang mewakili operasi normal dan undo.
Xwtek
2

Cara cerdas untuk menangani pembatalan, yang akan membuat perangkat lunak Anda juga cocok untuk kolaborasi multi-pengguna, adalah menerapkan transformasi operasional struktur data.

Konsep ini tidak terlalu populer tetapi didefinisikan dengan baik dan bermanfaat. Jika definisi terlihat terlalu abstrak bagi Anda, proyek ini adalah contoh yang berhasil tentang bagaimana transformasi operasional untuk objek JSON didefinisikan dan diimplementasikan dalam Javascript

danza
sumber
1

Kami menggunakan kembali pemuatan file dan menyimpan kode serialisasi untuk "objek" untuk bentuk yang nyaman untuk menyimpan dan memulihkan seluruh status objek. Kami mendorong objek serial tersebut ke undo stack - bersama dengan beberapa informasi tentang operasi apa yang dilakukan dan petunjuk untuk membatalkan operasi tersebut jika tidak ada cukup info yang dikumpulkan dari data serial. Undo dan Redoing seringkali hanya mengganti satu objek dengan yang lain (secara teori).

Ada banyak BANYAK bug karena pointer (C ++) ke objek yang tidak pernah diperbaiki saat Anda melakukan beberapa urutan pengurungan ulang yang aneh (tempat-tempat tersebut tidak diperbarui ke "pengidentifikasi" yang lebih aman dan tidak sadar). Bug di area ini sering ... ummm ... menarik.

Beberapa operasi dapat menjadi kasus khusus untuk kecepatan / penggunaan sumber daya - seperti mengukur sesuatu, memindahkan barang.

Banyak pilihan juga memberikan beberapa komplikasi menarik. Untungnya kami sudah memiliki konsep pengelompokan dalam kodenya. Komentar Kristopher Johnson tentang sub-item sangat mirip dengan apa yang kami lakukan.

tapir
sumber
Ini terdengar semakin tidak bisa dijalankan seiring dengan bertambahnya ukuran model Anda.
Warren P
Dengan cara apa? Pendekatan ini tetap bekerja tanpa perubahan karena "hal" baru ditambahkan ke setiap objek. Kinerja bisa menjadi masalah karena bentuk serial dari objek bertambah besar - tetapi ini bukan masalah besar. Sistem ini telah dikembangkan secara berkelanjutan selama lebih dari 20 tahun dan digunakan oleh 1000 pengguna.
Aardvark
1

Saya harus melakukan ini saat menulis pemecah untuk permainan puzzle peg-jump. Saya membuat setiap gerakan objek Command yang menyimpan cukup informasi sehingga bisa dilakukan atau dibatalkan. Dalam kasus saya, ini semudah menyimpan posisi awal dan arah setiap gerakan. Saya kemudian menyimpan semua objek ini dalam tumpukan sehingga program dapat dengan mudah membatalkan gerakan sebanyak yang diperlukan saat mundur.

Bill the Lizard
sumber
1

Anda dapat mencoba implementasi pola Undo / Redo yang sudah jadi di PostSharp. https://www.postsharp.net/model/undo-redo

Ini memungkinkan Anda menambahkan fungsionalitas undo / redo ke aplikasi Anda tanpa menerapkan polanya sendiri. Ini menggunakan pola Recordable untuk melacak perubahan dalam model Anda dan bekerja dengan pola INotifyPropertyChanged yang juga diimplementasikan di PostSharp.

Anda diberikan kontrol UI dan Anda dapat memutuskan apa nama dan perincian dari setiap operasi.

Antonín Procházka
sumber
0

Saya pernah bekerja pada aplikasi di mana semua perubahan yang dibuat oleh perintah ke model aplikasi (yaitu CDocument ... kami menggunakan MFC) dipertahankan di akhir perintah dengan memperbarui bidang dalam database internal yang dipertahankan dalam model. Jadi kami tidak perlu menulis kode undo / redo yang terpisah untuk setiap tindakan. Tumpukan urung hanya mengingat kunci utama, nama bidang, dan nilai lama setiap kali catatan diubah (di akhir setiap perintah).

Agnel Kurian
sumber
0

Bagian pertama dari Pola Desain (GoF, 1994) memiliki kasus penggunaan untuk mengimplementasikan undo / redo sebagai pola desain.

Peter Turner
sumber
0

Anda dapat membuat ide awal Anda berhasil.

Gunakan struktur data yang persisten , dan pertahankan dengan menyimpan daftar referensi ke keadaan lama . (Tapi itu hanya benar-benar berfungsi jika operasi semua data di kelas negara Anda tidak dapat diubah, dan semua operasi di atasnya mengembalikan versi baru --- tetapi versi baru tidak perlu berupa salinan dalam, cukup ganti salinan bagian yang diubah -on-write '.)

Matthias
sumber
0

Saya telah menemukan pola Command sangat berguna di sini. Alih-alih menerapkan beberapa perintah terbalik, saya menggunakan rollback dengan eksekusi tertunda pada contoh kedua dari API saya.

Pendekatan ini tampaknya masuk akal jika Anda menginginkan upaya implementasi yang rendah dan kemudahan pemeliharaan (dan dapat membeli memori tambahan untuk instans kedua).

Lihat di sini untuk contoh: https://github.com/thilo20/Undo/

Thilo
sumber
-1

Saya tidak tahu apakah ini akan berguna bagi Anda, tetapi ketika saya harus melakukan sesuatu yang serupa di salah satu proyek saya, saya akhirnya mengunduh UndoEngine dari http://www.undomadeeasy.com - mesin yang luar biasa dan saya benar-benar tidak terlalu peduli tentang apa yang ada di bawah kap mesin - itu berhasil.

NativeBreed
sumber
Silakan posting komentar Anda sebagai jawaban hanya jika Anda yakin dapat memberikan solusi! Jika tidak, lebih suka mempostingnya sebagai komentar di bawah pertanyaan! (jika tidak memungkinkan untuk melakukannya sekarang! harap tunggu sampai Anda mendapatkan reputasi yang baik)
InfantPro'Aravind '11
-1

Menurut saya, UNDO / REDO dapat diimplementasikan dalam 2 cara secara luas. 1. Command Level (disebut command level Undo / Redo) 2. Tingkat dokumen (disebut global Undo / Redo)

Tingkat perintah: Seperti yang ditunjukkan oleh banyak jawaban, ini dicapai secara efisien dengan menggunakan pola Memento. Jika perintah juga mendukung penjurnalan tindakan, pengulangan mudah didukung.

Batasan: Setelah cakupan perintah keluar, undo / redo tidak mungkin dilakukan, yang mengarah ke tingkat dokumen (global) undo / redo

Saya kira kasus Anda akan cocok dengan undo / redo global karena cocok untuk model yang melibatkan banyak ruang memori. Selain itu, ini juga cocok untuk membatalkan / mengulang secara selektif. Ada dua tipe primitif

  1. Semua memori dibatalkan / ulangi
  2. Tingkat objek Urungkan Ulangi

Dalam "Semua memori Undo / Ulangi", seluruh memori diperlakukan sebagai data yang terhubung (seperti pohon, atau daftar atau grafik) dan memori dikelola oleh aplikasi daripada OS. Jadi operator baru dan hapus jika di C ++ kelebihan beban untuk memuat struktur yang lebih spesifik untuk mengimplementasikan operasi secara efektif seperti a. Jika ada node yang dimodifikasi, b. memegang dan membersihkan data, dll., Cara fungsinya pada dasarnya adalah menyalin seluruh memori (dengan asumsi bahwa alokasi memori sudah dioptimalkan dan dikelola oleh aplikasi menggunakan algoritme lanjutan) dan menyimpannya dalam tumpukan. Jika salinan memori diminta, struktur pohon disalin berdasarkan kebutuhan untuk memiliki salinan yang dangkal atau dalam. Salinan dalam dibuat hanya untuk variabel yang dimodifikasi. Karena setiap variabel dialokasikan menggunakan alokasi khusus, aplikasi memiliki keputusan akhir kapan harus menghapusnya jika perlu. Hal-hal menjadi sangat menarik jika kita harus mempartisi Undo / Redo ketika kebetulan kita perlu Undo / Redo secara selektif programatik satu set operasi. Dalam hal ini, hanya variabel baru tersebut, atau variabel yang dihapus atau variabel yang dimodifikasi yang diberi tanda sehingga Undo / Redo hanya membatalkan / mengulang memori tersebut. Hal-hal menjadi lebih menarik jika kita perlu melakukan sebagian Undo / Redo di dalam suatu objek. Jika demikian, gagasan baru tentang "Pola pengunjung" digunakan. Ini disebut "Undo / Ulangi Tingkat Objek" atau variabel yang dihapus atau variabel yang dimodifikasi diberi tanda sehingga Undo / Redo hanya membatalkan / mengulang memori tersebut. Hal-hal menjadi lebih menarik jika kita perlu melakukan sebagian Urungkan / Ulangi di dalam suatu objek. Jika demikian, gagasan baru tentang "Pola pengunjung" digunakan. Ini disebut "Undo / Ulangi Tingkat Objek" atau variabel yang dihapus atau variabel yang dimodifikasi diberi tanda sehingga Undo / Redo hanya membatalkan / mengulang memori tersebut. Hal-hal menjadi lebih menarik jika kita perlu melakukan sebagian Urungkan / Ulangi di dalam suatu objek. Jika demikian, gagasan baru tentang "Pola pengunjung" digunakan. Ini disebut "Undo / Ulangi Tingkat Objek"

  1. Tingkat objek Undo / Redo: Ketika pemberitahuan untuk membatalkan / mengulang dipanggil, setiap objek mengimplementasikan operasi streaming dimana, streamer mendapatkan dari objek data lama / data baru yang diprogram. Data yang tidak akan diganggu dibiarkan tidak terganggu. Setiap objek mendapat streamer sebagai argumen dan di dalam panggilan UNDo / Redo, itu mengalirkan / melepaskan data dari objek.

Baik 1 dan 2 bisa memiliki metode seperti 1. BeforeUndo () 2. AfterUndo () 3. BeforeRedo () 4. AfterRedo (). Metode ini harus diterbitkan dalam Perintah Batalkan / ulangi dasar (bukan perintah kontekstual) sehingga semua objek menerapkan metode ini juga untuk mendapatkan tindakan tertentu.

Strategi yang baik adalah membuat gabungan dari 1 dan 2. Yang menarik adalah bahwa metode ini (1 & 2) sendiri menggunakan pola perintah

Parthasarathy SRINIVASAN
sumber