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

1package ds.persistent.set;

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

5 Ordered linked lists require a total ordering

6 on the elem domain.

8 This is a PERSISTENT implementation.

9*/

11import ds.interfaces.Set;

13import ds.util.E; // example class for elements

14import ds.util.Invariant;

16import java.util.Iterator;

18import static java.lang.Integer.signum;

19import static ds.util.Undef.undefined;

21public abstract

22 class OrderedList

23 implements Set {

25 //----------------------------------------

26 // the smart constructors

28 // empty list

29 public static OrderedList empty() {

30 return

31 EMPTY;

32 }

34 // singleton list

35 public static OrderedList singleton(E e) {

36 return

37 EMPTY.cons(e);

38 }

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

41 public static

42 OrderedList fromIterator(Iterator<E> elems) {

44 OrderedList res = empty();

45 while ( elems.hasNext() ) {

46 E e = elems.next();

47 res = res.insert(e);

48 }

49 return

50 res;

51 }

53 public abstract OrderedList insert(E e);

54 public abstract OrderedList remove(E e);

55 public abstract OrderedList union(Set m2);

56 public abstract OrderedList intersect(Set m2);

57 public abstract OrderedList difference(Set m2);

59 public Iterator<E> iterator() {

60 ++cntIter;

61 return

62 new ListIterator(this);

63 }

65 public OrderedList copy() {

66 return

67 this;

68 }

70 //----------------------------------------

71 // internal methods

73 // cons

74 protected Node cons(E e) {

75 return

76 new Node(e, this);

77 }

79 // access methods, only legal for Node objects

80 // not defined for Empty object

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

83 E elem() { return nodeExpected(); }

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

86 private static <A> A nodeExpected() {

87 return

88 undefined("Node expected");

89 }

91 //----------------------------------------

92 // the empty list implemented by applying the singleton design pattern

94 // the empty list object

96 private static final OrderedList EMPTY

97 = new Empty();

99 // the singleton class for the empty list object

100

101 private static final

102 class Empty

103 extends OrderedList {

104

105 public boolean isEmpty() {

106 return true;

107 }

108

109 public boolean member(E e) {

110 return false;

111 }

112

113 public int size() {

114 return 0;

115 }

116

117 public E findMin() {

118 nodeExpected();

119 return null;

120 }

121

122 public E findMax() {

123 nodeExpected();

124 return null;

125 }

126

127 public OrderedList insert(E e) {

128 return

129 singleton(e);

130 }

131

132 public OrderedList remove(E e) {

133 return

134 this;

135 }

136

137 public OrderedList union(Set m2) {

138 return

139 (OrderedList)m2;

140 }

141

142 public OrderedList intersect(Set m2) {

143 return

144 this;

145 }

146

147 public OrderedList difference(Set m2) {

148 return

149 this;

150 }

151

152 public boolean inv() {

153 return true;

154 }

155

156 //----------------------------------------

157 // not public stuff

158

159 Empty() { }

160

161 }

162

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

164 // the node class for none empty trees

165

166 private static final

167 class Node

168 extends OrderedList {

169

170 /* persistent */

171 final E e;

172 final OrderedList next;

173

174 /* destructive *

175 E e;

176 OrderedList next;

177 /**/

178

179 Node(E e, OrderedList next) {

180 assert e != null;

181 assert next != null;

182

183 this.e = e;

184 this.next = next;

185 ++cntNode;

186 }

187

188 //----------------------------------------

189 // predicates and attributes

190

191 public boolean isEmpty() {

192 return false;

193 }

194

195 public boolean member(E e) {

196 assert e != null;

197

198 switch (signum(e.compareTo(this.e))) {

199 case -1:

200 return

201 false;

202 case 0:

203 return

204 true;

205 case +1:

206 return

207 next.member(e);

208 }

209 // never executed, but required by javac

210 return

211 false;

212 }

213

214 public int size() {

215 return

216 1 + next.size();

217 }

218

219 public E findMin() {

220 return e;

221 }

222

223 public E findMax() {

224 if ( next.isEmpty() )

225 return e;

226 return

227 next.findMax();

228 }

229

230 public boolean inv() {

231 if ( next.isEmpty() )

232 return

233 true;

234 return

235 e.compareTo(next.elem()) < 0

236 &&

237 next.inv();

238 }

239

240 //----------------------------------------

241 // internal methods

242

243 Node node() { return this; }

244 E elem() { return e; }

245 OrderedList next() { return next; }

246

247 // setter

248

249 private Node setNext(OrderedList next) {

250 /* persistent */

251 if ( next == this.next )

252 return

253 this;

254 return

255 next.cons(this.e);

256

257 /* destructive *

258 this.next = next;

259 return

260 this;

261 /**/

262 }

263

264 //----------------------------------------

265

266 public OrderedList insert(E e) {

267 assert e != null;

268

269 switch ( signum(e.compareTo(this.e)) ) {

270 case -1: // add to the front

271 return

272 this.cons(e);

273 case 0: // already there

274 return

275 this;

276 case +1: // continue search

277 return

278 setNext(next.insert(e));

279 }

280 // never executed, but required by javac

281 return

282 null;

283 }

284

285 public OrderedList remove(E e) {

286 assert e != null;

287

288 switch ( signum(e.compareTo(this.e)) ) {

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

290 return

291 this;

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

293 return

294 next;

295 case +1: // continue search

296 return

297 setNext(next.remove(e));

298 }

299 // never executed, but required by javac

300 return

301 null;

302 }

303

304 public OrderedList union(Set m2) {

305 assert m2 != null;

306

307 OrderedList l2 = (OrderedList)m2;

308

309 if ( l2.isEmpty() )

310 return

311 this;

312

313 Node n2 = l2.node();

314 switch ( signum(n2.e.compareTo(this.e)) ) {

315

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

317 return

318 n2.setNext(union(n2.next));

319

320 case 0: // same elem, ignore head of m2

321 return

322 setNext(next.union(n2.next));

323

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

325 return

326 setNext(next.union(m2));

327 }

328 // never executed, but required by javac

329 return

330 null;

331 }

332

333 public OrderedList intersect(Set m2) {

334 assert m2 != null;

335

336 OrderedList l2 = (OrderedList)m2;

337

338 if ( l2.isEmpty() )

339 return

340 l2;

341

342 Node n2 = l2.node();

343 switch ( signum(n2.e.compareTo(this.e)) ) {

344

345 case -1: // ignore head of m2

346 return

347 intersect(n2.next);

348

349 case 0: // head remains in result

350 return

351 setNext(next.intersect(n2.next));

352

353 case +1: // ignore head

354 return

355 next.intersect(m2);

356 }

357 // never executed, but required by javac

358 return

359 null;

360 }

361

362 public OrderedList difference(Set m2) {

363 assert m2 != null;

364

365 OrderedList l2 = (OrderedList)m2;

366

367 if ( l2.isEmpty() ) // nothing to do

368 return

369 this;

370

371 Node n2 = l2.node();

372 switch ( signum(n2.e.compareTo(this.e)) ) {

373

374 case -1: // ignore head of m2

375 return

376 difference(n2.next);

377

378 case 0: // same elem, remove elem

379 return

380 next.difference(n2.next);

381

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

383 return

384 setNext(next.difference(m2));

385 }

386 // never executed, but required by javac

387 return

388 null;

389 }

390

391 /* destructive *

392 public OrderedList copy() {

393 return

394 next.copy().cons(e);

395 }

396 /**/

397 }

398

399 //----------------------------------------

400 // iterators

401

402 // ascending enumeration

403

404 private static

405 class ListIterator

406 extends ds.util.Iterator<E> {

407

408 OrderedList queue;

409

410 ListIterator(OrderedList n) {

411 assert n != null;

412

413 queue = n;

414 ++cntIter;

415 }

416

417 public boolean hasNext() {

418 return

419 ! queue.isEmpty();

420 }

421

422 public E next() {

423 if ( queue.isEmpty() )

424 return

425 undefined("empty list");

426

427 Node n = queue.node();

428 queue = queue.next();

429 return

430 n.e;

431 }

432 }

433

434 //----------------------------------------

435 // profiling

436

437 private static int cntNode = 0;

438 private static int cntIter = 0;

439

440 public static String stats() {

441 return

442 "stats for ds.persistent.set.OrderedList:\n" +

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

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

445 }

446

447 public String objStats() {

448 int s = size();

449 int o = s;

450 int f = 2 * s;

451 int m = o + f;

452

453 return

454 "mem stats for ds.persistent.set.OrderedList object:\n" +

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

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

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

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

459 }

460}