compareCurves

.block

license: mit

README.md

Comparing Morton and Hilbert curves

This is a first step to a visual and numeric comparison of Morton and Hilbert curves, in the context of geocode systems. Building with blockbuilder.org.

Step1

Was only a test of the D3js animations, using vasturiano/d3-morton-order and vasturiano/d3-hilbert libraries. See at bl.ocks and at gist.github.

Step2 - compare labels

This gist is a first complete grid with on-mouse-over interface.

curves-demo2.js

/**
 * Renderizing with Grid and curves (Hilbert and Morton) of external libs.
 * It is small, it is not a module. See https://stackoverflow.com/q/57592962/287948
 *
 * FROM https://github.com/osm-codes/site
 * DEMO at http://osm.codes/_foundations/curves2.htm
 * LICENCE MIT. (c) ppkrauss
 */

// falta algoritmo que retorna o código XY da vizinhança-8, ou retorna cellID. No morton temos, no Hilbert precisa pesquisar.
// mas já HILBERT devem ter definido algoritmo que faz isso rápida

// BUG: arrumar problema do scroll que já estava arrumado... comparar com t0-Hilbert.
// NEW ISSUE: revisar d3Digest(animacao) para mostrem apenas os vertices, destacando os centros de célula e mantendo a curva de fundo.
// NEW ISSUE: grade embaixo para mostrar IDs (ou sufixos de ID) das células e configuração colorida das vizinhanas conforme escolhas.
//    A célula destacada abaixo precisa ser gêmea do on-mouse-over.
// NEW ISSUE : on-click manter célula em cor destacadada de memória da grade (dataset do node).


////////////// non-exported components of this module.

function adTag(s,tag="code") { return `<${tag}>${s}</${tag}>`; }


function baseItens(sbi_id) {
  // Here define the presentation order of bases.
  let crvID   = sbi_id.val // or int
  var crvID4  = sbi_id.toString('4h');  // parseInt(crvID).toString(4).padStart(globOrder,'0');
  var crvID16 = sbi_id.toString('16h'); // parseInt(crvID).toString(16).padStart(globOrder,'0');
  var crvID32 = sbi_id.toString('32pt');  // parseInt(crvID).toString(32).padStart(globOrder/2,'0');
  let msgb32 = (globOrder_exact % 2.5)? '': `<hr/>base32nvu: ${adTag(crvID32)}`;
  let msg;
  if (globOrder_exact>2) msg = `base16h: ${adTag(crvID16)}${msgb32}<hr/>base4: ${adTag(crvID4)}`;
  else msg = `base4h: ${adTag(crvID4)}<hr/>base16h: ${adTag(crvID16)}`;
  return msg + `<br/>decimal: ${adTag(crvID)}`;
}


class Demo {  // usada apenas para extends

  constructor(domRef_id='hilbert-chart', reftab='reftab') {
    this.domRef_id = domRef_id;
    var theChart   = '#'+ this.domRef_id +' svg.theChart';
    var refWidth = parseInt( document.getElementById(reftab).getBoundingClientRect().width/2.0 );
    this.canvasWidth = Math.min(window.innerWidth, refWidth);

    this.curve = null;  // or param curveMethods;
    this.svg   = d3.select(theChart);
    this.XGrid = new Grid(null, globOrder, domRef_id, this.canvasWidth);
    this.domGrid_notFirst = false;
    this.domGrid = this.XGrid.build(this.svg, globOrder, true); // first
	// aqui pintar
    this.init();
  }
  preDigest()  {
	d3.select('#'+ this.domRef_id +' span.numCells').text(4**globOrder_exact);
 	if (this.domGrid_notFirst) {
    		this.XGrid.build(this.domGrid, globOrder, false);
	}
	this.domGrid_notFirst = true;
  }

  d3Digest() {}
  init0() {}

  init() {
        this.init0();

        this.svg.attr("width", this.canvasWidth).attr("height", this.canvasWidth);

        var myGrid = this.XGrid; // or this.domGrid
	var myDomGrid = this.domGrid;
        var canvas = this.svg.append('g');
        canvas.append('path').attr('class', 'skeleton');
        canvas.append('path');

        // Canvas zoom/pan
        this.svg.call(d3.zoom()
            .translateExtent([[0, 0], [this.canvasWidth, this.canvasWidth]])
            .scaleExtent([1, Infinity])
            .on("zoom", function() {
		if (xzoomNode.value==1) {
			canvas.attr("transform", d3.event.transform);
			myDomGrid.attr("transform", d3.event.transform);
		}
            })
        );

        // Value Tooltip
	var domRef = d3.select('#'+ this.domRef_id);
        var valTooltip = domRef.select('div.theChartTooltip');
	var sbi = new SizedBigInt();
	var lastCellPos = [null,null];
	var mySVG   = this.svg;
	var myCurve = this.curve;
	var myThis  = this;
        this.svg
          .on('mouseover', function() {
		valTooltip.style("display", "inline");
	  })
	  .on('mouseout', function() {
		valTooltip.style("display", "none");
		if (lastCellPos[0]!==null) {
			mySVG.select(`rect.xy${lastCellPos[0]}-${lastCellPos[1]}`).style("fill", '#FFF'); //lastCellPos[2]
			if (globOrder_prevHalf)
				mySVG.select(`rect.xy${lastCellPos[3]}-${lastCellPos[4]}`).style("fill", '#FFF'); // lastCellPos[2]
		}
		lastCellPos = [null,null];
	  })
          .on('mousemove', function () {
                var coords = d3.mouse(canvas.node());
		var crvID0 = myCurve.getValAtXY(coords[0], coords[1]); // curve ID, concete
		var grd_IJ0  = myGrid.getValAtXY(coords[0], coords[1]);
		let crvID=crvID0; // on half is abstract
		var crvID_i0=null; // concrete
		var crvID_i1=null; // concrete
		let crvID_max = 4**globOrder_exact -1;
		if (globOrder_prevHalf)  {
			crvID = crvID0>>1; // ID na curva Half, abstraida.
			crvID_i0 = crvID<<1;
			crvID_i1 = crvID_i0+1; // na curva e grade concretas.
			if (crvID0 != crvID_i0) {
				grd_IJ0 = myThis.getIjAtVal(crvID_i0)
				crvID0 = crvID_i0;
			}
		}
		let bits = crvID_max.toString(2).length;
		var sbi_id = sbi.fromInt( crvID, bits);
    var msg = baseItens(sbi_id);
    valTooltip.html(msg)
        .style('left', d3.event.pageX+'px')
        .style('top', d3.event.pageY+'px');
		if (grd_IJ0[0]!==lastCellPos[0] || grd_IJ0[1]!==lastCellPos[1]) {
			var rclass = `rect.xy${grd_IJ0[0]}-${grd_IJ0[1]}`;
			var domCell = mySVG.select(rclass);
			grd_IJ0.push( domCell.style("fill") ); // save origibal color
			if (globOrder_prevHalf)  {
				let color = "#6D6";
				domCell.style("fill", color);
				let grdID1 = myThis.getIjAtVal(crvID_i1)
				let rclass1 = `rect.xy${grdID1[0]}-${grdID1[1]}`;
				let domCell1 = mySVG.select(rclass1);
				domCell1.style("fill", color);
				grd_IJ0.push(grdID1[0],grdID1[1]); // save sister-cell coordinates
			} else domCell.style("fill", "#D55"); // it is possible to select by postion? seems not, so use DOM.
			if (lastCellPos[0]!==null) {
				mySVG.select(`rect.xy${lastCellPos[0]}-${lastCellPos[1]}`).style("fill",'#FFF');
				if (globOrder_prevHalf)
					mySVG.select(`rect.xy${lastCellPos[3]}-${lastCellPos[4]}`).style("fill",'#FFF');
			}
			lastCellPos = grd_IJ0;
		}
           });

        this.preDigest();
        this.d3Digest();
    } // \init()

  // IJ is admentional (unitary vectors or grid position), I and J are integers; XY is "metric" (spatial coordinate), X and Y are float.
  /**
   * Returns cell coordinates XY from cell ID. Non-used.
   * @param d: distance (Cell ID).
   */
  getXyAtVal(d) { return null;}

  /**
   * Returns cell coordinates IJ from cell ID. Used.
   * @param d: distance (Cell ID).
   */
  getIjAtVal(d) { return null;}

} // \class


/////////////////////////////



class HilbertDemo extends Demo {

   constructor(domRef_id='hilbert-chart', reftab='reftab') {
	super(domRef_id, reftab);
   }

   init0() {
        this.curve = d3.hilbert()  // see importers
            .order(globOrder)
            .canvasWidth(this.canvasWidth)
            .simplifyCurves(false);
   }

  /**
   * Returns IJ from cell ID.
   * @param d: distance (cell ID).
   */
  getIjAtVal(d) {
    let n = 2**globOrder; // sqrt of num cells (square side size)
    var rx, ry, t = d,
        xy = [0, 0];

    for (var s = 1; s < n; s *= 2) {
        rx = 1 & (t / 2);
        ry = 1 & (t ^ rx);
        rot(s, xy, rx, ry); // local func

        xy[0] += (s * rx);
        xy[1] += (s * ry);
        t /= 4;
    }
    return xy;

    function rot(n, xy, rx, ry) {
    // rotate/flip a quadrant appropriately
	    if (ry == 0) {
		if (rx == 1) {
		    xy[0] = (n - 1 - xy[0]);
		    xy[1] = (n - 1 - xy[1]);
		}
		xy.push(xy.shift()); //Swap
	    }
    }
  } // \method getIjAtVal

  d3Digest() {  // redo from here on globOrder-change, after init().
        var curveData = {
            start: 0,
            length: Math.pow(4, globOrder)
        };
        this.curve.order(globOrder).layout(curveData); // recorrencia

        this.svg.selectAll('path')
            .datum(curveData)
            .attr('d', function(d) { return getHilbertPath(d.pathVertices); })
            .attr('transform', function(d) {
                return 'scale('+ d.cellWidth + ') '
                    + 'translate(' + (d.startCell[0] +.5) + ',' + (d.startCell[1] +.5) + ')';
            });

        this.svg.select('path:not(.skeleton)')
            .transition().duration(globOrder * 1000).ease(d3.easePoly)
            .attrTween('stroke-dasharray', tweenDash);

        function getHilbertPath(vertices) {
            var path = 'M0 0L0 0';

            vertices.forEach(function(vert) {
                switch(vert) {
                    case 'U': path += 'v-1'; break;
                    case 'D': path += 'v1'; break;
                    case 'L': path += 'h-1'; break;
                    case 'R': path += 'h1'; break;
                }
            });
            return path;
        }

        function tweenDash() {
            var l = this.getTotalLength(),
                i = d3.interpolateString("0," + l, l + "," + l);
            return function(t) { return i(t); };
        }
    }
} // \class HilbertDemo


class MortonDemo extends Demo {

   constructor(domRef_id='morton-chart', reftab='reftab') {
	super(domRef_id, reftab);
   }

   init0() {
        this.curve = d3.zOrder()
            .order(globOrder)
            .canvasWidth(this.canvasWidth)
            .simplifyCurves(false);
   }


  getIjAtVal(d) {
    return [
        deinterleave(d),
        deinterleave(d >> 1)
    ];
    function deinterleave(x) {
        x = x & 0x55555555;
        x = (x | (x >> 1)) & 0x33333333;
        x = (x | (x >> 2)) & 0x0F0F0F0F;
        x = (x | (x >> 4)) & 0x00FF00FF;
        x = (x | (x >> 8)) & 0x0000FFFF;
        return x;
    }
  } // \method

  d3Digest() {  // redo from here on globOrder-change, after init().
        var curveData = {
            start: 0,
            length: Math.pow(4, globOrder)
        };
        this.curve.order(globOrder).layout(curveData);
        this.svg.selectAll('path')
            .datum(curveData)
            .attr('d', function(d) { return getZOrderPath(d.pathVertices); })
            .attr('transform', function(d) {
                return 'scale('+ d.cellWidth + ') '
                    + 'translate(' + (d.pathVertices[0][0] +.5) + ',' + (d.pathVertices[0][1] +.5) + ')';
            })
	;
        this.svg.select('path:not(.skeleton)')
            .transition().duration(globOrder * 1000).ease(d3.easePoly)
            .attrTween('stroke-dasharray', tweenDash)
	;

        function getZOrderPath(vertices) {
            var path = 'M0 0L0 0';
            vertices.forEach(function(vert) {
                path += 'L' + vert.join(',');
            });
            return path;
        }

        function tweenDash() {
            var l = this.getTotalLength(),
                i = d3.interpolateString("0," + l, l + "," + l);
            return function(t) { return i(t); };
        }
    } // \d3Digest

} // \class MortonDemo

curves-grid.js

class Grid {

  constructor(D3_svg, globOrder, grdID, frame_width, firstBuild=true, line_width=2) {
      this.restart(grdID, frame_width,line_width);
      if (D3_svg && globOrder)
	this.build(D3_svg, globOrder, firstBuild, line_width);
  }

  restart(grdID, frame_width,line_width) {
      this.myID         = grdID       || "noID";
      this.frame_width  = frame_width || 300; // in pixels when not defined
      this.line_width   = line_width  || 2;   // of vertical border lines in the grid layout

      this.frame_width_real = this.frame_width-this.line_width; // estimatives here.
  	// or, perhaps, buildData() need to calculate round(x) accumulation error as line_width
      this.cell_width   = null;
      this.cells_perRow = null;
      this.cell_height  = null;
      this.globOrder    = null;
      this.cell_area    = null;  // important on degenerated cells
      this.cell_frac_area = null;
  }

  buildData(globOrder=2, xpos = 1, ypos = 1) {
  	//starting xpos and ypos at 1 so the stroke will show when we make the grid below
	//  need also calculate cell_area, cell_width, cell_height .. cell_int_index e cell_base_code vem depois. Base code é hierarquico.
  	this.globOrder = globOrder; // grid refinement level
  	var data_body = new Array();


  	var iniclick = 0;
// revisar como fica no this.globOrder fracionario. 4^gFrac = 4^(g/2); raiz(4^gFrac) = raiz(4^(g/2)) = 2^(g/2)
	this.cells_total  = Math.pow(4,this.globOrder); // 4^g is total cells in square grid; 4 is the aperture (factor of partition).
  	this.cells_perRow = Math.pow(2,this.globOrder); // sqrt(4^g) = ((2^2)^g)^0.5 = (2^(2*0.5))^g = 2^g

  	var rows=this.cells_perRow;
  	var cols=this.cells_perRow;  // square .. can be rectangular?
  	this.cell_width = this.frame_width_real/rows;
  	this.cell_height = this.frame_width_real/cols;
	this.cell_area = this.cell_width*this.cell_area;
	this.cell_frac_area = 1/(rows*cols);


  	// iterate for rows
  	for (var row = 0; row < rows; row++) {
  		data_body.push( new Array() );

  		// iterate for cells/columns inside rows
  		for (var column = 0; column < cols; column++) {
  			data_body[row].push({
  				x: xpos,
  				y: ypos,
  				idref: `${column}-${row}`,
  				width: this.cell_width, // in pixels
  				height: this.cell_height,
  				click: iniclick
  			})
  			// increment the x position. I.e. move it over by 50 (cell_width variable)
  			xpos += this.cell_width;
  		}
  		// reset the x position after a row is complete
  		xpos = 1;
  		// increment the y position for the next row. Move it down 50 (cell_height variable)
  		ypos += this.cell_height;
  	}
  	return data_body; // temporary, is not to this.body
  }

  getValAtXY(xpos,ypos) {
  	return [parseInt(xpos/this.cell_width), parseInt(ypos/this.cell_width)];
  }


  build(D3_svg, globOrder, firstBuild=true, line_width=2) {
  	var gdt = this.buildData(globOrder);

  	if (globOrder>5) return; //preserving last grid and not building a new one
  	this.globOrder = globOrder;
  	var  grid;
  	if (firstBuild) {
  		grid = D3_svg.append("g");
  		grid.attr("class", "the_grid grdID-"+this.grdID);
  	} else {
  		grid = D3_svg;
  		//bug not removed D3_svg.select('g.the_grid').remove();
  		D3_svg.selectAll("*").remove(); // remove elements, preserve attributes
  	}

  	//grid.attr("data-conf", JSON.stringify(gdt.conf) ); // conferir se retorna JSON, senao fazer um a um.
  	// ops, nao parece ter em browser velho, https://developer.mozilla.org/en-US/docs/Web/SVG/Attribute/data-*#Browser_compatibility

  	var row = grid.selectAll(".row")
  		.data(gdt)
  		.enter().append("g")
  		//.attr("opacity", "0.3") //=1.0 it is on background
  		.attr("class", "row");

  	var column = row.selectAll(".square")
  		.data(function(d) { return d; })
  		.enter().append("rect")
  		.attr("class",function(d) { return `square xy${d.idref}`; })
  		.attr("x", function(d) { return d.x; })
  		.attr("y", function(d) { return d.y; })
  		.attr("width",  function(d) { return d.width; })
  		.attr("height", function(d) { return d.height; })
  		.style("fill", "#fff")
  		.style("stroke", "#F00");

  	return grid;
  } // \build

} // \class


// to extend D3,  d3.selection.prototype.layout = function() { ... code here ...}

index.html

<!DOCTYPE html>
<html>

<head>
   <meta charset="utf-8"/>
   <meta name="viewport" content="width=1000">
   <title>Sp-filling curves, compare 1</title>

    <script src="https://d3js.org/d3.v5.min.js"></script>
    <script src="https://unpkg.com/d3-morton"></script>
    <script src="https://unpkg.com/d3-hilbert"></script>

    <script src="./SizedBigInt.js"></script>
    <script src="./curves-demo2.js"></script>
    <script src="./curves-grid.js"></script>

<style>
	body {
	    text-align: center;
	}
	table {
	  padding:10px;
	  border-bottom: 1px solid #ddd;
	  border-top: 1px solid #ddd;
	}

        #chartsContainer svg.theChart  {
            margin: 10px;
        }

	#chartsContainer svg.theChart path {
            fill: none;
            stroke: #3A5894;
            stroke-width: 0.25;
            stroke-linecap: square;
        }

        #chartsContainer svg.theChart path.skeleton {
            stroke: #DDD;
            stroke-width: 0.1;
        }

        #chartsContainer div.theChartTooltip {
            display: none;
            position: absolute;
            margin-top: 22px;
            margin-left: -1px;
            padding: 5px;
            border-radius: 3px;
            font: 16px sans-serif;
            color: #eee;
            background: rgba(0,0,140,0.9);
            text-align: center;
            pointer-events: none;
        }

        #chartsContainer div.theChartTooltip code,
	#chartsContainer span.numCells {
	    font-weight: bold;
        }
        #chartsContainer div.theChartTooltip code:first-child {
            font-size: 150%;
        }
</style>

<script>
var globOrder_exact = 3; // change selected option
var crvID0_showDecimal = false;

var xzoomNode;
//var xbaseNode;
let md,hd;
var globOrder = Math.ceil(globOrder_exact);
var globOrder_prevHalf = (globOrder != globOrder_exact);

function changeOrder(v) {
	globOrder_exact = v
	globOrder = Math.ceil(v);
	globOrder_prevHalf = (globOrder!=v);

	md.preDigest(); md.d3Digest();
	hd.preDigest(); hd.d3Digest();
}

function redoOrderOptions(mode='all',max=9) {
	let modeAll = (mode=='all');
	let modeInt = (mode=='int');
	let opts = [...Array(modeAll? max: Math.ceil(max/2)).keys()]
		.map(x => modeAll? (1 + x/2): (
			modeInt? parseInt(1+x): (0.5+x)
		));
	document.getElementById('xvalue').innerHTML = opts
		.map(x => `<option${(x==globOrder_exact)? ' selected':''}>${x}</option>`)
		.join()
	;
}

function changeZoom(obj) {
 let v = obj.value;
 if (v<0) {
   alert("em construção:\naqui deveria fazer reset do zoom");
   obj.value = (v==-1)? 1: 0;
 }
}

function setFormOption(domId,val) {
	var sel = document.getElementById(domId),
	    opts = sel.options;
	for (var i = 0; i < opts.length; i++)  if (opts[i].label == val)
	      sel.selectedIndex = i;
}

function ONLOAD() {
  // Inits, interface:
  redoOrderOptions('all');
  document.getElementById("form1").reset();// reset selected options of page history.
  setFormOption('xvalue',globOrder_exact);
  xzoomNode = document.getElementById('xzoom');
  //xbaseNode = document.getElementById('xbase');

  // Curves:
  hd = new HilbertDemo('hilbert-chart', 'chartsContainer');  // from curves-demo.js
  md = new MortonDemo('morton-chart', 'chartsContainer');
  const canvasWidth_min = 320;
  if (hd.canvasWidth< canvasWidth_min) {
      let perc = Math.round( 100.0*(canvasWidth_min-hd.canvasWidth)/canvasWidth_min )
      alert(`This visualization not works with small screens.\nPlease use a screen ${perc}% bigger.`);
  }
} // \ONLOAD
////////////
</script>
</head>

<body onload="ONLOAD()">
<form id="form1">
<b>Level</b> <i>L</i> of <span style="color:red">grid</span> refinement = <a href="https://en.wikipedia.org/wiki/Space-filling_curve">Space-filling <span style="color:blue">curve</span></a>  <b>order</b>:
	<select id="xvalue" onchange="changeOrder(this.value)"></select>
  <select id="xopts" onchange="	redoOrderOptions(this.value)">
    <option value="all">all L</option>
    <option value="int">L int</option>
    <option value="half">half L</option>
</select>

<br/>Zoom/pan:
	<select id="xzoom" onchange="changeZoom(this)">
		<option value="1" selected>Enable
		<option value="0">Disable<!--
		<option value="-1">RESET and Enable
		<option value="-2">RESET and Disable -->
	</select>
&nbsp; &nbsp; &nbsp;
On mouse-over: usual base10 and <a href="https://en.wikipedia.org/wiki/base32" target="_blank">base32</a>; hierarchical <a href="http://osm.codes/_foundations/art1.pdf" target="_blank">base4h and base16h described here</a>.

	<br/>&nbsp;<br/>
</form>

<table id="chartsContainer" border="0" width="85%" align="center">
	<tr>
	 <td id="morton-chart"><a href="https://en.wikipedia.org/wiki/Z-order_curve">MORTON CURVE</a>
		in a grid of <span class="numCells"></span> cells<br/>
		<svg class="theChart"></svg>
		<div class="theChartTooltip"></div>
	 </td>
	 <td id="hilbert-chart"><a href="https://en.wikipedia.org/wiki/Hilbert_curve">HILBERT CURVE</a>
		in a grid of <span class="numCells"></span> cells<br/>
		<svg class="theChart"></svg>
		<div class="theChartTooltip"></div>
	 </td>
	</tr>
</table>


</body>
</html>

SizedBigInt.js

/**
 * Sized BigInt's (SizedBigInt) are arbitrary-precision integers with defined number of bits.
 * Each instance is a pair (size,number). Input and output accepts many optional representations.
 *
 * License CC0   https://creativecommons.org/publicdomain/zero/1.0
 * Original (C) 2019 by ppkrauss, source at https://github.com/ppKrauss/SizedBigInt
 */

// rever uso do >>> para inteiros 32 bits sem sinal https://stackoverflow.com/a/16155417/287948

class SizedBigInt {

  constructor(val,radix,bits,maxBits=null) {
    SizedBigInt.kxRefresh_defaults(); // global cache once.
    let t = typeof val;
    if (val && t=='object') { // not-null object
       if (val instanceof SizedBigInt)
        [val,radix,bits,maxBits]=[val.val,null,val.bits,null]; // clone()
       else if (val instanceof Array)
        [val,radix,bits,maxBits]=val;
       else ({val,radix,bits,maxBits} = val);
       t = typeof val
    }
    // set to default values when 0, null or undefined:
    if (t=='string') {
      if (!radix) radix = 4;
      if (bits) throw new Error("Invalid input bits for string");
      this.fromString(val, radix, maxBits)
    } else // bigint, number or null
      this.fromInt(val, bits, maxBits)
  }

  /**
   * Internal class-level cache-builder for Base4h and Base16ph complete translations.
   * and generates all other kx_baseLabel global defaults. Singleton Design Pattern.
   */
  static kxRefresh_defaults() {
   // each standard alphabet as key in the translator.
   if (!SizedBigInt.kx_tr) {
     SizedBigInt.kx_tr={};
     SizedBigInt.kx_baseLabel = {
       "2":   { base:2, alphabet:"01", isDefault:true, ref:"ECMA-262" }
       ,"4h": {
         base:4, isDefault:true,
         useHalfDigit:true,
         alphabet:"0123GH", case:"upper",
         regex:'^([0123]*)([GH])?$',
         ref:"SizedBigInt"
         }
       ,"16h": {
         base:16, isDefault:true,
         useHalfDigit:true,
         alphabet:"0123456789abcdefGHIJKLMNOPQRST",
         regex:'^([0-9a-f]*)([G-T])?$',
         ref:"SizedBigInt"
       }
       ,"4js":   { alphabet:"0123", ref:"ECMA-262" }
       ,"8js":   { alphabet:"01234567", isDefault:true, ref:"ECMA-262" }
       ,"16js":  { alphabet:"0123456789abcdef", ref:"ECMA-262" } // RFC 4648 sec 8 is upper
       ,"32hex": { alphabet:"0123456789abcdefghijklmnopqrstuv", isDefault:true, ref:"RFC 4648 sec. 7" }
       ,"32pt":  { alphabet:"0123456789BCDFGHJKLMNPQRSTUVWXYZ", ref:"Portuguese encodings" }
       ,"32rfc": { alphabet:"ABCDEFGHIJKLMNOPQRSTUVWXYZ234567", ref:"RFC 4648 sec. 6" }
       ,"32ghs": { alphabet:"0123456789bcdefghjkmnpqrstuvwxyz", ref:"Geohash, classical of 2008" }
       ,"64url": {
         alphabet:"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789-_",
         isDefault:true, ref:"RFC 4648 sec. 5"
       }
     };
     SizedBigInt.kx_baseLabel_setRules();

     SizedBigInt.kx_tr['4h-to-2'] = {
       "G":"0","H":"1", // HalfDigit to binary
       "0":"00", "1":"01", "2":"10", "3":"11", // standard base4 to binary
     };
     SizedBigInt.kx_tr['2-to-4h']  = SizedBigInt.objSwap(SizedBigInt.kx_tr['4h-to-2']);
     SizedBigInt.kx_trConfig('16js'); // '16js-to-2' and '2-to-16js'
     SizedBigInt.kx_tr['16h-to-2'] = Object.assign(
         SizedBigInt.kx_tr['16js-to-2'],
         {
           "G":"0","H":"1", // HalfDigit to binary
           "I":"00","J":"01","K":"10","L":"11",  // 2-bit-HalfDigits to binary
           "M":"000","N":"001","O":"010","P":"011","Q":"100","R":"101","S":"110","T":"111" // 3-bit-HalfDigits
         }
     );
     SizedBigInt.kx_tr['2-to-16h'] = SizedBigInt.objSwap(SizedBigInt.kx_tr['16h-to-2']);
     // any other kx_tr[] must to use the fabric kx_trConfig().
   } // \if
  }

  clone() {
    return new SizedBigInt(this.val, null, this.bits)
  }

  static createMany(a) { // mulple constructor
    let t = typeof a;
    // if (a instanceof Set) ... if (WeakMap) ...
    if (t=='array' || a instanceof Array)
      return a.map( x => new SizedBigInt(x) );
    else if (t=='object')
      return Object.assign(...Object.entries(a).map(
        ([k, v]) => ({ [k]: new SizedBigInt(v) })
      ));
    else throw new Error("Invalid input type, use Array or Object");
  }

  // // //
  // Input methods:

  fromNull() { this.val=null; this.bits=0; return this; }

  fromBinaryString(strval, maxBits=null) {
    if (!strval) return this.fromNull();
    this.bits = strval.length
    if (maxBits && this.bits>maxBits)
      throw new Error(`bit-length ${this.bits} exceeded the limit ${maxBits}`);
    this.val = BigInt("0b"+strval)
    return this
  }

  /**
   * Input from string.
   * @param strval string with valid representation for radix.
   * @param radix the representation adopted in strval, a label of SizedBigInt.kx_baseLabel.
   * @param maxBits null or maximal number of bits.
   * @return new or redefined SizedBigInt.
   */
  fromString(strval, radix=4, maxBits=null) {
    if (typeof strval!='string') throw new Error("Invalid input type, must be String");
    let r = SizedBigInt.baseLabel(radix,false)
    if (!strval) return this.fromNull()
    if (r.base==2)
      return this.fromBinaryString(strval,maxBits);
    let trLabel = r.label+'-to-2'
    if (!SizedBigInt.kx_tr[trLabel]) SizedBigInt.kx_trConfig(r.label);
    let tr = SizedBigInt.kx_tr[trLabel]
    let strbin = ''
    for (let i=0; i<strval.length; i++)
      strbin += tr[ strval.charAt(i) ]
    return this.fromBinaryString(strbin,maxBits)
  }

  /**
   * Input from BigInt or integer part of a Number.
   * @param val Number or BigInt.
   * @param bits optional, the bit-length of val, to padding zeros.
   * @param maxBits null or maximal number of bits (trunc when val is Number).
   * @return new or redefined SizedBigInt.
   */
  fromInt(val, bits=0, maxBits=null) {
    let t = typeof val
    let isNum = (t=='number')
    if (t == 'bigint' || isNum) {
      if (isNum)  this.val =
        maxBits? BigInt.asUintN( maxBits, String(val) ) // or unsigned by zero-fill operator, x >>> 0
        : BigInt( String(val) );
      else this.val = val; // is a clone?
      let l = this.val.toString(2).length  // ? check https://stackoverflow.com/q/54758130/287948
      this.bits = bits? bits: l;
      if (l>this.bits)
        throw new Error("invalid input value, bigger than input bit-length");
      if (maxBits && this.bits>maxBits)
        throw new Error(`bit-length ${this.bits} exceeded the limit ${maxBits}`);
      return this
    } else // null, undefined, string, etc.
      return this.fromNull()
  }

  _fromHexString(strval) {  // not in use, for performance optimizations
    if (!strval) return this.fromNull()
    this.bits = strval.length*4
    this.val = BigInt("0x"+strval)
    return this
  }

  // // //
  // Getters and output methods:

  get value() { return [this.bits,this.val] }


  /**
   * Overrides the default toString() method and implements radix convertions.
   * @param radix optional, the base-label (see keys of SizedBigInt.kx_baseLabel)
   */
  toString(radix) {
    if (radix===undefined)
      return `[${this.bits},${this.val}]`; // Overrides Javascript toString()
    let rTo = SizedBigInt.baseLabel(radix,false)
    if (this.val===null || (!rTo.useHalfDigit && this.bits % rTo.bitsPerDigit != 0))
      return '';
    if (rTo.base==2)
      return this.val.toString(2).padStart(this.bits,'0');

    let b = this.toString(2) // recurrence
    let trLabel = '2-to-'+rTo.label

    if (!SizedBigInt.kx_tr[trLabel]) SizedBigInt.kx_trConfig(rTo.label);
    let tr = SizedBigInt.kx_tr[trLabel]
    let r = ''
    for (let i=0; i<b.length; i+=rTo.bitsPerDigit)
      r += tr[ b.slice(i,i+rTo.bitsPerDigit) ]
    return r;
  }

  // // //
  // Etc. and order:

  /**
   * Swap-object utility.
   * @return object with swapped key-values.
   */
  static objSwap(obj) {
    return Object.entries(obj).reduce(
      (obj, [key,value])  =>  ({ ...obj, [value]: key }),  {}
    )
  }

  /**
   * Apply correction rules to SizedBigInt.kx_baseLabel.
   */
  static kx_baseLabel_setRules(label=null) {
    let scan = label? [label]: Object.keys(SizedBigInt.kx_baseLabel)
    const rAlpha = {falsetrue:"upper", falsefalse:true, truefalse:"lower", truetrue:false};
    for (let i of scan) {
      const r = SizedBigInt.kx_baseLabel[i]
      if (!r.base)         r.base = r.alphabet.length;
      if (!r.bitsPerDigit) r.bitsPerDigit = Math.log2(r.base);
      if (!r.useHalfDigit) r.useHalfDigit = false;
      let alphaRgx = r.alphabet.replace('-','\\-')
      if (!r.regex)  r.regex =  '^(['+ alphaRgx +']+)$';
      if (!r.case)
        r.case = rAlpha[String(r.alphabet==r.alphabet.toLowerCase()) + (r.alphabet==r.alphabet.toUpperCase())]
      let aux = (r.case===false)? 'i': '';
      if (typeof r.regex =='string')  r.regex = new RegExp(r.regex,aux);
      if (r.isDefault===undefined)    r.isDefault=false;
      if (r.isDefault && i!=r.base) SizedBigInt.kx_baseLabel[String(r.base)] = {isAlias: i};
      aux = String(r.bitsPerDigit) +','+ r.bitsPerDigit;
      if (i!='2')
        r.regex_b2 = new RegExp('^((?:[01]{'+ aux +'})*)([01]*)$');
      r.label = i
    } // \for
  }

  /**
   * Check and normalize the base label. Access the global kx_baseLabel.
   * @param string label
   * @param boolean retLabel, to return string instead pointer.
   * @return object pointer (to the correct kx_baseLabel), or a string with normalized label.
   */
  static baseLabel(label,retLabel=false) {
    let t = typeof label;
    if (t=='number') label = String(label);
    else if (t=='boolean' || !label) label='2';
    label = label.toLowerCase();
    if (label.slice(0,3)=='base') label = label.slice(3);
    var r = SizedBigInt.kx_baseLabel[label]
    if (!r) throw new Error(`label "${label}" not exists, must be registered`);
    if (r.isAlias) r = SizedBigInt.kx_baseLabel[r.isAlias];
    return retLabel? r.label: r;
  }

  /**
   * Internal cache-builder for input radix methods. Generates the non-default objects.
   * Changes the state of SizedBigInt.kx_tr.
   */
  static kx_trConfig(baseLabel) {
    const r = SizedBigInt.kx_baseLabel[baseLabel];
    if (!r || r.isAlias) throw new Error(`label "${baseLabel}" not exists or is alias`);
    let label = r.label + '-to-2'
    if (!SizedBigInt.kx_tr[label]) SizedBigInt.kx_tr[label] = {};
    for (let i=0; i<r.base; i++) { // scans alphabet
        let c = r.alphabet.charAt(i)
        SizedBigInt.kx_tr[label][c] = i.toString(2).padStart(r.bitsPerDigit,'0')
    }
    SizedBigInt.kx_tr['2-to-'+r.label] = SizedBigInt.objSwap(SizedBigInt.kx_tr[label]);
  }

  /**
   * Compare two SizedBigInt's, by numeric or lexicographic order.
   * Changes the input array.
   * Flags lexOrder by external SizedBigInt.compare_lexicographic when not null.
   * @param a Array of SizedBigInt instances, to reverse order.
   * @param lexOrder null or boolean to lexicographic order, else numeric order.
   * @return integer 0 when a=b, 1 when a>b, -1 otherwise.
   */
  static compare(SizedBigInt_a, SizedBigInt_b, cmpLex=null) {
    if (SizedBigInt.compare_invert)
      [SizedBigInt_a, SizedBigInt_b] = [SizedBigInt_b, SizedBigInt_a];
    if ( cmpLex===true || SizedBigInt.compare_lexicographic===true) {
      // lexicographic order:
      let a = SizedBigInt_a.toString(2)
      let b = SizedBigInt_b.toString(2)
      return (a>b)? 1: ( (a==b)? 0: -1 )
    } else { // numeric order:
      let bitsDiff = SizedBigInt_a.bits - SizedBigInt_b.bits
      if (bitsDiff) return bitsDiff;
      else {
        let bigDiff = SizedBigInt_a.val - SizedBigInt_b.val
        return (bigDiff==0n)? 0: ( (bigDiff>0n)? 1: -1 )
      }
    }
  }

  /**
   * Sort or reverse-sort of an array of SizedBigInt's.
   * Changes the input array.
   * @param a Array of SizedBigInt instances, to reverse order.
   * @param lexOrder boolean to lexicographic order, else numeric order.
   * @param descOrder boolean to descendent order, else ascendent.
   */
  static sort(a, lexOrder=false, descOrder=false) {
    SizedBigInt.compare_lexicographic = lexOrder
    SizedBigInt.compare_invert = descOrder
    a.sort(SizedBigInt.compare)
    SizedBigInt.compare_lexicographic = null // clean
  }

  /**
   * Truncate returnig prefix and suffix.
   * @param bits integer, number of bits in the prefix.
   * @return array, two new SizedBigInts.
   */
   splitAt(bits) {
    if (!bits||bits<0||bits>this.bits) return null;
    let strbin = this.toString(2)
    return [
      new SizedBigInt( strbin.slice(0,bits), 2 ),
      new SizedBigInt( strbin.slice(bits), 2 )
    ]
  }

  /**
   * @param bits, number of bits of the result.
   * @return SizedBigInt, trucated clone. Same as this.splitAt(bits)[0];
   */
  trunc(bits) {
    if (!bits||bits<0||bits>this.bits) return null;
    return new SizedBigInt( this.toString(2).slice(0,bits), 2 )
  }


} // \class

thumbnail.png