鈍器本の自前vectorをJavaで実装したかった（敗北）

前回の読書日記で悩んでいたら、E_mattsanから「Javaで書いてみては？」とコメントで助言をいただきました。なるほど！

…結論をいうと、収穫を得る前にギブアップしてしまったのですが、迷走の記録を貼っておきます。

（追記: 2011/12/31）修正版を書きました。→ 鈍器本の自前vectorをJavaで実装（修正版） - 虎塚

まずはdouble型専用の自前vectorをJava化してみました。

package study.donki;

/**
 * 『ストラウストラップのプログラミング入門』の自前vector（※ただしdouble型に限る）をJavaで書き換えてみる
 * 
 */
public class VectorModoki implements Cloneable {
	private int sz; // 要素数（明示的に値を代入した要素の数）
	private double[] elem; // 要素
	private int space; // 要素数＋空きスロット数。elem.lengthとイコール。

	public VectorModoki() {
		sz = 0;
		space = 0;
		elem = null;
	}

	public VectorModoki(int s) {
		sz = s;
		elem = new double[s];
		space = s;

		for (int i = 0; i < sz; i++) {
			elem[i] = 0.0;
		}
	}

	public VectorModoki(final VectorModoki arg) {
		sz = arg.sz;
		elem = new double[arg.sz];
		for (int i = 0; i < arg.sz; i++) {
			elem[i] = arg.elem[i];
		}
	}

	/**
	 * VectorModokiオブジェクトのディープコピーを行う。 operator=のオーバーライドもどき。（？）
	 * 
	 * @see java.lang.Object#clone()
	 */
	@Override
	public Object clone() {
		try {
			// TODO: szまでの要素をコピーし、後ろの余分なspaceはコピーしたくない。
			return super.clone();
		} catch (CloneNotSupportedException e) {
			// ユーザコード側でcatchするのがめんどいので握りつぶす。ひしだまさんリスペクト。
			// c.f. http://www.ne.jp/asahi/hishidama/home/tech/java/clone.html
			throw new InternalError(e.toString());
		}
	}

	/**
	 * インデックスアクセスのために、getメソッドを提供する。VectorModokiは[]オペレータによるアクセスを提供できないため。
	 * 
	 * @param index
	 * @return
	 */
	public double get(int index) {
		// getの上限がelem.lengthでなくszなのは、明示的に値を代入済みの要素までを取得可能な要素とみなすため。
		if (index < 0 || sz < index) {
			throw new ArrayIndexOutOfBoundsException(); // gomen...
		}
		return elem[index];
	}

	public int size() {
		return sz;
	}

	public final int capacity() {
		return space;
	}

	public void resize(int newsize) {
		// VectorModokiにnewsize個の要素を持たせる
		reserve(newsize);
		for (int i = sz; i < newsize; ++i) {
			elem[i] = 0.0; // 新しい要素を初期化する
		}
		sz = newsize;
	}

	public void push_back(double d) {
		if (space == 0) { // 最初は要素8つ分の領域を確保する
			reserve(8);
		} else if (sz == space) {
			reserve(2 * space);
		}

		elem[sz] = d; // dを値あり要素の末尾として追加する
		++sz; // サイズを増やす
	}

	public void reserve(int newalloc) {
		if (newalloc <= space) {
			return;
		}
		double[] p = new double[newalloc]; // 新しい領域を割り当てる
		// 古い領域をコピーする。ただし、明示的に値を代入した要素までとする。
		for (int i = 0; i < sz; i++) {
			p[i] = elem[i];
		}
		// Javaにはdeleteがないので、古い領域の割り当て解除は省略
		elem = p;
		assert equals(elem.length == newalloc);
		space = newalloc;
	}
}

C++版との違いはこのあたりです。

Javaではメモリの取得と解放を行わないので、放置。
Javaではオペレータのオーバーライドができないので、ユーザの独自クラスを[]演算子でアクセスさせることができない。そのため、getメソッドを用意。
値を初期化せずにメモリだけ確保した状態を、Javaで表現するのは無理がある。上のコードでは、明示的に値を代入した要素を、初期化済みの値であると位置づけた。しかし、そうすると、0.0を明示的に代入した要素と、デフォルト値0.0で初期化した値との区別がつかない。あらら。

あと、cloneメソッドなんか使うくらいなら、ディープコピーを行うcopyメソッドを別途定義したほうが健全ではないか、等の疑問がありますね。。。まあいいや、次です。

鈍器本ではテンプレートを利用して、double型専用に作ったvectorを、様々な型で使えるようにしていました。

Javaにはテンプレートがないので、（内部的動作は異なるものの）似たようなことを実現できるジェネリックスを利用して、書いてみます。

package study.donki;

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

/**
 * 『ストラウストラップのプログラミング入門』の自前vector（汎用版）をJavaで書き換えてみる
 * 
 */
public class VectorModokiG<T> implements Cloneable {
	private int sz; // 要素数（明示的に値を代入した要素群の末尾を示す）
	private List<T> elem; // 要素
	private int space; // 要素数＋空きスロット数。elem.size()とイコール

	public VectorModokiG() {
		sz = 0;
		space = 0;
		elem = null;
	}

	public VectorModokiG(int s) {
		sz = s;
		elem = new ArrayList<T>();
		space = s;

		for (int i = 0; i < sz; i++) {
			elem.add(null);
		}
	}

	public VectorModokiG(final VectorModokiG<T> arg) {
		sz = arg.sz;
		elem = new ArrayList<T>(arg.sz);
		for (int i = 0; i < arg.sz; i++) {
			elem.set(i, arg.elem.get(i));
		}
	}

	/**
	 * VectorModokiオブジェクトのディープコピーを行う。 operator=のオーバーライドもどき。（？）
	 * 
	 * @see java.lang.Object#clone()
	 */
	@Override
	public Object clone() {
		try {
			// TODO: szまでの要素をコピーし、後ろの余分なspaceはコピーしたくない。
			return super.clone();
		} catch (CloneNotSupportedException e) {
			// ユーザコード側でcatchするのがめんどいので握りつぶす。ひしだまさんリスペクト。
			// c.f. http://www.ne.jp/asahi/hishidama/home/tech/java/clone.html
			throw new InternalError(e.toString());
		}
	}

	/**
	 * インデックスアクセスのために、getメソッドを提供する。VectorModokiは[]オペレータによるアクセスを提供できないため。
	 * 
	 * @param index
	 * @return
	 */
	public T get(int index) {
		// getの上限がelem.lengthでなくszなのは、明示的に値を代入済みの要素までを取得可能な要素とみなすため。
		if (index < 0 || sz < index) {
			throw new ArrayIndexOutOfBoundsException(); // gomen...
		}
		return elem.get(index);
	}

	public int size() {
		return sz;
	}

	public final int capacity() {
		return space;
	}

	public void resize(int newsize) {
		// VectorModokiにnewsize個の要素を持たせる
		reserve(newsize);
		for (int i = sz; i < newsize; ++i) {
			elem.set(i, null); // 新しい要素を初期化する
		}
		sz = newsize;
	}

	public void push_back(T d) {
		if (space == 0) { // 最初は要素8つ分の領域を確保する
			reserve(8);
		} else if (sz == space) {
			reserve(2 * space);
		}

		elem.set(sz, d); // dを値あり要素の末尾として追加する
		++sz; // サイズを増やす
	}

	public void reserve(int newalloc) {
		if (newalloc <= space) {
			return;
		}
		List<T> p = new ArrayList<T>(); // 新しい領域を割り当てる
		// 古い領域をコピーする。ただし、明示的に値を代入した要素までとする。
		for (int i = 0; i < sz; i++) {
			p.add(elem.get(i));
		}
		for (int i = sz; i < newalloc; i++) {
			p.add(null);
		}
		// Javaにはdeleteがないので、古い領域の割り当て解除は省略
		elem = p;
		assert equals(elem.size() == newalloc);
		space = newalloc;
	}
}

うーん、うーん。。。

ユーザコードはこんな感じです。

package study.donki;

public class UserCode {
	public static void main(String[] args) {

		// 実験(1): VectorModokiに値を追加する
		VectorModoki modoki = new VectorModoki(3);
		System.out.println("size == " + modoki.size());
		System.out.println("capacity == " + modoki.capacity());
		modoki.push_back(100.0);
		modoki.push_back(200.0);
		System.out.println("size == " + modoki.size());
		System.out.println("capacity == " + modoki.capacity());
		for (int i = 0; i < modoki.size(); i++) {
			System.out.println("[" + i + "] == " + modoki.get(i));
		}

		printSeparator();

		// 実験(2): (1)のオブジェクトをコピーする
		VectorModoki cloModoki;
		cloModoki = (VectorModoki) modoki.clone();
		System.out.println("size == " + cloModoki.size());
		System.out.println("capacity == " + cloModoki.capacity());
		for (int i = 0; i < cloModoki.size(); i++) {
			System.out.println("[" + i + "] == " + cloModoki.get(i));
		}

		printSeparator();

		// 実験(3): 汎用版VectorModokiGをStringで扱うことにして、値を追加する
		VectorModokiG<String> strModoki = new VectorModokiG<String>(3);
		System.out.println("size == " + strModoki.size());
		System.out.println("capacity == " + strModoki.capacity());
		strModoki.push_back("hoge");
		strModoki.push_back("moga");
		System.out.println("size == " + strModoki.size());
		System.out.println("capacity == " + strModoki.capacity());
		for (int i = 0; i < strModoki.size(); i++) {
			System.out.println("[" + i + "] == " + strModoki.get(i));
		}

		printSeparator();

		// 実験(4): 汎用版VectorModokiGをユーザクラスで扱うことにして、値を追加する
		VectorModokiG<catStructure> catm = new VectorModokiG<catStructure>(3);
		System.out.println("size == " + catm.size());
		System.out.println("capacity == " + catm.capacity());
		catm.push_back(new catStructure(5, "Tama", Color.SHIRO));
		catm.push_back(new catStructure(2, "Mee", Color.MIKE));
		System.out.println("size == " + catm.size());
		System.out.println("capacity == " + catm.capacity());
		for (int i = 0; i < catm.size(); i++) {
			System.out.println("[" + i + "] == " + catm.get(i));
		}
	}

	protected static void printSeparator() {
		System.out.println("--------");
	}
}

class catStructure {
	protected int age;
	protected String name;
	protected Color color;

	public catStructure() {
		age = 0;
		name = "nanashi";
		color = Color.NA;
	}

	public catStructure(int a, String n, Color c) {
		age = a;
		name = n;
		color = c;
	}

	@Override
	public String toString() {
		return "[age==" + age + ", name==" + name + ", color==" + color + "]";
	}
}

enum Color {
	NA, SHIRO, KURO, MIKE, KINCHA, KIJITORA, CHATORA,
}

読ませる気あんのかって感じに汚いですね。ごめんなさい。こういうときどうやって書いたらいいのかわからないの・・・。

実行結果です。

size == 3
capacity == 3
size == 5
capacity == 6
[0] == 0.0
[1] == 0.0
[2] == 0.0
[3] == 100.0
[4] == 200.0
--------
size == 5
capacity == 6
[0] == 0.0
[1] == 0.0
[2] == 0.0
[3] == 100.0
[4] == 200.0
--------
size == 3
capacity == 3
size == 5
capacity == 6
[0] == null
[1] == null
[2] == null
[3] == hoge
[4] == moga
--------
size == 3
capacity == 3
size == 5
capacity == 6
[0] == null
[1] == null
[2] == null
[3] == [age==5, name==Tama, color==SHIRO]
[4] == [age==2, name==Mee, color==MIKE]

根本的に無理がありますが、やりたかったことにはそこそこ近くなりました。push_backでsizeが増えてしまうあたりとか。その際に割り当て分は2倍取ってくるあたりとか。

さて、ここでようやく本題のAlocatorと基底クラス（vector_base）を導入しようとしたのですが、はたと止まってしまいました。

Javaのジェネリックスは、C++のテンプレート引数のように、Aの前にあるTでAを初期化する、といったことはできません。えぇっ！？どうすれば・・・。

というわけで、このアプローチは一回休み。

~~VectorModoki.java https://gist.github.com/1533795~~
~~VectorModokiG.java https://gist.github.com/1533799~~
~~UserCode.java https://gist.github.com/1533804~~

（追記: 2011/12/31）修正版のコードセット https://gist.github.com/1541121