Demonstrates the output of rewriting the MedallionCollections source for us in an inline NuGet package

MedallionCollections.cs

////////////////////////////////////////////////////////////////////////////////
// PACKAGE MedallionCollections.Inline 1.0.1
//
// The code in this file was AUTO-GENERATED by installing the MedallionCollections.Inline NuGet package.
// To update, run Update-Package MedallionCollections.Inline in the NuGet package manager console.
//
// You can modify this file without changing its source by setting
// preprocessor directives referenced here in your project properties
////////////////////////////////////////////////////////////////////////////////

using System.Collections.Generic;
using System.Collections;
using System.Diagnostics;
using System.Linq;
using System.Runtime.CompilerServices;
using System;

namespace
#if MedallionCollections_USE_LOCAL_NAMESPACE
                        Medallion.Tools.InlineNuGet.Tests
#else
                        Medallion.Collections
#endif
{
    [global::System.CodeDom.Compiler.GeneratedCodeAttribute("Medallion.Tools.InlineNuGet", "1.0.0.0"), global::System.Diagnostics.DebuggerNonUserCodeAttribute]

#if MedallionCollections_PUBLIC
                            public
#else
    internal
#endif
static partial class CollectionHelper
    {
        #region ---- Partition ----
        /// <summary>
        /// Splits the given <paramref name="source"/> sequence into a series of <see cref="List{T}"/>s
        /// of length <paramref name="partitionSize"/>. Note that the final partition may be less than
        /// <paramref name="partitionSize"/>
        /// </summary>
        public static IEnumerable<List<T>> Partition<T>(
#if !MedallionCollections_DISABLE_EXTENSIONS
                        this
#endif
IEnumerable<T> source, int partitionSize)
        {
            if (source == null) { throw new ArgumentNullException("source"); }
            if (partitionSize < 1) { throw new ArgumentOutOfRangeException(paramName: "partitionSize", message: string.Format("Value must be positive (got {0})", partitionSize)); }

            return PartitionIterator(source, partitionSize);
        }

        private static IEnumerable<List<T>> PartitionIterator<T>(
#if !MedallionCollections_DISABLE_EXTENSIONS
                        this
#endif
IEnumerable<T> source, int partitionSize)
        {
            // we like initializing our lists with capacity to avoid resizes. However, we don't want to trigger
            // OutOfMemory if the partition size is huge
            var initialCapacity = Math.Min(partitionSize, 1024);

            using (var enumerator = source.GetEnumerator())
            {
                while (enumerator.MoveNext())
                {
                    var partition = new List<T>(capacity: initialCapacity) { enumerator.Current };
                    for (var i = 1; i < partitionSize && enumerator.MoveNext(); ++i)
                    {
                        partition.Add(enumerator.Current);
                    }
                    yield return partition;
                }
            }
        }
        #endregion

        #region ---- Append ----
        /// <summary>
        /// As <see cref="Enumerable.Concat{TSource}(IEnumerable{TSource}, IEnumerable{TSource})"/>, but with better
        /// performance for repeated calls. See http://blogs.msdn.com/b/wesdyer/archive/2007/03/23/all-about-iterators.aspx
        /// </summary>
        public static IEnumerable<TElement> Append<TElement>(
#if !MedallionCollections_DISABLE_EXTENSIONS
                        this
#endif
IEnumerable<TElement> first, IEnumerable<TElement> second)
        {
            if (first == null) { throw new ArgumentNullException("first"); }
            if (second == null) { throw new ArgumentNullException("second"); }

            return new AppendEnumerable<TElement>(first, second);
        }

        /// <summary>
        /// As <see cref="Enumerable.Concat{TSource}(IEnumerable{TSource}, IEnumerable{TSource})"/>, but appends only one element
        /// Optimized for repeated calls. See http://blogs.msdn.com/b/wesdyer/archive/2007/03/23/all-about-iterators.aspx
        /// </summary>
        public static IEnumerable<TElement> Append<TElement>(
#if !MedallionCollections_DISABLE_EXTENSIONS
                        this
#endif
IEnumerable<TElement> sequence, TElement next)
        {
            if (sequence == null) { throw new ArgumentNullException("sequence"); }

            return new AppendOneEnumerable<TElement>(sequence, next);
        }

        /// <summary>
        /// As <see cref="Append{TElement}(IEnumerable{TElement}, IEnumerable{TElement})"/>, but prepends the elements
        /// instead
        /// </summary>
        public static IEnumerable<TElement> Prepend<TElement>(
#if !MedallionCollections_DISABLE_EXTENSIONS
                        this
#endif
IEnumerable<TElement> second, IEnumerable<TElement> first)
        {
            if (first == null) { throw new ArgumentNullException("first"); }
            if (second == null) { throw new ArgumentNullException("second"); }

            return new AppendEnumerable<TElement>(first, second);
        }

        /// <summary>
        /// As <see cref="Append{TElement}(IEnumerable{TElement}, TElement)"/>, but prepends an element instead
        /// </summary>
        public static IEnumerable<TElement> Prepend<TElement>(
#if !MedallionCollections_DISABLE_EXTENSIONS
                        this
#endif
IEnumerable<TElement> sequence, TElement previous)
        {
            if (sequence == null) { throw new ArgumentNullException("sequence"); }

            return new PrependOneEnumerable<TElement>(previous, sequence);
        }

        private interface IAppendEnumerable<out TElement>
        {
            IEnumerable<TElement> PreviousElements { get; }
            TElement PreviousElement { get; }
            IEnumerable<TElement> NextElements { get; }
            TElement NextElement { get; }
        }

        private abstract class AppendEnumerableBase<TElement> : IAppendEnumerable<TElement>, IEnumerable<TElement>
        {
            public abstract TElement NextElement { get; }
            public abstract IEnumerable<TElement> NextElements { get; }
            public abstract TElement PreviousElement { get; }
            public abstract IEnumerable<TElement> PreviousElements { get; }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return this.AsEnumerable().GetEnumerator();
            }

            IEnumerator<TElement> IEnumerable<TElement>.GetEnumerator()
            {
                // we special case the basic case so that it doesn't even need to create the stack
                if (!(this.PreviousElements is IAppendEnumerable<TElement>)
                    && !(this.NextElements is IAppendEnumerable<TElement>))
                {
                    if (this.PreviousElements != null)
                    {
                        foreach (var element in this.PreviousElements)
                        {
                            yield return element;
                        }
                    }
                    else
                    {
                        yield return this.PreviousElement;
                    }

                    if (this.NextElements != null)
                    {
                        foreach (var element in this.NextElements)
                        {
                            yield return element;
                        }
                    }
                    else
                    {
                        yield return this.NextElement;
                    }
                }

                // the algorithm here keeps 2 pieces of state:
                // (1) the current node in the append enumerable binary tree
                // (2) a stack of nodes we have to come back to to process the right subtree (nexts)
                // the steps are as follows, starting with current as the root of the tree:
                // (1) if the left subtree is a leaf, yield it
                // (2) otherwise, push current on the stack and set current = the left subtree
                // (3) if the right subtree is a leaf, yield it
                // (4) otherwise, set current = right subtree
                // (5) if both subtrees were leaves, set current = stack.Pop(), or exit if stack is empty

                IAppendEnumerable<TElement> currentAppendEnumerable = this;
                var enumerableStack = new Stack<IAppendEnumerable<TElement>>();
                while (true)
                {
                    if (currentAppendEnumerable != null)
                    {
                        var previous = currentAppendEnumerable.PreviousElements;
                        if (previous == null)
                        {
                            yield return currentAppendEnumerable.PreviousElement;
                        }
                        else
                        {
                            var previousAppendEnumerable = previous as IAppendEnumerable<TElement>;
                            if (previousAppendEnumerable != null)
                            {
                                enumerableStack.Push(currentAppendEnumerable);
                                currentAppendEnumerable = previousAppendEnumerable;
                                continue;
                            }

                            foreach (var previousElement in currentAppendEnumerable.PreviousElements)
                            {
                                yield return previousElement;
                            }
                        }
                    }

                    if (currentAppendEnumerable == null)
                    {
                        if (enumerableStack.Count == 0)
                        {
                            yield break;
                        }
                        currentAppendEnumerable = enumerableStack.Pop();
                    }

                    var next = currentAppendEnumerable.NextElements;
                    if (next == null)
                    {
                        yield return currentAppendEnumerable.NextElement;
                    }
                    else
                    {
                        var nextAppendEnumerable = currentAppendEnumerable.NextElements as IAppendEnumerable<TElement>;
                        if (nextAppendEnumerable != null)
                        {
                            currentAppendEnumerable = nextAppendEnumerable;
                            continue;
                        }

                        foreach (var nextElement in currentAppendEnumerable.NextElements)
                        {
                            yield return nextElement;
                        }
                    }

                    currentAppendEnumerable = null;
                }
            }
        }

        private sealed class AppendEnumerable<TElement> : AppendEnumerableBase<TElement>
        {
            private readonly IEnumerable<TElement> previous, next;

            public AppendEnumerable(IEnumerable<TElement> previous, IEnumerable<TElement> next)
            {
                this.previous = previous;
                this.next = next;
            }

            public override TElement NextElement { get { throw new InvalidOperationException(); } }
            public override IEnumerable<TElement> NextElements { get { return this.next; } }
            public override TElement PreviousElement { get { throw new InvalidOperationException(); } }
            public override IEnumerable<TElement> PreviousElements { get { return this.previous; } }
        }

        private sealed class AppendOneEnumerable<TElement> : AppendEnumerableBase<TElement>
        {
            private readonly IEnumerable<TElement> previous;
            private readonly TElement next;

            public AppendOneEnumerable(IEnumerable<TElement> previous, TElement next)
            {
                this.previous = previous;
                this.next = next;
            }

            public override TElement NextElement { get { return this.next; } }
            public override IEnumerable<TElement> NextElements { get { return null; } }
            public override TElement PreviousElement { get { throw new InvalidOperationException(); } }
            public override IEnumerable<TElement> PreviousElements { get { return this.previous; } }
        }

        private sealed class PrependOneEnumerable<TElement> : AppendEnumerableBase<TElement>
        {
            private readonly TElement previous;
            private readonly IEnumerable<TElement> next;

            public PrependOneEnumerable(TElement previous, IEnumerable<TElement> next)
            {
                this.previous = previous;
                this.next = next;
            }

            public override TElement NextElement { get { throw new InvalidOperationException(); } }
            public override IEnumerable<TElement> NextElements { get { return this.next; } }
            public override TElement PreviousElement { get { return this.previous; ; } }
            public override IEnumerable<TElement> PreviousElements { get { return null; } }
        }
        #endregion

        #region ---- MaxBy / MinBy ----
        /// <summary>
        /// As <see cref="Enumerable.Max{TSource, TResult}(IEnumerable{TSource}, Func{TSource, TResult})"/>, but returns the
        /// maximum item from the original sequence instead of the value projected by <paramref name="keySelector"/>. The
        /// optional <paramref name="comparer"/> allows key comparisons to be specified
        /// </summary>
        public static TSource MaxBy<TSource, TKey>(
#if !MedallionCollections_DISABLE_EXTENSIONS
                        this
#endif
IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer = null)
        {
            if (source == null) { throw new ArgumentNullException("source"); }
            if (keySelector == null) { throw new ArgumentNullException("keySelector"); }

            var cmp = comparer ?? Comparer<TKey>.Default;
            using (var enumerator = source.GetEnumerator())
            {
                var isNullable = default(TSource) == null;
                if (!enumerator.MoveNext())
                {
                    // just like native Min/Max, the empty sequence returns null for nullable types
                    // and throws hard for non-nullable types
                    if (isNullable) { return default(TSource); }
                    throw new InvalidOperationException("Sequence contains no elements");
                }

                var bestValue = enumerator.Current;
                var bestKey = keySelector(bestValue);
                while (enumerator.MoveNext())
                {
                    var value = enumerator.Current;
                    var key = keySelector(value);

                    if (isNullable
                        // like Min/Max, nulls are excluded from the comparison
                        ? (bestKey == null || (cmp.Compare(key, bestKey) > 0 && key != null))
                        : cmp.Compare(key, bestKey) > 0)
                    {
                        bestValue = value;
                        bestKey = key;
                    }
                }

                return bestValue;
            }
        }

        /// <summary>
        /// As <see cref="Enumerable.Min{TSource, TResult}(IEnumerable{TSource}, Func{TSource, TResult})"/>, but returns the
        /// minimum item from the original sequence instead of the value projected by <paramref name="keySelector"/>. The
        /// optional <paramref name="comparer"/> allows key comparisons to be specified
        /// </summary>
        public static TSource MinBy<TSource, TKey>(
#if !MedallionCollections_DISABLE_EXTENSIONS
                        this
#endif
IEnumerable<TSource> source, Func<TSource, TKey> keySelector, IComparer<TKey> comparer = null)
        {
            if (source == null) { throw new ArgumentNullException("source"); }
            if (keySelector == null) { throw new ArgumentNullException("keySelector"); }

            var cmp = comparer ?? Comparer<TKey>.Default;
            using (var enumerator = source.GetEnumerator())
            {
                var isNullable = default(TSource) == null;
                if (!enumerator.MoveNext())
                {
                    // just like native Min/Max, the empty sequence returns null for nullable types
                    // and throws hard for non-nullable types
                    if (isNullable) { return default(TSource); }
                    throw new InvalidOperationException("Sequence contains no elements");
                }

                var bestValue = enumerator.Current;
                var bestKey = keySelector(bestValue);
                while (enumerator.MoveNext())
                {
                    var value = enumerator.Current;
                    var key = keySelector(value);

                    if (isNullable
                        // like Min/Max, nulls are excluded from the comparison
                        ? (bestKey == null || (cmp.Compare(key, bestKey) < 0 && key != null))
                        : cmp.Compare(key, bestKey) < 0)
                    {
                        bestValue = value;
                        bestKey = key;
                    }
                }

                return bestValue;
            }
        }
        #endregion

        #region ---- CollectionEquals ----
        /// <summary>
        /// Determines whether <paramref name="this"/> and <paramref name="that"/> are equal in the sense of having the exact same
        /// elements. Unlike <see cref="Enumerable.SequenceEqual{TSource}(IEnumerable{TSource}, IEnumerable{TSource})"/>,
        /// this method disregards order. Unlike <see cref="ISet{T}.SetEquals(IEnumerable{T})"/>, this method does not disregard duplicates.
        /// An optional <paramref name="comparer"/> allows the equality semantics for the elements to be specified
        /// </summary>
        public static bool CollectionEquals<TElement>(
#if !MedallionCollections_DISABLE_EXTENSIONS
                        this
#endif
IEnumerable<TElement> @this, IEnumerable<TElement> that, IEqualityComparer<TElement> comparer = null)
        {
            if (@this == null) { throw new ArgumentNullException("this"); }
            if (that == null) { throw new ArgumentNullException("that"); }

            // FastCount optimization: If both of the collections are materialized and have counts, 
            // we can exit very quickly if those counts differ
            int thisCount, thatCount;
            var hasThisCount = TryFastCount(@this, out thisCount);
            bool hasThatCount;
            if (hasThisCount)
            {
                hasThatCount = TryFastCount(that, out thatCount);
                if (hasThatCount)
                {
                    if (thisCount != thatCount)
                    {
                        return false;
                    }
                    if (thisCount == 0)
                    {
                        return true;
                    }
                }
            }
            else
            {
                hasThatCount = false;
            }

            var cmp = comparer ?? EqualityComparer<TElement>.Default;

            var itemsEnumerated = 0;
            // SequenceEqual optimization: we reduce/avoid hashing
            // the collections have common prefixes, at the cost of only one
            // extra Equals() call in the case where the prefixes are not common
            using (var thisEnumerator = @this.GetEnumerator())
            using (var thatEnumerator = that.GetEnumerator())
            {
                while (true)
                {
                    var thisFinished = !thisEnumerator.MoveNext();
                    var thatFinished = !thatEnumerator.MoveNext();

                    if (thisFinished)
                    {
                        // either this shorter than that, or the two were sequence-equal
                        return thatFinished;
                    }
                    if (thatFinished)
                    {
                        // that shorter than this
                        return false;
                    }

                    // keep track of this so that we can factor it into count-based 
                    // logic below
                    ++itemsEnumerated;

                    if (!cmp.Equals(thisEnumerator.Current, thatEnumerator.Current))
                    {
                        break; // prefixes were not equal
                    }
                }

                // now, build a dictionary of item => count out of one collection and then
                // probe it with the other collection to look for mismatches

                // Build/Probe Choice optimization: if we know the count of one collection, we should
                // use the other collection to build the dictionary. That way we can bail immediately if
                // we see too few or too many items
                CountingSet<TElement> elementCounts;
                IEnumerator<TElement> probeSide;
                if (hasThisCount)
                {
                    // we know this's count => use that as the build side
                    probeSide = thisEnumerator;
                    var remaining = thisCount - itemsEnumerated;
                    if (hasThatCount)
                    {
                        // if we have both counts, that means they must be equal or we would have already
                        // exited. However, in this case, we know exactly the capacity needed for the dictionary
                        // so we can avoid resizing
                        elementCounts = new CountingSet<TElement>(capacity: remaining, comparer: cmp);
                        do
                        {
                            elementCounts.Increment(thatEnumerator.Current);
                        }
                        while (thatEnumerator.MoveNext());
                    }
                    else
                    {
                        elementCounts = TryBuildElementCountsWithKnownCount(thatEnumerator, remaining, cmp);
                    }
                }
                else if (TryFastCount(that, out thatCount))
                {
                    // we know that's count => use this as the build side
                    probeSide = thatEnumerator;
                    var remaining = thatCount - itemsEnumerated;
                    elementCounts = TryBuildElementCountsWithKnownCount(thisEnumerator, remaining, cmp);
                }
                else
                {
                    // when we don't know either count, just use that as the build side arbitrarily
                    probeSide = thisEnumerator;
                    elementCounts = new CountingSet<TElement>(cmp);
                    do
                    {
                        elementCounts.Increment(thatEnumerator.Current);
                    }
                    while (thatEnumerator.MoveNext());
                }

                // check whether we failed to construct a dictionary. This happens when we know
                // one of the counts and we detect, during construction, that the counts are unequal
                if (elementCounts == null)
                {
                    return false;
                }

                // probe the dictionary with the probe side enumerator
                do
                {
                    if (!elementCounts.TryDecrement(probeSide.Current))
                    {
                        // element in probe not in build => not equal
                        return false;
                    }
                }
                while (probeSide.MoveNext());

                // we are equal only if the loop above completely cleared out the dictionary
                return elementCounts.IsEmpty;
            }
        }

        /// <summary>
        /// Constructs a count dictionary, staying mindful of the known number of elements
        /// so that we bail early (returning null) if we detect a count mismatch
        /// </summary>
        private static CountingSet<TKey> TryBuildElementCountsWithKnownCount<TKey>(
            IEnumerator<TKey> elements,
            int remaining,
            IEqualityComparer<TKey> comparer)
        {
            if (remaining == 0)
            {
                // don't build the dictionary at all if nothing should be in it
                return null;
            }

            const int MaxInitialElementCountsCapacity = 1024;
            var elementCounts = new CountingSet<TKey>(capacity: Math.Min(remaining, MaxInitialElementCountsCapacity), comparer: comparer);
            elementCounts.Increment(elements.Current);
            while (elements.MoveNext())
            {
                if (--remaining < 0)
                {
                    // too many elements
                    return null;
                }
                elementCounts.Increment(elements.Current);
            }

            if (remaining > 0)
            {
                // too few elements
                return null;
            }

            return elementCounts;
        }

        /// <summary>
        /// Key Lookup Reduction optimization: this custom datastructure halves the number of <see cref="IEqualityComparer{T}.GetHashCode(T)"/>
        /// and <see cref="IEqualityComparer{T}.Equals(T, T)"/> operations by building in the increment/decrement operations of a counting dictionary.
        /// This also solves <see cref="Dictionary{TKey, TValue}"/>'s issues with null keys
        /// </summary>
        private sealed class CountingSet<T>
        {
            // picked based on observing unit test performance
            private const double MaxLoad = .62;

            private readonly IEqualityComparer<T> comparer;
            private Bucket[] buckets;
            private int populatedBucketCount;
            /// <summary>
            /// When we reach this count, we need to resize
            /// </summary>
            private int nextResizeCount;

            public CountingSet(IEqualityComparer<T> comparer, int capacity = 0)
            {
                this.comparer = comparer;
                // we pick the initial length by assuming our current table is one short of the desired
                // capacity and then using our standard logic of picking the next valid table size
                this.buckets = new Bucket[GetNextTableSize((int)(capacity / MaxLoad) - 1)];
                this.nextResizeCount = this.CalculateNextResizeCount();
            }

            public bool IsEmpty { get { return this.populatedBucketCount == 0; } }

            public void Increment(T item)
            {
                int bucketIndex;
                uint hashCode;
                if (this.TryFindBucket(item, out bucketIndex, out hashCode))
                {
                    // if a bucket already existed, just update it's count
                    ++this.buckets[bucketIndex].Count;
                }
                else
                {
                    // otherwise, claim a new bucket
                    this.buckets[bucketIndex].HashCode = hashCode;
                    this.buckets[bucketIndex].Value = item;
                    this.buckets[bucketIndex].Count = 1;
                    ++this.populatedBucketCount;

                    // resize the table if we've grown too full
                    if (this.populatedBucketCount == this.nextResizeCount)
                    {
                        var newBuckets = new Bucket[GetNextTableSize(this.buckets.Length)];

                        // rehash
                        for (var i = 0; i < this.buckets.Length; ++i)
                        {
                            var oldBucket = this.buckets[i];
                            if (oldBucket.HashCode != 0)
                            {
                                var newBucketIndex = oldBucket.HashCode % newBuckets.Length;
                                while (true)
                                {
                                    if (newBuckets[newBucketIndex].HashCode == 0)
                                    {
                                        newBuckets[newBucketIndex] = oldBucket;
                                        break;
                                    }

                                    newBucketIndex = (newBucketIndex + 1) % newBuckets.Length;
                                }
                            }
                        }

                        this.buckets = newBuckets;
                        this.nextResizeCount = this.CalculateNextResizeCount();
                    }
                }
            }

            public bool TryDecrement(T item)
            {
                int bucketIndex;
                uint ignored;
                if (this.TryFindBucket(item, out bucketIndex, out ignored)
                    && this.buckets[bucketIndex].Count > 0)
                {
                    if (--this.buckets[bucketIndex].Count == 0)
                    {
                        // Note: we can't do this because it messes up our try-find logic
                        //// mark as unpopulated. Not strictly necessary because CollectionEquals always does all increments
                        //// before all decrements currently. However, this is very cheap to do and allowing the collection to
                        //// "just work" in any situation is a nice benefit
                        //// this.buckets[bucketIndex].HashCode = 0;

                        --this.populatedBucketCount;
                    }
                    return true;
                }

                return false;
            }

            private bool TryFindBucket(T item, out int index, out uint hashCode)
            {
                // we convert the raw hash code to a uint to get correctly-signed mod operations
                // and get rid of the zero value so that we can use 0 to mean "unoccupied"
                var rawHashCode = this.comparer.GetHashCode(item);
                hashCode = rawHashCode == 0 ? uint.MaxValue : unchecked((uint)rawHashCode);

                var bestBucketIndex = (int)(hashCode % this.buckets.Length);

                var bucketIndex = bestBucketIndex;
                while (true) // guaranteed to terminate because of how we set load factor
                {
                    var bucket = this.buckets[bucketIndex];
                    if (bucket.HashCode == 0)
                    {
                        // found unoccupied bucket
                        index = bucketIndex;
                        return false;
                    }
                    if (bucket.HashCode == hashCode && this.comparer.Equals(bucket.Value, item))
                    {
                        // found matching bucket
                        index = bucketIndex;
                        return true;
                    }

                    // otherwise march on to the next adjacent bucket
                    bucketIndex = (bucketIndex + 1) % this.buckets.Length;
                }
            }

            private int CalculateNextResizeCount()
            {
                return (int)(MaxLoad * this.buckets.Length) + 1;
            }

            private static readonly int[] HashTableSizes = new[]
            {
                // hash table primes from http://planetmath.org/goodhashtableprimes
                23, 53, 97, 193, 389, 769, 1543, 3079, 6151, 12289,
                24593, 49157, 98317, 196613, 393241, 786433, 1572869,
                3145739, 6291469, 12582917, 25165843, 50331653, 100663319,
                201326611, 402653189, 805306457, 1610612741,
                // the first two values are (1) a prime roughly half way between the previous value and int.MaxValue
                // and (2) the prime closest too, but not above, int.MaxValue. The maximum size is, of course, int.MaxValue
                1879048201, 2147483629, int.MaxValue
            };

            private static int GetNextTableSize(int currentSize)
            {
                for (var i = 0; i < HashTableSizes.Length; ++i)
                {
                    var nextSize = HashTableSizes[i];
                    if (nextSize > currentSize) { return nextSize; }
                }

                throw new InvalidOperationException("Hash table cannot expand further");
            }

            [DebuggerDisplay("{Value}, {Count}, {HashCode}")]
            private struct Bucket
            {
                // note: 0 (default) means the bucket is unoccupied
                internal uint HashCode;
                internal T Value;
                internal int Count;
            }
        }
        #endregion

        #region ---- GetOrAdd ----
        /// <summary>
        /// If <paramref name="key"/> exists in <paramref name="dictionary"/>, returns the associated value. Otherwise,
        /// generates a new value by applying <paramref name="valueFactory"/> to the given <paramref name="key"/>. The 
        /// new value is stored in <paramref name="dictionary"/> and returned
        /// </summary>
        public static TValue GetOrAdd<TKey, TValue>(
#if !MedallionCollections_DISABLE_EXTENSIONS
                        this
#endif
IDictionary<TKey, TValue> dictionary, TKey key, Func<TKey, TValue> valueFactory)
        {
            if (dictionary == null) { throw new ArgumentNullException("dictionary"); }
            if (valueFactory == null) { throw new ArgumentNullException("valueFactory"); }

            TValue existing;
            if (dictionary.TryGetValue(key, out existing))
            {
                return existing;
            }

            var value = valueFactory(key);
            dictionary.Add(key, value);
            return value;
        }
        #endregion

        private static bool TryFastCount<T>(IEnumerable<T> @this, out int count)
        {
            var collection = @this as ICollection<T>;
            if (collection != null)
            {
                count = collection.Count;
                return true;
            }

            var readOnlyCollection = @this as IReadOnlyCollection<T>;
            if (readOnlyCollection != null)
            {
                count = readOnlyCollection.Count;
                return true;
            }

            count = -1;
            return false;
        }
    }
}

namespace
#if MedallionCollections_USE_LOCAL_NAMESPACE
                        Medallion.Tools.InlineNuGet.Tests
#else
                        Medallion.Collections
#endif
{
    [global::System.CodeDom.Compiler.GeneratedCodeAttribute("Medallion.Tools.InlineNuGet", "1.0.0.0"), global::System.Diagnostics.DebuggerNonUserCodeAttribute]

#if MedallionCollections_PUBLIC
                            public
#else
    internal
#endif
static partial class Comparers
    {
        #region ---- Key Comparer ----
        /// <summary>
        /// Creates a <see cref="Comparer{T}"/> which compares values of type <typeparamref name="T"/> by
        /// projecting them to type <typeparamref name="TKey"/> using the given <paramref name="keySelector"/>.
        /// The optional <paramref name="keyComparer"/> determines how keys are compared
        /// </summary>
        public static Comparer<T> Create<T, TKey>(Func<T, TKey> keySelector, IComparer<TKey> keyComparer = null)
        {
            if (keySelector == null) { throw new ArgumentNullException("keySelector"); }

            return new KeyComparer<T, TKey>(keySelector, keyComparer ?? Comparer<TKey>.Default);
        }

        private sealed class KeyComparer<T, TKey> : Comparer<T>
        {
            private readonly Func<T, TKey> keySelector;
            private readonly IComparer<TKey> keyComparer;

            public KeyComparer(Func<T, TKey> keySelector, IComparer<TKey> keyComparer)
            {
                this.keySelector = keySelector;
                this.keyComparer = keyComparer;
            }

            public override int Compare(T x, T y)
            {
                // from Comparer<T>.Compare(object, object)
                if (x == null)
                {
                    return y == null ? 0 : -1;
                }
                if (y == null)
                {
                    return 1;
                }

                return this.keyComparer.Compare(this.keySelector(x), this.keySelector(y));
            }

            public override bool Equals(object obj)
            {
                if (ReferenceEquals(obj, this)) { return true; }

                var that = obj as KeyComparer<T, TKey>;
                return that != null
                    && that.keySelector.Equals(this.keySelector)
                    && that.keyComparer.Equals(this.keyComparer);
            }

            public override int GetHashCode()
            {
                return unchecked((3 * this.keySelector.GetHashCode()) + this.keyComparer.GetHashCode());
            }
        }
        #endregion

        #region ---- Reverse ----
        /// <summary>
        /// Gets an <see cref="IComparer{T}"/> which represents the reverse of
        /// the order implied by <see cref="Comparer{T}.Default"/>
        /// </summary>
        public static IComparer<T> Reverse<T>()
        {
            return ReverseComparer<T>.Default;
        }

        /// <summary>
        /// Gets an <see cref="IComparer{T}"/> which represents the reverse of
        /// the order implied by the given <paramref name="comparer"/>
        /// </summary>
        public static IComparer<T> Reverse<T>(
#if !MedallionCollections_DISABLE_EXTENSIONS
                        this
#endif
IComparer<T> comparer)
        {
            if (comparer == null) { throw new ArgumentNullException("comparer"); }

            return comparer == Comparer<T>.Default
                ? Reverse<T>()
                : new ReverseComparer<T>(comparer);
        }

        // we don't want Comparer<T> here because that doesn't let us override
        // the comparison of nulls in the Compare(object, object) method
        private sealed class ReverseComparer<T> : IComparer<T>, IComparer
        {
            public static readonly ReverseComparer<T> Default = new ReverseComparer<T>(Comparer<T>.Default);

            private readonly IComparer<T> comparer;

            public ReverseComparer(IComparer<T> comparer)
            {
                this.comparer = comparer;
            }

            public int Compare(T x, T y)
            {
                return this.comparer.Compare(y, x);
            }

            int IComparer.Compare(object x, object y)
            {
                return this.Compare((T)x, (T)y);
            }

            public override bool Equals(object obj)
            {
                if (ReferenceEquals(obj, this)) { return true; }

                var that = obj as ReverseComparer<T>;
                return that != null && that.comparer.Equals(this.comparer);
            }

            public override int GetHashCode()
            {
                return ReferenceEquals(this, Default)
                    ? base.GetHashCode()
                    : unchecked((3 * Default.GetHashCode()) + this.comparer.GetHashCode());
            }
        }
        #endregion

        #region ---- ThenBy ----
        /// <summary>
        /// Gets a <see cref="Comparer{T}"/> which compares using <paramref name="first"/>
        /// and breaks ties with <paramref name="second"/>
        /// </summary>
        public static Comparer<T> ThenBy<T>(
#if !MedallionCollections_DISABLE_EXTENSIONS
                        this
#endif
IComparer<T> first, IComparer<T> second)
        {
            if (first == null) { throw new ArgumentNullException("first"); }
            if (second == null) { throw new ArgumentNullException("second"); }

            return new ThenByComparer<T>(first, second);
        }

        private sealed class ThenByComparer<T> : Comparer<T>
        {
            private readonly IComparer<T> first, second;

            public ThenByComparer(IComparer<T> first, IComparer<T> second)
            {
                this.first = first;
                this.second = second;
            }

            public override int Compare(T x, T y)
            {
                var firstComparison = this.first.Compare(x, y);
                return firstComparison != 0 ? firstComparison : this.second.Compare(x, y);
            }

            public override bool Equals(object obj)
            {
                if (ReferenceEquals(obj, this)) { return true; }

                var that = obj as ThenByComparer<T>;
                return that != null
                    && that.first.Equals(this.first)
                    && that.second.Equals(this.second);
            }

            public override int GetHashCode()
            {
                return unchecked((3 * this.first.GetHashCode()) + this.second.GetHashCode());
            }
        }
        #endregion

        #region ---- Sequence Comparer ----
        /// <summary>
        /// Gets a <see cref="Comparer{T}"/> which sorts sequences lexographically. The optional
        /// <paramref name="elementComparer"/> can be used to override comparisons of individual elements
        /// </summary>
        public static Comparer<IEnumerable<T>> GetSequenceComparer<T>(IComparer<T> elementComparer = null)
        {
            return elementComparer == null || elementComparer == Comparer<T>.Default
                ? SequenceComparer<T>.DefaultInstance
                : new SequenceComparer<T>(elementComparer);
        }

        private sealed class SequenceComparer<T> : Comparer<IEnumerable<T>>
        {
            private static Comparer<IEnumerable<T>> defaultInstance;
            public static Comparer<IEnumerable<T>> DefaultInstance
            {
                get
                {
                    return defaultInstance ?? (defaultInstance = new SequenceComparer<T>(Comparer<T>.Default));
                }
            }

            private readonly IComparer<T> elementComparer;

            public SequenceComparer(IComparer<T> elementComparer)
            {
                this.elementComparer = elementComparer;
            }

            public override int Compare(IEnumerable<T> x, IEnumerable<T> y)
            {
                // from Comparer<T>.Compare(object, object)
                if (x == null)
                {
                    return y == null ? 0 : -1;
                }
                if (y == null)
                {
                    return 1;
                }

                if (ReferenceEquals(x, y))
                {
                    return 0;
                }

                using (var xEnumerator = x.GetEnumerator())
                using (var yEnumerator = y.GetEnumerator())
                {
                    while (true)
                    {
                        var xHasMore = xEnumerator.MoveNext();
                        var yHasMore = yEnumerator.MoveNext();

                        if (!xHasMore)
                        {
                            return yHasMore ? -1 : 0;
                        }
                        if (!yHasMore)
                        {
                            return 1;
                        }

                        var cmp = this.elementComparer.Compare(xEnumerator.Current, yEnumerator.Current);
                        if (cmp != 0)
                        {
                            return cmp;
                        }
                    }
                }
            }

            public override bool Equals(object obj)
            {
                if (ReferenceEquals(obj, this)) { return true; }

                var that = obj as SequenceComparer<T>;
                return that != null && that.elementComparer.Equals(this.elementComparer);
            }

            public override int GetHashCode()
            {
                return ReferenceEquals(this, DefaultInstance)
                    ? base.GetHashCode()
                    : unchecked((3 * DefaultInstance.GetHashCode()) + this.elementComparer.GetHashCode());
            }
        }
        #endregion
    }
}

namespace
#if MedallionCollections_USE_LOCAL_NAMESPACE
                        Medallion.Tools.InlineNuGet.Tests
#else
                        Medallion.Collections
#endif
{
    [global::System.CodeDom.Compiler.GeneratedCodeAttribute("Medallion.Tools.InlineNuGet", "1.0.0.0"), global::System.Diagnostics.DebuggerNonUserCodeAttribute]

#if MedallionCollections_PUBLIC
                            public
#else
    internal
#endif
static partial class Empty
    {
        /// <summary>A cached instance of <see cref="IEnumerable"/></summary>
        public static IEnumerable ObjectEnumerable
        {
            get
            {
                return EmptyCollection<object>.Instance;
            }
        }

        /// <summary>A cached readonly instance of <see cref="ICollection"/></summary>
        public static ICollection ObjectCollection
        {
            get
            {
                return EmptyCollection<object>.Instance;
            }
        }

        /// <summary>A cached readonly instance of <see cref="IList"/></summary>
        public static IList ObjectList
        {
            get
            {
                return EmptyCollection<object>.Instance;
            }
        }

        /// <summary>A cached readonly instance of <see cref="IDictionary"/></summary>
        public static IDictionary ObjectDictionary
        {
            get
            {
                return EmptyDictionary<object, object>.Instance;
            }
        }

        /// <summary>A cached instance of <see cref = "IEnumerable{T}"/></summary>
        public static IEnumerable<T> Enumerable<T>()
        {
            return EmptyCollection<T>.Instance;
        }/// <summary>A cached readonly instance of <see cref = "ICollection{T}"/></summary>
        public static ICollection<T> Collection<T>()
        {
            return EmptyCollection<T>.Instance;
        }/// <summary>A cached instance of <see cref = "IReadOnlyCollection{T}"/></summary>
        public static IReadOnlyCollection<T> ReadOnlyCollection<T>()
        {
            return EmptyCollection<T>.Instance;
        }/// <summary>A cached instance of an array of <typeparamref name = "T"/></summary>
        public static T[] Array<T>()
        {
            return EmptyArray<T>.Instance;
        }/// <summary>A cached readonly instance of <see cref = "IList{T}"/></summary>
        public static IList<T> List<T>()
        {
            return EmptyCollection<T>.Instance;
        }/// <summary>A cached instance of <see cref = "IReadOnlyList{T}"/></summary>
        public static IReadOnlyList<T> ReadOnlyList<T>()
        {
            return EmptyCollection<T>.Instance;
        }/// <summary>A cached readonly instance of <see cref = "ISet{T}"/></summary>
        public static ISet<T> Set<T>()
        {
            return EmptyCollection<T>.Instance;
        }/// <summary>A cached readonly instance of <see cref = "IDictionary{TKey, TValue}"/></summary>
        public static IDictionary<TKey, TValue> Dictionary<TKey, TValue>()
        {
            return EmptyDictionary<TKey, TValue>.Instance;
        }/// <summary>A cached instance of <see cref = "IReadOnlyDictionary{TKey, TValue}"/></summary>
        public static IReadOnlyDictionary<TKey, TValue> ReadOnlyDictionary<TKey, TValue>()
        {
            return EmptyDictionary<TKey, TValue>.Instance;
        }
        #region ---- Empty Array ----
        private static class EmptyArray<TElement>
        {
            // this takes advantage of the fact that Enumerable.Empty() is currently implemented
            // using a cached empty array without depending on that fact
            public static readonly TElement[] Instance = (System.Linq.Enumerable.Empty<TElement>() as TElement[]) ?? new TElement[0];
        }
        #endregion

        #region ---- Empty Collection ----
        private class EmptyCollection<TElement> : IList<TElement>, IReadOnlyList<TElement>, ISet<TElement>, IEnumerator<TElement>, IList
        {
            public static readonly EmptyCollection<TElement> Instance = new EmptyCollection<TElement>();

            protected EmptyCollection() { }

            TElement IReadOnlyList<TElement>.this[int index]
            {
                get { throw ThrowCannotIndex(); }
            }

            object IList.this[int index]
            {
                get { throw ThrowCannotIndex(); }
                set { throw ThrowReadOnly(); }
            }

            TElement IList<TElement>.this[int index]
            {
                get { throw ThrowCannotIndex(); }
                set { throw ThrowReadOnly(); }
            }

            int IReadOnlyCollection<TElement>.Count
            {
                get
                {
                    return 0;
                }
            }

            int ICollection.Count
            {
                get
                {
                    return 0;
                }
            }

            int ICollection<TElement>.Count
            {
                get
                {
                    return 0;
                }
            }

            object IEnumerator.Current
            {
                // based on ((IEnumerator)new List<int>().GetEnumerator()).Current
                get { throw new InvalidOperationException("Enumeration has either not started or has already finished"); }
            }

            // based on new List<int>().GetEnumerator().Current
            TElement IEnumerator<TElement>.Current
            {
                get
                {
                    return default(TElement);
                }
            }

            bool IList.IsFixedSize
            {
                get
                {
                    return true;
                }
            }

            bool IList.IsReadOnly
            {
                get
                {
                    return true;
                }
            }

            bool ICollection<TElement>.IsReadOnly
            {
                get
                {
                    return true;
                }
            }

            bool ICollection.IsSynchronized
            {
                get
                {
                    return false;
                }
            }

            object ICollection.SyncRoot
            {
                get
                {
                    return this;
                }
            }

            int IList.Add(object value)
            {
                throw ThrowReadOnly();
            }

            bool ISet<TElement>.Add(TElement item)
            {
                throw ThrowReadOnly();
            }

            void ICollection<TElement>.Add(TElement item)
            {
                throw ThrowReadOnly();
            }

            void IList.Clear()
            {
                throw ThrowReadOnly();
            }

            void ICollection<TElement>.Clear()
            {
                throw ThrowReadOnly();
            }
            bool IList.Contains(object value)
            {
                return false;
            }
            bool ICollection<TElement>.Contains(TElement item)
            {
                return false;
            }
            void ICollection.CopyTo(Array array, int index)
            {
                if (array == null) { throw new ArgumentNullException("array"); }
                if (index < 0 || index > array.Length) { throw new ArgumentOutOfRangeException("index"); }
            }

            void ICollection<TElement>.CopyTo(TElement[] array, int arrayIndex)
            {
                if (array == null) { throw new ArgumentNullException("array"); }
                if (arrayIndex < 0 || arrayIndex > array.Length) { throw new ArgumentOutOfRangeException("arrayIndex"); }
            }

            void IDisposable.Dispose()
            {
            }

            void ISet<TElement>.ExceptWith(IEnumerable<TElement> other)
            {
                throw ThrowReadOnly();
            }

            IEnumerator IEnumerable.GetEnumerator()
            {
                return this;
            }

            IEnumerator<TElement> IEnumerable<TElement>.GetEnumerator()
            {
                return this;
            }
            int IList.IndexOf(object value)
            {
                return -1;
            }
            int IList<TElement>.IndexOf(TElement item)
            {
                return -1;
            }
            void IList.Insert(int index, object value)
            {
                throw ThrowReadOnly();
            }

            void IList<TElement>.Insert(int index, TElement item)
            {
                throw ThrowReadOnly();
            }

            void ISet<TElement>.IntersectWith(IEnumerable<TElement> other)
            {
                throw ThrowReadOnly();
            }

            bool ISet<TElement>.IsProperSubsetOf(IEnumerable<TElement> other)
            {
                if (other == null) { throw new ArgumentNullException("other"); }
                return other.Any();
            }

            bool ISet<TElement>.IsProperSupersetOf(IEnumerable<TElement> other)
            {
                if (other == null) { throw new ArgumentNullException("other"); }
                return false;
            }

            bool ISet<TElement>.IsSubsetOf(IEnumerable<TElement> other)
            {
                if (other == null) { throw new ArgumentNullException("other"); }
                return true;
            }

            bool ISet<TElement>.IsSupersetOf(IEnumerable<TElement> other)
            {
                if (other == null) { throw new ArgumentNullException("other"); }
                return !other.Any();
            }
            bool IEnumerator.MoveNext()
            {
                return false;
            }
            bool ISet<TElement>.Overlaps(IEnumerable<TElement> other)
            {
                if (other == null) { throw new ArgumentNullException("other"); }
                return false;
            }

            void IList.Remove(object value)
            {
                throw ThrowReadOnly();
            }

            bool ICollection<TElement>.Remove(TElement item)
            {
                throw ThrowReadOnly();
            }

            void IList.RemoveAt(int index)
            {
                throw ThrowReadOnly();
            }

            void IList<TElement>.RemoveAt(int index)
            {
                throw ThrowReadOnly();
            }

            void IEnumerator.Reset()
            {
            }

            bool ISet<TElement>.SetEquals(IEnumerable<TElement> other)
            {
                if (other == null) { throw new ArgumentNullException("other"); }
                return !other.Any();
            }

            void ISet<TElement>.SymmetricExceptWith(IEnumerable<TElement> other)
            {
                throw ThrowReadOnly();
            }

            void ISet<TElement>.UnionWith(IEnumerable<TElement> other)
            {
                throw ThrowReadOnly();
            }

            private static Exception ThrowCannotIndex()
            {
                throw new ArgumentOutOfRangeException("Cannot index into an empty collection");
            }
        }
        #endregion

        #region ---- Empty Dictionary ----
        private sealed class EmptyDictionary<TKey, TValue> : EmptyCollection<KeyValuePair<TKey, TValue>>, IReadOnlyDictionary<TKey, TValue>, IDictionary<TKey, TValue>, IDictionary, IDictionaryEnumerator
        {
            public static new readonly EmptyDictionary<TKey, TValue> Instance = new EmptyDictionary<TKey, TValue>();

            private EmptyDictionary() { }

            object IDictionary.this[object key]
            {
                get { return null; }
                set { throw ThrowReadOnly(); }
            }

            TValue IDictionary<TKey, TValue>.this[TKey key]
            {
                get { throw new KeyNotFoundException(); }
                set { throw ThrowReadOnly(); }
            }

            TValue IReadOnlyDictionary<TKey, TValue>.this[TKey key]
            {
                get { throw new KeyNotFoundException(); }
            }

            bool IDictionary.IsFixedSize
            {
                get
                {
                    return true;
                }
            }

            bool IDictionary.IsReadOnly
            {
                get
                {
                    return true;
                }
            }

            ICollection IDictionary.Keys
            {
                get
                {
                    return ObjectCollection;
                }
            }

            ICollection<TKey> IDictionary<TKey, TValue>.Keys
            {
                get
                {
                    return Collection<TKey>();
                }
            }

            IEnumerable<TKey> IReadOnlyDictionary<TKey, TValue>.Keys
            {
                get
                {
                    return Collection<TKey>();
                }
            }

            ICollection<TValue> IDictionary<TKey, TValue>.Values
            {
                get
                {
                    return Collection<TValue>();
                }
            }

            ICollection IDictionary.Values
            {
                get
                {
                    return ObjectCollection;
                }
            }

            IEnumerable<TValue> IReadOnlyDictionary<TKey, TValue>.Values
            {
                get
                {
                    return ReadOnlyCollection<TValue>();
                }
            }

            object IDictionaryEnumerator.Key
            {
                get { throw new InvalidOperationException("Enumeration has either not started or has already finished"); }
            }

            object IDictionaryEnumerator.Value
            {
                get { throw new InvalidOperationException("Enumeration has either not started or has already finished"); }
            }

            DictionaryEntry IDictionaryEnumerator.Entry
            {
                get { throw new InvalidOperationException("Enumeration has either not started or has already finished"); }
            }

            void IDictionary.Add(object key, object value)
            {
                throw ThrowReadOnly();
            }

            void IDictionary<TKey, TValue>.Add(TKey key, TValue value)
            {
                throw ThrowReadOnly();
            }

            void IDictionary.Clear()
            {
                throw ThrowReadOnly();
            }
            bool IDictionary.Contains(object key)
            {
                return false;
            }
            bool IDictionary<TKey, TValue>.ContainsKey(TKey key)
            {
                return false;
            }
            bool IReadOnlyDictionary<TKey, TValue>.ContainsKey(TKey key)
            {
                return false;
            }
            IDictionaryEnumerator IDictionary.GetEnumerator()
            {
                return this;
            }
            void IDictionary.Remove(object key)
            {
                throw ThrowReadOnly();
            }

            bool IDictionary<TKey, TValue>.Remove(TKey key)
            {
                throw ThrowReadOnly();
            }

            bool IDictionary<TKey, TValue>.TryGetValue(TKey key, out TValue value)
            {
                value = default(TValue);
                return false;
            }

            bool IReadOnlyDictionary<TKey, TValue>.TryGetValue(TKey key, out TValue value)
            {
                value = default(TValue);
                return false;
            }
        }
        #endregion

        private static Exception ThrowReadOnly([CallerMemberName] string memberName = null)
        {
            throw new NotSupportedException(memberName + ": the collection is read-only");
        }
    }
}

namespace
#if MedallionCollections_USE_LOCAL_NAMESPACE
                        Medallion.Tools.InlineNuGet.Tests
#else
                        Medallion.Collections
#endif
{
    [global::System.CodeDom.Compiler.GeneratedCodeAttribute("Medallion.Tools.InlineNuGet", "1.0.0.0"), global::System.Diagnostics.DebuggerNonUserCodeAttribute]

#if MedallionCollections_PUBLIC
                            public
#else
    internal
#endif
static partial class EqualityComparers
    {
        #region ---- Func Comparer ----
        /// <summary>
        /// Creates an <see cref="EqualityComparer{T}"/> using the given <paramref name="equals"/> function
        /// for equality and the optional <paramref name="hash"/> function for hashing (if <paramref name="hash"/> is not
        /// provided, all values hash to 0). Note that null values are handled directly by the comparer and will not
        /// be passed to these functions
        /// </summary>
        public static EqualityComparer<T> Create<T>(Func<T, T, bool> equals, Func<T, int> hash = null)
        {
            if (equals == null) { throw new ArgumentNullException("equals"); }

            return new FuncEqualityComparer<T>(equals, hash);
        }

        private sealed class FuncEqualityComparer<T> : EqualityComparer<T>
        {
            private static readonly Func<T, int> DefaultHash = _ => -1;

            private readonly Func<T, T, bool> equals;
            private readonly Func<T, int> hash;

            public FuncEqualityComparer(Func<T, T, bool> equals, Func<T, int> hash)
            {
                this.equals = equals;
                this.hash = hash ?? DefaultHash;
            }

            public override bool Equals(T x, T y)
            {
                // TODO do these cause boxing?
                // null checks consistent with Equals(object, object)
                return x == null
                    ? y == null
                    : y != null && this.equals(x, y);
            }

            public override int GetHashCode(T obj)
            {
                // consistent with GetHashCode(object)
                return obj == null ? 0 : this.hash(obj);
            }

            public override bool Equals(object obj)
            {
                if (ReferenceEquals(obj, this)) { return true; }

                var that = obj as FuncEqualityComparer<T>;
                return that != null
                    && that.equals.Equals(this.equals)
                    && that.hash.Equals(this.hash);
            }

            public override int GetHashCode()
            {
                return unchecked((3 * this.equals.GetHashCode()) + this.hash.GetHashCode());
            }
        }
        #endregion

        #region ---- Key Comparer ----
        /// <summary>
        /// Creates an <see cref="EqualityComparer{T}"/> which compares elements of type <typeparamref name="T"/> by projecting
        /// them to an instance of type <typeparamref name="TKey"/> using the provided <paramref name="keySelector"/> and comparing/hashing
        /// these keys. The optional <paramref name="keyComparer"/> argument can be used to specify how the keys are compared. Note that null
        /// values are handled directly by the comparer and will not be passed to <paramref name="keySelector"/>
        /// </summary>
        public static EqualityComparer<T> Create<T, TKey>(Func<T, TKey> keySelector, IEqualityComparer<TKey> keyComparer = null)
        {
            if (keySelector == null) { throw new ArgumentNullException("keySelector"); }

            return new KeyComparer<T, TKey>(keySelector, keyComparer);
        }

        private sealed class KeyComparer<T, TKey> : EqualityComparer<T>
        {
            private readonly Func<T, TKey> keySelector;
            private readonly IEqualityComparer<TKey> keyComparer;

            public KeyComparer(Func<T, TKey> keySelector, IEqualityComparer<TKey> keyComparer)
            {
                this.keySelector = keySelector;
                this.keyComparer = keyComparer ?? EqualityComparer<TKey>.Default;
            }

            public override bool Equals(T x, T y)
            {
                if (x == null) { return y == null; }
                if (y == null) { return false; }

                return this.keyComparer.Equals(this.keySelector(x), this.keySelector(y));
            }

            public override int GetHashCode(T obj)
            {
                return obj == null ? 0 : this.keyComparer.GetHashCode(this.keySelector(obj));
            }

            public override bool Equals(object obj)
            {
                if (ReferenceEquals(obj, this)) { return true; }

                var that = obj as KeyComparer<T, TKey>;
                return that != null
                    && that.keySelector.Equals(this.keySelector)
                    && that.keyComparer.Equals(this.keyComparer);
            }

            public override int GetHashCode()
            {
                return unchecked((3 * this.keySelector.GetHashCode()) + this.keyComparer.GetHashCode());
            }
        }
        #endregion

        #region ---- Reference Comparer ----
        /// <summary>
        /// Gets a cached <see cref="EqualityComparer{T}"/> instance which performs all comparisons by reference
        /// (i. e. as if with <see cref="object.ReferenceEquals(object, object)"/>). Uses 
        /// <see cref="RuntimeHelpers.GetHashCode(object)"/> to emulate the native identity-based hash function
        /// </summary>
        public static EqualityComparer<T> GetReferenceComparer<T>()
            where T : class
        {
            return ReferenceEqualityComparer<T>.Instance;
        }

        private sealed class ReferenceEqualityComparer<T> : EqualityComparer<T>
            where T : class
        {
            public static readonly EqualityComparer<T> Instance = new ReferenceEqualityComparer<T>();

            public override bool Equals(T x, T y)
            {
                return ReferenceEquals(x, y);
            }

            public override int GetHashCode(T obj)
            {
                // handles nulls
                return RuntimeHelpers.GetHashCode(obj);
            }
        }
        #endregion

        #region ---- Collection Comparer ----
        /// <summary>
        /// Gets an <see cref="EqualityComparer{T}"/> that compares instances of <see cref="IEnumerable{TElement}"/> as
        /// if with <see cref="CollectionHelper.CollectionEquals{TElement}(IEnumerable{TElement}, IEnumerable{TElement}, IEqualityComparer{TElement})"/>.
        /// The optional <paramref name="elementComparer"/> can be used to override the comparison of individual elements
        /// </summary>
        public static EqualityComparer<IEnumerable<TElement>> GetCollectionComparer<TElement>(IEqualityComparer<TElement> elementComparer = null)
        {
            return elementComparer == null || elementComparer == EqualityComparer<TElement>.Default
                ? CollectionComparer<TElement>.DefaultInstance
                : new CollectionComparer<TElement>(elementComparer);
        }

        private sealed class CollectionComparer<TElement> : EqualityComparer<IEnumerable<TElement>>
        {
            private static EqualityComparer<IEnumerable<TElement>> defaultInstance;
            public static EqualityComparer<IEnumerable<TElement>> DefaultInstance
            {
                get
                {
                    return defaultInstance ?? (defaultInstance = new CollectionComparer<TElement>(EqualityComparer<TElement>.Default));
                }
            }

            private readonly IEqualityComparer<TElement> elementComparer;

            public CollectionComparer(IEqualityComparer<TElement> elementComparer)
            {
                this.elementComparer = elementComparer;
            }

            public override bool Equals(IEnumerable<TElement> x, IEnumerable<TElement> y)
            {
                if (x == null)
                {
                    return y == null;
                }
                else if (y == null)
                {
                    return false;
                }

                // avoid calling as extension to support DISABLE_EXTENSIONs in the Inline package
                return CollectionHelper.CollectionEquals(x, y, this.elementComparer);
            }

            public override int GetHashCode(IEnumerable<TElement> obj)
            {
                return obj != null
                    // combine hashcodes with xor to be order-insensitive
                    ? obj.Aggregate(-1, (hash, element) => hash ^ this.elementComparer.GetHashCode(element))
                    : 0;
            }

            public override bool Equals(object obj)
            {
                if (ReferenceEquals(obj, this)) { return true; }

                var that = obj as CollectionComparer<TElement>;
                return that != null && that.elementComparer.Equals(this.elementComparer);
            }

            public override int GetHashCode()
            {
                return ReferenceEquals(this, DefaultInstance)
                    ? base.GetHashCode()
                    : unchecked((3 * DefaultInstance.GetHashCode()) + this.elementComparer.GetHashCode());
            }
        }
        #endregion

        #region ---- Sequence Comparer ----
        /// <summary>
        /// Gets an <see cref="EqualityComparer{T}"/> which compares instances of <see cref="IEnumerable{TElement}"/> as if
        /// with <see cref="Enumerable.SequenceEqual{TSource}(IEnumerable{TSource}, IEnumerable{TSource})"/>. The optional 
        /// <paramref name="elementComparer"/> can be used to override the comparison of individual elements
        /// </summary>
        public static EqualityComparer<IEnumerable<TElement>> GetSequenceComparer<TElement>(IEqualityComparer<TElement> elementComparer = null)
        {
            return elementComparer == null || elementComparer == EqualityComparer<TElement>.Default
                ? SequenceComparer<TElement>.DefaultInstance
                : new SequenceComparer<TElement>(elementComparer);
        }

        private sealed class SequenceComparer<TElement> : EqualityComparer<IEnumerable<TElement>>
        {
            private static EqualityComparer<IEnumerable<TElement>> defaultInstance;
            public static EqualityComparer<IEnumerable<TElement>> DefaultInstance
            {
                get
                {
                    return defaultInstance ?? (defaultInstance = new SequenceComparer<TElement>(EqualityComparer<TElement>.Default));
                }
            }

            private readonly IEqualityComparer<TElement> elementComparer;

            public SequenceComparer(IEqualityComparer<TElement> elementComparer)
            {
                this.elementComparer = elementComparer;
            }

            public override bool Equals(IEnumerable<TElement> x, IEnumerable<TElement> y)
            {
                if (x == null)
                {
                    return y == null;
                }
                if (y == null)
                {
                    return false;
                }

                return x.SequenceEqual(y, this.elementComparer);
            }

            public override int GetHashCode(IEnumerable<TElement> obj)
            {
                return obj != null
                    // hash combine logic based on .NET Tuple.CombineHashCodes
                    ? obj.Aggregate(-1, (hash, element) => (((hash << 5) + hash) ^ this.elementComparer.GetHashCode(element)))
                    : 0;
            }

            public override bool Equals(object obj)
            {
                if (ReferenceEquals(obj, this)) { return true; }

                var that = obj as SequenceComparer<TElement>;
                return that != null && that.elementComparer.Equals(this.elementComparer);
            }

            public override int GetHashCode()
            {
                return ReferenceEquals(this, DefaultInstance)
                    ? base.GetHashCode()
                    : unchecked((3 * DefaultInstance.GetHashCode()) + this.elementComparer.GetHashCode());
            }
        }
        #endregion
    }
}

namespace
#if MedallionCollections_USE_LOCAL_NAMESPACE
                        Medallion.Tools.InlineNuGet.Tests
#else
                        Medallion.Collections
#endif
{
    [global::System.CodeDom.Compiler.GeneratedCodeAttribute("Medallion.Tools.InlineNuGet", "1.0.0.0"), global::System.Diagnostics.DebuggerNonUserCodeAttribute]

#if MedallionCollections_PUBLIC
                            public
#else
    internal
#endif
static partial class Traverse
    {
        #region ---- Along ----
        /// <summary>
        /// Enumerates the implicit sequence starting from <paramref name="root"/>
        /// and following the chain of <paramref name="next"/> calls until a null value
        /// is encountered. For example, this can be used to traverse a chain of exceptions:
        /// <code>
        ///     var innermostException = Traverse.Along(exception, e => e.InnerException).Last();
        /// </code>
        /// </summary>
        public static IEnumerable<T> Along<T>(T root, Func<T, T> next)
            where T : class
        {
            if (next == null) { throw new ArgumentNullException("next"); }

            return AlongIterator(root, next);
        }

        private static IEnumerable<T> AlongIterator<T>(T root, Func<T, T> next)
        {
            for (var node = root; node != null; node = next(node))
            {
                yield return node;
            }
        }
        #endregion

        #region ---- Breadth-First ----
        /// <summary>
        /// Enumerates the implicit tree described by <paramref name="root"/> and <paramref name="children"/>
        /// in a breadth-first manner. For example, this could be used to enumerate the exceptions of an
        /// <see cref="AggregateException"/>:
        /// <code>
        ///     var allExceptions = Traverse.BreadthFirst((Exception)new AggregateException(), e => (e as AggregateException)?.InnerExceptions ?? Enumerable.Empty&lt;Exception&gt;());
        /// </code>
        /// </summary>
        public static IEnumerable<T> BreadthFirst<T>(T root, Func<T, IEnumerable<T>> children)
        {
            if (children == null) { throw new ArgumentNullException("children"); }

            return BreadthFirstIterator(root, children);
        }

        private static IEnumerable<T> BreadthFirstIterator<T>(T root, Func<T, IEnumerable<T>> children)
        {
            // note that this implementation has two nice properties which require a bit more complexity
            // in the code: (1) children are yielded in order and (2) child enumerators are fully lazy

            yield return root;
            var queue = new Queue<IEnumerable<T>>();
            queue.Enqueue(children(root));

            do
            {
                foreach (var child in queue.Dequeue())
                {
                    yield return child;
                    queue.Enqueue(children(child));
                }
            }
            while (queue.Count > 0);
        }
        #endregion

        #region ---- Depth-First ----
        /// <summary>
        /// Enumerates the implicit tree described by <paramref name="root"/> and <paramref name="children"/>
        /// in a depth-first manner. For example, this could be used to enumerate the exceptions of an
        /// <see cref="AggregateException"/>:
        /// <code>
        ///     var allExceptions = Traverse.DepthFirst((Exception)new AggregateException(), e => (e as AggregateException)?.InnerExceptions ?? Enumerable.Empty&lt;Exception&gt;());
        /// </code>
        /// </summary>
        public static IEnumerable<T> DepthFirst<T>(T root, Func<T, IEnumerable<T>> children)
        {
            if (children == null) { throw new ArgumentNullException("children"); }

            return DepthFirstIterator(root, children);
        }

        private static IEnumerable<T> DepthFirstIterator<T>(T root, Func<T, IEnumerable<T>> children)
        {
            // note that this implementation has two nice properties which require a bit more complexity
            // in the code: (1) children are yielded in order and (2) child enumerators are fully lazy

            var current = root;
            var stack = new Stack<IEnumerator<T>>();

            try
            {
                while (true)
                {
                    yield return current;

                    var childrenEnumerator = children(current).GetEnumerator();
                    if (childrenEnumerator.MoveNext())
                    {
                        // if we have children, the first child is our next current
                        // and push the new enumerator
                        current = childrenEnumerator.Current;
                        stack.Push(childrenEnumerator);
                    }
                    else
                    {
                        // otherwise, cleanup the empty enumerator and...
                        childrenEnumerator.Dispose();

                        // search up the stack for an enumerator with elements left
                        while (true)
                        {
                            if (stack.Count == 0)
                            {
                                // we didn't find one, so we're all done
                                yield break;
                            }

                            var topEnumerator = stack.Peek();
                            if (topEnumerator.MoveNext())
                            {
                                current = topEnumerator.Current;
                                break;
                            }
                            else
                            {
                                stack.Pop().Dispose();
                            }
                        }
                    }
                }
            }
            finally
            {
                // guarantee that everything is cleaned up even
                // if we don't enumerate all the way through
                while (stack.Count > 0)
                {
                    stack.Pop().Dispose();
                }
            }
        }
        #endregion
    }
}