Quad Tree Node ID Generator

QuatTreeId.js

/* [ NOTES ] ============================================================
BigInt has 64 bits, since its signed there is only 63 bits to work with.

First 5 bits are reserved to store the Level value, which results the max value of 31

63bits - 5bits = 58 bits for quadrant information

Each quadrant needs 2bits to store its information
So 58 / 2 = 29, which is the max level to generate ids from

Quadrants - ZigZag Pattern
A:00  C:01
B:10  D:11

If the First Bit is ON, its a LEFT Side, else Right Side
if the Second Bit is ON, Its a BOTTOM Side, else a TOP Side.
*/

const LVL_BLEN = 5n;
const LVL_MASK = 31n;

export default class QuadTreeId{
    static A = 0n;   // 00
    static B = 2n;   // 10
    static C = 1n;   // 01
    static D = 3n;   // 11

    static new( id=null, lvl=null, quad=null ){
        if( id == null || lvl == null || quad == null ) return 0n;

        let bLvl      = BigInt( lvl );                   
        const shift   = ( (bLvl-1n) * 2n ) + LVL_BLEN;      // How many bits to shift based on level
        const qId     = quad << shift;                      // Quad ID at Bit Level
        const mask    = ~( (3n << shift) + LVL_MASK );      // Create Mask to clear out lvl and quad of old ID : ex. 1111001100000
        const curLvl  = id & LVL_MASK;                      // Grab the first 5 Bits which defines the level

        if( curLvl > bLvl ) bLvl = curLvl;                  // Use the greater LVL value for the ID, Current or existing.

        return ( id & mask ) ^ bLvl ^ qId;                  // Rebuild ID with new level and Quadrant ID
    }

    static getLevel( id ){ return Number( id & LVL_MASK ); }

    static getPos( id, out=[0,0] ){
        const lvl   = id & LVL_MASK;                // Mask out the Level
        const shift = ( (lvl-1n) * 2n ) + LVL_BLEN; // How much to Shift Right
        const quad  = ( id >> shift ) & 3n;         // Mask out the First 2 bits after shift

        out[ 0 ]    = Number( quad & 1n );
        out[ 1 ]    = Number( quad & 2 ) * 0.5;
        return out;
    }

    static getInfo( id ){
        const lvl   = id & LVL_MASK;                // Mask out the Level
        const shift = ( (lvl-1n) * 2n ) + LVL_BLEN; // How much to Shift Right
        const quad  = ( id >> shift ) & 3n;         // Mask out the First 2 bits after shift

        let qrant;
        switch( quad ){
            case this.A : qrant = "A"; break;
            case this.B : qrant = "B"; break;
            case this.C : qrant = "C"; break;
            case this.D : qrant = "D"; break;
        }

        return {
            level    : Number(lvl),
            quad     : quad,
            pos      : [ Number(quad & 1n), Number( quad & 2n ) * 0.5 ],
            quadrant : qrant,
        };
    }

    static debug( id ){
        const lvl = ( id & LVL_MASK );
        console.log( "Max Level : ", lvl );

        // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        let i;
        let bits = "Bits : ";
        let end  = (lvl - 1n) * 2n + 7n;

        for( i=0n; i < end; i++ ){
            //bits += ((id >> i) & 1n) + (( (i & 1n) && i > 2n )?" ":"");
            bits += ((id >> i) & 1n);
            if( (i & 1n) === 0n && i > 3n ) bits += ' ';
        }

        console.log( bits.split('').reverse().join('') );

        // ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
        let v, q;
        for( i=0n; i < lvl; i++ ){
            //v = ( id >> ((i * 2n) + 4n) ) & 3n;

            v = ( id >> LVL_BLEN + (i * 2n)) & 3n;

            switch( v ){
                case this.A : q = "A-00"; break;
                case this.B : q = "B-10"; break;
                case this.C : q = "C-01"; break;
                case this.D : q = "D-11"; break;
                default: q = "X";   // error
            }

            console.log( "LVL:", i+1n, " : ", q);
        }
    }
}

ZTest,js

const root = QuadTreeId.new();
const n1_B = QuadTreeId.new( root, 1, QuadTreeId.B );
const n2_C = QuadTreeId.new( n1_B, 2, QuadTreeId.C );
const n3_D = QuadTreeId.new( n2_C, 3, QuadTreeId.D );
const n4_A = QuadTreeId.new( n3_D, 4, QuadTreeId.A );

// QuadTreeId.debug( n1_B );
// QuadTreeId.debug( n2_C );
// QuadTreeId.debug( n3_D );
QuadTreeId.debug( n4_A );

console.log( 'String', n4_A.toString() );
console.log( 'Lvl', QuadTreeId.getLevel( n4_A ) );
console.log( 'Info', QuadTreeId.getInfo( n4_A ) );