1

I'm trying to build an architecture in C#, and I can't figure out a way to accomplish the task. Basically, there's a set of classes A, B, C and D that inherit from I. Each of these classes has an operation Foo that operates on one of the other classes, and returns an object of type R:

class A : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
}
class B : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
}
class C : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
}
class D : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
}

This operation Foo is symmetric (i.e. a.Foo(b) == b.Foo(a), d.Foo(a) == a.Foo(d), etc.). (Of course, this means that we really only need to define Foo(A a) in A, Foo(A a) and Foo(B b) in B, and so on, but you get the idea).

If we introduce a new class E, it has to implement Foo for types A, B, C, D, and E.

class E : I
{
    public R Foo(A a);
    public R Foo(B b);
    public R Foo(C c);
    public R Foo(D d);
    public R Foo(E e);
}

Obviously we can't externally add an implementation for public R Foo(E e) in each of the classes A, B, C, and D (well, not without extension methods), but since Foo is symmetric, a.Foo(e) == e.Foo(a), so we only really need to implement Foo(A a) in E.

Now the part that makes this really difficult for me at least, is there's also a "viewer" object V that contains a list of I's. V has to be able to perform the Foo operation between two I's without knowing their actual types. V only knows that the operation Foo exists between two I's. Theoretically, this is what it would look like:

class V {
    public R Foo(I i1, I i2)
    {
        // Check if i1 has an implementation for Foo taking
        // the type of i2.
        if (!i1.HasFoo(i2.GetType()))
        {
            // Do the same for i2 on i1.
            if (!i2.HasFoo(i1.GetType()))
                return null;
            return i2.Foo(i1);
        }
        return i1.Foo(i2);
    }
}

Obviously this would never work, for the same reasons this doesn't work. I've thought about this for quite some time now, and I can't think of an architecture that satisfies these requirements in a clean way. I've thought up a number of convoluted methods that abuse generic types and strategy patterns and visitor patterns and the whole sh'bang, but nothing that isn't prone to bugs or overcomplicated.

How should I implement this, if it's even possible?

This is the actual, non-abstracted application. It's a collision detection engine, where the classes A, B, etc. are different geometries with fundamentally different properties (circle vs infinite line vs polygon, etc.). The different Foos are the different algorithms that test if two geometric shapes are colliding. V is an algorithmic container for a large number of these geometric objects (a quadtree or something).

  • Can you possibly refactor Foo so that it uses intermediates? You'd have three operations: The first, FooL returns an RL type. The second, FooR returns an RR type. Then a general Foo that takes an RL and an RR and returns an R. Each new type would only have to implement FooL and FooR, and V would just call Foo ( FooL ( i1 ), FooR ( i2 ) ). – Erik Eidt Jun 28 '15 at 18:16
  • @ErikEidt I updated the question to include some more specific details on the application. I don't know if your idea would work, because it would require FooL and FooR to return a common geometric format to test for intersections between, which simply isn't possible for all geometric objects. The algorithm for circle-to-circle collision detection is vastly different to the algorithm for infinite ray-to-concave polygon collision detection, for example. – user3002473 Jun 28 '15 at 18:24
  • Let's say we could figure out a common format that FooL and FooR could return that Foo could then use. Every different collision algorithm would have to be implemented in Foo, so introducing a new class E would require adding that new algorithm to Foo, which isn't feasible. I'm not sure what else you could do with FooL and FooR. It's a very clever idea, I just don't see how it could work with this application. – user3002473 Jun 28 '15 at 18:27
  • @user3002473 I remembered something and modified my answer to something that actually works now (I even tested it this time!) It's a slightly "clever" way to do double dispatch, and I generally don't like "clever" code, but it's such a simple, minimal method compared to the complexity of other solutions that I think it's worth considering – Ben Aaronson Jul 2 '15 at 11:49
1

It sounds like your method Foo should not exist in your I subclasses.

As you mentioned, with your suggested approach adding a new I subclass violates the Open/Closed principle.

Instead, try moving Foo to a new class responsible for the symmetrical operation

abstract class SymmetricalFoo<T,U>
    where T : I 
    where U : I
{
    public R Foo(T t, u u)
    {
        this.Bar(t, u);
    }
    public R Foo(U u, T u)
    {
        this.Bar(t, u);
    }
    protected abstract R Bar(T t, U u);
}

And implement a concrete SymmetricalFoo for every I subclass pair.

This way when you add a new I subclass you won't need to modify existing classes. You'll only need to create new SymmetricalFoos.

As for your V class. This goes against my general hatred of the pattern... but I think you need an Abstract Factory.

Pass two instances of I subclasses to the factory a get the appropriate SymmetricalFoo as a result.

I'll leave the implementation of that factory to you (because I really dislike writing them!), but it will probably involve making the generic SymmetricalFoo<T,U> class implement a non-generic ISymmetricalFoo interface.

  • So then the implementations of SymmetricalFoo would be passed into V? – user3002473 Jun 28 '15 at 18:32
  • 1
    Well, this is one of the few cases where an abstract factory would work. Create an abstract factory that takes as parameters two instances of I subclasses and returns the appropriate SymmetricalFoo. V would interact with that factory. I'll add this to the answer. – MetaFight Jun 28 '15 at 18:37
  • Wait, let's say I make some SymmetricalFoos for a new class E I'm introducing. How would the abstract factory know about it in the first place? As far as I can tell, the abstract factory would have to be a singleton, and the SymmetricFoo's would have to add themselves to the abstract factory's list of known implementations of Foo in a static constructor. – user3002473 Jun 28 '15 at 21:21
  • The abstract factory doesn't need to be a singleton. It just needs to know how to map the pair E,x to the appropriate SymmetricalFoo and how to construct it. The simplest way to implement that mapping is to hardcode it into the factory. Granted, it's not ideal. Every time you add a new I subclass you'll need to modify the factory... but that's still a whole lot better than having to modify all the existing I subclasses. – MetaFight Jun 28 '15 at 21:28
  • 1
    I don't have time to give a full answer now... but if you're building an API for others to extend then using MEF might help. Your users could register their SymmetricalFoos using the ExportAttribute and the abstract factory would pick them up dynamically. – MetaFight Jun 28 '15 at 21:34
4

What you encountered is called double dispatch and what you have implemented is some form of Visitor pattern. The problem you encountered is one of the limitations of Visitor pattern. You usually have to choose between inheritance and visitor. When you have one, it makes the other harder. C#'s type and method dispatch system is simply not powerful enough to support both at the same time.

The only possible solution is to give up on having compiler check if every pair of possibilities is implemented and just keep dictionary where the two types are key and operation is the value. (its the same as you are doing it in your own answer, but your solution "hides" this fact). The confidence, that all permutations are implemented can be regained if you write an automated test, that checks if all permutations have valid calculation.

And I would say that there is no need to bring generics into mix. You would still need to convert both values into object type before passing them into the double-dispatch routine.

2

Actually this can be relatively simply resolved with the C# trick of using dynamic to do double dispatch. You simply need a method on base class I like:

public R Foo(I i)
{
    return (i as dynamic).Foo(this as dynamic);
}

The viewer can call this, because it knows it has an instance of I. The trick here is that when you cast to dynamic, you always pick the appropriate overload for the runtime type of the object (see the above link if it's not clear what that means).


Note that this also solves your problem of adding new classes. Say you have A,B,C,D and you add E. E has an explicit Foo override for all the previous ones, but none of them have an explicit override for E.

Now you do:

I e == new E();
I a = new A();
a.Foo(e);

This will call E.Foo(A a). Alternatively, if you do:

e.Foo(a);

This will first call A.Foo(I i) (Since there's no A.Foo(E e)). This will then call E.Foo(A a), which is the same as above.


As usual with dynamic, the downsides are:

  • Loss of type safety
  • Performance

Because you're using it within such a specific scope, I'd say the first point is pretty much irrelevant here. It doesn't force you to use dynamic anywhere else.

How relevant performance is is up to you to find for your specific code. If these methods aren't called in a tight loop, it's unlikely to matter, and if you're not sure, you should profile.

Note also that if you call this for two classes where neither can convert to the other, you'll recurse infinitely and overflow the stack!

  • Doesn't this require I to implement Foo(A a), Foo(B b), and all the other implementations of Foo? Otherwise it would be a compile time error because I has no method Foo(E e) (for example)? – user3002473 Jun 28 '15 at 20:23
  • @user3002473 I've edited to explain that. Rememer I has a method for Foo(I i), so if it can't find a method for Foo(E e), it'll fall back to that one – Ben Aaronson Jun 28 '15 at 20:27
  • Ah I see, very clever! This is a very elusive problem; it seems as though every approach has some "slightly annoying thing" holding it back. – user3002473 Jun 28 '15 at 20:33
0

How should you implement it?

You should adopt some convention, like the class made last, gets to implement the behavior and the other one simply forwards the call. Ideally, you can implement them as static methods so that a method and its mirror live next to one another in code.

Yes, this means you have to modify the set when they're expanded. Annoying, but simple to do and unlikely to happen much.

C# can't really enforce symmetry like this easily. Your best bet is to just make the code do it and then punish programmers who break the rules.

  • Although it can't easily be enforced at compile time, using an abstract factory (to resolve the appropriate method from the class pairings) would allow you to enforce it at run time. – MetaFight Jun 28 '15 at 20:04
  • @metafight - I don't see how that gets you anything. Instead of adding new methods, you now get to add new objects and methods for all of the new classes. – Telastyn Jun 28 '15 at 20:15
  • I was mentioning using an abstract factory in the context of my answer. In that answer I recommended moving the symmetrical Foo method into separate classes (one for each I subclass pair) and using the factory to resolve, at runtime, which of those classes to use. The advantage being that when you add new I subclasses you don't need to modify existing ones. And, if a developer creates a new I subclass but forgets to create all the other classes for each new I,I pair, then the factory will throw an exception at run time. – MetaFight Jun 28 '15 at 20:39
  • this is all very abstract. Maybe it'll be easier to talk about this in chat. – MetaFight Jun 28 '15 at 20:41
-1

I just realized, C# has dynamic types!

interface I
{
    int Precedence { get; }
}

class A : I
{
    public int Precedence { get { return 0; } }
    public R Foo(A a) { return ...; }
}

class B : I
{
    public int Precedence { get { return 1; } }
    public R Foo(A a) { return ...; }
    public R Foo(B b) { return ...; }
}

class C : I
{
    public int Precedence { get { return 2; } }
    public R Foo(A a) { return ...; }
    public R Foo(B b) { return ...; }
    public R Foo(C c) { return ...; }
}

class D : I
{
    public int Precedence { get { return 3; } }
    public R Foo(A a) { return ...; }
    public R Foo(B b) { return ...; }
    public R Foo(C c) { return ...; }
    public R Foo(D d) { return ...; }
}

using Microsoft.CSharp.RuntimeBinder;
class V
{
    public R Foo(I i1, I i2)
    {
        try 
        {
            if (i1.Precedence >= i2.Precedence)
                return DynamicFoo(i1, i2);
            return DynamicFoo(i2, i1);
        }
        catch (RuntimeBinderException)
        {
            return null;
        }
    }

    private R DynamicFoo(dynamic a, dynamic b)
    {
        return a.Foo(b);
    }
}

Here we use the convention that any class with a precedence of n must implement Foo for all classes with precedence less than or equal to n.

The problems with this solution are that if you want to implement a new class E you have to know what the previous highest precedence value was (in this case 3), and the user has to understand the precedence convention in the first place. You could also argue that catching an exception is an inefficient method of detecting when no Foo exists, but that feels like premature optimization.

An example of implementing E:

class E : I
{
    public int Precedence { get { return 4; } }
    public R Foo(A a) { return ...; }
    public R Foo(B b) { return ...; }
    public R Foo(C c) { return ...; }
    public R Foo(D d) { return ...; }
    public R Foo(E e) { return ...; }
}
  • Would the downvoter care to elaborate? – user3002473 Jun 29 '15 at 11:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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