I'm writing down the API for my IMap<A,B> interface. In other systems it has the name Dictionary, Associative Array, or Map. I prefer the latter because it seems to be just a way of mapping a domain (A) to a range (B). The basics of the interface are three operations:

  • GetAt(A a)
  • SetAt(A a, B b)
  • RemoveAt(A a)
  • ISet<A> Domain { get; }
  • ICollection<B> Range { get; }
However, I'm a little unsure about what the signatures should look like. I was considering: "B GetAt(A a)" but then there's the issue of what happens when you try to get using an element that isn't in the map. I think returning default(B) is a bad idea because you can't distinguish the failure case from the case where the value actually maps to default(B). I could throw an exception, however based on personal experience this has a very serious affect on performance. In one of my applications a Map was used as the core data structure and 'Get'ing was easily 75% of the app time and it was extremely common to try to get values that weren't in the map. If i had to either catch the exception, or do a "if (map.Domain.Contains(a))" then I'd seriously affect performance.

Because of this use of a map i see it as being part of the expected behavior that someone might try to query what a value maps to when that value isn't in the Domain of the map. In other words, I don't think that that's exceptional behavior, but expected behavior. Because of this, the API needs to take that into account. There are a couple of ways that taht could be done. One is to use C#'s 'out' parameters (a feature I'm not a fan of) to indicate if the value was in the range: "B GetAt(A a, out bool inDomain)". If 'a' was in the domain then the value is returned and "true" is passed out. If 'a' isn't in the domain then "false" is passed out and the return value is undefined. The other alternative is to use the Optional type to return both the value and the bool at once: "IOptional<B> GetAt(A a)". If the map doesn't contain the value in the domain then an IOptional whose HasValue is false is returned. If the map does contain the value in the domain then an IOptional whose Hasvalue is true and whose Value is the element from teh range is returned.

Any other ideas for how this should be handled? Are there any styles that you think are better than this? Compelling reasons for exceptions, out params, optional types?

Another thing that came up while talkign to Neil about the collections is what the interface for IList would look like. Currently it's:

public interface IList<A> : ICollection<A>, IMap<int,A>, IRange<int> {
      ...
}
This inheritance chain made sense to me because you can think of a list as a collection of values and a mapping from the integers to those values. However, this leads to an interesting developement. The methods for IList now look like this:
    IOptional<A> GetAt(int index);
    IOptional<A> SetAt(int index, A value);
    IOptional<A> RemoveAt(int index);
This is quite different that the list APIs that I am used to that normally throw when you try to get an element using an index that isn't in the range 0<->list.Length - 1. However, in this version you'll instead get an IOptional back and will nevver throw. I think I could get used to this, however I'm unsure of how galling other's might find it. The more I use it, the more I like it. It's more cumbersome in the case where you know you are indexing ok into the list, but it's far less cumbersome in the case where you're not and you're catching IndexOutOfRangeExceptions.

Edit: The code for IOptional<T> looks like this:

 

public interface IOptional<A> {
    bool HasValue { get; }
    A Value { get; }
}