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

1package ds.persistent.map;

3/** This is a translation of a Haskell implementation

4 for red-black trees from

5 http://matt.might.net/articles/red-black-delete/

6 The Haskell source can be found under

7 http://matt.might.net/articles/red-black-delete/code/RedBlackSet.hs

9 This Java implementation is a PERSISTENT one and

10 it supports deletion.

11*/

13import ds.interfaces.Map;

15import ds.util.K; // example class for keys

16import ds.util.V; // example class for values

17import ds.util.KV; // key value pair

18import ds.util.Queue; // used by iterators

19import ds.util.Function2;

20import ds.util.NullIterator;

22import static ds.util.KV.mkPair;

23import static ds.util.Boolean.toInt;

24import static ds.util.Integer.max;

25import static ds.util.Integer.min;

26import static ds.util.Undef.undefined;

28import java.util.Iterator;

30import static java.lang.Integer.signum;

32//----------------------------------------

34public abstract

35 class RedBlackTree

36 implements Map {

38 /* trc *

39 static void msg(String s) {

40 System.out.println(s);

41 }

43 static RedBlackTree trc(String s, RedBlackTree t) {

44 msg(s + " " + t);

45 return t;

46 }

47 /**/

49 //----------------------------------------

50 // the smart constructors

52 // empty tree

53 public static

54 RedBlackTree empty() {

55 return

56 EMPTY;

57 }

59 // singleton tree

60 public static

61 RedBlackTree singleton(K k, V v) {

62 return

63 empty().insert(k, v);

64 }

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

67 public static

68 RedBlackTree fromIterator(Iterator<KV> elems) {

70 RedBlackTree res = empty();

71 while ( elems.hasNext() ) {

72 KV p = elems.next();

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

74 }

75 return

76 res;

77 }

79 public RedBlackTree

80 union(Map m2) {

81 return

82 unionWith(const2, m2);

83 }

85 // general unionWith by iterating over m2

86 public RedBlackTree

87 unionWith(Function2<V,V,V> op,

88 Map m2) {

89 Iterator<KV> i = m2.iterator();

90 RedBlackTree res = this;

92 while ( i.hasNext() ) {

93 KV kv2 = i.next();

94 K k2 = kv2.fst;

95 V v2 = kv2.snd;

96 V v1 = res.lookup(k2);

97 V vr = v1 == null ? v2 : op.apply(v1, v2);

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

99 }

100 return

101 res;

102 }

103

104 public RedBlackTree

105 difference(Map m2) {

106 return

107 differenceWith(null2, m2);

108 }

109

110 // general differenceWith by iterating over m2

111 public RedBlackTree

112 differenceWith(Function2<V,V,V> op,

113 Map m2) {

114

115 Iterator<KV> i = m2.iterator();

116 RedBlackTree res = this;

117

118 while ( i.hasNext() ) {

119 KV kv2 = i.next();

120 K k2 = kv2.fst;

121 V v2 = kv2.snd;

122 V v1 = res.lookup(k2);

123

124 if ( v1 != null ) { // key found in res

125 V vr = op.apply(v1, v2);

126 if ( vr == null )

127 res = res.remove(k2);

128 else

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

130 }

131 }

132 return

133 res;

134 }

135

136 public RedBlackTree copy() {

137 return

138 this;

139 }

140

141 //----------------------------------------

142 // special binary tree methods

143

144 abstract public int depth();

145 abstract public int minDepth();

146

147 public boolean member(K k) {

148 return

149 lookup(k) != null;

150 }

151

152 //----------------------------------------

153 // internal methods

154

155 // getter

156 Node node() { return nodeExpected(); }

157 int color() { return nodeExpected(); }

158 K key() { return nodeExpected(); }

159 V value() { return nodeExpected(); }

160 RedBlackTree left() { return nodeExpected(); }

161 RedBlackTree right() { return nodeExpected(); }

162

163 // tree manipulation

164 public RedBlackTree insert(K k, V v) {

165 assert k != null;

166

167 return

168 insert1(k, v).paintItBlack();

169 }

170

171 public RedBlackTree remove(K k) {

172 assert k != null;

173

174 return

175 remove1(k).paintItBlack();

176 }

177

178 // 2. iterator for descending enumeration

179

180 abstract public Iterator<KV> iteratorDesc();

181

182 public String toString() {

183 return

184 iterator().toString();

185 }

186

187 public boolean inv() {

188 return

189 invOrdered()

190 &&

191 invRedWithBlackChildren()

192 &&

193 noOfBlackNodes() != -1

194 &&

195 isBlack();

196 }

197

198

199 //----------------------------------------

200 // internal methods

201

202 abstract RedBlackTree insert1(K k, V v);

203 abstract RedBlackTree remove1(K k);

204

205 abstract boolean invRedWithBlackChildren();

206 abstract int noOfBlackNodes();

207 abstract boolean invOrdered();

208 abstract boolean allLS(K k);

209 abstract boolean allGT(K k);

210

211 // helper for ***With functions

212 private static <A> A nodeExpected() {

213 return

214 undefined("Node expected");

215 }

216

217 private static Function2<V,V,V> const2

218 = new Function2<V,V,V>() {

219 public V apply(V x, V y) {

220 return y;

221 }

222 };

223

224 private static Function2<V,V,V> null2

225 = new Function2<V,V,V>() {

226 public V apply(V x, V y) {

227 return null;

228 }

229 };

230

231 //----------------------------------------

232 // coloring

233

234 static final int NEGATIVE_BLACK = -1;

235 static final int RED = 0;

236 static final int BLACK = 1;

237 static final int DOUBLE_BLACK = 2;

238

239 static int blacker(int c) {

240 assert c < DOUBLE_BLACK;

241 return

242 c + 1;

243 }

244

245 static int redder(int c) {

246 assert c > NEGATIVE_BLACK;

247 return

248 c - 1;

249 }

250

251 boolean isRed() { return color() == RED; }

252 boolean isBlack() { return color() == BLACK; }

253 boolean isDoubleBlack() { return color() == DOUBLE_BLACK; }

254 boolean isNegativeBlack() { return color() == NEGATIVE_BLACK; }

255 boolean isEmptyDoubleBlack() { return false; }

256

257 abstract RedBlackTree paintItRed();

258 abstract RedBlackTree paintItBlack();

259

260 abstract RedBlackTree blacker();

261 abstract RedBlackTree redder();

262

263 //----------------------------------------

264 // the empty tree implemented by applying the singleton design pattern

265

266 // the "generic" empty list object (with a raw type)

267

268 private static final RedBlackTree EMPTY

269 = new Empty();

270

271 // the singleton class for the empty list object

272

273 private static

274 class Empty extends RedBlackTree {

275

276 public boolean isEmpty() {

277 return true;

278 }

279

280 public int size() {

281 return 0;

282 }

283

284 public int depth() {

285 return 0;

286 }

287

288 public int minDepth() {

289 return 0;

290 }

291

292 public V lookup(K k) {

293 return null;

294 }

295

296 public KV findMin() {

297 return nodeExpected();

298 }

299

300 public KV findMax() {

301 return nodeExpected();

302 }

303

304 public Iterator<KV> iterator() {

305 ++cntIter;

306 return

307 new NullIterator<KV>();

308 }

309 public Iterator<KV> iteratorDesc() {

310 return

311 iterator();

312 }

313

314 /* *

315 public String toString() {

316 return

317 ".";

318 }

319 /* */

320

321 //----------------------------------------

322 // not public stuff

323

324 Empty() { }

325

326 boolean invRedWithBlackChildren() { return true; }

327 int noOfBlackNodes() { return 1; }

328 boolean invOrdered() { return true; }

329 boolean allLS(K k) { return true; }

330 boolean allGT(K k) { return true; }

331

332 int color() {

333 return BLACK;

334 }

335

336 RedBlackTree insert1(K k, V v) {

337 return

338 new Node(k, v, RED, EMPTY, EMPTY);

339 }

340 RedBlackTree remove1(K k) {

341 return

342 this;

343 }

344 RedBlackTree paintItBlack() {

345 return

346 empty(); // works also for DoubleEmpty

347 }

348 RedBlackTree paintItRed() {

349 return

350 undefined("paintItRed on empty tree");

351 }

352 RedBlackTree blacker() {

353 return

354 doubleEmpty();

355 }

356 RedBlackTree redder() {

357 return

358 undefined("redder of empty tree");

359 }

360

361 }

362

363 //----------------------------------------

364 // double black empty tree

365 // helper for deletion

366

367 private static

368 RedBlackTree doubleEmpty() {

369 return

370 DOUBLE_EMPTY;

371 }

372

373 private static final RedBlackTree DOUBLE_EMPTY

374 = new DoubleEmpty();

375

376 // the singleton class for the double black empty tree

377

378 private static final

379 class DoubleEmpty extends Empty {

380

381 /* *

382 public String toString() {

383 return

384 "!";

385 }

386 /* */

387

388 DoubleEmpty() { }

389

390 int color() {

391 return DOUBLE_BLACK;

392 }

393

394 boolean isEmptyDoubleBlack() {

395 return true;

396 }

397

398 RedBlackTree blacker() {

399 return

400 undefined("blacker of double black");

401 }

402 RedBlackTree redder() {

403 return

404 empty();

405 }

406 }

407

408 //----------------------------------------

409 // the node class for none empty trees

410

411 private static final

412 class Node extends RedBlackTree {

413

414 /* persistent */

415 final K k;

416 final V v;

417 final int c; // the color

418 final RedBlackTree l;

419 final RedBlackTree r;

420

421 /* destructive *

422 K k;

423 V v;

424 int c;

425 RedBlackTree l;

426 RedBlackTree r;

427 /**/

428

429 Node(K k, V v, int c, RedBlackTree l, RedBlackTree r) {

430 assert k != null;

431

432 this.k = k;

433 this.v = v;

434 this.c = c;

435 this.l = l;

436 this.r = r;

437 ++cntNode;

438 }

439

440 /* destructive *

441 public RedBlackTree copy() {

442 return

443 new Node(k, v, c, l, r);

444 }

445 /**/

446

447 /* trc *

448 String toString() {

449 return

450 "(" + l + " " + k + "," + v + "," + c2s(c) + " " + r + ")";

451 }

452 /**/

453

454 private static String c2s(int c) {

455 switch ( c ) {

456 case NEGATIVE_BLACK: return "N";

457 case RED: return "R";

458 case BLACK: return "B";

459 case DOUBLE_BLACK: return "D";

460 }

461 return "";

462 }

463

464 //----------------------------------------

465 // predicates and attributes

466

467 public boolean isEmpty() {

468 return false;

469 }

470

471 public int size() {

472 return

473 1 + l.size() + r.size();

474 }

475

476 public int depth() {

477 return

478 1 + max(l.depth(), r.depth());

479 }

480

481 public int minDepth() {

482 return

483 1 + min(l.minDepth(), r.minDepth());

484 }

485

486 public V lookup(K k) {

487 assert k != null;

488

489 switch (signum(k.compareTo(this.k))) {

490 case -1:

491 return

492 l.lookup(k);

493 case 0:

494 return

495 v;

496 case +1:

497 return

498 r.lookup(k);

499 }

500 // never executed, but required

501 return

502 null;

503 }

504

505 //----------------------------------------

506 // getter

507

508 Node node() { return this; }

509 int color() { return c; }

510 K key() { return k; }

511 V value() { return v; }

512 RedBlackTree left() { return l; }

513 RedBlackTree right() { return r; }

514

515 public KV findMin() {

516 if ( l.isEmpty() )

517 return

518 mkPair(k, v);

519 return

520 l.findMin();

521 }

522

523 public KV findMax() {

524 if ( r.isEmpty() )

525 return

526 mkPair(k, v);

527 return

528 r.findMax();

529 }

530

531 public Iterator<KV> iterator() {

532 ++cntIter;

533 return

534 new NodeIterator(this);

535 }

536

537 public Iterator<KV> iteratorDesc() {

538 ++cntIter;

539 return

540 new NodeIteratorDescending(this);

541 }

542

543 //----------------------------------------

544 // invariant helpers

545

546 boolean invRedWithBlackChildren() {

547 return

548 ( ! isRed()

549 ||

550 ( l.isBlack() && r.isBlack() ) )

551 &&

552 l.invRedWithBlackChildren()

553 &&

554 r.invRedWithBlackChildren();

555 }

556

557 // -1 indicates # of black nodes differ

558 int noOfBlackNodes() {

559 int nl = l.noOfBlackNodes();

560 int nr = r.noOfBlackNodes();

561 return

562 (nl == nr && nl != -1)

563 ? nl + toInt(isBlack())

564 : -1;

565 }

566

567 boolean invOrdered() {

568 return

569 l.allLS(k)

570 &&

571 r.allGT(k)

572 &&

573 l.invOrdered()

574 &&

575 r.invOrdered();

576 }

577

578 boolean allLS(K k) {

579 return

580 this.k.compareTo(k) < 0

581 &&

582 r.allLS(k)

583 // && // redundant if only

584 // l.allLS(k) // used by inv

585 ;

586 }

587 boolean allGT(K k) {

588 return

589 this.k.compareTo(k) > 0

590 &&

591 l.allGT(k)

592 // && // redundant if only

593 // r.allGT(k) // used by inv

594 ;

595 }

596

597

598 //----------------------------------------

599 // getter

600

601 //----------------------------------------

602 // recoloring

603

604 RedBlackTree paintItBlack() {

605 return

606 setColor(BLACK);

607 }

608 RedBlackTree paintItRed() {

609 return

610 setColor(RED);

611 }

612 RedBlackTree blacker() {

613 return

614 setColor(blacker(color()));

615 }

616 RedBlackTree redder() {

617 return

618 setColor(redder(color()));

619 }

620

621 //----------------------------------------

622 // balancing

623

624 Node balance(int c, RedBlackTree t1, K k, V v, RedBlackTree t2) {

625 if ( c == BLACK )

626 return

627 balanceBlack(t1, k, v, t2);

628

629 // DOUBLE_BLACK only used in remove1

630 if ( c == DOUBLE_BLACK )

631 return

632 balanceDoubleBlack(t1, k, v, t2);

633

634 // no balancing at red nodes

635 return

636 set(k, v, c, t1, t2);

637 }

638

639 // Okasaki's rules for insertion balancing

640

641 Node balanceBlack(RedBlackTree l, K k, V v, RedBlackTree r) {

642 // pattern matching with java is pain in the ass

643

644 if ( l.isRed() ) {

645 Node ln = l.node();

646 if ( ln.l.isRed() ) {

647 Node lln = ln.l.node();

648 return

649 build3(RED, lln.l, lln.k, lln.v,

650 lln.r, ln.k, ln.v,

651 ln.r, k, v, r, ln, lln);

652 }

653 if ( ln.r.isRed() ) {

654 Node lrn = ln.r.node();

655 return

656 build3(RED, ln.l, ln.k, ln.v,

657 lrn.l, lrn.k, lrn.v,

658 lrn.r, k, v, r, ln, lrn);

659 }

660 }

661 if ( r.isRed() ) {

662 Node rn = r.node();

663 if ( rn.l.isRed() ) {

664 Node rln = rn.l.node();

665 return

666 build3(RED,

667 l, k, v,

668 rln.l, rln.k, rln.v,

669 rln.r, rn.k, rn.v,

670 rn.r,

671 rln, rn);

672 }

673 if ( rn.r.isRed() ) {

674 Node rrn = rn.r.node();

675 return

676 build3(RED,

677 l, k, v,

678 rn.l, rn.k, rn.v,

679 rrn.l, rrn.k, rrn.v,

680 rrn.r,

681 rrn, rn);

682 }

683 }

684 return

685 set(k, v, BLACK, l, r);

686 }

687

688 Node balanceDoubleBlack(RedBlackTree l, K k, V v, RedBlackTree r) {

689 // same rules as in balanceBlack, double black is absorbed

690

691 if ( l.isRed() ) {

692 Node ln = l.node();

693 if ( ln.l.isRed() ) {

694 Node lln = ln.l.node();

695 return

696 build3(BLACK,

697 lln.l, lln.k, lln.v,

698 lln.r, ln.k, ln.v,

699 ln.r, k, v,

700 r,

701 ln, lln);

702 }

703 if ( ln.r.isRed() ) {

704 Node lrn = ln.r.node();

705 return

706 build3(BLACK,

707 ln.l, ln.k, ln.v,

708 lrn.l, lrn.k, lrn.v,

709 lrn.r, k, v,

710 r,

711 ln, lrn);

712 }

713 }

714 if ( r.isRed() ) {

715 Node rn = r.node();

716 if ( rn.l.isRed() ) {

717 Node rln = rn.l.node();

718 return

719 build3(BLACK,

720 l, k, v,

721 rln.l, rln.k, rln.v,

722 rln.r, rn.k, rn.v,

723 rn.r,

724 rln, rn);

725 }

726 if ( rn.r.isRed() ) {

727 Node rrn = rn.r.node();

728 return

729 build3(BLACK,

730 l, k, v,

731 rn.l, rn.k, rn.v,

732 rrn.l, rrn.k, rrn.v,

733 rrn.r,

734 rrn, rn);

735 }

736 }

737

738 // extra rules for negative black none empty trees

739 if ( r.isNegativeBlack() ) {

740 Node rn = r.node();

741 if ( rn.l.isBlack()

742 &&

743 rn.r.isBlack() ) {

744 Node rln = rn.l.node();

745 return

746 rln.set(rln.k, rln.v, BLACK,

747 set(k, v, BLACK, l, rln.l),

748 rn.balanceBlack(rln.r, rn.k, rn.v, rn.r.paintItRed()));

749 }

750 }

751 if ( l.isNegativeBlack() ) {

752 Node ln = l.node();

753 if ( ln.l.isBlack()

754 &&

755 ln.r.isBlack() ) {

756 Node lrn = ln.r.node();

757 return

758 lrn.set(lrn.k, lrn.v, BLACK,

759 ln.balanceBlack(ln.l.paintItRed(), ln.k, ln.v, lrn.l),

760 set(k, v, BLACK, l, lrn.r));

761 }

762 }

763 return

764 set(k, v, DOUBLE_BLACK, l, r);

765 }

766

767 Node bubble(int c, RedBlackTree l, K k, V v, RedBlackTree r) {

768 if ( l.isDoubleBlack()

769 ||

770 r.isDoubleBlack() ) {

771 return

772 balance(blacker(c), l.redder(), k, v, r.redder());

773 }

774 return

775 balance(c, l, k, v, r);

776 }

777

778 // build 3 nodes from a b c and d with labels x y z

779 // when a destrutive set is used

780 // the root is stored in this

781 // the left node is stored in l

782 // the right node in r

783

784 Node build3(int rootColor,

785 RedBlackTree a, K xk, V xv,

786 RedBlackTree b, K yk, V yv,

787 RedBlackTree c, K zk, V zv,

788 RedBlackTree d,

789 Node l, Node r) {

790 return

791 set(yk, yv, rootColor,

792 l.set(xk, xv, BLACK, a, b),

793 r.set(zk, zv, BLACK, c, d));

794 }

795

796 //----------------------------------------

797 // setter

798

799 private Node set(K k, V v, int c,

800 RedBlackTree l,

801 RedBlackTree r) {

802 /* persistent */

803 if ( k == this.k && v == this.v

804 &&

805 c == this.c

806 &&

807 l == this.l && r == this.r )

808 return

809 this;

810 return

811 new Node(k, v, c, l, r);

812

813 /* destructive *

814 this.k = k;

815 this.v = v;

816 this.c = c;

817 this.l = l;

818 this.r = r;

819 return

820 this;

821 /**/

822 }

823 private Node setV(V v) {

824 /* persistent */

825 return

826 ( v == this.v )

827 ? this

828 : new Node(this.k, v, this.c, this.l, this.r);

829

830 /* destructive *

831 this.v = v;

832 return

833 this;

834 /**/

835 }

836

837 private Node setColor(int c) {

838 /* persistent */

839 return

840 c == this.c

841 ? this

842 : new Node(this.k, this.v, c, this.l, this.r);

843

844 /* destructive *

845 this.c = c;

846 return

847 this;

848 /**/

849 }

850

851 //----------------------------------------

852 // tree manipulation

853

854 RedBlackTree insert1(K k, V v) {

855 switch ( signum(k.compareTo(this.k)) ) {

856 case -1:

857 return

858 balance(c, l.insert1(k, v), this.k, this.v, r);

859 case 0:

860 return

861 setV(v);

862 case +1:

863 return

864 balance(c, l, this.k, this.v, r.insert1(k, v));

865 }

866 // never executed, but required

867 return

868 null;

869 }

870

871 RedBlackTree remove1(K k) {

872 switch ( signum(k.compareTo(this.k)) ) {

873 case -1:

874 return

875 bubble(c, l.remove1(k), this.k, this.v, r);

876 case 0:

877 return

878 removeRoot();

879 //trc("removeRoot",removeRoot());

880 case +1:

881 return

882 bubble(c, l, this.k, this.v, r.remove1(k));

883 }

884 // never executed, but required

885 return

886 null;

887 }

888

889 RedBlackTree removeRoot() {

890 if ( isRed()

891 &&

892 l.isEmpty()

893 &&

894 r.isEmpty()

895 )

896 return

897 empty();

898 if ( isBlack() ) {

899 if ( l.isEmpty()

900 &&

901 r.isEmpty() )

902 return

903 doubleEmpty();

904 if ( l.isRed()

905 &&

906 r.isEmpty() )

907 return

908 l.blacker();

909 if ( r.isRed()

910 &&

911 l.isEmpty() )

912 return

913 r.blacker();

914 }

915 KV p = l.findMax();

916 return

917 bubble(c, l.node().removeMax(), p.fst, p.snd, r);

918 }

919

920 RedBlackTree removeMax() {

921 if ( r.isEmpty() )

922 return

923 removeRoot();

924 return

925 bubble(c, l, k, v, r.node().removeMax());

926 }

927

928 //----------------------------------------

929 // iterators

930

931 // ascending enumeration

932

933 private static

934 class NodeIterator

935 extends ds.util.Iterator<KV> {

936

937 Queue queue;

938

939 NodeIterator(Node n) {

940 queue = Queue.empty();

941 add(n);

942 ++cntIter;

943 }

944

945 void add(Node n) {

946 queue = queue.cons(n);

947 if ( ! n.l.isEmpty() )

948 add(n.l.node()); // downcast

949 }

950

951 void addSubNodes(Node n) {

952 if ( ! n.r.isEmpty() )

953 add(n.r.node());

954 }

955

956 public boolean hasNext() {

957 return

958 ! queue.isEmpty();

959 }

960

961 public KV next() {

962 if ( queue.isEmpty() )

963 return

964 undefined("empty tree");

965

966 Node n = (Node)queue.head();

967 queue = queue.tail();

968 addSubNodes(n);

969 return

970 mkPair(n.k, n.v);

971 }

972 }

973

974 // descending enumeration

975

976 private

977 class NodeIteratorDescending

978 extends NodeIterator {

979

980 NodeIteratorDescending(Node n) {

981 super(n);

982 }

983

984 void add(Node n) {

985 queue = queue.cons(n);

986 if ( ! n.r.isEmpty() )

987 add(n.r.node()); // downcast

988 }

989

990 void addSubNodes(Node n) {

991 if ( ! n.l.isEmpty() )

992 add(n.l.node());

993 }

994 }

995 }

996

997 //----------------------------------------

998 // profiling

999

1000 private static int cntNode = 0;

1001 private static int cntIter = 0;

1002

1003 public static String stats() {

1004 return

1005 "stats for ds.persistent.map.RedBlackTree:\n" +

1006 "# new Node() : " + cntNode + "\n" +

1007 "# new Iterator() : " + cntIter + "\n";

1008 }

1009

1010 public String objStats() {

1011 int s = size();

1012 int o = s;

1013 int f = 5 * s;

1014 int m = o + f;

1015

1016 return

1017 "mem stats for ds.persistent.map.RedBlackTree object:\n" +

1018 "# elements (size) : " + s + "\n" +

1019 "# objects : " + o + "\n" +

1020 "# fields : " + f + "\n" +

1021 "# mem words : " + m + "\n";

1022 }

1023}