On Tuesday, 13 August 2019 at 08:41:02 UTC, Bert wrote:
On Tuesday, 13 August 2019 at 04:43:29 UTC, Paul Backus wrote:
It seems to me like the obvious solution is to use two different classes, one to store the global state, and one to store the individual objects in your structure. For example:

class Tree {
    State state;
    Node root;
}

class Node {
    Node[] children;
}

Yes, I forgot to mention this as a solution.

I was going to go in to more detail. This is not a great solution because it requires a base class simply to hold the "global" state and it requires nodes to have an accessor(they won't know which tree they come from).

What you're essentially looking at here is my solution 4):

class Node {
    Node parent;
    Node[] children;
    @property State state() {
        return parent.state;
    }
}

class Root : Node {
    State treeState;
    override @property State state() {
        return treeState;
    }
}

class State {}



What I was thinking though, with D's capabilities, if a constructor could somehow return a "Voldemort" type that makes it all work out.

e.g.,

class Tree {
    State state;
    Node root;
    alias root this;
}

then the constructor just returns tree which acts as an node.

It doesn't have to be a voldemort but it at least hides some of the details...

Ultimately it is not too different from using a dictionary though, effectively does the same thing.

Something like this may be possible, but it will still need to keep around a pointer to the context (likely the root), costing you the exact same as having a pointer to either the root or the state in each node:

class Root {
    State state;
    this() { state = new State(); }
    auto newNode() {
        class Node {
            State getState() { return state; }
        }
        return new Node();
    }
}

class State { }

unittest {
    auto root1 = new Root();
    auto node = root1.newNode();

    assert(node.getState() == root1.state);
// Note that Node keeps track of its context, thus taking up more space: assert(__traits(classInstanceSize, typeof(node)) > __traits(classInstanceSize, State));
}


There may be no way around such a problem in that these might be "optimal". Your's, which added parent in node, might be better since a dictionary doesn't have to be directly maintained.

Also, if space is a concern, the dictionary is actually worse than adding a pointer to the state in each node, as the internal book-keeping of the dictionary is more than one pointer's worth per entry (at the very least it needs to keep both the hash of the Node and the pointer to the state).


I'd like to get away from actually having a different "root" type though. Mainly because it reduces uniformity and complicates the design I already have. If I could hide all these things and it is not too complicated then it would work better for me.

The solution of having a Root class that derives from Node causes complications in three situations: When you create a new tree, when you move a subtree to become a new tree, and when you move a tree to become a subtree. The last two may or may not actually occur in your code, but without knowing more, I have no idea if that's the case. I'm fairly certain you will at some point be creating new trees, though. If the creation of new trees is confined to one or two functions while the creation of new nodes is widespread, this special-casing of roots should be easily manageable.

However, since you specifically mention in this post that Paul 'added parent in node', you should definitely go with a pointer to the state in the Node, as per my earlier post. It's faster, you pay the memory cost anyway, and it's easy for maintainers (that's you in 6 months cursing your young-and-careless self) to understand what's going on.

Actually, there's one complication with having a pointer to the state in each node that we haven't mentioned: is the state often replaced wholesale? That is, not just its contents changed, but can the state of a tree suddenly point to a wholly different instance of the same class? If each node holds a pointer to it, then this operation is costly. However, this is generally easy to fix/avoid by a) favor mutation over reassignment, or b) another layer of indirection.

--
  Simen

Reply via email to