4

I have a problem and I want to know what is the best way to solve it.

Problem:

I have a Binary Decision Tree. Each leaf node has an object (called Matrix) that stores some information and performs some calculations. At some point during execution, I want to ask Matrix if I should split the leaf node. If yes, I should create two children each has its own Matrix and I should delete the Matrix of current node (because it's no longer a leaf). There are two kinds of Matrices but all leaf nodes use the same kind.

interface Matrix {}
class MatrixA extends Matrix {}
class MatrixB extends Matrix {}

I have come up with different approaches to solve this but I don't know which one is better.

Design #1:

class Node {
    Node left, right;
    Matrix mat;
    MatrixFactory fact;
    Node(MatrixFactory fact) {
        this.fact = fact;
        this.mat = fact.newMatrix();
    }
    void split() {
        if (mat.isSplitNeeded()) {
            this.mat = null;
            this.left = Node(this.fact);
            this.right = Node(this.fact);
        }
    }
}

The problem is that, It feels like I'm violating Single Responsibility Principle, because the Node is responsible for the structure of tree, the matrix handling, and splitting.

Design #2:

class Node {
    Node left, right;
}
class NodeMatrixManager {
    Map<Node, Matrix> map;
    MatrixFactory fact;
    NodeMatrixManager(MatrixFactory fact) {
        this.fact = fact;
    }
    void split(Node node) {
        mat = this.map[node];
        if (mat.isSplitNeeded()) {
            node.left = Node();
            node.right = Node();
            this.map.remove(node);
            this.map.insert(new Pair(node.left, this.fact.newMatrix()));
            this.map.insert(new Pair(node.right, this.fact.newMatrix()));
        }
    }
}

Again I feel I'm violating Single Responsibility Principle, because NodeMatrixManager is both responsible for keeping track of Matrix-Node relationship, and also for splitting.

Design #3:

class Node {
    Node left, right;
}
class NodeMatrixManager {
    Map<Node, Matrix> map;
    Matrix getMat(Node node) {return this.map[node];}
    insert(Node node, Matrix mat) {this.map.insert(new Pair(node, mat));}
    remove(Node node) {this.map.remove(node);}
}
class Splitter {
    NodeMatrixManager manager;
    MatrixFactory fact;
    Splitter(NodeMatrixManager manager, MatrixFactory fact) {
        this.manager = manager;
        this.fact = fact;
    }
    void split(Node node) {
        mat = this.manager.getMat(node);
        if (mat.isSplitNeeded()) {
            node.left = Node();
            node.right = Node();
            this.manager.remove(node);
            this.manager.insert(node.left, this.fact.newMatrix());
            this.manager.insert(node.right, this.fact.newMatrix());
        }
    }
}

In this approach I feel that class NodeMatrixManager is unnecessary, because I separated Matrix from Node so that Node doesn't bear too much responsibility and now Splitter has all the responsibility. So why not just put Matrix back in the Node and avoid unnecessary mapping?

Design #4:

class Node {
    Node left, right;
    Matrix mat;
    Node(Matrix mat) {this.mat = mat;}
}
class Splitter {
    MatrixFactory fact;
    Splitter(MatrixFactory fact) {
        this.fact = fact;
    }
    void split(Node node) {
        if (node.mat.isSplitNeeded()) {
            node.mat = null;
            node.left = Node(this.fact.newMatrix());
            node.right = Node(this.fact.newMatrix());
        }
    }
}

My problem with this design is that one class (Splitter) is accessing and manipulating information stored in another class (Node). It doesn't feel correct. If I put splitting back in class Node, I'm back where I began.


So what is the best design approach? (sorry for the long question)

  • in your design, you don't transmit the old data of the matrix to the child matrix, or am I missing something ? – Walfrat Mar 24 '17 at 10:05
  • @Walfrat No, children have new matrices. Old matrix is no longer needed. – Mehran Mar 24 '17 at 10:18
  • 1
    What is troubling me more on your code is the following : void split() {if (mat.isSplitNeeded()) {}}. The fact tha you check in the splt method if it's needed or don't do anything feel like a code smell IMO. If the split method is called when it should not be called, I would rather have an IllegalStateException. Otherwse I think the solution 1 don't violate the SRP. If you define in the behaviour of your Node Object that he's able to split himself, then it's part of is responsability to handle it. – Walfrat Mar 24 '17 at 10:25
  • I would also go with the first solution - the logic of splitting the node belongs to the Node object itself, no need to complicate the design. – sventevit Mar 24 '17 at 11:07
  • @Mehran: I think you need to define "best". If "best" is "best for performance" I'd recommend focusing on data locality (and cache access patterns) and this is extremely different (and rarely compatible with) other definitions of "best" (like "easiest to maintain"). – Brendan Mar 24 '17 at 11:44
10

Most of your design decision seems to be centered around the Single Responsibility Principle. I'm going to make your design decision easier by clarifying that principle.

Single Responsibility doesn't mean "do only one thing." It means "have only one reason to change," which is a bit obtuse. Here's what that means.

Let's say you have a worker that is shift manager at a local fast-food restaurant. How many responsibilities does he have? More than one, you say? How could that be? His job is his job, not because of the laundry list of responsibilities he has, but because his job title effectively encompasses those responsibilities.

Would you hire more people because the shift manager has more than one responsibility? No, you wouldn't; you would expect him to satisfy all of his job responsibilities. Would you hire more people because he has too many responsibilities? Possibly. But the only way his fundamental responsibilities will change is if his job title changes. The shift manager doesn't generally flip burgers, because that's someone else's job.

If a worker should have only one reason to change (i.e. his job title), how does he change that? He changes jobs.

So what sort of restaurant do we have here? A Binary Decision Tree restaurant. How many workers do you need? What job titles are they going to have?

One more thing. The restaurant isn't going to be religious about those job titles. If the manager needs to sweep the floor, he'll sweep the floor.

Good luck.

  • 2
    I indeed was confusing "have one reason to change" with "do only one thing". Your answer clarified that confusion for me. Thank you. – Mehran Mar 24 '17 at 16:07

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.