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 C5;
24 using NUnit.Framework;
25 using SCG = System.Collections.Generic;
26 
27 namespace C5UnitTests.heaps
28 {
29   using CollectionOfInt = IntervalHeap<int>;
30 
31   [TestFixture]
32   public class GenericTesters
33   {
34     [Test]
TestEvents()35     public void TestEvents()
36     {
37       Fun<CollectionOfInt> factory = delegate() { return new CollectionOfInt(TenEqualityComparer.Default); };
38       new C5UnitTests.Templates.Events.PriorityQueueTester<CollectionOfInt>().Test(factory);
39     }
40 
41     [Test]
Extensible()42     public void Extensible()
43     {
44       C5UnitTests.Templates.Extensible.Clone.Tester<CollectionOfInt>();
45       C5UnitTests.Templates.Extensible.Serialization.Tester<CollectionOfInt>();
46     }
47   }
48 
49   [TestFixture]
50   public class Events
51   {
52     IPriorityQueue<int> queue;
53     ArrayList<KeyValuePair<Acts, int>> events;
54 
55 
56     [SetUp]
Init()57     public void Init()
58     {
59       queue = new IntervalHeap<int>();
60       events = new ArrayList<KeyValuePair<Acts, int>>();
61     }
62 
63 
64     [TearDown]
Dispose()65     public void Dispose() { queue = null; events = null; }
66 
67     [Test]
Listenable()68     public void Listenable()
69     {
70       Assert.AreEqual(EventTypeEnum.Basic, queue.ListenableEvents);
71     }
72 
73     enum Acts
74     {
75       Add, Remove, Changed
76     }
77 
78     [Test]
Direct()79     public void Direct()
80     {
81       CollectionChangedHandler<int> cch;
82       ItemsAddedHandler<int> iah;
83       ItemsRemovedHandler<int> irh;
84       Assert.AreEqual(EventTypeEnum.None, queue.ActiveEvents);
85       queue.CollectionChanged += (cch = new CollectionChangedHandler<int>(queue_CollectionChanged));
86       Assert.AreEqual(EventTypeEnum.Changed, queue.ActiveEvents);
87       queue.ItemsAdded += (iah = new ItemsAddedHandler<int>(queue_ItemAdded));
88       Assert.AreEqual(EventTypeEnum.Changed | EventTypeEnum.Added, queue.ActiveEvents);
89       queue.ItemsRemoved += (irh = new ItemsRemovedHandler<int>(queue_ItemRemoved));
90       Assert.AreEqual(EventTypeEnum.Changed | EventTypeEnum.Added | EventTypeEnum.Removed, queue.ActiveEvents);
91       queue.Add(34);
92       queue.Add(56);
93       queue.AddAll<int>(new int[] { });
94       queue.Add(34);
95       queue.Add(12);
96       queue.DeleteMax();
97       queue.DeleteMin();
98       queue.AddAll<int>(new int[] { 4, 5, 6, 2 });
99       Assert.AreEqual(17, events.Count);
100       int[] vals = { 34, 0, 56, 0, 34, 0, 12, 0, 56, 0, 12, 0, 4, 5, 6, 2, 0 };
101       Acts[] acts = { Acts.Add, Acts.Changed, Acts.Add, Acts.Changed, Acts.Add, Acts.Changed, Acts.Add, Acts.Changed,
102                 Acts.Remove, Acts.Changed, Acts.Remove, Acts.Changed, Acts.Add, Acts.Add, Acts.Add, Acts.Add, Acts.Changed };
103       for (int i = 0; i < vals.Length; i++)
104       {
105         //Console.WriteLine("{0}", events[cell]);
106         Assert.AreEqual(acts[i], events[i].Key, "Action " + i);
107         Assert.AreEqual(vals[i], events[i].Value, "Value " + i);
108       }
109       queue.CollectionChanged -= cch;
110       Assert.AreEqual(EventTypeEnum.Added | EventTypeEnum.Removed, queue.ActiveEvents);
111       queue.ItemsAdded -= iah;
112       Assert.AreEqual(EventTypeEnum.Removed, queue.ActiveEvents);
113       queue.ItemsRemoved -= irh;
114       Assert.AreEqual(EventTypeEnum.None, queue.ActiveEvents);
115     }
116 
117     [Test]
Guarded()118     public void Guarded()
119     {
120       ICollectionValue<int> guarded = new GuardedCollectionValue<int>(queue);
121       guarded.CollectionChanged += new CollectionChangedHandler<int>(queue_CollectionChanged);
122       guarded.ItemsAdded += new ItemsAddedHandler<int>(queue_ItemAdded);
123       guarded.ItemsRemoved += new ItemsRemovedHandler<int>(queue_ItemRemoved);
124       queue.Add(34);
125       queue.Add(56);
126       queue.Add(34);
127       queue.Add(12);
128       queue.DeleteMax();
129       queue.DeleteMin();
130       queue.AddAll<int>(new int[] { 4, 5, 6, 2 });
131       Assert.AreEqual(17, events.Count);
132       int[] vals = { 34, 0, 56, 0, 34, 0, 12, 0, 56, 0, 12, 0, 4, 5, 6, 2, 0 };
133       Acts[] acts = { Acts.Add, Acts.Changed, Acts.Add, Acts.Changed, Acts.Add, Acts.Changed, Acts.Add, Acts.Changed,
134                 Acts.Remove, Acts.Changed, Acts.Remove, Acts.Changed, Acts.Add, Acts.Add, Acts.Add, Acts.Add, Acts.Changed };
135       for (int i = 0; i < vals.Length; i++)
136       {
137         //Console.WriteLine("{0}", events[cell]);
138         Assert.AreEqual(vals[i], events[i].Value);
139         Assert.AreEqual(acts[i], events[i].Key);
140       }
141     }
142 
143 
queue_CollectionChanged(object sender)144     void queue_CollectionChanged(object sender)
145     {
146       events.Add(new KeyValuePair<Acts, int>(Acts.Changed, 0));
147     }
queue_ItemAdded(object sender, ItemCountEventArgs<int> e)148     void queue_ItemAdded(object sender, ItemCountEventArgs<int> e)
149     {
150       events.Add(new KeyValuePair<Acts, int>(Acts.Add, e.Item));
151     }
queue_ItemRemoved(object sender, ItemCountEventArgs<int> e)152     void queue_ItemRemoved(object sender, ItemCountEventArgs<int> e)
153     {
154       events.Add(new KeyValuePair<Acts, int>(Acts.Remove, e.Item));
155     }
156   }
157 
158   [TestFixture]
159   public class Formatting
160   {
161     IntervalHeap<int> coll;
162     IFormatProvider rad16;
163     [SetUp]
Init()164     public void Init() { coll = new IntervalHeap<int>(); rad16 = new RadixFormatProvider(16); }
165     [TearDown]
Dispose()166     public void Dispose() { coll = null; rad16 = null; }
167     [Test]
Format()168     public void Format()
169     {
170       Assert.AreEqual("{  }", coll.ToString());
171       coll.AddAll<int>(new int[] { -4, 28, 129, 65530 });
172       Assert.AreEqual("{ -4, 65530, 28, 129 }", coll.ToString());
173       Assert.AreEqual("{ -4, FFFA, 1C, 81 }", coll.ToString(null, rad16));
174       Assert.AreEqual("{ -4, 65530, ... }", coll.ToString("L14", null));
175       Assert.AreEqual("{ -4, FFFA, ... }", coll.ToString("L14", rad16));
176     }
177   }
178 
179 
180   [TestFixture]
181   public class IntervalHeapTests
182   {
183     IPriorityQueue<int> queue;
184 
185 
186     [SetUp]
Init()187     public void Init() { queue = new IntervalHeap<int>(); }
188 
189 
190     [TearDown]
Dispose()191     public void Dispose() { queue = null; }
192 
193     [Test]
194     [ExpectedException(typeof(NullReferenceException))]
NullEqualityComparerinConstructor1()195     public void NullEqualityComparerinConstructor1()
196     {
197       new IntervalHeap<int>(null);
198     }
199 
200     [Test]
201     [ExpectedException(typeof(NullReferenceException))]
NullEqualityComparerinConstructor2()202     public void NullEqualityComparerinConstructor2()
203     {
204       new IntervalHeap<int>(5, null);
205     }
206 
207     [Test]
Handles()208     public void Handles()
209     {
210       IPriorityQueueHandle<int>[] handles = new IPriorityQueueHandle<int>[10];
211 
212       queue.Add(ref handles[0], 7);
213       Assert.IsTrue(queue.Check());
214       queue.Add(ref handles[1], 72);
215       Assert.IsTrue(queue.Check());
216       queue.Add(ref handles[2], 27);
217       Assert.IsTrue(queue.Check());
218       queue.Add(ref handles[3], 17);
219       Assert.IsTrue(queue.Check());
220       queue.Add(ref handles[4], 70);
221       Assert.IsTrue(queue.Check());
222       queue.Add(ref handles[5], 1);
223       Assert.IsTrue(queue.Check());
224       queue.Add(ref handles[6], 2);
225       Assert.IsTrue(queue.Check());
226       queue.Add(ref handles[7], 7);
227       Assert.IsTrue(queue.Check());
228       queue.Add(ref handles[8], 8);
229       Assert.IsTrue(queue.Check());
230       queue.Add(ref handles[9], 9);
231       Assert.IsTrue(queue.Check());
232       queue.Delete(handles[2]);
233       Assert.IsTrue(queue.Check());
234       queue.Delete(handles[0]);
235       Assert.IsTrue(queue.Check());
236       queue.Delete(handles[8]);
237       Assert.IsTrue(queue.Check());
238       queue.Delete(handles[4]);
239       Assert.IsTrue(queue.Check());
240       queue.Delete(handles[6]);
241       Assert.IsTrue(queue.Check());
242       Assert.AreEqual(5, queue.Count);
243     }
244 
245     [Test]
Replace()246     public void Replace()
247     {
248       IPriorityQueueHandle<int> handle = null;
249       queue.Add(6);
250       queue.Add(10);
251       queue.Add(ref handle, 7);
252       queue.Add(21);
253       Assert.AreEqual(7, queue.Replace(handle, 12));
254       Assert.AreEqual(21, queue.FindMax());
255       Assert.AreEqual(12, queue.Replace(handle, 34));
256       Assert.AreEqual(34, queue.FindMax());
257       Assert.IsTrue(queue.Check());
258       //replace max
259       Assert.AreEqual(34, queue.Replace(handle, 60));
260       Assert.AreEqual(60, queue.FindMax());
261       Assert.AreEqual(60, queue.Replace(handle, queue[handle] + 80));
262       Assert.AreEqual(140, queue.FindMax());
263       Assert.IsTrue(queue.Check());
264     }
265 
266     [Test]
Replace2()267     public void Replace2()
268     {
269       IPriorityQueueHandle<int> handle = null;
270       queue.Add(6);
271       queue.Add(10);
272       queue.Add(ref handle, 7);
273       //Replace last item in queue with something large
274       Assert.AreEqual(7, queue.Replace(handle, 12));
275       Assert.IsTrue(queue.Check());
276     }
277 
278     /// <summary>
279     /// bug20070504.txt by Viet Yen Nguyen
280     /// </summary>
281     [Test]
Replace3()282     public void Replace3()
283     {
284       IPriorityQueueHandle<int> handle = null;
285       queue.Add(ref handle, 10);
286       Assert.AreEqual(10, queue.Replace(handle, 12));
287       Assert.IsTrue(queue.Check());
288     }
289 
290     /// <summary>
291     /// bug20080222.txt by Thomas Dufour
292     /// </summary>
293     [Test]
Replace4a()294     public void Replace4a()
295     {
296       IPriorityQueueHandle<int> handle1 = null;
297       queue.Add(ref handle1, 4);
298       Assert.AreEqual(4, queue.FindMin());
299       queue.Add(3);
300       Assert.AreEqual(3, queue.FindMin());
301       Assert.AreEqual(4, queue.Replace(handle1, 2));
302       Assert.AreEqual(2, queue.FindMin());
303     }
304 
305     [Test]
Replace4b()306     public void Replace4b()
307     {
308       IPriorityQueueHandle<int> handle1 = null;
309       queue.Add(ref handle1, 2);
310       Assert.AreEqual(2, queue.FindMax());
311       queue.Add(3);
312       Assert.AreEqual(3, queue.FindMax());
313       Assert.AreEqual(2, queue.Replace(handle1, 4));
314       Assert.AreEqual(4, queue.FindMax());
315     }
316 
317     [Test]
Replace5a()318     public void Replace5a()
319     {
320       for (int size = 0; size < 130; size++)
321       {
322         IPriorityQueue<double> q = new IntervalHeap<double>();
323         IPriorityQueueHandle<double> handle1 = null;
324         q.Add(ref handle1, 3.0);
325         Assert.AreEqual(3.0, q.FindMin());
326         for (int i = 1; i < size; i++)
327           q.Add(i + 3.0);
328         Assert.AreEqual(3.0, q.FindMin());
329         for (int min = 2; min >= -10; min--)
330         {
331           Assert.AreEqual(min + 1.0, q.Replace(handle1, min));
332           Assert.AreEqual(min, q.FindMin());
333         }
334         Assert.AreEqual(-10.0, q.DeleteMin());
335         for (int i = 1; i < size; i++)
336           Assert.AreEqual(i + 3.0, q.DeleteMin());
337         Assert.IsTrue(q.IsEmpty);
338       }
339     }
340 
341     [Test]
Replace5b()342     public void Replace5b()
343     {
344       for (int size = 0; size < 130; size++)
345       {
346         IPriorityQueue<double> q = new IntervalHeap<double>();
347         IPriorityQueueHandle<double> handle1 = null;
348         q.Add(ref handle1, -3.0);
349         Assert.AreEqual(-3.0, q.FindMax());
350         for (int i = 1; i < size; i++)
351           q.Add(-i - 3.0);
352         Assert.AreEqual(-3.0, q.FindMax());
353         for (int max = -2; max <= 10; max++)
354         {
355           Assert.AreEqual(max - 1.0, q.Replace(handle1, max));
356           Assert.AreEqual(max, q.FindMax());
357         }
358         Assert.AreEqual(10.0, q.DeleteMax());
359         for (int i = 1; i < size; i++)
360           Assert.AreEqual(- i - 3.0, q.DeleteMax());
361         Assert.IsTrue(q.IsEmpty);
362       }
363     }
364 
365     [Test]
Delete1a()366     public void Delete1a()
367     {
368       IPriorityQueueHandle<int> handle1 = null;
369       queue.Add(ref handle1, 4);
370       Assert.AreEqual(4, queue.FindMin());
371       queue.Add(3);
372       Assert.AreEqual(3, queue.FindMin());
373       queue.Add(2);
374       Assert.AreEqual(4, queue.Delete(handle1));
375       Assert.AreEqual(2, queue.FindMin());
376       Assert.AreEqual(3, queue.FindMax());
377     }
378 
379     [Test]
Delete1b()380     public void Delete1b()
381     {
382       IPriorityQueueHandle<int> handle1 = null;
383       queue.Add(ref handle1, 2);
384       Assert.AreEqual(2, queue.FindMax());
385       queue.Add(3);
386       Assert.AreEqual(3, queue.FindMax());
387       queue.Add(4);
388       Assert.AreEqual(2, queue.Delete(handle1));
389       Assert.AreEqual(3, queue.FindMin());
390       Assert.AreEqual(4, queue.FindMax());
391     }
392 
393     [Test]
ReuseHandle()394     public void ReuseHandle()
395     {
396       IPriorityQueueHandle<int> handle = null;
397       queue.Add(ref handle, 7);
398       queue.Delete(handle);
399       queue.Add(ref handle, 8);
400     }
401 
402     [Test]
403     [ExpectedException(typeof(InvalidPriorityQueueHandleException))]
ErrorAddValidHandle()404     public void ErrorAddValidHandle()
405     {
406       IPriorityQueueHandle<int> handle = null;
407       queue.Add(ref handle, 7);
408       queue.Add(ref handle, 8);
409     }
410 
411     [Test]
412     [ExpectedException(typeof(InvalidPriorityQueueHandleException))]
ErrorDeleteInvalidHandle()413     public void ErrorDeleteInvalidHandle()
414     {
415       IPriorityQueueHandle<int> handle = null;
416       queue.Add(ref handle, 7);
417       queue.Delete(handle);
418       queue.Delete(handle);
419     }
420 
421     [Test]
422     [ExpectedException(typeof(InvalidPriorityQueueHandleException))]
ErrorReplaceInvalidHandle()423     public void ErrorReplaceInvalidHandle()
424     {
425       IPriorityQueueHandle<int> handle = null;
426       queue.Add(ref handle, 7);
427       queue.Delete(handle);
428       queue.Replace(handle, 13);
429     }
430 
431     [Test]
Simple()432     public void Simple()
433     {
434       Assert.IsTrue(queue.AllowsDuplicates);
435       Assert.AreEqual(0, queue.Count);
436       queue.Add(8); queue.Add(18); queue.Add(8); queue.Add(3);
437       Assert.AreEqual(4, queue.Count);
438       Assert.AreEqual(18, queue.DeleteMax());
439       Assert.AreEqual(3, queue.Count);
440       Assert.AreEqual(3, queue.DeleteMin());
441       Assert.AreEqual(2, queue.Count);
442       Assert.AreEqual(8, queue.FindMax());
443       Assert.AreEqual(8, queue.DeleteMax());
444       Assert.AreEqual(8, queue.FindMax());
445       queue.Add(15);
446       Assert.AreEqual(15, queue.FindMax());
447       Assert.AreEqual(8, queue.FindMin());
448       Assert.IsTrue(queue.Comparer.Compare(2, 3) < 0);
449       Assert.IsTrue(queue.Comparer.Compare(4, 3) > 0);
450       Assert.IsTrue(queue.Comparer.Compare(3, 3) == 0);
451 
452     }
453 
454 
455     [Test]
Enumerate()456     public void Enumerate()
457     {
458       int[] a = new int[4];
459       int siz = 0;
460       foreach (int i in queue)
461         siz++;
462       Assert.AreEqual(0, siz);
463 
464       queue.Add(8); queue.Add(18); queue.Add(8); queue.Add(3);
465 
466       foreach (int i in queue)
467         a[siz++] = i;
468       Assert.AreEqual(4, siz);
469       Array.Sort(a, 0, siz);
470       Assert.AreEqual(3, a[0]);
471       Assert.AreEqual(8, a[1]);
472       Assert.AreEqual(8, a[2]);
473       Assert.AreEqual(18, a[3]);
474 
475       siz = 0;
476       Assert.AreEqual(18, queue.DeleteMax());
477       foreach (int i in queue)
478         a[siz++] = i;
479       Assert.AreEqual(3, siz);
480       Array.Sort(a, 0, siz);
481       Assert.AreEqual(3, a[0]);
482       Assert.AreEqual(8, a[1]);
483       Assert.AreEqual(8, a[2]);
484 
485       siz = 0;
486       Assert.AreEqual(8, queue.DeleteMax());
487       foreach (int i in queue)
488         a[siz++] = i;
489       Assert.AreEqual(2, siz);
490       Array.Sort(a, 0, siz);
491       Assert.AreEqual(3, a[0]);
492       Assert.AreEqual(8, a[1]);
493 
494       siz = 0;
495       Assert.AreEqual(8, queue.DeleteMax());
496       foreach (int i in queue)
497         a[siz++] = i;
498       Assert.AreEqual(1, siz);
499       Assert.AreEqual(3, a[0]);
500     }
501 
502     [Test]
Random()503     public void Random()
504     {
505       int length = 1000;
506       int[] a = new int[length];
507       Random ran = new Random(6754);
508 
509       for (int i = 0; i < length; i++)
510         queue.Add(a[i] = ran.Next());
511 
512       Assert.IsTrue(queue.Check());
513       Array.Sort(a);
514       for (int i = 0; i < length / 2; i++)
515       {
516         Assert.AreEqual(a[length - i - 1], queue.DeleteMax());
517         Assert.IsTrue(queue.Check());
518         Assert.AreEqual(a[i], queue.DeleteMin());
519         Assert.IsTrue(queue.Check());
520       }
521 
522       Assert.IsTrue(queue.IsEmpty);
523     }
524 
525     [Test]
RandomWithHandles()526     public void RandomWithHandles()
527     {
528       int length = 1000;
529       int[] a = new int[length];
530       Random ran = new Random(6754);
531 
532       for (int i = 0; i < length; i++)
533       {
534         IPriorityQueueHandle<int> h = null;
535         queue.Add(ref h, a[i] = ran.Next());
536         Assert.IsTrue(queue.Check());
537       }
538 
539       Assert.IsTrue(queue.Check());
540       Array.Sort(a);
541       for (int i = 0; i < length / 2; i++)
542       {
543         Assert.AreEqual(a[length - i - 1], queue.DeleteMax());
544         Assert.IsTrue(queue.Check());
545         Assert.AreEqual(a[i], queue.DeleteMin());
546         Assert.IsTrue(queue.Check());
547       }
548 
549       Assert.IsTrue(queue.IsEmpty);
550     }
551 
552     [Test]
RandomWithDeleteHandles()553     public void RandomWithDeleteHandles()
554     {
555       Random ran = new Random(6754);
556       int length = 1000;
557       int[] a = new int[length];
558       ArrayList<int> shuffle = new ArrayList<int>(length);
559       IPriorityQueueHandle<int>[] h = new IPriorityQueueHandle<int>[length];
560 
561       for (int i = 0; i < length; i++)
562       {
563         shuffle.Add(i);
564         queue.Add(ref h[i], a[i] = ran.Next());
565         Assert.IsTrue(queue.Check());
566       }
567 
568       Assert.IsTrue(queue.Check());
569       shuffle.Shuffle(ran);
570       for (int i = 0; i < length; i++)
571       {
572         int j = shuffle[i];
573         Assert.AreEqual(a[j], queue.Delete(h[j]));
574         Assert.IsTrue(queue.Check());
575       }
576 
577       Assert.IsTrue(queue.IsEmpty);
578     }
579 
580     [Test]
RandomIndexing()581     public void RandomIndexing()
582     {
583       Random ran = new Random(6754);
584       int length = 1000;
585       int[] a = new int[length];
586       int[] b = new int[length];
587       ArrayList<int> shuffle = new ArrayList<int>(length);
588       IPriorityQueueHandle<int>[] h = new IPriorityQueueHandle<int>[length];
589 
590       for (int i = 0; i < length; i++)
591       {
592         shuffle.Add(i);
593         queue.Add(ref h[i], a[i] = ran.Next());
594         b[i] = ran.Next();
595         Assert.IsTrue(queue.Check());
596       }
597 
598       Assert.IsTrue(queue.Check());
599       shuffle.Shuffle(ran);
600       for (int i = 0; i < length; i++)
601       {
602         int j = shuffle[i];
603         Assert.AreEqual(a[j], queue[h[j]]);
604         queue[h[j]] = b[j];
605         Assert.AreEqual(b[j], queue[h[j]]);
606         Assert.IsTrue(queue.Check());
607       }
608     }
609 
610 
611 
612     [Test]
RandomDuplicates()613     public void RandomDuplicates()
614     {
615       int length = 1000;
616       int s;
617       int[] a = new int[length];
618       Random ran = new Random(6754);
619 
620       for (int i = 0; i < length; i++)
621         queue.Add(a[i] = ran.Next(3, 13));
622       Assert.IsTrue(queue.Check());
623 
624       Array.Sort(a);
625 
626       for (int i = 0; i < length / 2; i++)
627       {
628         Assert.AreEqual(a[i], queue.DeleteMin());
629         Assert.IsTrue(queue.Check());
630         Assert.AreEqual(a[length - i - 1], s = queue.DeleteMax());
631         Assert.IsTrue(queue.Check());
632       }
633 
634       Assert.IsTrue(queue.IsEmpty);
635     }
636 
637 
638     [Test]
AddAll()639     public void AddAll()
640     {
641       int length = 1000;
642       int[] a = new int[length];
643       Random ran = new Random(6754);
644 
645       LinkedList<int> lst = new LinkedList<int>();
646       for (int i = 0; i < length; i++)
647         lst.Add(a[i] = ran.Next());
648 
649       queue.AddAll(lst);
650       Assert.IsTrue(queue.Check());
651       Array.Sort(a);
652       for (int i = 0; i < length / 2; i++)
653       {
654         Assert.AreEqual(a[length - i - 1], queue.DeleteMax());
655         Assert.IsTrue(queue.Check());
656         Assert.AreEqual(a[i], queue.DeleteMin());
657         Assert.IsTrue(queue.Check());
658       }
659 
660       Assert.IsTrue(queue.IsEmpty);
661     }
662 
663   }
664 
665 
666 }