1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
4 
5 using System.Collections.Generic;
6 using System.Linq;
7 using Xunit;
8 
9 namespace System.Collections.Tests
10 {
11     /// <summary>
12     /// Contains tests that ensure the correctness of the SortedSet class.
13     /// </summary>
14     public abstract partial class SortedSet_Generic_Tests<T> : ISet_Generic_Tests<T>
15     {
16         #region ISet<T> Helper Methods
17 
GenericISetFactory()18         protected override ISet<T> GenericISetFactory()
19         {
20             return new SortedSet<T>();
21         }
22 
23         #endregion
24 
25         #region Constructors
26 
27         [Fact]
SortedSet_Generic_Constructor()28         public void SortedSet_Generic_Constructor()
29         {
30             SortedSet<T> set = new SortedSet<T>();
31             Assert.Empty(set);
32         }
33 
34         [Fact]
SortedSet_Generic_Constructor_IComparer()35         public void SortedSet_Generic_Constructor_IComparer()
36         {
37             IComparer<T> comparer = GetIComparer();
38             SortedSet<T> set = new SortedSet<T>(comparer);
39             Assert.Equal(comparer ?? Comparer<T>.Default, set.Comparer);
40         }
41 
42         [Theory]
43         [MemberData(nameof(EnumerableTestData))]
SortedSet_Generic_Constructor_IEnumerable(EnumerableType enumerableType, int setLength, int enumerableLength, int numberOfMatchingElements, int numberOfDuplicateElements)44         public void SortedSet_Generic_Constructor_IEnumerable(EnumerableType enumerableType, int setLength, int enumerableLength, int numberOfMatchingElements, int numberOfDuplicateElements)
45         {
46             IEnumerable<T> enumerable = CreateEnumerable(enumerableType, null, enumerableLength, 0, numberOfDuplicateElements);
47             SortedSet<T> set = new SortedSet<T>(enumerable);
48             Assert.True(set.SetEquals(enumerable));
49         }
50 
51         [Fact]
SortedSet_Generic_Constructor_IEnumerable_Null()52         public void SortedSet_Generic_Constructor_IEnumerable_Null()
53         {
54             Assert.Throws<ArgumentNullException>(() => new SortedSet<T>((IEnumerable<T>)null));
55             Assert.Throws<ArgumentNullException>(() => new SortedSet<T>((IEnumerable<T>)null, Comparer<T>.Default));
56         }
57 
58         [Theory]
59         [MemberData(nameof(EnumerableTestData))]
60         [ActiveIssue("dotnet/corefx #16790", TargetFrameworkMonikers.NetFramework)]
SortedSet_Generic_Constructor_IEnumerable_IComparer_Netcoreapp(EnumerableType enumerableType, int setLength, int enumerableLength, int numberOfMatchingElements, int numberOfDuplicateElements)61         public void SortedSet_Generic_Constructor_IEnumerable_IComparer_Netcoreapp(EnumerableType enumerableType, int setLength, int enumerableLength, int numberOfMatchingElements, int numberOfDuplicateElements)
62         {
63             IEnumerable<T> enumerable = CreateEnumerable(enumerableType, null, enumerableLength, 0, 0);
64             SortedSet<T> set = new SortedSet<T>(enumerable, GetIComparer());
65             Assert.True(set.SetEquals(enumerable));
66         }
67 
68         [Theory]
69         [MemberData(nameof(EnumerableTestData))]
70         [ActiveIssue("dotnet/corefx #16790", ~TargetFrameworkMonikers.NetFramework)]
SortedSet_Generic_Constructor_IEnumerable_IComparer_Netfx(EnumerableType enumerableType, int setLength, int enumerableLength, int numberOfMatchingElements, int numberOfDuplicateElements)71         public void SortedSet_Generic_Constructor_IEnumerable_IComparer_Netfx(EnumerableType enumerableType, int setLength, int enumerableLength, int numberOfMatchingElements, int numberOfDuplicateElements)
72         {
73             IEnumerable<T> enumerable = CreateEnumerable(enumerableType, null, enumerableLength, 0, 0);
74             SortedSet<T> set = new SortedSet<T>(enumerable, GetIComparer() ?? Comparer<T>.Default);
75             Assert.True(set.SetEquals(enumerable));
76         }
77 
78         [Theory]
79         [MemberData(nameof(EnumerableTestData))]
80         [ActiveIssue("dotnet/corefx #16790", TargetFrameworkMonikers.NetFramework)]
SortedSet_Generic_Constructor_IEnumerable_IComparer_NullComparer_Netcoreapp(EnumerableType enumerableType, int setLength, int enumerableLength, int numberOfMatchingElements, int numberOfDuplicateElements)81         public void SortedSet_Generic_Constructor_IEnumerable_IComparer_NullComparer_Netcoreapp(EnumerableType enumerableType, int setLength, int enumerableLength, int numberOfMatchingElements, int numberOfDuplicateElements)
82         {
83             IEnumerable<T> enumerable = CreateEnumerable(enumerableType, null, enumerableLength, 0, 0);
84             SortedSet<T> set = new SortedSet<T>(enumerable, comparer: null);
85             Assert.True(set.SetEquals(enumerable));
86         }
87 
88 #endregion
89 
90 #region Max and Min
91 
92         [Theory]
93         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_MaxAndMin(int setLength)94         public void SortedSet_Generic_MaxAndMin(int setLength)
95         {
96             SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
97             if (setLength > 0)
98             {
99                 List<T> expected = set.ToList();
100                 expected.Sort(GetIComparer());
101                 Assert.Equal(expected[0], set.Min);
102                 Assert.Equal(expected[setLength - 1], set.Max);
103             }
104             else
105             {
106                 Assert.Equal(default(T), set.Min);
107                 Assert.Equal(default(T), set.Max);
108             }
109         }
110 
111 #endregion
112 
113 #region GetViewBetween
114 
115         [Theory]
116         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_GetViewBetween_EntireSet(int setLength)117         public void SortedSet_Generic_GetViewBetween_EntireSet(int setLength)
118         {
119             if (setLength > 0)
120             {
121                 SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
122                 T firstElement = set.ElementAt(0);
123                 T lastElement = set.ElementAt(setLength - 1);
124                 SortedSet<T> view = set.GetViewBetween(firstElement, lastElement);
125                 Assert.Equal(setLength, view.Count);
126                 Assert.True(set.SetEquals(view));
127             }
128         }
129 
130         [Theory]
131         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_GetViewBetween_MiddleOfSet(int setLength)132         public void SortedSet_Generic_GetViewBetween_MiddleOfSet(int setLength)
133         {
134             if (setLength >= 3)
135             {
136                 IComparer<T> comparer = GetIComparer() ?? Comparer<T>.Default;
137                 SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
138                 T firstElement = set.ElementAt(1);
139                 T lastElement = set.ElementAt(setLength - 2);
140 
141                 List<T> expected = new List<T>(setLength - 2);
142                 foreach (T value in set)
143                     if (comparer.Compare(value, firstElement) >= 0 && comparer.Compare(value, lastElement) <= 0)
144                         expected.Add(value);
145 
146                 SortedSet<T> view = set.GetViewBetween(firstElement, lastElement);
147                 Assert.Equal(expected.Count, view.Count);
148                 Assert.True(view.SetEquals(expected));
149             }
150         }
151 
152         [Theory]
153         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_GetViewBetween_LowerValueGreaterThanUpperValue_ThrowsArgumentException(int setLength)154         public void SortedSet_Generic_GetViewBetween_LowerValueGreaterThanUpperValue_ThrowsArgumentException(int setLength)
155         {
156             if (setLength >= 2)
157             {
158                 IComparer<T> comparer = GetIComparer() ?? Comparer<T>.Default;
159                 SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
160                 T firstElement = set.ElementAt(0);
161                 T lastElement = set.ElementAt(setLength - 1);
162                 if (comparer.Compare(firstElement, lastElement) < 0)
163                     AssertExtensions.Throws<ArgumentException>("lowerValue", null, () => set.GetViewBetween(lastElement, firstElement));
164             }
165         }
166 
167         [Theory]
168         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_GetViewBetween_SubsequentOutOfRangeCall_ThrowsArgumentOutOfRangeException(int setLength)169         public void SortedSet_Generic_GetViewBetween_SubsequentOutOfRangeCall_ThrowsArgumentOutOfRangeException(int setLength)
170         {
171             if (setLength >= 3)
172             {
173                 SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
174                 IComparer<T> comparer = GetIComparer() ?? Comparer<T>.Default;
175                 T firstElement = set.ElementAt(0);
176                 T middleElement = set.ElementAt(setLength / 2);
177                 T lastElement = set.ElementAt(setLength - 1);
178                 if ((comparer.Compare(firstElement, middleElement) < 0) && (comparer.Compare(middleElement, lastElement) < 0))
179                 {
180                     SortedSet<T> view = set.GetViewBetween(firstElement, middleElement);
181                     Assert.Throws<ArgumentOutOfRangeException>(() => view.GetViewBetween(middleElement, lastElement));
182                 }
183             }
184         }
185 
186         [Theory]
187         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_GetViewBetween_Empty_MinMax(int setLength)188         public void SortedSet_Generic_GetViewBetween_Empty_MinMax(int setLength)
189         {
190             if (setLength < 4) return;
191 
192             SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
193             Assert.Equal(setLength, set.Count);
194 
195             T firstElement = set.ElementAt(0);
196             T secondElement = set.ElementAt(1);
197             T nextToLastElement = set.ElementAt(setLength - 2);
198             T lastElement = set.ElementAt(setLength - 1);
199 
200             T[] items = set.ToArray();
201             for (int i = 1; i < setLength - 1; i++)
202             {
203                 set.Remove(items[i]);
204             }
205             Assert.Equal(2, set.Count);
206 
207             SortedSet<T> view = set.GetViewBetween(secondElement, nextToLastElement);
208             Assert.Equal(0, view.Count);
209 
210             Assert.Equal(default(T), view.Min);
211             Assert.Equal(default(T), view.Max);
212         }
213 
214         #endregion
215 
216 #region RemoveWhere
217 
218         [Theory]
219         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_RemoveWhere_AllElements(int setLength)220         public void SortedSet_Generic_RemoveWhere_AllElements(int setLength)
221         {
222             SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
223             int removedCount = set.RemoveWhere((value) => { return true; });
224             Assert.Equal(setLength, removedCount);
225         }
226 
227         [Theory]
228         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_RemoveWhere_NoElements(int setLength)229         public void SortedSet_Generic_RemoveWhere_NoElements(int setLength)
230         {
231             SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
232             int removedCount = set.RemoveWhere((value) => { return false; });
233             Assert.Equal(0, removedCount);
234             Assert.Equal(setLength, set.Count);
235         }
236 
237         [Fact]
SortedSet_Generic_RemoveWhere_NullPredicate_ThrowsArgumentNullException()238         public void SortedSet_Generic_RemoveWhere_NullPredicate_ThrowsArgumentNullException()
239         {
240             SortedSet<T> set = (SortedSet<T>)GenericISetFactory();
241             AssertExtensions.Throws<ArgumentNullException>("match", () => set.RemoveWhere(null));
242         }
243 
244 #endregion
245 
246 #region Enumeration and Ordering
247 
248         [Theory]
249         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_SetIsProperlySortedAccordingToComparer(int setLength)250         public void SortedSet_Generic_SetIsProperlySortedAccordingToComparer(int setLength)
251         {
252             SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
253             List<T> expected = set.ToList();
254             expected.Sort(GetIComparer());
255             int expectedIndex = 0;
256             foreach (T value in set)
257                 Assert.Equal(expected[expectedIndex++], value);
258         }
259 
260         [Theory]
261         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_ReverseSetIsProperlySortedAccordingToComparer(int setLength)262         public void SortedSet_Generic_ReverseSetIsProperlySortedAccordingToComparer(int setLength)
263         {
264             SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
265             List<T> expected = set.ToList();
266             expected.Sort(GetIComparer());
267             expected.Reverse();
268             int expectedIndex = 0;
269             foreach (T value in set.Reverse())
270                 Assert.Equal(expected[expectedIndex++], value);
271         }
272 
273         [Fact]
SortedSet_Generic_TestSubSetEnumerator()274         public void SortedSet_Generic_TestSubSetEnumerator()
275         {
276             SortedSet<int> sortedSet = new SortedSet<int>();
277             for (int i = 0; i < 10000; i++)
278             {
279                 if (!sortedSet.Contains(i))
280                     sortedSet.Add(i);
281             }
282             SortedSet<int> mySubSet = sortedSet.GetViewBetween(45, 90);
283 
284             Assert.Equal(46, mySubSet.Count); //"not all elements were encountered"
285 
286             IEnumerable<int> en = mySubSet.Reverse();
287             Assert.True(mySubSet.SetEquals(en)); //"Expected to be the same set."
288         }
289 
290 #endregion
291 
292 #region CopyTo
293 
294         [Theory]
295         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_CopyTo_WithoutIndex(int setLength)296         public void SortedSet_Generic_CopyTo_WithoutIndex(int setLength)
297         {
298             SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
299             List<T> expected = set.ToList();
300             expected.Sort(GetIComparer());
301             T[] actual = new T[setLength];
302             set.CopyTo(actual);
303             Assert.Equal(expected, actual);
304         }
305 
306         [Theory]
307         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_CopyTo_WithValidFullCount(int setLength)308         public void SortedSet_Generic_CopyTo_WithValidFullCount(int setLength)
309         {
310             SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
311             List<T> expected = set.ToList();
312             expected.Sort(GetIComparer());
313             T[] actual = new T[setLength];
314             set.CopyTo(actual, 0, setLength);
315             Assert.Equal(expected, actual);
316         }
317 
318         [Theory]
319         [MemberData(nameof(ValidCollectionSizes))]
SortedSet_Generic_CopyTo_NegativeCount_ThrowsArgumentOutOfRangeException(int setLength)320         public void SortedSet_Generic_CopyTo_NegativeCount_ThrowsArgumentOutOfRangeException(int setLength)
321         {
322             SortedSet<T> set = (SortedSet<T>)GenericISetFactory(setLength);
323             T[] actual = new T[setLength];
324             Assert.Throws<ArgumentOutOfRangeException>(() => set.CopyTo(actual, 0, -1));
325             Assert.Throws<ArgumentOutOfRangeException>(() => set.CopyTo(actual, 0, int.MinValue));
326         }
327 
328 #endregion
329 
330 #region CreateSetComparer
331 
332         [Fact]
SetComparer_SetEqualsTests()333         public void SetComparer_SetEqualsTests()
334         {
335             List<T> objects = new List<T>() { CreateT(1), CreateT(2), CreateT(3), CreateT(4), CreateT(5), CreateT(6) };
336 
337             var set = new HashSet<SortedSet<T>>()
338             {
339                 new SortedSet<T> { objects[0], objects[1], objects[2] },
340                 new SortedSet<T> { objects[3], objects[4], objects[5] }
341             };
342 
343             var noComparerSet = new HashSet<SortedSet<T>>()
344             {
345                 new SortedSet<T> { objects[0], objects[1], objects[2] },
346                 new SortedSet<T> { objects[3], objects[4], objects[5] }
347             };
348 
349             var comparerSet1 = new HashSet<SortedSet<T>>(SortedSet<T>.CreateSetComparer())
350             {
351                 new SortedSet<T> { objects[0], objects[1], objects[2] },
352                 new SortedSet<T> { objects[3], objects[4], objects[5] }
353             };
354 
355             var comparerSet2 = new HashSet<SortedSet<T>>(SortedSet<T>.CreateSetComparer())
356             {
357                 new SortedSet<T> { objects[3], objects[4], objects[5] },
358                 new SortedSet<T> { objects[0], objects[1], objects[2] }
359             };
360 
361             Assert.False(noComparerSet.SetEquals(set));
362             Assert.True(comparerSet1.SetEquals(set));
363             Assert.True(comparerSet2.SetEquals(set));
364         }
365 #endregion
366     }
367 }
368