鈍器本の自前vector（汎用）Java版

VectorModokiG.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;
	}
}