Algorithmen & Datenstrukturen mit Java: ds.persistent.map.BinaryTree

1package ds.persistent.map;

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.

8 Binary search trees require a total ordering

9 on the key.

10*/

12import ds.interfaces.Map;

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;

21import static ds.util.KV.mkPair;

22import static ds.util.Integer.max;

23import static ds.util.Integer.min;

24import static ds.util.Undef.undefined;

26import java.util.Iterator;

28import static java.lang.Integer.signum;

30//----------------------------------------

32public abstract

33 class BinaryTree

34 implements Map {

36 //----------------------------------------

37 // the smart constructors

39 // empty tree

40 public static

41 BinaryTree empty() {

42 return

43 EMPTY;

44 }

46 // singleton tree

47 public static

48 BinaryTree singleton(K k, V v) {

49 return

50 new Node(k, v, EMPTY, EMPTY);

51 }

53 // build search tree from arbitrary sequence (iterator)

54 public static

55 BinaryTree fromIterator(Iterator<KV> elems) {

57 BinaryTree res = empty();

58 while ( elems.hasNext() ) {

59 KV p = elems.next();

60 res = res.insert(p.fst, p.snd);

61 }

62 return

63 res;

64 }

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

70 public static

71 BinaryTree rebuild(Iterator<KV> elems, int len) {

73 if ( len == 0 )

74 return EMPTY;

76 int lenL = len / 2;

77 int lenR = len - lenL - 1;

79 BinaryTree l = rebuild(elems, lenL);

80 KV p = elems.next();

81 BinaryTree r = rebuild(elems, lenR);

83 return

84 new Node(p.fst, p.snd, l, r);

85 }

87 //----------------------------------------

88 // public methods

90 public abstract BinaryTree insert(K k, V v);

91 public abstract BinaryTree remove(K k);

93 public boolean member(K k) {

94 return

95 lookup(k) != null;

96 }

98 public BinaryTree

99 union(Map m2) {

100 return

101 unionWith(const2, m2);

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(v1, v2);

119 res = res.insert(k2, vr);

120 }

121 return

122 res;

123 }

124

125 public BinaryTree

126 difference(Map m2) {

127 return

128 differenceWith(null2, m2);

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(v1, v2);

148 if ( vr == null )

149 res = res.remove(k2);

150 else

151 res = res.insert(k2, vr);

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 x, V 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 x, V 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 k, V v) {

299 return

300 singleton(k, v);

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(null, null, EMPTY, EMPTY);

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 k, V v, BinaryTree l, BinaryTree 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(k, v);

439 return

440 l.findMin();

441 }

442

443 public KV findMax() {

444 if ( r.isEmpty() )

445 return

446 mkPair(k, v);

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 k, V 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(k, v, l, r);

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.k, this.v, l, this.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.k, this.v, this.l, r);

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.k, v, this.l, this.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 k, V 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(k, v));

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.fst, maxL.snd, newL, r);

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(op, splitm2.l);

655 BinaryTree rr = r.unionWith(op, splitm2.r);

656 V vr = splitm2.k == null ? v : op.apply(v, splitm2.v);

657 return

658 set(k, vr, lr, rr);

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.k, n.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}