Cell ID generator fix
Generate unique cell IDs fix. Constraints:
- must be thread safe
- must be reproducible
Thread safe is given in any case, but the IDs are only reproducible if there are < 32^3 top level cells and the depth of the tree is <= 16.
We leave the first 15 bits of an unsigned long long for the top level cells, allowing for 32^3 unique top level cells. For every level of prodigy cells, we add three bits at the leftmost available position (i.e. increasing the value of the ID) based on the prodigy cell's position within the parent cell. Finally, add a leading 1 to mark that the cell ID is taken at that level and to make it unique.
Simplified Example:
- using 3 rightmost bits instead of 15 for top level cells in this example
- dots every three digits are included for improved readability
Depth Cell ID binary
-------------------------
0 000.000.000.001 [top level cell]
1 000.001.000.001
1 000.001.001.001
1 000.001.010.001
1 000.001.011.001
1 000.001.100.001
1 000.001.101.001
1 000.001.110.001
1 000.001.111.001
2 001.000.000.001
2 001.001.000.001
2 001.010.000.001
2 001.011.000.001
2 001.100.000.001
2 001.101.000.001
2 001.110.000.001
2 001.111.000.001
.
.
.
2 001.111.110.001
2 001.111.111.001
etc
Current WIP status because I'm waiting for some bigger tests to finish, but this should work fine.
Edited by Mladen Ivkovic