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

1package ds.persistent.map;

3/** Implementation of maps by a binary Patricia tree.

4 Runtime for lookup, insert and remove is O(1),

5 (it does not depend on the size of the map).

6 This is guaranted by limiting the depth of the tree

7 by the # of bits (32) used for an int value.

9 The keys are restricted to int values

11 This is a PERSISTENT implementation.

12*/

14import ds.persistent.genlist.LinkedList;

16import ds.interfaces.Map;

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

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

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

21import ds.util.Queue; // for iterators

22import ds.util.Function2;

23import ds.util.NullIterator;

25import ds.util.Function2;

26import ds.util.Invariant;

27import ds.util.Pair;

28import ds.util.Predicate;

29import ds.util.NullIterator;

30import ds.util.SingletonIterator;

32import static ds.util.K.mkK;

33import static ds.util.KV.mkPair;

34import static ds.util.Integer.max;

35import static ds.util.Integer.min;

36import static ds.util.Integer.compareUnsigned;

37import static ds.util.Integer.getPrefix;

38import static ds.util.Integer.commonPrefixMask;

39import static ds.util.Integer.matchPrefix;

40import static ds.util.Integer.shorterMask;

41import static ds.util.Integer.toStringBS;

42import static ds.util.Integer.toStringPX;

43import static ds.util.Undef.undefined;

45import java.util.Iterator;

47import static java.lang.Integer.MIN_VALUE;

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

51public abstract

52 class IntMap

53 implements Map {

55 //----------------------------------------

56 // the smart constructors

58 // empty tree

59 public static

60 IntMap empty() {

61 return

62 EMPTY;

63 }

65 // singleton tree

66 public static

67 IntMap singleton(K k, V v) {

68 return

69 new Leaf(k.intValue(), v);

70 }

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

73 public static

74 IntMap fromIterator(Iterator<KV> elems) {

76 IntMap res = empty();

77 while ( elems.hasNext() ) {

78 KV p = elems.next();

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

80 }

81 return

82 res;

83 }

85 //----------------------------------------

86 // public methods

88 public boolean isEmpty() {

89 return false;

90 }

92 public boolean member(K k) {

93 return

94 lookup(k) != null;

95 }

97 public V lookup(K k) {

98 return

99 lookup1(k.intValue());

100 }

101

102 abstract public int depth();

103 abstract public int minDepth();

104

105 public KV findMin() { return leafExpected(); }

106 public KV findMax() { return leafExpected(); }

107

108

109 public abstract IntMap insert(K k, V v);

110 public abstract IntMap remove(K k);

111

112 abstract public

113 IntMap unionWith(Function2<V,V,V> op,

114 Map m2);

115

116 abstract public

117 IntMap differenceWith(Function2<V,V,V> op,

118 Map m2);

119

120 public IntMap union(Map m2) {

121 Function2<V,V,V> op = new Function2<V,V,V>() {

122 public V apply(V v1, V v2) {

123 return

124 v1;

125 }

126 };

127 return

128 unionWith(op, m2);

129 }

130

131 public IntMap difference(Map m2) {

132 Function2<V,V,V> op = new Function2<V,V,V>() {

133 public V apply(V v1, V v2) {

134 return

135 null;

136 }

137 };

138 return

139 differenceWith(op, m2);

140 }

141

142 public String toString() {

143 return

144 iterator().toString();

145 }

146

147 public IntMap copy() {

148 return

149 this;

150 }

151

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

153

154 boolean isLeaf() { return false; }

155 boolean isFork() { return false; }

156

157 // getter

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

159 K value() { return leafExpected(); }

160 IntMap left() { return forkExpected(); }

161 IntMap right() { return forkExpected(); }

162

163 //----------------------------------------

164 // internal methods

165

166 abstract V lookup1(int k);

167

168 Fork getFork() { return forkExpected(); }

169 Leaf getLeaf() { return leafExpected(); }

170

171 private static <A> A leafExpected() {

172 return

173 undefined("Leaf expected");

174 }

175 private static <A> A forkExpected() {

176 return

177 undefined("Fork expected");

178 }

179

180 //----------------------------------------

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

182

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

184

185 private static final IntMap EMPTY

186 = new Empty();

187

188 // the singleton class for the empty list object

189

190 private static final

191 class Empty

192 extends IntMap {

193

194 // predicates and attributes

195 public boolean isEmpty() { return true; }

196 public int size() { return 0; }

197 public int depth() { return 0; }

198 public int minDepth() { return 0; }

199

200 public boolean inv() { return true; }

201 public String toString() { return "<empty>"; }

202

203 public Iterator<KV> iterator() {

204 ++cntIter;

205 return

206 new NullIterator<KV>();

207 }

208

209 V lookup1(int k) {

210 return

211 null;

212 }

213

214 public IntMap insert(K k, V v) {

215 return

216 singleton(k, v);

217 }

218

219 public IntMap remove(K k) {

220 return

221 this;

222 }

223

224 public IntMap unionWith(Function2<V,V,V> op,

225 Map m2) {

226 return

227 (IntMap)m2;

228 }

229

230 public IntMap differenceWith(Function2<V,V,V> op,

231 Map m2) {

232 return

233 this;

234 }

235

236 //----------------------------------------

237 // not public stuff

238

239 Empty() { }

240 }

241

242 //----------------------------------------

243 // the Leaf class for storing a key value pair

244

245 private static final

246 class Leaf

247 extends IntMap {

248

249 final int k;

250

251 /* persistent */

252 final V v;

253

254 /* destructive *

255 V v;

256 /**/

257

258 Leaf(int k, V v) {

259 this.k = k;

260 this.v = v;

261 ++cntLeaf;

262 }

263

264 /* destructive *

265 public IntMap copy() {

266 return

267 new Leaf(k, v);

268 }

269 /**/

270

271 public boolean inv() { return true; }

272 public boolean isLeaf() { return true; }

273 public int depth() { return 1; }

274 public int minDepth() { return 1; }

275 public int size() { return 1; }

276

277 Leaf getLeaf() { return this; }

278

279

280 public KV findMin() {

281 return

282 mkPair(mkK(k), v);

283 }

284

285 public KV findMax() {

286 return

287 findMin();

288 }

289

290 public V lookup1(int k) {

291 return

292 k == this.k

293 ? v

294 : (V)null;

295 }

296

297 public IntMap insert(K k, V v) {

298 int k0 = k.intValue();

299

300 if ( k0 == this.k ) {

301 return

302 setValue(v);

303 }

304 return

305 join(k0, singleton(k, v),

306 this.k, this);

307 }

308

309 public IntMap remove(K k) {

310 if ( k.intValue() == this.k ) {

311 return

312 empty(); // the only place where an empty tree is given back

313 }

314 return

315 this;

316 }

317

318 public IntMap unionWith(Function2<V,V,V> op,

319 Map m) {

320 IntMap m2 = (IntMap)m;

321

322 // case 1: m2 is empty

323

324 if ( m2.isEmpty() )

325 return

326 this;

327

328 // case 2: m2 is a leaf: union of 2 leafs

329 // this is the only case where the op is used

330

331 if ( m2.isLeaf() ) {

332 Leaf l2 = m2.getLeaf();

333 if ( l2.k == this.k )

334 return

335 setValue(op.apply(v, l2.v));

336

337 return

338 join( l2.k, l2,

339 this.k, this);

340 }

341

342 // case 3: m2 is a fork

343 // "insert" this.k and this.v into m2

344

345 Fork f2 = m2.getFork();

346

347 if ( ! matchPrefix(k, f2.prefix, f2.mask) )

348 return

349 join(k, this,

350 f2.prefix, f2);

351

352 if ( (k & f2.mask) != 0 )

353 return

354 f2.setR(unionWith(op, f2.r));

355 return

356 f2.setL(unionWith(op, f2.l));

357 }

358

359 public IntMap differenceWith(Function2<V,V,V> op,

360 Map m) {

361 IntMap m2 = (IntMap)m;

362

363 V v2 = m2.lookup1(k);

364 if ( v2 == null ) // not there, do nothing

365 return

366 this;

367

368 V v1 = op.apply(v, v2); // combine values

369 if ( v1 == null ) // remove leaf

370 return

371 empty();

372

373 // update value

374 return

375 setValue(v1);

376 }

377

378 public Iterator<KV> iterator() {

379 return

380 new SingletonIterator<KV>(mkPair(mkK(k), v));

381 }

382

383 Leaf setValue(V v) {

384 /* persistent */

385 if ( v == this.v ) // nothing will change

386 return

387 this;

388 return

389 new Leaf(k, v);

390 /* destructive *

391 this.v = v;

392 return

393 this;

394 /**/

395 }

396 }

397

398 //----------------------------------------

399

400 private static

401 class Fork

402 extends IntMap {

403

404 final int prefix;

405 final int mask;

406

407 /* persistent */

408 final IntMap l;

409 final IntMap r;

410

411 /* destructive *

412 IntMap l;

413 IntMap r;

414 /**/

415

416 Fork(int prefix, int mask, IntMap l, IntMap r) {

417 this.prefix = prefix;

418 this.mask = mask;

419 this.l = l;

420 this.r = r;

421 ++cntFork;

422 }

423

424 /* destructive *

425 public IntMap copy() {

426 return

427 new Fork(prefix, mask,

428 l.copy(),

429 r.copy());

430 }

431 /**/

432

433

434 boolean isFork() {

435 return true;

436 }

437 Fork getFork() {

438 return this;

439 }

440

441 public boolean inv() {

442 return

443 ! l.isEmpty() && ! r.isEmpty()

444 &&

445 ( compareUnsigned(findMin().fst.intValue(),

446 findMax().fst.intValue()

447 ) < 0 )

448 &&

449 l.inv()

450 &&

451 r.inv();

452 }

453

454 public int size() {

455 return

456 l.size() + r.size();

457 }

458

459 public int depth() {

460 return

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

462 }

463

464 public int minDepth() {

465 return

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

467 }

468

469 V lookup1(int k) {

470 if ( matchPrefix(k, prefix, mask) ) {

471

472 IntMap t1 = (k & mask) != 0 ? r : l;

473 return

474 t1.lookup1(k);

475

476 }

477 return

478 null;

479 }

480

481 public KV findMin() {

482 return

483 l.findMin();

484 }

485

486 public KV findMax() {

487 return

488 r.findMax();

489 }

490

491 public Iterator<KV> iterator() {

492 return

493 new IntMapIteratorAscending(this);

494 }

495

496

497 public IntMap insert(K k, V v) {

498 int k0 = k.intValue();

499

500 if ( ! matchPrefix(k0, prefix, mask) )

501 return

502 join(k0, singleton(k, v),

503 prefix, this);

504

505 if ( (k0 & mask) != 0 )

506 return

507 setR(r.insert(k, v));

508 return

509 setL(l.insert(k, v));

510 }

511

512 public IntMap remove(K k) {

513 int k0 = k.intValue();

514

515 if ( ! matchPrefix(k0, prefix, mask) )

516 return

517 this;

518 if ( (k0 & mask) != 0 ) {

519 IntMap r1 = r.remove(k);

520 if ( r1.isEmpty() ) // no more fork needed

521 return

522 l;

523 return

524 setR(r1);

525 } else {

526 IntMap l1 = l.remove(k);

527 if ( l1.isEmpty() ) // no more fork needed

528 return

529 r;

530 return

531 setL(l1);

532 }

533 }

534

535 public IntMap unionWith(Function2<V,V,V> op,

536 Map m) {

537 IntMap m2 = (IntMap)m;

538

539 // case 1: m2 is empty

540

541 if ( m2.isEmpty() )

542 return

543 this;

544

545 // case 2: m2 is a leaf

546

547 if ( m2.isLeaf() ) {

548 Leaf l2 = m2.getLeaf();

549

550 // "insert" l2.k and l2.v

551 if ( ! matchPrefix(l2.k, prefix, mask) )

552 return

553 join(l2.k, l2, prefix, this);

554

555 if ( (l2.k & mask) != 0 )

556 return

557 setR(r.unionWith(op, m2));

558 return

559 setL(l.unionWith(op, m2));

560 }

561

562 // case 3: two forks must be merged

563

564 Fork f2 = m2.getFork();

565

566 // this fork is nearer by the root than fork f2

567 if ( shorterMask(mask, f2.mask) ) {

568

569 // prefixes don't match, add a fork for storing both subtrees

570 if ( ! matchPrefix(f2.prefix, prefix, mask) )

571 return

572 join(prefix, this, f2.prefix, f2);

573

574 // prefixes match, merge f2 with lefth or right subtree

575 if ( (f2.prefix & mask) == 0 )

576 return

577 setL(l.unionWith(op, f2));

578

579 return

580 setR(r.unionWith(op, f2));

581 }

582

583 // symmetric case, fork f2 is nearer by the root than this

584 if ( shorterMask(f2.mask, mask) ) {

585 if ( ! matchPrefix(prefix, f2.prefix, f2.mask) )

586 return

587 join(f2.prefix, f2, prefix, this);

588 if ( (prefix & f2.mask) == 0 )

589 return

590 f2.setL(f2.l.unionWith(op, this));

591 return

592 f2.setR(f2.r.unionWith(op, this));

593 }

594

595 // masks are equal and prefixes are equal

596 // merge left and right subtrees

597 if ( prefix == f2.prefix )

598 return

599 setL(l.unionWith(op, f2.l)).

600 setR(r.unionWith(op, f2.r));

601

602 // prefixes don't match, join them like in the two 1. subcases above

603 return

604 join(prefix, this, f2.prefix, f2);

605 }

606

607 public IntMap differenceWith(Function2<V,V,V> op,

608 Map m) {

609 IntMap m2 = (IntMap)m;

610

611 // case 1: m2 is empty

612

613 if ( m2.isEmpty() )

614 return

615 this;

616

617 // case 2: m2 is a leaf

618

619 if ( m2.isLeaf() ) {

620 Leaf l2 = m2.getLeaf();

621

622 // "delete" l2.k

623 if ( ! matchPrefix(l2.k, prefix, mask) )

624 // nothing to delete

625 return

626 this;

627

628 // delete l2.k in one of the children

629 if ( (l2.k & mask) != 0)

630 return

631 setR(r.differenceWith(op, m2));

632 return

633 setL(l.differenceWith(op, m2));

634 }

635

636 // case 3: diff with a fork

637

638 Fork f2 = m2.getFork();

639

640 // this for is nearer by the root than fork f2

641 if ( shorterMask(mask, f2.mask) ) {

642

643 // prefixes don't match, nothing to remove

644 if ( ! matchPrefix(f2.prefix, prefix, mask) )

645 return

646 this;

647

648 // prefixes match, remove elements within one of the children

649 if ( (f2.prefix & mask) == 0 )

650 return

651 setL(l.differenceWith(op, f2));

652 return

653 setR(r.differenceWith(op, f2));

654

655 }

656 if ( shorterMask(f2.mask, mask) ) {

657

658 // prefixes don't match, nothing to remove

659 if ( ! matchPrefix(prefix, f2.prefix, f2.mask) )

660 return

661 this;

662

663 // remove all elems given in f2.l

664 if ( (prefix & f2.mask) == 0 )

665 return

666 differenceWith(op, f2.l);

667

668 // remove all elems given in f2.r

669 return

670 differenceWith(op, f2.r);

671

672 }

673

674 // masks and prefixes are equal

675 if ( prefix == f2.prefix )

676 return

677 setL(l.differenceWith(op, f2.l)).

678 setR(r.differenceWith(op, f2.r));

679

680 // prefixes don't match, nothing to remove

681 return

682 this;

683 }

684

685 Fork setL(IntMap l) {

686 /* persistent */

687 if ( l == this.l ) // nothing will change, may occurs with remove

688 return

689 this;

690 return

691 new Fork(prefix, mask, l, this.r);

692 /* destructive *

693 this.l = l;

694 return

695 this;

696 /**/

697 }

698 Fork setR(IntMap r) {

699 /* persistent */

700 if ( r == this.r ) // nothing will change, may occurs with remove

701 return

702 this;

703 return

704 new Fork(prefix, mask, this.l, r);

705 /* destructive *

706 this.r = r;

707 return

708 this;

709 /**/

710 }

711 }

712

713 private static IntMap join(int px1, IntMap t1,

714 int px2, IntMap t2) {

715 int mask = commonPrefixMask(px1, px2);

716 int px = getPrefix(px1, mask);

717

718 if ( (px1 & mask) != 0 )

719 return

720 new Fork(px, mask, t2, t1);

721

722 return

723 new Fork(px, mask, t1, t2);

724 }

725

726 //----------------------------------------

727 // iterators

728

729 private static

730 class IntMapIteratorAscending

731 extends ds.util.Iterator<KV> {

732

733 Queue queue;

734

735 IntMapIteratorAscending(Fork f) {

736 queue = Queue.empty();

737 add(f);

738 ++cntIter;

739 }

740

741 void add(IntMap m) {

742 if ( ! m.isEmpty() )

743 queue = queue.cons(m);

744 }

745

746 void destruct(Fork f) {

747 // insertion is done by taking keys as unsigned int

748 // so for the Fork with the sign bit set

749 // the subtrees are swapped

750

751 if ( f.mask == MIN_VALUE ) {

752 queue = queue.cons(f.l).cons(f.r);

753 } else {

754 queue = queue.cons(f.r).cons(f.l);

755 }

756 }

757

758 public boolean hasNext() {

759 return

760 ! queue.isEmpty();

761 }

762

763 public KV next() {

764 if ( queue.isEmpty() )

765 return

766 undefined("empty IntMap");

767 IntMap m = (IntMap)queue.head();

768 queue = queue.tail();

769 if ( m.isLeaf() ) {

770 Leaf l = m.getLeaf();

771 return

772 mkPair(mkK(l.k), l.v);

773 }

774 assert m.isFork();

775 destruct(m.getFork());

776 return

777 next();

778 }

779 }

780

781 private static

782 class IntMapIteratorDescending

783 extends IntMapIteratorAscending {

784 IntMapIteratorDescending(Fork f) {

785 super(f);

786 }

787

788 void destruct(Fork f) {

789 if ( f.mask == MIN_VALUE ) {

790 queue = queue.cons(f.r).cons(f.l);

791 } else {

792 queue = queue.cons(f.l).cons(f.r);

793 }

794 }

795 }

796

797 //----------------------------------------

798 // test output trees

799

800 static void indent(StringBuffer out, int level) {

801 for (int i = 0; i < level; ++i)

802 out.append(' ');

803 }

804

805 void showIntMap(StringBuffer out, int level) {

806 indent(out, level);

807 if ( this.isEmpty() ) {

808 out.append("Nil\n");

809 return;

810 }

811 if ( this.isLeaf() ) {

812 Leaf l = this.getLeaf();

813 out.append("\"");

814 out.append(toStringBS(l.k));

815 out.append("\"\t");

816 out.append(l.v.toString());

817 out.append("\n");

818 return;

819 }

820 {

821 Fork f = this.getFork();

822 out.append("\"");

823 out.append(toStringPX(f.prefix, f.mask));

824 out.append("\"\n");

825 f.l.showIntMap(out, level + 2);

826 f.r.showIntMap(out, level + 2);

827 }

828 }

829

830 void showIntMap(StringBuffer out, String s) {

831 // out.append(s);

832 // out.append(this.toString());

833 // out.append("\n");

834 showIntMap(out, 0);

835 // out.append("\n");

836 }

837

838 public String showIntMap() {

839 StringBuffer out = new StringBuffer();

840 showIntMap(out, "");

841 return

842 new String(out);

843 }

844

845 //----------------------------------------

846 // profiling

847

848 private static int cntFork = 0;

849 private static int cntLeaf = 0;

850 private static int cntIter = 0;

851

852 public static String stats() {

853 return

854 "stats for ds.persistent.map.IntMap:\n" +

855 "# new Fork() : " + cntFork + "\n" +

856 "# new Leaf() : " + cntLeaf + "\n" +

857 "# new IntMapIterator() : " + cntIter + "\n";

858 }

859

860 public String objStats() {

861 int s = size();

862 int o = s + (s - 1) + 1; // leafs + forks + anchor

863 int l = 2 * s;

864 int f = 4 * (s - 1);

865 int m = o + 1 + l + f;

866

867 return

868 "mem stats for ds.persistent.map.IntMap object:\n" +

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

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

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

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

873 }

874}