[2024.10.09] History 관리(Command 패턴 & Deque 자료구조 & Factory Method 패턴)

Today I Learned

[2024.10.09] History 관리(Command 패턴 & Deque 자료구조 & Factory Method 패턴)

monkeykim 2024. 10. 9. 00:56

History 관리 (Undo, Redo)

회사에서 History 관리에 대한 요구사항을 받았고, 이를 수행하기 위해 디자인 패턴 중 Command 패턴을 이용하기로 하였다.

Command 패턴은 소프트웨어 디자인 패턴 중 하나로, 주로 실행 취소(Undo)와 다시 실행(Redo) 기능을 구현할 때 많이 사용된다. 이 패턴에서는 각 작업을 커맨드 객체로 캡슐화하여, 작업에 대한 정보를 독립적으로 관리하고 실행할 수 있게 한다.

예를 들어, 사용자가 텍스트를 입력하거나 객체를 추가하는 등의 작업을 할 때, 각각의 작업을 커맨드 객체로 만들어 저장한다. 이렇게 하면 언제든지 실행 취소(Undo)나 다시 실행(Redo)할 수 있어, 복잡한 작업도 쉽게 관리할 수 있다.

command-manager.ts

import { Deque } from './deque';

export class CommandManager {
  public undoHistory: Deque;
  public redoHistory: Deque;

  private static instance: CommandManager | null = null;

  private constructor() {
    this.undoHistory = new Deque();
    this.redoHistory = new Deque();
  }

  /**
   * `CommandManager`의 인스턴스를 반환합니다. 이미 인스턴스가 존재하면 해당 인스턴스를 반환하고,
   * 존재하지 않으면 새로 생성합니다.
   * @returns {CommandManager} `CommandManager`의 싱글톤 인스턴스.
   * @throws {Error} 인스턴스 생성 중 오류가 발생할 경우 오류를 출력합니다.
   */
  static getInstance(): CommandManager {
    try {
      if (CommandManager.instance === null) {
        CommandManager.instance = new CommandManager();
      }
      return CommandManager.instance;
    } catch (e) {
      console.error(e);
    }
  }

  /**
   * 주어진 Command를 실행하고, 실행된 Command를 `undoHistory`에 추가합니다.
   * `undoHistory`의 크기가 100개를 초과하면 가장 오래된 Command를 제거합니다.
   * @param {object} command - 실행할 Command 객체. 이 객체는 `execute()` 메서드를 가져야 합니다.
   * @returns {*} Command 실행의 결과를 반환합니다.
   * @throws {Error} Command 실행 중 오류가 발생할 경우 오류를 출력합니다.
   */
  execute(command: any): any {
    try {
      let result;
      // undoHistory 100개 갯수 제한
      if (this.undoHistory.getSize() === 100) {
        this.undoHistory.removeFront();
      }
      if (command) {
        result = command.execute();
        this.undoHistory.addBack(command);
      }
      if (this.redoHistory.getSize() > 0) {
        this.redoHistory.clear();
      }
      return result;
    } catch (e) {
      if (command && command.constructor) {
        console.error(`Error in command instance of type: ${command.constructor.name}`);
      }
      console.error(e);
    }
  }

  /**
   * 실행된 Command를 실행 취소(undo)합니다. 실행 취소된 Command는 `redoHistory`에 추가됩니다.
   * @returns {Promise<void>} 실행 취소 작업이 완료되면 반환됩니다.
   * @throws {Error} 실행 취소 중 오류가 발생할 경우 오류를 출력합니다.
   */
  async undo(): Promise<void> {
    let command: any;
    try {
      command = this.undoHistory.removeBack();
      if (command) {
        command.undo();
        this.redoHistory.addBack(command);
      }
    } catch (e) {
      if (command && command.constructor) {
        console.error(`Error in command instance of type: ${command.constructor.name}`);
      }
      console.error(e);
    }
  }

  /**
   * 실행 취소된 Command를 다시 실행(redo)합니다. 다시 실행된 Command는 `undoHistory`에 추가됩니다.
   * @returns {Promise<void>} 다시 실행 작업이 완료되면 반환됩니다.
   * @throws {Error} 다시 실행 중 오류가 발생할 경우 오류를 출력합니다.
   */
  async redo(): Promise<void> {
    let command: any;
    try {
      const command = this.redoHistory.removeBack();
      if (command) {
        command.redo();
        this.undoHistory.addBack(command);
      }
    } catch (e) {
      if (command && command.constructor) {
        console.error(`Error in command instance of type: ${command.constructor.name}`);
      }
      console.error(e);
    }
  }
}

Command 패턴에서 일반적으로 undoHistory와 redoHistory는 배열을 사용하지만, 여기서는 Deque(데크) 자료구조를 선택했다. 그 이유는 시간 복잡도 때문이다.

히스토리를 관리할 때, 무제한으로 저장할 수 없기 때문에 저장 개수에 제한을 두어야 한다. 이 경우, 가장 오래된 작업은 제거되고, 새로운 작업이 추가되는 방식으로 동작하게 된다.

배열을 사용할 경우, 맨 앞의 요소를 제거하려면 shift() 메서드를 사용해야 하는데, 이때 모든 요소의 인덱스를 재정렬해야 하므로 O(n)의 시간 복잡도를 가지게 된다. 요소가 많아질수록 비효율적이라는 단점이 있다.

반면, Deque는 헤드(head)와 테일(tail) 포인터를 가지고 있어, 맨 앞이나 맨 뒤에서 요소를 제거하고 추가하는 작업을 O(1)의 시간 복잡도로 수행할 수 있다. 이러한 이유로, Deque 자료구조를 사용하여 더 효율적으로 히스토리를 관리하였다.

Deque(데크)

Deque(데크, Double Ended Queue)는 큐와 스택의 기능을 모두 가진 자료구조로, 양쪽 끝(Front와 Back)에서 요소를 추가하거나 제거할 수 있다. Deque는 head와 tail을 통해 각 끝을 관리하며, 이로 인해 효율적인 요소 추가와 제거가 가능하다.

Deque의 구성 요소

head: 가장 앞(front)에 있는 노드를 가리킴.
tail: 가장 뒤(back)에 있는 노드를 가리킴.
node: 실제 값을 가지고 있는 요소로, 다른 노드와 연결됨.
prev: 이전 노드를 가리키는 포인터.
next: 다음 노드를 가리키는 포인터.

deque.ts

export class Node {
  public value; // 노드에 저장되는 실제 값(command)
  public prev; // 이전 노드를 가리키는 링크 (초기값은 null)
  public next; // 이후 노드를 가리키는 링크 (초기값은 null)

  constructor(value: any) {
    this.value = value;
    this.prev = null;
    this.next = null;
  }
}

export class Deque {
  private head; //  Deque의 첫 번째 노드를 가리키는 포인터
  public tail; //  Deque의 마지막 노드를 가리키는 포인터
  public size; //  Deque 안에 있는 노드의 수

  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  /**
   * Deque의 앞에 새로운 값을 추가합니다.
   *
   * @param {any} value - Deque에 추가할 값.
   * @returns {void}
   */
  addFront(value: any): void {
    const newNode = new Node(value);
    if (this.size === 0) {
      // Deque가 비어있는 경우
      this.head = this.tail = newNode;
    } else {
      // 기존의 Deque 앞에 새로운 노드를 추가함
      // 새로운 노드의 next는 기존의 Deque의 head를 가리킨다.
      newNode.next = this.head;
      this.head.prev = newNode;
      // Deque의 head는 새로운 노드를 가리킨다.
      this.head = newNode;
    }
    this.size++;
  }

  /**
   * Deque의 뒤에 새로운 값을 추가합니다.
   *
   * @param {any} value - Deque에 추가할 값.
   * @returns {void}
   */
  addBack(value: any): void {
    const newNode = new Node(value);
    if (this.size === 0) {
      this.head = this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }

  /**
   * Deque의 앞에서 값을 제거하고 반환합니다.
   *
   * @returns {any} - 제거된 값. Deque가 비어있으면 null을 반환합니다.
   */
  removeFront(): any {
    if (this.size === 0) return null;
    // 현재 head의 value를 저장한다.
    const value = this.head.value;
    // 현재 head의 next를 새로운 head로 지정한다.
    this.head = this.head.next;

    //  head가 변경 되었다면, 즉 새로운 head가 존재하면,
    if (this.head) {
      // 이 노드의 prev를 null로 지정한다. 새로운 head보다 더 앞에 있는 노드가 없다는 것을 의미한다.
      this.head.prev = null;
    } else {
      // Deque가 비워지면(this.head가 null이면), tail도 null로 설정하여 Deque가 완전히 비어 있음을 표시한다.
      this.tail = null;
    }
    this.size--;
    return value;
  }

  /**
   * Deque의 뒤에서 값을 제거하고 반환합니다.
   *
   * @returns {any} - 제거된 값. Deque가 비어있으면 null을 반환합니다.
   */
  removeBack(): any {
    if (this.size === 0) return null;
    const value = this.tail.value;
    this.tail = this.tail.prev;
    if (this.tail) {
      this.tail.next = null;
    } else {
      this.head = null;
    }
    this.size--;
    return value;
  }

  /**
   * 현재 Deque의 크기를 반환합니다.
   *
   * @returns {number} - Deque의 노드 수.
   */
  getSize(): number {
    return this.size;
  }

  /**
   * Deque이 비어 있는지 확인합니다.
   *
   * @returns {boolean} - Deque이 비어 있으면 true, 그렇지 않으면 false.
   */
  isEmpty(): boolean {
    return this.size === 0;
  }

  /**
   * Deque을 비웁니다.
   *
   * @returns {void}
   */
  clear(): void {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
}

예시

addFront(0):

Deque에 0을 추가하면 다음과 같은 상태가 된다.
[0]

Head / Tail -> [0]: head와 tail이 모두 0을 가리킨다.

addBack(2)

Deque의 끝에 2를 추가하면 다음과 같은 상태가 된다.
[0, 2]
노드 구성
- 0의 next는 2를 가리킨다.
- 2의 prev는 0을 가리킨다.
Deque 상태
- head는 0을 가리키고, tail은 2를 가리킨다.

Head -> [0] <-> [2] <- Tail

addFront(-1)

Deque의 앞에 -1을 추가하면 다음과 같은 상태가 된다.
[-1, 0, 2]
노드 구성
- -1의 next는 0을 가리킨다. (newNode.next = this.head)
- 0의 prev는 -1을 가리킨다. (this.head.prev = newNode)
- 0의 next는 2를 가리킨다.
- 2의 prev는 0을 가리킨다.
Deque 상태
- head는 -1을 가리키고, tail은 2를 가리킨다.

Head -> [-1] <-> [0] <-> [2] <- Tail

Factory Method 패턴

팩토리 메소드 패턴은 객체 생성 로직을 캡슐화하여 데이터에 따라 적절한 객체를 인스턴스화하는 디자인 패턴이다.

이 패턴을 사용하면, 클라이언트 코드가 직접적으로 객체를 생성하지 않고, 팩토리 메소드를 통해 필요한 객체를 생성할 수 있다.

도입 배경

수많은 Command 클래스들을 클라이언트 코드에서 직접 인스턴스화하다 보면 코드가 난잡해지고, 객체 생성 로직이 흩어지면서 유지보수가 어려워지는 문제가 발생하였다.

이 패턴을 사용하면 객체 생성 로직을 하나의 중앙화된 위치로 모아서 관리를 할 수 있다. 즉, 클라이언트 코드가 Command 클래스에 직접 접근하지 않고, 팩토리 메소드를 통해 필요한 Command 객체를 생성하도록 구조화할 수 있다.

command-factory.ts

type CommandType = 'modify' | 'remove' | 'add' | 'erase' | 'colorChange' | 'clear'

class CommandFactory {
  static createCommand(type: CommandType, data: any): CommandBase {
    switch (type) {
      case 'modify':
        return new ObjectModifiedCommand(data);
      case 'remove':
        return new ObjectRemoveCommand(data);
      case 'add':
        return new ObjectAddCommand(data);
      case 'erase':
        return new ObjectEraseCommand(data);
      case 'colorChange':
        return new ObjectColorChangeCommand(data);
      case 'clear':
        return new ObjectClearCommand(data);
      default:
        throw new Error(`Unrecognized command type '${type}'`);
    }
  }
}

export { CommandFactory };

'Today I Learned' 카테고리의 다른 글

[2024.10.17] JavaScript의 Prototype과 __proto__ (1)	2024.10.17
[2024.10.16] Angular EventEmitter (0)	2024.10.16
[2024.10.15] 정보처리기사 실기 3회 모의고사 오답 (1)	2024.10.15
[2024.10.10] event.preventDefault & event stopPropagation (0)	2024.10.10
[2024.10.08] 정보처리기사 실기 문제 풀이 (1)	2024.10.08

현재글[2024.10.09] History 관리(Command 패턴 & Deque 자료구조 & Factory Method 패턴)

Monkeykim's blog

개발 공부 블로그입니다. https://github.com/monkeykim111

Factory Method Pattern, 완전탐색, Ctrl + Z, 프로그래머스, Event.preventDefault, output, ngonchange, ctrl + shift + z, __proto__, Command Pattern, event.stoppropagation, event emitter, BRUTE FORCE, 구현, Deque, eventemitter, angular, 데코레이터, Life Cycle, Component,

Today :
Yesterday :

일	월	화	수	목	금	토
		1	2	3	4	5
6	7	8	9	10	11	12
13	14	15	16	17	18	19
20	21	22	23	24	25	26
27	28	29	30	31

Monkeykim's blog