연결리스트를 사용하여 병합이 제대로 이루어지는 것을 확인할 수 있었다.
하지만, 아직 몇 가지 문제점이 남아있었다.
우선, 현재 상태로는 단일 글자의 삽입만 가능하다는 것과 병합 과정에서 충돌에 대한 대비가 제대로 되어있지 않았다.

여러 글자의 삽입/삭제

insertLocal(index: number, letter: string, time: number) {
    const newNode = new Node(this.id, letter, time);
    newNode.nextNode = this.searchNodeByIndex(index);

    if (index - 1 <= 0) {
      this.head = new Node(this.id, '', 0); // head가 없는 경우이므로 head를 먼저 생성
      this.head.nextNode = newNode;
    } else {
      this.searchNodeByIndex(index - 1)!.nextNode = newNode;
    }

    console.log(this.toString());

    return newNode;
}

기존의 코드는 한 글자의 입력을 전제로 구성되어 있다.

여러 글자를 삽입하기 위해서는 아래의 순서가 필요하다.

1. 글자를 각각 토큰화 한다
2. 1의 결과를 연결리스트로 만든다
3. 삽입할 위치에 있는 Node의 nextNode를 2의 head로 수정하고 2의 마지막 Node의 nextNode를 기존 연결리스트로 수정한다

결과적으로 여러 글자가 삽입되는 경우, 해당 글자들을 연결리스트로 만들어 기존 연결리스트에 삽입하면 된다.

이를 구현하기 위해 글자의 length를 함께 인자로 받을 수 있도록 구성했다.
length를 알기 위해 기존 문자열의 길이에서 수정된 문자열의 길이를 빼고 이를 절댓값으로 변환했다.

만약, 기존 문자열 보다 수정된 문자열의 길이가 길었다면 입력에 해당할 것이고 반대로 길이가 짧다면 삭제에 해당할 것이다.
이것을 사용하여 변경된 문자열의 길이를 구하고 selectionStart 이벤트를 이용해 커서의 위치를 구했다.

커서의 위치를 구하고 변경된 문자열의 길이만큼 slice를 한다면 문자열을 얻을 수 있을 것으로 기대했다.

위와 같이 연결리스트로 구성된 문자열이 있을 때 2번째 Node 뒤에 test를 삽입하는 경우라면

1. 기존 문자열의 길이: 5 / 수정된 문자열의 길이: 9 (수정 후 길이 > 기존 문자열)
2. 1에 의해 문자열이 삽입 되었음을 파악
3. selectionStart에 의해 삽입 후 커서의 위치가 6임을 파악
4. 1과 3에 의해 기존의 커서 위치는 6 - 4 = 2임을 파악
5. slice를 통해 삽입된 문자열이 test임을 파악
6. 결과적으로 test라는 문자열이 2번 Node 뒤에 삽입 되었음을 확인

위의 과정을 통해 문자열이 여러 개 삽입 된 경우를 알 수 있었다.
또한, 위와 같은 단계에서 단일 글자인 경우라도 삽입된 길이가 1인 문자열로 동일하게 생각할 수 있었다.

위의 내용을 그림으로 나타내면 다음과 같다.

연결리스트의 장점으로 인해 문자열을 중간에 삽입하는 과정을 효율적으로 수행할 수 있었다.

삭제의 경우는 삽입의 경우와 반대로 해결할 수 있었다.
위의 문자열에서 다시 test를 지우는 경우라면

1. 기존 문자열의 길이: 9 / 수정된 문자열의 길이: 5 (수정 후 길이 < 기존 문자열)
2. 1에 의해 문자열이 삭제 되었음을 파악
3. selectionStart에 의해 삭제 후 커서의 위치가 2임을 파악
4. 결과적으로 1과 3에 의해 문자열이 2 ~ 5까지 삭제되었음을 파악 (커서 2부터 길이 4만큼 삭제)

삽입과 다른 점은 어떤 문자열인지 알 필요가 없다는 것이다.
삭제의 경우는 범위에 대해서만 알면 됐기 때문에 범위를 구하는 것으로 삭제를 구현할 수 있었다.

충돌

앞의 내용들이 자신의 로컬에 적용하는 이야기였다면 충돌은 원격 피어의 문자열과 병합하는 과정에서 발생한다.
내 로컬의 문자열과 상대방의 문자열이 다르다면 적절히 병합하는 과정이 필요하다.
현재 우리는 각 글자를 유니크하게 관리하기 위해 아래와 같은 Identifier를 사용하고 있었다.

export default class Identifier {
  time: number;
  id: string;

  constructor(time: number, id: string) {
    this.time = time;
    this.id = id;
  }
}

export class Node {
  identifier: Identifier;
  letter: string;
  nextNode: Node | null;

  constructor(id: string, letter: string, time: number) {
    this.identifier = new Identifier(time, id);
    this.letter = letter;
    this.nextNode = null;
  }
}

같은 위치에 서로 다른 letter가 있는 경우 충돌로 간주하고

1. time을 비교
2. id (각 클라이언트 고유의 소켓 ID)를 비교

위의 과정을 갖도록 했다.

병합의 경우는 두 가지 경우가 존재했다.

1. 두 연결 리스트의 길이가 다른 경우
2. 두 연결 리스트의 길이가 같은 경우

1번의 경우는 로컬의 연결 리스트를 원격 연결 리스트로 교체하는 것으로 구현했다.
그 이유는 원격의 길이가 다른 경우는 내 로컬에 비해 다른 작업이 수행 되었을 것이라 판단했으며 내 로컬에 비해 최신 정보를 갖고 있을 것이라 판단했기 때문이다.

원격 연결 리스트가 수신되어 병합이 이루어지는 시점은 원격의 수정이 있을 때다.
원격의 수정 + 내 문자열의 길이와 다르다 = 원격이 더 최신의 데이터를 갖는다
위와 같은 생각으로 1번의 경우는 단순히 로컬 연결 리스트를 원격 연결리스트로 교체했다.

두 연결 리스트의 길이가 같은 경우라면 두 연결 리스트를 모두 순회하도록 구성했다.
문자열의 길이가 N이라면 두 연결 리스트를 동시에 순회하는 과정을 거쳐 O(N)으로 순회할 수 있었다.

로직을 코드로 나타내보면 아래와 같다.

private merging(recievedLinkedList: CRDT) {
    const newCRDT = new CRDT(this.id);

    let localPointer = this.head?.nextNode;
    let remotePointer = recievedLinkedList.head?.nextNode;
    let counter = 1;

    while (localPointer && remotePointer) {
      if (
        localPointer.letter === remotePointer.letter &&
        localPointer.identifier.id === remotePointer.identifier.id &&
        localPointer.identifier.time === remotePointer.identifier.time
      ) {
        console.log('같음');
        newCRDT.insert(localPointer.letter, counter++);
      } else {
        if (localPointer.identifier.time < remotePointer.identifier.time) {
          console.log('시간으로 내가 이김');
          newCRDT.insert(localPointer.letter, counter++);
          newCRDT.insert(remotePointer.letter, counter++);
        } else if (localPointer.identifier.time > remotePointer.identifier.time) {
          console.log('시간으로 쟤가 이김');
          newCRDT.insert(remotePointer.letter, counter++);
          newCRDT.insert(localPointer.letter, counter++);
        } else {
          if (localPointer.identifier.id < remotePointer.identifier.id) {
            console.log('id로 내가 이김');
            newCRDT.insert(localPointer.letter, counter++);
            newCRDT.insert(remotePointer.letter, counter++);
          } else {
            console.log('id로 쟤가 이김');
            newCRDT.insert(remotePointer.letter, counter++);
            newCRDT.insert(localPointer.letter, counter++);
          }
        }
      }

      localPointer = localPointer.nextNode;
      remotePointer = remotePointer.nextNode;
    }

    this.head = newCRDT.head;
    this.length = newCRDT.length;
}

(위와 같이 구현하지는 않았으며, 로직을 보기 위해 극단적으로 풀어서 작성한 코드)

로컬과 원격의 연결 리스트를 순회하기 위한 pointer를 하나씩 생성하여 사용했다.

1. 글자와 time, id가 모두 같은 경우 = 동일한 토큰
2. time으로 비교
3. time이 같다면 id로 비교

위와 같은 순서로 비교를 진행했으며 새로운 연결 리스트를 생성하여 순회 결과를 저장하도록 했다.

마지막으로 로컬의 head를 새로운 연결 리스트로 교체하는 것으로 마무리 했다.

결과

기존 연결 리스트로 구현된 부분을 개선하여 더 다양한 상황에 사용할 수 있도록 개선했다.
원격의 결과와 로컬의 결과를 제대로 병합할 수 있었으며 의도한 대로 병합이 되었다.

하지만, 아직 부족한 부분이 있다.
hello | 와 같이 hello 뒤에 커서가 있었고, 원격 피어가 맨 앞에 test를 삽입하는 경우 커서가 밀리게 된다.
testh | ello 이와 같이 앞에 들어오는 글자 수 만큼 커서가 앞으로 밀리게 되는 문제가 발생헀다.