2 Copyright (c) 2003-2006 Niels Kokholm and Peter Sestoft
\r
3 Permission is hereby granted, free of charge, to any person obtaining a copy
\r
4 of this software and associated documentation files (the "Software"), to deal
\r
5 in the Software without restriction, including without limitation the rights
\r
6 to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
\r
7 copies of the Software, and to permit persons to whom the Software is
\r
8 furnished to do so, subject to the following conditions:
\r
10 The above copyright notice and this permission notice shall be included in
\r
11 all copies or substantial portions of the Software.
\r
13 THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
\r
14 IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
\r
15 FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
\r
16 AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
\r
17 LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
\r
18 OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
\r
24 using NUnit.Framework;
\r
25 using SCG = System.Collections.Generic;
\r
27 namespace C5UnitTests.arrays.sorted
\r
29 using CollectionOfInt = SortedArray<int>;
\r
32 public class GenericTesters
\r
35 public void TestEvents()
\r
37 Fun<CollectionOfInt> factory = delegate() { return new CollectionOfInt(TenEqualityComparer.Default); };
\r
38 new C5UnitTests.Templates.Events.SortedIndexedTester<CollectionOfInt>().Test(factory);
\r
42 public void Extensible()
\r
44 C5UnitTests.Templates.Extensible.Clone.Tester<CollectionOfInt>();
\r
45 C5UnitTests.Templates.Extensible.Serialization.Tester<CollectionOfInt>();
\r
49 static class Factory
\r
51 public static ICollection<T> New<T>() { return new SortedArray<T>(); }
\r
56 public class Formatting
\r
58 ICollection<int> coll;
\r
59 IFormatProvider rad16;
\r
61 public void Init() { coll = Factory.New<int>(); rad16 = new RadixFormatProvider(16); }
\r
63 public void Dispose() { coll = null; rad16 = null; }
\r
65 public void Format()
\r
67 Assert.AreEqual("{ }", coll.ToString());
\r
68 coll.AddAll<int>(new int[] { -4, 28, 129, 65530 });
\r
69 Assert.AreEqual("{ -4, 28, 129, 65530 }", coll.ToString());
\r
70 Assert.AreEqual("{ -4, 1C, 81, FFFA }", coll.ToString(null, rad16));
\r
71 Assert.AreEqual("{ -4, 28, 129... }", coll.ToString("L14", null));
\r
72 Assert.AreEqual("{ -4, 1C, 81... }", coll.ToString("L14", rad16));
\r
79 private SortedArray<int> array;
\r
81 private SCG.IComparer<int> c;
\r
88 array = new SortedArray<int>(c);
\r
89 for (int i = 1; i <= 10; i++)
\r
97 public void Enumerator()
\r
99 SCG.IEnumerator<int> e = array.RangeFromTo(5, 17).GetEnumerator();
\r
102 while (e.MoveNext())
\r
104 Assert.AreEqual(2 * i++, e.Current);
\r
107 Assert.AreEqual(9, i);
\r
112 [ExpectedException(typeof(CollectionModifiedException))]
\r
113 public void Enumerator3()
\r
115 SCG.IEnumerator<int> e = array.RangeFromTo(5, 17).GetEnumerator();
\r
124 public void Remove()
\r
126 int[] all = new int[] { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
\r
128 array.RemoveRangeFrom(18);
\r
129 Assert.IsTrue(IC.eq(array, new int[] { 2, 4, 6, 8, 10, 12, 14, 16 }));
\r
130 array.RemoveRangeFrom(28);
\r
131 Assert.IsTrue(IC.eq(array, new int[] { 2, 4, 6, 8, 10, 12, 14, 16 }));
\r
132 array.RemoveRangeFrom(13);
\r
133 Assert.IsTrue(IC.eq(array, new int[] { 2, 4, 6, 8, 10, 12 }));
\r
134 array.RemoveRangeFrom(2);
\r
135 Assert.IsTrue(IC.eq(array));
\r
136 foreach (int i in all) array.Add(i);
\r
138 array.RemoveRangeTo(10);
\r
139 Assert.IsTrue(IC.eq(array, new int[] { 10, 12, 14, 16, 18, 20 }));
\r
140 array.RemoveRangeTo(2);
\r
141 Assert.IsTrue(IC.eq(array, new int[] { 10, 12, 14, 16, 18, 20 }));
\r
142 array.RemoveRangeTo(21);
\r
143 Assert.IsTrue(IC.eq(array));
\r
144 foreach (int i in all) array.Add(i);
\r
146 array.RemoveRangeFromTo(4, 8);
\r
147 Assert.IsTrue(IC.eq(array, 2, 8, 10, 12, 14, 16, 18, 20));
\r
148 array.RemoveRangeFromTo(14, 28);
\r
149 Assert.IsTrue(IC.eq(array, 2, 8, 10, 12));
\r
150 array.RemoveRangeFromTo(0, 9);
\r
151 Assert.IsTrue(IC.eq(array, 10, 12));
\r
152 array.RemoveRangeFromTo(0, 81);
\r
153 Assert.IsTrue(IC.eq(array));
\r
157 public void Normal()
\r
159 int[] all = new int[] { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
\r
161 Assert.IsTrue(IC.eq(array, all));
\r
162 Assert.IsTrue(IC.eq(array.RangeAll(), all));
\r
163 Assert.AreEqual(10, array.RangeAll().Count);
\r
164 Assert.IsTrue(IC.eq(array.RangeFrom(11), new int[] { 12, 14, 16, 18, 20 }));
\r
165 Assert.AreEqual(5, array.RangeFrom(11).Count);
\r
166 Assert.IsTrue(IC.eq(array.RangeFrom(12), new int[] { 12, 14, 16, 18, 20 }));
\r
167 Assert.IsTrue(IC.eq(array.RangeFrom(2), all));
\r
168 Assert.IsTrue(IC.eq(array.RangeFrom(1), all));
\r
169 Assert.IsTrue(IC.eq(array.RangeFrom(21), new int[] { }));
\r
170 Assert.IsTrue(IC.eq(array.RangeFrom(20), new int[] { 20 }));
\r
171 Assert.IsTrue(IC.eq(array.RangeTo(8), new int[] { 2, 4, 6 }));
\r
172 Assert.IsTrue(IC.eq(array.RangeTo(7), new int[] { 2, 4, 6 }));
\r
173 Assert.AreEqual(3, array.RangeTo(7).Count);
\r
174 Assert.IsTrue(IC.eq(array.RangeTo(2), new int[] { }));
\r
175 Assert.IsTrue(IC.eq(array.RangeTo(1), new int[] { }));
\r
176 Assert.IsTrue(IC.eq(array.RangeTo(3), new int[] { 2 }));
\r
177 Assert.IsTrue(IC.eq(array.RangeTo(20), new int[] { 2, 4, 6, 8, 10, 12, 14, 16, 18 }));
\r
178 Assert.IsTrue(IC.eq(array.RangeTo(21), all));
\r
179 Assert.IsTrue(IC.eq(array.RangeFromTo(7, 12), new int[] { 8, 10 }));
\r
180 Assert.IsTrue(IC.eq(array.RangeFromTo(6, 11), new int[] { 6, 8, 10 }));
\r
181 Assert.IsTrue(IC.eq(array.RangeFromTo(1, 12), new int[] { 2, 4, 6, 8, 10 }));
\r
182 Assert.AreEqual(5, array.RangeFromTo(1, 12).Count);
\r
183 Assert.IsTrue(IC.eq(array.RangeFromTo(2, 12), new int[] { 2, 4, 6, 8, 10 }));
\r
184 Assert.IsTrue(IC.eq(array.RangeFromTo(6, 21), new int[] { 6, 8, 10, 12, 14, 16, 18, 20 }));
\r
185 Assert.IsTrue(IC.eq(array.RangeFromTo(6, 20), new int[] { 6, 8, 10, 12, 14, 16, 18 }));
\r
190 public void Backwards()
\r
192 int[] all = new int[] { 2, 4, 6, 8, 10, 12, 14, 16, 18, 20 };
\r
193 int[] lla = new int[] { 20, 18, 16, 14, 12, 10, 8, 6, 4, 2 };
\r
195 Assert.IsTrue(IC.eq(array, all));
\r
196 Assert.IsTrue(IC.eq(array.RangeAll().Backwards(), lla));
\r
197 Assert.IsTrue(IC.eq(array.RangeFrom(11).Backwards(), new int[] { 20, 18, 16, 14, 12 }));
\r
198 Assert.IsTrue(IC.eq(array.RangeFrom(12).Backwards(), new int[] { 20, 18, 16, 14, 12 }));
\r
199 Assert.IsTrue(IC.eq(array.RangeFrom(2).Backwards(), lla));
\r
200 Assert.IsTrue(IC.eq(array.RangeFrom(1).Backwards(), lla));
\r
201 Assert.IsTrue(IC.eq(array.RangeFrom(21).Backwards(), new int[] { }));
\r
202 Assert.IsTrue(IC.eq(array.RangeFrom(20).Backwards(), new int[] { 20 }));
\r
203 Assert.IsTrue(IC.eq(array.RangeTo(8).Backwards(), new int[] { 6, 4, 2 }));
\r
204 Assert.IsTrue(IC.eq(array.RangeTo(7).Backwards(), new int[] { 6, 4, 2 }));
\r
205 Assert.IsTrue(IC.eq(array.RangeTo(2).Backwards(), new int[] { }));
\r
206 Assert.IsTrue(IC.eq(array.RangeTo(1).Backwards(), new int[] { }));
\r
207 Assert.IsTrue(IC.eq(array.RangeTo(3).Backwards(), new int[] { 2 }));
\r
208 Assert.IsTrue(IC.eq(array.RangeTo(20).Backwards(), new int[] { 18, 16, 14, 12, 10, 8, 6, 4, 2}));
\r
209 Assert.IsTrue(IC.eq(array.RangeTo(21).Backwards(), lla));
\r
210 Assert.IsTrue(IC.eq(array.RangeFromTo(7, 12).Backwards(), new int[] { 10, 8 }));
\r
211 Assert.IsTrue(IC.eq(array.RangeFromTo(6, 11).Backwards(), new int[] { 10, 8, 6 }));
\r
212 Assert.IsTrue(IC.eq(array.RangeFromTo(1, 12).Backwards(), new int[] { 10, 8, 6, 4, 2 }));
\r
213 Assert.IsTrue(IC.eq(array.RangeFromTo(2, 12).Backwards(), new int[] { 10, 8, 6, 4, 2 }));
\r
214 Assert.IsTrue(IC.eq(array.RangeFromTo(6, 21).Backwards(), new int[] { 20, 18, 16, 14, 12, 10, 8, 6 }));
\r
215 Assert.IsTrue(IC.eq(array.RangeFromTo(6, 20).Backwards(), new int[] { 18, 16, 14, 12, 10, 8, 6 }));
\r
219 public void Direction()
\r
221 Assert.AreEqual(EnumerationDirection.Forwards, array.Direction);
\r
222 Assert.AreEqual(EnumerationDirection.Forwards, array.RangeFrom(20).Direction);
\r
223 Assert.AreEqual(EnumerationDirection.Forwards, array.RangeTo(7).Direction);
\r
224 Assert.AreEqual(EnumerationDirection.Forwards, array.RangeFromTo(1, 12).Direction);
\r
225 Assert.AreEqual(EnumerationDirection.Forwards, array.RangeAll().Direction);
\r
226 Assert.AreEqual(EnumerationDirection.Backwards, array.Backwards().Direction);
\r
227 Assert.AreEqual(EnumerationDirection.Backwards, array.RangeFrom(20).Backwards().Direction);
\r
228 Assert.AreEqual(EnumerationDirection.Backwards, array.RangeTo(7).Backwards().Direction);
\r
229 Assert.AreEqual(EnumerationDirection.Backwards, array.RangeFromTo(1, 12).Backwards().Direction);
\r
230 Assert.AreEqual(EnumerationDirection.Backwards, array.RangeAll().Backwards().Direction);
\r
235 public void Dispose()
\r
243 public class BagItf
\r
245 private SortedArray<int> array;
\r
251 array = new SortedArray<int>(new IC());
\r
252 for (int i = 10; i < 20; i++)
\r
263 Assert.AreEqual(0, array.ContainsCount(7));
\r
264 Assert.AreEqual(1, array.ContainsCount(10));
\r
265 array.RemoveAllCopies(10);
\r
266 Assert.AreEqual(0, array.ContainsCount(10));
\r
267 array.RemoveAllCopies(7);
\r
272 public void Dispose()
\r
282 private SortedArray<int> array;
\r
288 array = new SortedArray<int>(new IC());
\r
292 [ExpectedException(typeof(NullReferenceException))]
\r
293 public void NullEqualityComparerinConstructor1()
\r
295 new SortedArray<int>(null);
\r
299 [ExpectedException(typeof(NullReferenceException))]
\r
300 public void NullEqualityComparerinConstructor2()
\r
302 new SortedArray<int>(5, null);
\r
306 [ExpectedException(typeof(NullReferenceException))]
\r
307 public void NullEqualityComparerinConstructor3()
\r
309 new SortedArray<int>(5, null, EqualityComparer<int>.Default);
\r
313 [ExpectedException(typeof(NullReferenceException))]
\r
314 public void NullEqualityComparerinConstructor4()
\r
316 new SortedArray<int>(5, Comparer<int>.Default, null);
\r
320 [ExpectedException(typeof(NullReferenceException))]
\r
321 public void NullEqualityComparerinConstructor5()
\r
323 new SortedArray<int>(5, null, null);
\r
327 public void Choose()
\r
330 Assert.AreEqual(7, array.Choose());
\r
334 [ExpectedException(typeof(NoSuchItemException))]
\r
335 public void BadChoose()
\r
342 private void loadup()
\r
344 for (int i = 10; i < 20; i++)
\r
353 public void NoDuplicatesEtc()
\r
355 Assert.IsFalse(array.AllowsDuplicates);
\r
357 Assert.IsFalse(array.AllowsDuplicates);
\r
358 Assert.AreEqual(Speed.Log, array.ContainsSpeed);
\r
359 Assert.IsTrue(array.Comparer.Compare(2, 3) < 0);
\r
360 Assert.IsTrue(array.Comparer.Compare(4, 3) > 0);
\r
361 Assert.IsTrue(array.Comparer.Compare(3, 3) == 0);
\r
367 Assert.IsTrue(array.Add(17));
\r
368 Assert.IsFalse(array.Add(17));
\r
369 Assert.IsTrue(array.Add(18));
\r
370 Assert.IsFalse(array.Add(18));
\r
371 Assert.AreEqual(2, array.Count);
\r
376 public void Dispose()
\r
384 public class FindOrAdd
\r
386 private SortedArray<KeyValuePair<int,string>> bag;
\r
392 bag = new SortedArray<KeyValuePair<int,string>>(new KeyValuePairComparer<int,string>(new IC()));
\r
397 public void Dispose()
\r
406 KeyValuePair<int,string> p = new KeyValuePair<int,string>(3, "tre");
\r
408 Assert.IsFalse(bag.FindOrAdd(ref p));
\r
410 Assert.IsTrue(bag.FindOrAdd(ref p));
\r
411 Assert.AreEqual("tre", p.Value);
\r
413 Assert.AreEqual(1, bag.ContainsCount(p));
\r
414 Assert.AreEqual("tre", bag[0].Value);
\r
419 public class FindPredicate
\r
421 private SortedArray<int> list;
\r
422 Fun<int, bool> pred;
\r
427 list = new SortedArray<int>(TenEqualityComparer.Default);
\r
428 pred = delegate(int i) { return i % 5 == 0; };
\r
432 public void Dispose() { list = null; }
\r
438 Assert.IsFalse(list.Find(pred, out i));
\r
439 list.AddAll<int>(new int[] { 4, 22, 67, 37 });
\r
440 Assert.IsFalse(list.Find(pred, out i));
\r
441 list.AddAll<int>(new int[] { 45, 122, 675, 137 });
\r
442 Assert.IsTrue(list.Find(pred, out i));
\r
443 Assert.AreEqual(45, i);
\r
447 public void FindLast()
\r
450 Assert.IsFalse(list.FindLast(pred, out i));
\r
451 list.AddAll<int>(new int[] { 4, 22, 67, 37 });
\r
452 Assert.IsFalse(list.FindLast(pred, out i));
\r
453 list.AddAll<int>(new int[] { 45, 122, 675, 137 });
\r
454 Assert.IsTrue(list.FindLast(pred, out i));
\r
455 Assert.AreEqual(675, i);
\r
459 public void FindIndex()
\r
461 Assert.IsFalse(0 <= list.FindIndex(pred));
\r
462 list.AddAll<int>(new int[] { 4, 22, 67, 37 });
\r
463 Assert.IsFalse(0 <= list.FindIndex(pred));
\r
464 list.AddAll<int>(new int[] { 45, 122, 675, 137 });
\r
465 Assert.AreEqual(3, list.FindIndex(pred));
\r
469 public void FindLastIndex()
\r
471 Assert.IsFalse(0 <= list.FindLastIndex(pred));
\r
472 list.AddAll<int>(new int[] { 4, 22, 67, 37 });
\r
473 Assert.IsFalse(0 <= list.FindLastIndex(pred));
\r
474 list.AddAll<int>(new int[] { 45, 122, 675, 137 });
\r
475 Assert.AreEqual(7, list.FindLastIndex(pred));
\r
480 public class UniqueItems
\r
482 private SortedArray<int> list;
\r
485 public void Init() { list = new SortedArray<int>(); }
\r
488 public void Dispose() { list = null; }
\r
493 Assert.IsTrue(IC.seteq(list.UniqueItems()));
\r
494 Assert.IsTrue(IC.seteq(list.ItemMultiplicities()));
\r
495 list.AddAll<int>(new int[] { 7, 9, 7 });
\r
496 Assert.IsTrue(IC.seteq(list.UniqueItems(), 7, 9));
\r
497 Assert.IsTrue(IC.seteq(list.ItemMultiplicities(), 7, 1, 9, 1));
\r
502 public class ArrayTest
\r
504 private SortedArray<int> tree;
\r
512 tree = new SortedArray<int>(new IC());
\r
514 for (int i = 0; i < 10; i++)
\r
520 public void Dispose() { tree = null; }
\r
523 private string aeq(int[] a, params int[] b)
\r
525 if (a.Length != b.Length)
\r
526 return "Lengths differ: " + a.Length + " != " + b.Length;
\r
528 for (int i = 0; i < a.Length; i++)
\r
530 return String.Format("{0}'th elements differ: {1} != {2}", i, a[i], b[i]);
\r
532 return "Alles klar";
\r
537 public void ToArray()
\r
539 Assert.AreEqual("Alles klar", aeq(tree.ToArray()));
\r
542 Assert.AreEqual("Alles klar", aeq(tree.ToArray(), 4, 7));
\r
547 public void CopyTo()
\r
550 Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009));
\r
553 Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 6, 1003, 1004, 1005, 1006, 1007, 1008, 1009));
\r
557 Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 6, 1003, 4, 6, 9, 1007, 1008, 1009));
\r
561 Assert.AreEqual("Alles klar", aeq(a, 1000, 1001, 6, 1003, 4, 6, 9, 1007, 1008, 7));
\r
566 [ExpectedException(typeof(ArgumentOutOfRangeException))]
\r
567 public void CopyToBad()
\r
569 tree.CopyTo(a, 11);
\r
574 [ExpectedException(typeof(ArgumentOutOfRangeException))]
\r
575 public void CopyToBad2()
\r
577 tree.CopyTo(a, -1);
\r
582 [ExpectedException(typeof(ArgumentOutOfRangeException))]
\r
583 public void CopyToTooFar()
\r
593 public class Combined
\r
595 private IIndexedSorted<KeyValuePair<int,int>> lst;
\r
601 lst = new SortedArray<KeyValuePair<int,int>>(new KeyValuePairComparer<int,int>(new IC()));
\r
602 for (int i = 0; i < 10; i++)
\r
603 lst.Add(new KeyValuePair<int,int>(i, i + 30));
\r
608 public void Dispose() { lst = null; }
\r
614 KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);
\r
616 Assert.IsTrue(lst.Find(ref p));
\r
617 Assert.AreEqual(3, p.Key);
\r
618 Assert.AreEqual(33, p.Value);
\r
619 p = new KeyValuePair<int,int>(13, 78);
\r
620 Assert.IsFalse(lst.Find(ref p));
\r
625 public void FindOrAdd()
\r
627 KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);
\r
629 Assert.IsTrue(lst.FindOrAdd(ref p));
\r
630 Assert.AreEqual(3, p.Key);
\r
631 Assert.AreEqual(33, p.Value);
\r
632 p = new KeyValuePair<int,int>(13, 79);
\r
633 Assert.IsFalse(lst.FindOrAdd(ref p));
\r
634 Assert.AreEqual(13, lst[10].Key);
\r
635 Assert.AreEqual(79, lst[10].Value);
\r
640 public void Update()
\r
642 KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);
\r
644 Assert.IsTrue(lst.Update(p));
\r
645 Assert.AreEqual(3, lst[3].Key);
\r
646 Assert.AreEqual(78, lst[3].Value);
\r
647 p = new KeyValuePair<int,int>(13, 78);
\r
648 Assert.IsFalse(lst.Update(p));
\r
653 public void UpdateOrAdd()
\r
655 KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);
\r
657 Assert.IsTrue(lst.UpdateOrAdd(p));
\r
658 Assert.AreEqual(3, lst[3].Key);
\r
659 Assert.AreEqual(78, lst[3].Value);
\r
660 p = new KeyValuePair<int,int>(13, 79);
\r
661 Assert.IsFalse(lst.UpdateOrAdd(p));
\r
662 Assert.AreEqual(13, lst[10].Key);
\r
663 Assert.AreEqual(79, lst[10].Value);
\r
668 public void RemoveWithReturn()
\r
670 KeyValuePair<int,int> p = new KeyValuePair<int,int>(3, 78);
\r
672 Assert.IsTrue(lst.Remove(p, out p));
\r
673 Assert.AreEqual(3, p.Key);
\r
674 Assert.AreEqual(33, p.Value);
\r
675 Assert.AreEqual(4, lst[3].Key);
\r
676 Assert.AreEqual(34, lst[3].Value);
\r
677 p = new KeyValuePair<int,int>(13, 78);
\r
678 Assert.IsFalse(lst.Remove(p, out p));
\r
684 public class Remove
\r
686 private SortedArray<int> array;
\r
692 array = new SortedArray<int>(new IC());
\r
693 for (int i = 10; i < 20; i++)
\r
702 public void SmallTrees()
\r
707 Assert.IsTrue(array.Remove(7));
\r
708 Assert.IsTrue(array.Check());
\r
713 public void ByIndex()
\r
716 int n = array.Count;
\r
719 array.RemoveAt(10);
\r
720 Assert.IsTrue(array.Check());
\r
721 Assert.IsFalse(array.Contains(i));
\r
722 Assert.AreEqual(n - 1, array.Count);
\r
725 i = array.FindMin();
\r
727 Assert.IsTrue(array.Check());
\r
728 Assert.IsFalse(array.Contains(i));
\r
729 Assert.AreEqual(n - 2, array.Count);
\r
732 i = array.FindMax();
\r
733 array.RemoveAt(array.Count - 1);
\r
734 Assert.IsTrue(array.Check());
\r
735 Assert.IsFalse(array.Contains(i));
\r
736 Assert.AreEqual(n - 3, array.Count);
\r
741 Assert.IsTrue(array.Check());
\r
742 Assert.IsFalse(array.Contains(i));
\r
743 Assert.AreEqual(n - 4, array.Count);
\r
748 public void AlmostEmpty()
\r
754 Assert.IsTrue(array.Check());
\r
755 Assert.IsFalse(array.Contains(3));
\r
756 Assert.AreEqual(0, array.Count);
\r
761 [ExpectedException(typeof(IndexOutOfRangeException), "Index out of range for sequenced collectionvalue")]
\r
762 public void Empty()
\r
770 [ExpectedException(typeof(IndexOutOfRangeException), "Index out of range for sequenced collectionvalue")]
\r
771 public void HighIndex()
\r
773 array.RemoveAt(array.Count);
\r
778 [ExpectedException(typeof(IndexOutOfRangeException), "Index out of range for sequenced collectionvalue")]
\r
779 public void LowIndex()
\r
781 array.RemoveAt(-1);
\r
786 public void Normal()
\r
788 Assert.IsFalse(array.Remove(-20));
\r
790 //No demote case, with move_item
\r
791 Assert.IsTrue(array.Remove(20));
\r
792 Assert.IsTrue(array.Check());
\r
793 Assert.IsFalse(array.Remove(20));
\r
796 Assert.IsTrue(array.Remove(14));
\r
797 Assert.IsTrue(array.Check(), "Bad tree");
\r
800 Assert.IsTrue(array.Remove(25));
\r
801 Assert.IsTrue(array.Check(), "Bad tree");
\r
804 Assert.IsTrue(array.Remove(29));
\r
805 Assert.IsTrue(array.Check(), "Bad tree");
\r
808 Assert.IsTrue(array.Remove(10));
\r
809 Assert.IsTrue(array.Check(), "Bad tree");
\r
812 Assert.IsTrue(array.Remove(12));
\r
813 Assert.IsTrue(array.Remove(11));
\r
816 Assert.IsTrue(array.Remove(18));
\r
817 Assert.IsTrue(array.Remove(13));
\r
818 Assert.IsTrue(array.Remove(15));
\r
821 for (int i = 0; i < 10; i++)
\r
822 array.Add(50 - 2 * i);
\r
824 Assert.IsTrue(array.Remove(42));
\r
825 Assert.IsTrue(array.Remove(38));
\r
826 Assert.IsTrue(array.Remove(28));
\r
827 Assert.IsTrue(array.Remove(40));
\r
830 Assert.IsTrue(array.Remove(16));
\r
831 Assert.IsTrue(array.Remove(23));
\r
832 Assert.IsTrue(array.Remove(17));
\r
833 Assert.IsTrue(array.Remove(19));
\r
834 Assert.IsTrue(array.Remove(50));
\r
835 Assert.IsTrue(array.Remove(26));
\r
836 Assert.IsTrue(array.Remove(21));
\r
837 Assert.IsTrue(array.Remove(22));
\r
838 Assert.IsTrue(array.Remove(24));
\r
839 for (int i = 0; i < 48; i++)
\r
842 //Almost empty tree:
\r
843 Assert.IsFalse(array.Remove(26));
\r
844 Assert.IsTrue(array.Remove(48));
\r
845 Assert.IsTrue(array.Check(), "Bad tree");
\r
848 Assert.IsFalse(array.Remove(26));
\r
849 Assert.IsTrue(array.Check(), "Bad tree");
\r
854 public void Dispose()
\r
863 public class PredecessorStructure
\r
865 private SortedArray<int> tree;
\r
871 tree = new SortedArray<int>(new IC());
\r
875 private void loadup()
\r
877 for (int i = 0; i < 20; i++)
\r
883 public void Predecessor()
\r
886 Assert.AreEqual(6, tree.Predecessor(7));
\r
887 Assert.AreEqual(6, tree.Predecessor(8));
\r
890 Assert.AreEqual(0, tree.Predecessor(1));
\r
893 Assert.AreEqual(38, tree.Predecessor(39));
\r
898 [ExpectedException(typeof(NoSuchItemException))]
\r
899 public void PredecessorTooLow1()
\r
901 tree.Predecessor(-2);
\r
906 [ExpectedException(typeof(NoSuchItemException))]
\r
907 public void PredecessorTooLow2()
\r
909 tree.Predecessor(0);
\r
914 public void WeakPredecessor()
\r
917 Assert.AreEqual(6, tree.WeakPredecessor(7));
\r
918 Assert.AreEqual(8, tree.WeakPredecessor(8));
\r
921 Assert.AreEqual(0, tree.WeakPredecessor(1));
\r
922 Assert.AreEqual(0, tree.WeakPredecessor(0));
\r
925 Assert.AreEqual(38, tree.WeakPredecessor(39));
\r
926 Assert.AreEqual(38, tree.WeakPredecessor(38));
\r
931 [ExpectedException(typeof(NoSuchItemException))]
\r
932 public void WeakPredecessorTooLow1()
\r
934 tree.WeakPredecessor(-1);
\r
939 public void Successor()
\r
942 Assert.AreEqual(8, tree.Successor(7));
\r
943 Assert.AreEqual(10, tree.Successor(8));
\r
946 Assert.AreEqual(2, tree.Successor(0));
\r
947 Assert.AreEqual(0, tree.Successor(-1));
\r
950 Assert.AreEqual(38, tree.Successor(37));
\r
955 [ExpectedException(typeof(NoSuchItemException))]
\r
956 public void SuccessorTooHigh1()
\r
958 tree.Successor(38);
\r
963 [ExpectedException(typeof(NoSuchItemException))]
\r
964 public void SuccessorTooHigh2()
\r
966 tree.Successor(39);
\r
971 public void WeakSuccessor()
\r
974 Assert.AreEqual(6, tree.WeakSuccessor(6));
\r
975 Assert.AreEqual(8, tree.WeakSuccessor(7));
\r
978 Assert.AreEqual(0, tree.WeakSuccessor(-1));
\r
979 Assert.AreEqual(0, tree.WeakSuccessor(0));
\r
982 Assert.AreEqual(38, tree.WeakSuccessor(37));
\r
983 Assert.AreEqual(38, tree.WeakSuccessor(38));
\r
988 [ExpectedException(typeof(NoSuchItemException))]
\r
989 public void WeakSuccessorTooHigh1()
\r
991 tree.WeakSuccessor(39);
\r
996 public void Dispose()
\r
1005 public class PriorityQueue
\r
1007 private SortedArray<int> tree;
\r
1011 public void Init()
\r
1013 tree = new SortedArray<int>(new IC());
\r
1017 private void loadup()
\r
1019 foreach (int i in new int[] { 1, 2, 3, 4 })
\r
1025 public void Normal()
\r
1028 Assert.AreEqual(1, tree.FindMin());
\r
1029 Assert.AreEqual(4, tree.FindMax());
\r
1030 Assert.AreEqual(1, tree.DeleteMin());
\r
1031 Assert.AreEqual(4, tree.DeleteMax());
\r
1032 Assert.IsTrue(tree.Check(), "Bad tree");
\r
1033 Assert.AreEqual(2, tree.FindMin());
\r
1034 Assert.AreEqual(3, tree.FindMax());
\r
1035 Assert.AreEqual(2, tree.DeleteMin());
\r
1036 Assert.AreEqual(3, tree.DeleteMax());
\r
1037 Assert.IsTrue(tree.Check(), "Bad tree");
\r
1042 [ExpectedException(typeof(NoSuchItemException))]
\r
1043 public void Empty1()
\r
1050 [ExpectedException(typeof(NoSuchItemException))]
\r
1051 public void Empty2()
\r
1058 [ExpectedException(typeof(NoSuchItemException))]
\r
1059 public void Empty3()
\r
1066 [ExpectedException(typeof(NoSuchItemException))]
\r
1067 public void Empty4()
\r
1074 public void Dispose()
\r
1083 public class IndexingAndCounting
\r
1085 private SortedArray<int> array;
\r
1089 public void Init()
\r
1091 array = new SortedArray<int>(new IC());
\r
1095 private void populate()
\r
1105 public void ToArray()
\r
1109 int[] a = array.ToArray();
\r
1111 Assert.AreEqual(4, a.Length);
\r
1112 Assert.AreEqual(10, a[0]);
\r
1113 Assert.AreEqual(30, a[1]);
\r
1114 Assert.AreEqual(50, a[2]);
\r
1115 Assert.AreEqual(70, a[3]);
\r
1120 public void GoodIndex()
\r
1122 Assert.AreEqual(~0, array.IndexOf(20));
\r
1123 Assert.AreEqual(~0, array.LastIndexOf(20));
\r
1125 Assert.AreEqual(10, array[0]);
\r
1126 Assert.AreEqual(30, array[1]);
\r
1127 Assert.AreEqual(50, array[2]);
\r
1128 Assert.AreEqual(70, array[3]);
\r
1129 Assert.AreEqual(0, array.IndexOf(10));
\r
1130 Assert.AreEqual(1, array.IndexOf(30));
\r
1131 Assert.AreEqual(2, array.IndexOf(50));
\r
1132 Assert.AreEqual(3, array.IndexOf(70));
\r
1133 Assert.AreEqual(~1, array.IndexOf(20));
\r
1134 Assert.AreEqual(~0, array.IndexOf(0));
\r
1135 Assert.AreEqual(~4, array.IndexOf(90));
\r
1136 Assert.AreEqual(0, array.LastIndexOf(10));
\r
1137 Assert.AreEqual(1, array.LastIndexOf(30));
\r
1138 Assert.AreEqual(2, array.LastIndexOf(50));
\r
1139 Assert.AreEqual(3, array.LastIndexOf(70));
\r
1140 Assert.AreEqual(~1, array.LastIndexOf(20));
\r
1141 Assert.AreEqual(~0, array.LastIndexOf(0));
\r
1142 Assert.AreEqual(~4, array.LastIndexOf(90));
\r
1147 [ExpectedException(typeof(IndexOutOfRangeException))]
\r
1148 public void IndexTooLarge()
\r
1151 Console.WriteLine(array[4]);
\r
1156 [ExpectedException(typeof(IndexOutOfRangeException))]
\r
1157 public void IndexTooSmall()
\r
1160 Console.WriteLine(array[-1]);
\r
1165 public void FilledTreeOutsideInput()
\r
1168 Assert.AreEqual(0, array.CountFrom(90));
\r
1169 Assert.AreEqual(0, array.CountFromTo(-20, 0));
\r
1170 Assert.AreEqual(0, array.CountFromTo(80, 100));
\r
1171 Assert.AreEqual(0, array.CountTo(0));
\r
1172 Assert.AreEqual(4, array.CountTo(90));
\r
1173 Assert.AreEqual(4, array.CountFromTo(-20, 90));
\r
1174 Assert.AreEqual(4, array.CountFrom(0));
\r
1179 public void FilledTreeIntermediateInput()
\r
1182 Assert.AreEqual(3, array.CountFrom(20));
\r
1183 Assert.AreEqual(1, array.CountFromTo(20, 40));
\r
1184 Assert.AreEqual(2, array.CountTo(40));
\r
1189 public void FilledTreeMatchingInput()
\r
1192 Assert.AreEqual(3, array.CountFrom(30));
\r
1193 Assert.AreEqual(2, array.CountFromTo(30, 70));
\r
1194 Assert.AreEqual(0, array.CountFromTo(50, 30));
\r
1195 Assert.AreEqual(0, array.CountFromTo(50, 50));
\r
1196 Assert.AreEqual(0, array.CountTo(10));
\r
1197 Assert.AreEqual(2, array.CountTo(50));
\r
1202 public void CountEmptyTree()
\r
1204 Assert.AreEqual(0, array.CountFrom(20));
\r
1205 Assert.AreEqual(0, array.CountFromTo(20, 40));
\r
1206 Assert.AreEqual(0, array.CountTo(40));
\r
1211 public void Dispose()
\r
1220 namespace ModificationCheck
\r
1223 public class Enumerator
\r
1225 private SortedArray<int> tree;
\r
1227 private SCG.IEnumerator<int> e;
\r
1231 public void Init()
\r
1233 tree = new SortedArray<int>(new IC());
\r
1234 for (int i = 0; i < 10; i++)
\r
1237 e = tree.GetEnumerator();
\r
1242 public void CurrentAfterModification()
\r
1246 Assert.AreEqual(0, e.Current);
\r
1251 [ExpectedException(typeof(CollectionModifiedException))]
\r
1252 public void MoveNextAfterAdd()
\r
1263 [ExpectedException(typeof(CollectionModifiedException))]
\r
1264 public void MoveNextAfterRemove()
\r
1273 [ExpectedException(typeof(CollectionModifiedException))]
\r
1274 public void MoveNextAfterClear()
\r
1283 public void Dispose()
\r
1293 public class RangeEnumerator
\r
1295 private SortedArray<int> tree;
\r
1297 private SCG.IEnumerator<int> e;
\r
1301 public void Init()
\r
1303 tree = new SortedArray<int>(new IC());
\r
1304 for (int i = 0; i < 10; i++)
\r
1307 e = tree.RangeFromTo(3, 7).GetEnumerator();
\r
1312 public void CurrentAfterModification()
\r
1316 Assert.AreEqual(3, e.Current);
\r
1321 [ExpectedException(typeof(CollectionModifiedException))]
\r
1322 public void MoveNextAfterAdd()
\r
1332 [ExpectedException(typeof(CollectionModifiedException))]
\r
1333 public void MoveNextAfterRemove()
\r
1341 [ExpectedException(typeof(CollectionModifiedException))]
\r
1342 public void MoveNextAfterClear()
\r
1350 public void Dispose()
\r
1358 namespace HigherOrder
\r
1360 internal class CubeRoot: IComparable<int>
\r
1365 internal CubeRoot(int c) { this.c = c; }
\r
1368 public int CompareTo(int that) { return c - that * that * that; }
\r
1370 public bool Equals(int that) { return c == that * that * that; }
\r
1376 class Interval: IComparable<int>
\r
1381 internal Interval(int b, int t) { this.b = b; this.t = t; }
\r
1384 public int CompareTo(int that) { return that < b ? 1 : that > t ? -1 : 0; }
\r
1386 public bool Equals(int that) { return that >= b && that <= t; }
\r
1392 public class Simple
\r
1394 private SortedArray<int> array;
\r
1396 private SCG.IComparer<int> ic;
\r
1400 public void Init()
\r
1403 array = new SortedArray<int>(ic);
\r
1407 private bool never(int i) { return false; }
\r
1410 private bool always(int i) { return true; }
\r
1413 private bool even(int i) { return i % 2 == 0; }
\r
1416 private string themap(int i) { return String.Format("AA {0,4} BB", i); }
\r
1419 private string badmap(int i) { return String.Format("AA {0} BB", i); }
\r
1422 private int appfield1;
\r
1424 private int appfield2;
\r
1427 private void apply(int i) { appfield1++; appfield2 += i * i; }
\r
1431 public void Apply()
\r
1433 Simple simple1 = new Simple();
\r
1435 array.Apply(new Act<int>(simple1.apply));
\r
1436 Assert.AreEqual(0, simple1.appfield1);
\r
1437 Assert.AreEqual(0, simple1.appfield2);
\r
1439 Simple simple2 = new Simple();
\r
1441 for (int i = 0; i < 10; i++) array.Add(i);
\r
1443 array.Apply(new Act<int>(simple2.apply));
\r
1444 Assert.AreEqual(10, simple2.appfield1);
\r
1445 Assert.AreEqual(285, simple2.appfield2);
\r
1452 Assert.IsTrue(array.All(new Fun<int, bool>(never)));
\r
1453 Assert.IsTrue(array.All(new Fun<int, bool>(even)));
\r
1454 Assert.IsTrue(array.All(new Fun<int, bool>(always)));
\r
1455 for (int i = 0; i < 10; i++) array.Add(i);
\r
1457 Assert.IsFalse(array.All(new Fun<int, bool>(never)));
\r
1458 Assert.IsFalse(array.All(new Fun<int, bool>(even)));
\r
1459 Assert.IsTrue(array.All(new Fun<int, bool>(always)));
\r
1461 for (int i = 0; i < 10; i++) array.Add(i * 2);
\r
1463 Assert.IsFalse(array.All(new Fun<int, bool>(never)));
\r
1464 Assert.IsTrue(array.All(new Fun<int, bool>(even)));
\r
1465 Assert.IsTrue(array.All(new Fun<int, bool>(always)));
\r
1467 for (int i = 0; i < 10; i++) array.Add(i * 2 + 1);
\r
1469 Assert.IsFalse(array.All(new Fun<int, bool>(never)));
\r
1470 Assert.IsFalse(array.All(new Fun<int, bool>(even)));
\r
1471 Assert.IsTrue(array.All(new Fun<int, bool>(always)));
\r
1476 public void Exists()
\r
1478 Assert.IsFalse(array.Exists(new Fun<int, bool>(never)));
\r
1479 Assert.IsFalse(array.Exists(new Fun<int, bool>(even)));
\r
1480 Assert.IsFalse(array.Exists(new Fun<int, bool>(always)));
\r
1481 for (int i = 0; i < 10; i++) array.Add(i);
\r
1483 Assert.IsFalse(array.Exists(new Fun<int, bool>(never)));
\r
1484 Assert.IsTrue(array.Exists(new Fun<int, bool>(even)));
\r
1485 Assert.IsTrue(array.Exists(new Fun<int, bool>(always)));
\r
1487 for (int i = 0; i < 10; i++) array.Add(i * 2);
\r
1489 Assert.IsFalse(array.Exists(new Fun<int, bool>(never)));
\r
1490 Assert.IsTrue(array.Exists(new Fun<int, bool>(even)));
\r
1491 Assert.IsTrue(array.Exists(new Fun<int, bool>(always)));
\r
1493 for (int i = 0; i < 10; i++) array.Add(i * 2 + 1);
\r
1495 Assert.IsFalse(array.Exists(new Fun<int, bool>(never)));
\r
1496 Assert.IsFalse(array.Exists(new Fun<int, bool>(even)));
\r
1497 Assert.IsTrue(array.Exists(new Fun<int, bool>(always)));
\r
1502 public void FindAll()
\r
1504 Assert.AreEqual(0, array.FindAll(new Fun<int, bool>(never)).Count);
\r
1505 for (int i = 0; i < 10; i++)
\r
1508 Assert.AreEqual(0, array.FindAll(new Fun<int, bool>(never)).Count);
\r
1509 Assert.AreEqual(10, array.FindAll(new Fun<int, bool>(always)).Count);
\r
1510 Assert.AreEqual(5, array.FindAll(new Fun<int, bool>(even)).Count);
\r
1511 Assert.IsTrue(((SortedArray<int>)array.FindAll(new Fun<int, bool>(even))).Check());
\r
1518 Assert.AreEqual(0, array.Map(new Fun<int,string>(themap), new SC()).Count);
\r
1519 for (int i = 0; i < 11; i++)
\r
1520 array.Add(i * i * i);
\r
1522 IIndexedSorted<string> res = array.Map(new Fun<int,string>(themap), new SC());
\r
1524 Assert.IsTrue(((SortedArray<string>)res).Check());
\r
1525 Assert.AreEqual(11, res.Count);
\r
1526 Assert.AreEqual("AA 0 BB", res[0]);
\r
1527 Assert.AreEqual("AA 27 BB", res[3]);
\r
1528 Assert.AreEqual("AA 125 BB", res[5]);
\r
1529 Assert.AreEqual("AA 1000 BB", res[10]);
\r
1534 [ExpectedException(typeof(ArgumentException), "mapper not monotonic")]
\r
1535 public void BadMap()
\r
1537 for (int i = 0; i < 11; i++)
\r
1538 array.Add(i * i * i);
\r
1540 ISorted<string> res = array.Map(new Fun<int,string>(badmap), new SC());
\r
1547 for (int i = 0; i < 10; i++)
\r
1553 Assert.IsTrue(array.Cut(new CubeRoot(27), out low, out lval, out high, out hval));
\r
1554 Assert.IsTrue(lval && hval);
\r
1555 Assert.AreEqual(4, high);
\r
1556 Assert.AreEqual(2, low);
\r
1557 Assert.IsFalse(array.Cut(new CubeRoot(30), out low, out lval, out high, out hval));
\r
1558 Assert.IsTrue(lval && hval);
\r
1559 Assert.AreEqual(4, high);
\r
1560 Assert.AreEqual(3, low);
\r
1565 public void CutInt()
\r
1567 for (int i = 0; i < 10; i++)
\r
1573 Assert.IsFalse(array.Cut(new IC(3), out low, out lval, out high, out hval));
\r
1574 Assert.IsTrue(lval && hval);
\r
1575 Assert.AreEqual(4, high);
\r
1576 Assert.AreEqual(2, low);
\r
1577 Assert.IsTrue(array.Cut(new IC(6), out low, out lval, out high, out hval));
\r
1578 Assert.IsTrue(lval && hval);
\r
1579 Assert.AreEqual(8, high);
\r
1580 Assert.AreEqual(4, low);
\r
1585 public void CutInterval()
\r
1587 for (int i = 0; i < 10; i++)
\r
1593 Assert.IsTrue(array.Cut(new Interval(5, 9), out lo, out lv, out hi, out hv));
\r
1594 Assert.IsTrue(lv && hv);
\r
1595 Assert.AreEqual(10, hi);
\r
1596 Assert.AreEqual(4, lo);
\r
1597 Assert.IsTrue(array.Cut(new Interval(6, 10), out lo, out lv, out hi, out hv));
\r
1598 Assert.IsTrue(lv && hv);
\r
1599 Assert.AreEqual(12, hi);
\r
1600 Assert.AreEqual(4, lo);
\r
1601 for (int i = 0; i < 100; i++)
\r
1604 array.Cut(new Interval(77, 105), out lo, out lv, out hi, out hv);
\r
1605 Assert.IsTrue(lv && hv);
\r
1606 Assert.AreEqual(106, hi);
\r
1607 Assert.AreEqual(76, lo);
\r
1608 array.Cut(new Interval(5, 7), out lo, out lv, out hi, out hv);
\r
1609 Assert.IsTrue(lv && hv);
\r
1610 Assert.AreEqual(8, hi);
\r
1611 Assert.AreEqual(4, lo);
\r
1612 array.Cut(new Interval(80, 110), out lo, out lv, out hi, out hv);
\r
1613 Assert.IsTrue(lv && hv);
\r
1614 Assert.AreEqual(112, hi);
\r
1615 Assert.AreEqual(78, lo);
\r
1620 public void UpperCut()
\r
1622 for (int i = 0; i < 10; i++)
\r
1628 Assert.IsFalse(array.Cut(new CubeRoot(1000), out l, out lv, out h, out hv));
\r
1629 Assert.IsTrue(lv && !hv);
\r
1630 Assert.AreEqual(9, l);
\r
1631 Assert.IsFalse(array.Cut(new CubeRoot(-50), out l, out lv, out h, out hv));
\r
1632 Assert.IsTrue(!lv && hv);
\r
1633 Assert.AreEqual(0, h);
\r
1638 public void Dispose() { ic = null; array = null; }
\r
1645 namespace MultiOps
\r
1648 public class AddAll
\r
1650 private int sqr(int i) { return i * i; }
\r
1653 SortedArray<int> array;
\r
1657 public void Init() { array = new SortedArray<int>(new IC()); }
\r
1661 public void EmptyEmpty()
\r
1663 array.AddAll(new FunEnumerable(0, new Fun<int,int>(sqr)));
\r
1664 Assert.AreEqual(0, array.Count);
\r
1665 Assert.IsTrue(array.Check());
\r
1670 public void SomeEmpty()
\r
1672 for (int i = 4; i < 9; i++) array.Add(i);
\r
1674 array.AddAll(new FunEnumerable(0, new Fun<int,int>(sqr)));
\r
1675 Assert.AreEqual(5, array.Count);
\r
1676 Assert.IsTrue(array.Check());
\r
1681 public void EmptySome()
\r
1683 array.AddAll(new FunEnumerable(4, new Fun<int,int>(sqr)));
\r
1684 Assert.AreEqual(4, array.Count);
\r
1685 Assert.IsTrue(array.Check());
\r
1686 Assert.AreEqual(0, array[0]);
\r
1687 Assert.AreEqual(1, array[1]);
\r
1688 Assert.AreEqual(4, array[2]);
\r
1689 Assert.AreEqual(9, array[3]);
\r
1694 public void SomeSome()
\r
1696 for (int i = 3; i < 9; i++) array.Add(i);
\r
1698 array.AddAll(new FunEnumerable(4, new Fun<int,int>(sqr)));
\r
1699 Assert.AreEqual(9, array.Count);
\r
1700 Assert.IsTrue(array.Check());
\r
1701 Assert.IsTrue(IC.eq(array, 0, 1, 3,4, 5, 6, 7, 8, 9));
\r
1706 public void Dispose() { array = null; }
\r
1712 public class AddSorted
\r
1714 private int sqr(int i) { return i * i; }
\r
1717 private int bad(int i) { return i * (5 - i); }
\r
1720 SortedArray<int> array;
\r
1724 public void Init() { array = new SortedArray<int>(new IC()); }
\r
1728 public void EmptyEmpty()
\r
1730 array.AddSorted(new FunEnumerable(0, new Fun<int,int>(sqr)));
\r
1731 Assert.AreEqual(0, array.Count);
\r
1732 Assert.IsTrue(array.Check());
\r
1738 public void SomeEmpty()
\r
1740 for (int i = 4; i < 9; i++) array.Add(i);
\r
1742 array.AddSorted(new FunEnumerable(0, new Fun<int,int>(sqr)));
\r
1743 Assert.AreEqual(5, array.Count);
\r
1744 Assert.IsTrue(array.Check());
\r
1750 public void EmptySome()
\r
1752 array.AddSorted(new FunEnumerable(4, new Fun<int,int>(sqr)));
\r
1753 Assert.AreEqual(4, array.Count);
\r
1754 Assert.IsTrue(array.Check());
\r
1755 Assert.AreEqual(0, array[0]);
\r
1756 Assert.AreEqual(1, array[1]);
\r
1757 Assert.AreEqual(4, array[2]);
\r
1758 Assert.AreEqual(9, array[3]);
\r
1764 public void SomeSome()
\r
1766 for (int i = 3; i < 9; i++) array.Add(i);
\r
1768 array.AddSorted(new FunEnumerable(4, new Fun<int,int>(sqr)));
\r
1769 Assert.AreEqual(9, array.Count);
\r
1770 Assert.IsTrue(array.Check());
\r
1771 Assert.IsTrue(IC.eq(array, 0, 1, 3, 4, 5, 6, 7, 8, 9));
\r
1775 [ExpectedException(typeof(ArgumentException), "Argument not sorted")]
\r
1776 public void EmptyBad()
\r
1778 array.AddSorted(new FunEnumerable(9, new Fun<int,int>(bad)));
\r
1783 public void Dispose() { array = null; }
\r
1789 SortedArray<int> array, array2;
\r
1793 public void Init()
\r
1795 array = new SortedArray<int>(new IC());
\r
1796 array2 = new SortedArray<int>(new IC());
\r
1797 for (int i = 0; i < 10; i++)
\r
1800 for (int i = 0; i < 10; i++)
\r
1801 array2.Add(2 * i);
\r
1806 public void RemoveAll()
\r
1808 array.RemoveAll(array2.RangeFromTo(3, 7));
\r
1809 Assert.AreEqual(8, array.Count);
\r
1810 Assert.IsTrue(array.Check());
\r
1811 Assert.IsTrue(IC.eq(array, 0, 1, 2, 3, 5, 7, 8, 9));
\r
1812 array.RemoveAll(array2.RangeFromTo(3, 7));
\r
1813 Assert.AreEqual(8, array.Count);
\r
1814 Assert.IsTrue(array.Check());
\r
1815 Assert.IsTrue(IC.eq(array, 0, 1, 2, 3, 5, 7, 8, 9));
\r
1816 array.RemoveAll(array2.RangeFromTo(13, 17));
\r
1817 Assert.AreEqual(8, array.Count);
\r
1818 Assert.IsTrue(array.Check());
\r
1819 Assert.IsTrue(IC.eq(array, 0, 1, 2, 3, 5, 7, 8, 9));
\r
1820 array.RemoveAll(array2.RangeFromTo(3, 17));
\r
1821 Assert.AreEqual(7, array.Count);
\r
1822 Assert.IsTrue(array.Check());
\r
1823 Assert.IsTrue(IC.eq(array, 0, 1, 2, 3, 5, 7, 9));
\r
1824 for (int i = 0; i < 10; i++) array2.Add(i);
\r
1826 array.RemoveAll(array2.RangeFromTo(-1, 10));
\r
1827 Assert.AreEqual(0, array.Count);
\r
1828 Assert.IsTrue(array.Check());
\r
1829 Assert.IsTrue(IC.eq(array));
\r
1834 public void RetainAll()
\r
1836 array.RetainAll(array2.RangeFromTo(3, 17));
\r
1837 Assert.AreEqual(3, array.Count);
\r
1838 Assert.IsTrue(array.Check());
\r
1839 Assert.IsTrue(IC.eq(array, 4, 6, 8));
\r
1840 array.RetainAll(array2.RangeFromTo(1, 17));
\r
1841 Assert.AreEqual(3, array.Count);
\r
1842 Assert.IsTrue(array.Check());
\r
1843 Assert.IsTrue(IC.eq(array, 4, 6, 8));
\r
1844 array.RetainAll(array2.RangeFromTo(3, 5));
\r
1845 Assert.AreEqual(1, array.Count);
\r
1846 Assert.IsTrue(array.Check());
\r
1847 Assert.IsTrue(IC.eq(array, 4));
\r
1848 array.RetainAll(array2.RangeFromTo(7, 17));
\r
1849 Assert.AreEqual(0, array.Count);
\r
1850 Assert.IsTrue(array.Check());
\r
1851 Assert.IsTrue(IC.eq(array));
\r
1852 for (int i = 0; i < 10; i++) array.Add(i);
\r
1854 array.RetainAll(array2.RangeFromTo(5, 5));
\r
1855 Assert.AreEqual(0, array.Count);
\r
1856 Assert.IsTrue(array.Check());
\r
1857 Assert.IsTrue(IC.eq(array));
\r
1858 for (int i = 0; i < 10; i++) array.Add(i);
\r
1860 array.RetainAll(array2.RangeFromTo(15, 25));
\r
1861 Assert.AreEqual(0, array.Count);
\r
1862 Assert.IsTrue(array.Check());
\r
1863 Assert.IsTrue(IC.eq(array));
\r
1868 public void ContainsAll()
\r
1870 Assert.IsFalse(array.ContainsAll(array2));
\r
1871 Assert.IsTrue(array.ContainsAll(array));
\r
1873 Assert.IsTrue(array.ContainsAll(array2));
\r
1875 Assert.IsTrue(array.ContainsAll(array2));
\r
1877 Assert.IsFalse(array.ContainsAll(array2));
\r
1882 public void RemoveInterval()
\r
1884 array.RemoveInterval(3, 4);
\r
1885 Assert.IsTrue(array.Check());
\r
1886 Assert.AreEqual(6, array.Count);
\r
1887 Assert.IsTrue(IC.eq(array, 0, 1, 2, 7, 8, 9));
\r
1888 array.RemoveInterval(2, 3);
\r
1889 Assert.IsTrue(array.Check());
\r
1890 Assert.AreEqual(3, array.Count);
\r
1891 Assert.IsTrue(IC.eq(array, 0, 1, 9));
\r
1892 array.RemoveInterval(0, 3);
\r
1893 Assert.IsTrue(array.Check());
\r
1894 Assert.AreEqual(0, array.Count);
\r
1895 Assert.IsTrue(IC.eq(array));
\r
1900 [ExpectedException(typeof(ArgumentOutOfRangeException))]
\r
1901 public void RemoveRangeBad1()
\r
1903 array.RemoveInterval(-3, 8);
\r
1908 [ExpectedException(typeof(ArgumentOutOfRangeException))]
\r
1909 public void RemoveRangeBad2()
\r
1911 array.RemoveInterval(3, -8);
\r
1916 [ExpectedException(typeof(ArgumentOutOfRangeException))]
\r
1917 public void RemoveRangeBad3()
\r
1919 array.RemoveInterval(3, 8);
\r
1924 public void GetRange()
\r
1926 SCG.IEnumerable<int> e = array[3, 3];
\r
1928 Assert.IsTrue(IC.eq(e, 3, 4, 5));
\r
1930 Assert.IsTrue(IC.eq(e));
\r
1935 [ExpectedException(typeof(ArgumentOutOfRangeException))]
\r
1936 public void GetRangeBad1()
\r
1938 object foo = array[-3, 0];
\r
1943 [ExpectedException(typeof(ArgumentOutOfRangeException))]
\r
1944 public void GetRangeBad2()
\r
1946 object foo = array[3, -1];
\r
1951 [ExpectedException(typeof(ArgumentOutOfRangeException))]
\r
1952 public void GetRangeBad3()
\r
1954 object foo = array[3, 8];
\r
1959 public void Dispose() { array = null; array2 = null; }
\r
1969 public class SyncRoot
\r
1971 private SortedArray<int> tree;
\r
1977 public void Safe()
\r
1979 System.Threading.Thread t1 = new System.Threading.Thread(new System.Threading.ThreadStart(safe1));
\r
1980 System.Threading.Thread t2 = new System.Threading.Thread(new System.Threading.ThreadStart(safe2));
\r
1986 Assert.AreEqual(2 * sz + 1, tree.Count);
\r
1987 Assert.IsTrue(tree.Check());
\r
1992 public void UnSafe()
\r
1996 for (int i = 0; i < 10; i++)
\r
1998 System.Threading.Thread t1 = new System.Threading.Thread(new System.Threading.ThreadStart(unsafe1));
\r
1999 System.Threading.Thread t2 = new System.Threading.Thread(new System.Threading.ThreadStart(unsafe2));
\r
2005 if (bad = 2 * sz + 1 != tree.Count)
\r
2007 Console.WriteLine("{0}::Unsafe(): bad at {1}", GetType(), i);
\r
2012 Assert.IsTrue(bad, "No sync problems!");
\r
2017 public void SafeUnSafe()
\r
2019 System.Threading.Thread t1 = new System.Threading.Thread(new System.Threading.ThreadStart(unsafe1));
\r
2020 System.Threading.Thread t2 = new System.Threading.Thread(new System.Threading.ThreadStart(unsafe2));
\r
2026 Assert.AreEqual(2 * sz + 1, tree.Count);
\r
2031 public void Init() { tree = new SortedArray<int>(new IC()); }
\r
2034 private void unsafe1()
\r
2036 for (int i = 0; i < 2 * sz; i++)
\r
2039 for (int i = 1; i < sz; i++)
\r
2040 tree.Remove(i * 4);
\r
2044 private void safe1()
\r
2046 for (int i = 0; i < 2 * sz; i++)
\r
2047 lock (tree.SyncRoot)
\r
2050 for (int i = 1; i < sz; i++)
\r
2051 lock (tree.SyncRoot)
\r
2052 tree.Remove(i * 4);
\r
2056 private void unsafe2()
\r
2058 for (int i = 2 * sz; i > 0; i--)
\r
2059 tree.Add(i * 2 + 1);
\r
2061 for (int i = sz; i > 0; i--)
\r
2062 tree.Remove(i * 4 + 1);
\r
2066 private void safe2()
\r
2068 for (int i = 2 * sz; i > 0; i--)
\r
2069 lock (tree.SyncRoot)
\r
2070 tree.Add(i * 2 + 1);
\r
2072 for (int i = sz; i > 0; i--)
\r
2073 lock (tree.SyncRoot)
\r
2074 tree.Remove(i * 4 + 1);
\r
2079 public void Dispose() { tree = null; }
\r
2085 public class ConcurrentQueries
\r
2087 private SortedArray<int> tree;
\r
2093 public void Init()
\r
2095 tree = new SortedArray<int>(new IC());
\r
2096 for (int i = 0; i < sz; i++)
\r
2106 public int count = 0;
\r
2108 SortedArray<int> t;
\r
2111 public A(SortedArray<int> t) { this.t = t; }
\r
2114 public void a(int i) { count++; }
\r
2117 public void traverse() { t.Apply(new Act<int>(a)); }
\r
2124 public void Safe()
\r
2126 A a = new A(tree);
\r
2129 Assert.AreEqual(sz, a.count);
\r
2134 public void RegrettablyUnsafe()
\r
2136 System.Threading.Thread[] t = new System.Threading.Thread[10];
\r
2137 A[] a = new A[10];
\r
2138 for (int i = 0; i < 10; i++)
\r
2140 a[i] = new A(tree);
\r
2141 t[i] = new System.Threading.Thread(new System.Threading.ThreadStart(a[i].traverse));
\r
2144 for (int i = 0; i < 10; i++)
\r
2146 for (int i = 0; i < 10; i++)
\r
2148 for (int i = 0; i < 10; i++)
\r
2149 Assert.AreEqual(sz,a[i].count);
\r
2155 public void Dispose() { tree = null; }
\r
2165 public class ISequenced
\r
2167 private ISequenced<int> dit, dat, dut;
\r
2171 public void Init()
\r
2173 dit = new SortedArray<int>(8,Comparer<int>.Default, EqualityComparer<int>.Default);
\r
2174 dat = new SortedArray<int>(8,Comparer<int>.Default, EqualityComparer<int>.Default);
\r
2175 dut = new SortedArray<int>(8,new RevIC(), EqualityComparer<int>.Default);
\r
2180 public void EmptyEmpty()
\r
2182 Assert.IsTrue(dit.SequencedEquals(dat));
\r
2187 public void EmptyNonEmpty()
\r
2190 Assert.IsFalse(dit.SequencedEquals(dat));
\r
2191 Assert.IsFalse(dat.SequencedEquals(dit));
\r
2195 public void HashVal()
\r
2197 Assert.AreEqual(CHC.sequencedhashcode(), dit.GetSequencedHashCode());
\r
2199 Assert.AreEqual(CHC.sequencedhashcode(3), dit.GetSequencedHashCode());
\r
2201 Assert.AreEqual(CHC.sequencedhashcode(3, 7), dit.GetSequencedHashCode());
\r
2202 Assert.AreEqual(CHC.sequencedhashcode(), dut.GetSequencedHashCode());
\r
2204 Assert.AreEqual(CHC.sequencedhashcode(3), dut.GetSequencedHashCode());
\r
2206 Assert.AreEqual(CHC.sequencedhashcode(7, 3), dut.GetSequencedHashCode());
\r
2211 public void Normal()
\r
2216 Assert.IsFalse(dit.SequencedEquals(dat));
\r
2217 Assert.IsFalse(dat.SequencedEquals(dit));
\r
2219 Assert.IsTrue(dit.SequencedEquals(dat));
\r
2220 Assert.IsTrue(dat.SequencedEquals(dit));
\r
2225 public void WrongOrder()
\r
2229 Assert.IsTrue(dit.SequencedEquals(dut));
\r
2230 Assert.IsTrue(dut.SequencedEquals(dit));
\r
2233 Assert.IsFalse(dit.SequencedEquals(dut));
\r
2234 Assert.IsFalse(dut.SequencedEquals(dit));
\r
2239 public void Reflexive()
\r
2241 Assert.IsTrue(dit.SequencedEquals(dit));
\r
2243 Assert.IsTrue(dit.SequencedEquals(dit));
\r
2245 Assert.IsTrue(dit.SequencedEquals(dit));
\r
2250 public void Dispose()
\r
2261 public class IEditableCollection
\r
2263 private ICollection<int> dit, dat, dut;
\r
2267 public void Init()
\r
2269 dit = new SortedArray<int>(8,Comparer<int>.Default, EqualityComparer<int>.Default);
\r
2270 dat = new SortedArray<int>(8,Comparer<int>.Default, EqualityComparer<int>.Default);
\r
2271 dut = new SortedArray<int>(8,new RevIC(), EqualityComparer<int>.Default);
\r
2276 public void EmptyEmpty()
\r
2278 Assert.IsTrue(dit.UnsequencedEquals(dat));
\r
2283 public void EmptyNonEmpty()
\r
2286 Assert.IsFalse(dit.UnsequencedEquals(dat));
\r
2287 Assert.IsFalse(dat.UnsequencedEquals(dit));
\r
2292 public void HashVal()
\r
2294 Assert.AreEqual(CHC.unsequencedhashcode(), dit.GetUnsequencedHashCode());
\r
2296 Assert.AreEqual(CHC.unsequencedhashcode(3), dit.GetUnsequencedHashCode());
\r
2298 Assert.AreEqual(CHC.unsequencedhashcode(3, 7), dit.GetUnsequencedHashCode());
\r
2299 Assert.AreEqual(CHC.unsequencedhashcode(), dut.GetUnsequencedHashCode());
\r
2301 Assert.AreEqual(CHC.unsequencedhashcode(3), dut.GetUnsequencedHashCode());
\r
2303 Assert.AreEqual(CHC.unsequencedhashcode(7, 3), dut.GetUnsequencedHashCode());
\r
2308 public void Normal()
\r
2313 Assert.IsFalse(dit.UnsequencedEquals(dat));
\r
2314 Assert.IsFalse(dat.UnsequencedEquals(dit));
\r
2316 Assert.IsTrue(dit.UnsequencedEquals(dat));
\r
2317 Assert.IsTrue(dat.UnsequencedEquals(dit));
\r
2322 public void WrongOrder()
\r
2326 Assert.IsTrue(dit.UnsequencedEquals(dut));
\r
2327 Assert.IsTrue(dut.UnsequencedEquals(dit));
\r
2330 Assert.IsTrue(dit.UnsequencedEquals(dut));
\r
2331 Assert.IsTrue(dut.UnsequencedEquals(dit));
\r
2336 public void Reflexive()
\r
2338 Assert.IsTrue(dit.UnsequencedEquals(dit));
\r
2340 Assert.IsTrue(dit.UnsequencedEquals(dit));
\r
2342 Assert.IsTrue(dit.UnsequencedEquals(dit));
\r
2347 public void Dispose()
\r