2015-06に記述,JavaのListの独自実装

MyList.java

import java.util.*;
import java.util.function.*;
import java.util.stream.*;

public class MyList<E extends Comparable<E>> implements List<E>
{
    public static void main(String[] args)
    {
        // MyList クラスのテスト
        List<String> list = new MyList<String>();
        //#1. 引数無しコンストラクター
        list.add("banana");
        //#2. add(E) メソッド
        list.add(0, "apple");
        //#3. add(int,E) メソッド
        System.out.println(list);
        //#4. toString() メソッド -> [apple, banana]
        assert list.equals(new MyList<>(Arrays.asList("apple", "banana")));

        List<String> list2 = new MyList<String>(list);
        //#5. 引数有りコンストラクター(要素の実態をコピー)
        System.out.println(list2.size());
        //#6. size() メソッド -> 2
        assert list2.size() == 2;

        list.remove(0);
        //#7. remove(int) メソッド
        System.out.println(list2.get(0));
        //#8. get(int) メソッド -> apple
        assert list2.get(0) == "apple";

        list2.add("cherry");
        System.out.println(list2.subList(1, 3));
        //#9. subList(int,int) メソッド -> [banana, cherry]
        assert list2.subList(1,3).equals(new MyList<>(Arrays.asList("banana", "cherry")));

        list.clear();
        //#10. clear() メソッド
        System.out.println(list.isEmpty());
        //#11. isEmpty() メソッド -> true
        assert list.isEmpty(): list;

        list2.set(1, "durian");
        //#12. set(int,E) メソッド
        System.out.println(list2.contains("banana"));
        //#13. contains(Object) メソッド -> false
        assert list2.contains("banana") == false;

        System.out.println(list2.indexOf("banana"));
        //#14. indexOf(E) メソッド -> -1
        assert list2.indexOf("banana") == -1;

        Object[] array = list2.toArray();
        //#15. toArray() メソッド
        for(int i = 0; i < array.length; i++)
        {
            System.out.println(i + ":" + array[i]);
            //# -> 0:apple↵ 1:durian↵ 2:cherry
        }
        list = new MyList<String>(list2);
        System.out.println(list == list2);
        //# -> false
        assert (list == list2) == false;

        System.out.println(list.equals(list2));
        //#16. equals(Object) メソッド
        assert list.equals(list2);

        // test by ne260258
        {
            MyList<String> l0 = new MyList<>(Arrays.asList("a", "b", "c", "d"));
            l0.subList(1, 3).clear();
            System.out.println(l0);
            assert l0.equals(new MyList<>(Arrays.asList("a", "d"))): l0;
        }

        {
            MyList<String> r0 = new MyList<>(Arrays.asList("a", "b", "a", "b", "b"));
            r0.removeAll(Arrays.asList("b"));
            System.out.println(r0);
            assert r0.equals(Arrays.asList("a", "a")) : r0;
        }

        {
            MyList<String> r1 = new MyList<>(Arrays.asList("a", "b", "a", "b", "b"));
            r1.removeAll(Arrays.asList("a"));
            System.out.println(r1);
            assert r1.equals(Arrays.asList("b", "b", "b")) : r1;
        }
        // sort test
        {
            MyList<Integer> toBeSorted = new MyList<>(Arrays.asList(3, 4, 0, 2, 1));
            toBeSorted.sort();
            System.out.println(toBeSorted);
            assert toBeSorted.equals(Arrays.asList(0, 1, 2, 3, 4)) : toBeSorted;
        }
        // sort pred test
        {
            MyList<Integer> toBeSorted = new MyList<>(Arrays.asList(5, 4, 3, 1, 2));
            // 1以下で表示して終了する
            toBeSorted.sort((e) ->
                            {
                                if(new Integer(1).compareTo(e) <= 0)
                                {
                                    System.out.println("min limit over:" + e); // エラー値を表示
                                    return null; // 今回は修正しない
                                }
                                else
                                {
                                    return e; // 正常値はそのまま返す
                                }
                            });
        }
        // sort exception test
        {
            MyList<Integer> toBeSorted = new MyList<>(Arrays.asList(5, 4, 3, 1, 2));
            // 1以下で表示して終了する
            try
            {
                toBeSorted.sort(1);
            }
            catch(final Exception e)
            {
                System.out.println(e);
            }
        }
    }

    public MyList()
    {
    }

    public MyList(E e)
    {
        this.begin = new Node<E>(e);
        this.rbegin = this.begin;
    }

    public MyList(Collection<? extends E> c)
    {
        c.stream().forEach(this::add);
    }

    private MyList(Node<E> l, Node<E> r)
    {
        this.begin = l;
        this.rbegin = r;
    }

    public boolean add(E e)
    {
        this.addLast(e);
        return true;
    }

    public void add(int index, E element)
    {
        Node<E> l = this.getNode(index - 1);
        if(l == null)
        {
            this.addFirst(element);
        }
        else if(l == this.rbegin)
        {
            this.addLast(element);
        }
        else
        {
            Node.link(l, new Node<E>(element), l.tail);
        }
    }

    public void addFirst(E e)
    {
        if(this.begin == null)  // cons的な方式だと両端リストには対応できないので,nullチェックが必要
        {
            this.begin = new Node<E>(e);
            this.rbegin = this.begin;
        }
        else
        {
            this.begin = Node.link(this.begin.prev, new Node<E>(e), this.begin);
        }
    }

    public void addLast(E e)
    {
        if(this.begin == null)
        {
            this.begin = new Node<E>(e);
            this.rbegin = this.begin;
        }
        else
        {
            this.rbegin = Node.link(this.rbegin, new Node<E>(e), this.rbegin.tail).tail;
        }
    }

    public boolean addAll(Collection<? extends E> c)
    {
        c.stream().forEach(this::addLast);
        return (c.isEmpty()) ? false : true;
    }

    public boolean addAll(int index, Collection<? extends E> c)
    {
        return index !=
            c.stream().reduce(index, (i, e) ->
                              {
                                  this.add(i, e);
                                  return index + 1;
                              },
                              (il, ir) -> il + ir);
    }

    public void clear()
    {
        IntStream.range(0, this.size()).forEach(n -> this.removeFirst());
    }

    public boolean contains(Object o)
    {
        return this.stream().anyMatch(e -> e == null ? o == null : e.equals(o));
    }

    public boolean containsAll(Collection<?> c)
    {
        return c.stream().allMatch(this::contains);
    }

    @SuppressWarnings("unchecked") // 例外はcatchするので問題ない
    public boolean equals(Object o)
    {
        try
        {
            // 規約によると,ListはListとのみ等しくなる
            for(ListIterator<E> ti = this.listIterator(), oi = ((List<E>)o).listIterator();
                ti.hasNext() || oi.hasNext();)
            {
                if(ti.next() != oi.next())
                {
                    return false;
                }
            }
            return true;
        }
        catch(RuntimeException e)
        {
            return false;
        }
    }

    public E get(int index)
    {
        return this.getNode(index).head;
    }

    public int hashCode()
    {
        return this.stream().reduce(1, (l, r) -> 31 * l + r.hashCode(), (a, b) -> a + b);
    }

    public int indexOf(Object o)
    {
        int index = 0;
        for(ListIterator<E> it = this.listIterator(); it.hasNext(); ++index)
        {
            final E e = it.next();
            if((o == null && e == null) || o.equals(e))
            {
                return index;
            }
        }
        return -1;              // List規約: 見つからなければ-1
    }

    public int lastIndexOf(Object o)
    {
        int index = this.size() - 1;
        for(ListIterator<E> it = this.listIterator(this.size() - 1); it.hasPrevious(); --index)
        {
            final E e = it.previous();
            if((o == null && e == null) || o.equals(e))
            {
                return index;
            }
        }
        return -1;              // List規約: 見つからなければ-1
    }

    public boolean isEmpty()
    {
        return this.begin == null;
    }

    public Iterator<E> iterator()
    {
        return this.listIterator();
    }

    public ListIterator<E> listIterator()
    {
        return this.listIterator(0);
    }

    public ListIterator<E> listIterator(int index)
    {
        return this.begin == null ?
            new MyListIterator<E>(index, null, null, null):
            new MyListIterator<E>(index, this.getNode(index), this.begin, this.rbegin.tail);
    }

    public E remove(int index)
    {
        Node<E> removeTarget = this.getNode(index);
        if(removeTarget == this.begin)
        {
            return removeFirst();
        }
        else if(removeTarget == this.rbegin)
        {
            return removeLast();
        }
        else
        {
            E result = removeTarget.head;
            Node.link(removeTarget.prev, removeTarget.tail);
            return result;
        }
    }

    public E removeFirst()
    {
        E removedElement = this.begin.head;
        Node.link(this.begin.prev, this.begin.tail);
        this.begin = this.begin.tail;
        return removedElement;
    }

    public E removeLast()
    {
        E removedElement = this.rbegin.head;
        Node.link(this.rbegin.prev, this.rbegin.tail);
        this.rbegin = this.rbegin.prev;
        return removedElement;
    }

    public boolean remove(Object o)
    {
        Node<E> e = this.begin;
        if(e.head.equals(o))    // first
        {
            this.removeFirst();
            return true;
        }
        for(e = e.tail; e != this.rbegin; e = e.tail)
        {
            if(e.head.equals(o))
            {
                Node.link(e.prev, e.tail);
                return true;
            }
        }
        if(e.head.equals(o))    // last
        {
            this.removeLast();
            return true;
        }
        return false;
    }

    @SuppressWarnings("unchecked") // 例外発生までがListの仕様
    public boolean removeAll(Collection<?> c)
    {
        boolean changed = false;
        for(ListIterator<E> eit = this.listIterator(); eit.hasNext();)
        {
            if(c.contains(eit.next()))
            {
                eit.remove();
                changed = true;
            }
        }
        return changed;
    }

    @SuppressWarnings("unchecked") // 例外発生までがListの仕様
    public boolean retainAll(Collection<?> c)
    {
        boolean changed = false;
        for(ListIterator<E> eit = this.listIterator(); eit.hasNext();)
        {
            if(!c.contains(eit.next()))
            {
                eit.remove();
                changed = true;
            }
        }
        return changed;
    }

    public E set(int index, E element)
    {
        Node<E> resetNode = this.getNode(index);
        E resetElement = resetNode.head;
        resetNode.head = element;
        return resetElement;
    }

    public int size()
    {
        return this.begin == null ? 0 : this.begin.distance(this.rbegin);
    }

    public List<E> subList(int fromIndex, int toIndex)
    {
        return new MyList<E>(this.getNode(fromIndex), this.getNode(toIndex - 1));
    }

    public Object[] toArray()
    {
        Object[] array = new Object[this.size()];
        int i = 0;
        for(ListIterator it = this.listIterator(); it.hasNext(); ++i)
        {
            array[i] = (Object)(it.next());
        }
        return array;
    }

    @SuppressWarnings("unchecked") // 例外発生許容
    public <T> T[] toArray(T[] a)
    {
        if(this.size() <= a.length)
        {
            int i = 0;
            for(ListIterator<E> it = this.listIterator(); it.hasNext(); ++i)
            {
                a[i] = (T)(it.next());
            }
            for(; i < a.length; ++i) // Listの規約: 残りはnull埋めする
            {
                a[i] = null;
            }
            return a;
        }
        else
        {
            Object[] array = new Object[this.size()];
            int i = 0;
            for(ListIterator it = this.listIterator(); it.hasNext(); ++i)
            {
                array[i] = (T)(it.next());
            }
            return (T[])array;
        }
    }

    public String toString()
    {
        StringBuilder acc = new StringBuilder("[");
        ListIterator<E> it = this.listIterator();
        if(it.hasNext())
        {
            acc.append(it.next());
        }
        while(it.hasNext())
        {
            acc.append(", ");
            acc.append(it.next());
        }
        acc.append("]");
        return acc.toString();
    }

    public void sort() {
        if (this.size() < 2) return;
        MyList<E> left = new MyList<E>(this.subList(0, this.size() / 2)); // リストの左半分を格納
        MyList<E> right = new MyList<E>(this.subList(this.size() / 2, this.size())); // リストの右半分を格納
        left.sort(); // 左半分をソート(再帰)
        right.sort(); // 右半分をソート(再帰)
        this.clear(); // 自分自身のリストはマージのために一旦クリアする
        while(true) { // ループ終了はbreakで行う
            MyList<E> target = left.get(0).compareTo(right.get(0)) < 0 ? left : right; // 左端が小さい(比較基準で)方のリストをtargetと命名
            this.add(target.get(0)); // 小さい方の左端をthisにコピー
            target.remove(0); // コピー元から消去
            if (target.size() == 0) break; // どちらかが空になればループを抜ける
        }

        MyList<E> leftover = left.size() > 0 ? left :right; // 空ではないリストをleftoverと命名
        while (leftover.size() > 0) { // leftoverが空になるまでループ
            this.add(leftover.get(0)); // leftoverからthisに要素をコピー
            leftover.remove(0); // コピー元から消去
        }
        return;
    }

    /**
     * @param fmapMaybe 値を修正する関数.許容しないならnullを返す
     */
    public void sort(final Function<E, E> fmapMaybe) {
        if (this.size() < 2) return;
        MyList<E> left = new MyList<E>(this.subList(0, this.size() / 2)); // リストの左半分を格納
        MyList<E> right = new MyList<E>(this.subList(this.size() / 2, this.size())); // リストの右半分を格納
        left.sort(); // 左半分をソート(再帰)
        right.sort(); // 右半分をソート(再帰)
        this.clear(); // 自分自身のリストはマージのために一旦クリアする
        while(true) { // ループ終了はbreakで行う
            MyList<E> target = left.get(0).compareTo(right.get(0)) < 0 ? left : right; // 左端が小さい(比較基準で)方のリストをtargetと命名
            E toBeInserted = fmapMaybe.apply(target.get(0)); // 複数回参照するため名前をつける

            if(toBeInserted == null) // nullは許容しない
            {
                return;
            }
            else
            {
                this.add(toBeInserted); // 小さい方の左端をthisにコピー
                target.remove(0); // コピー元から消去
                if (target.size() == 0) break; // どちらかが空になればループを抜ける
            }
        }

        MyList<E> leftover = left.size() > 0 ? left :right; // 空ではないリストをleftoverと命名
        while (leftover.size() > 0) { // leftoverが空になるまでループ
            this.add(leftover.get(0)); // leftoverからthisに要素をコピー
            leftover.remove(0); // コピー元から消去
        }
        return;
    }

    public void sort(final E minLimit) {
        if (this.size() < 2) return;
        MyList<E> left = new MyList<E>(this.subList(0, this.size() / 2)); // リストの左半分を格納
        MyList<E> right = new MyList<E>(this.subList(this.size() / 2, this.size())); // リストの右半分を格納
        left.sort(); // 左半分をソート(再帰)
        right.sort(); // 右半分をソート(再帰)
        this.clear(); // 自分自身のリストはマージのために一旦クリアする
        while(true) { // ループ終了はbreakで行う
            MyList<E> target = left.get(0).compareTo(right.get(0)) < 0 ? left : right; // 左端が小さい(比較基準で)方のリストをtargetと命名
            E toBeInserted = target.get(0); // 複数回参照するため名前をつける
            if(minLimit.compareTo(toBeInserted) <= 0) // 指定された値以下なら例外送出
            {
                throw new RuntimeException("min limit over:" + toBeInserted.toString());
            }
            else
            {
                this.add(toBeInserted); // 小さい方の左端をthisにコピー
                target.remove(0); // コピー元から消去
                if (target.size() == 0) break; // どちらかが空になればループを抜ける
            }
        }

        MyList<E> leftover = left.size() > 0 ? left :right; // 空ではないリストをleftoverと命名
        while (leftover.size() > 0) { // leftoverが空になるまでループ
            this.add(leftover.get(0)); // leftoverからthisに要素をコピー
            leftover.remove(0); // コピー元から消去
        }
        return;
    }

    private Node<E> getNode(int index)
    {
        if(this.begin == null)
        {
            throw new IndexOutOfBoundsException();
        }
        return this.begin.get(index);
    }

    private Node<E> begin;
    private Node<E> rbegin;
}

final class Node<E>
{
    public Node(E h)
    {
        this.head = h;
    }

    public Node(Node<E> take)
    {
        this.head = take.head;
        this.tail = take.tail;
        this.prev = take.prev;
    }

    public Node<E> get(int distance)
    {
        if(0 <= distance)
        {
            Node<E> result = this;
            for(int i = 0; i < distance; ++i)
            {
                result = result.tail;
            }
            return result;
        }
        else
        {
            Node<E> result = this;
            for(int i = 0; i < Math.abs(distance); ++i)
            {
                result = result.prev;
            }
            return result;
        }
    }

    public int distance(Node<E> r)
    {
        int distAmount = 0;
        for(Node<E> step = this; step != r; step = step.tail)
        {
            ++distAmount;
        }
        return distAmount + 1;
    }

    public static <E> Node<E> link(Node<E> l, Node<E> r)
    {
        if(l == null && r == null)
        {
            return null;
        }
        else if(l == null)
        {
            r.prev = null;
            return r;
        }
        else if(r == null)
        {
            l.tail = null;
            return l;
        }
        else
        {
            l.tail = r;
            r.prev = l;
            return l;
        }
    }

    public static <E> Node<E> link(Node<E> p, Node<E> i, Node<E> n)
    {
        return Node.link(p, Node.link(i, n));
    }

    public E head;
    public Node<E> tail;
    public Node<E> prev;
}

final class MyListIterator<E> implements ListIterator<E>
{
    public MyListIterator(int index, Node<E> next, Node<E> begin, Node<E> end)
    {
        this.index = index;
        this.next = next;
        this.begin = begin;
        this.end = end;
    }

    public void add(E e)
    {
        Node.link(this.next.prev, new Node<E>(e), this.next);
        this.index += 1;
        this.recent = null;
    }

    public boolean hasNext()
    {
        return this.next != end;
    }

    public boolean hasPrevious()
    {
        return this.next != begin;
    }

    public int nextIndex()
    {
        return this.index;
    }

    public int previousIndex()
    {
        return this.index - 1;
    }

    public E next()
    {
        if(!this.hasNext())
        {
            throw new NoSuchElementException();
        }
        this.recent = this.next;
        this.next = this.next.tail;
        this.index += 1;
        return this.recent.head;
    }

    public E previous()
    {
        if(!this.hasPrevious())
        {
            throw new NoSuchElementException();
        }
        this.recent = this.next.prev;
        this.next = this.next.prev;
        this.index -= 1;
        return this.recent.head;
    }

    public void remove()
    {
        if(recent == null)
        {
            throw new IllegalStateException();
        }
        if(this.recent != this.next) // 前回実行はnext
        {
            this.index -= 1;
        }
        Node.link(this.recent.prev, this.recent.tail);
        this.recent = null;
    }

    public void set(E e)
    {
        if(recent == null)
        {
            throw new IllegalStateException();
        }
        this.recent.head = e;
        this.recent = null;
    }

    private int index;
    private Node<E> next;
    private Node<E> begin;
    private Node<E> end;

    private Node<E> recent;
}