ListExtensions - Defines a set of extension methods to add commonly-used operations to every List instance.

ListExtensions.cs

// Copyright (c) 2017 StagPoint Software

namespace StagPoint.Collections
{
	using System;
	using System.Collections.Generic;

	/// <summary>
	/// Defines a set of extension methods to add commonly-used operations to every List instance.
	/// </summary>
	public static class ListExtensions
	{
		/// <summary>
		/// Ensures that the list contains the internal capacity to add the indicated number of elements.
		/// </summary>
		/// <param name="capacity">The number of elements that will be added.</param>
		public static void EnsureCapacity<T>( this List<T> list, int capacity )
		{
			if( capacity > list.Capacity )
			{
				list.Capacity = capacity;
			}
		}

		/// <summary>
		/// Removes the first occurrence of a specific object from the collection. This function is faster (in some
		/// cases *WAY* faster) than Remove() due to moving only one element as opposed to shifting larger portions
		/// of the internal array, but will change the order of the elements contained in the list.
		/// </summary>
		public static bool FastRemove<T>( this IList<T> list, T item )
		{
			var index = list.IndexOf( item );
			if( index == -1 )
				return false;

			if( index < list.Count - 1 )
			{
				list[ index ] = list[ list.Count - 1 ];
			}

			list.RemoveAt( list.Count - 1 );

			return true;
		}

		/// <summary>
		/// Removes the the element at the specified index position. This function is faster (in some
		/// cases *WAY* faster) than Remove() due to moving only one element as opposed to shifting 
		/// larger portions of the internal array, but will change the order of the elements contained 
		/// in the list.
		/// </summary>
		public static bool FastRemoveAt<T>( this IList<T> list, int index )
		{
			if( index < list.Count - 1 )
			{
				list[ index ] = list[ list.Count - 1 ];
			}

			list.RemoveAt( list.Count - 1 );

			return true;
		}

		/// <summary>
		/// Determines the index of a specific item in the collection by checking object references only, which
		/// can be faster than checking for equality using an EqualityComparer, but only works for reference
		/// types.
		/// </summary>
		public static int IndexOfReference<T>( this IList<T> list, object obj ) where T : class
		{
			var count = list.Count;
			for( int i = 0; i < count; i++ )
			{
				if( object.ReferenceEquals( obj, list[ i ] ) )
				{
					return i;
				}
			}

			return -1;
		}

		/// <summary>
		/// Determines whether the collection contains the specified reference by checking object references only,
		/// which can be faster than checking for equality using an EqualityComparer, but only works for reference
		/// types. If this collection contains a value type the function will always return FALSE.
		/// </summary>
		public static bool ContainsReference<T>( this IList<T> list, T item ) where T : class
		{
			var count = list.Count;

			for( int i = 0; i < count; i++ )
			{
				if( object.ReferenceEquals( list[ i ], item ) )
				{
					return true;
				}
			}

			return false;
		}

		/// <summary>
		/// Removes the first occurrence of a specific object from the collection. This function is faster (in some
		/// cases *WAY* faster) than Remove(), but will change the order of the elements contained in the list.
		/// This function searches for the item using object reference comparisons only, which can be faster than 
		/// checking for equality using an EqualityComparer, but only works for reference types.
		/// </summary>
		public static bool FastRemoveReference<T>( this IList<T> list, T item ) where T : class
		{
			var index = IndexOfReference( list, item );
			if( index == -1 )
				return false;

			var maxIndex = list.Count - 1;

			if( index < maxIndex )
			{
				list[ index ] = list[ maxIndex ];
			}

			list.RemoveAt( maxIndex );

			return true;
		}

		/// <summary>
		/// Removes an object by searching only for the specified object reference, which can be faster 
		/// than checking for equality using an EqualityComparer, but only works for reference
		/// types. 
		/// </summary>
		public static bool RemoveReference<T>( this IList<T> list, T obj ) where T : class
		{
			var index = IndexOfReference( list, obj );
			if( index == -1 )
				return false;

			list.RemoveAt( index );

			return true;
		}

		/// <summary>
		/// Sorts a range of elements in a pair of lists (one contains the keys and the other contains the corresponding items) based on the keys list using the <see cref="T:System.IComparable"/> implementation of each key.
		/// </summary>
		/// <param name="items">The list that contains the items that correspond to each of the keys in the <paramref name="keys"/> list.</param>
		/// <param name="keys">The list that contains the keys to sort.</param>
		/// <param name="index">The starting index of the range to sort.</param>
		/// <param name="length">The number of elements in the range to sort.</param>
		public static void SortBy<TItem, TKey>( this IList<TItem> items, IList<TKey> keys, int index, int length ) where TKey : IComparable<TKey>
		{
			var itemCount = items.Count;
			if( keys.Count - index < length || index > itemCount - length )
			{
				throw new ArgumentException( "Invalid start index or number of elements" );
			}

			// NOTE: Insertion sort is likely to be faster on smaller arrays
			if( length <= 128 )
			{
				insertionSort( keys, items, index, length );
			}
			else
			{
				quickSort( keys, items, index, index + length - 1 );
			}
		}

		/// <summary>
		/// Sorts all elements in a pair of lists (one contains the keys and the other contains the corresponding items) based on the keys list using the <see cref="T:System.IComparable"/> implementation of each key.
		/// </summary>
		/// <param name="items">The list that contains the items that correspond to each of the keys in the <paramref name="keys"/> list.</param>
		/// <param name="keys">The list that contains the keys to sort.</param>
		public static void SortBy<TItem, TKey>( this IList<TItem> items, IList<TKey> keys ) where TKey : IComparable<TKey>
		{
			var itemCount = items.Count;
			if( keys.Count != itemCount )
			{
				throw new ArgumentException( "The keys array does not contain the same number of elements as the array to be sorted" );
			}

			// NOTE: Insertion sort is likely to be faster on smaller arrays
			if( itemCount <= 128 )
			{
				insertionSort( keys, items, 0, itemCount );
			}
			else
			{
				quickSort( keys, items, 0, itemCount - 1 );
			}
		}

		#region Private utility functions

		private static void insertionSort<TKey, TItem>( IList<TKey> keys, IList<TItem> items, int index, int length ) where TKey : IComparable<TKey>
		{
			for( int i = index; i < length - 1; i++ )
			{
				int j = i + 1;

				while( j > index )
				{
					if( keys[ j - 1 ].CompareTo( keys[ j ] ) > 0 )
					{
						TKey tempKey = keys[ j - 1 ];
						keys[ j - 1 ] = keys[ j ];
						keys[ j ] = tempKey;

						TItem tempItem = items[ j - 1 ];
						items[ j - 1 ] = items[ j ];
						items[ j ] = tempItem;
					}

					j--;
				}
			}
		}

		private static void quickSort<TKey, TItem>( IList<TKey> keys, IList<TItem> items, int start, int end ) where TKey : IComparable<TKey>
		{
			if( start < end )
			{
				int pivot = partition( keys, items, start, end );
				quickSort( keys, items, start, pivot - 1 );
				quickSort( keys, items, pivot + 1, end );
			}
		}

		private static int partition<TKey, TItem>( IList<TKey> keys, IList<TItem> items, int start, int end ) where TKey : IComparable<TKey>
		{
			var pivot = keys[ end ];
			int pivotIndex = start;

			TKey keyTemp = default( TKey );
			TItem itemTemp = default( TItem );

			for( int i = start; i < end; i++ )
			{
				if( keys[ i ].CompareTo( pivot ) <= 0 )
				{
					keyTemp = keys[ i ];
					keys[ i ] = keys[ pivotIndex ];
					keys[ pivotIndex ] = keyTemp;

					itemTemp = items[ i ];
					items[ i ] = items[ pivotIndex ];
					items[ pivotIndex ] = itemTemp;

					pivotIndex++;
				}
			}

			keyTemp = keys[ pivotIndex ];
			keys[ pivotIndex ] = keys[ end ];
			keys[ end ] = keyTemp;

			itemTemp = items[ pivotIndex ];
			items[ pivotIndex ] = items[ end ];
			items[ end ] = itemTemp;

			return pivotIndex;
		}

		#endregion
	}
}