Algorithmen & Datenstrukturen mit Java: Beispielklasse für einfach verkettete Ringe

List	implementiert als einfach verketteter Ring
	nur destruktive Implementierung möglich
	ohne Generics
package ds.destructive.list;
/** A linked ring is an efficient implementation
    for FIFO buffers (queues).
    A ring is always a destructive data structure,
    every modifying operation changes some references
    in the LinkedRing objects.
 */
import ds.interfaces.List;
import ds.util.NullIterator;
import ds.util.E;
import java.util.Iterator;
import static ds.util.Undef.undefined;
public abstract class LinkedRing
    implements List {
    //----------------------------------------
    // the smart constructors
    // empty ring
    public static LinkedRing empty() {
        return
            EMPTY;
    }
    // singleton ring
    public static LinkedRing singleton(E e) {
        return
            new Node(e);
    }
    // list from iterator
    public static LinkedRing fromIterator(Iterator<E> elems) {
        LinkedRing acc = empty();
        while ( elems.hasNext() ) {
            E info = elems.next();
            acc = acc.append(info);
        }
        return
            acc;
    }
    //----------------------------------------
    public boolean inv() {
        return
            true;
    }
    public abstract LinkedRing concat(List l2);
    public LinkedRing append(E e) {
        return
            this.concat(singleton(e));
    }
    public LinkedRing cons(E e) {
        return
            singleton(e).concat(this);
    }
    //----------------------------------------
    // generally usable methods
    // working with iterators
    public E at(int i) {
        Iterator<E> xs = iterator();
        while ( i != 0 ) {
            xs.next();
            --i;
        }
        return
            xs.next();
    }
    public boolean member(E e) {
        for (E x : this)
            if ( e.equalTo(x) )
                return
                    true;
        return
            false;
    }
    public int length() {
        int res = 0;
        for (E x : this)
            ++res;
        return
            res;
    }
    public LinkedRing copy() {
        LinkedRing res = empty();
        for (E x : this)
            res = res.append(x);
        return
            res;
    }
    public String toString() {
        return
            iterator().toString();
    }
    //----------------------------------------
    // the empty ring
    // the "generic" empty ring object
    private static final LinkedRing EMPTY
        = new Empty();
    // the singleton class for the empty list object
    private static final
        class Empty
        extends LinkedRing {
        public boolean isEmpty() {
            return true;
        }
        public boolean member(E e) {
            return false;
        }
        public int length() {
            return 0;
        }
        public E head() {
            return
                undefined("head of empty list");
        }
        public LinkedRing tail() {
            return
                undefined("tail of empty list");
        }
        public E last() {
            return
                undefined("last of empty list");
        }
        public LinkedRing init() {
            return
                undefined("init of empty list");
        }
        public LinkedRing concat(List l2) {
            // only linked rings are allowed for l2
            return
                (LinkedRing)l2;
        }
        public LinkedRing reverse() {
            return
                this;
        }
        public LinkedRing copy() {
            return
                this;
        }
        public Iterator<E> iterator() {
            ++cntIter;
            return
                new NullIterator<E>();
        }
        //----------------------------------------
        // not public stuff
        Empty() { }
    }
    // downcast from LinkedRing to Node
    Node node() {
        return
            undefined("Node expected");
    }
    //----------------------------------------
    // the none empty list class
    private static final
        class Node
        extends LinkedRing {
        public boolean isEmpty() {
            return false;
        }
        public E head() {
            return
                next.info;
        }
        public LinkedRing tail() {
            if ( next == this ) // singleton ring
                return
                    empty();
            next = next.next;
            return
                this;
        }
        public E last() {
            return
                info;
        }
        public LinkedRing init() {
            if ( next == this ) // singleton ring
                return
                    empty();
            // search the node in front of this
            Node cur = this.next.node();
            while ( cur.next != this ) {
                cur = cur.next.node();
            }
            cur.next = this.next;
            return
                cur;
        }
        public LinkedRing concat(List l2) {
            // only linked rings are allowed for l2
            LinkedRing r2 = (LinkedRing)l2;
            if ( r2.isEmpty() )
                return
                    this;
            Node n2   = r2.node();
            Node  t   = n2.next;
            n2  .next = next;
            this.next = t;
            return
                n2;
        }
        public LinkedRing reverse() {
            Node cur = this.next.node();
            Node prv = this;
            while ( cur != this ) {
                Node tmp = cur.next.node();
                cur.next = prv;
                prv      = cur;
                cur      = tmp;
            }
            Node res = this.next;
            this.next = prv;
            return
                res;
        }
        public Iterator<E> iterator() {
            ++cntIter;
            return
                new NodeIterator(this);
        }
        //----------------------------------------
        // not public stuff
        private E    info;
        private Node next;
        Node(E e) {
            info = e;
            next = this;
            ++cntNode;
        }
        // downcast from LinkedRing to Node
        Node node() {
            return this;
        }
        // iterator for none empty rings
        private static final
            class NodeIterator
            extends ds.util.Iterator<E> {
            Node    r;
            Node    cur;
            boolean first;
            NodeIterator(Node r) {
                this.r     = r;
                this.cur   = r;
                this.first = true;
            }
            public boolean hasNext() {
                return
                    first || r != cur;
            }
            public E next() {
                if ( ! hasNext() )
                    return
                        undefined("ring exhausted");
                first = false;
                cur   = cur.next;
                return
                    cur.info;
            }
        }
    }
    //----------------------------------------
    // profiling
    private static int cntNode = 0;
    private static int cntIter = 0;
    public static String stats() {
        return
            "stats for ds.destructive.list.LinkedRing:\n" +
            "# new Node()         : " + cntNode + "\n" +
            "# new ListIterator() : " + cntIter + "\n";
    }
}
Quellen
	interface List
	class LinkedRing
	class E
	class Iterator
	class NullIterator
	class Invariant
	class Undef
Beispielklasse für einfach verkettete Ringe

LinkedRing.java
