Piece Table은 텍스트 편집기에서 효율적으로 텍스트를 삽입, 삭제, 수정하기 위해 사용되는 데이터 구조입니다.
구조도 단순하고 삽입, 삭제 로직도 직관적이라 바로 구현해보겠습니다.
매우 심플합니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class PieceTable
{
private readonly string originalBuffer;
private StringBuilder addedBuffer;
private List<Piece> pieces;
public PieceTable(string originalText)
{
originalBuffer = originalText;
addedBuffer = new StringBuilder();
pieces = new List<Piece>
{
new Piece(Piece.BufferType.Original, 0, originalText.Length)
};
}
// 함수들
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Piece
{
public enum BufferType
{
Original,
Added
}
public BufferType Type { get; }
public int Start { get; }
public int Length { get; }
public Piece(BufferType type, int start, int length)
{
Type = type;
Start = start;
Length = length;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
public string GetText()
{
var result = new StringBuilder();
foreach (var piece in pieces)
{
string buffer = piece.Type == Piece.BufferType.Original ? originalBuffer : addedBuffer.ToString();
result.Append(buffer.Substring(piece.Start, piece.Length));
}
return result.ToString();
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
public void Insert(int start, string text)
{
addedBuffer.Append(text);
int addedStart = addedBuffer.Length - text.Length;
var newPieces = new List<Piece>();
int position = 0;
int arrayIndex = 0;
foreach (var piece in pieces)
{
if (position + piece.Length <= start)
{
newPieces.Add(piece);
position += piece.Length;
arrayIndex++;
}
else
{
break;
}
}
if (position < start)
{
var splitPiece = pieces[arrayIndex];
int splitOffset = start - position;
newPieces.Add(new Piece(splitPiece.Type, splitPiece.Start, splitOffset));
newPieces.Add(new Piece(Piece.BufferType.Added, addedStart, text.Length));
newPieces.Add(new Piece(splitPiece.Type, splitPiece.Start + splitOffset, splitPiece.Length - splitOffset));
arrayIndex++;
}
else
{
newPieces.Add(new Piece(Piece.BufferType.Added, addedStart, text.Length));
}
if (arrayIndex < pieces.Count)
{
newPieces.AddRange(pieces.GetRange(arrayIndex, pieces.Count - arrayIndex));
}
pieces = newPieces;
}
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
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
public void Delete(int start, int length)
{
var newPieces = new List<Piece>();
int position = 0;
int arrayIndex = 0;
int end = start + length;
foreach (var piece in pieces)
{
if (position + piece.Length <= start)
{
newPieces.Add(piece);
position += piece.Length;
arrayIndex++;
}
else
{
break;
}
}
if (position < start)
{
var splitPiece = pieces[arrayIndex];
int splitOffset = start - position;
newPieces.Add(new Piece(splitPiece.Type, splitPiece.Start, splitOffset));
}
for (int i = arrayIndex; i < pieces.Count; i++)
{
if (position + pieces[i].Length <= end)
{
position += pieces[i].Length;
arrayIndex++;
}
else
{
break;
}
}
if (position < end)
{
var splitPiece = pieces[arrayIndex];
int splitOffset = end - position;
newPieces.Add(new Piece(splitPiece.Type, splitPiece.Start + splitOffset, splitPiece.Length - splitOffset));
arrayIndex++;
}
if (arrayIndex < pieces.Count)
{
newPieces.AddRange(pieces.GetRange(arrayIndex, pieces.Count - arrayIndex));
}
pieces = newPieces;
}
장점
단점