편집기에서 명령들은 Command Pattern 사용한다. 편집기에서 Undo/Redo 기능을 구현하기 위해 사용한 자료구조는 Circular Buffer이다. 사실 Undo/Redo를 구현할 때 대표적으로 사용되는 자료구조는 두 개의 stack을 사용하는 것이다. 하지만 두 개의 stack을 사용하여 현재 이미 실행된 Command 스택과 실행 취소한 Command(또는 Redo 할 수 있는 Command) 스택을 분리하는 것보다 선형 자료구조를 사용하여 구현해보고자 하였다.

Circular Buffer의 Operation

void Init(uint32 Capacity);
void Add(UCommand* NewElement);
void Undo();
void Redo();
UCommand* GetCurrentElement() const;
UCommand* operator[](uint32 Index);
const UCommand* operator[](uint32 Index) const;
uint32 Capacity() const;
uint32 GetNextIndex(uint32 CurrentIndex) const;
uint32 GetPreviousIndex(uint32 CurrentIndex) const;

Circular Buffer의 멤버 변수

uint32 IndexMask; // 주어진 인덱스가 유효한 인덱스로 변환되기 위한 마스크 값. IndexMask는 버퍼의 길이와 같다.

UPROPERTY(VisibleAnywhere)
int32 Current = -1; // 현재 Command를 가리키는 인덱스. 현재 Command는 실행된 상태이다. 초깃값은 -1이다.

UPROPERTY(VisibleAnywhere)
int32 Head = 0; // 처음 Command를 가리키는 인덱스. 초깃값은 0이고, 0보다 작을 수 없다.
	
UPROPERTY(VisibleAnywhere)
int32 Tail = 0; // 마지막 Command를 가리키는 인덱스. 초깃값은 0이고, 0보다 작을 수 없다.
	
/** Holds the buffer's Buffer. */
UPROPERTY(VisibleAnywhere)
TArray<UCommand*> Buffer; // Command를 저장할 배열

연산의 구현

Init

버퍼의 크기는 입력 파라미터 Capcity에 의해 결정된다. 함수 내부에서 RoundUpToPowerOfTwo 함수를 호출하는데 이 함수는 Capacity와 가장 가까우면서 큰 2의 승수를 반환한다.

IndexMask는 코드에서 보여지는 것과 같이 Buffer의 크기보다 1 작다. 그 이유는 IndexMask는 제수이고, 결과인 나머지는 [0, 제수-1]의 범위를 갖기 때문이다.

void ACommandManager::Init(uint32 Capacity)
{
	checkSlow(Capacity <= 0xffffffffU);

	Buffer.Init(nullptr, FMath::RoundUpToPowerOfTwo(Capacity));
	IndexMask = Buffer.Num() - 1;

	EditorPawn = (Cast<ATransformerPawn>(GetOwner()));
}

// MicrosoftPlatformMath.h
static FORCEINLINE uint32 RoundUpToPowerOfTwo(uint32 Arg)
{
		return 1 << CeilLogTwo(Arg);
}

Add

Add 연산은 총 6가지의 경우가 있다.

1. Head == Current Current == Tail
2. Head ≠ Current Current == Tail
3. Head ≠ Current Current == Tail Tail + 1 == Head
4. Head == Current Current ≠ Tail
5. Head ≠ Current Tail ≠ Current
6. Current == -1

위 6가지의 경우는 아래 코드와 같이 2가지 경우로 줄일 수 있다.

// Add 함수는 임의의 Command가 입력 되었을 때, Circular Buffer에 해당 Command가 추가된다.
void ACommandManager::Add(UCommand* NewElement)
{
	if (NewElement)
	{
		if (Current == Tail)
		{
			Current = (Current + 1) & IndexMask;
			Tail = (Tail + 1) & IndexMask;
			if (Tail == Head)
			{
				Head = (Head + 1) & IndexMask;
			}
		}
		else // Current != Tail
		{
			if (Current == -1)
			{
				Current = Head;
			}
			else
			{
				Current = (Current + 1) & IndexMask;
			}
			Tail = Current;
		}

		Buffer[Current] = NewElement;
		Buffer[Current]->Execute();
	}
}