Algorithmen & Datenstrukturen mit Java: Beispielklasse für Mengen als verkettete Listen

Set	Schnittstelle

package ds.interfaces;
/** Simple interface for sets */
import java.util.Iterator;
import ds.util.Invariant;
import ds.util.E;  // example class for elements
public
    interface Set
    extends Iterable<E>,
            Invariant {
    boolean isEmpty();
    boolean member(E e);
    int     size();
    E       findMin();
    E       findMax();
    Set     insert(E e);
    Set     remove(E e);
    Set     union(Set m2);
    Set     difference(Set m2);
    Set     intersect(Set m2);
    Set     copy();
    // inherited
    // Iterator<E> iterator();
    // boolean inv();
}

Set	implementiert als sortierte einfach verkettete Liste
	gleiche Datenstruktur wie bei List als verkettete Liste
	ohne Generics
	persistente Implementierung
	destruktive Implementierung in Kommentar

package ds.persistent.set;
/** Implementation of sets with ordered single linked lists.
    Ordered linked lists require a total ordering
    on the elem domain.
    This is a PERSISTENT implementation.
*/
import ds.interfaces.Set;
import ds.util.E;          // example class for elements
import ds.util.Invariant;
import java.util.Iterator;
import static java.lang.Integer.signum;
import static ds.util.Undef.undefined;
public abstract
    class OrderedList
    implements Set {
    //----------------------------------------
    // the smart constructors
    // empty list
    public static OrderedList empty() {
        return
            EMPTY;
    }
    // singleton list
    public static OrderedList singleton(E e) {
        return
            EMPTY.cons(e);
    }
    // build search tree from arbitrary sequence (iterator)
    public static
        OrderedList fromIterator(Iterator<E> elems) {
        OrderedList res = empty();
        while ( elems.hasNext() ) {
            E e = elems.next();
            res = res.insert(e);
        }
        return
            res;
    }
    public abstract OrderedList insert(E e);
    public abstract OrderedList remove(E e);
    public abstract OrderedList union(Set m2);
    public abstract OrderedList intersect(Set m2);
    public abstract OrderedList difference(Set m2);
    public Iterator<E> iterator() {
        ++cntIter;
        return
            new ListIterator(this);
    }
    public OrderedList copy() {
        return
            this;
    }
    //----------------------------------------
    // internal methods
    // cons
    protected Node cons(E e) {
        return
            new Node(e, this);
    }
    // access methods, only legal for Node objects
    // not defined for Empty object
    Node        node() { return nodeExpected(); }
    E           elem() { return nodeExpected(); }
    OrderedList next() { return nodeExpected(); }
    private static <A> A nodeExpected() {
        return
            undefined("Node expected");
    }  
    //----------------------------------------
    // the empty list implemented by applying the singleton design pattern
    // the empty list object
    private static final OrderedList EMPTY
        = new Empty();
    // the singleton class for the empty list object
    private static final
        class Empty
        extends OrderedList {
        public boolean isEmpty() {
            return true;
        }
        public boolean member(E e) {
            return false;
        }
        public int size() {
            return 0;
        }
        public E findMin() {
            nodeExpected();
            return null;
        }
  
        public E findMax() {
            nodeExpected();
            return null;
        }
        public OrderedList insert(E e) {
            return
                singleton(e);
        }
        public OrderedList remove(E e) {
            return
                this;
        }
        public OrderedList union(Set m2) {
            return
                (OrderedList)m2;
        }
        public OrderedList intersect(Set m2) {
            return
                this;
        }
        public OrderedList difference(Set m2) {
            return
                this;
        }
        public boolean inv() {
            return true;
        }
        //----------------------------------------
        // not public stuff
        Empty() { }
    }
    
    //----------------------------------------
    // the node class for none empty trees
    private static final
        class Node
        extends OrderedList {
        /* persistent */
        final E           e;
        final OrderedList next;
        /* destructive *
        E           e;
        OrderedList next;
        /**/
        Node(E e, OrderedList next) {
            assert e    != null;
            assert next != null;
            this.e    = e;
            this.next = next;
            ++cntNode;
        }
        //----------------------------------------
        // predicates and attributes
        public boolean isEmpty() {
            return false;
        }
        public boolean member(E e) {
            assert e != null;
            switch (signum(e.compareTo(this.e))) {
            case -1:
                return
                    false;
            case 0:
                return
                    true;
            case +1:
                return
                    next.member(e);
            }
            // never executed, but required by javac
            return
                false;
        }
        public int size() {
            return
                1 + next.size();
        }
        public E findMin() {
            return e;
        }  
        public E findMax() {
            if ( next.isEmpty() )
                return e;
            return
                next.findMax();
        }  
        public boolean inv() {
            if ( next.isEmpty() )
                return
                    true;
            return
                e.compareTo(next.elem()) < 0
                &&
                next.inv();
        }
        //----------------------------------------
        // internal methods
        Node        node() { return this; }
        E           elem() { return e;    }
        OrderedList next() { return next; }
        // setter
        private Node setNext(OrderedList next) {
            /* persistent */
            if ( next == this.next )
                return
                    this;
            return
                next.cons(this.e);
            /* destructive *
            this.next = next;
            return
                this;
            /**/
        }
        //----------------------------------------
        public OrderedList insert(E e) {
            assert e != null;
            switch ( signum(e.compareTo(this.e)) ) {
            case -1: // add to the front
                return
                    this.cons(e);
            case 0: // already there
                return
                    this;
            case +1: // continue search
                return
                    setNext(next.insert(e));
            }
            // never executed, but required by javac
            return
                null;
        }
    
        public OrderedList remove(E e) {
            assert e != null;
            switch ( signum(e.compareTo(this.e)) ) {
            case -1: // not there: nothing to remove
                return
                    this;
            case 0: // found: remove head of list
                return
                    next;
            case +1: // continue search
                return
                    setNext(next.remove(e));
            }
            // never executed, but required by javac
            return
                null;
        }
        public OrderedList union(Set m2) {
            assert m2 != null;
            OrderedList l2 = (OrderedList)m2;
            if ( l2.isEmpty() )
                return
                    this;
            Node n2 = l2.node();
            switch ( signum(n2.e.compareTo(this.e)) ) {
            case -1: // add head of m2 to the front of the result
                return
                    n2.setNext(union(n2.next));
            case 0: // same elem, ignore head of m2
                return
                    setNext(next.union(n2.next));
            case +1: // add head to the result and merge tail with m2
                return
                    setNext(next.union(m2));
            }
            // never executed, but required by javac
            return
                null;
        }
        public OrderedList intersect(Set m2) {
            assert m2 != null;
            OrderedList l2 = (OrderedList)m2;
            if ( l2.isEmpty() )
                return
                    l2;
            Node n2 = l2.node();
            switch ( signum(n2.e.compareTo(this.e)) ) {
            case -1: // ignore head of m2
                return
                    intersect(n2.next);
            case 0: // head remains in result
                return
                    setNext(next.intersect(n2.next));
            case +1: // ignore head
                return
                    next.intersect(m2);
            }
            // never executed, but required by javac
            return
                null;
        }
        public OrderedList difference(Set m2) {
            assert m2 != null;
            OrderedList l2 = (OrderedList)m2;
            if ( l2.isEmpty() ) // nothing to do
                return
                    this;
            Node n2 = l2.node();
            switch ( signum(n2.e.compareTo(this.e)) ) {
            case -1: // ignore head of m2
                return
                    difference(n2.next);
            case 0: // same elem, remove elem
                return
                    next.difference(n2.next);
            case +1: // take head as it is and continue
                return
                    setNext(next.difference(m2));
            }
            // never executed, but required by javac
            return
                null;
        }
        /* destructive *
        public OrderedList copy() {
            return
                next.copy().cons(e);
        }
        /**/
    }
    
    //----------------------------------------
    // iterators
    // ascending enumeration
    private static
        class ListIterator
        extends ds.util.Iterator<E> {
        
        OrderedList queue;
        ListIterator(OrderedList n) {
            assert n != null;
            queue = n;
            ++cntIter;
        }
        public boolean hasNext() {
            return
                ! queue.isEmpty();
        }
        public E next() {
            if ( queue.isEmpty() )
                return
                    undefined("empty list");
            Node n = queue.node();
            queue  = queue.next();
            return
                n.e;
        }
    }
    //----------------------------------------
    // profiling
    private static int cntNode = 0;
    private static int cntIter = 0;
    public static String stats() {
        return
            "stats for ds.persistent.set.OrderedList:\n" +
            "# new Node()               : " + cntNode + "\n" +
            "# new Iterator()           : " + cntIter + "\n";
    }
    public String objStats() {
        int s = size();
        int o = s;
        int f = 2 * s;
        int m = o + f;
        return
            "mem stats for ds.persistent.set.OrderedList object:\n" +
            "# elements (size)      : " + s + "\n" +
            "# objects              : " + o + "\n" +
            "# fields               : " + f + "\n" +
            "# mem words            : " + m + "\n";
    }
}

Quellen
	interface Set
	class OrderedList
	class E
	class Iterator
	class Invariant
	class Undef