Skip to content

Instantly share code, notes, and snippets.

@ppKrauss

ppKrauss/.block

Last active September 26, 2019 00:45
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save ppKrauss/f8e947f4628a7cc066ef0b9024f79e13 to your computer and use it in GitHub Desktop.
Save ppKrauss/f8e947f4628a7cc066ef0b9024f79e13 to your computer and use it in GitHub Desktop.
Download ZIP
compareCurves
Raw
.block
license: mit
Raw
README.md
Raw
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
Raw
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 ...}
Raw
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>
Raw
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
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment