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

1package ds.persistent.map;

3/** Implementation of maps with ordered single linked lists.

5 Ordered linked lists require a total ordering

6 on the key value. This is reflected by the

7 constraint on the type variable K.

9 This is a PERSISTENT implementation.

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 static ds.util.KV.mkPair;

19import ds.util.Function2;

20import ds.util.Invariant;

21import ds.util.NullIterator;

22import ds.util.Pair;

23import ds.util.Predicate;

25import java.util.Iterator;

27import static java.lang.Integer.signum;

28import static ds.util.Undef.undefined;

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

32public abstract

33 class OrderedList

34 implements Map {

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

37 // the smart constructors

39 // empty list

40 public static OrderedList empty() {

41 return

42 EMPTY;

43 }

45 // singleton list

46 public static OrderedList singleton(K k, V v) {

47 return

48 EMPTY.cons(k, v);

49 }

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

52 public static

53 OrderedList fromIterator(Iterator<KV> elems) {

55 OrderedList res = empty();

56 while ( elems.hasNext() ) {

57 KV p = elems.next();

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

59 }

60 return

61 res;

62 }

64 public boolean member(K k) {

65 return

66 lookup(k) != null;

67 }

69 public abstract OrderedList

70 insert(K k, V v);

72 public abstract OrderedList

73 remove(K k);

75 public OrderedList

76 union(Map m2) {

77 return

78 unionWith(const2, m2);

79 }

81 public abstract OrderedList

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

83 Map m2);

85 public OrderedList

86 difference(Map m2) {

87 return

88 differenceWith(null2, m2);

89 }

91 public abstract OrderedList

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

93 Map m2);

95 public OrderedList copy() {

96 return

97 this;

98 }

100 //----------------------------------------

101 // internal methods

102

103 // getter

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

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

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

107 OrderedList next() { return nodeExpected(); }

108

109 private static <A> A nodeExpected() {

110 return

111 undefined("Node expected");

112 }

113

114 // cons

115 protected

116 Node cons(K k, V v) {

117 return

118 new Node(k, v, this);

119 }

120

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

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

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

124 return y;

125 }

126 };

127

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

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

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

131 return null;

132 }

133 };

134

135 //----------------------------------------

136 // the empty list implemented by applying

137 // the singleton design pattern

138

139 // the "generic" empty list object

140

141 private static final OrderedList EMPTY

142 = new Empty();

143

144 // the singleton class for the empty list object

145

146 private static final

147 class Empty

148 extends OrderedList {

149

150 // predicates and attributes

151 public boolean isEmpty() {

152 return true;

153 }

154

155 public int size() {

156 return 0;

157 }

158

159 public V lookup(K k) {

160 return null;

161 }

162

163 public KV findMin() {

164 return nodeExpected();

165 }

166

167 public KV findMax() {

168 return nodeExpected();

169 }

170

171 public boolean inv() {

172 return true;

173 }

174

175 public Iterator<KV> iterator() {

176 ++cntIter;

177 return

178 new NullIterator<KV>();

179 }

180

181 // tree manipulation

182 public OrderedList insert(K k, V v) {

183 return

184 singleton(k, v);

185 }

186 public OrderedList remove(K k) {

187 return

188 this;

189 }

190

191 public OrderedList

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

193 Map m2) {

194 return

195 (OrderedList)m2;

196 }

197

198 public OrderedList

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

200 Map m2) {

201 return

202 this;

203 }

204

205 //----------------------------------------

206 // not public stuff

207

208 Empty() { }

209

210 }

211

212 //----------------------------------------

213 // the node class for none empty trees

214

215 private static final

216 class Node

217 extends OrderedList {

218

219 /* persistent */

220 final K k;

221 final V v;

222 final OrderedList next;

223

224 /* destructive *

225 K k;

226 V v;

227 OrderedList next;

228 /**/

229

230 Node(K k, V v, OrderedList next) {

231 assert k != null;

232

233 this.k = k;

234 this.v = v;

235 this.next = next;

236 ++cntNode;

237 }

238

239 //----------------------------------------

240 // predicates and attributes

241

242 public boolean isEmpty() {

243 return false;

244 }

245

246 public int size() {

247 return

248 1 + next.size();

249 }

250

251 public V lookup(K k) {

252 assert k != null;

253

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

255 case -1:

256 return

257 null; // not found

258 case 0:

259 return

260 v;

261 case +1:

262 return

263 next.lookup(k);

264 }

265 // never executed, but required by javac

266 return

267 null;

268 }

269

270 public KV findMin() {

271 return

272 mkPair(k, v);

273 }

274

275 public KV findMax() {

276 if ( next.isEmpty() )

277 return

278 mkPair(k, v);

279 return

280 next.findMax();

281 }

282

283 public Iterator<KV> iterator() {

284 ++cntIter;

285 return

286 new NodeIterator(this);

287 }

288

289 public boolean inv() {

290 if ( next.isEmpty() )

291 return

292 true;

293 return

294 k.compareTo(next.key()) < 0

295 &&

296 next.inv();

297 }

298

299 //----------------------------------------

300 // internal methods

301

302 // getter

303

304 Node node() { return this; }

305 K key() { return k; }

306 V value() { return v; }

307 OrderedList next() { return next; }

308

309 // setter

310

311 private Node setNext(OrderedList next) {

312 /* persistent */

313 if ( next == this.next )

314 return

315 this;

316 return

317 next.cons(this.k, this.v);

318

319 /* destructive *

320 this.next = next;

321 return

322 this;

323 /**/

324 }

325

326 private Node setV(V v) {

327 /* persistent */

328 return

329 ( v == this.v )

330 ? this

331 : next.cons(this.k, v);

332

333 /* destructive *

334 this.v = v;

335 return

336 this;

337 /**/

338 }

339

340 //----------------------------------------

341 // tree manipulation

342

343 public OrderedList insert(K k, V v) {

344 assert k != null;

345

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

347 case -1: // add to the front

348 return

349 this.cons(k, v);

350 case 0: // already there: update value

351 return

352 setV(v);

353 case +1: // continue search

354 return

355 setNext(next.insert(k, v));

356 }

357 // never executed, but required by javac

358 return

359 null;

360 }

361

362 public OrderedList remove(K k) {

363 assert k != null;

364

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

366 case -1: // not there: nothing to remove

367 return

368 this;

369 case 0: // found: remove head of list

370 return

371 next;

372 case +1: // continue search

373 return

374 setNext(next.remove(k));

375 }

376 // never executed, but required by javac

377 return

378 null;

379 }

380

381 public OrderedList

382 union(Map m2) {

383 return

384 unionWith(const2, m2);

385 }

386

387 public OrderedList

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

389 Map m2) {

390 if ( m2.isEmpty() )

391 return

392 this;

393

394 Node n2 = ((OrderedList)m2).node();

395 switch ( signum(n2.k.compareTo(this.k)) ) {

396

397 case -1: // add head of m2 to the front of the result

398 return

399 n2.setNext(unionWith(op, n2.next));

400

401 case 0: // same key, ignore head of m2

402 return

403 setV(op.apply(v, n2.v)).setNext(next.unionWith(op, n2.next));

404

405 case +1: // add head to the result and merge tail with m2

406 return

407 setNext(next.unionWith(op, m2));

408 }

409 // never executed, but required by javac

410 return

411 null;

412 }

413

414 public OrderedList

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

416 Map m2) {

417 if ( m2.isEmpty() )

418 return // nothing to do

419 this;

420

421 Node n2 = ((OrderedList)m2).node();

422 switch ( signum(n2.k.compareTo(this.k)) ) {

423

424 case -1: // ignore head of m2

425 return

426 unionWith(op, n2.next);

427

428 case 0: // same key, combine values or remove key

429 V v1 = op.apply(v, n2.v);

430 OrderedList l1 = next.unionWith(op, n2.next);

431 if ( v1 == null )

432 return // remove key

433 l1;

434 return // update value and next

435 setV(v1).setNext(l1);

436

437 case +1: // take head as it is and continue

438 return

439 setNext(next.unionWith(op, m2));

440 }

441 // never executed, but required by javac

442 return

443 null;

444 }

445

446 /* destructive *

447 public OrderedList copy() {

448 return

449 next.copy().cons(k, v);

450 }

451 /**/

452

453 //----------------------------------------

454 // iterators

455

456 // ascending enumeration

457

458 private static

459 class NodeIterator

460 extends ds.util.Iterator<KV> {

461

462 OrderedList queue;

463

464 NodeIterator(Node n) {

465 queue = n;

466 ++cntIter;

467 }

468

469 public boolean hasNext() {

470 return

471 ! queue.isEmpty();

472 }

473

474 public KV next() {

475 if ( queue.isEmpty() )

476 return

477 undefined("empty list");

478

479 Node n = queue.node();

480 queue = queue.next();

481 return

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

483 }

484 }

485 }

486

487 //----------------------------------------

488 // profiling

489

490 private static int cntNode = 0;

491 private static int cntIter = 0;

492

493 public static String stats() {

494 return

495 "stats for ds.persistent.map.OrderedList:\n" +

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

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

498 }

499

500 public String objStats() {

501 int s = size();

502 int o = s;

503 int f = 3 * s;

504 int m = o + f;

505

506 return

507 "mem stats for ds.persistent.map.OrderedList object:\n" +

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

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

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

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

512 }

513}