Guest User

Untitled

a guest
Sep 1st, 2021
80
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. public class ReferenceCompare<T> : IComparer<T> where T : class
  2.     {
  3.         public int Compare(T x, T y)
  4.         {
  5.             if (x == y) return 0;
  6.  
  7.             return -1;
  8.         }
  9.     }
  10.  
  11.     /// <summary>
  12.     /// Stores a full specification of combinations to generate, and allows the construction of enumerators to generate the combinations.
  13.     /// </summary>
  14.     /// <typeparam name="T">the type to generate combinations of</typeparam>
  15.     public class Combinations<T> : IEnumerable<T[]> {
  16.         #region Combinations Members
  17.         private readonly ElementSet<T> _elements;
  18.         private readonly int _choose;
  19.        
  20.         /// <summary>
  21.         /// Constructs a new <c>Combinations</c> given a collection of elements and how many elements should be present in each combination. Note that if the same collection of elements is used with multiple <paramref name="choose"/> values, it is faster to construct an <see cref="ElementSet{T}"/> once and use <see cref="Combinations{T}(ElementSet{T}, int)"/>.
  22.         /// </summary>
  23.         /// <param name="elements">the collection of elements</param>
  24.         /// <param name="choose">the length of a combination</param>
  25.         public Combinations(IEnumerable<T> elements, int choose)
  26.             : this(new ElementSet<T>(elements, null), choose) {
  27.         }
  28.  
  29.         /// <summary>
  30.         /// Constructs a new <c>Combinations</c> given a collection of elements and how many elements should be present in each combination. Note that if the same collection of elements is used with multiple <paramref name="choose"/> values, it is faster to construct an <see cref="ElementSet{T}"/> once and use <see cref="Combinations{T}(ElementSet{T}, int)"/>.
  31.         /// </summary>
  32.         /// <param name="elements">the collection of elements</param>
  33.         /// <param name="choose">the length of a combination</param>
  34.         /// <param name="comparer">the comparer used to order the elements</param>
  35.         public Combinations(IEnumerable<T> elements, IComparer<T> comparer, int choose)
  36.             : this(new ElementSet<T>(elements, comparer), choose) {
  37.         }
  38.  
  39.         /// <summary>
  40.         /// Constructs a new <c>Combinations</c> given a collection of elements and how many elements should be present in each combination. If the same set of elements will be used with different values of <paramref name="choose"/>, this constructor is the best choice as the elements are processed only once, during the construction of the <see cref="ElementSet{T}"/>.
  41.         /// </summary>
  42.         /// <param name="elements">the collection of elements</param>
  43.         /// <param name="choose">the length of a combination</param>
  44.         public Combinations(ElementSet<T> elements, int choose) {
  45.             if (elements == null) {
  46.                 throw new ArgumentNullException(nameof(elements));
  47.             }
  48.             if (choose < 0 || choose > elements.Count) {
  49.                 throw new ArgumentOutOfRangeException(nameof(choose));
  50.             }
  51.             _elements = elements;
  52.             _choose = choose;
  53.         }
  54.         #endregion
  55.  
  56.         #region IEnumerable<T[]> Members
  57.         /// <summary>
  58.         /// Creates and returns an enumerator over the combinations. Each combination's elements will be returned in ascending order as defined by the compararer. The combinations themselves will also be returned in ascending order.
  59.         /// </summary>
  60.         /// <returns>an enumerator</returns>
  61.         /// <seealso cref="IEnumerable{T}.GetEnumerator"/>
  62.         public IEnumerator<T[]> GetEnumerator() {
  63.             if (_choose == 0) {
  64.                 return new ChooseZeroEnumerator();
  65.             } else {
  66.                 return new Enumerator(this);
  67.             }
  68.         }
  69.         #endregion
  70.  
  71.         #region IEnumerable Members
  72.         IEnumerator IEnumerable.GetEnumerator() {
  73.             return new Enumerator(this);
  74.         }
  75.         #endregion
  76.  
  77.         #region Enumerator Class
  78.         private class Enumerator : IEnumerator<T[]> {
  79.             #region Enumerator Members
  80.             private readonly Combinations<T> _combinations;
  81.             private readonly int[] _indices;
  82.             private readonly int[] _indicesAt;
  83.             private bool _pastEnd;
  84.  
  85.             internal Enumerator(Combinations<T> combinations) {
  86.                 _combinations = combinations;
  87.                 _indices = new int[_combinations._choose];
  88.                 _indicesAt = new int[_combinations._elements.Elements.Count];
  89.                 Reset();
  90.             }
  91.  
  92.             private void MoveFirst() {
  93.                 // Move all the indices as far left as possible.
  94.                 // Lower-numbered indices go further left.
  95.                 int currentIndex = 0;
  96.                 int usedCurrent = 0;
  97.                 for (int i = 0; i < _indices.Length; i++) {
  98.                     Debug.Assert(currentIndex < _combinations._elements.Elements.Count);
  99.                     _indices[i] = currentIndex;
  100.                     _indicesAt[currentIndex]++;
  101.                     usedCurrent++;
  102.                     if (usedCurrent == _combinations._elements.Elements.Values[currentIndex]) {
  103.                         // We've used all of the current element. Go to the next element.
  104.                         currentIndex++;
  105.                         usedCurrent = 0;
  106.                     }
  107.                 }
  108.             }
  109.  
  110.             private void MoveIndex(int index, int offset) {
  111.                 if (_indices[index] >= 0 && _indices[index] < _indicesAt.Length) {
  112.                     _indicesAt[_indices[index]]--;
  113.                 }
  114.                 _indices[index] += offset;
  115.                 if (_indices[index] >= 0 && _indices[index] < _indicesAt.Length) {
  116.                     _indicesAt[_indices[index]]++;
  117.                 }
  118.             }
  119.  
  120.             private bool IsFull(int position) {
  121.                 // True if (position) has as many indices as it can hold.
  122.                 return _indicesAt[position] == _combinations._elements.Elements.Values[position];
  123.             }
  124.  
  125.             private bool CanFitRemainingIndices(int index) {
  126.                 int space = _combinations._elements.ElementsAtOrAfter[_indices[index]];
  127.                 return space >= _indices.Length - index;
  128.             }
  129.  
  130.             private bool AdvanceIndex(int index, int doNotReach) {
  131.                 // First move the index one position to the right.
  132.                 MoveIndex(index, 1);
  133.                 // If we've found an existing position with no other index, and there's room at-and-to-the-right-of us for all the indices greater than us, we're good.
  134.                 if (_indices[index] < doNotReach) {
  135.                     if (_indicesAt[_indices[index]] == 1) {
  136.                         if (CanFitRemainingIndices(index)) {
  137.                             return true;
  138.                         }
  139.                     }
  140.                 }
  141.                 // We've either fallen off the right hand edge, or hit a position with another index. If we're index 0, we're past the end of the enumeration. If not, we need to advance the next lower index, then push ourself left as far as possible until we hit another occupied position.
  142.                 if (index == 0) {
  143.                     _pastEnd = true;
  144.                     return false;
  145.                 }
  146.                 if (!AdvanceIndex(index - 1, _indices[index])) {
  147.                     return false;
  148.                 }
  149.                 // We must move at least one space to the left. If we can't, the enumeration is over.
  150.                 // If the position immediately to the left is already full, we can't move there.
  151.                 if (IsFull(_indices[index] - 1)) {
  152.                     _pastEnd = true;
  153.                     return false;
  154.                 }
  155.                 // Move left until the next leftmost element is full, or the current element has an index.
  156.                 do {
  157.                     MoveIndex(index, -1);
  158.                 } while (_indicesAt[_indices[index]] == 1 && !IsFull(_indices[index] - 1));
  159.                 return true;
  160.             }
  161.             #endregion
  162.  
  163.             #region IEnumerator<T[]> Members
  164.             public T[] Current {
  165.                 get {
  166.                     if (_indices[0] == -1 || _pastEnd) {
  167.                         // Before first or after last.
  168.                         throw new InvalidOperationException();
  169.                     } else {
  170.                         T[] current = new T[_indices.Length];
  171.                         for (int i = 0; i < _indices.Length; i++) {
  172.                             current[i] = _combinations._elements.Elements.Keys[_indices[i]];
  173.                         }
  174.                         return current;
  175.                     }
  176.                 }
  177.             }
  178.             #endregion
  179.  
  180.             #region IDisposable Members
  181.             public void Dispose() {
  182.                 // Do nothing.
  183.             }
  184.             #endregion
  185.  
  186.             #region IEnumerator Members
  187.             object IEnumerator.Current => Current;
  188.  
  189.             public bool MoveNext() {
  190.                 if (_pastEnd) {
  191.                     return false;
  192.                 }
  193.                 if (_indices[0] == -1) {
  194.                     MoveFirst();
  195.                     return true;
  196.                 } else {
  197.                     bool ret = AdvanceIndex(_indices.Length - 1, _indicesAt.Length);
  198.                     return ret;
  199.                 }
  200.             }
  201.  
  202.             public void Reset() {
  203.                 for (int i = 0; i < _indices.Length; i++) {
  204.                     _indices[i] = -1;
  205.                 }
  206.                 Array.Clear(_indicesAt, 0, _indicesAt.Length);
  207.                 _pastEnd = false;
  208.             }
  209.             #endregion
  210.         }
  211.         #endregion
  212.  
  213.         #region ChooseZeroEnumerator Class
  214.         private class ChooseZeroEnumerator : IEnumerator<T[]> {
  215.             #region ChooseZeroEnumerator Members
  216.             private enum State {
  217.                 BeforeBeginning,
  218.                 OnElement,
  219.                 PastEnd,
  220.             }
  221.  
  222.             private State _state;
  223.  
  224.             internal ChooseZeroEnumerator() {
  225.                 Reset();
  226.             }
  227.             #endregion
  228.  
  229.             #region IEnumerator<T[]> Members
  230.             public T[] Current {
  231.                 get {
  232.                     if (_state == State.OnElement) {
  233.                         return new T[0];
  234.                     } else {
  235.                         throw new InvalidOperationException();
  236.                     }
  237.                 }
  238.             }
  239.             #endregion
  240.  
  241.             #region IDisposable Members
  242.             public void Dispose() {
  243.                 // Do nothing.
  244.             }
  245.             #endregion
  246.  
  247.             #region IEnumerator Members
  248.             object IEnumerator.Current => Current;
  249.  
  250.             public bool MoveNext() {
  251.                 switch (_state) {
  252.                     case State.BeforeBeginning:
  253.                         _state = State.OnElement;
  254.                         return true;
  255.  
  256.                     case State.OnElement:
  257.                     case State.PastEnd:
  258.                         _state = State.PastEnd;
  259.                         return false;
  260.  
  261.                     default:
  262.                         throw new InvalidOperationException();
  263.                 }
  264.             }
  265.  
  266.             public void Reset() {
  267.                 _state = State.BeforeBeginning;
  268.             }
  269.             #endregion
  270.         }
  271.         #endregion
  272.     }
RAW Paste Data