homedukeAlgorithmen & Datenstrukturen mit Java: Beispielklasse für Verzeichnisse als binäre Suchbäume Prof. Dr. Uwe Schmidt FH Wedel

Beispielklasse für Verzeichnisse als binäre Suchbäume

weiter

weiter

Map
Schnittstelle wie bei sortierter Liste
weiter
   1package ds.interfaces;
   2
   3/** Simple interface for maps
   4 */
   5
   6import java.util.Iterator;
   7
   8import ds.util.Invariant;
   9import ds.util.Function2;
  10
  11import ds.util.K;  // example class for keys
  12import ds.util.V;  // example class for values
  13import ds.util.KV// key value pair
  14
  15public
  16    interface Map
  17    extends Iterable<KV>,
  18            Invariant {
  19
  20    boolean isEmpty();
  21    boolean member(K k);
  22    V       lookup(K k);
  23    int     size();
  24    KV      findMin();
  25    KV      findMax();
  26    Map     insert(K kV v);
  27    Map     remove(K k);
  28    Map     union(Map m2);
  29    Map     difference(Map m2);
  30    Map     unionWith(Function2<V,V,V> opMap m2);
  31    Map     differenceWith(Function2<V,V,V> opMap m2);
  32    Map     copy();
  33
  34    // inherited
  35
  36    // public Iterator<KV> iterator();
  37    // public inv();
  38}
weiter
Map
implementiert als binärer Suchbaum
ohne Generics
persistente Implementierung
destruktive Implementierung in Kommentar
weiter
   1package ds.persistent.map;
   2
   3/** Persistent implementation of binary search treee.
   4    Operations manipulating trees always create copies
   5    of the objects to be manipulated. This assures, that
   6    old trees remains unchanged.
   7
   8    Binary search trees require a total ordering
   9    on the key.
  10*/
  11
  12import ds.interfaces.Map;
  13
  14import ds.util.K;         // example class for keys
  15import ds.util.V;         // example class for values
  16import ds.util.KV;        // key value pair
  17import ds.util.Queue;     // for iterators
  18import ds.util.Function2;
  19import ds.util.NullIterator;
  20
  21import static ds.util.KV.mkPair;
  22import static ds.util.Integer.max;
  23import static ds.util.Integer.min;
  24import static ds.util.Undef.undefined;
  25
  26import java.util.Iterator;
  27
  28import static java.lang.Integer.signum;
  29
  30//----------------------------------------
  31
  32public abstract
  33    class BinaryTree
  34    implements Map {
  35
  36    //----------------------------------------
  37    // the smart constructors
  38
  39    // empty tree
  40    public static
  41        BinaryTree empty() {
  42        return
  43            EMPTY;
  44    }
  45
  46    // singleton tree
  47    public static
  48        BinaryTree singleton(K kV v) {
  49        return
  50            new Node(kvEMPTYEMPTY);
  51    }
  52
  53    // build search tree from arbitrary sequence (iterator)
  54    public static
  55        BinaryTree fromIterator(Iterator<KV> elems) {
  56
  57        BinaryTree res = empty();
  58        while ( elems.hasNext() ) {
  59            KV p = elems.next();
  60            res = res.insert(p.fstp.snd);
  61        }
  62        return
  63            res;
  64    }
  65
  66    // smart constructor for building a balanced search tree
  67    // out of an ascending sorted sequence of values
  68    // The length of the sequence must be known in advance
  69
  70    public static
  71        BinaryTree rebuild(Iterator<KV> elemsint len) {
  72
  73        if ( len == 0 )
  74            return EMPTY;
  75
  76        int lenL = len / 2;
  77        int lenR = len - lenL - 1;
  78            
  79        BinaryTree l = rebuild(elemslenL);
  80        KV         p = elems.next();
  81        BinaryTree r = rebuild(elemslenR);
  82
  83        return
  84            new Node(p.fstp.sndlr);
  85    }
  86
  87    //----------------------------------------
  88    // public methods
  89
  90    public abstract BinaryTree insert(K kV v);
  91    public abstract BinaryTree remove(K k);
  92
  93    public boolean member(K k) {
  94        return
  95            lookup(k) != null;
  96    }
  97
  98    public BinaryTree
  99        union(Map m2) {
 100        return
 101            unionWith(const2m2);
 102    }
 103
 104    // general unionWith by iterating over m2
 105    // this has poor runtime, Why? O(???)?
 106
 107    public BinaryTree
 108        unionWith(Function2<V,V,V> op,
 109                  Map m2) {
 110        Iterator<KV> i = m2.iterator();
 111        BinaryTree res = this;
 112
 113        while ( i.hasNext() ) {
 114            KV kv2 = i.next();
 115            K  k2  = kv2.fst;
 116            V  v2  = kv2.snd;
 117            V  v1  = res.lookup(k2);
 118            V  vr  = v1 == null ? v2 : op.apply(v1v2);
 119            res = res.insert(k2vr);
 120        }
 121        return
 122            res;
 123    }
 124
 125    public BinaryTree
 126        difference(Map m2) {
 127        return
 128            differenceWith(null2m2);
 129    }
 130
 131    public BinaryTree
 132        differenceWith(Function2<V,V,V> op,
 133                       Map m2) {
 134        // general differenceWith by iterating over m2
 135        // this has also poor runtime, Why? O(???)
 136
 137        Iterator<KV> i = m2.iterator();
 138        BinaryTree res = this;
 139
 140        while ( i.hasNext() ) {
 141            KV kv2 = i.next();
 142            K  k2  = kv2.fst;
 143            V  v2  = kv2.snd;
 144            V  v1  = res.lookup(k2);
 145
 146            if ( v1 != null ) { // key found in res
 147                V  vr  = op.apply(v1v2);
 148                if ( vr == null )
 149                    res = res.remove(k2);
 150                else
 151                    res = res.insert(k2vr);
 152            }
 153        }
 154        return
 155            res;
 156    }
 157
 158    public String toString() {
 159        return 
 160            iterator().toString();
 161    }
 162
 163    public BinaryTree copy() {
 164        return
 165            this;
 166    }
 167
 168    //----------------------------------------
 169    // special binary tree methods
 170
 171    abstract public int depth();
 172    abstract public int minDepth();
 173
 174    public boolean balanced() {
 175        return
 176            depth() <= minDepth() + 1;
 177    }
 178
 179    public BinaryTree balance() {
 180        return
 181            rebuild(iterator()size());
 182    }
 183
 184    // 2. iterator for descending enumeration
 185    abstract public Iterator<KV> iteratorDesc();
 186
 187    abstract public Iterator<KV> iteratorBreadthFirst();
 188
 189    public KV findRoot() {
 190        return nodeExpected();
 191    }  
 192
 193    //----------------------------------------
 194    // internal methods
 195
 196    // getter
 197    Node       node()  { return nodeExpected()}  
 198    K          key()   { return nodeExpected()}
 199    V          value() { return nodeExpected()}
 200    BinaryTree left()  { return nodeExpected()}
 201    BinaryTree right() { return nodeExpected()}
 202
 203    // helper for inv
 204    abstract boolean allLS(K k);
 205    abstract boolean allGT(K k);
 206    
 207    // helper for union
 208    // split a tree into letf and right part
 209    // and optinally a root with key k and attr v
 210    // here k and v of the result may be null
 211    abstract Node splitAt(K k);
 212
 213    private static <A> A nodeExpected() {
 214        return
 215            undefined("Node expected");
 216    }  
 217
 218    // helper for ***With functions
 219    private static Function2<V,V,V> const2
 220        = new Function2<V,V,V>() {
 221        public V apply(V xV y) {
 222            return y;
 223        }
 224    };
 225
 226    private static Function2<V,V,V> null2
 227        = new Function2<V,V,V>() {
 228        public V apply(V xV y) {
 229            return null;
 230        }
 231    };
 232
 233    //----------------------------------------
 234    // the empty tree implemented by applying
 235    // the singleton design pattern
 236
 237    // the "generic" empty tree object
 238
 239    private static final BinaryTree EMPTY
 240        = new Empty();
 241
 242    // the singleton class for the empty tree object
 243
 244    private static final
 245        class Empty
 246        extends BinaryTree {
 247
 248        // predicates and attributes
 249        public boolean isEmpty() {
 250            return true;
 251        }
 252
 253        public int size() {
 254            return 0;
 255        }
 256
 257        public int depth() {
 258            return 0;
 259        }
 260
 261        public int minDepth() {
 262            return 0;
 263        }
 264
 265        public V lookup(K k) {
 266            return null;
 267        }
 268
 269        public KV findMin() {
 270            return nodeExpected();
 271        }
 272  
 273        public KV findMax() {
 274            return nodeExpected();
 275        }  
 276
 277        public boolean inv() {
 278            return true;
 279        }
 280
 281        public Iterator<KV> iterator() {
 282            ++cntIter;
 283            return
 284                new NullIterator<KV>();
 285        }
 286
 287        public Iterator<KV> iteratorDesc() {
 288            return
 289                iterator();
 290        }
 291
 292        public Iterator<KV> iteratorBreadthFirst() {
 293            return
 294                iterator();
 295        }
 296
 297        // tree manipulation
 298        public BinaryTree insert(K kV v) {
 299            return
 300                singleton(kv);
 301        }
 302
 303        public BinaryTree remove(K k) {
 304            return
 305                this;
 306        }
 307
 308        public BinaryTree
 309            unionWith(Function2<V,V,V> op,
 310                      Map m2) {
 311            return
 312                (BinaryTree)m2;
 313        }
 314
 315        public BinaryTree
 316            differenceWith(Function2<V,V,V> op,
 317                           Map m2) {
 318            return
 319                this;
 320        }
 321
 322        public BinaryTree balance() {
 323            return
 324                this;
 325        }
 326
 327        //----------------------------------------
 328        // not public stuff
 329
 330        Empty() { }
 331
 332        boolean allLS(K k) {
 333            return true;
 334        }
 335        boolean allGT(K k) {
 336            return true;
 337        }
 338
 339        Node splitAt(K k) {
 340            return
 341                new Node(nullnullEMPTYEMPTY);
 342        }
 343    }
 344    
 345    //----------------------------------------
 346    // the node class for none empty trees
 347
 348    private static final
 349        class Node
 350        extends BinaryTree {
 351
 352        /* persistent */
 353        final K          k;
 354        final V          v;
 355        final BinaryTree l;
 356        final BinaryTree r;
 357
 358        /* destructive *
 359        K          k;
 360        V          v;
 361        BinaryTree l;
 362        BinaryTree r;
 363        /**/
 364
 365        Node(K kV vBinaryTree lBinaryTree r) {
 366            assert k != null;
 367
 368            this.k = k;
 369            this.v = v;
 370            this.l = l;
 371            this.r = r;
 372            ++cntNode;
 373        }
 374
 375        //----------------------------------------
 376        // predicates and attributes
 377
 378        public boolean isEmpty() {
 379            return false;
 380        }
 381
 382        public int size() {
 383            return
 384                1 + l.size() + r.size();
 385        }
 386
 387        public int depth() {
 388            return
 389                1 + max(l.depth()r.depth());
 390        }
 391
 392        public int minDepth() {
 393            return
 394                1 + min(l.minDepth()r.minDepth());
 395        }
 396
 397        public V lookup(K k) {
 398            assert k != null;
 399
 400            switch (signum(k.compareTo(this.k))) {
 401            case -1:
 402                return
 403                    l.lookup(k);
 404            case 0:
 405                return
 406                    v;
 407            case +1:
 408                return
 409                    r.lookup(k);
 410            }
 411            // never executed, but required by javac
 412            return
 413                null;
 414        }
 415
 416        public boolean inv() {
 417            return
 418                l.allLS(k)
 419                &&
 420                r.allGT(k)
 421                &&
 422                l.inv()
 423                &&
 424                r.inv();
 425        }
 426
 427        //----------------------------------------
 428
 429        public KV findRoot() {
 430            return
 431                mkPair(key()value());
 432        }  
 433
 434
 435        public KV findMin() {
 436            if ( l.isEmpty() )
 437                return
 438                    mkPair(kv);
 439            return
 440                l.findMin();
 441        }  
 442
 443        public KV findMax() {
 444            if ( r.isEmpty() )
 445                return
 446                    mkPair(kv);
 447            return
 448                r.findMax();
 449        }  
 450
 451        public Iterator<KV> iterator() {
 452            return
 453                new NodeIterator(this);
 454        }
 455
 456        public Iterator<KV> iteratorDesc() {
 457            return
 458                new NodeIteratorDescending(this);
 459        }
 460
 461        public Iterator<KV> iteratorBreadthFirst() {
 462            return
 463                new NodeIteratorBF(this);
 464        }
 465        //----------------------------------------
 466        // internal methods
 467
 468        // getter
 469        Node       node()  { return this}  
 470        K          key()   { return k}
 471        V          value() { return v}
 472        BinaryTree left()  { return l}
 473        BinaryTree right() { return r}
 474
 475
 476        // helper for inv
 477
 478        boolean allLS(K k) {
 479            return
 480                this.k.compareTo(k) < 0
 481                &&
 482                r.allLS(k)
 483                // &&         // redundant if only
 484                // l.allLS(k) // used by inv
 485                ;
 486        }
 487
 488        boolean allGT(K k) {
 489            return
 490                this.k.compareTo(k) > 0
 491                &&
 492                l.allGT(k)
 493                // &&         // redundant if only
 494                // r.allGT(k) // used by inv
 495                ;
 496        }
 497
 498        // helper for union
 499
 500        Node splitAt(K k) {
 501            switch ( signum(k.compareTo(this.k)) ) {
 502            case -1:
 503                Node rl = l.splitAt(k);
 504                return
 505                    rl.setR(this.setL(rl.r));
 506            case  0:
 507                return
 508                    this;
 509            case +1:
 510                Node rr = r.splitAt(k);
 511                return
 512                    rr.setL(this.setR(rr.l));
 513            }
 514            // dead code
 515            return
 516                null;
 517        }
 518
 519
 520        // setter
 521
 522        private Node set(K kV v,
 523                         BinaryTree l,
 524                         BinaryTree r) {
 525            /* persistent */
 526            if ( k == this.k && v == this.v
 527                 &&
 528                 l == this.l && r == this.r
 529                 )
 530                return
 531                    this;
 532            return
 533                new Node(kvlr);
 534
 535            /* destructive *
 536            this.k = k;
 537            this.v = v;
 538            this.l = l;
 539            this.r = r;
 540            return
 541                this;
 542            /**/
 543        }
 544        private Node setL(BinaryTree l) {
 545            /* persistent */
 546            if ( l == this.l )
 547                return
 548                    this;
 549            return
 550                new Node(this.kthis.vlthis.r);
 551
 552            /* destructive *
 553            this.l = l;
 554            return
 555                this;
 556            /**/
 557        }
 558        private Node setR(BinaryTree r) {
 559            /* persistent */
 560            if ( r == this.r )
 561                return
 562                    this;
 563            return
 564                new Node(this.kthis.vthis.lr);
 565
 566            /* destructive *
 567            this.r = r;
 568            return
 569                this;
 570            /**/
 571        }
 572        private Node setV(V v) {
 573            /* persistent */
 574            return
 575                ( v == this.v )
 576                ? this
 577                : new Node(this.kvthis.lthis.r);
 578
 579            /* destructive *
 580            this.v = v;
 581            return
 582                this;
 583            /**/
 584        }
 585
 586        //----------------------------------------
 587        // tree manipulation
 588
 589        public BinaryTree insert(K kV v) {
 590            assert k != null;
 591
 592            switch ( signum(k.compareTo(this.k)) ) {
 593            case -1:
 594                return
 595                    setL(l.insert(k,v));
 596            case 0:
 597                return
 598                    setV(v);
 599            case +1:
 600                return
 601                    setR(r.insert(kv));
 602            }
 603            // never executed, but required by javac
 604            return
 605                null;
 606        }
 607    
 608        public BinaryTree remove(K k) {
 609            assert k != null;
 610
 611            switch ( signum(k.compareTo(this.k)) ) {
 612            case -1:
 613                return
 614                    setL(l.remove(k));
 615            case 0:
 616                return
 617                    removeRoot();
 618            case +1:
 619                return
 620                    setR(r.remove(k));
 621            }
 622            // never executed, but required by javac
 623            return
 624                null;
 625        }
 626
 627        private BinaryTree removeRoot() {
 628            if ( l.isEmpty() )
 629                return
 630                    r;
 631            if ( r.isEmpty() )
 632                return
 633                    l;
 634
 635            // take maximum value in left tree as new root
 636            KV         maxL = l.findMax();
 637            BinaryTree newL = l.remove(maxL.fst);
 638
 639            return
 640                set(maxL.fstmaxL.sndnewLr);
 641        }
 642
 643        // fast union
 644        // merging of trees is done with respect to order in m2
 645        public BinaryTree
 646            unionWith(Function2<V,V,V> op,
 647                      Map m2) {
 648            BinaryTree t2 = (BinaryTree)m2;
 649            if ( t2.isEmpty() )
 650                return
 651                    this;
 652
 653            Node splitm2 = t2.splitAt(k);
 654            BinaryTree lr = l.unionWith(opsplitm2.l);
 655            BinaryTree rr = r.unionWith(opsplitm2.r);
 656            V   vr = splitm2.k == null ? v : op.apply(vsplitm2.v);
 657            return
 658                set(kvrlrrr);
 659        }
 660
 661
 662        /* destructive *
 663        public BinaryTree copy() {
 664            return
 665                new Node(k, v,
 666                         l.copy(),
 667                         r.copy());
 668        }
 669        /**/
 670
 671        //----------------------------------------
 672        // iterators
 673
 674        // ascending enumeration
 675
 676        private static
 677            class NodeIterator
 678            extends ds.util.Iterator<KV> {
 679        
 680            Queue queue;
 681
 682            NodeIterator(Node n) {
 683                queue = Queue.empty();
 684                add(n);
 685                ++cntIter;
 686            }
 687
 688            void add(Node n) {
 689                queue = queue.cons(n);
 690                if ( ! n.l.isEmpty() ) {
 691                    add(n.l.node())// downcast
 692                }
 693            }
 694
 695            void addSubNodes(Node n) {
 696                if ( ! n.r.isEmpty() )
 697                    add(n.r.node());
 698            }
 699
 700            public boolean hasNext() {
 701                return
 702                    ! queue.isEmpty();
 703            }
 704
 705            public KV next() {
 706                if ( queue.isEmpty() )
 707                    return
 708                        undefined("empty tree");
 709
 710                Node n = (Node)queue.head();
 711                queue  = queue.tail();
 712                addSubNodes(n);
 713                return
 714                    mkPair(n.kn.v);
 715            }
 716        }   // end NodeIterator
 717
 718        // descending enumeration
 719        private
 720            class NodeIteratorDescending
 721            extends NodeIterator {
 722
 723            NodeIteratorDescending(Node n) {
 724                super(n);
 725            }
 726        
 727            void add(Node n) {
 728                queue = queue.cons(n);
 729                if ( ! n.r.isEmpty() )
 730                    add(n.r.node())// downcast
 731            }
 732
 733            void addSubNodes(Node n) {
 734                if ( ! n.l.isEmpty() )
 735                    add(n.l.node());
 736            }
 737        }   // end NodeIteratorDescending
 738
 739        // descending enumeration
 740        private
 741            class NodeIteratorBF
 742            extends NodeIterator {
 743
 744            NodeIteratorBF(Node n) {
 745                super(n);
 746            }
 747        
 748            void add(Node n) {
 749                // add the nodes at the bottom
 750                queue = queue.append(n);
 751            }
 752
 753            void addSubNodes(Node n) {
 754                if ( ! n.l.isEmpty() )
 755                    add(n.l.node());
 756                if ( ! n.r.isEmpty() )
 757                    add(n.r.node());
 758            }
 759        }   // end NodeIteratorBF
 760    }
 761
 762    //----------------------------------------
 763    // profiling
 764
 765    private static int cntNode = 0;
 766    private static int cntIter = 0;
 767
 768    public static String stats() {
 769        return
 770            "stats for ds.persistent.map.BinaryTree:\n" +
 771            "# new Node()               : " + cntNode + "\n" +
 772            "# new Iterator()           : " + cntIter + "\n";
 773    }
 774
 775    public String objStats() {
 776        int s = size();
 777        int o = s;
 778        int f = 4 * s;
 779        int m = o + f;
 780
 781        return
 782            "mem stats for ds.persistent.map.BinaryTree object:\n" +
 783            "# elements (size)      : " + s + "\n" +
 784            "# objects              : " + o + "\n" +
 785            "# fields               : " + f + "\n" +
 786            "# mem words            : " + m + "\n";
 787    }
 788}
weiter
Quellen
weiter

Letzte Änderung: 08.12.2015
© Prof. Dr. Uwe Schmidt
Prof. Dr. Uwe Schmidt FH Wedel