VerticalCode の Java 実装。List<Byte> なぞを使っているので、空間効率はよろしくない。

VerticalCode.java

package verticalcode;

import java.util.ArrayList;
import java.util.List;

public class VerticalCode {
    private static final int BLOCK_BYTES = 1;

    private static final int BLOCK_SIZE = BLOCK_BYTES * 8;

    private static final int NUM_VALUE_BITS = 32;

    private List<Byte> codes;

    private List<Integer> codeIndexes;

    private List<Integer> base;

    private int size;

    public VerticalCode(int[] values) {
        build(values);
    }

    private void build(int[] values) {
        codes = new ArrayList<Byte>();

        codeIndexes = new ArrayList<Integer>();
        codeIndexes.add(0);

        base = new ArrayList<Integer>();
        base.add(0);

        size = values.length;

        int i = 0;
        for (i = 0; i + BLOCK_SIZE < values.length; i += BLOCK_SIZE) {
            buildBlock(values, i);
        }

        if (i < values.length) {
            int[] temp = new int[BLOCK_SIZE];

            int count = 0;
            for (; i < values.length; i++) {
                temp[count++] = values[i];
            }

            buildBlock(temp, 0);
        }
    }

    private void buildBlock(int[] values, int offset) {
        byte[] block = new byte[NUM_VALUE_BITS];

        int sum = 0;
        int msb = 0;
        for (int i = 0; i < BLOCK_SIZE; i++) {
            int val = values[offset + i];
            sum += val;

            int j = 0;
            for (; j < NUM_VALUE_BITS && val != 0; j++) {
                // TODO 以下のキャストは、codes の要素の型に依存する
                block[j] |= (byte) ((val & 1) << i);
                val >>>= 1;
            }

            msb = Math.max(msb, j);
        }

        int prevBase = base.get(base.size() - 1);
        if ((Integer.MAX_VALUE - prevBase) < sum) {
            throw new ArithmeticException(
                    "与えられた数値列をこの Vertical Code 実装で表現することができません。");
        }

        for (int i = 0; i < msb; i++) {
            codes.add(block[i]);
        }

        int prevIndex = codeIndexes.get(codeIndexes.size() - 1); 
        codeIndexes.add(prevIndex + msb);
        base.add(prevBase + sum);
    }

    public int get(int index) {
        int blockIndex = index / BLOCK_SIZE;
        int bitOffset = index & (BLOCK_SIZE - 1);

        int codeIndex = codeIndexes.get(blockIndex);
        int end = codeIndexes.get(blockIndex + 1);

        int result = 0;
        int count = 0;
        for (int i = codeIndex; i < end; i++) {
            int code = codes.get(i);
            result += ((code >>> bitOffset) & 1) << count;
            count++;
        }

        return result;
    }

    public int getTotal(int index) {
        int blockIndex = index / BLOCK_SIZE;
        int bitOffset = index & (BLOCK_SIZE - 1);

        int bitMask = (1 << (bitOffset + 1)) - 1;

        int codeIndex = codeIndexes.get(blockIndex);
        int end = codeIndexes.get(blockIndex + 1);

        int result = 0;
        int count = 0;
        for (int i = codeIndex; i < end; i++) {
            int code = codes.get(i) & bitMask;
            result += Integer.bitCount(code) << count;
            count++;
        }

        return result + base.get(blockIndex);
    }

    public int size() {
        return size;
    }

    public static void main(String[] args) {
        VerticalCode vc = new VerticalCode(new int[] { 1, 0, 1, 1, 2, 3, 5, 8,
                13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597, 2584, 4181,
                6765, 10946, 17711, 28657, 46368, 75025, 121393 });

        for (int i = 0; i < vc.size(); i++) {
            System.out.println(i + " : " + vc.get(i) + ", " + vc.getTotal(i));
        }
    }
}