Method Extensions

2010/12/24 · by · in Comp*, Ideas, Language

I’ve come across another programming language feature that I would like to have. The last one was a bit outlandish, and I’d really like to refine it a bit. Dress it up a little.

Supposing you were asked to perform the well known Dijkstra’s Algorithm. Someone hands you a graph of generic items, let’s call them Nodes, and you know that each Node has a List<Node*> of edges. So far, so good.

Now, Dijkstra’s Algorithm works pretty well if you are allowed to tag or mark the Nodes in some way. If you have control over the Node class, then you might be tempted to ‘gift’ the class with a member field to hold this tag. But, you should resist this temptation, because it’s not really appropriate.

It will pollute your class. You are increasing the size of each and every Node, regardless of wether it participates in Dijkstra’s Algorithm. The additional field, if not commented, might confuse you later. If you’re paranoid you might never touch it again; even after removing Dijkstra’s Algorithm from your codebase. Even if commented, you might later hijack the field for use in other algorithms for which marking or tagging is convenient. Cleverly using the same field for dual missions, and later confusing yourself or getting into an inconsistent state.

So, we don’t want to make an additional field. Fine, what other options are there?

We could subclass Node to make a MarkableNode. But, in the implementation given above, we see that Nodes point only to other Nodes. To really give a seamless touch to the algorithm, we’d have to make a complete copy of the graph we were given, out of the MarkableNodes.

Alternatively, We could write a wrapper class, MarkableNode that wraps a Node*. This will work generically, yet you have to write a ton of other features for equality tests, worry about creating two different MarkableNodes around the same Node*, etc. What a crapload of tedious busywork.

class MarkedNode
{
public:
    MarkedNode(Node *node)
        :m_node = node;
        ,m_mark = false; {
    }
 
    void mark() {
        m_mark = true;
    }
 
private:
    Node *m_node;
    bool m_mark;
}

How ’bout this last option. We could temporarily attach to Node* a method (and storage) for marking the nodes. This method would only exist in the scope that it’s needed, so it won’t pollute the Node class. It would behave like a subclass or a wrapper class, but will need to be syntactically lighter weight, and semantically the same as having a Node* except for the specific extensions for marking.

Class MarkedNode : extends Node*
{
    m_marked = false;
 
public:
    void mark() {
        m_marked = true;
    }
}

So, essentially we can call this method on any Node*, and we allow the compiler to figure out how it will map (1-to-1) each m_marked field to each Node*. We also let the compiler figure out how to mangle the mark() method. Doing the mapping of Node* to extended data will be tricky, especially if we want to clear out the data when a Node* is deleted.