Algorithmen & Datenstrukturen mit Java: ds.persistent.queue.BinaryHeap

1package ds.persistent.queue;

3/** Persistent implementation of binary heap tree.

4 Operations manipulating trees always create copies

5 of the objects to be manipulated. This assures, that

6 old trees remains unchanged.

8 Binary heap trees require a total ordering

9 on the priority value.

10*/

12import ds.interfaces.PriorityQueue;

14import ds.util.P; // example class for prios

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

16import ds.util.PV; // prio value pair

18import static ds.util.PV.mkPair;

19import static ds.util.Integer.max;

20import static ds.util.Integer.min;

21import static ds.util.Undef.undefined;

23import java.util.Iterator;

25import static java.lang.Integer.signum;

27//----------------------------------------

29public abstract

30 class BinaryHeap

31 implements PriorityQueue {

33 //----------------------------------------

34 // the smart constructors

36 // empty list

37 public static

38 BinaryHeap empty() {

39 return

40 EMPTY;

41 }

43 // singleton list

44 public static

45 BinaryHeap singleton(P p, V v) {

46 return

47 new Node(p, v, EMPTY, EMPTY);

48 }

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

51 public static

52 BinaryHeap fromIterator(Iterator<PV> elems) {

54 BinaryHeap res = empty();

55 while ( elems.hasNext() ) {

56 PV p = elems.next();

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

58 }

59 return

60 res;

61 }

63 //----------------------------------------

64 // public methods

66 public abstract BinaryHeap insert(P p, V v);

67 public abstract BinaryHeap removeMin();

69 public String toString() {

70 return

71 iterator().toString();

72 }

74 public Iterator<PV> iterator() {

75 return

76 new HeapIterator(this);

77 }

79 public BinaryHeap copy() {

80 return

81 this;

82 }

84 //----------------------------------------

85 // special binary tree methods

87 abstract public int depth();

88 abstract public int minDepth();

90 //----------------------------------------

91 // internal methods

93 // helper

94 abstract boolean childGE(P p);

96 abstract BinaryHeap merge(BinaryHeap h2);

97 abstract BinaryHeap merge2(Node n1);

99 private static <A> A nodeExpected() {

100 return

101 undefined("Node expected");

102 }

103

104 //----------------------------------------

105 // the empty tree implemented by applying

106 // the singleton design pattern

107

108 // the "generic" empty tree object

109

110 private static final BinaryHeap EMPTY

111 = new Empty();

112

113 // the singleton class for the empty tree object

114

115 private static final

116 class Empty

117 extends BinaryHeap {

118

119 // predicates and attributes

120 public boolean isEmpty() {

121 return true;

122 }

123

124 public int size() {

125 return 0;

126 }

127

128 public int depth() {

129 return 0;

130 }

131

132 public int minDepth() {

133 return 0;

134 }

135

136 public PV findMin() {

137 return nodeExpected();

138 }

139

140 public BinaryHeap insert(P p, V v) {

141 return

142 singleton(p, v);

143 }

144

145 public BinaryHeap removeMin() {

146 return nodeExpected();

147 }

148

149 public boolean inv() {

150 return true;

151 }

152

153 //----------------------------------------

154 // not public stuff

155

156 Empty() { }

157

158 boolean childGE(P p) {

159 return true;

160 }

161

162 BinaryHeap merge(BinaryHeap h2) {

163 return h2;

164 }

165 BinaryHeap merge2(Node n1) {

166 return n1;

167 }

168

169 }

170

171 //----------------------------------------

172 // the node class for none empty trees

173

174 private static final

175 class Node

176 extends BinaryHeap {

177

178 /* persistent */

179 final P p;

180 final V v;

181 final BinaryHeap l;

182 final BinaryHeap r;

183

184 /* destructive *

185 P p;

186 V v;

187 BinaryHeap l;

188 BinaryHeap r;

189 /**/

190

191 Node(P p, V v, BinaryHeap l, BinaryHeap r) {

192 assert p != null;

193

194 this.p = p;

195 this.v = v;

196 this.l = l;

197 this.r = r;

198 ++cntNode;

199 }

200

201 //----------------------------------------

202 // predicates and attributes

203

204 public boolean isEmpty() {

205 return false;

206 }

207

208 public int size() {

209 return

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

211 }

212

213 public int depth() {

214 return

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

216 }

217

218 public int minDepth() {

219 return

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

221 }

222

223 public PV findMin() {

224 return

225 mkPair(p, v);

226 }

227

228 public BinaryHeap insert(P p, V v) {

229 return

230 this.merge(singleton(p, v));

231 }

232

233 public BinaryHeap removeMin() {

234 // forget the root

235 return

236 l.merge(r);

237 }

238

239 /* destructive *

240 public BinaryHeap copy() {

241 return

242 new Node(p, v,

243 l.copy(),

244 r.copy());

245 }

246 /**/

247

248 public boolean inv() {

249 return

250 l.childGE(p)

251 &&

252 r.childGE(p)

253 &&

254 l.inv()

255 &&

256 r.inv();

257 }

258

259 //----------------------------------------

260 // internal methods

261

262 // helper for inv

263 boolean childGE(P p) {

264 return

265 this.p.compareTo(p) >= 0;

266 }

267

268 // the workers: merge and join

269 // merge and merge2 simulate double dispatch

270 // over both heaps

271

272 BinaryHeap merge(BinaryHeap h2) {

273 return

274 h2.merge2(this);

275 }

276

277 BinaryHeap merge2(Node n1) {

278 if ( this.p.compareTo(n1.p) <= 0)

279 return

280 this.join(n1);

281 return

282 n1.join(this);

283 }

284

285 BinaryHeap join(Node n2) {

286 return

287 setLR(this.r, this.l.merge(n2));

288 }

289

290 // setter

291

292 private Node setLR(BinaryHeap l, BinaryHeap r) {

293 /* persistent */

294 if ( l == this.l && r == this.r )

295 return

296 this;

297 return

298 new Node(this.p, this.v, l, r);

299

300 /* destructive *

301 this.l = l;

302 this.r = r;

303 return

304 this;

305 /**/

306 }

307

308 } // end Node

309

310 //----------------------------------------

311 // iterator

312 // ascending enumeration

313

314 private static

315 class HeapIterator

316 extends ds.util.Iterator<PV> {

317

318 BinaryHeap queue;

319

320 HeapIterator(BinaryHeap n) {

321 /* persistent */

322 queue = n;

323

324 /* destructive *

325 // we need a copy of the heap,

326 // else the queue is destroied by the iterator

327 queue = n.copy();

328

329 /**/

330 ++cntIter;

331 }

332

333 public boolean hasNext() {

334 return

335 ! queue.isEmpty();

336 }

337

338 public PV next() {

339 if ( queue.isEmpty() )

340 return

341 undefined("empty heap");

342

343 PV res = queue.findMin();

344 queue = queue.removeMin();

345 return

346 res;

347 }

348 } // end HeapIterator

349

350 //----------------------------------------

351 // profiling

352

353 private static int cntNode = 0;

354 private static int cntIter = 0;

355

356 public static String stats() {

357 return

358 "stats for ds.persistent.queue.BinaryHeap:\n" +

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

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

361 }

362

363 public String objStats() {

364 int s = size();

365 int o = s;

366 int f = 4 * s;

367 int m = o + f;

368

369 return

370 "mem stats for ds.persistent.queue.BinaryHeap object:\n" +

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

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

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

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

375 }

376}