5edfa95d833f — Michael Johnson 2 months ago
Merge 'Add extra tests around ShuffleInPlace'
M src/Benchmarks/Benchmarks.csproj +5 -1
@@ 12,9 12,13 @@ 
     <AnalysisLevel>8</AnalysisLevel>
   </PropertyGroup>
 
-  <ItemGroup>
+  <ItemGroup Condition="'$(TargetFramework)'!='net48'">
     <PackageReference Include="BenchmarkDotNet" Version="0.13.12" />
   </ItemGroup>
+  <ItemGroup Condition="'$(TargetFramework)'=='net48'">
+    <!-- 0.13.3 breaks with Mono on Linux, so we hold the .NET 4.8 target back -->
+    <PackageReference Include="BenchmarkDotNet" Version="0.13.2" />
+  </ItemGroup>
 
   <ItemGroup>
     <ProjectReference Include="..\Core\Core.csproj" />

          
M src/Benchmarks/Extensions.cs +0 -3
@@ 5,9 5,6 @@ using BenchmarkDotNet.Attributes;
 
 namespace RandN.Benchmarks;
 
-//[SimpleJob(BenchmarkDotNet.Jobs.RuntimeMoniker.Net48)]
-//[SimpleJob(BenchmarkDotNet.Jobs.RuntimeMoniker.Net60)]
-//[SimpleJob(BenchmarkDotNet.Jobs.RuntimeMoniker.Net80)]
 public class Extensions
 {
     public const Int32 Iterations = 16384;

          
M src/RandN/RngExtensions.cs +15 -13
@@ 9,7 9,8 @@ namespace RandN;
 /// <summary>
 /// Various extension methods to simplify use of RNGs.
 /// </summary>
-public static class RngExtensions {
+public static class RngExtensions
+{
     /// <summary>
     /// Shuffles a list using the in-place Fisher-Yates shuffling algorithm.
     /// </summary>

          
@@ 18,25 19,24 @@ public static class RngExtensions {
     public static void ShuffleInPlace<TRng, T>(this TRng rng, IList<T> list)
         where TRng : notnull, IRng
     {
-        if (list.GetType() == typeof(T[]))
+        if (list is T[] array)
         {
-            ShuffleInPlace(rng, Unsafe.As<T[]>(list).AsSpan());
+            ShuffleInPlace(rng, array.AsSpan());
             return;
         }
-#if NET5_0_OR_GREATER
-        else if (list.GetType() == typeof(List<T>))
+#if NET6_0_OR_GREATER
+        if (list is List<T> concrete)
         {
-            ShuffleInPlace(rng, CollectionsMarshal.AsSpan(Unsafe.As<List<T>>(list)));
+            ShuffleInPlace(rng, CollectionsMarshal.AsSpan(concrete));
             return;
         }
 #endif
         // Fisher-Yates shuffle
-        for (Int32 i = list.Count - 1; i >= 1; i--) {
+        for (Int32 i = list.Count - 1; i >= 1; i--)
+        {
             var dist = Uniform.NewInclusive(0, i);
             var swapIndex = dist.Sample(rng);
-            T temp = list[swapIndex];
-            list[swapIndex] = list[i];
-            list[i] = temp;
+            (list[swapIndex], list[i]) = (list[i], list[swapIndex]);
         }
     }
 

          
@@ 48,9 48,10 @@ public static class RngExtensions {
     public static void ShuffleInPlace<TRng, T>(this TRng rng, Span<T> span)
         where TRng : notnull, IRng
     {
-        ref var first = ref MemoryMarshal.GetReference(span); ;
+        ref var first = ref MemoryMarshal.GetReference(span);
         // Fisher-Yates shuffle
-        for (Int32 i = span.Length - 1; i >= 1; i--) {
+        for (Int32 i = span.Length - 1; i >= 1; i--)
+        {
             var dist = Uniform.NewInclusive(0, i);
             var swapIndex = dist.Sample(rng);
             ref var right = ref Unsafe.Add(ref first, i);

          
@@ 67,7 68,8 @@ public static class RngExtensions {
     /// <returns>A new <typeparamref name="TRng"/> instance.</returns>
     public static TRng Create<TRng, TSeed, TSeedingRng>(this IReproducibleRngFactory<TRng, TSeed> factory, TSeedingRng seedingRng)
         where TRng : notnull, IRng
-        where TSeedingRng : notnull, IRng {
+        where TSeedingRng : notnull, IRng
+    {
         var seed = factory.CreateSeed(seedingRng);
         return factory.Create(seed);
     }

          
M src/Tests/RngExtensionTests.cs +81 -6
@@ 1,5 1,8 @@ 
 using System;
+using System.Collections;
 using System.Collections.Generic;
+using System.Linq;
+using RandN.Rngs;
 using Xunit;
 
 namespace RandN;

          
@@ 7,17 10,27 @@ namespace RandN;
 public sealed class RngExtensionTests
 {
     [Fact]
-    public void Shuffle()
+    public void SimpleShuffle()
     {
-        var list = new List<Int32> { 1, 2, 3, 4, 5, 6, 7 };
+        Int32[] expectedOrder = [2, 3, 4, 5, 6, 7, 1];
+
+        Span<Int32> span = [1, 2, 3, 4, 5, 6, 7];
+        var array = span.ToArray();
+        var list = new List<Int32>(array);
+        var notList = new NotList(new List<Int32>(list));
         var rng = new StepRng(0) { Increment = 0 };
+
+        rng.ShuffleInPlace(span);
+        Assert.True(span.SequenceEqual(expectedOrder));
+
+        rng.ShuffleInPlace(array);
+        Assert.Equal(expectedOrder, array);
+
         rng.ShuffleInPlace(list);
-        var expectedOrder = new[] { 2, 3, 4, 5, 6, 7, 1 };
         Assert.Equal(expectedOrder, list);
 
-        Span<Int32> span = stackalloc Int32[] { 1, 2, 3, 4, 5, 6, 7 };
-        rng.ShuffleInPlace(span);
-        Assert.True(span.SequenceEqual(expectedOrder));
+        rng.ShuffleInPlace(notList);
+        Assert.Equal(expectedOrder, notList);
 
         Assert.Throws<ArgumentNullException>(() => rng.ShuffleInPlace(default(IList<Int32>)!));
 

          
@@ 26,4 39,66 @@ public sealed class RngExtensionTests
         rng.ShuffleInPlace(new List<Int32>());
         rng.ShuffleInPlace(Span<Int32>.Empty);
     }
+
+    [Theory]
+    [InlineData(0, 10ul)]
+    [InlineData(1, 20ul)]
+    [InlineData(2, 30ul)]
+    [InlineData(3, 40ul)]
+    [InlineData(7, 50ul)]
+    [InlineData(15, 60ul)]
+    [InlineData(16, 65ul)]
+    [InlineData(16384, 123ul)]
+    [InlineData(32768, 456ul)]
+    [InlineData(65536, 789ul)]
+    public void CompareShuffle(Int32 count, UInt64 seed)
+    {
+        var array = Enumerable.Range(0, count).ToArray();
+        var notList = new NotList(new List<Int32>(array));
+        
+        var arrayRng = Pcg32.Create(seed, 123);
+        var notListRng = Pcg32.Create(seed, 123);
+        
+        arrayRng.ShuffleInPlace(array);
+        notListRng.ShuffleInPlace(notList);
+        
+        Assert.Equal(array, notList);
+    }
+    
+    /// <summary>
+    /// This is used to ensure we test the non-span path for lists.
+    /// </summary>
+    /// <param name="wrapped"></param>
+    private sealed class NotList(IList<Int32> wrapped) : IList<Int32>
+    {
+        public IEnumerator<Int32> GetEnumerator() => wrapped.GetEnumerator();
+
+        IEnumerator IEnumerable.GetEnumerator() => ((IEnumerable)wrapped).GetEnumerator();
+
+        public void Add(Int32 item) => wrapped.Add(item);
+
+        public void Clear() => wrapped.Clear();
+
+        public Boolean Contains(Int32 item) => wrapped.Contains(item);
+
+        public void CopyTo(Int32[] array, Int32 arrayIndex) => wrapped.CopyTo(array, arrayIndex);
+
+        public Boolean Remove(Int32 item) => wrapped.Remove(item);
+
+        public Int32 Count => wrapped.Count;
+
+        public Boolean IsReadOnly => wrapped.IsReadOnly;
+
+        public Int32 IndexOf(Int32 item) => wrapped.IndexOf(item);
+
+        public void Insert(Int32 index, Int32 item) => wrapped.Insert(index, item);
+
+        public void RemoveAt(Int32 index) => wrapped.RemoveAt(index);
+
+        public Int32 this[Int32 index]
+        {
+            get => wrapped[index];
+            set => wrapped[index] = value;
+        }
+    }
 }