5 // Jb Evain <jbevain@novell.com>
7 // Copyright (C) 2010 Novell, Inc (http://www.novell.com)
9 // Permission is hereby granted, free of charge, to any person obtaining
10 // a copy of this software and associated documentation files (the
11 // "Software"), to deal in the Software without restriction, including
12 // without limitation the rights to use, copy, modify, merge, publish,
13 // distribute, sublicense, and/or sell copies of the Software, and to
14 // permit persons to whom the Software is furnished to do so, subject to
15 // the following conditions:
17 // The above copyright notice and this permission notice shall be
18 // included in all copies or substantial portions of the Software.
20 // THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
21 // EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
22 // MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND
23 // NONINFRINGEMENT. IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE
24 // LIABLE FOR ANY CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION
25 // OF CONTRACT, TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION
26 // WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
32 using System.Collections;
33 using System.Collections.Generic;
35 using System.Runtime.Serialization;
37 using NUnit.Framework;
39 namespace MonoTests.System.Collections.Generic
42 public class SortedSetTest
45 public void CtorNullComparer ()
47 var set = new SortedSet<int> ((IComparer<int>) null);
48 Assert.AreEqual (Comparer<int>.Default, set.Comparer);
52 [ExpectedException (typeof (ArgumentNullException))]
53 public void CtorNullCollection ()
55 new SortedSet<int> (null as IEnumerable<int>);
59 public void CtorDefault ()
61 var set = new SortedSet<int> ();
62 Assert.IsNotNull (set.Comparer);
68 var set = new SortedSet<int> ();
69 Assert.AreEqual (0, set.Count);
70 Assert.IsTrue (set.Add (2));
71 Assert.IsTrue (set.Add (4));
72 Assert.IsTrue (set.Add (3));
73 Assert.AreEqual (3, set.Count);
74 Assert.IsFalse (set.Add (2));
80 var set = new SortedSet<int> ();
81 Assert.IsTrue (set.Add (2));
82 Assert.IsTrue (set.Add (4));
83 Assert.AreEqual (2, set.Count);
84 Assert.IsTrue (set.Remove (4));
85 Assert.IsTrue (set.Remove (2));
86 Assert.AreEqual (0, set.Count);
87 Assert.IsFalse (set.Remove (4));
88 Assert.IsFalse (set.Remove (2));
94 var set = new SortedSet<int> { 2, 3, 4, 5 };
95 Assert.AreEqual (4, set.Count);
97 Assert.AreEqual (0, set.Count);
101 public void Contains ()
103 var set = new SortedSet<int> { 2, 3, 4, 5 };
104 Assert.IsTrue (set.Contains (4));
105 Assert.IsFalse (set.Contains (7));
109 public void GetEnumerator ()
111 var set = new SortedSet<int> { 5, 3, 1, 2, 6, 4 };
112 Assert.IsTrue (set.SequenceEqual (new [] { 1, 2, 3, 4, 5, 6 }));
116 public void Reverse ()
118 var set = new SortedSet<int> { 5, 3, 1, 2, 6, 4 };
119 var reversed = set.Reverse ();
120 Assert.IsTrue (reversed.SequenceEqual (new [] { 6, 5, 4, 3, 2, 1 }));
124 public void RemoveWhere ()
126 var set = new SortedSet<int> { 1, 2, 3, 4, 5, 6 };
127 Assert.AreEqual (3, set.RemoveWhere (i => i % 2 == 0));
128 Assert.AreEqual (3, set.Count);
129 Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 5 }));
136 var set = new SortedSet<int> { 1, 3, 12, 9 };
137 Assert.AreEqual (12, set.Max);
143 var set = new SortedSet<int> { 2, 3, 1, 9 };
144 Assert.AreEqual (1, set.Min);
148 [ExpectedException (typeof (ArgumentException))]
149 public void GetViewBetweenLowerBiggerThanUpper ()
151 var set = new SortedSet<int> { 1, 2, 3, 4, 5, 6 };
152 set.GetViewBetween (4, 2);
156 public void GetView ()
158 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
159 var view = set.GetViewBetween (3, 7);
161 Assert.IsTrue (view.SequenceEqual (new [] { 3, 5, 7 }));
165 public void ViewAdd ()
167 var set = new SortedSet<int> { 1, 3, 5, 7 };
168 var view = set.GetViewBetween (3, 5);
170 Assert.IsTrue (view.Add (4));
171 Assert.IsTrue (view.Contains (4));
172 Assert.IsTrue (set.Contains (4));
174 Assert.IsFalse (view.Add (5));
178 [ExpectedException (typeof (ArgumentOutOfRangeException))]
179 public void ViewAddOutOfRange ()
181 var set = new SortedSet<int> { 1, 3, 5, 7 };
182 var view = set.GetViewBetween (3, 5);
188 public void ViewContains ()
190 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
191 var view = set.GetViewBetween (3, 7);
193 Assert.IsFalse (view.Contains (4));
194 Assert.IsTrue (view.Contains (3));
195 Assert.IsTrue (view.Contains (5));
199 public void ViewRemove ()
201 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
202 var view = set.GetViewBetween (3, 7);
204 Assert.IsTrue (view.Remove (3));
205 Assert.IsFalse (view.Contains (3));
206 Assert.IsFalse (set.Contains (3));
207 Assert.IsFalse (view.Remove (9));
208 Assert.IsTrue (set.Contains (9));
212 public void ViewClear ()
214 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
215 var view = set.GetViewBetween (3, 7);
219 Assert.AreEqual (0, view.Count);
220 Assert.IsTrue (set.SequenceEqual (new [] { 1, 9 }));
224 [ExpectedException (typeof (ArgumentOutOfRangeException))]
225 public void ViewGetViewLowerOutOfRange ()
227 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
228 var view = set.GetViewBetween (3, 7);
229 view.GetViewBetween (2, 5);
233 [ExpectedException (typeof (ArgumentOutOfRangeException))]
234 public void ViewGetViewUpperOutOfRange ()
236 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
237 var view = set.GetViewBetween (3, 7);
238 view.GetViewBetween (5, 9);
242 public void ViewGetView ()
244 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
245 var view = set.GetViewBetween (3, 7);
246 view = view.GetViewBetween (4, 6);
248 Assert.IsTrue (view.SequenceEqual (new [] { 5 }));
251 void EmptySubView (SortedSet<int> set)
253 var view = set.GetViewBetween (-20, -15);
254 Assert.AreEqual (0, view.Count);
255 Assert.AreEqual (0, view.Min);
256 Assert.AreEqual (0, view.Max);
258 view = set.GetViewBetween (15, 20);
259 Assert.AreEqual (0, view.Count);
260 Assert.AreEqual (0, view.Min);
261 Assert.AreEqual (0, view.Max);
265 public void EmptySubView ()
267 EmptySubView (new SortedSet<int> ());
268 EmptySubView (new SortedSet<int> { 1, 3, 5, 7, 9 });
269 EmptySubView (new SortedSet<int> { -40, 40 });
270 EmptySubView (new SortedSet<int> { -40, -10, 10, 40 });
274 public void ViewMin ()
276 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
278 var view = set.GetViewBetween (4, 8);
279 Assert.AreEqual (5, view.Min);
281 view = set.GetViewBetween (-2, 4);
282 Assert.AreEqual (1, view.Min);
284 view = set.GetViewBetween (1, 9);
285 Assert.AreEqual (1, view.Min);
289 public void ViewMax ()
291 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
293 var view = set.GetViewBetween (4, 8);
294 Assert.AreEqual (7, view.Max);
296 view = set.GetViewBetween (4, 55);
297 Assert.AreEqual (9, view.Max);
299 view = set.GetViewBetween (1, 9);
300 Assert.AreEqual (9, view.Max);
304 public void ViewCount ()
306 var set = new SortedSet<int> { 1, 3, 4, 5, 6, 7, 8, 9 };
307 var view = set.GetViewBetween (4, 8);
309 Assert.AreEqual (5, view.Count);
311 Assert.AreEqual (4, view.Count);
313 Assert.AreEqual (4, view.Count);
315 Assert.AreEqual (4, view.Count);
317 Assert.AreEqual (5, view.Count);
320 [Test, ExpectedException (typeof (ArgumentNullException))]
321 public void IntersectWith_Null ()
323 var set = new SortedSet<int> ();
324 set.IntersectWith (null);
328 public void IntersectWith ()
330 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
331 set.IntersectWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
332 Assert.IsTrue (set.SequenceEqual (new [] { 3, 5, 7 }));
336 public void ViewIntersectWith ()
338 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
339 var view = set.GetViewBetween (4, 8);
340 view.IntersectWith (new [] { 1, 5, 9 });
341 Assert.IsTrue (view.SequenceEqual (new [] { 5 }));
342 Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 5, 9 }));
343 view.IntersectWith (new [] { 1, 2 });
344 Assert.IsTrue (view.SequenceEqual (new int [] {}));
345 Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 9 }));
348 [Test, ExpectedException (typeof (ArgumentNullException))]
349 public void UnionWith_Null ()
351 var set = new SortedSet<int> ();
352 set.UnionWith (null);
356 public void UnionWith ()
358 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
359 set.UnionWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
360 Assert.IsTrue (set.SequenceEqual (new [] { 1, 2, 3, 5, 7, 9, 11 }));
364 public void ViewUnionWith ()
366 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
367 var view = set.GetViewBetween (4, 8);
368 view.UnionWith (new [] { 4, 5, 6, 6, 4 });
369 Assert.IsTrue (view.SequenceEqual (new [] { 4, 5, 6, 7 }));
370 Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 4, 5, 6, 7, 9 }));
373 [Test, ExpectedException (typeof (ArgumentOutOfRangeException))]
374 public void ViewUnionWith_oor ()
376 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
377 var view = set.GetViewBetween (4, 8);
378 view.UnionWith (new [] {1});
381 [Test, ExpectedException (typeof (ArgumentNullException))]
382 public void ExceptWith_Null ()
384 var set = new SortedSet<int> ();
385 set.ExceptWith (null);
389 public void ExceptWith ()
391 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
392 set.ExceptWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
393 Assert.IsTrue (set.SequenceEqual (new [] { 1, 9 }));
397 public void ViewExceptWith ()
399 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
400 var view = set.GetViewBetween (4, 8);
401 view.ExceptWith (new [] { 4, 5, 6, 6, 4 });
402 Assert.IsTrue (view.SequenceEqual (new [] { 7 }));
403 Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 7, 9 }));
404 view.ExceptWith (new [] { 1, 2 });
405 Assert.IsTrue (view.SequenceEqual (new [] { 7 }));
406 Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 7, 9 }));
409 [Test, ExpectedException (typeof (ArgumentNullException))]
410 public void SymmetricExceptWith_Null ()
412 var set = new SortedSet<int> ();
413 set.SymmetricExceptWith (null);
417 public void SymmetricExceptWith ()
419 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
420 set.SymmetricExceptWith (new [] { 5, 7, 3, 7, 11, 7, 5, 2 });
421 Assert.IsTrue (set.SequenceEqual (new [] { 1, 2, 9, 11 }));
425 public void ViewSymmetricExceptWith ()
427 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
428 var view = set.GetViewBetween (4, 8);
429 view.SymmetricExceptWith (new [] { 4, 5, 6, 6, 4 });
430 Assert.IsTrue (view.SequenceEqual (new [] { 4, 6, 7 }));
431 Assert.IsTrue (set.SequenceEqual (new [] { 1, 3, 4, 6, 7, 9 }));
434 [Test, ExpectedException (typeof (ArgumentOutOfRangeException))]
435 public void ViewSymmetricExceptWith_oor ()
437 var set = new SortedSet<int> { 1, 3, 5, 7, 9 };
438 var view = set.GetViewBetween (4, 8);
439 view.SymmetricExceptWith (new [] {2});
442 void do_test_e (SortedSet<int> s1, IEnumerable<int> s2, bool o, bool se = false, bool psb = false, bool psu = false)
444 bool sb = false, su = false;
452 Assert.IsTrue (!su || !psb);
453 Assert.IsTrue (!sb || !psu);
456 Assert.AreEqual (o, s1.Overlaps (s2));
457 Assert.AreEqual (se, s1.SetEquals (s2));
458 Assert.AreEqual (sb, s1.IsSubsetOf (s2));
459 Assert.AreEqual (su, s1.IsSupersetOf (s2));
460 Assert.AreEqual (psb, s1.IsProperSubsetOf (s2));
461 Assert.AreEqual (psu, s1.IsProperSupersetOf (s2));
464 void do_test (SortedSet<int> s1, SortedSet<int> s2, bool o = false, bool se = false, bool psb = false, bool psu = false)
466 if (s1.Count != 0 && s2.Count != 0 && (se || psb || psu))
468 do_test_e (s1, s2, o, se, psb, psu);
469 do_test_e (s2, s1, o, se, psu, psb);
473 public void TestSetCompares ()
475 var empty = new SortedSet<int> ();
476 var zero = new SortedSet<int> { 0 };
477 var one = new SortedSet<int> { 1 };
478 var two = new SortedSet<int> { 2 };
479 var bit = new SortedSet<int> { 0, 1 };
480 var trit = new SortedSet<int> { 0, 1, 2 };
481 var odds = new SortedSet<int> { 1, 3, 5, 7, 9 };
482 var evens = new SortedSet<int> { 2, 4, 6, 8 };
483 var digits = new SortedSet<int> { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
484 var squares = new SortedSet<int> { 0, 1, 4, 9 };
486 var non_prime_odd_digit = odds.GetViewBetween (8, 42);
487 var non_trit = digits.GetViewBetween (3, 42);
489 do_test (empty, empty, se: true);
490 do_test (empty, zero, psb: true);
491 do_test (empty, digits, psb: true);
492 do_test (zero, zero, se: true);
494 do_test (zero, bit, psb: true);
495 do_test (zero, trit, psb: true);
496 do_test (one, bit, psb: true);
497 do_test (one, trit, psb: true);
499 do_test (two, trit, psb: true);
500 do_test (odds, squares, o: true);
501 do_test (evens, squares, o: true);
502 do_test (odds, digits, psb: true);
503 do_test (evens, digits, psb: true);
504 do_test (squares, digits, psb: true);
505 do_test (digits, digits, se: true);
506 do_test_e (digits, squares.Concat (evens.Concat (odds)), o: true, se: true);
507 do_test (non_prime_odd_digit, digits, psb: true);
508 do_test_e (non_prime_odd_digit, new [] { 9 }, o: true, se: true);
509 do_test (non_trit, digits, psb: true);
510 do_test (trit, non_trit);
511 do_test_e (digits, trit.Concat (non_trit), o: true, se: true);
512 do_test_e (non_trit, new [] { 3, 4, 5, 6, 7, 8, 9 }, o: true, se: true);
513 do_test (digits.GetViewBetween (0, 2), trit, se: true);