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

Map	Schnittstelle (sehr einfach gehalten)

package ds.interfaces;
/** Simple interface for maps
 */
import java.util.Iterator;
import ds.util.Invariant;
import ds.util.Function2;
import ds.util.K;  // example class for keys
import ds.util.V;  // example class for values
import ds.util.KV; // key value pair
public
    interface Map
    extends Iterable<KV>,
            Invariant {
    boolean isEmpty();
    boolean member(K k);
    V       lookup(K k);
    int     size();
    KV      findMin();
    KV      findMax();
    Map     insert(K k, V v);
    Map     remove(K k);
    Map     union(Map m2);
    Map     difference(Map m2);
    Map     unionWith(Function2<V,V,V> op, Map m2);
    Map     differenceWith(Function2<V,V,V> op, Map m2);
    Map     copy();
    // inherited
    // public Iterator<KV> iterator();
    // public inv();
}

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

package ds.persistent.map;
/** Implementation of maps with ordered single linked lists.
    Ordered linked lists require a total ordering
    on the key value. This is reflected by the
    constraint on the type variable K.
    This is a PERSISTENT implementation.
*/
import ds.interfaces.Map;
import ds.util.K;  // example class for keys
import ds.util.V;  // example class for values
import ds.util.KV; // key value pair
import static ds.util.KV.mkPair;
import ds.util.Function2;
import ds.util.Invariant;
import ds.util.NullIterator;
import ds.util.Pair;
import ds.util.Predicate;
import java.util.Iterator;
import static java.lang.Integer.signum;
import static ds.util.Undef.undefined;
//----------------------------------------
public abstract
    class OrderedList
    implements Map {
    //----------------------------------------
    // the smart constructors
    // empty list
    public static OrderedList empty() {
        return
            EMPTY;
    }
    // singleton list
    public static OrderedList singleton(K k, V v) {
        return
            EMPTY.cons(k, v);
    }
    // build search tree from arbitrary sequence (iterator)
    public static
        OrderedList fromIterator(Iterator<KV> elems) {
        OrderedList res = empty();
        while ( elems.hasNext() ) {
            KV p = elems.next();
            res = res.insert(p.fst, p.snd);
        }
        return
            res;
    }
    public boolean member(K k) {
        return
            lookup(k) != null;
    }
    public abstract OrderedList
        insert(K k, V v);
    public abstract OrderedList
        remove(K k);
    public OrderedList
        union(Map m2) {
        return
            unionWith(const2, m2);
    }
    public abstract OrderedList
        unionWith(Function2<V,V,V> op,
                  Map m2);
    public OrderedList
        difference(Map m2) {
        return
            differenceWith(null2, m2);
    }
    public abstract OrderedList
        differenceWith(Function2<V,V,V> op,
                       Map m2);
    public OrderedList copy() {
        return
            this;
    }
    //----------------------------------------
    // internal methods
    // getter
    Node        node()  { return nodeExpected(); }
    K           key()   { return nodeExpected(); }
    V           value() { return nodeExpected(); }
    OrderedList next()  { return nodeExpected(); }
    private static <A> A nodeExpected() {
        return
            undefined("Node expected");
    }  
    // cons
    protected
        Node cons(K k, V v) {
        return
            new Node(k, v, this);
    }
    private static Function2<V,V,V> const2
        = new Function2<V,V,V>() {
        public V apply(V x, V y) {
            return y;
        }
    };
    private static Function2<V,V,V> null2
        = new Function2<V,V,V>() {
        public V apply(V x, V y) {
            return null;
        }
    };
    //----------------------------------------
    // the empty list implemented by applying
    // the singleton design pattern
    // the "generic" 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 {
        // predicates and attributes
        public boolean isEmpty() {
            return true;
        }
        public int size() {
            return 0;
        }
        public V lookup(K k) {
            return null;
        }
        public KV findMin() {
            return nodeExpected();
        }
  
        public KV findMax() {
            return nodeExpected();
        }
  
        public boolean inv() {
            return true;
        }
        public Iterator<KV> iterator() {
            ++cntIter;
            return
                new NullIterator<KV>();
        }
        // tree manipulation
        public OrderedList insert(K k, V v) {
            return
                singleton(k, v);
        }
        public OrderedList remove(K k) {
            return
                this;
        }
        public OrderedList
            unionWith(Function2<V,V,V> op,
                      Map m2) {
            return
                (OrderedList)m2;
        }
        public OrderedList
            differenceWith(Function2<V,V,V> op,
                           Map m2) {
            return
                this;
        }
        //----------------------------------------
        // not public stuff
        Empty() { }
    }
    
    //----------------------------------------
    // the node class for none empty trees
    private static final
        class Node
        extends OrderedList {
        /* persistent */
        final K           k;
        final V           v;
        final OrderedList next;
        /* destructive *
           K           k;
           V           v;
           OrderedList next;
           /**/
        Node(K k, V v, OrderedList next) {
            assert k != null;
            this.k    = k;
            this.v    = v;
            this.next = next;
            ++cntNode;
        }
        //----------------------------------------
        // predicates and attributes
        public boolean isEmpty() {
            return false;
        }
        public int size() {
            return
                1 + next.size();
        }
        public V lookup(K k) {
            assert k != null;
            switch ( signum(k.compareTo(this.k)) ) {
            case -1:
                return
                    null; // not found
            case 0:
                return
                    v;
            case +1:
                return
                    next.lookup(k);
            }
            // never executed, but required by javac
            return
                null;
        }
        public KV findMin() {
            return
                mkPair(k, v);
        }  
        public KV findMax() {
            if ( next.isEmpty() )
                return
                    mkPair(k, v);
            return
                next.findMax();
        }  
        public Iterator<KV> iterator() {
            ++cntIter;
            return
                new NodeIterator(this);
        }
        public boolean inv() {
            if ( next.isEmpty() )
                return
                    true;
            return
                k.compareTo(next.key()) < 0
                &&
                next.inv();
        }
        //----------------------------------------
        // internal methods
        // getter
        Node        node()  { return this; }
        K           key()   { return k;    }
        V           value() { return v;    }
        OrderedList next()  { return next; }
        // setter
        private Node setNext(OrderedList next) {
            /* persistent */
            if ( next == this.next )
                return
                    this;
            return
                next.cons(this.k, this.v);
            /* destructive *
               this.next = next;
               return
               this;
               /**/
        }
        private Node setV(V v) {
            /* persistent */
            return
                ( v == this.v )
                ? this
                : next.cons(this.k, v);
            /* destructive *
               this.v = v;
               return
               this;
               /**/
        }
        //----------------------------------------
        // tree manipulation
        public OrderedList insert(K k, V v) {
            assert k != null;
            switch ( signum(k.compareTo(this.k)) ) {
            case -1: // add to the front
                return
                    this.cons(k, v);
            case 0: // already there: update value
                return
                    setV(v);
            case +1: // continue search
                return
                    setNext(next.insert(k, v));
            }
            // never executed, but required by javac
            return
                null;
        }
    
        public OrderedList remove(K k) {
            assert k != null;
            switch ( signum(k.compareTo(this.k)) ) {
            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(k));
            }
            // never executed, but required by javac
            return
                null;
        }
        public OrderedList
            union(Map m2) {
            return
                unionWith(const2, m2);
        }
        public OrderedList
            unionWith(Function2<V,V,V> op,
                      Map m2) {
            if ( m2.isEmpty() )
                return
                    this;
            Node n2 = ((OrderedList)m2).node();
            switch ( signum(n2.k.compareTo(this.k)) ) {
            case -1: // add head of m2 to the front of the result
                return
                    n2.setNext(unionWith(op, n2.next));
            case 0: // same key, ignore head of m2
                return
                    setV(op.apply(v, n2.v)).setNext(next.unionWith(op, n2.next));
            case +1: // add head to the result and merge tail with m2
                return
                    setNext(next.unionWith(op, m2));
            }
            // never executed, but required by javac
            return
                null;
        }
        public OrderedList
            differenceWith(Function2<V,V,V> op,
                           Map m2) {
            if ( m2.isEmpty() )
                return // nothing to do
                    this;
            Node n2 = ((OrderedList)m2).node();
            switch ( signum(n2.k.compareTo(this.k)) ) {
            case -1: // ignore head of m2
                return
                    unionWith(op, n2.next);
            case 0: // same key, combine values or remove key
                V                      v1 = op.apply(v, n2.v);
                OrderedList l1 = next.unionWith(op, n2.next);
                if ( v1 == null )
                    return // remove key
                        l1;
                return // update value and next
                    setV(v1).setNext(l1);
            case +1: // take head as it is and continue
                return
                    setNext(next.unionWith(op, m2));
            }
            // never executed, but required by javac
            return
                null;
        }
        /* destructive *
        public OrderedList copy() {
            return
                next.copy().cons(k, v);
        }
        /**/
        //----------------------------------------
        // iterators
        // ascending enumeration
        private static
            class NodeIterator
            extends ds.util.Iterator<KV> {
        
            OrderedList queue;
            NodeIterator(Node n) {
                queue = n;
                ++cntIter;
            }
            public boolean hasNext() {
                return
                    ! queue.isEmpty();
            }
            public KV next() {
                if ( queue.isEmpty() )
                    return
                        undefined("empty list");
                Node n = queue.node();
                queue  = queue.next();
                return
                    mkPair(n.k, n.v);
            }
        }
    }
    //----------------------------------------
    // profiling
    private static int cntNode = 0;
    private static int cntIter = 0;
    public static String stats() {
        return
            "stats for ds.persistent.map.OrderedList:\n" +
            "# new Node()               : " + cntNode + "\n" +
            "# new Iterator()           : " + cntIter + "\n";
    }
    public String objStats() {
        int s = size();
        int o = s;
        int f = 3 * s;
        int m = o + f;
        return
            "mem stats for ds.persistent.map.OrderedList object:\n" +
            "# elements (size)      : " + s + "\n" +
            "# objects              : " + o + "\n" +
            "# fields               : " + f + "\n" +
            "# mem words            : " + m + "\n";
    }
}

Quellen
	interface Map
	class OrderedList
	class K
	class V
	class KV
	class Iterator
	class Invariant
	class Undef