Algorithmen & Datenstrukturen mit Java: Beispielklasse für Verzeichnisse als binäre Suchbäume

Map	Schnittstelle wie bei sortierter Liste

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 binärer Suchbaum
	ohne Generics
	persistente Implementierung
	destruktive Implementierung in Kommentar

package ds.persistent.map;
/** Persistent implementation of binary search treee.
    Operations manipulating trees always create copies
    of the objects to be manipulated. This assures, that
    old trees remains unchanged.
    Binary search trees require a total ordering
    on the key.
*/
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 ds.util.Queue;     // for iterators
import ds.util.Function2;
import ds.util.NullIterator;
import static ds.util.KV.mkPair;
import static ds.util.Integer.max;
import static ds.util.Integer.min;
import static ds.util.Undef.undefined;
import java.util.Iterator;
import static java.lang.Integer.signum;
//----------------------------------------
public abstract
    class BinaryTree
    implements Map {
    //----------------------------------------
    // the smart constructors
    // empty tree
    public static
        BinaryTree empty() {
        return
            EMPTY;
    }
    // singleton tree
    public static
        BinaryTree singleton(K k, V v) {
        return
            new Node(k, v, EMPTY, EMPTY);
    }
    // build search tree from arbitrary sequence (iterator)
    public static
        BinaryTree fromIterator(Iterator<KV> elems) {
        BinaryTree res = empty();
        while ( elems.hasNext() ) {
            KV p = elems.next();
            res = res.insert(p.fst, p.snd);
        }
        return
            res;
    }
    // smart constructor for building a balanced search tree
    // out of an ascending sorted sequence of values
    // The length of the sequence must be known in advance
    public static
        BinaryTree rebuild(Iterator<KV> elems, int len) {
        if ( len == 0 )
            return EMPTY;
        int lenL = len / 2;
        int lenR = len - lenL - 1;
            
        BinaryTree l = rebuild(elems, lenL);
        KV         p = elems.next();
        BinaryTree r = rebuild(elems, lenR);
        return
            new Node(p.fst, p.snd, l, r);
    }
    //----------------------------------------
    // public methods
    public abstract BinaryTree insert(K k, V v);
    public abstract BinaryTree remove(K k);
    public boolean member(K k) {
        return
            lookup(k) != null;
    }
    public BinaryTree
        union(Map m2) {
        return
            unionWith(const2, m2);
    }
    // general unionWith by iterating over m2
    // this has poor runtime, Why? O(???)?
    public BinaryTree
        unionWith(Function2<V,V,V> op,
                  Map m2) {
        Iterator<KV> i = m2.iterator();
        BinaryTree res = this;
        while ( i.hasNext() ) {
            KV kv2 = i.next();
            K  k2  = kv2.fst;
            V  v2  = kv2.snd;
            V  v1  = res.lookup(k2);
            V  vr  = v1 == null ? v2 : op.apply(v1, v2);
            res = res.insert(k2, vr);
        }
        return
            res;
    }
    public BinaryTree
        difference(Map m2) {
        return
            differenceWith(null2, m2);
    }
    public BinaryTree
        differenceWith(Function2<V,V,V> op,
                       Map m2) {
        // general differenceWith by iterating over m2
        // this has also poor runtime, Why? O(???)
        Iterator<KV> i = m2.iterator();
        BinaryTree res = this;
        while ( i.hasNext() ) {
            KV kv2 = i.next();
            K  k2  = kv2.fst;
            V  v2  = kv2.snd;
            V  v1  = res.lookup(k2);
            if ( v1 != null ) { // key found in res
                V  vr  = op.apply(v1, v2);
                if ( vr == null )
                    res = res.remove(k2);
                else
                    res = res.insert(k2, vr);
            }
        }
        return
            res;
    }
    public String toString() {
        return 
            iterator().toString();
    }
    public BinaryTree copy() {
        return
            this;
    }
    //----------------------------------------
    // special binary tree methods
    abstract public int depth();
    abstract public int minDepth();
    public boolean balanced() {
        return
            depth() <= minDepth() + 1;
    }
    public BinaryTree balance() {
        return
            rebuild(iterator(), size());
    }
    // 2. iterator for descending enumeration
    abstract public Iterator<KV> iteratorDesc();
    abstract public Iterator<KV> iteratorBreadthFirst();
    public KV findRoot() {
        return nodeExpected();
    }  
    //----------------------------------------
    // internal methods
    // getter
    Node       node()  { return nodeExpected(); }  
    K          key()   { return nodeExpected(); }
    V          value() { return nodeExpected(); }
    BinaryTree left()  { return nodeExpected(); }
    BinaryTree right() { return nodeExpected(); }
    // helper for inv
    abstract boolean allLS(K k);
    abstract boolean allGT(K k);
    
    // helper for union
    // split a tree into letf and right part
    // and optinally a root with key k and attr v
    // here k and v of the result may be null
    abstract Node splitAt(K k);
    private static <A> A nodeExpected() {
        return
            undefined("Node expected");
    }  
    // helper for ***With functions
    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 tree implemented by applying
    // the singleton design pattern
    // the "generic" empty tree object
    private static final BinaryTree EMPTY
        = new Empty();
    // the singleton class for the empty tree object
    private static final
        class Empty
        extends BinaryTree {
        // predicates and attributes
        public boolean isEmpty() {
            return true;
        }
        public int size() {
            return 0;
        }
        public int depth() {
            return 0;
        }
        public int minDepth() {
            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>();
        }
        public Iterator<KV> iteratorDesc() {
            return
                iterator();
        }
        public Iterator<KV> iteratorBreadthFirst() {
            return
                iterator();
        }
        // tree manipulation
        public BinaryTree insert(K k, V v) {
            return
                singleton(k, v);
        }
        public BinaryTree remove(K k) {
            return
                this;
        }
        public BinaryTree
            unionWith(Function2<V,V,V> op,
                      Map m2) {
            return
                (BinaryTree)m2;
        }
        public BinaryTree
            differenceWith(Function2<V,V,V> op,
                           Map m2) {
            return
                this;
        }
        public BinaryTree balance() {
            return
                this;
        }
        //----------------------------------------
        // not public stuff
        Empty() { }
        boolean allLS(K k) {
            return true;
        }
        boolean allGT(K k) {
            return true;
        }
        Node splitAt(K k) {
            return
                new Node(null, null, EMPTY, EMPTY);
        }
    }
    
    //----------------------------------------
    // the node class for none empty trees
    private static final
        class Node
        extends BinaryTree {
        /* persistent */
        final K          k;
        final V          v;
        final BinaryTree l;
        final BinaryTree r;
        /* destructive *
        K          k;
        V          v;
        BinaryTree l;
        BinaryTree r;
        /**/
        Node(K k, V v, BinaryTree l, BinaryTree r) {
            assert k != null;
            this.k = k;
            this.v = v;
            this.l = l;
            this.r = r;
            ++cntNode;
        }
        //----------------------------------------
        // predicates and attributes
        public boolean isEmpty() {
            return false;
        }
        public int size() {
            return
                1 + l.size() + r.size();
        }
        public int depth() {
            return
                1 + max(l.depth(), r.depth());
        }
        public int minDepth() {
            return
                1 + min(l.minDepth(), r.minDepth());
        }
        public V lookup(K k) {
            assert k != null;
            switch (signum(k.compareTo(this.k))) {
            case -1:
                return
                    l.lookup(k);
            case 0:
                return
                    v;
            case +1:
                return
                    r.lookup(k);
            }
            // never executed, but required by javac
            return
                null;
        }
        public boolean inv() {
            return
                l.allLS(k)
                &&
                r.allGT(k)
                &&
                l.inv()
                &&
                r.inv();
        }
        //----------------------------------------
        public KV findRoot() {
            return
                mkPair(key(), value());
        }  
        public KV findMin() {
            if ( l.isEmpty() )
                return
                    mkPair(k, v);
            return
                l.findMin();
        }  
        public KV findMax() {
            if ( r.isEmpty() )
                return
                    mkPair(k, v);
            return
                r.findMax();
        }  
        public Iterator<KV> iterator() {
            return
                new NodeIterator(this);
        }
        public Iterator<KV> iteratorDesc() {
            return
                new NodeIteratorDescending(this);
        }
        public Iterator<KV> iteratorBreadthFirst() {
            return
                new NodeIteratorBF(this);
        }
        //----------------------------------------
        // internal methods
        // getter
        Node       node()  { return this; }  
        K          key()   { return k; }
        V          value() { return v; }
        BinaryTree left()  { return l; }
        BinaryTree right() { return r; }
        // helper for inv
        boolean allLS(K k) {
            return
                this.k.compareTo(k) < 0
                &&
                r.allLS(k)
                // &&         // redundant if only
                // l.allLS(k) // used by inv
                ;
        }
        boolean allGT(K k) {
            return
                this.k.compareTo(k) > 0
                &&
                l.allGT(k)
                // &&         // redundant if only
                // r.allGT(k) // used by inv
                ;
        }
        // helper for union
        Node splitAt(K k) {
            switch ( signum(k.compareTo(this.k)) ) {
            case -1:
                Node rl = l.splitAt(k);
                return
                    rl.setR(this.setL(rl.r));
            case  0:
                return
                    this;
            case +1:
                Node rr = r.splitAt(k);
                return
                    rr.setL(this.setR(rr.l));
            }
            // dead code
            return
                null;
        }
        // setter
        private Node set(K k, V v,
                         BinaryTree l,
                         BinaryTree r) {
            /* persistent */
            if ( k == this.k && v == this.v
                 &&
                 l == this.l && r == this.r
                 )
                return
                    this;
            return
                new Node(k, v, l, r);
            /* destructive *
            this.k = k;
            this.v = v;
            this.l = l;
            this.r = r;
            return
                this;
            /**/
        }
        private Node setL(BinaryTree l) {
            /* persistent */
            if ( l == this.l )
                return
                    this;
            return
                new Node(this.k, this.v, l, this.r);
            /* destructive *
            this.l = l;
            return
                this;
            /**/
        }
        private Node setR(BinaryTree r) {
            /* persistent */
            if ( r == this.r )
                return
                    this;
            return
                new Node(this.k, this.v, this.l, r);
            /* destructive *
            this.r = r;
            return
                this;
            /**/
        }
        private Node setV(V v) {
            /* persistent */
            return
                ( v == this.v )
                ? this
                : new Node(this.k, v, this.l, this.r);
            /* destructive *
            this.v = v;
            return
                this;
            /**/
        }
        //----------------------------------------
        // tree manipulation
        public BinaryTree insert(K k, V v) {
            assert k != null;
            switch ( signum(k.compareTo(this.k)) ) {
            case -1:
                return
                    setL(l.insert(k,v));
            case 0:
                return
                    setV(v);
            case +1:
                return
                    setR(r.insert(k, v));
            }
            // never executed, but required by javac
            return
                null;
        }
    
        public BinaryTree remove(K k) {
            assert k != null;
            switch ( signum(k.compareTo(this.k)) ) {
            case -1:
                return
                    setL(l.remove(k));
            case 0:
                return
                    removeRoot();
            case +1:
                return
                    setR(r.remove(k));
            }
            // never executed, but required by javac
            return
                null;
        }
        private BinaryTree removeRoot() {
            if ( l.isEmpty() )
                return
                    r;
            if ( r.isEmpty() )
                return
                    l;
            // take maximum value in left tree as new root
            KV         maxL = l.findMax();
            BinaryTree newL = l.remove(maxL.fst);
            return
                set(maxL.fst, maxL.snd, newL, r);
        }
        // fast union
        // merging of trees is done with respect to order in m2
        public BinaryTree
            unionWith(Function2<V,V,V> op,
                      Map m2) {
            BinaryTree t2 = (BinaryTree)m2;
            if ( t2.isEmpty() )
                return
                    this;
            Node splitm2 = t2.splitAt(k);
            BinaryTree lr = l.unionWith(op, splitm2.l);
            BinaryTree rr = r.unionWith(op, splitm2.r);
            V   vr = splitm2.k == null ? v : op.apply(v, splitm2.v);
            return
                set(k, vr, lr, rr);
        }
        /* destructive *
        public BinaryTree copy() {
            return
                new Node(k, v,
                         l.copy(),
                         r.copy());
        }
        /**/
        //----------------------------------------
        // iterators
        // ascending enumeration
        private static
            class NodeIterator
            extends ds.util.Iterator<KV> {
        
            Queue queue;
            NodeIterator(Node n) {
                queue = Queue.empty();
                add(n);
                ++cntIter;
            }
            void add(Node n) {
                queue = queue.cons(n);
                if ( ! n.l.isEmpty() ) {
                    add(n.l.node()); // downcast
                }
            }
            void addSubNodes(Node n) {
                if ( ! n.r.isEmpty() )
                    add(n.r.node());
            }
            public boolean hasNext() {
                return
                    ! queue.isEmpty();
            }
            public KV next() {
                if ( queue.isEmpty() )
                    return
                        undefined("empty tree");
                Node n = (Node)queue.head();
                queue  = queue.tail();
                addSubNodes(n);
                return
                    mkPair(n.k, n.v);
            }
        }   // end NodeIterator
        // descending enumeration
        private
            class NodeIteratorDescending
            extends NodeIterator {
            NodeIteratorDescending(Node n) {
                super(n);
            }
        
            void add(Node n) {
                queue = queue.cons(n);
                if ( ! n.r.isEmpty() )
                    add(n.r.node()); // downcast
            }
            void addSubNodes(Node n) {
                if ( ! n.l.isEmpty() )
                    add(n.l.node());
            }
        }   // end NodeIteratorDescending
        // descending enumeration
        private
            class NodeIteratorBF
            extends NodeIterator {
            NodeIteratorBF(Node n) {
                super(n);
            }
        
            void add(Node n) {
                // add the nodes at the bottom
                queue = queue.append(n);
            }
            void addSubNodes(Node n) {
                if ( ! n.l.isEmpty() )
                    add(n.l.node());
                if ( ! n.r.isEmpty() )
                    add(n.r.node());
            }
        }   // end NodeIteratorBF
    }
    //----------------------------------------
    // profiling
    private static int cntNode = 0;
    private static int cntIter = 0;
    public static String stats() {
        return
            "stats for ds.persistent.map.BinaryTree:\n" +
            "# new Node()               : " + cntNode + "\n" +
            "# new Iterator()           : " + cntIter + "\n";
    }
    public String objStats() {
        int s = size();
        int o = s;
        int f = 4 * s;
        int m = o + f;
        return
            "mem stats for ds.persistent.map.BinaryTree object:\n" +
            "# elements (size)      : " + s + "\n" +
            "# objects              : " + o + "\n" +
            "# fields               : " + f + "\n" +
            "# mem words            : " + m + "\n";
    }
}

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