C# Set Implementation (pre-.NET 3.5)

I was recently working on a .NET 3.0 project and found that this version of the framework didn't have any support for a mathematical Set collection. As of .NET 3.5 there is the System.Collections.Generic.HashSet implementation, however, I was working on a WinForms project and updating the framework on the client machines was out of scope for this piece of work.

I had some spare time available and thought it would be a good exercise to write a custom generic Set collection. The first step was to define an interface:

using System.Collections.Generic;

...

public interface ISet<T> : ICollection<T>
{
    void UnionWith(ISet<T> set);
    void IntersectWith(ISet<T> set);
}

By inheriting from ICollection, we get all of the generally useful collection-based methods included in the ISet interface (e.g. Add, Clear, Contains etc.). I just had two methods to add to those, these were the set union and set intersection operations.

The next step was the implementation of the set. To keep things simple, I opted for a list-based implementation. I used the adapter pattern to map the ISet interface to a list interface. Therefore, the internal representation of the Set was actually an instance of System.Collections.Generic.List. By using this approach, I could delegate a lot of the method logic to use the list method implementations (i.e. Clear, Contains, CopyTo and Remove). The only custom logic I needed to write was the Add method (to avoid adding items already within the set), UnionWith method, IntersectWith method, ToString method and the readonly indexer. The implementation is below:

/// <summary>
/// A list-based implementation of a mathematical set.
/// </summary>
public sealed class ListBasedSet<T> : ISet<T>
{
    private IList<T> _thisSet = new List<T>();

    /// <summary>
    /// Gets the number of elements contained in this set.
    /// </summary>
    public int Count { get { return _thisSet.Count; } }

    /// <summary>
    /// Gets a value indicating whether this set is readonly.
    /// </summary>
    public bool IsReadOnly { get { return false; } }

    /// <summary>
    /// Gets the item at the specified index in the set.
    /// </summary>
    /// <param name="i">
    /// Index of the item to retrieve from the set.
    /// </param>
    /// <returns>Item at the specified index</returns>
    public T this[int i] { get { return _thisSet[i]; } }

    /// <summary>
    /// Adds item into the set if this set does not already
    /// contain the item.
    /// </summary>
    /// <param name="item">Item to add to the set.</param>
    public void Add(T item)
    {
        if (!Contains(item))
            _thisSet.Add(item);
    }

    /// <summary>
    /// Clears the items from the set resulting in an empty set.
    /// </summary>
    public void Clear()
    {
        _thisSet.Clear();
    }

    /// <summary>
    /// Determines if the specified item is within the set.
    /// </summary>
    /// <param name="item">
    /// The object to locate in the set.
    /// </param>
    /// <returns>
    /// true if item is found in the set; false otherwise.
    /// </returns>
    public bool Contains(T item)
    {
        return _thisSet.Contains(item);
    }

    /// <summary>
    /// Copies the entire set to a one-dimensional array, 
    /// starting at the specified target index of the target 
    /// array.
    /// </summary>
    /// <param name="array">
    /// The one-dimensional array to copy to.
    /// </param>
    /// <param name="arrayIndex">
    /// The zero-based index in array at which copying begins.
    /// </param>
    public void CopyTo(T[] array, int arrayIndex)
    {
        _thisSet.CopyTo(array, arrayIndex);
    }

    /// <summary>
    /// Removes the specified item from the set.
    /// </summary>
    /// <param name="item">Item to remove.</param>
    /// <returns>
    /// true if item is successfully removed; otherwise, false. 
    /// This method also returns false if item was not found 
    /// in the set.
    /// </returns>
    public bool Remove(T item)
    {
        return _thisSet.Remove(item);
    }

    /// <summary>
    /// Returns an enumerator that iterates through the set.
    /// </summary>
    /// <returns>
    /// An IEnumerator object that can be used to iterate 
    /// through the set.
    /// </returns>
    public IEnumerator<T> GetEnumerator()
    {
        return _thisSet.GetEnumerator();
    }

    /// <summary>
    /// Returns an enumerator that iterates through the set.
    /// </summary>
    /// <returns>
    /// An IEnumerator object that can be used to iterate 
    /// through the set.
    /// </returns>
    System.Collections.IEnumerator 
        System.Collections.IEnumerable.GetEnumerator()
    {
        return _thisSet.GetEnumerator();
    }

    /// <summary>
    /// Modifies this set to contain all elements that are 
    /// present in itself, the specified collection, or both.
    /// </summary>
    /// <param name="otherSet">The set to union with.</param>
    public void UnionWith(ISet<T> otherSet)
    {
        foreach (var item in otherSet)
            Add(item);
    }

    /// <summary>
    /// Modifies this set to contain only the elements that are 
    /// present in it and in the specified collection.
    /// </summary>
    /// <param name="otherSet">The set to intersect with.</param>
    public void IntersectWith(ISet<T> otherSet)
    {
        var itemsToRemove = new List<T>();

        for (int i  = 0; i < Count; i++)
        {
            T item = this[i];

            if (!otherSet.Contains(item))
                itemsToRemove.Add(item);
        }

        foreach (var itemToRemove in itemsToRemove)
            Remove(itemToRemove);
    }

    /// <summary>
    /// Returns a string representation of this set
    /// </summary>
    /// <returns>A string representation of this set</returns>
    public override string ToString()
    {
        var setStringBuilder = new StringBuilder();
        setStringBuilder.Append("{");

        foreach (var item in _thisSet)
            setStringBuilder.Append(
                string.Format(" {0},", item));
            
        return string.Format("{0} }}", 
            setStringBuilder.ToString().TrimEnd(','));
    }
}

Example usage:

ISet<string> set = new ListBasedSet<string> 
    { "Mars", "Earth", "Pluto" };
ISet<string> otherSet = new ListBasedSet<string> 
    { "Jupiter", "Earth", "Pluto", "Venus" };
ISet<string> earthSet = new ListBasedSet<string> 
    { "Earth" };
ISet<string> emptySet = new ListBasedSet<string>();

set.UnionWith(otherSet);
Console.WriteLine("set UNION otherset = {0}", set);

Console.WriteLine("|set| (cardinality of set) = {0}", set.Count);

set.IntersectWith(earthSet);
Console.WriteLine("set INTERSECTION earthSet = {0}", set);

set.UnionWith(emptySet);
Console.WriteLine("set UNION emptySet = {0}", set);

set.IntersectWith(emptySet);
Console.WriteLine("set INTERSECTION emptySet = {0}", set);

You can download the source files for the ISet interface and the ListBasedSet class from here.

10 C#/.NET Features You May Not Know About

I thought it would be useful to document some of the typically lesser known features of the C# programming language and the .NET framework as a series of posts. Some of these features I've found useful and others I probably just haven't found a suitable use case for yet.

1. Anonymous Code Scopes in Methods

It's possible to have anonymous inner scopes within your method definitions. (I'm yet to come across a non-contrived use case for this!)

void MethodWithAnonymousScope()
{
    var helloPart = "Hello";

    {
        var worldPart = "world";
        Console.WriteLine("{0} {1}", helloPart, worldPart);
    }

    // "worldPart" doesn't resolve in this scope
}

2. Increment/Decrement Operator Position Significance

The position of the increment (++) and decrement (--) operators is significant. In the example below, when the increment operator is used as a postfix, it returns the value of 'number' before it has been incremented. Conversely, the prefix increment operator returns the value after it has been incremented. The decrement operator works with the same logic but decrements the number.

void PlusPlusOperator()
{
    var number = 0;

    Console.WriteLine(number++); // Outputs zero
    Console.WriteLine(++number); // Outputs two
}

3. The Default Keyword

The default keyword is a neat way to get the default value for a specified type. It's especially useful when working in a generic context.

void DefaultKeyword()
{
    var intDefault = default(int); // default(int) == 0
    var boolDefault = default(bool); // default(bool) == false

    // default(string) == null (as for all reference types)
    var stringDefault = default(string); 
}

4. Null-Coalescing Operator

The null-coalescing operator (??) provides a succinct way of returning a default value if your reference or nullable-value type is null. In the following example, if myNullableInteger (left operand) is not null, then it's returned, else the default value for int is returned (right operand).

int NullCoalescingOperator()
{
    int? myNullableInteger = SomeMethodThatCouldReturnNull();
    return myNullableInteger ?? default(int);
}

5. Short-Circuit Evaluation with Boolean Operators

The logical AND (&&) and OR (||) operators are short-circuit evaluated (left to right). For example, if the left operand of a logical AND is false, the right operand is not evaluated (as the whole condition will always be false). Similarly, if the left operand of a logical OR is true, the right operand is not evaluated. This can be demonstrated by observing the output of:

void ShortCircuitEvaluation()
{
    bool result;
            
    result = LeftOperand(true) || RightOperand(false);
    result = LeftOperand(false) || RightOperand(true);
    result = LeftOperand(true) && RightOperand(false);
    result = LeftOperand(false) && RightOperand(true);
}

bool LeftOperand(bool value)
{
    Console.WriteLine("Left operand evaluated");
    return value;
}

bool RightOperand(bool value)
{
    Console.WriteLine("Right operand evaluated");
    return value;
}

It's useful to know this so that you can safely perform multiple tests in a single if statement. In the example below, if myObject is null, the right operand is not evaluated (which is good because it'd cause a NullReferenceException).

if (myObject != null && myObject.SomeProperty == SomeValue)
    ...

Also note that if you use a single '&' and single '|' you bypass short-circuit evaluation and force the entire condition to be evaluated.

6. Aliases for Generic Types

You can assign an alias to a namespace but you can also assign an alias to a specific generic type to save yourself from typing the awkward generic syntax over and over again (especially useful when working with key/value pair based generic types where the value may also be a key/value pair!).

using StringList = System.Collections.Generic.List<string>;
...
void GenericAliases()
{
    // Can use the alias "StringList"
    // instead of List<string> 

    var stringList = new StringList();
    stringList.Add("Hello");
    stringList.Add("World");
    stringList.ForEach(Console.WriteLine);
}

7. Extension Methods on Dynamic Types

I came across this one when working with the dynamic ViewBag in ASP.NET MVC. As the title states, you cannot invoke an extension method on a type (that has the extension method defined for it and is in scope) which is dynamically typed. I have documented this one in this post (click to view). As the post shows, you have to call your extension method in the same fashion as you would call a standard static method, then pass your dynamically typed variable in as a parameter to the extension method.

8. System.String supports an Indexer

The string class has a readonly (get) char indexer defined on it, thus allowing you to access characters in the string using a zero-based index.

void StringIndexer()
{
    string message = "Hello, world!";

    for (int i = 0; i < message.Length; i++)
    {
        Console.WriteLine(message[i]); 
    }
}

9. Using foreach with System.String

The string class implements the IEnumerable<char> interface, which means that you can use the foreach statement on a string to enumerate through each character.

void ForeachWithString()
{
    string message = "Hello, world!";

    foreach (char character in message)
    {
        Console.WriteLine(character);
    }
}

10. Introspecting Code with Expression Trees

The System.Linq.Expressions.Expression class enables you to represent a code expression in a tree-based data structure that can then be used for introspection. This is a powerful feature which also then enables code modification in the expression tree (at runtime) and then subsequent compilation and execution.

The following example shows how we can wrap a simple lambda expression into an Expression, introspect the expression, compile the expression (in this case returning a Func<int, int, int>) and then execute the expression.

void Expressions()
{
    Expression<Func<int, int, int>> addExpression = (a, b) => a + b;

    foreach (var param in addExpression.Parameters)
    {
        Console.WriteLine(
            "Func Param Name: {0}, Param Type: {1}", 
            param.Name, 
            param.Type);
    }

    Console.WriteLine("Func return type: {0}", 
        addExpression.ReturnType);

    Console.WriteLine("10 + 20 = {0}", 
        addExpression.Compile()(10, 20));
                        
    // Can also use the Invoke method on the returned Func<...>
    // to aid readability
    // e.g. addExpression.Compile().Invoke(10, 20);
}

You may have indirectly used expression trees if you're an ASP.NET MVC developer. The HTML helper classes make extensive use of them, for example, the Html.TextBoxFor method has an overload that accepts a single parameter of type Expression<Func<dynamic, dynamic>>. An example call to this method would be @Html.TextBoxFor(m => m.FirstName) where 'm' is an instance of your view model. The TextBoxFor method uses the supplied expression (a lambda) to construct the HTML that is put back into the view. In this case it outputs an input element with an id and name attribute value of "FirstName" - which was retrieved using introspection (made possible with expression trees).

Dependency Resolution in ASP.NET MVC3/4 with Ninject

The topic for this post is setting up the Ninject Inversion of Control (IoC) container in your ASP.NET MVC3/4 applications. I'm assuming the reader has familiarity with the following concepts:

• Programming to an interface (or contract)
• The IoC programming technique
• Dependency injection
• IoC containers

The intention is for this post to serve as a useful reference for ASP.NET MVC developers who want to get an IoC container (specifically Ninject) up and running swiftly with the MVC framework.

When working on a new MVC project, one of my first steps usually involves setting up an IoC container. I've typically used Ninject as my IoC container due to its ease of setup and intuitive fluent API. As of ASP.NET MVC3, there is the option of using the Ninject extension for MVC3 (wrapped up in a NuGet package called Ninject.MVC3). This option is simple to setup and you'll typically have little reason to use another approach. Another option is to write your own implementation of the IDependencyResolver interface. In this scenario, you'll implement this interface (which again is quite simple with Ninject) and then hook your custom resolver into the framework for it to use. In a nutshell, the MVC framework will use your custom IDependencyResolver implementation as a first port of call to resolve any required dependencies.

In this post, we'll go with the former option.

Using the Ninject.MVC3 NuGet Package

As mentioned, the Ninject.MVC3 NuGet package is an easy way to get Ninject up and running in your project. The first step is to get the package installed in your solution. I'm using Visual Studio 2012 so the steps may differ slightly depending on what version of the IDE you're running on. Right click your MVC solution node in Solution Explorer. Select the "Manage NuGet Packages for Solution" option in the context menu.



This will bring up the NuGet package manager dialog. In the top right, you should see a text box with the watermark "Search Online". Type "Ninject" and hit enter. In the middle pane, you'll see the Ninject.MV3 package, select it and click the Install button.



At this point, the NuGet package manager will have done all of the hard work. If you expand the App_Start folder in your solution, you'll find a new file called NinjectWebCommon.cs.



This file contains a static class definition and a number of static methods. The methods that you're interested in are the CreateKernal and the RegisterServices methods. If you have had experience with Ninject in the past, then you'll be at home with what the CreateKernal method is doing. It creates an instance of the StandardKernal (the default implementation of Ninjects IKernal interface). The StandardKernel is the class you'll use to map (or in Ninject terminology "bind") interfaces to the implementations that you want to use. This is done by using the generic methods Bind and To on the kernel object, where you pass your interface and implementation, respectively, as type parameters. You'll notice that the CreateKernal method makes a call to a method named RegisterServices. This is the method where you'll register your bindings with Ninject.

private static void RegisterServices(IKernel kernel)
{
    // Register your ninject bindings here!
}

Now that Ninject is setup in the project, we'll try and inject a dependency through a controller constructor. In this example, imagine you have a simple logging interface, defined as:

public interface ILogService
{
    void Log(string message);
}

We then have an implementation of this interface:

public class DebugLogService : ILogService
{
    public void Log(string message)
    {
        System.Diagnostics.Debug.WriteLine(message);
    }
}

Imagine further that we now wanted various actions in our HomeController to log to the debug output. With dependency injection, one way to inject our DebugLogService implementation into our HomeController would be through the constructor - as follows:

public class HomeController : Controller
{
    private readonly ILogService _logService;

    public HomeController(ILogService logService)
    {
        _logService = logService;
    }

    public ActionResult Index()
    {
        _logService.Log(
            string.Format("Index() called at {0}", 
                DateTime.Now));

        return View();
    }
}

If you're following the steps and you now run your web application, you'll get a runtime exception stating that there was an error activating ILogService. This is good, as it tells you that Ninject tried to create an instance of the HomeController, but failed in doing so because the HomeController has no default constructor. The constructor that it does have, however, has one required parameter (logService) that Ninject has no type bindings for. We'll now go back to the static RegisterServices method in the NinjectWebCommon class and add the binding as shown below:

private static void RegisterServices(IKernel kernel)<br />{<br />    kernel.Bind<ILogService>().To<DebugLogService>();<br />}

If you now run the application, you'll find that the HomeController is successfully being instantiated with Ninject passing an instance of the DebugLogService class through to the constructor. You can verify this by looking at the output window for the log entry.



And that's it - you'll now follow this pattern for registering your bindings in the RegisterServices method and programming to your interfaces for which you have registered bindings. As all of your bindings are registered in a single location, swapping out your implementations with other implementations is an easy job. We can now easily switch all logging to a file by writing a new FileLogService (that implements ILogService) and then bind this to the ILogService in the RegisterServices method.