3
\$\begingroup\$

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...
}
\$\endgroup\$

2 Answers 2

2
\$\begingroup\$
  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.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ Re #1 - the non-standard TValue constraint I have allows for System.Nullable structs like int?, but not int (enforced at compile time for the latter). So, class won't work. Re #2 - this effectively answers my question of whether it is possible to throw a compile time error (which is no) - so, I'll mark this as the answer. Between this and @mjolka's answer, it appears that changing the API would make the most sense. \$\endgroup\$
    – gangreen
    Jan 12, 2015 at 5:09
3
\$\begingroup\$

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.

\$\endgroup\$
2
  • \$\begingroup\$ Re the Interface - I’m hesitant to change their API since so much of it is interdependent. They definitely rely on the null value being returned when a key is not there in other classes. Changes would require careful study and I am still trying to grasp the fundamentals. Re exceptions - I’ve heard it said that throwing exceptions is expensive, so if I were to catch KeyNotFoundException’s when necessary (e.g., during a massive insert into separate-chaining hash table), do you think performance would be significantly reduced? \$\endgroup\$
    – gangreen
    Jan 11, 2015 at 1:29
  • \$\begingroup\$ @gangreen I understand your concerns, but I really think this is the way to go. The careful study you mention will be good for your understanding of the data structures, and for becoming more familiar with C#. Throwing exceptions is relatively expensive, so providing a non-throwing way of retrieving a value e.g. TryGetValue is a good idea. \$\endgroup\$
    – mjolka
    Jan 11, 2015 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.