템플릿 메서드 패턴: Segment Tree

책 Effective Java의 아이템 20에서 '템플릿 메서드 패턴'을 간단하게 소개하는 부분이 있다. 인터페이스로 타입을 정의하고, 추상 클래스에 다른 하위 클래스에서 공통적으로 정의될 메서드를 모아서 하위 클래스의 골격으로 사용하는 것이다. 글로만 봤을 때는 이 패턴이 왜 좋은지 크게 와닿지 않아서 최근에 알고리즘 문제(BOJ10868, BOJ2042)를 풀기 위해 공부했던 Segment Tree에 이 패턴을 적용해서 만들어 볼 수 있을 것 같아서 구현해보았다.

먼저 인터페이스에 들어갈 메서드가 어떤 것이 있을 지 생각해봤다.

public interface SegmentTree {
    Object[] getTree();
    void update(int idx, Object diff);
    Object getIntervalValue(int left, int right);
}

기본적으로 3개의 메서드를 생각했다. 첫 번째는 기본적인 트리를 배열 형태로 반환하는 메서드이다. Segment Tree는 기본적으로 인덱스로 트리에서의 위치를 기억하지만, 기본적인 데이터를 볼 수는 있어야 한다고 생각했기 때문이다. 두 번째는 update 메서드인데, 변경할 데이터의 인덱스와 변경될 때의 차이를 매개변수로 갖는다. Segment Tree 자료 구조에서 기본적으로 사용되는 메서드라고 생각해서 추가해두었다. 세 번째는 getIntervalValue 메서드인데, 구하고자 하는 값의 범위의 시작과 끝을 매개변수로 갖는다. 이것 또한 Segment Tree 자료 구조에서 기본적으로 사용되는 메서드이다.

다음으로 추상 골격 구현 클래스를 작성했다.

public abstract class AbstractSegmentTree implements SegmentTree {
    protected Object[] tree;
    protected final int height, arrayLength;

    protected AbstractSegmentTree(Object[] arr) {
        arrayLength = arr.length;
        height = (int) Math.ceil(Math.log(arrayLength) / Math.log(2));
        tree = new Object[(int) Math.pow(2, height + 1)];
        generate(arr, 1, 0, arrayLength - 1);
    }
    public Object[] getTree() { return tree; }
    public void update(int idx, Object diff) {
        internalUpdate(1, 0, arrayLength - 1, idx, diff);
    }
    public Object getIntervalValue(int left, int right) {
        return internalIntervalValue(1, 0, arrayLength - 1, left, right);
    }
    abstract Object generate(Object[] arr, int current, int start, int end);
    abstract void internalUpdate(int current, int start, int end, int idx, Object diff);
    abstract Object internalIntervalValue(int current, int start, int end, int left, int right);
}

이 클래스는 tree라는 Object 배열과 생성할 때 주어지는 Object 배열에 의해 결정되는 정수인 height, arrayLength를 멤버 변수로 갖는다. 위에서 만들어놓은 SegmentTree 인터페이스를 구현하기 때문에 getTree 메서드, update 메서드, getIntervalValue 메서드를 정의해야 한다. 생성자에서 호출하는 generate 메서드와 인터페이스 메서드들이 호출하는 internal~ 로 시작하는 메서드는 어떤 논리 구조를 가진 Segment Tree인지에 따라 구현이 달라지기 때문에 추상 메서드로 만들어 놓고, 이 추상 클래스를 상속받는 클래스에서 구현하도록 만들어 두었다.

이렇게 했을 때, 이 추상 클래스를 상속받은 클래스는 인터페이스를 구현하지 않아도 된다. 그리고 타입은 인터페이스의 타입을 그대로 가져갈 수 있다. 그리고 추상 클래스에 있는 추상 메서드만 정의하면 인터페이스를 자유롭게 사용할 수 있다. 실제로 어떻게 사용하는지 예제를 두 가지 정도 만들어 보았다.

먼저 Long 타입 정수 배열이 들어왔을 때, 구간의 합을 구할 수 있는 클래스를 구현했다.

public class PrefixSumSegmentTree extends AbstractSegmentTree {
    private PrefixSumSegmentTree(Object[] arr) { super(arr); }
    public static PrefixSumSegmentTree create(Long[] arr) { return new PrefixSumSegmentTree(arr); }

    @Override
    Long generate(Object[] arr, int current, int start, int end) {
        if (start == end) return (Long) (this.tree[current] = arr[start]);
        int mid = (start + end) / 2;
        return (Long) (this.tree[current] = generate(arr, current * 2, start, mid) +
                generate(arr, current * 2 + 1, mid + 1, end));
    }

    @Override
    void internalUpdate(int current, int start, int end, int idx, Object diff) {
        if (idx < start || idx > end) return;
        this.tree[current] = (Long) this.tree[current] + (Long) diff;
        if (start != end) {
            int mid = (start + end) / 2;
            internalUpdate(current * 2, start, mid, idx, diff);
            internalUpdate(current * 2 + 1, mid + 1, end, idx, diff);
        }
    }

    @Override
    Long internalIntervalValue(int current, int start, int end, int left, int right) {
        if (left > end || right < start) return 0L;
        if (left <= start && right >= end) return (Long) this.tree[current];
        int mid = (start + end) / 2;
        return internalIntervalValue(current * 2, start, mid, left, right) +
                internalIntervalValue(current * 2 + 1, mid + 1, end, left, right);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        final int defaultBlank = String.valueOf(tree[1]).length() + 1;
        for (int i = 1; i < height + 1; i++) {
            int size = (int) Math.pow(2, i);
            if (i == 1) {
                sb.append(tree[1]).append(" = ");
            } else sb.append(" ".repeat(defaultBlank)).append("= ");
            for (int j = 0; j < size; j += 2) {
                if (tree[size + j] != null) {
                    sb.append("(").append(tree[size + j]).append(" + ");
                    sb.append(tree[size + j + 1]).append(")");
                } else sb.append(tree[(size + j) / 2]);
                if (j < size - 2) sb.append(" + ");
            }
            sb.append('\n');
        }
        return sb.toString();
    }
}

generate 메서드, internalIntervalValue 메서드, internalUpdate 메서드 모두 재귀적으로 작동하며 Object 배열인 tree를 채우거나, 최신화하거나 값을 계산한다. 구간 합의 경우에는 트리 형태를 직관적으로 보여줄 수 있을 것 같아서 toString 메서드도 추가해두었다. 예를 보면 다음과 같다.

Long[] test = new Long[]{3L, 1L, 2L, 5L, 4L};  
PrefixSumSegmentTree prefixSumSegmentTree = PrefixSumSegmentTree.create(test);  
System.out.println(prefixSumSegmentTree);   
---------
15 = (6 + 9)
   = (4 + 2) + (5 + 4)
   = (3 + 1) + 2 + 5 + 4

이것과 비슷하게 구간에서 최솟값을 구할 수 있는 클래스를 구현했는데, update 메서드는 기존의 방식대로 만들면 예외가 발생할 수 있어서 비워두었다.

public class MinimumSegmentTree extends AbstractSegmentTree {
    private Long[] originalArray;
    private MinimumSegmentTree(Object[] arr) {
        super(arr);
        this.originalArray = (Long[]) arr;
    }
    public static MinimumSegmentTree create(Long[] arr) { return new MinimumSegmentTree(arr); }

    @Override
    Long generate(Object[] arr, int current, int start, int end) {
        if (start == end) return (Long) (this.tree[current] = arr[start]);
        int mid = (start + end) / 2;
        return (Long) (this.tree[current] = Math.min(generate(arr, current * 2, start, mid),
                generate(arr, current * 2 + 1, mid + 1, end)));
    }

    @Override
    void internalUpdate(int current, int start, int end, int idx, Object diff) {

    }

    @Override
    Long internalIntervalValue(int current, int start, int end, int left, int right) {
        if (left > end || right < start) return Long.MAX_VALUE;
        if (left <= start && right >= end) return (Long) this.tree[current];
        int mid = (start + end) / 2;
        return Math.min(internalIntervalValue(current * 2 , start, mid, left, right),
                internalIntervalValue(current * 2 + 1, mid + 1, end, left, right));
    }
}

책을 읽고 내가 이해한대로 구현해본 것이라 이것이 일반적으로 사용하는 템플릿 메서드 패턴인지는 확신할 수가 없는데, 글쓴이가 어떤 의도로 그것을 추천하는지는 알 수 있었던 것 같다. 기본적으로 공통으로 사용하는 메서드를 모아서 사용하는 추상 클래스를 사용하는 것이 핵심인 것으로 보이는데, 인터페이스와 엮어서 효율적으로 잘 사용하는 방법인 것 같고, 위의 코드도 좀 더 중복을 줄일 수 있지 않을까 하는 생각도 든다. 다른 Segment Tree 문제를 풀게 되면, 거기서 나오는 새로운 구조도 이렇게 구현해보면서 공통으로 사용할 수 있는 것이 더 없는지 생각해봐야겠다.