Triển khai thuật toán Undo-Redo trong JavaScript

Đối với hầu hết các ứng dụng (text editor, chỉnh sửa ảnh,...), việc triển khai thuật toán Undo-Redo là thật sự cần thiết. Tuy nhiên, để hiểu và triển khai thuật toán này thì không hề đơn giản chút nào. Vì vậy, bài viết này mình sẽ cố gắng chia sẻ với các bạn những kiến thức mà mình rút ra sau khi đọc và tìm hiểu rất nhiều hướng dẫn trên mạng. Qua đó, bạn có thể dễ dàng triển khai thuật toán Undo-Redo với bất kì ngôn ngữ nào, chứ không chỉ giới hạn ở JavaScript.

Vai trò của việc triển khai thuật toán Undo-Redo

Có lẽ không cần phải nói nhiều về vai trò của thuật toán Undo-Redo. Vì nó hiện diện ở hầu hết các ứng dụng mà lập trình viên chúng ta sử dụng hằng ngày. Công cụ này giúp lưu lại trạng thái của ứng dụng mỗi khi có một sự thay đổi diễn ra.

Nhờ đó mà người dùng có thể đưa ứng dụng quay trở lại trạng thái cũ hoặc từ trạng thái cũ tiến lên trạng thái mới hơn.

Cách thức hoạt động của Undo-Redo

Giả sử, bạn đã lưu lại trạng thái ứng dụng là: S[0], S[1], S[2],..., S[i],..., S[n-1], S[n].

Trong đó:

• S[0] là trạng thái đầu tiên
• S[n] là trạng thái mới nhất của ứng dụng
• S[i] là trạng thái hiện tại của ứng dụng

Cách thức hoạt động của Undo

Undo là hoạt động đưa ứng dụng về trạng thái cũ hơn với bước nhảy là 1: S[n] → S[n-1] → ... → S[1] → S[0]. Nghĩa là bạn chỉ có thể thực hiện Undo khi bạn đang ở trạng thái S[i] với i > 0.

Cách thức hoạt động của Redo

Ngược lại với Undo, Redo là hoạt động đưa ứng dụng về trạng thái mới hơn với bước nhảy là 1: S[0] → S[1] → ... → S[n-1] → S[n]. Nghĩa là bạn chỉ có thể thực hiện Redo khi bạn đang ở trạng thái thứ S[i] với i < n.

Cách thức hoạt động của phần Thêm trạng thái

Khi có một trạng thái mới được thêm vào tập các trạng thái của Undo-Redo, sẽ có 2 trường hợp mà bạn cần phải quan tâm:

• Ứng dụng đang ở trạng thái mới nhất S[n]: Trường hợp này đơn giản, bạn chỉ cần thêm trạng thái S[n + 1] vào sau trạng thái S[n]. Khi đó, tập trạng thái của ứng dụng là: S[0], S[1], S[2],..., S[n-1], S[n], S[n+1].

• Ứng dụng đang ở trạng thái cũ S[i] với i < n: Trường hợp này xảy ra khi bạn đã thực hiện ít nhất một lần Undo. Lúc này, bạn phải xoá đi toàn bộ các trạng thái từ S[i+1] đến S[n]. Sau đó, mới thêm trạng thái S'[i+1] vào sau S[i]. Khi đó, tập trạng thái của ứng dụng là: S[0], S[1], S[2],..., S[i], S'[i+1]. Điều đó cũng có nghĩa là bạn sẽ không thể đưa ứng dụng tới các trạng thái S[i+1], S[i+2],..., S[n], sau khi đã chèn trạng thái S'[i+1] vào.

Chú ý: Trạng thái S'[i+1] khác với S[i+1] và S'[i+1] đang là trạng thái mới nhất hiện tại.

Triển khai thuật toán Undo-Redo

Dựa vào cách thức hoạt động của Undo-Redo đã trình bày phía trên, mình quyết định sẽ sử dụng Stack để lưu lại tập các trạng thái của ứng dụng. Tuy nhiên, để đơn giản mình sẽ sử dụng 2 Stack, 1 stack cho Undo và 1 stack cho Redo.

Dưới đây là code mình triển khai thuật toán Undo-Redo trong JavaScript (các ngôn ngữ khác cũng tương tự):

class UndoRedoHandler {
  constructor(currentstate) {
    this._undoStack = [];
    this._redoStack = [];
    this._redoStack.push(currentstate);
  }

  insert(state) {
    this._undoStack.push(this._redoStack.pop());
    this._redoStack.length = 0;
    this._redoStack.push(state);
  }

  getPrevState() {
    if (this._undoStack.length >= 1) {
      let state = this._undoStack.pop();
      this._redoStack.push(state);
      return state;
    }
  }

  getNextState() {
    if (this._redoStack.length >= 2) {
      let state = this._redoStack.pop();
      this._undoStack.push(state);
      return this._redoStack[this._redoStack.length - 1];
    }
  }

  clear() {
    if (this._redoStack.length >= 1) {
      let state = this._redoStack.pop();
      this._undoStack.length = 0;
      this._redoStack.length = 0;
      this._redoStack.push(state);
    }
  }
}

Triển khai phần Khởi tạo

constructor(currentstate) {
  this._undoStack = [];
  this._redoStack = [];
  this._redoStack.push(currentstate);
}

Thực chất, array trong JavaScript có thể đóng vai trò là Stack, với sự hỗ trợ của các phương thức push, pop. Do đó, mình khởi tạo Undo Stack - this._undoStack và Redo Stack - this._redoStack là các mảng rỗng. Sau đó, push trạng thái hiện tại của ứng dụng currentstate vào this._redoStack.

Mục đích: mình sẽ sử dụng đỉnh của Redo Stack để lưu giá trị hiện tại của ứng dụng.

Nghĩa là: một cách tổng quát, this._undoStack sẽ lưu các trạng thái từ S[0] đến S[i-1] và this._redoStack sẽ lưu các trạng thái từ S[i] đến S[n]. Với S[i] là giá trị hiện tại của ứng dụng, nằm tại đỉnh của this._redoStack.

Dĩ nhiên, bạn có thể cho trạng thái hiện tại vào this._undoStack hoặc tạo thêm một biến để lưu trạng thái này. Khi đó, bạn chỉ cần sửa lại code một chút. Về cơ bản, chúng vẫn giống nhau, nên bạn có thể làm theo cách của mình.

Triển khai phần Thêm trạng thái

insert(state) {
  this._undoStack.push(this._redoStack.pop());
  this._redoStack.length = 0;
  this._redoStack.push(state);
}

Khi thêm một trạng mới vào ứng dụng thì trạng thái hiện tại phải được đưa vào Undo Stack. Do đó mình phải pop state S[i] tại đỉnh của Redo Stack (là giá trị hiện tại của ứng dụng), để push vào Undo Stack:

this._undoStack.push(this._redoStack.pop());

Sau đó, toàn bộ trạng thái S[i+1] đến S[n] bị xoá đi. Tức là this._redoStack phải bị xoá đi:

this._redoStack.length = 0;

Cuối cùng trạng thái state mới nhất sẽ được đưa vào this._redoStack:

this._redoStack.push(state);

Triển khai phần Undo

getPrevState() {
  if (this._undoStack.length >= 1) {
    let state = this._undoStack.pop();
    this._redoStack.push(state);
    return state;
  }
}

Undo tức là quay trở về trạng thái cũ. Nghĩa là trạng thái cũ phải tồn tại thì bạn mới thực hiện Undo được. Ở đây, điều kiện Undo được là this._undoStack phải khác rỗng hay this._undoStack.length >= 1.

Khi điều kiện Undo thoả mãn, bạn có thể thực hiện những thứ sau đây.

Bạn nhớ rằng, trạng thái hiện tại của ứng dụng là S[i]. Undo sẽ đưa ứng dụng về trạng thái S[i-1].

Nghĩa là bạn phải pop trạng thái S[i-1] từ this._undoStack.

let state = this._undoStack.pop();

Trạng thái S[i-1] này sẽ được push vào this._redoStack.

this._redoStack.push(state);

Và return để sử dụng cho việc thay đổi trạng thái ứng dụng.

return state;

Triển khai phần Redo

getNextState() {
  if (this._redoStack.length >= 2) {
    let state = this._redoStack.pop();
    this._undoStack.push(state);
    return this._redoStack[this._redoStack.length - 1];
  }
}

Redo tức là đưa về trạng thái mới hơn. Mà trạng thái mới hơn lại được lưu trữ tại Redo Stack.

Khác với Undo Stack, trạng thái tại đỉnh của Redo Stack luôn là trạng thái hiện tại của ứng dụng. Do đó, để thực hiện Redo thì trong Redo Stack phải có ít nhất 2 phần tử (1 là trạng thái hiện tại, 1 là trạng thái mới hơn).

this._redoStack.length >= 2;

Khi thực hiện Redo, trạng thái hiện tại phải được pop khỏi Redo Stack.

let state = this._redoStack.pop();

Sau đó, trạng thái này được push ngược lại vào Undo Stack.

this._undoStack.push(state);

Lúc này trạng thái mới hơn (cần di chuyển đến) đang nằm ở đỉnh của Redo Stack. Mình cần phải return lại giá trị này để sử dụng cho việc thay đổi trạng thái ứng dụng:

return this._redoStack[this._redoStack.length - 1];

Triển khai phần Clear

clear() {
  if (this._redoStack.length >= 1) {
    let state = this._redoStack.pop();
    this._undoStack.length = 0;
    this._redoStack.length = 0;
    this._redoStack.push(state);
  }
}

Đây là phần mình thêm vào. Phương thức clear này sẽ giữ lại trạng thái hiện tại của ứng dụng, bằng cách pop trạng thái tại đỉnh của Redo Stack:

let state = this._redoStack.pop();

Tiếp theo là xoá bỏ hết tất cả các trạng thái trong 2 Stack bằng cách gán length của chúng bằng 0:

this._undoStack.length = 0;
this._redoStack.length = 0;

Cuối cùng lưu lại trạng thái hiện tại của ứng dụng vào Redo Stack - giống như mình đã làm trong phần khởi tạo.

this._redoStack.push(state);

Demo sử dụng thuật toán Undo-Redo

Đây là một ứng dụng demo đơn giản sử dụng thuật toán Undo-Redo. Ứng dụng này có khả năng thay đổi nội dung và màu sắc của chữ UNDO-REDO.

Nghĩa là mình có thể lưu trạng thái của ứng dụng bằng một object với 2 trường thông tin là: text và color.

Cụ thể:

Phần khởi tạo:

const undoRedoHandler = new UndoRedoHandler({
  text: textDefault,
  color: colorDefault,
});

Phần thêm trạng thái:

undoRedoHandler.insert({
  text: _content.value,
  color: _color.value,
});

Phần Undo:

const state = undoRedoHandler.getPrevState();

if (state) {
  applyPreview(state.text, state.color);
}

Phần Redo:

const state = undoRedoHandler.getNextState();

if (state) {
  applyPreview(state.text, state.color);
}

Phần clear:

undoRedoHandler.clear();

Bạn có thể chạy thử chương trình để thấy rõ được sự thay đổi sau khi thực hiện các lệnh Undo, Redo và Clear.

Lời kết

Trên đây là cách thức triển khai thuật toán Undo-Redo, cũng như cách mình áp dụng nó trong ví dụ thực tế. Dĩ nhiên, với mỗi bài toán cụ thể, bạn sẽ cần phải tuỳ chỉnh lại cách triển khai sao cho phù hợp và tối ưu nhất. Chưa kể đến việc triển khai thuật toán này trên các ngôn ngữ khác có thể sẽ phức tạp hơn JavaScript một chút. Nhưng dù sao thì mình hy vọng rằng bạn đã phần nào hiểu được cách thức triển khai thuật toán Undo-Redo này. Và biến nó thành của chính bạn.

Nếu có phần nào chưa hiểu, cần góp ý hoặc sự giúp đỡ của mình thì bạn có thể để lại dưới phần bình luận phía dưới.

Còn bây giờ thì xin chào và hẹn gặp lại bạn trong bài viết tiếp theo, thân ái!

Tham khảo

• Part 1: Undo/Redo Implementation in C# using Single Object Representing Change Approach
• Part 2: Undo/Redo Implementation in C# using Command Pattern
• Part 3: Undo/Redo Implementation in C# using Memento Pattern