開発メモ

開発用のメモです。

リスト構造

ソース

package jp.mirageworld.algorithm.util;

import java.util.AbstractList;
import java.util.Arrays;
import java.util.Collection;
import java.util.List;

public class GenericList<E> extends AbstractList<E> {

    public static class Creator<E> {
        public E newObject() {
            return null;
        }
    }

    protected int capacity;
    protected int addCapacity = 10;
    protected int size = 0;
    protected Object[] parameter;
    protected boolean catchIndexOutOfBounds;

    public GenericList() {
        this(10);
    }

    public GenericList(int capacity) {
        this(capacity, false);
    }

    public GenericList(boolean catchIndexOutOfBounds) {
        this(10, catchIndexOutOfBounds);
    }

    public GenericList(int capacity, boolean catchIndexOutOfBounds) {
        this(capacity, catchIndexOutOfBounds, capacity);
    }

    public GenericList(int capacity, int addCapacity) {
        this(capacity, false, addCapacity);
    }

    public GenericList(int capacity, boolean catchIndexOutOfBounds, int addCapacity) {
        super();
        this.catchIndexOutOfBounds = catchIndexOutOfBounds;
        this.capacity = capacity;
        this.addCapacity = addCapacity;
        this.parameter = array(capacity);
    }

    @SuppressWarnings("unchecked")
    @Override
    public E get(int index) {
        try {
            return (E) this.parameter[index];
        } catch (IndexOutOfBoundsException e) {
            if (!catchIndexOutOfBounds)
                throw e;
        }
        return null;
    }

    public E getFirst() {
        return get(0);
    }

    public E getLast() {
        return get(size - 1);
    }

    @Override
    public int size() {
        return size;
    }

    @Override
    public boolean add(E element) {
        try {
            add(size++, element);
            return true;
        } catch (IndexOutOfBoundsException e) {
            return false;
        }
    }

    @Override
    public void add(int index, E element) {
        while (hasArrayCopy(index)) {
            this.parameter = Arrays.copyOf(this.parameter, capacity + addCapacity);
            capacity = capacity + addCapacity;
        }
        if (index > size) {
            size = index + 1;
        }
        this.parameter[index] = element;
    }

    @Override
    public E set(int index, E element) {
        E old = get(index);
        parameter[index] = element;
        return old;
    }

    @Override
    public E remove(int index) {
        E old = get(index);
        for (int i = index; i < size; i++) {
            this.parameter[i] = this.parameter[i + 1];
            this.parameter[i + 1] = null;
        }
        return old;
    }

    @Override
    public boolean addAll(int index, Collection<? extends E> c) {
        for (E e : c) {
            this.add(index++, e);
        }
        return true;
    }

    @Override
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    @Override
    public List<E> subList(int fromIndex, int toIndex) {
        GenericList<E> subList = new GenericList<>();

        for (int i = fromIndex; i <= toIndex; i++) {
            subList.add(get(i));
        }
        return subList;
    }

    @Override
    protected void removeRange(int fromIndex, int toIndex) {
        if (toIndex < fromIndex) {
            throw new ArrayIndexOutOfBoundsException("from > to");
        }
        int size = this.size;
        for (int i = fromIndex; i <= toIndex && i < this.size; i++, size--) {
            this.remove(fromIndex);
        }
        this.size = size;
    }

    protected E getLastCapacity() {
        return get(capacity - 1);
    }

    protected boolean hasArrayCopy(int index) {
        return (index >= capacity && getLastCapacity() != null);
    }

    @SuppressWarnings("unchecked")
    protected E[] array(int length) {
        E[] temp = array();
        return Arrays.copyOf(temp, length);
    }

    private E[] array(@SuppressWarnings("unchecked") E... es) {
        return es;
    }
}

テストケース

package jp.mirageworld.algorithm.util;

import static org.hamcrest.CoreMatchers.*;
import static org.junit.Assert.*;

import java.util.Arrays;
import java.util.Calendar;
import java.util.List;

import org.junit.Before;
import org.junit.Test;

public class GenericListTest {

    GenericList<Calendar> list;

    @Before
    public void doBefore() {
        list = new GenericList<>();
    }

    @Test
    public void testSize() {
        assertThat(list.size(), is(0));
        list.add(null);
        assertThat(list.size(), is(1));
        try {
            list.add(5, null);
            assertThat(list.size(), is(6));
        } catch (IndexOutOfBoundsException e) {
            fail(e.getClass().getName());
        }
    }

    @Test
    public void testRemoveRange() {
        Calendar c;
        for (int i = Calendar.JANUARY; i <= Calendar.DECEMBER; i++) {
            c = Calendar.getInstance();
            c.set(Calendar.MONTH, i);
            list.add(c);
        }
        list.removeRange(3, 5); // 4月~6月

        assertThat(list.size(), is(9));
        assertThat(list.get(0).get(Calendar.MONTH), is(Calendar.JANUARY));
        assertThat(list.get(1).get(Calendar.MONTH), is(Calendar.FEBRUARY));
        assertThat(list.get(2).get(Calendar.MONTH), is(Calendar.MARCH));
        assertThat(list.get(3).get(Calendar.MONTH), is(Calendar.JULY));
        assertThat(list.get(4).get(Calendar.MONTH), is(Calendar.AUGUST));
        assertThat(list.get(5).get(Calendar.MONTH), is(Calendar.SEPTEMBER));
        assertThat(list.get(6).get(Calendar.MONTH), is(Calendar.OCTOBER));
        assertThat(list.get(7).get(Calendar.MONTH), is(Calendar.NOVEMBER));
        assertThat(list.get(8).get(Calendar.MONTH), is(Calendar.DECEMBER));
    }

    @Test
    public void testGenericList() {
        GenericList<String> list = new GenericList<>();
        assertThat(list.capacity, is(10));
        assertThat(list.addCapacity, is(10));
        assertThat(list.catchIndexOutOfBounds, is(false));
        assertThat(list.parameter.length, is(10));
        assertThat(list.size, is(0));
    }

    @Test
    public void testGenericListInt() {
        GenericList<String> list = new GenericList<>(50);
        assertThat(list.capacity, is(50));
        assertThat(list.addCapacity, is(50));
        assertThat(list.catchIndexOutOfBounds, is(false));
        assertThat(list.parameter.length, is(50));
        assertThat(list.size, is(0));
    }

    @Test
    public void testGenericListBoolean() {
        GenericList<String> list = new GenericList<>(true);
        assertThat(list.capacity, is(10));
        assertThat(list.addCapacity, is(10));
        assertThat(list.catchIndexOutOfBounds, is(true));
        assertThat(list.parameter.length, is(10));
        assertThat(list.size, is(0));
    }

    @Test
    public void testGenericListIntBoolean() {
        GenericList<String> list = new GenericList<>(50, true);
        assertThat(list.capacity, is(50));
        assertThat(list.addCapacity, is(50));
        assertThat(list.catchIndexOutOfBounds, is(true));
        assertThat(list.parameter.length, is(50));
        assertThat(list.size, is(0));
    }

    @Test
    public void testGenericListIntInt() {
        GenericList<String> list = new GenericList<>(50, 100);
        assertThat(list.capacity, is(50));
        assertThat(list.addCapacity, is(100));
        assertThat(list.catchIndexOutOfBounds, is(false));
        assertThat(list.parameter.length, is(50));
        assertThat(list.size, is(0));
    }

    @Test
    public void testGenericListIntBooleanInt() {
        GenericList<String> list = new GenericList<>(50, 100);
        assertThat(list.capacity, is(50));
        assertThat(list.addCapacity, is(100));
        assertThat(list.catchIndexOutOfBounds, is(false));
        assertThat(list.parameter.length, is(50));
        assertThat(list.size, is(0));
    }

    @Test
    public void testGetInt() {
        Calendar c = Calendar.getInstance();
        list.add(c);
        assertThat(list.get(0), is(c));

        Calendar c2 = Calendar.getInstance();
        c2.set(Calendar.YEAR, 2100);
        list.add(c2);
        assertThat(list.get(1), is(c2));
    }

    @Test
    public void testGetFirst() {
        Calendar c = Calendar.getInstance();
        list.add(c);
        assertThat(list.get(0), is(list.getFirst()));
    }

    @Test
    public void testGetLast() {
        GenericList<Integer> list = new GenericList<>();
        List<Integer> t = Arrays.asList(1, 2, 3, 4, 5, 6);
        list.addAll(t);

        assertThat(list.getLast(), is(6));
    }

    @Test
    public void testAddE() {
        Calendar c = Calendar.getInstance();
        list.add(c);
        assertThat((Calendar) list.parameter[0], is(c));
    }

    @Test
    public void testAddIntE() {
        Calendar c = Calendar.getInstance();
        list.add(5, c);
        assertThat((Calendar) list.parameter[5], is(c));
    }

    @Test
    public void testSetIntE() {
        Calendar c = Calendar.getInstance();
        list.set(5, c);
        assertThat((Calendar) list.parameter[5], is(c));
    }

    @Test
    public void testRemoveInt() {
        Calendar c = Calendar.getInstance();
        list.add(c);
        assertThat(list.get(0), is(c));

        Calendar c2 = Calendar.getInstance();
        c2.set(Calendar.YEAR, 2100);
        list.add(c2);
        list.remove(0);

        assertThat(list.get(0), is(c2));
    }

    @Test
    public void testAddAllIntCollectionOfQextendsE() {
        GenericList<Integer> list = new GenericList<>();
        List<Integer> t = Arrays.asList(1, 2, 3, 4, 5, 6);
        list.addAll(1, t);

        assertThat(list.get(0), is((Integer) null));
        for (int i = 0; i < t.size(); i++) {
            assertThat(list.get(i + 1), is(t.get(i)));
        }
    }

    @Test
    public void testAddAllCollectionOfQextendsE() {
        GenericList<Integer> list = new GenericList<>();
        List<Integer> t = Arrays.asList(1, 2, 3, 4, 5, 6);
        list.addAll(t);

        for (int i = 0; i < t.size(); i++) {
            assertThat(list.get(i), is(t.get(i)));
        }
    }

    @Test
    public void testSubListIntInt() {
        GenericList<Integer> list = new GenericList<>();
        List<Integer> t = Arrays.asList(1, 2, 3, 4, 5, 6);
        list.addAll(t);

        List<Integer> sList = list.subList(3, 4);

        assertThat(sList.toString(), is(Arrays.asList(4, 5).toString()));
    }

}
Twitter: @asahina_alice