RemoveWhere Extension Method

RemoveWhere.cs

/// <summary>
/// Modifies a collection in-place by removing items from the collection that match
/// a given <see cref="T:Predicate[T]"/>.
/// </summary>
/// <remarks>
/// The type of collection passed in will affect how the method performs. For collections
/// with a built-in method to remove in-place (such as sets) the existing implementation
/// will be used. For collections implementing IList[T], the method will perform better
/// because the collection can be enumerated more efficiently. For all other collections,
/// the items to remove will be buffered and Remove will be called individually which,
/// depending on the collection type, can be very slow resulting in an O(n) scan to
/// determine the items to remove, then a separate O(n) scan for each item that matched.
/// </remarks>
/// <typeparam name="T">The type of item in the collection.</typeparam>
/// <param name="collection">The collection to remove from.</param>
/// <param name="match">The predicate that determines if the item will be removed.</param>
/// <returns>The number of items removed.</returns>
/// <example>
/// <![CDATA[
///     var numbers = new Collection<int>() { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };
///     numbers.RemoveWhere( x => x % 2 == 0 );  // remove even numbers
/// ]]>
/// </example>
public static int RemoveWhere<T>( this ICollection<T> collection, Predicate<T> match )
{

    Args.ThrowIfNull( collection, "collection" );
    Args.ThrowIfNull( match, "match" );

    if ( collection.IsReadOnly ) { throw new NotSupportedException( "The collection is read-only." ); }

    // Defer to existing implementation...
    var hashSetOfT = collection as HashSet<T>;
    if ( hashSetOfT != null ) {
        return hashSetOfT.RemoveWhere( match );
    }

    // Defer to existing implementation...
    var sortedSetOfT = collection as SortedSet<T>;
    if ( sortedSetOfT != null ) {
        return sortedSetOfT.RemoveWhere( match );
    }

    // Defer to existing implementation...
    var listOfT = collection as List<T>;
    if ( listOfT != null ) {
        return listOfT.RemoveAll( match );
    }

    // Have to use our own implementation.

    int removed = 0;

    // IList<T> is pretty efficient because we only have to enumerate
    // the list once and if a match, we remove at that position.
    // Enumerate backwards so that the indexes don't shift out from under us.
    var list = collection as IList<T>;
    if ( list != null ) {

        for ( int i = list.Count - 1 ; i >= 0 ; i-- ) {
            T item = list[i];
            if ( match( item ) ) {
                list.RemoveAt( i );
                removed++;
            }
        }

        return removed;

    }

    // For ICollection<T> it isn't as efficient because we have to first
    // buffer all the items to remove in a temporary collection.
    // Then we enumerate that temp collection removing each individually
    // from the ICollection<T> which could be potentially O(n).

    var itemsToRemove = new List<T>( from x in collection where match( x ) select x );
    foreach ( T item in itemsToRemove ) {
        if ( collection.Remove( item ) ) {
            removed++;
        }
    }

    return removed;

}

RemoveWhere_Tests.cs

[TestClass]
public class CollectionExtensionsTests
{

    private static int[] numbers;
    private static int[] odds;

    [ClassInitialize]
    public static void ClassInitialize( TestContext context )
    {
        numbers = Enumerable.Range( 0, 100000 ).ToArray( );
        odds = Enumerable.Range( 0, 100000 ).Where( x => x % 2 != 0 ).ToArray( );
    }

    [TestMethod]
    public void RemoveWhere_HashSet( )
    {

        var collection = new HashSet<int>( numbers );
        collection.RemoveWhere( IsEven );

        Assert.IsTrue( collection.SetEquals( odds ) );

    }

    [TestMethod]
    public void RemoveWhere_SortedSet( )
    {

        var collection = new SortedSet<int>( numbers );
        collection.RemoveWhere( IsEven );

        CollectionAssert.AreEqual( collection, odds );

    }

    [TestMethod]
    public void RemoveWhere_ListOfT( )
    {

        var collection = new List<int>( numbers );
        collection.RemoveWhere( IsEven );

        CollectionAssert.AreEqual( collection, odds );

    }

    [TestMethod]
    public void RemoveWhere_ObservableCollection( )
    {

        var collection = new ObservableCollection<int>( numbers.ToList( ) );
        collection.RemoveWhere( IsEven );

        CollectionAssert.AreEqual( collection, odds );

    }

    [TestMethod]
    public void RemoveWhere_Collection( )
    {

        var collection = new Collection<int>( numbers.ToList( ) );
        collection.RemoveWhere( IsEven );

        CollectionAssert.AreEqual( collection, odds );

    }


    private static bool IsEven( int x )
    {
        return ( x % 2 ) == 0;
    }

}