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 }