Unveränderliche Listen mit wahlfreiem Zugriff in Java

In diesem Artikel hatte ich bereits die Okasaki-Listen mit O(log n) für indizierten Zugriff vorgestellt. Hier zum Vergleich eine Java-Version:

import java.util.Iterator;
import java.util.NoSuchElementException;
import java.util.Stack;

public class RAList<T> implements Iterable<T> {

    private static final RAList EMPTY = new RAList(null, null);
    private final Tree<T> head;
    private final RAList<T> tail;

    private RAList(Tree<T> head, RAList<T> tail) {
        this.head = head;
        this.tail = tail;
    }

    public boolean isEmpty() {
        return this == EMPTY;
    }

    public RAList<T> add(T t) {
        return !isEmpty() && !tail.isEmpty() && head.size == tail.head.size
            ? new RAList(new Tree<T>(t, head, tail.head), tail.tail)
            : new RAList(new Tree<T>(t), this);
    }

    public T head() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return head.t;
    }

    public RAList<T> tail() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return head.size == 1 ? tail
                : new RAList<T>(head.left, new RAList<T>(head.right, tail));
    }

    public T get(int index) {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return index < head.size ? head.get(index) : tail.get(index - head.size);
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        for (T t : this) {
            sb.append(sb.length() == 0 ? '[' : ',').append(t);
        }
        return sb.append(']').toString();
    }

    public static <T> RAList<T> from(T... ts) {
        RAList<T> list = EMPTY;
        for (int i = ts.length - 1; i >= 0; i--) {
            list = list.add(ts[i]);
        }
        return list;
    }
   
    public Iterator<T> iterator() {

        return new Iterator<T>() {

            private RAList<T> list = RAList.this;
            private Iterator<T> treeIterator = isEmpty() ? null : head.iterator();

            public boolean hasNext() {
                if (isEmpty()) {
                    return false;
                } else if (treeIterator.hasNext()) {
                    return true;
                } else if (list.tail.isEmpty()) {
                    return false;
                } else {
                    list = list.tail;
                    treeIterator = list.head.iterator();
                    return true;
                }
            }

            public T next() {
                if (! hasNext()) {
                    throw new NoSuchElementException();
                }
                return treeIterator.next();
            }

            public void remove() {
                throw new UnsupportedOperationException("Not supported.");
            }
        };
    }

    private static class Tree<T> implements Iterable<T> {

        private static Tree EMPTY_TREE = new Tree(null, null, null);

        private final int size;
        private final T t;
        private final Tree<T> left;
        private final Tree<T> right;

        private Tree(T t, Tree<T> left, Tree<T> right) {
            this.t = t;
            this.left = left;
            this.right = right;
            this.size = left == null || right == null ? 0 : 1 + left.size + right.size;
        }

        private Tree(T t) {
            this(t, EMPTY_TREE, EMPTY_TREE);
        }

        private T get(int index) {
            assert (this == EMPTY_TREE || index >= size); //should be avoided by algorithm
            if (index == 0) {
                return t;
            } else if (index < size / 2) {
                return left.get(index - 1);
            } else {
                return right.get(index - (size + 1) / 2);
            }
        }

        public Iterator<T> iterator() {
            return new Iterator<T>() {

                Stack<Tree<T>> trees = new Stack<Tree<T>>();

                {
                    trees.add(Tree.this);
                }

                public boolean hasNext() {
                    return !trees.isEmpty();
                }

                public T next() {
                    if (!hasNext()) {
                        throw new NoSuchElementException();
                    }
                    Tree<T> tree = trees.pop();
                    if (tree.right != EMPTY_TREE) {
                        trees.push(tree.right);
                    }
                    if (tree.left != EMPTY_TREE) {
                        trees.push(tree.left);
                    }
                    return tree.t;
                }

                public void remove() {
                    throw new UnsupportedOperationException("Not supported");
                }
            };
        }
    }
}

Bei der Implementierung habe ich ein wenig gemogelt, EMPTY und EMPTY_TREE sind statische Variablen statt Unterklassen, und deshalb hat sich auch das verpönte null wieder in meinen Code eingeschlichen. Und eine ordentliche Implementierung müsste noch so einiges verbessern (beispielsweise ist eine eigene size-Variable in jedem Baumknoten eine riesige Speicherverschwendung). Aber was soll’s, Hauptsache es funktioniert.