javascript - How to incrementally build an array tree where each array can only have 1, 2, 4, 8, 16, or 32 items?

Question

At a high level, what I am trying to do is build up a "tree array" structure, exactly like in the tree array structure in this answer, with one additional constraint: every array can only be 1, 2, 4, 8, 16, or 32 items/arrays in length.

It acts like an array from the outside (has all the regular array methods), but it is constructed of a tree. With the added constraint that every node in the tree can only have 1, 2, 4, 8, 16, or 32 nodes (powers of 2). The nodes can be internal ("container") nodes, the base, or the leaves. In order to achieve these numbers 1, 2, 4, 8, 16 and 32, for items you add a null placeholder in the trailing spots after where you added an item, and for the containers (arrays), you simply add extra arrays to give you to that level.

I will demonstrate what the data structure looks like at different key points in its development now.

So here is how the first 32 items get laid out:

[]
[1]
[1,2]
[1,2,3,-]
[1,2,3,4]
[1,2,3,4,5,-,-,-]
[1,2,3,4,5,6,-,-]
[1,2,3,4,5,6,7,-]
[1,2,3,4,5,6,7,8]
[1,2,3,4,5,6,7,8,9,- ,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ]
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,- ,- ,- ,- ,- ,- ,- ,- ,- ,- ]
...
[1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,...,32]

Once it gets to 32, it nests, exactly like this question/answer. So then it starts to build like this:

[[1,2,...,32],[1]]
[[1,2,...,32],[1,2]]
[[1,2,...,32],[1,2,3,-]]
[[1,2,...,32],[1,2,3,4]]
[[1,2,...,32],[1,2,3,4,5,-,-,-]]
...
[[1,2,...,32],[1,2,3,4,5,...,32]]

Then the 3rd one at this nesting level creates an extra blank array:

[[1,2,...,32],[1,2,..,32],[1],[]]
[[1,2,...,32],[1,2,..,32],[1,2],[]]
[[1,2,...,32],[1,2,..,32],[1,2,3,-],[]]
[[1,2,...,32],[1,2,..,32],[1,2,3,4],[]]
[[1,2,...,32],[1,2,..,32],[1,2,3,4,5,-,-,-],[]]
...
[[1,2,...,32],[1,2,..,32],[1,2,3,4,5,...,32],[]]

The reason for the extra [] array at the end is so that the top-level array has 4 children. I guess it could also be null (-), either one would work, whatever is easier, so it could be this too.

[[1,2,...,32],[1,2,..,32],[1,2,3,4,5,...,32],-]

So now we fill up the second layer of arrays, all with 32 items each:

[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]]

What happens next is it nests again!

[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,3,-]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,3,4]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,3,4,5,-,-,-]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,3,4,5,...,32]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,...,32]],[[1]],[[]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,...,32]],[[1,2]],[[]]]
[[[1,2,...,32],[1,2,..,32],...,[1,2,...,32]],[[1,2,...,32]],[[1,2,3,-]],[[]]]
...

What this means is that every "object" in the array tree (every item, which can be anything, even arrays!) is at the same level in the tree (at the same depth), exactly like the linked simplified MVP question/answer.

I have tried to do it but I quickly get lost. I would love to see how this is done in an iterative fashion (i.e. instead of recursion), but recursion would be a nice touch too if you wanted to add it as well. (Some helpful methods can be found at the bottom of that gist too.)

NOTE: The numbers I used in the arrays are not what the actual values would be. The actual values will be any JavaScript objects (arrays, objects, numbers, strings, dates, etc.). I just used numbers to show the positions and how they relate to each other in a concise way. ??

It should work with a single method like in the linked question: tree.add(object), or tree.push(object), or push(tree, object), etc.

Also note, I am asking for this in JavaScript for simplicity's sake. I get that JavaScript arrays are dynamically sized, but pretend they are not. I am going to use this in a custom programming language which has fixed size arrays like C does, so I would like to know how it would work when you have to recreate the arrays as they are required to grow in size.

I modified the linked answer here to get pretty close to what I'm imagining, but still not there yet.

Answer 1

I went for the null option for internal levels as well, like you suggested:

I guess it could also be null (-), either one would work, whatever is easier, so it could be this too.

You also wrote:

every item, which can be anything, even arrays!

For your previous question I used an Array-check to detect whether an item in the tree was a leaf or not, but as that would not work here, I added a property in my Tree class that keeps track of the height of the tree.

As arrays will be padded with null values, JavaScript's length property will not give a clue about where to insert the next item. To avoid that the code would repeatedly have to iterate such arrays to find the index of the first null, I decided to keep track of the data sizes (so not counting the null padding) of the arrays that are on the path to the last inserted item. This way I have both the height of the tree (as length of this path), and the information where the next null is that can be used for storing the new item.

This path-based solution has also the advantage that you can actually store null items if you really wanted to. Although impossible to distinguish from the padding, you would notice the difference once you add another non-null value after that. The previously added null item will remain in tact.

Here is the implementation:

class Tree {
    constructor(maxPower=5) {
        this.root = null;
        this.maxSize = 2**maxPower; // default: 32
        // Path of rightmost data-branch from bottom to top:
        //   It will have {node, size} objects
        this.rightPath = []; 
    }
    add(value) {
        for (let level of this.rightPath) {
            let {node, size} = level;
            if (size < this.maxSize) {
                // Double array size when there is no more room:
                if (size === node.length) node.push(...Array(size).fill(null));
                node[size] = value; // This is the empty spot to use
                level.size++; // Update size on the path
                return;
            }
            // If we get here, there was no available spot at this level
            // Wrap the value so when it gets inserted at a higher level,
            //    the core value will still end up at the bottom level.
            value = [value];
            // Update path accordingly (for use in future `add` calls)
            level.node = value;
            level.size = 1;
        }
        // If we get here, there was no available spot in the tree: 
        //    add a level at the top
        this.root = this.root ? [this.root, value] : [value];
        // Update path accordingly
        this.rightPath.push({ node: this.root, size: this.root.length });
    }
}

// Demo
let tree = new Tree;
for (let i = 1; i <= 65; i++) {
    tree.add(i);
    console.log(JSON.stringify(tree.root));
}