Local static class fields

[Bert]

On Tuesday, 13 August 2019 at 12:22:45 UTC, Simen Kjærås wrote:
> 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.
>

Generally no, I think that your solution is not great. There is 
no reason to contain a pointer in each node. I mentioned in the 
other reply that there might be better alternative, a hybrid.

Basically


class StateNode : Node

and then use a limited traversal. Replace every kth node with a 
StateNode and simply traverse up to it. One is guaranteed to find 
one within kN steps and on average half that. It also then 
reduces memory requires by kN.

This seems to be the best all around approach. It still requires 
some type of construction but this might be done behind the 
scenes by silently creating and removing StateNodes as necessary.

With only the root as a StateNode, i.e., your solution, the path 
length is the total depth. With each node a StateMode(other 
extreme) then the memory waste is the entire tree size * 
ptr.sizeof.

In this hybrid approach, one can limit both to reasonable levels. 
Each tree could be optimized to reduce overall cost. It should 
significantly reduce memory in a typical tree. One might not need 
to traverse to the root, but can traverse to a leaf or a 
neighbor, but I'm not sure if this would be worth it. This could, 
on average reduce the traversal cost even further.

In my use case the tree is fixed, but in others it may not be. 
I'm trying to find a good solution. This seems to be the best all 
around. I haven't thought about it too much in the general 
case(for tree operations) but with proper balancing it should be 
nearly ideal.

I'll probably have to do some testing to figure out what would be 
the proper way to distribute these "StateNodes" in the tree would 
be and what are the ramifications on tree operations. I imagine 
if they just point to the root and then have the root contain the 
state, it might remove some of the problems, but when merging 
tree's and such these notes would still have to be updated and 
all that.

What do you think? Seems good?