CODEWITHSUNDEEP
java
abcdabcd987
abcdabcd987

Reputation: 2053

What's the better way to add additional information about an existing object?

For example, I have a Node class for binary tree.

public class Node {
    public Node lchild;
    public Node rchild; // public for convenience
}

And now, I have a processor that needs to record some additional information about Node instances and only use them privately. Let's say the number in the pre-order tree traverse.

I think one straight way to make it is to add a field in the class:

public class Node {
    public Node lchild;
    public Node rchild;
    public int no;   // the number in the pre-order tree traverse
}

However, I believe that is definitely a bad idea. So what I'm using now is: use a Map<Node, Integer>

public class MyProcessor {
    private Map<Node, Integer> no;
    public void process1(Node node) {
        int id = no.get(node); // or something like this
    }
}

Certainly, this can solve problem. But my concern is:

  1. Frequent access to a map seems less efficient? (compared to the add-field approach)
  2. If I need several more kinds of information, I need to make several more maps, which seems to be a nightmare.

So, is there a better way please? Thanks!

Upvotes: 2

Views: 99

Answers (4)

xiaofeng.li
xiaofeng.li

Reputation: 8587

For the sub classing approach, you should use "getter methods" for accessing child nodes, so that the subclass can override them.

public class Node {
    protected Node left;
    protected Node right;

    public Node(Node left, Node right) {
        this.left = left;
        this.right = right;
    }

    public Node getLeft() { return left; }
    public Node getRight() { return right; }
}

And override these in a subclass, lazily create the child nodes when needed.

public class DecoratedNode extends Node {
    private Node original;
    private int no = 0;

    public DecoratedNode(Node n) {
        super(null, null);
        original = n;
    }

    @Override
    public Node getLeft() {
        if (left == null && original.getLeft() != null) 
            left = new DecoratedNode(original.getLeft());
        return left; 
    }

    @Override
    public Node getRight() { 
        if (right == null && original.getRight() != null) 
            right = new DecoratedNode(original.getRight());
        return right; 
    }

    public int getNo() { return no; }
    public void setNo(int no) { this.no = no; }
}

Then pass new DecoratedNode(root) to the process method.

Upvotes: 0

Vincent Vandemeulebrouck
Vincent Vandemeulebrouck

Reputation: 61

The additional information is specific to one processor of Node hierarchy, so it should not leak into the Node (separation of concerns)

Potential solutions:

  1. Use a parallel tree structure for this processor

As the Node is a tree structure, using a parallel structure that is built while visiting the Node structures. This parallel item (ProcessedNode?) would hold the additional information, reference to the Node, and left/right ProcessedNode children.

This may be better in terms of memory and access (no Map overhead), but make the processor a bit more complex: it would visit ProcessedNode instead of Node. Instead of visiting the next Node, it would create a ProcessedNode for the next Node, and visit the ProcessedNode.

You can lazy-build the ProcessedNode, so the parallel tree is built as needed.

It is not practical if the Node tree may be mutated, and you need to keep the ProcessedNode information for more than the duration of one processing.

  1. Use a Map

Instead of having one map per additional information, you can gather all these in a class Details containing the additional information, and use a single Map

The advantage of this solution is simplicity to implement. Disadvantage is that if you keep the map, you need to maintain if a Node disappear.

The final choice depends on how long the additional details will be needed, if you only need to maintain the information for the duration of the processing, the map will be dropped at the end of the processing, so the cost of adding items to the map is not leveraged.

If creating a Map is practical, before optimizing with an alternate solution, you should measure what is the actual overhead: is the gain worth the effort?

Upvotes: 0

Gerald M&#252;cke
Gerald M&#252;cke

Reputation: 11132

It's a matter of separation of concerns. Is the information you'd like to add a concern of the Node or the processor of the tree.

I'd say, the following statements describe the situation

  • the tree has nodes (composition aggregation)
  • the node has nodes (aggregation)
  • the node has node info (aggregation)
  • the processor processes the tree ( dependency)

So I'd put or associate the info with the node. In order to have a certain degree of flexbility, you could have the info on an extension of Node 

class ExtNode extends Node {

    int no;

}

or a Decorator:

class NodeDecorator {

    Node node;
    int no;

    NodeDecorator(node){
        this.node = node;
    }
}

In case you go for the map, efficiency shouldn't be your concern at this phase. Access to maps is quite efficient. You can optimize later if needed.

If additional information gets added, you could define a new structure, let's say NodeInfo and put all the information in there and put it in the Map or to the Node instead of int.

For example

class NodeInfo {
    int no;
    String other;
}

Upvotes: 0

npinti
npinti

Reputation: 52185

The best solution would probably be to extend the Node object you have, this will allow you to leverage new functionality while at the same time not breaking existing code.

You could also couple this with the Decorator and Factory patterns to try and have a transparent and structured object creation process.

Upvotes: 2

Related Questions