1
|
/*
|
2
|
Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
|
3
|
Permission is hereby granted, free of charge, to any person obtaining a copy
|
4
|
of this software and associated documentation files (the "Software"), to deal
|
5
|
in the Software without restriction, including without limitation the rights
|
6
|
to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
|
7
|
copies of the Software, and to permit persons to whom the Software is
|
8
|
furnished to do so, subject to the following conditions:
|
9
|
|
10
|
The above copyright notice and this permission notice shall be included in
|
11
|
all copies or substantial portions of the Software.
|
12
|
|
13
|
THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
|
14
|
IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
|
15
|
FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
|
16
|
AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
|
17
|
LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
|
18
|
OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
|
19
|
SOFTWARE.
|
20
|
*/
|
21
|
|
22
|
using System;
|
23
|
using System.Diagnostics;
|
24
|
using SCG = System.Collections.Generic;
|
25
|
|
26
|
namespace C5
|
27
|
{
|
28
|
/// <summary>
|
29
|
/// A priority queue class based on an interval heap data structure.
|
30
|
/// </summary>
|
31
|
/// <typeparam name="T">The item type</typeparam>
|
32
|
[Serializable]
|
33
|
public class IntervalHeap<T> : CollectionValueBase<T>, IPriorityQueue<T>
|
34
|
{
|
35
|
#region Events
|
36
|
|
37
|
/// <summary>
|
38
|
///
|
39
|
/// </summary>
|
40
|
/// <value></value>
|
41
|
public override EventTypeEnum ListenableEvents { get { return EventTypeEnum.Basic; } }
|
42
|
|
43
|
#endregion
|
44
|
|
45
|
#region Fields
|
46
|
[Serializable]
|
47
|
struct Interval
|
48
|
{
|
49
|
internal T first, last; internal Handle firsthandle, lasthandle;
|
50
|
|
51
|
|
52
|
public override string ToString() { return String.Format("[{0}; {1}]", first, last); }
|
53
|
}
|
54
|
|
55
|
int stamp;
|
56
|
|
57
|
SCG.IComparer<T> comparer;
|
58
|
SCG.IEqualityComparer<T> itemequalityComparer;
|
59
|
|
60
|
Interval[] heap;
|
61
|
|
62
|
int size;
|
63
|
#endregion
|
64
|
|
65
|
#region Util
|
66
|
bool heapifyMin(int i)
|
67
|
{
|
68
|
bool swappedroot = false;
|
69
|
int cell = i, currentmin = cell;
|
70
|
T currentitem = heap[cell].first;
|
71
|
Handle currenthandle = heap[cell].firsthandle;
|
72
|
|
73
|
if (i > 0)
|
74
|
{
|
75
|
T other = heap[cell].last;
|
76
|
if (2 * cell + 1 < size && comparer.Compare(currentitem, other) > 0)
|
77
|
{
|
78
|
swappedroot = true;
|
79
|
Handle otherhandle = heap[cell].lasthandle;
|
80
|
updateLast(cell, currentitem, currenthandle);
|
81
|
currentitem = other;
|
82
|
currenthandle = otherhandle;
|
83
|
}
|
84
|
}
|
85
|
|
86
|
T minitem = currentitem;
|
87
|
Handle minhandle = currenthandle;
|
88
|
|
89
|
while (true)
|
90
|
{
|
91
|
int l = 2 * cell + 1, r = l + 1;
|
92
|
T lv, rv;
|
93
|
|
94
|
if (2 * l < size && comparer.Compare(lv = heap[l].first, minitem) < 0)
|
95
|
{ currentmin = l; minitem = lv; }
|
96
|
|
97
|
if (2 * r < size && comparer.Compare(rv = heap[r].first, minitem) < 0)
|
98
|
{ currentmin = r; minitem = rv; }
|
99
|
|
100
|
if (currentmin == cell)
|
101
|
break;
|
102
|
|
103
|
minhandle = heap[currentmin].firsthandle;
|
104
|
updateFirst(cell, minitem, minhandle);
|
105
|
cell = currentmin;
|
106
|
|
107
|
//Maybe swap first and last
|
108
|
T other = heap[cell].last;
|
109
|
if (2 * currentmin + 1 < size && comparer.Compare(currentitem, other) > 0)
|
110
|
{
|
111
|
Handle otherhandle = heap[cell].lasthandle;
|
112
|
updateLast(cell, currentitem, currenthandle);
|
113
|
currentitem = other;
|
114
|
currenthandle = otherhandle;
|
115
|
}
|
116
|
|
117
|
|
118
|
minitem = currentitem;
|
119
|
minhandle = currenthandle;
|
120
|
}
|
121
|
|
122
|
if (cell != i || swappedroot)
|
123
|
updateFirst(cell, minitem, minhandle);
|
124
|
return swappedroot;
|
125
|
}
|
126
|
|
127
|
|
128
|
bool heapifyMax(int i)
|
129
|
{
|
130
|
bool swappedroot = false;
|
131
|
int cell = i, currentmax = cell;
|
132
|
T currentitem = heap[cell].last;
|
133
|
Handle currenthandle = heap[cell].lasthandle;
|
134
|
|
135
|
if (i > 0)
|
136
|
{
|
137
|
T other = heap[cell].first;
|
138
|
if (comparer.Compare(currentitem, other) < 0)
|
139
|
{
|
140
|
swappedroot = true;
|
141
|
Handle otherhandle = heap[cell].firsthandle;
|
142
|
updateFirst(cell, currentitem, currenthandle);
|
143
|
currentitem = other;
|
144
|
currenthandle = otherhandle;
|
145
|
}
|
146
|
}
|
147
|
|
148
|
T maxitem = currentitem;
|
149
|
Handle maxhandle = currenthandle;
|
150
|
|
151
|
while (true)
|
152
|
{
|
153
|
int l = 2 * cell + 1, r = l + 1;
|
154
|
T lv, rv;
|
155
|
|
156
|
if (2 * l + 1 < size && comparer.Compare(lv = heap[l].last, maxitem) > 0)
|
157
|
{ currentmax = l; maxitem = lv; }
|
158
|
|
159
|
if (2 * r + 1 < size && comparer.Compare(rv = heap[r].last, maxitem) > 0)
|
160
|
{ currentmax = r; maxitem = rv; }
|
161
|
|
162
|
if (currentmax == cell)
|
163
|
break;
|
164
|
|
165
|
maxhandle = heap[currentmax].lasthandle;
|
166
|
updateLast(cell, maxitem, maxhandle);
|
167
|
cell = currentmax;
|
168
|
|
169
|
//Maybe swap first and last
|
170
|
T other = heap[cell].first;
|
171
|
if (comparer.Compare(currentitem, other) < 0)
|
172
|
{
|
173
|
Handle otherhandle = heap[cell].firsthandle;
|
174
|
updateFirst(cell, currentitem, currenthandle);
|
175
|
currentitem = other;
|
176
|
currenthandle = otherhandle;
|
177
|
}
|
178
|
|
179
|
maxitem = currentitem;
|
180
|
maxhandle = currenthandle;
|
181
|
}
|
182
|
|
183
|
if (cell != i || swappedroot) //Check could be better?
|
184
|
updateLast(cell, maxitem, maxhandle);
|
185
|
return swappedroot;
|
186
|
}
|
187
|
|
188
|
|
189
|
void bubbleUpMin(int i)
|
190
|
{
|
191
|
if (i > 0)
|
192
|
{
|
193
|
T min = heap[i].first, iv = min;
|
194
|
Handle minhandle = heap[i].firsthandle;
|
195
|
int p = (i + 1) / 2 - 1;
|
196
|
|
197
|
while (i > 0)
|
198
|
{
|
199
|
if (comparer.Compare(iv, min = heap[p = (i + 1) / 2 - 1].first) < 0)
|
200
|
{
|
201
|
updateFirst(i, min, heap[p].firsthandle);
|
202
|
min = iv;
|
203
|
i = p;
|
204
|
}
|
205
|
else
|
206
|
break;
|
207
|
}
|
208
|
|
209
|
updateFirst(i, iv, minhandle);
|
210
|
}
|
211
|
}
|
212
|
|
213
|
|
214
|
void bubbleUpMax(int i)
|
215
|
{
|
216
|
if (i > 0)
|
217
|
{
|
218
|
T max = heap[i].last, iv = max;
|
219
|
Handle maxhandle = heap[i].lasthandle;
|
220
|
int p = (i + 1) / 2 - 1;
|
221
|
|
222
|
while (i > 0)
|
223
|
{
|
224
|
if (comparer.Compare(iv, max = heap[p = (i + 1) / 2 - 1].last) > 0)
|
225
|
{
|
226
|
updateLast(i, max, heap[p].lasthandle);
|
227
|
max = iv;
|
228
|
i = p;
|
229
|
}
|
230
|
else
|
231
|
break;
|
232
|
}
|
233
|
|
234
|
updateLast(i, iv, maxhandle);
|
235
|
|
236
|
}
|
237
|
}
|
238
|
|
239
|
#endregion
|
240
|
|
241
|
#region Constructors
|
242
|
/// <summary>
|
243
|
/// Create an interval heap with natural item comparer and default initial capacity (16)
|
244
|
/// </summary>
|
245
|
public IntervalHeap() : this(16) { }
|
246
|
|
247
|
|
248
|
/// <summary>
|
249
|
/// Create an interval heap with external item comparer and default initial capacity (16)
|
250
|
/// </summary>
|
251
|
/// <param name="comparer">The external comparer</param>
|
252
|
public IntervalHeap(SCG.IComparer<T> comparer) : this(16, comparer) { }
|
253
|
|
254
|
|
255
|
//TODO: maybe remove
|
256
|
/// <summary>
|
257
|
/// Create an interval heap with natural item comparer and prescribed initial capacity
|
258
|
/// </summary>
|
259
|
/// <param name="capacity">The initial capacity</param>
|
260
|
public IntervalHeap(int capacity) : this(capacity, Comparer<T>.Default, EqualityComparer<T>.Default) { }
|
261
|
|
262
|
|
263
|
/// <summary>
|
264
|
/// Create an interval heap with external item comparer and prescribed initial capacity
|
265
|
/// </summary>
|
266
|
/// <param name="comparer">The external comparer</param>
|
267
|
/// <param name="capacity">The initial capacity</param>
|
268
|
public IntervalHeap(int capacity, SCG.IComparer<T> comparer) : this(capacity, comparer, new ComparerZeroHashCodeEqualityComparer<T>(comparer)) { }
|
269
|
|
270
|
IntervalHeap(int capacity, SCG.IComparer<T> comparer, SCG.IEqualityComparer<T> itemequalityComparer)
|
271
|
{
|
272
|
if (comparer == null)
|
273
|
throw new NullReferenceException("Item comparer cannot be null");
|
274
|
if (itemequalityComparer == null)
|
275
|
throw new NullReferenceException("Item equality comparer cannot be null");
|
276
|
this.comparer = comparer;
|
277
|
this.itemequalityComparer = itemequalityComparer;
|
278
|
int length = 1;
|
279
|
while (length < capacity) length <<= 1;
|
280
|
heap = new Interval[length];
|
281
|
}
|
282
|
|
283
|
#endregion
|
284
|
|
285
|
#region IPriorityQueue<T> Members
|
286
|
|
287
|
/// <summary>
|
288
|
/// Find the current least item of this priority queue.
|
289
|
/// <exception cref="NoSuchItemException"/> if queue is empty
|
290
|
/// </summary>
|
291
|
/// <returns>The least item.</returns>
|
292
|
[Tested]
|
293
|
public T FindMin()
|
294
|
{
|
295
|
if (size == 0)
|
296
|
throw new NoSuchItemException();
|
297
|
|
298
|
return heap[0].first;
|
299
|
}
|
300
|
|
301
|
|
302
|
/// <summary>
|
303
|
/// Remove the least item from this priority queue.
|
304
|
/// <exception cref="NoSuchItemException"/> if queue is empty
|
305
|
/// </summary>
|
306
|
/// <returns>The removed item.</returns>
|
307
|
[Tested]
|
308
|
public T DeleteMin()
|
309
|
{
|
310
|
IPriorityQueueHandle<T> handle = null;
|
311
|
return DeleteMin(out handle);
|
312
|
}
|
313
|
|
314
|
|
315
|
/// <summary>
|
316
|
/// Find the current largest item of this priority queue.
|
317
|
/// <exception cref="NoSuchItemException"/> if queue is empty
|
318
|
/// </summary>
|
319
|
/// <returns>The largest item.</returns>
|
320
|
[Tested]
|
321
|
public T FindMax()
|
322
|
{
|
323
|
if (size == 0)
|
324
|
throw new NoSuchItemException("Heap is empty");
|
325
|
else if (size == 1)
|
326
|
return heap[0].first;
|
327
|
else
|
328
|
return heap[0].last;
|
329
|
}
|
330
|
|
331
|
|
332
|
/// <summary>
|
333
|
/// Remove the largest item from this priority queue.
|
334
|
/// <exception cref="NoSuchItemException"/> if queue is empty
|
335
|
/// </summary>
|
336
|
/// <returns>The removed item.</returns>
|
337
|
[Tested]
|
338
|
public T DeleteMax()
|
339
|
{
|
340
|
IPriorityQueueHandle<T> handle = null;
|
341
|
return DeleteMax(out handle);
|
342
|
}
|
343
|
|
344
|
|
345
|
/// <summary>
|
346
|
/// The comparer object supplied at creation time for this collection
|
347
|
/// </summary>
|
348
|
/// <value>The comparer</value>
|
349
|
public SCG.IComparer<T> Comparer { get { return comparer; } }
|
350
|
|
351
|
#endregion
|
352
|
|
353
|
#region IExtensible<T> Members
|
354
|
|
355
|
/// <summary>
|
356
|
/// If true any call of an updating operation will throw an
|
357
|
/// <code>ReadOnlyCollectionException</code>
|
358
|
/// </summary>
|
359
|
/// <value>True if this collection is read-only.</value>
|
360
|
public bool IsReadOnly { get { return false; } }
|
361
|
|
362
|
/// <summary>
|
363
|
///
|
364
|
/// </summary>
|
365
|
/// <value>True since this collection has bag semantics</value>
|
366
|
[Tested]
|
367
|
public bool AllowsDuplicates { [Tested]get { return true; } }
|
368
|
|
369
|
/// <summary>
|
370
|
/// Value is null since this collection has no equality concept for its items.
|
371
|
/// </summary>
|
372
|
/// <value></value>
|
373
|
public virtual SCG.IEqualityComparer<T> EqualityComparer { get { return itemequalityComparer; } }
|
374
|
|
375
|
/// <summary>
|
376
|
/// By convention this is true for any collection with set semantics.
|
377
|
/// </summary>
|
378
|
/// <value>True if only one representative of a group of equal items
|
379
|
/// is kept in the collection together with the total count.</value>
|
380
|
public virtual bool DuplicatesByCounting { get { return false; } }
|
381
|
|
382
|
|
383
|
|
384
|
/// <summary>
|
385
|
/// Add an item to this priority queue.
|
386
|
/// </summary>
|
387
|
/// <param name="item">The item to add.</param>
|
388
|
/// <returns>True</returns>
|
389
|
[Tested]
|
390
|
public bool Add(T item)
|
391
|
{
|
392
|
stamp++;
|
393
|
if (add(null, item))
|
394
|
{
|
395
|
raiseItemsAdded(item, 1);
|
396
|
raiseCollectionChanged();
|
397
|
return true;
|
398
|
}
|
399
|
return false;
|
400
|
}
|
401
|
|
402
|
private bool add(Handle itemhandle, T item)
|
403
|
{
|
404
|
if (size == 0)
|
405
|
{
|
406
|
size = 1;
|
407
|
updateFirst(0, item, itemhandle);
|
408
|
return true;
|
409
|
}
|
410
|
|
411
|
if (size == 2 * heap.Length)
|
412
|
{
|
413
|
Interval[] newheap = new Interval[2 * heap.Length];
|
414
|
|
415
|
Array.Copy(heap, newheap, heap.Length);
|
416
|
heap = newheap;
|
417
|
}
|
418
|
|
419
|
if (size % 2 == 0)
|
420
|
{
|
421
|
int i = size / 2, p = (i + 1) / 2 - 1;
|
422
|
T tmp = heap[p].last;
|
423
|
|
424
|
if (comparer.Compare(item, tmp) > 0)
|
425
|
{
|
426
|
updateFirst(i, tmp, heap[p].lasthandle);
|
427
|
updateLast(p, item, itemhandle);
|
428
|
bubbleUpMax(p);
|
429
|
}
|
430
|
else
|
431
|
{
|
432
|
updateFirst(i, item, itemhandle);
|
433
|
|
434
|
if (comparer.Compare(item, heap[p].first) < 0)
|
435
|
bubbleUpMin(i);
|
436
|
}
|
437
|
}
|
438
|
else
|
439
|
{
|
440
|
int i = size / 2;
|
441
|
T other = heap[i].first;
|
442
|
|
443
|
if (comparer.Compare(item, other) < 0)
|
444
|
{
|
445
|
updateLast(i, other, heap[i].firsthandle);
|
446
|
updateFirst(i, item, itemhandle);
|
447
|
bubbleUpMin(i);
|
448
|
}
|
449
|
else
|
450
|
{
|
451
|
updateLast(i, item, itemhandle);
|
452
|
bubbleUpMax(i);
|
453
|
}
|
454
|
}
|
455
|
size++;
|
456
|
|
457
|
return true;
|
458
|
}
|
459
|
|
460
|
private void updateLast(int cell, T item, Handle handle)
|
461
|
{
|
462
|
heap[cell].last = item;
|
463
|
if (handle != null)
|
464
|
handle.index = 2 * cell + 1;
|
465
|
heap[cell].lasthandle = handle;
|
466
|
}
|
467
|
|
468
|
private void updateFirst(int cell, T item, Handle handle)
|
469
|
{
|
470
|
heap[cell].first = item;
|
471
|
if (handle != null)
|
472
|
handle.index = 2 * cell;
|
473
|
heap[cell].firsthandle = handle;
|
474
|
}
|
475
|
|
476
|
|
477
|
/// <summary>
|
478
|
/// Add the elements from another collection with a more specialized item type
|
479
|
/// to this collection.
|
480
|
/// </summary>
|
481
|
/// <typeparam name="U">The type of items to add</typeparam>
|
482
|
/// <param name="items">The items to add</param>
|
483
|
[Tested]
|
484
|
public void AddAll<U>(SCG.IEnumerable<U> items) where U : T
|
485
|
{
|
486
|
stamp++;
|
487
|
int oldsize = size;
|
488
|
foreach (T item in items)
|
489
|
add(null, item);
|
490
|
if (size != oldsize)
|
491
|
{
|
492
|
if ((ActiveEvents & EventTypeEnum.Added) != 0)
|
493
|
foreach (T item in items)
|
494
|
raiseItemsAdded(item, 1);
|
495
|
raiseCollectionChanged();
|
496
|
}
|
497
|
}
|
498
|
|
499
|
#endregion
|
500
|
|
501
|
#region ICollection<T> members
|
502
|
|
503
|
/// <summary>
|
504
|
///
|
505
|
/// </summary>
|
506
|
/// <value>True if this collection is empty.</value>
|
507
|
[Tested]
|
508
|
public override bool IsEmpty { [Tested]get { return size == 0; } }
|
509
|
|
510
|
/// <summary>
|
511
|
///
|
512
|
/// </summary>
|
513
|
/// <value>The size of this collection</value>
|
514
|
[Tested]
|
515
|
public override int Count { [Tested]get { return size; } }
|
516
|
|
517
|
|
518
|
/// <summary>
|
519
|
/// The value is symbolic indicating the type of asymptotic complexity
|
520
|
/// in terms of the size of this collection (worst-case or amortized as
|
521
|
/// relevant).
|
522
|
/// </summary>
|
523
|
/// <value>A characterization of the speed of the
|
524
|
/// <code>Count</code> property in this collection.</value>
|
525
|
public override Speed CountSpeed { get { return Speed.Constant; } }
|
526
|
|
527
|
/// <summary>
|
528
|
/// Choose some item of this collection.
|
529
|
/// </summary>
|
530
|
/// <exception cref="NoSuchItemException">if collection is empty.</exception>
|
531
|
/// <returns></returns>
|
532
|
public override T Choose()
|
533
|
{
|
534
|
if (size == 0)
|
535
|
throw new NoSuchItemException("Collection is empty");
|
536
|
return heap[0].first;
|
537
|
}
|
538
|
|
539
|
|
540
|
/// <summary>
|
541
|
/// Create an enumerator for the collection
|
542
|
/// <para>Note: the enumerator does *not* enumerate the items in sorted order,
|
543
|
/// but in the internal table order.</para>
|
544
|
/// </summary>
|
545
|
/// <returns>The enumerator(SIC)</returns>
|
546
|
[Tested]
|
547
|
public override SCG.IEnumerator<T> GetEnumerator()
|
548
|
{
|
549
|
int mystamp = stamp;
|
550
|
for (int i = 0; i < size; i++)
|
551
|
{
|
552
|
if (mystamp != stamp) throw new CollectionModifiedException();
|
553
|
yield return i % 2 == 0 ? heap[i >> 1].first : heap[i >> 1].last;
|
554
|
}
|
555
|
yield break;
|
556
|
}
|
557
|
|
558
|
|
559
|
#endregion
|
560
|
|
561
|
#region Diagnostics
|
562
|
private bool check(int i, T min, T max)
|
563
|
{
|
564
|
bool retval = true;
|
565
|
Interval interval = heap[i];
|
566
|
T first = interval.first, last = interval.last;
|
567
|
|
568
|
if (2 * i + 1 == size)
|
569
|
{
|
570
|
if (comparer.Compare(min, first) > 0)
|
571
|
{
|
572
|
Console.WriteLine("Cell {0}: parent.first({1}) > first({2}) [size={3}]", i, min, first, size);
|
573
|
retval = false;
|
574
|
}
|
575
|
|
576
|
if (comparer.Compare(first, max) > 0)
|
577
|
{
|
578
|
Console.WriteLine("Cell {0}: first({1}) > parent.last({2}) [size={3}]", i, first, max, size);
|
579
|
retval = false;
|
580
|
}
|
581
|
if (interval.firsthandle != null && interval.firsthandle.index != 2 * i)
|
582
|
{
|
583
|
Console.WriteLine("Cell {0}: firsthandle.index({1}) != 2*cell({2}) [size={3}]", i, interval.firsthandle.index, 2 * i, size);
|
584
|
retval = false;
|
585
|
}
|
586
|
|
587
|
return retval;
|
588
|
}
|
589
|
else
|
590
|
{
|
591
|
if (comparer.Compare(min, first) > 0)
|
592
|
{
|
593
|
Console.WriteLine("Cell {0}: parent.first({1}) > first({2}) [size={3}]", i, min, first, size);
|
594
|
retval = false;
|
595
|
}
|
596
|
|
597
|
if (comparer.Compare(first, last) > 0)
|
598
|
{
|
599
|
Console.WriteLine("Cell {0}: first({1}) > last({2}) [size={3}]", i, first, last, size);
|
600
|
retval = false;
|
601
|
}
|
602
|
|
603
|
if (comparer.Compare(last, max) > 0)
|
604
|
{
|
605
|
Console.WriteLine("Cell {0}: last({1}) > parent.last({2}) [size={3}]", i, last, max, size);
|
606
|
retval = false;
|
607
|
}
|
608
|
if (interval.firsthandle != null && interval.firsthandle.index != 2 * i)
|
609
|
{
|
610
|
Console.WriteLine("Cell {0}: firsthandle.index({1}) != 2*cell({2}) [size={3}]", i, interval.firsthandle.index, 2 * i, size);
|
611
|
retval = false;
|
612
|
}
|
613
|
if (interval.lasthandle != null && interval.lasthandle.index != 2 * i + 1)
|
614
|
{
|
615
|
Console.WriteLine("Cell {0}: lasthandle.index({1}) != 2*cell+1({2}) [size={3}]", i, interval.lasthandle.index, 2 * i + 1, size);
|
616
|
retval = false;
|
617
|
}
|
618
|
|
619
|
int l = 2 * i + 1, r = l + 1;
|
620
|
|
621
|
if (2 * l < size)
|
622
|
retval = retval && check(l, first, last);
|
623
|
|
624
|
if (2 * r < size)
|
625
|
retval = retval && check(r, first, last);
|
626
|
}
|
627
|
|
628
|
return retval;
|
629
|
}
|
630
|
|
631
|
|
632
|
/// <summary>
|
633
|
/// Check the integrity of the internal data structures of this collection.
|
634
|
/// Only avaliable in DEBUG builds???
|
635
|
/// </summary>
|
636
|
/// <returns>True if check does not fail.</returns>
|
637
|
[Tested]
|
638
|
public bool Check()
|
639
|
{
|
640
|
if (size == 0)
|
641
|
return true;
|
642
|
|
643
|
if (size == 1)
|
644
|
return (object)(heap[0].first) != null;
|
645
|
|
646
|
return check(0, heap[0].first, heap[0].last);
|
647
|
}
|
648
|
|
649
|
#endregion
|
650
|
|
651
|
#region IPriorityQueue<T> Members
|
652
|
|
653
|
[Serializable]
|
654
|
class Handle : IPriorityQueueHandle<T>
|
655
|
{
|
656
|
/// <summary>
|
657
|
/// To save space, the index is 2*cell for heap[cell].first, and 2*cell+1 for heap[cell].last
|
658
|
/// </summary>
|
659
|
internal int index = -1;
|
660
|
|
661
|
public override string ToString()
|
662
|
{
|
663
|
return String.Format("[{0}]", index);
|
664
|
}
|
665
|
|
666
|
}
|
667
|
|
668
|
/// <summary>
|
669
|
/// Get or set the item corresponding to a handle.
|
670
|
/// </summary>
|
671
|
/// <exception cref="InvalidPriorityQueueHandleException">if the handle is invalid for this queue</exception>
|
672
|
/// <param name="handle">The reference into the heap</param>
|
673
|
/// <returns></returns>
|
674
|
[Tested]
|
675
|
public T this[IPriorityQueueHandle<T> handle]
|
676
|
{
|
677
|
get
|
678
|
{
|
679
|
int cell;
|
680
|
bool isfirst;
|
681
|
checkHandle(handle, out cell, out isfirst);
|
682
|
|
683
|
return isfirst ? heap[cell].first : heap[cell].last;
|
684
|
}
|
685
|
set
|
686
|
{
|
687
|
Replace(handle, value);
|
688
|
}
|
689
|
}
|
690
|
|
691
|
|
692
|
/// <summary>
|
693
|
/// Check safely if a handle is valid for this queue and if so, report the corresponding queue item.
|
694
|
/// </summary>
|
695
|
/// <param name="handle">The handle to check</param>
|
696
|
/// <param name="item">If the handle is valid this will contain the corresponding item on output.</param>
|
697
|
/// <returns>True if the handle is valid.</returns>
|
698
|
public bool Find(IPriorityQueueHandle<T> handle, out T item)
|
699
|
{
|
700
|
Handle myhandle = handle as Handle;
|
701
|
if (myhandle == null)
|
702
|
{
|
703
|
item = default(T);
|
704
|
return false;
|
705
|
}
|
706
|
int toremove = myhandle.index;
|
707
|
int cell = toremove / 2;
|
708
|
bool isfirst = toremove % 2 == 0;
|
709
|
{
|
710
|
if (toremove == -1 || toremove >= size)
|
711
|
{
|
712
|
item = default(T);
|
713
|
return false;
|
714
|
}
|
715
|
Handle actualhandle = isfirst ? heap[cell].firsthandle : heap[cell].lasthandle;
|
716
|
if (actualhandle != myhandle)
|
717
|
{
|
718
|
item = default(T);
|
719
|
return false;
|
720
|
}
|
721
|
}
|
722
|
item = isfirst ? heap[cell].first : heap[cell].last;
|
723
|
return true;
|
724
|
}
|
725
|
|
726
|
|
727
|
/// <summary>
|
728
|
/// Add an item to the priority queue, receiving a
|
729
|
/// handle for the item in the queue,
|
730
|
/// or reusing an already existing handle.
|
731
|
/// </summary>
|
732
|
/// <param name="handle">On output: a handle for the added item.
|
733
|
/// On input: null for allocating a new handle, an invalid handle for reuse.
|
734
|
/// A handle for reuse must be compatible with this priority queue,
|
735
|
/// by being created by a priority queue of the same runtime type, but not
|
736
|
/// necessarily the same priority queue object.</param>
|
737
|
/// <param name="item">The item to add.</param>
|
738
|
/// <returns>True since item will always be added unless the call throws an exception.</returns>
|
739
|
[Tested]
|
740
|
public bool Add(ref IPriorityQueueHandle<T> handle, T item)
|
741
|
{
|
742
|
stamp++;
|
743
|
Handle myhandle = (Handle)handle;
|
744
|
if (myhandle == null)
|
745
|
handle = myhandle = new Handle();
|
746
|
else
|
747
|
if (myhandle.index != -1)
|
748
|
throw new InvalidPriorityQueueHandleException("Handle not valid for reuse");
|
749
|
if (add(myhandle, item))
|
750
|
{
|
751
|
raiseItemsAdded(item, 1);
|
752
|
raiseCollectionChanged();
|
753
|
return true;
|
754
|
}
|
755
|
return false;
|
756
|
}
|
757
|
|
758
|
/// <summary>
|
759
|
/// Delete an item with a handle from a priority queue.
|
760
|
/// </summary>
|
761
|
/// <exception cref="InvalidPriorityQueueHandleException">if the handle is invalid</exception>
|
762
|
/// <param name="handle">The handle for the item. The handle will be invalidated, but reusable.</param>
|
763
|
/// <returns>The deleted item</returns>
|
764
|
[Tested]
|
765
|
public T Delete(IPriorityQueueHandle<T> handle)
|
766
|
{
|
767
|
stamp++;
|
768
|
int cell;
|
769
|
bool isfirst;
|
770
|
Handle myhandle = checkHandle(handle, out cell, out isfirst);
|
771
|
|
772
|
T retval;
|
773
|
myhandle.index = -1;
|
774
|
int lastcell = (size - 1) / 2;
|
775
|
|
776
|
if (cell == lastcell)
|
777
|
{
|
778
|
if (isfirst)
|
779
|
{
|
780
|
retval = heap[cell].first;
|
781
|
if (size % 2 == 0)
|
782
|
{
|
783
|
updateFirst(cell, heap[cell].last, heap[cell].lasthandle);
|
784
|
heap[cell].last = default(T);
|
785
|
heap[cell].lasthandle = null;
|
786
|
}
|
787
|
else
|
788
|
{
|
789
|
heap[cell].first = default(T);
|
790
|
heap[cell].firsthandle = null;
|
791
|
}
|
792
|
}
|
793
|
else
|
794
|
{
|
795
|
retval = heap[cell].last;
|
796
|
heap[cell].last = default(T);
|
797
|
heap[cell].lasthandle = null;
|
798
|
}
|
799
|
size--;
|
800
|
}
|
801
|
else if (isfirst)
|
802
|
{
|
803
|
retval = heap[cell].first;
|
804
|
|
805
|
if (size % 2 == 0)
|
806
|
{
|
807
|
updateFirst(cell, heap[lastcell].last, heap[lastcell].lasthandle);
|
808
|
heap[lastcell].last = default(T);
|
809
|
heap[lastcell].lasthandle = null;
|
810
|
}
|
811
|
else
|
812
|
{
|
813
|
updateFirst(cell, heap[lastcell].first, heap[lastcell].firsthandle);
|
814
|
heap[lastcell].first = default(T);
|
815
|
heap[lastcell].firsthandle = null;
|
816
|
}
|
817
|
|
818
|
size--;
|
819
|
if (heapifyMin(cell))
|
820
|
bubbleUpMax(cell);
|
821
|
else
|
822
|
bubbleUpMin(cell);
|
823
|
}
|
824
|
else
|
825
|
{
|
826
|
retval = heap[cell].last;
|
827
|
|
828
|
if (size % 2 == 0)
|
829
|
{
|
830
|
updateLast(cell, heap[lastcell].last, heap[lastcell].lasthandle);
|
831
|
heap[lastcell].last = default(T);
|
832
|
heap[lastcell].lasthandle = null;
|
833
|
}
|
834
|
else
|
835
|
{
|
836
|
updateLast(cell, heap[lastcell].first, heap[lastcell].firsthandle);
|
837
|
heap[lastcell].first = default(T);
|
838
|
heap[lastcell].firsthandle = null;
|
839
|
}
|
840
|
|
841
|
size--;
|
842
|
if (heapifyMax(cell))
|
843
|
bubbleUpMin(cell);
|
844
|
else
|
845
|
bubbleUpMax(cell);
|
846
|
}
|
847
|
|
848
|
raiseItemsRemoved(retval, 1);
|
849
|
raiseCollectionChanged();
|
850
|
|
851
|
return retval;
|
852
|
}
|
853
|
|
854
|
private Handle checkHandle(IPriorityQueueHandle<T> handle, out int cell, out bool isfirst)
|
855
|
{
|
856
|
Handle myhandle = (Handle)handle;
|
857
|
int toremove = myhandle.index;
|
858
|
cell = toremove / 2;
|
859
|
isfirst = toremove % 2 == 0;
|
860
|
{
|
861
|
if (toremove == -1 || toremove >= size)
|
862
|
throw new InvalidPriorityQueueHandleException("Invalid handle, index out of range");
|
863
|
Handle actualhandle = isfirst ? heap[cell].firsthandle : heap[cell].lasthandle;
|
864
|
if (actualhandle != myhandle)
|
865
|
throw new InvalidPriorityQueueHandleException("Invalid handle, doesn't match queue");
|
866
|
}
|
867
|
return myhandle;
|
868
|
}
|
869
|
|
870
|
|
871
|
/// <summary>
|
872
|
/// Replace an item with a handle in a priority queue with a new item.
|
873
|
/// Typically used for changing the priority of some queued object.
|
874
|
/// </summary>
|
875
|
/// <param name="handle">The handle for the old item</param>
|
876
|
/// <param name="item">The new item</param>
|
877
|
/// <returns>The old item</returns>
|
878
|
[Tested]
|
879
|
public T Replace(IPriorityQueueHandle<T> handle, T item)
|
880
|
{
|
881
|
stamp++;
|
882
|
int cell;
|
883
|
bool isfirst;
|
884
|
checkHandle(handle, out cell, out isfirst);
|
885
|
if (size == 0)
|
886
|
throw new NoSuchItemException();
|
887
|
|
888
|
T retval;
|
889
|
|
890
|
if (isfirst)
|
891
|
{
|
892
|
retval = heap[cell].first;
|
893
|
heap[cell].first = item;
|
894
|
if (size == 1)
|
895
|
{
|
896
|
}
|
897
|
else if (size == 2 * cell + 1) // cell == lastcell
|
898
|
{
|
899
|
int p = (cell + 1) / 2 - 1;
|
900
|
if (comparer.Compare(item, heap[p].last) > 0)
|
901
|
{
|
902
|
Handle thehandle = heap[cell].firsthandle;
|
903
|
updateFirst(cell, heap[p].last, heap[p].lasthandle);
|
904
|
updateLast(p, item, thehandle);
|
905
|
bubbleUpMax(p);
|
906
|
}
|
907
|
else
|
908
|
bubbleUpMin(cell);
|
909
|
}
|
910
|
else if (heapifyMin(cell))
|
911
|
bubbleUpMax(cell);
|
912
|
else
|
913
|
bubbleUpMin(cell);
|
914
|
}
|
915
|
else
|
916
|
{
|
917
|
retval = heap[cell].last;
|
918
|
heap[cell].last = item;
|
919
|
if (heapifyMax(cell))
|
920
|
bubbleUpMin(cell);
|
921
|
else
|
922
|
bubbleUpMax(cell);
|
923
|
}
|
924
|
|
925
|
raiseItemsRemoved(retval, 1);
|
926
|
raiseItemsAdded(item, 1);
|
927
|
raiseCollectionChanged();
|
928
|
|
929
|
return retval;
|
930
|
}
|
931
|
|
932
|
/// <summary>
|
933
|
/// Find the current least item of this priority queue.
|
934
|
/// </summary>
|
935
|
/// <param name="handle">On return: the handle of the item.</param>
|
936
|
/// <returns>The least item.</returns>
|
937
|
public T FindMin(out IPriorityQueueHandle<T> handle)
|
938
|
{
|
939
|
if (size == 0)
|
940
|
throw new NoSuchItemException();
|
941
|
handle = heap[0].firsthandle;
|
942
|
|
943
|
return heap[0].first;
|
944
|
}
|
945
|
|
946
|
/// <summary>
|
947
|
/// Find the current largest item of this priority queue.
|
948
|
/// </summary>
|
949
|
/// <param name="handle">On return: the handle of the item.</param>
|
950
|
/// <returns>The largest item.</returns>
|
951
|
public T FindMax(out IPriorityQueueHandle<T> handle)
|
952
|
{
|
953
|
if (size == 0)
|
954
|
throw new NoSuchItemException();
|
955
|
else if (size == 1)
|
956
|
{
|
957
|
handle = heap[0].firsthandle;
|
958
|
return heap[0].first;
|
959
|
}
|
960
|
else
|
961
|
{
|
962
|
handle = heap[0].lasthandle;
|
963
|
return heap[0].last;
|
964
|
}
|
965
|
}
|
966
|
|
967
|
/// <summary>
|
968
|
/// Remove the least item from this priority queue.
|
969
|
/// </summary>
|
970
|
/// <param name="handle">On return: the handle of the removed item.</param>
|
971
|
/// <returns>The removed item.</returns>
|
972
|
public T DeleteMin(out IPriorityQueueHandle<T> handle)
|
973
|
{
|
974
|
stamp++;
|
975
|
if (size == 0)
|
976
|
throw new NoSuchItemException();
|
977
|
|
978
|
T retval = heap[0].first;
|
979
|
Handle myhandle = heap[0].firsthandle;
|
980
|
handle = myhandle;
|
981
|
if (myhandle != null)
|
982
|
myhandle.index = -1;
|
983
|
|
984
|
if (size == 1)
|
985
|
{
|
986
|
size = 0;
|
987
|
heap[0].first = default(T);
|
988
|
heap[0].firsthandle = null;
|
989
|
}
|
990
|
else
|
991
|
{
|
992
|
int lastcell = (size - 1) / 2;
|
993
|
|
994
|
if (size % 2 == 0)
|
995
|
{
|
996
|
updateFirst(0, heap[lastcell].last, heap[lastcell].lasthandle);
|
997
|
heap[lastcell].last = default(T);
|
998
|
heap[lastcell].lasthandle = null;
|
999
|
}
|
1000
|
else
|
1001
|
{
|
1002
|
updateFirst(0, heap[lastcell].first, heap[lastcell].firsthandle);
|
1003
|
heap[lastcell].first = default(T);
|
1004
|
heap[lastcell].firsthandle = null;
|
1005
|
}
|
1006
|
|
1007
|
size--;
|
1008
|
heapifyMin(0);
|
1009
|
}
|
1010
|
|
1011
|
raiseItemsRemoved(retval, 1);
|
1012
|
raiseCollectionChanged();
|
1013
|
return retval;
|
1014
|
|
1015
|
}
|
1016
|
|
1017
|
/// <summary>
|
1018
|
/// Remove the largest item from this priority queue.
|
1019
|
/// </summary>
|
1020
|
/// <param name="handle">On return: the handle of the removed item.</param>
|
1021
|
/// <returns>The removed item.</returns>
|
1022
|
public T DeleteMax(out IPriorityQueueHandle<T> handle)
|
1023
|
{
|
1024
|
stamp++;
|
1025
|
if (size == 0)
|
1026
|
throw new NoSuchItemException();
|
1027
|
|
1028
|
T retval;
|
1029
|
Handle myhandle;
|
1030
|
|
1031
|
if (size == 1)
|
1032
|
{
|
1033
|
size = 0;
|
1034
|
retval = heap[0].first;
|
1035
|
myhandle = heap[0].firsthandle;
|
1036
|
if (myhandle != null)
|
1037
|
myhandle.index = -1;
|
1038
|
heap[0].first = default(T);
|
1039
|
heap[0].firsthandle = null;
|
1040
|
}
|
1041
|
else
|
1042
|
{
|
1043
|
retval = heap[0].last;
|
1044
|
myhandle = heap[0].lasthandle;
|
1045
|
if (myhandle != null)
|
1046
|
myhandle.index = -1;
|
1047
|
|
1048
|
int lastcell = (size - 1) / 2;
|
1049
|
|
1050
|
if (size % 2 == 0)
|
1051
|
{
|
1052
|
updateLast(0, heap[lastcell].last, heap[lastcell].lasthandle);
|
1053
|
heap[lastcell].last = default(T);
|
1054
|
heap[lastcell].lasthandle = null;
|
1055
|
}
|
1056
|
else
|
1057
|
{
|
1058
|
updateLast(0, heap[lastcell].first, heap[lastcell].firsthandle);
|
1059
|
heap[lastcell].first = default(T);
|
1060
|
heap[lastcell].firsthandle = null;
|
1061
|
}
|
1062
|
|
1063
|
size--;
|
1064
|
heapifyMax(0);
|
1065
|
}
|
1066
|
raiseItemsRemoved(retval, 1);
|
1067
|
raiseCollectionChanged();
|
1068
|
handle = myhandle;
|
1069
|
return retval;
|
1070
|
}
|
1071
|
|
1072
|
#endregion
|
1073
|
|
1074
|
#region ICloneable Members
|
1075
|
|
1076
|
/// <summary>
|
1077
|
/// Make a shallow copy of this IntervalHeap.
|
1078
|
/// </summary>
|
1079
|
/// <returns></returns>
|
1080
|
public virtual object Clone()
|
1081
|
{
|
1082
|
IntervalHeap<T> clone = new IntervalHeap<T>(size, comparer, itemequalityComparer);
|
1083
|
clone.AddAll(this);
|
1084
|
return clone;
|
1085
|
}
|
1086
|
|
1087
|
#endregion
|
1088
|
|
1089
|
}
|
1090
|
|
1091
|
}
|