1. 개요
이번에는 trello를 클론코딩하는 프로젝트를 맡게되었다. trello는 칸반보드와 같이 보드 위에 컬럼과 카드를 생성하고, 컬럼과 카드를 자유롭게 이동시킬수 있는 것이 특징이다.
이때 카드간의 이동을 배열로 구현하면 데이터베이스에도 배열 형태로 데이터를 저장시켜야 하거나, 혹은 카드를 옮길때마다 다른 카드의 index를 모두 수정해야 하는 문제가 발생한다.
위 같은 문제때문에 만약 카드가 몇천장이 넘어간다면 옮길때마다 발생하는 소요시간이 너무 커진다. 이러한 상황을 해결하기 위해 다른 방법을 생각해보았다.
2. 카드를 이동, 정렬 시키는 방법
- next 속성으로 다음 카드를 저장하기
첫번째는 연결리스트에서 영감을 받았다. 카드를 옮길때마다 모든 카드를 수정하지 않기 위해서는 현재 카드의 다음에 오는 카드가 무엇인지만 저장하면 된다.
따라서 위와 같이 카드에서 next 속성으로 다음카드의 id를 저장시켜 순서를 구현한다.
- 정렬기준 속성을 생성해 그것만 바꾸기
두번쨰는 정렬기준을 넣어서 카드를 옮길때마다 정렬기준 값을 이동시킬 위치의 이전 카드와 다음 카드의 정렬기준의 사이 값으로 저장한다.
위와 같은 방법에서 정렬기준은 중요한 요소인데 여러가지 방법이 있었지만, jira에서 제공하는 LexoRank를 선택했다.
3. LexoRank
LexoRank는 숫자가 아닌 문자열을 통해 값을 비교한다. 즉 정렬기준을 문자열로 한다.
예를 들면 다음과 같은 알고리즘이다.
1) hzzzzz와 hzzzzv 의 사이값 => hzzzzx
2) hzzzzz와 hzzzzx 의 사이값 => hzzzzy
3) hzzzzz와 hzzzzy 의 사이값 => hzzzzy:i
(z와 y사이에는 알파벳이 없기 때문에 새로운 알파벳이 추가됨)
만약 숫자라면 많은 횟수의 요청이 있을 경우 부동소수점 문제 또는 횟수 제한등의 문제가 발생할 수 있지만, 문자열이기 때문에 횟수도 아득하게 많고 소수점등의 제한도 발생하지 않는다.
- LexoRank 메서드
카드 삽입, 이동등에 필요한 메서드는 다음과 같다.
-
LexoRank.toString()
LexoRank 값을 문자열로만 보여준다. -
LexoRank.middle()
LexoRank 중간 값을 생성한다. (초기 LexoRank값을 생성할때 쓰인다) -
LexoRank.genNext()
현재 LexoRank의 값보다 큰 다음 LexoRank값을 생성한다. -
LexoRank.genPrev()
현재 LexoRank의 값보다 작은 이전 LexoRank값을 생성한다. -
LexoRank.between(other: LexoRank)
두 LexoRank값의 사이값에 해당하는 LexoRank값을 생성한다. -
LexoRank.compareTo(other: LexoRank)
두 LexoRank값을 비교한 결과를 반환한다.
4. 프로젝트 적용 전, 연습코드
실제 프로젝트에 적용하기 이전에 간단한 추상데이터를 바탕으로 카드의 이동을 구현했다.
이동에 필요한 로직은 다음과 같다.
- 이동할 위치가 맨 처음일때, 맨 끝일때, 두 카드의 사이일때로 조건을 나눈다.
- 맨 처음일때는 첫번째 위치한 카드의 LexoRank값에서 genPrev()를 이용해 더 작은 LexoRank값을 할당한다.
- 맨 끝일때는 마지막에 위치한 카드의 LexoRank값에서 genNext()를 이용해 더 큰 LexoRank값을 할당한다.
- 두 카드의 사이일 경우에 between()을 이용해서 두 카드의 LexoRank값들의 사이값인 LexoRank값을 할당한다.
실제 코드 구현은 다음과 같다.
import { Injectable } from "@nestjs/common";
import { LexoRank } from "lexorank";
@Injectable()
export class AppService {
items: { data: string; lexo: LexoRank }[] = [
{ data: "item1", lexo: null },
{ data: "item2", lexo: null },
{ data: "item3", lexo: null },
{ data: "item4", lexo: null },
{ data: "item5", lexo: null },
{ data: "item6", lexo: null },
{ data: "item7", lexo: null },
];
constructor() {
let lexoRank = LexoRank.middle();
this.items.map((item) => {
item.lexo = lexoRank;
lexoRank = lexoRank.genPrev();
});
}
// lexo 값대로 정렬해서 출력
find() {
const newItems = this.items
.sort((a, b) => {
return a.lexo.compareTo(b.lexo);
})
.map((item) => {
return { data: item.data, lexo: item.lexo.toString() };
});
return newItems;
}
// 위치주어짐(어디 뒤로 갈건지), 그리고 어떤걸 이동시킬건지(index 4)
move(id: number, where: number) {
let newLexo: LexoRank;
if (where >= this.items.length) {
newLexo = this.items[this.items.length - 1].lexo.genNext();
} else if (where <= 0) {
newLexo = this.items[0].lexo.genPrev();
} else {
newLexo = this.items[where].lexo.between(
this.items[where + 1].lexo,
);
}
this.items[id].lexo = newLexo;
return true;
}
}참고
