Ttykuu

Am simply wondering if I made any egregious mistakes while implementing the Alias Method as an IEnumerator<TElement>; would also like to know if there are any sorts of general improvements that can be made to the design of the class.

Usage:

var rng = Pcg32XshRr.New(0, 1);
var generator = ProbabilisticEnumerator
 .New(
 elementWeights: new Dictionary<string, int> 
 "A", 1 ,
 "B", 2 ,
 "C", 4 
 ,
 randomNumberGenerator: rng
 )
 .Take(100000);
var summary = generator
 .GroupBy(item => item)
 .Select(item => new 
 Element = item.Key,
 Count = item.Count(),
 )
 .OrderBy(item => item.Element);

foreach (var item in summary) item.Count");

Code:

Nuget Package

Source Repository

/// <summary>
/// Represents an enumerator that yields elements in accordance with the rules descibed by a probability table; relies on Michael D Vose's implementation of <a href="https://en.wikipedia.org/wiki/Alias_method">Walker's Alias Method.</a>
/// </summary>
/// <typeparam name="TElement">The type of elements encapsulated by the enumerator.</typeparam>
/// <remarks>
/// Derived from https://github.com/BlueRaja/Weighted-Item-Randomizer-for-C-Sharp.
/// </remarks>
public class ProbabilisticEnumerator<TElement> : IEnumerable<TElement>, IEnumerator<TElement>

 private readonly struct ElementMetadata
 
 public int ActualIndex get; 
 public int AliasedIndex get; 
 public int Threshold get; 

 public ElementMetadata(int actualIndex, int aliasedIndex, int biasAreaSize) 
 ActualIndex = actualIndex;
 AliasedIndex = aliasedIndex;
 Threshold = biasAreaSize;
 
 

 private readonly ElementMetadata[] m_elementMetadata;
 private readonly TElement[] m_elements;
 private readonly int m_heightPerRectangle;
 private readonly IUniformlyDistributedRandomNumberGenerator m_randomNumberGenerator;

 /// <summary>
 /// Gets the next random element.
 /// </summary>
 public TElement Current 
 get 
 var elementMetadata = m_elementMetadata;
 var elements = m_elements;
 var heightPerRectangle = m_heightPerRectangle;
 var randomNumberGenerator = m_randomNumberGenerator;
 var randomHeight = randomNumberGenerator.NextInt32(0, heightPerRectangle);
 var randomMetadata = elementMetadata[randomNumberGenerator.NextInt32(0, (elementMetadata.Length - 1))];

 return ((randomHeight <= randomMetadata.Threshold) ? elements[randomMetadata.ActualIndex] : elements[randomMetadata.AliasedIndex]);
 
 
 /// <summary>
 /// Gets the next random element.
 /// </summary>
 object IEnumerator.Current => Current;

 /// <summary>
 /// Initializes a new instance of the <see cref="ProbabilisticEnumeratorTElement"/> class.
 /// </summary>
 /// <param name="elementWeights">The collection of element-to-weight pairs that defines the rules for the table.</param>
 /// <param name="randomNumberGenerator">The source of random numbers that will be used to perform extract elements from the table.</param>
 private ProbabilisticEnumerator(IReadOnlyDictionary<TElement, int> elementWeights, IUniformlyDistributedRandomNumberGenerator randomNumberGenerator) 
 if (elementWeights.IsNull()) 
 throw new ArgumentNullException(paramName: nameof(elementWeights));
 

 var count = unchecked((ulong)elementWeights.Count);
 var elements = new TElement[count];
 var index = 0;
 var totalWeight = 0UL;

 foreach (var kvp in elementWeights) 
 var element = kvp.Key;
 var weight = kvp.Value;

 if (0 > weight) 
 throw new ArgumentOutOfRangeException(actualValue: weight, message: "weight must be a positive integer", paramName: nameof(weight));
 

 elements[index++] = element;
 totalWeight += unchecked((ulong)weight);
 

 var gcd = BitwiseHelpers.GreatestCommonDivisor(count, totalWeight);
 var heightPerRectangle = checked((int)(totalWeight / gcd));
 var weightMultiplier = checked((int)(count / gcd));

 m_elementMetadata = InitializeMetadata(elementWeights, weightMultiplier, heightPerRectangle);
 m_elements = elements;
 m_heightPerRectangle = heightPerRectangle;
 m_randomNumberGenerator = randomNumberGenerator;
 

 /// <summary>
 /// Releases all resources used by this <see cref="ProbabilisticEnumeratorTElement"/> instance.
 /// </summary>
 public void Dispose() 
 /// <summary>
 /// Returns an enumerator that yields a random element from the table.
 /// </summary>
 public IEnumerator<TElement> GetEnumerator() => this;
 /// <summary>
 /// Returns an enumerator that yields a random element from the table.
 /// </summary>
 IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
 /// <summary>
 /// Returns true.
 /// </summary>
 public bool MoveNext() => true;
 /// <summary>
 /// Throws <see cref="NotSupportedException"/>.
 /// </summary>
 public void Reset() => new NotSupportedException();

 private static ElementMetadata[] InitializeMetadata(IReadOnlyDictionary<TElement, int> elementWeights, int weightMultiplier, int heightPerRectangle) 
 var count = elementWeights.Count;
 var elementMetadata = new ElementMetadata[count];
 var index = 0;
 var stackLarge = new Stack<KeyValuePair<int, int>>();
 var stackSmall = new Stack<KeyValuePair<int, int>>();

 foreach (var kvp in elementWeights) 
 var newWeight = (kvp.Value * weightMultiplier);

 if (newWeight > heightPerRectangle) 
 stackLarge.Push(new KeyValuePair<int, int>(index++, newWeight));
 
 else 
 stackSmall.Push(new KeyValuePair<int, int>(index++, newWeight));
 
 

 while (0 < stackLarge.Count) 
 var largeItem = stackLarge.Pop();
 var smallItem = stackSmall.Pop();

 largeItem = new KeyValuePair<int, int>(largeItem.Key, (largeItem.Value - (heightPerRectangle - smallItem.Value)));

 if (largeItem.Value > heightPerRectangle) 
 stackLarge.Push(largeItem);
 
 else 
 stackSmall.Push(largeItem);
 

 elementMetadata[--count] = new ElementMetadata(smallItem.Key, largeItem.Key, smallItem.Value);
 

 while (0 < stackSmall.Count) 
 var smallItem = stackSmall.Pop();

 elementMetadata[--count] = new ElementMetadata(smallItem.Key, smallItem.Key, heightPerRectangle);
 

 return elementMetadata;
 

 /// <summary>
 /// Initializes a new instance of the <see cref="ProbabilisticEnumeratorTElement"/> class.
 /// </summary>
 /// <param name="elementWeights">The collection of element-to-weight pairs that defines the rules for the table.</param>
 /// <param name="randomNumberGenerator">The source of random numbers that will be used to perform extract elements from the table.</param>
 public static ProbabilisticEnumerator<TElement> New(IReadOnlyDictionary<TElement, int> elementWeights, IUniformlyDistributedRandomNumberGenerator randomNumberGenerator) => new ProbabilisticEnumerator<TElement>(elementWeights, randomNumberGenerator);


/// <summary>
/// A collection of methods that directly or indirectly augment the <see cref="ProbabilisticEnumeratorTElement"/> class.
/// </summary>
public static class ProbabilisticEnumerator

 /// <summary>
 /// Initializes a new instance of the <see cref="ProbabilisticEnumeratorTElement"/> class.
 /// </summary>
 /// <param name="elementWeights">The collection of element-to-weight pairs that defines the rules for the table.</param>
 /// <param name="randomNumberGenerator">The source of random numbers that will be used to perform extract elements from the table.</param>
 public static ProbabilisticEnumerator<TElement> New<TElement>(IReadOnlyDictionary<TElement, int> elementWeights, IUniformlyDistributedRandomNumberGenerator randomNumberGenerator) => ProbabilisticEnumerator<TElement>.New(elementWeights, randomNumberGenerator);