鈍器本の自前vectorのJava版

TestVectorModoki.java

package study.donki;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import org.junit.Test;

public class TestVectorModoki {

	@Test
	public void testDefaultConstructor() throws Exception {
		VectorModoki vec = new VectorModoki();
		assertEquals(0, vec.size());
		assertEquals(0, vec.capacity());
	}

	@Test
	public void testSizeConstructor() throws Exception {
		VectorModoki vec = new VectorModoki(3);
		assertEquals(3, vec.size());
		assertEquals(3, vec.capacity());

		try {
			VectorModoki badVec = new VectorModoki(-1);
			fail();
		} catch (Exception expect) {
			assertTrue(expect instanceof IllegalArgumentException);
		}
	}

	@Test
	public void testCopyConstructor() throws Exception {
		VectorModoki vec = new VectorModoki(3);
		vec.push_back(100.0);
		vec.push_back(200.0);

		VectorModoki vec2 = new VectorModoki(vec);
		assertEquals(5, vec2.size());
		// コピーコンストラクタでは、末尾の余剰スペースをコピーしない。
		assertEquals(5, vec2.capacity());
	}

	@Test
	public void testIndexAccess() throws Exception {
		VectorModoki vec = new VectorModoki(3);
		vec.push_back(100.0);
		assertEquals(100.0, vec.get(3), 0);
	}

	@Test
	public void testSize() throws Exception {
		VectorModoki vec = new VectorModoki(3);
		assertEquals(3, vec.size());
	}

	@Test
	public void testCapacity() throws Exception {
		VectorModoki vec = new VectorModoki(3);
		assertEquals(3, vec.capacity());

		// 要素数＝スペース数のときは、単純に2倍のスペースを確保する。
		vec.push_back(100.0);
		assertEquals(6, vec.capacity());
	}

	@Test
	public void testResize() throws Exception {
		VectorModoki vec = new VectorModoki(3);
		assertEquals(vec.size(), 3);
		assertEquals(vec.capacity(), 3);

		vec.resize(16);
		assertEquals(16, vec.size());
		assertEquals(16, vec.capacity());

		VectorModoki badVec = new VectorModoki(3);
		try {
			badVec.resize(-1);
			fail();
		} catch (Exception expect) {
			assertTrue(expect instanceof IllegalArgumentException);
		}
	}

	@Test
	public void testReserve() throws Exception {
		VectorModoki vec = new VectorModoki(3);
		vec.push_back(100.0);
		assertEquals(vec.size(), 4);
		assertEquals(vec.capacity(), 6);

		vec.reserve(16);
		// size()で取得するszの値は、reserveをラップするresizeで更新されるので、元のまま。
		assertEquals(4, vec.size());
		assertEquals(16, vec.capacity());
		// resize後も元の値が元の位置に保持されていることを確認。
		assertEquals(100.0, vec.get(3), 0);

		VectorModoki zeroVec = new VectorModoki(3);
		zeroVec.reserve(0);
		assertEquals(3, zeroVec.size());
		assertEquals(3, zeroVec.capacity());

		VectorModoki negativeVec = new VectorModoki(3);
		negativeVec.reserve(-1);
		assertEquals(3, negativeVec.size());
		assertEquals(3, negativeVec.capacity());
	}

	@Test
	public void testPush_Back() throws Exception {
		VectorModoki vec = new VectorModoki();
		vec.push_back(100.0);
		assertEquals(0 + 1, vec.size());
		assertEquals(0 + 8, vec.capacity());

		VectorModoki vec2 = new VectorModoki();
		VectorModokiG<String> strVector2 = new VectorModokiG<String>();
		vec2.push_back(100.0);
		vec2.push_back(200.0);
		// size == spaceのVectorModokiオブジェクトを作成するために、コピーコンストラクタを利用。
		VectorModoki vec3 = new VectorModoki(vec2);
		assertEquals(2, vec3.size());
		assertEquals(2, vec3.capacity());
		vec3.push_back(300.0);
		assertEquals(2 + 1, vec3.size());
		assertEquals(2 * 2, vec3.capacity());
	}
}

TestVectorModokiG.java

package study.donki;

import static org.junit.Assert.assertEquals;
import static org.junit.Assert.assertTrue;
import static org.junit.Assert.fail;

import org.junit.Test;

public class TestVectorModokiG {

	@Test
	public void testDefaultConstructor() throws Exception {
		VectorModokiG<String> strVector = new VectorModokiG<String>();
		assertEquals(0, strVector.size());
		assertEquals(0, strVector.capacity());
	}

	@Test
	public void testSizeConstructor() throws Exception {
		VectorModokiG<String> strVector = new VectorModokiG<String>(3);
		assertEquals(3, strVector.size());
		assertEquals(3, strVector.capacity());

		try {
			VectorModokiG<String> strBadVector = new VectorModokiG<String>(-1);
			fail();
		} catch (Exception expect) {
			assertTrue(expect instanceof IllegalArgumentException);
		}
	}

	@Test
	public void testCopyConstructor() throws Exception {
		VectorModokiG<String> strVector = new VectorModokiG<String>(3);
		strVector.push_back("foo");
		strVector.push_back("bar");

		VectorModokiG<String> strVetor2 = new VectorModokiG<String>(strVector);
		assertEquals(5, strVetor2.size());
		// コピーコンストラクタでは、末尾の余剰スペースをコピーしない。
		assertEquals(5, strVetor2.capacity());
	}

	@Test
	public void testIndexAccess() throws Exception {
		VectorModokiG<String> strVector = new VectorModokiG<String>(3);
		strVector.push_back("foo");
		assertEquals("foo", strVector.get(3));
	}

	@Test
	public void testSize() throws Exception {
		VectorModokiG<String> strVector = new VectorModokiG<String>(3);
		assertEquals(3, strVector.size());
	}

	@Test
	public void testCapacity() throws Exception {
		VectorModokiG<String> strVector = new VectorModokiG<String>(3);
		assertEquals(3, strVector.capacity());

		// 要素数＝スペース数のときは、単純に2倍のスペースを確保する。
		strVector.push_back("foo");
		assertEquals(6, strVector.capacity());
	}

	@Test
	public void testResize() throws Exception {
		VectorModokiG<String> strVector = new VectorModokiG<String>(3);
		assertEquals(strVector.size(), 3);
		assertEquals(strVector.capacity(), 3);

		strVector.resize(16);
		assertEquals(16, strVector.size());
		assertEquals(16, strVector.capacity());

		VectorModokiG<String> strBadVector = new VectorModokiG<String>(3);
		try {
			strBadVector.resize(-1);
			fail();
		} catch (Exception expect) {
			assertTrue(expect instanceof IllegalArgumentException);
		}
	}

	@Test
	public void testReserve() throws Exception {
		VectorModokiG<String> strVector = new VectorModokiG<String>(3);
		strVector.push_back("foo");
		assertEquals(strVector.size(), 4);
		assertEquals(strVector.capacity(), 6);

		strVector.reserve(16);
		// size()で取得するszの値は、reserveをラップするresizeで更新されるので、元のまま。
		assertEquals(4, strVector.size());
		assertEquals(16, strVector.capacity());
		// resize後も元の値が元の位置に保持されていることを確認。
		assertEquals("foo", strVector.get(3));

		VectorModokiG<String> strZeroVector = new VectorModokiG<String>(3);
		strZeroVector.reserve(0);
		assertEquals(3, strZeroVector.size());
		assertEquals(3, strZeroVector.capacity());

		VectorModokiG<String> strNegativeVector = new VectorModokiG<String>(3);
		strNegativeVector.reserve(-1);
		assertEquals(3, strNegativeVector.size());
		assertEquals(3, strNegativeVector.capacity());
	}

	@Test
	public void testPush_Back() throws Exception {
		VectorModokiG<String> strVector = new VectorModokiG<String>();
		strVector.push_back("foo");
		assertEquals(0 + 1, strVector.size());
		assertEquals(0 + 8, strVector.capacity());

		VectorModokiG<String> strVector2 = new VectorModokiG<String>();
		strVector2.push_back("foo");
		strVector2.push_back("bar");
		// size == spaceのVectorModokiGオブジェクトを作成するために、コピーコンストラクタを利用。
		VectorModokiG<String> strVector3 = new VectorModokiG<String>(strVector2);
		assertEquals(2, strVector3.size());
		assertEquals(2, strVector3.capacity());
		strVector3.push_back("bar");
		assertEquals(2 + 1, strVector3.size());
		assertEquals(2 * 2, strVector3.capacity());
	}
}

UserCode.java

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 = modoki;
		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,
}

VectorModoki.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 = new double[0];
	}

	public VectorModoki(int s) {
		if (s < 0) {
			throw new IllegalArgumentException();
		}
		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;
		space = arg.sz;
		elem = new double[arg.sz];
		for (int i = 0; i < arg.sz; i++) {
			elem[i] = arg.elem[i];
		}
	}

	/**
	 * インデックスアクセスを提供する。VectorModokiは[]オペレータによるアクセスを提供できないため。
	 * 
	 * @param index
	 * @return
	 */
	public double get(int index) {
		assert equals(sz == elem.length);
		if (index < 0 || sz < index) {
			throw new IndexOutOfBoundsException();
		}
		return elem[index];
	}

	public int size() {
		return sz;
	}

	public final int capacity() {
		return space;
	}

	/**
	 * VectorModokiにnewsize個の要素を持たせる
	 * 
	 * @param newsize
	 */
	public void resize(int newsize) {
		if (newsize < 0) {
			throw new IllegalArgumentException();
		}
		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;
	}
}

VectorModokiG.java

package study.donki;

/**
 * 『ストラウストラップのプログラミング入門』の自前vector（汎用版）をJavaで書き換えてみる
 * 
 */
public class VectorModokiG<T> implements Cloneable {
	private int sz; // 要素数（明示的に値を代入した要素の数）
	private Object[] elem; // 要素

	/**
	 * 要素数＋空きスロット数。elem.size()とイコール Javaでは、C++のalocator.alocate()に該当する処理がないため。
	 */
	private int space;

	public VectorModokiG() {
		sz = 0;
		space = 0;
		elem = new Object[0];
	}

	public VectorModokiG(int s) {
		if (s < 0) {
			throw new IllegalArgumentException();
		}
		sz = s;
		elem = new Object[s];
		space = s;
		for (int i = 0; i < sz; i++) {
			elem[i] = null;
		}
	}

	/**
	 * コピーコンストラクタ。
	 */
	public VectorModokiG(final VectorModokiG<T> arg) {
		sz = arg.sz;
		space = arg.sz;
		elem = new Object[arg.sz];
		for (int i = 0; i < arg.sz; i++) {
			elem[i] = arg.elem[i];
		}
	}

	/**
	 * インデックスアクセスを提供する。VectorModokiは[]オペレータによるアクセスを提供できないため。
	 * 
	 * @param index
	 * @return
	 */
	@SuppressWarnings("unchecked")
	public T get(int index) {
		assert equals(sz == elem.length);
		if (index < 0 || sz < index) {
			throw new IndexOutOfBoundsException();
		}
		return (T) elem[index];
	}

	public int size() {
		return sz;
	}

	public final int capacity() {
		return space;
	}

	/**
	 * VectorModokiGにnewsize個の要素を持たせる
	 * 
	 * @param newsize
	 */
	public void resize(int newsize) {
		if (newsize < 0) {
			throw new IllegalArgumentException();
		}
		reserve(newsize);
		for (int i = sz; i < newsize; ++i) {
			elem[i] = null;
		}
		sz = newsize;
	}

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