Nullable Generics - Implementing SequentialSearchST in C#

Question

For learning purposes, I am implementing certain code from Sedgewick & Wayne's Algorithms, Fourth Edition.

Because of language features, a direct translation doesn't seem possible.

For example, I believe the get method in their implementation of SequentialSearchST can return null for both value and reference types because Java boxes/unboxes "value objects" (for lack of a better term) like Integer automatically.

C#, as far as I can tell, does not have an equivalent built in. It also does not appear to be possible to put an all-purpose nullable constraint on a generic type.

At least one other person has tried this, but their implementation does not allow you to store reference types for TValue which prevents you from implementing other Algorithms classes like SeparateChainingHashST.

So, I have decided to throw a runtime error in the static constructor below. Is that about as good as it gets? That is, is there no way to throw a compile time error?

public class SequentialSearchSt<TKey, TValue>
{
    private Node first;

    static SequentialSearchSt()
    {
        if (!default(TValue).Equals(null)) throw new InvalidOperationException("TValue must be a nullable or reference type.");
    }

    private class Node
    {
        public TKey key;
        public TValue val;
        public Node next;

        public Node(TKey key, TValue val, Node next)
        {
            this.key = key;
            this.val = val;
            this.next = next;
        }
    }

    public TValue Get(TKey key)
    {
        for (Node x = first; x != null; x = x.next)
        {
            if (key.Equals(x.key))
            {
                return x.val;
            }
        }
        return default(TValue);
    }

    // more code...
}

Answer 1

1. Your requirement as it stands effectively means that TValue needs to be a reference type. Your method of enforcing this is unnecessary hard and non-standard. A generic type constraint would express this requirement much better and also lead to a compile time error rather than runtime error:

   public class SequentialSearchSt<TKey, TValue> where TValue : class
   {
        ....
   

2. The .NET library team had the same problem you did. Before generics where introduced classes like Hashtable were provided which would operate on object and thus box value types like int allowing it to actually return null if the key was not present. After generics where introduced this was not an option for classes like Dictionary<TKey, TValue>. The solution to this was to have Get throw a KeyNotFoundException and to implement a bool TryGet(TKey key, out TValue value) method which provides the value through the out parameter and return true or false depending on whether the key is present or not.

3. You might want to implement an iterator for your list. This will let you use LINQ for a great many constructs usually resulting in more concise code. Something like this:

   private IEnumerable<Node> AllNodes()
   {
       for (Node x = first; x != null; x = x.next)
       {
           yield return x;
       }
   }
   

   Lets you implement Get like this:

   public TValue Get(TKey key)
   {
       var n = AllNodes.FirstOrDefault(n => n.key == key);
       if (n == null)
           throw KeyNotFoundException();
       return n.val;
   }
   

4. Standard C# naming convention is to use PascalCase for public class/struct members. It's a matter of consistency which makes your code easier to read for others.

Answer 2

Consider removing the requirement that default(TValue) is null, and instead of returning null, throw a KeyNotFoundException:

The exception that is thrown when the key specified for accessing an element in a collection does not match any key in the collection.

For convenience, you may also want to provide a bool TryGetValue(TKey key, out TValue value) method.

If possible, making SequentialSearchSt<TKey, TValue> implement IDictionary<TKey, TValue> will make using the class easier for any .NET developer.