@thi.ng/associative
Advanced tools
Comparing version 4.4.1 to 4.5.0
@@ -6,2 +6,13 @@ # Change Log | ||
# [4.5.0](https://github.com/thi-ng/umbrella/compare/@thi.ng/associative@4.4.1...@thi.ng/associative@4.5.0) (2020-07-17) | ||
### Features | ||
* **associative:** add Trie.knownPrefix() ([26ddd2c](https://github.com/thi-ng/umbrella/commit/26ddd2ceaf7d9327cf0d6f65d9153cff476f2081)) | ||
## [4.4.1](https://github.com/thi-ng/umbrella/compare/@thi.ng/associative@4.4.0...@thi.ng/associative@4.4.1) (2020-07-08) | ||
@@ -8,0 +19,0 @@ |
@@ -1433,2 +1433,18 @@ 'use strict'; | ||
} | ||
knownPrefix(key) { | ||
let node = this; | ||
const prefix = []; | ||
for (let i = 0, n = key.length; i < n; i++) { | ||
const k = key[i].toString(); | ||
const next = node.next[k]; | ||
if (!next) | ||
break; | ||
prefix.push(k); | ||
node = next; | ||
} | ||
return prefix; | ||
} | ||
hasKnownPrefix(key) { | ||
return this.knownPrefix(key).length > 0; | ||
} | ||
add(key, val) { | ||
@@ -1435,0 +1451,0 @@ let node = this; |
@@ -1,1 +0,1 @@ | ||
!function(e,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports,require("tslib"),require("@thi.ng/api"),require("@thi.ng/equiv"),require("@thi.ng/checks"),require("@thi.ng/transducers"),require("@thi.ng/binary"),require("@thi.ng/dcons"),require("@thi.ng/compare"),require("@thi.ng/errors")):"function"==typeof define&&define.amd?define(["exports","tslib","@thi.ng/api","@thi.ng/equiv","@thi.ng/checks","@thi.ng/transducers","@thi.ng/binary","@thi.ng/dcons","@thi.ng/compare","@thi.ng/errors"],t):t(((e=e||self).thi=e.thi||{},e.thi.ng=e.thi.ng||{},e.thi.ng.associative={}),e.thi.ng[""],e.thi.ng.api,e.thi.ng.equiv,e.thi.ng.checks,e.thi.ng.transducers,e.thi.ng.binary,e.thi.ng.dcons,e.thi.ng.compare,e.thi.ng.errors)}(this,(function(e,t,s,r,n,i,o,a,h,u){"use strict";function l(e,t){for(let s of t)e.delete(s);return e}const c=(e,t)=>{if(e===t)return!0;if(!(t instanceof Map)||e.size!==t.size)return!1;for(let s of e.entries())if(!r.equiv(t.get(s[0]),s[1]))return!1;return!0},p=(e,t)=>{if(e===t)return!0;if(!(t instanceof Set)||e.size!==t.size)return!1;for(let s of e.keys())if(!t.has(s))return!1;return!0},g=n.isNode()?require("util").inspect:null,f=(e,t)=>[...i.map(e=>g(e,t),e)].join(", "),d=(e,t)=>[...i.map(([e,s])=>`${g(e,t)} => ${g(s,t)}`,e)].join(", "),y=s.mixin({[Symbol.for("nodejs.util.inspect.custom")](e,t){const s=this[Symbol.toStringTag],r=Object.assign(Object.assign({},t),{depth:null===t.depth?null:t.depth-1});return e>=0?[`${s}(${this.size||0}) {`,g?this instanceof Set?f(this,r):this instanceof Map?d(this,r):"":"","}"].join(" "):t.stylize(`[${s}]`,"special")}});function S(e,t){if(n.isMap(e))for(let s of t)e.set(s[0],s[1]);else for(let s of t)e.add(s);return e}var m;const v=new WeakMap,b=e=>v.get(e).vals;e.ArraySet=m=class extends Set{constructor(e,t={}){super(),v.set(this,{equiv:t.equiv||r.equiv,vals:[]}),e&&this.into(e)}*[Symbol.iterator](){yield*b(this)}get[Symbol.species](){return m}get[Symbol.toStringTag](){return"ArraySet"}get size(){return b(this).length}copy(){const e=v.get(this),t=new m(null,{equiv:e.equiv});return v.get(t).vals=e.vals.slice(),t}empty(){return new m(null,this.opts())}clear(){b(this).length=0}first(){if(this.size)return b(this)[0]}add(e){return!this.has(e)&&b(this).push(e),this}into(e){return S(this,e)}has(e){return this.get(e,s.SEMAPHORE)!==s.SEMAPHORE}get(e,t){const s=v.get(this),r=s.equiv,n=s.vals;for(let t=n.length;--t>=0;)if(r(n[t],e))return n[t];return t}delete(e){const t=v.get(this),s=t.equiv,r=t.vals;for(let t=r.length;--t>=0;)if(s(r[t],e))return r.splice(t,1),!0;return!1}disj(e){return l(this,e)}equiv(e){return p(this,e)}forEach(e,t){const s=b(this);for(let r=s.length;--r>=0;){const n=s[r];e.call(t,n,n,this)}}*entries(){for(let e of b(this))yield[e,e]}*keys(){yield*b(this)}*values(){yield*b(this)}opts(){return{equiv:v.get(this).equiv}}},e.ArraySet=m=t.__decorate([y],e.ArraySet);const w=(e,t,s=[])=>{for(let r in e)t.hasOwnProperty(r)&&s.push(r);return s},M=(e,t)=>n.implementsFunction(e,"empty")?e.empty():new(e[Symbol.species]||t),k=(e,t)=>n.implementsFunction(e,"copy")?e.copy():new(e[Symbol.species]||t)(e),x=e=>e[Symbol.iterator]().next().value,O=e=>n.isSet(e)?e:new Set(e),q=(e,t,s)=>s?i.reduce(e(),s):[()=>null,e=>e||new Set,(e,s)=>e?t(e,O(s)):O(s)],j=(e,t,s)=>{if(e===t)return s||M(e,Set);s=s?S(s,e):k(e,Set);for(let e of t)s.delete(e);return s};var A;const z=new WeakMap,E=e=>z.get(e).map;var _;e.EquivMap=A=class extends Map{constructor(t,s){super();const n=Object.assign({equiv:r.equiv,keys:e.ArraySet},s);z.set(this,{keys:new n.keys(null,{equiv:n.equiv}),map:new Map,opts:n}),t&&this.into(t)}[Symbol.iterator](){return this.entries()}get[Symbol.species](){return A}get[Symbol.toStringTag](){return"EquivMap"}get size(){return z.get(this).keys.size}clear(){const e=z.get(this);e.keys.clear(),e.map.clear()}empty(){return new A(null,z.get(this).opts)}copy(){const e=z.get(this),t=new A;return z.set(t,{keys:e.keys.copy(),map:new Map(e.map),opts:e.opts}),t}equiv(e){return c(this,e)}delete(e){const t=z.get(this);return(e=t.keys.get(e,s.SEMAPHORE))!==s.SEMAPHORE&&(t.map.delete(e),t.keys.delete(e),!0)}dissoc(e){return l(this,e)}forEach(e,t){for(let s of E(this))e.call(t,s[1],s[0],this)}get(e,t){const r=z.get(this);return(e=r.keys.get(e,s.SEMAPHORE))!==s.SEMAPHORE?r.map.get(e):t}has(e){return z.get(this).keys.has(e)}set(e,t){const r=z.get(this),n=r.keys.get(e,s.SEMAPHORE);return n!==s.SEMAPHORE?r.map.set(n,t):(r.keys.add(e),r.map.set(e,t)),this}into(e){return S(this,e)}entries(){return E(this).entries()}keys(){return E(this).keys()}values(){return E(this).values()}opts(){return z.get(this).opts}},e.EquivMap=A=t.__decorate([y],e.EquivMap);const P=new WeakMap,H=(e,t)=>function*(){for(let s of P.get(e).bins)s&&(yield s[t])};e.HashMap=_=class extends Map{constructor(e,t){super();const s=o.ceilPow2(Math.min(t.cap||16,4))-1;P.set(this,{hash:t.hash,equiv:t.equiv||r.equiv,load:t.load||.75,mask:s,bins:new Array(s+1),size:0}),e&&this.into(e)}get[Symbol.species](){return _}get[Symbol.toStringTag](){return"HashMap"}get size(){return P.get(this).size}[Symbol.iterator](){return this.entries()}*entries(){for(let e of P.get(this).bins)e&&(yield[e[0],e[1]])}keys(){return H(this,0)()}values(){return H(this,1)()}forEach(e,t){for(let s of P.get(this).bins)e.call(t,s[1],s[0],this)}clear(){const e=P.get(this);e.bins=new Array(16),e.mask=15,e.size=0}empty(){return new _(null,this.opts({cap:16}))}copy(){const e=P.get(this),t=new _(null,this.opts({cap:4}));return Object.assign(P.get(t),{bins:e.bins.slice(),mask:e.mask,size:e.size}),t}equiv(e){return c(this,e)}has(e){const t=P.get(this),s=this.find(e,t);return s>=0&&null!=t.bins[s]}get(e,t){const s=P.get(this),r=this.find(e,s);return r>=0&&s.bins[r]?s.bins[r][1]:t}set(e,t){const s=P.get(this);let r=this.find(e,s);return r>=0&&s.bins[r]?(s.bins[r][1]=t,this):(s.size>s.mask*s.load&&(this.resize(s),r=this.find(e,s)),s.bins[r]=[e,t],s.size++,this)}delete(e){const t=P.get(this);let s=this.find(e,t);const r=t.bins;if(s>=0&&!r[s])return!1;t.size--;const n=t.mask;let i,o=s;for(;;){delete r[s];do{if(o=o+1&n,!r[o])return!0;i=t.hash(r[o][0])&n}while(s<=o?s<i&&i<=o:s<i||i<=o);r[s]=r[o],s=o}}into(e){return S(this,e)}dissoc(e){return l(this,e)}opts(e){const t=P.get(this);return Object.assign({hash:t.hash,equiv:t.equiv,load:t.load,cap:t.mask+1},e)}find(e,t){const s=t.mask,r=t.bins,n=t.equiv;let i=s,o=t.hash(e)&s;for(;r[o]&&!n(r[o][0],e);){if(i--,i<0)return-1;o=o+1&t.mask}return o}resize(e){const t=e.bins,s=2*(e.mask+1);e.bins=new Array(s),e.mask=s-1,e.size=0;for(let e of t)e&&this.set(e[0],e[1])}},e.HashMap=_=t.__decorate([y],e.HashMap);const T=(e,t)=>{const s={};for(let r of t)e.hasOwnProperty(r)&&(s[r]=e[r]);return s},L=(t,s)=>{const r=new e.EquivMap;let n,i,o;for(n of t)i=T(n,s),o=r.get(i),!o&&r.set(i,o=M(t,Set)),o.add(n);return r},R=(e,t,s)=>{if(s=s||M(e,Set),e===t)return S(s,e);if(t.size<e.size)return R(t,e,s);for(let r of t)e.has(r)&&s.add(r);return s};const U=(e,t={})=>{for(let s in e)t[e[s]]=s;return t},W=(e,...t)=>Object.assign(e,...t),C=(e,t,s={})=>{for(let r in e)s[t.hasOwnProperty(r)?t[r]:r]=e[r];return s},F=(e,t,s)=>{if(e.size&&t.size){let r,n,i;e.size<=t.size?(r=e,n=t,i=U(s)):(r=t,n=e,i=s);const o=L(r,(e=>{const t=[];for(let s in e)e.hasOwnProperty(s)&&t.push(e[s]);return t})(i)),a=Object.keys(i),h=M(e,Set);for(let e of n){const t=o.get(C(T(e,a),i));if(t)for(let s of t)h.add(W(Object.assign({},s),e))}return h}return M(e,Set)};var D;F(new Set([{a:1,b:2}]),new Set([{id:1,c:2}]),{a:"id"});const K=new WeakMap,$=e=>K.get(e).vals;e.LLSet=D=class extends Set{constructor(e,t={}){super(),K.set(this,{equiv:t.equiv||r.equiv,vals:new a.DCons}),e&&this.into(e)}*[Symbol.iterator](){yield*$(this)}get[Symbol.species](){return D}get[Symbol.toStringTag](){return"LLSet"}get size(){return $(this).length}copy(){const e=K.get(this),t=new D(null,this.opts());return K.get(t).vals=e.vals.copy(),t}empty(){return new D(null,this.opts())}clear(){$(this).clear()}first(){if(this.size)return $(this).head.value}add(e){return!this.has(e)&&$(this).push(e),this}into(e){return S(this,e)}has(e){return this.get(e,s.SEMAPHORE)!==s.SEMAPHORE}get(e,t){const s=K.get(this),r=s.equiv;let n=s.vals.head;for(;n;){if(r(n.value,e))return n.value;n=n.next}return t}delete(e){const t=K.get(this),s=t.equiv;let r=t.vals.head;for(;r;){if(s(r.value,e))return t.vals.splice(r,1),!0;r=r.next}return!1}disj(e){return l(this,e)}equiv(e){return p(this,e)}forEach(e,t){let s=$(this).head;for(;s;)e.call(t,s.value,s.value,this),s=s.next}*entries(){for(let e of $(this))yield[e,e]}*keys(){yield*$(this)}*values(){yield*$(this)}opts(){return{equiv:K.get(this).equiv}}},e.LLSet=D=t.__decorate([y],e.LLSet);const N=(e,t)=>{for(let s in t){if("__proto__"===s)continue;const r=t[s];e[s]=n.isFunction(r)?r(e[s]):r}return e},V=(e,t,...s)=>B(e,Object.assign({},t),...s),B=(e,t,...s)=>{for(let r of s)if(null!=r)for(let s in r){if("__proto__"===s)continue;const n=r[s];t[s]=t.hasOwnProperty(s)?e(t[s],n):n}return t},G=(e,...t)=>V((e,t)=>n.isPlainObject(e)&&n.isPlainObject(t)?G(e,t):t,e,...t),I=(e,...t)=>B((e,t)=>n.isPlainObject(e)&&n.isPlainObject(t)?I(e,t):t,e,...t);var J;class Q{constructor(e,t,s){this.k=e,this.v=t,this.next=new Array(s+1)}}const X=new WeakMap;var Y;e.SortedMap=J=class extends Map{constructor(e,t={}){super();const s=t.capacity||J.DEFAULT_CAP,r=Math.ceil(Math.log2(s));X.set(this,{head:new Q(null,null,0),cap:Math.pow(2,r),cmp:t.compare||h.compare,p:t.probability||J.DEFAULT_P,maxh:r,length:0,h:0}),e&&this.into(e)}get[Symbol.species](){return J}*[Symbol.iterator](){let e=X.get(this).head;for(;e=e.next[0];)yield[e.k,e.v]}*entries(e,t=!1){const s=X.get(this);let r=s.head;const n=s.cmp;let i;if(t){for(;r=r.next[0];)if((void 0===e||(i=n(r.k,e))<=0)&&(yield[r.k,r.v],0===i))return}else for(;r=r.next[0];)(void 0===e||(i=n(r.k,e))>=0)&&(yield[r.k,r.v])}keys(e,t=!1){return i.map(e=>e[0],this.entries(e,t))}values(e,t=!1){return i.map(e=>e[1],this.entries(e,t))}get size(){return X.get(this).length}clear(){const e=X.get(this);e.head=new Q(null,null,0),e.length=0,e.h=0}empty(){return new J(null,Object.assign(Object.assign({},this.opts()),{capacity:J.DEFAULT_CAP}))}copy(){return new J(this,this.opts())}compare(e){const t=this.size,s=e.size;if(t<s)return-1;if(t>s)return 1;const r=this.entries(),n=e.entries();let i,o,a;for(;i=r.next(),o=n.next(),!i.done&&!o.done;)if(0!==(a=h.compare(i.value[0],o.value[0]))||0!==(a=h.compare(i.value[1],o.value[1])))return a;return 0}equiv(e){return c(this,e)}first(){const e=X.get(this).head.next[0];return e?[e.k,e.v]:void 0}get(e,t){const s=this.findPredNode(e).next[0];return s&&0===X.get(this).cmp(s.k,e)?s.v:t}has(e){return this.get(e,s.SEMAPHORE)!==s.SEMAPHORE}set(e,t){const s=X.get(this);let r=s.head,n=s.h,i=new Array(n);const o=s.cmp;let a;for(;n>=0;){for(;r.next[n]&&(a=o(r.next[n].k,e))<0;)r=r.next[n];if(r.next[n]&&0===a){do{r.next[n].v=t}while(--n>=0);return this}i[n--]=r}const h=this.pickHeight(s.maxh,s.h,s.p);for(r=new Q(e,t,h);s.h<h;)i[++s.h]=s.head;for(let e=0;e<=h;e++)r.next[e]=i[e].next[e],i[e].next[e]=r;return s.length++,s.length>=s.cap&&(s.cap*=2,s.maxh++),this}delete(e){const t=X.get(this);let s=t.head,r=t.h,n=!1;const i=t.cmp;let o;for(;r>=0;){for(;s.next[r]&&(o=i(s.next[r].k,e))<0;)s=s.next[r];s.next[r]&&0===o&&(n=!0,s.next[r]=s.next[r].next[r],s!=t.head||s.next[r]||(t.h=Math.max(0,t.h-1))),r--}return n&&t.length--,n}into(e){return S(this,e)}dissoc(e){return l(this,e)}forEach(e,t){for(let s of this)e.call(t,s[1],s[0],this)}$reduce(e,t){let s=X.get(this).head;for(;(s=s.next[0])&&!i.isReduced(t);)t=e(t,[s.k,s.v]);return t}opts(){const e=X.get(this);return{capacity:e.cap,compare:e.cmp,probability:e.p}}findPredNode(e){const t=X.get(this),s=t.cmp;let r=t.head,n=t.h;for(;n>=0;){for(;r.next[n]&&s(r.next[n].k,e)<0;)r=r.next[n];n--}return r}pickHeight(e,t,s){const r=Math.min(e,t+1);let n=0;for(;Math.random()<s&&n<r;)n++;return n}},e.SortedMap.DEFAULT_CAP=8,e.SortedMap.DEFAULT_P=1/Math.E,e.SortedMap=J=t.__decorate([y],e.SortedMap);const Z=new WeakMap;e.SortedSet=Y=class extends Set{constructor(t,s){super(),Z.set(this,new e.SortedMap(t?i.map(e=>[e,e],t):null,s))}[Symbol.iterator](){return this.keys()}get[Symbol.species](){return Y}get[Symbol.toStringTag](){return"SortedSet"}get size(){return Z.get(this).size}copy(){return new Y(this.keys(),this.opts())}empty(){return new Y(null,Object.assign(Object.assign({},this.opts()),{capacity:e.SortedMap.DEFAULT_CAP}))}compare(e){const t=this.size,s=e.size;if(t<s)return-1;if(t>s)return 1;const r=this.entries(),n=e.entries();let i,o,a;for(;i=r.next(),o=n.next(),!i.done&&!o.done;)if(0!==(a=h.compare(i.value[0],o.value[0])))return a;return 0}equiv(e){return p(this,e)}$reduce(e,t){return Z.get(this).$reduce((t,s)=>e(t,s[0]),t)}entries(e,t=!1){return Z.get(this).entries(e,t)}keys(e,t=!1){return Z.get(this).keys(e,t)}values(e,t=!1){return Z.get(this).values(e,t)}add(e){return Z.get(this).set(e,e),this}into(e){return S(this,e)}clear(){Z.get(this).clear()}first(){const e=Z.get(this).first();return e?e[0]:void 0}delete(e){return Z.get(this).delete(e)}disj(e){return l(this,e)}forEach(e,t){for(let s of this)e.call(t,s,s,this)}has(e){return Z.get(this).has(e)}get(e,t){return Z.get(this).get(e,t)}opts(){return Z.get(this).opts()}},e.SortedSet=Y=t.__decorate([y],e.SortedSet);const ee=new WeakMap,te=()=>u.illegalArgs("dense & sparse arrays must be of same size");e.ASparseSet=class extends Set{constructor(e,t){super(),ee.set(this,{dense:e,sparse:t,n:0})}[Symbol.iterator](){return this.keys()}get size(){return ee.get(this).n}get capacity(){return ee.get(this).dense.length}clear(){ee.get(this).n=0}equiv(e){if(this===e)return!0;if(!(e instanceof Set)||this.size!==e.size)return!1;const t=ee.get(this),s=t.dense;for(let r=t.n;--r>=0;)if(!e.has(s[r]))return!1;return!0}add(e){const t=ee.get(this),s=t.dense,r=t.sparse,n=s.length,i=r[e],o=t.n;return e<n&&o<n&&!(i<o&&s[i]===e)&&(s[o]=e,r[e]=o,t.n++),this}delete(e){const t=ee.get(this),s=t.dense,r=t.sparse,n=r[e];if(n<t.n&&s[n]===e){const e=s[--t.n];return s[n]=e,r[e]=n,!0}return!1}has(e){const t=ee.get(this),s=t.sparse[e];return s<t.n&&t.dense[s]===e}get(e,t=-1){return this.has(e)?e:t}first(){const e=ee.get(this);return e.n?e.dense[0]:void 0}into(e){return S(this,e)}disj(e){return l(this,e)}forEach(e,t){const s=ee.get(this),r=s.dense,n=s.n;for(let s=0;s<n;s++){const n=r[s];e.call(t,n,n,this)}}*entries(){const e=ee.get(this),t=e.dense,s=e.n;for(let e=0;e<s;e++)yield[t[e],t[e]]}*keys(){const e=ee.get(this),t=e.dense,s=e.n;for(let e=0;e<s;e++)yield t[e]}values(){return this.keys()}__copyTo(e){const t=ee.get(this),s=ee.get(e);return s.dense=t.dense.slice(),s.sparse=t.sparse.slice(),s.n=t.n,e}},e.ASparseSet=t.__decorate([y],e.ASparseSet);class se extends e.ASparseSet{constructor(e,t){n.isNumber(e)?super(new Uint8Array(e),new Uint8Array(e)):e.length===t.length?super(e,t):te()}get[Symbol.species](){return se}get[Symbol.toStringTag](){return"SparseSet8"}copy(){return this.__copyTo(new se(0))}empty(){return new se(this.capacity)}}class re extends e.ASparseSet{constructor(e,t){n.isNumber(e)?super(new Uint16Array(e),new Uint16Array(e)):e.length===t.length?super(e,t):te()}get[Symbol.species](){return re}get[Symbol.toStringTag](){return"SparseSet16"}copy(){return this.__copyTo(new re(0))}empty(){return new re(this.capacity)}}class ne extends e.ASparseSet{constructor(e,t){n.isNumber(e)?super(new Uint32Array(e),new Uint32Array(e)):e.length===t.length?super(e,t):te()}get[Symbol.species](){return ne}get[Symbol.toStringTag](){return"SparseSet32"}copy(){return this.__copyTo(new ne(0))}empty(){return new ne(this.capacity)}}class ie{constructor(){this.next={},this.n=0}*[Symbol.iterator](){const e=[["",this]];for(;e.length;){const[t,s]=e.pop();s.vals?yield*i.map(e=>[t,e],s.vals):s.queueChildren(e,t)}}*keys(e="",t=""){const s=[[t,this]];for(;s.length;){const[t,r]=s.pop();r.vals?yield t:r.queueChildren(s,t,e)}}*values(){const e=[this];for(;e.length;){const t=e.pop();t.vals?yield*t.vals:e.push(...i.vals(t.next))}}clear(){this.next={},this.n=0,this.vals=void 0}has(e){return!!this.get(e)}hasPrefix(e){return!!this.find(e)}*suffixes(e,t=!1){const s=this.find(e);s&&(yield*s.keys("",t?e.toString():""))}get(e){const t=this.find(e);return t?t.vals:void 0}find(e){let t=this;for(let s=0,r=e.length;s<r;s++)if(t=t.next[e[s].toString()],!t)return;return t}add(e,t){let s=this;for(let t=0,r=e.length;t<r;t++){const r=e[t].toString(),n=s.next[r];s=n||(s.n++,s.next[r]=this.makeChild())}s.vals||(s.vals=this.makeValueSet()),s.vals.add(t)}delete(e,t){const s=e.length;if(s<1)return!1;const r=[],n=[];let i=0,o=this;for(;i<s;i++){const t=e[i].toString();if(n.push(t),r.push(o),o=o.next[t],!o)return!1}if(void 0!==t){const e=o.vals;if(!e||!e.has(t))return!1;if(e.delete(t),e.size>0)return!0}for(;(o=r[--i])&&(delete o.next[n[i]],!--o.n););return!0}makeChild(){return new ie}makeValueSet(){return new Set}queueChildren(e,t,s=""){t=t.length?t+s:t,e.push(...i.map(e=>[t+e,this.next[e]],Object.keys(this.next)))}}const oe=(e,t,s)=>{if(e.size<t.size){const s=e;e=t,t=s}return s=s?S(s,e):k(e,Set),e===t?s:S(s,t)};e.SparseSet16=re,e.SparseSet32=ne,e.SparseSet8=se,e.Trie=ie,e.commonKeysMap=(e,t,s=[])=>{for(let r of e.keys())t.has(r)&&s.push(r);return s},e.commonKeysObj=w,e.defArraySet=(t,s)=>new e.ArraySet(t,s),e.defEquivMap=function(t,s){return new e.EquivMap(n.isPlainObject(t)?i.pairs(t):t,s)},e.defHashMap=function(t,s){if(n.isPlainObject(t)){const r=Object.keys(t);return new e.HashMap(i.map(e=>[e,t[e]],r),Object.assign({cap:r.length/(s.load||.75)},s))}return new e.HashMap(t,s)},e.defLLSet=(t,s)=>new e.LLSet(t,s),e.defSortedMap=function(t,s){if(n.isPlainObject(t)){const r=Object.keys(t);return new e.SortedMap(i.map(e=>[e,t[e]],r),Object.assign({capacity:r.length},s))}return new e.SortedMap(t,s)},e.defSortedSet=(t,s)=>new e.SortedSet(t,s),e.defSparseSet=e=>e<=256?new se(e):e<=65536?new re(e):new ne(e),e.difference=j,e.differenceR=function e(t){return q(e,j,t)},e.dissoc=l,e.dissocObj=(e,t)=>{for(let s of t)delete e[s];return e},e.indexed=L,e.intersection=R,e.intersectionR=function e(t){return q(e,R,t)},e.into=S,e.invertMap=(e,t)=>{t=t||new Map;for(let s of e)t.set(s[1],s[0]);return t},e.invertObj=U,e.join=(e,t)=>{if(e.size&&t.size){const s=w(x(e)||{},x(t)||{});let r,n;e.size<=t.size?(r=e,n=t):(r=t,n=e);const i=L(r,s),o=M(e,Set);for(let e of n){const t=i.get(T(e,s));if(t)for(let s of t)o.add(W(Object.assign({},s),e))}return o}return M(e,Set)},e.joinWith=F,e.meldApplyObj=N,e.meldDeepObj=I,e.meldObjWith=B,e.mergeApplyMap=(e,t)=>{const s=k(e,Map);for(let[e,r]of t)s.set(e,n.isFunction(r)?r(s.get(e)):r);return s},e.mergeApplyObj=(e,t)=>N(Object.assign({},e),t),e.mergeDeepObj=G,e.mergeMap=(e,...t)=>{for(let s of t)if(null!=s)for(let t of s)e.set(t[0],t[1]);return e},e.mergeMapWith=(e,t,...s)=>{const r=k(t,Map);for(let t of s)if(null!=t)for(let[s,n]of t)r.set(s,r.has(s)?e(r.get(s),n):n);return r},e.mergeObj=W,e.mergeObjWith=V,e.renameKeysMap=(e,t,s)=>{s=s||M(e,Map);for(let[r,n]of e)s.set(t.has(r)?t.get(r):r,n);return s},e.renameKeysObj=C,e.selectKeysMap=(e,t)=>{const s=M(e,Map);for(let r of t)e.has(r)&&s.set(r,e.get(r));return s},e.selectKeysObj=T,e.union=oe,e.unionR=function e(t){return q(e,oe,t)},e.withoutKeysMap=(e,t)=>{const s=O(t),r=M(e,Map);for(let t of e.entries()){const e=t[0];!s.has(e)&&r.set(e,t[1])}return r},e.withoutKeysObj=(e,t)=>{const s=O(t),r={};for(let t in e)e.hasOwnProperty(t)&&!s.has(t)&&(r[t]=e[t]);return r},Object.defineProperty(e,"__esModule",{value:!0})})); | ||
!function(e,t){"object"==typeof exports&&"undefined"!=typeof module?t(exports,require("tslib"),require("@thi.ng/api"),require("@thi.ng/equiv"),require("@thi.ng/checks"),require("@thi.ng/transducers"),require("@thi.ng/binary"),require("@thi.ng/dcons"),require("@thi.ng/compare"),require("@thi.ng/errors")):"function"==typeof define&&define.amd?define(["exports","tslib","@thi.ng/api","@thi.ng/equiv","@thi.ng/checks","@thi.ng/transducers","@thi.ng/binary","@thi.ng/dcons","@thi.ng/compare","@thi.ng/errors"],t):t(((e=e||self).thi=e.thi||{},e.thi.ng=e.thi.ng||{},e.thi.ng.associative={}),e.thi.ng[""],e.thi.ng.api,e.thi.ng.equiv,e.thi.ng.checks,e.thi.ng.transducers,e.thi.ng.binary,e.thi.ng.dcons,e.thi.ng.compare,e.thi.ng.errors)}(this,(function(e,t,s,r,n,i,o,a,h,u){"use strict";function l(e,t){for(let s of t)e.delete(s);return e}const c=(e,t)=>{if(e===t)return!0;if(!(t instanceof Map)||e.size!==t.size)return!1;for(let s of e.entries())if(!r.equiv(t.get(s[0]),s[1]))return!1;return!0},p=(e,t)=>{if(e===t)return!0;if(!(t instanceof Set)||e.size!==t.size)return!1;for(let s of e.keys())if(!t.has(s))return!1;return!0},f=n.isNode()?require("util").inspect:null,g=(e,t)=>[...i.map(e=>f(e,t),e)].join(", "),d=(e,t)=>[...i.map(([e,s])=>`${f(e,t)} => ${f(s,t)}`,e)].join(", "),y=s.mixin({[Symbol.for("nodejs.util.inspect.custom")](e,t){const s=this[Symbol.toStringTag],r=Object.assign(Object.assign({},t),{depth:null===t.depth?null:t.depth-1});return e>=0?[`${s}(${this.size||0}) {`,f?this instanceof Set?g(this,r):this instanceof Map?d(this,r):"":"","}"].join(" "):t.stylize(`[${s}]`,"special")}});function S(e,t){if(n.isMap(e))for(let s of t)e.set(s[0],s[1]);else for(let s of t)e.add(s);return e}var m;const v=new WeakMap,b=e=>v.get(e).vals;e.ArraySet=m=class extends Set{constructor(e,t={}){super(),v.set(this,{equiv:t.equiv||r.equiv,vals:[]}),e&&this.into(e)}*[Symbol.iterator](){yield*b(this)}get[Symbol.species](){return m}get[Symbol.toStringTag](){return"ArraySet"}get size(){return b(this).length}copy(){const e=v.get(this),t=new m(null,{equiv:e.equiv});return v.get(t).vals=e.vals.slice(),t}empty(){return new m(null,this.opts())}clear(){b(this).length=0}first(){if(this.size)return b(this)[0]}add(e){return!this.has(e)&&b(this).push(e),this}into(e){return S(this,e)}has(e){return this.get(e,s.SEMAPHORE)!==s.SEMAPHORE}get(e,t){const s=v.get(this),r=s.equiv,n=s.vals;for(let t=n.length;--t>=0;)if(r(n[t],e))return n[t];return t}delete(e){const t=v.get(this),s=t.equiv,r=t.vals;for(let t=r.length;--t>=0;)if(s(r[t],e))return r.splice(t,1),!0;return!1}disj(e){return l(this,e)}equiv(e){return p(this,e)}forEach(e,t){const s=b(this);for(let r=s.length;--r>=0;){const n=s[r];e.call(t,n,n,this)}}*entries(){for(let e of b(this))yield[e,e]}*keys(){yield*b(this)}*values(){yield*b(this)}opts(){return{equiv:v.get(this).equiv}}},e.ArraySet=m=t.__decorate([y],e.ArraySet);const w=(e,t,s=[])=>{for(let r in e)t.hasOwnProperty(r)&&s.push(r);return s},k=(e,t)=>n.implementsFunction(e,"empty")?e.empty():new(e[Symbol.species]||t),M=(e,t)=>n.implementsFunction(e,"copy")?e.copy():new(e[Symbol.species]||t)(e),x=e=>e[Symbol.iterator]().next().value,O=e=>n.isSet(e)?e:new Set(e),q=(e,t,s)=>s?i.reduce(e(),s):[()=>null,e=>e||new Set,(e,s)=>e?t(e,O(s)):O(s)],j=(e,t,s)=>{if(e===t)return s||k(e,Set);s=s?S(s,e):M(e,Set);for(let e of t)s.delete(e);return s};var A;const z=new WeakMap,E=e=>z.get(e).map;var P;e.EquivMap=A=class extends Map{constructor(t,s){super();const n=Object.assign({equiv:r.equiv,keys:e.ArraySet},s);z.set(this,{keys:new n.keys(null,{equiv:n.equiv}),map:new Map,opts:n}),t&&this.into(t)}[Symbol.iterator](){return this.entries()}get[Symbol.species](){return A}get[Symbol.toStringTag](){return"EquivMap"}get size(){return z.get(this).keys.size}clear(){const e=z.get(this);e.keys.clear(),e.map.clear()}empty(){return new A(null,z.get(this).opts)}copy(){const e=z.get(this),t=new A;return z.set(t,{keys:e.keys.copy(),map:new Map(e.map),opts:e.opts}),t}equiv(e){return c(this,e)}delete(e){const t=z.get(this);return(e=t.keys.get(e,s.SEMAPHORE))!==s.SEMAPHORE&&(t.map.delete(e),t.keys.delete(e),!0)}dissoc(e){return l(this,e)}forEach(e,t){for(let s of E(this))e.call(t,s[1],s[0],this)}get(e,t){const r=z.get(this);return(e=r.keys.get(e,s.SEMAPHORE))!==s.SEMAPHORE?r.map.get(e):t}has(e){return z.get(this).keys.has(e)}set(e,t){const r=z.get(this),n=r.keys.get(e,s.SEMAPHORE);return n!==s.SEMAPHORE?r.map.set(n,t):(r.keys.add(e),r.map.set(e,t)),this}into(e){return S(this,e)}entries(){return E(this).entries()}keys(){return E(this).keys()}values(){return E(this).values()}opts(){return z.get(this).opts}},e.EquivMap=A=t.__decorate([y],e.EquivMap);const _=new WeakMap,H=(e,t)=>function*(){for(let s of _.get(e).bins)s&&(yield s[t])};e.HashMap=P=class extends Map{constructor(e,t){super();const s=o.ceilPow2(Math.min(t.cap||16,4))-1;_.set(this,{hash:t.hash,equiv:t.equiv||r.equiv,load:t.load||.75,mask:s,bins:new Array(s+1),size:0}),e&&this.into(e)}get[Symbol.species](){return P}get[Symbol.toStringTag](){return"HashMap"}get size(){return _.get(this).size}[Symbol.iterator](){return this.entries()}*entries(){for(let e of _.get(this).bins)e&&(yield[e[0],e[1]])}keys(){return H(this,0)()}values(){return H(this,1)()}forEach(e,t){for(let s of _.get(this).bins)e.call(t,s[1],s[0],this)}clear(){const e=_.get(this);e.bins=new Array(16),e.mask=15,e.size=0}empty(){return new P(null,this.opts({cap:16}))}copy(){const e=_.get(this),t=new P(null,this.opts({cap:4}));return Object.assign(_.get(t),{bins:e.bins.slice(),mask:e.mask,size:e.size}),t}equiv(e){return c(this,e)}has(e){const t=_.get(this),s=this.find(e,t);return s>=0&&null!=t.bins[s]}get(e,t){const s=_.get(this),r=this.find(e,s);return r>=0&&s.bins[r]?s.bins[r][1]:t}set(e,t){const s=_.get(this);let r=this.find(e,s);return r>=0&&s.bins[r]?(s.bins[r][1]=t,this):(s.size>s.mask*s.load&&(this.resize(s),r=this.find(e,s)),s.bins[r]=[e,t],s.size++,this)}delete(e){const t=_.get(this);let s=this.find(e,t);const r=t.bins;if(s>=0&&!r[s])return!1;t.size--;const n=t.mask;let i,o=s;for(;;){delete r[s];do{if(o=o+1&n,!r[o])return!0;i=t.hash(r[o][0])&n}while(s<=o?s<i&&i<=o:s<i||i<=o);r[s]=r[o],s=o}}into(e){return S(this,e)}dissoc(e){return l(this,e)}opts(e){const t=_.get(this);return Object.assign({hash:t.hash,equiv:t.equiv,load:t.load,cap:t.mask+1},e)}find(e,t){const s=t.mask,r=t.bins,n=t.equiv;let i=s,o=t.hash(e)&s;for(;r[o]&&!n(r[o][0],e);){if(i--,i<0)return-1;o=o+1&t.mask}return o}resize(e){const t=e.bins,s=2*(e.mask+1);e.bins=new Array(s),e.mask=s-1,e.size=0;for(let e of t)e&&this.set(e[0],e[1])}},e.HashMap=P=t.__decorate([y],e.HashMap);const T=(e,t)=>{const s={};for(let r of t)e.hasOwnProperty(r)&&(s[r]=e[r]);return s},L=(t,s)=>{const r=new e.EquivMap;let n,i,o;for(n of t)i=T(n,s),o=r.get(i),!o&&r.set(i,o=k(t,Set)),o.add(n);return r},R=(e,t,s)=>{if(s=s||k(e,Set),e===t)return S(s,e);if(t.size<e.size)return R(t,e,s);for(let r of t)e.has(r)&&s.add(r);return s};const U=(e,t={})=>{for(let s in e)t[e[s]]=s;return t},W=(e,...t)=>Object.assign(e,...t),C=(e,t,s={})=>{for(let r in e)s[t.hasOwnProperty(r)?t[r]:r]=e[r];return s},F=(e,t,s)=>{if(e.size&&t.size){let r,n,i;e.size<=t.size?(r=e,n=t,i=U(s)):(r=t,n=e,i=s);const o=L(r,(e=>{const t=[];for(let s in e)e.hasOwnProperty(s)&&t.push(e[s]);return t})(i)),a=Object.keys(i),h=k(e,Set);for(let e of n){const t=o.get(C(T(e,a),i));if(t)for(let s of t)h.add(W(Object.assign({},s),e))}return h}return k(e,Set)};var D;F(new Set([{a:1,b:2}]),new Set([{id:1,c:2}]),{a:"id"});const K=new WeakMap,$=e=>K.get(e).vals;e.LLSet=D=class extends Set{constructor(e,t={}){super(),K.set(this,{equiv:t.equiv||r.equiv,vals:new a.DCons}),e&&this.into(e)}*[Symbol.iterator](){yield*$(this)}get[Symbol.species](){return D}get[Symbol.toStringTag](){return"LLSet"}get size(){return $(this).length}copy(){const e=K.get(this),t=new D(null,this.opts());return K.get(t).vals=e.vals.copy(),t}empty(){return new D(null,this.opts())}clear(){$(this).clear()}first(){if(this.size)return $(this).head.value}add(e){return!this.has(e)&&$(this).push(e),this}into(e){return S(this,e)}has(e){return this.get(e,s.SEMAPHORE)!==s.SEMAPHORE}get(e,t){const s=K.get(this),r=s.equiv;let n=s.vals.head;for(;n;){if(r(n.value,e))return n.value;n=n.next}return t}delete(e){const t=K.get(this),s=t.equiv;let r=t.vals.head;for(;r;){if(s(r.value,e))return t.vals.splice(r,1),!0;r=r.next}return!1}disj(e){return l(this,e)}equiv(e){return p(this,e)}forEach(e,t){let s=$(this).head;for(;s;)e.call(t,s.value,s.value,this),s=s.next}*entries(){for(let e of $(this))yield[e,e]}*keys(){yield*$(this)}*values(){yield*$(this)}opts(){return{equiv:K.get(this).equiv}}},e.LLSet=D=t.__decorate([y],e.LLSet);const N=(e,t)=>{for(let s in t){if("__proto__"===s)continue;const r=t[s];e[s]=n.isFunction(r)?r(e[s]):r}return e},V=(e,t,...s)=>B(e,Object.assign({},t),...s),B=(e,t,...s)=>{for(let r of s)if(null!=r)for(let s in r){if("__proto__"===s)continue;const n=r[s];t[s]=t.hasOwnProperty(s)?e(t[s],n):n}return t},G=(e,...t)=>V((e,t)=>n.isPlainObject(e)&&n.isPlainObject(t)?G(e,t):t,e,...t),I=(e,...t)=>B((e,t)=>n.isPlainObject(e)&&n.isPlainObject(t)?I(e,t):t,e,...t);var J;class Q{constructor(e,t,s){this.k=e,this.v=t,this.next=new Array(s+1)}}const X=new WeakMap;var Y;e.SortedMap=J=class extends Map{constructor(e,t={}){super();const s=t.capacity||J.DEFAULT_CAP,r=Math.ceil(Math.log2(s));X.set(this,{head:new Q(null,null,0),cap:Math.pow(2,r),cmp:t.compare||h.compare,p:t.probability||J.DEFAULT_P,maxh:r,length:0,h:0}),e&&this.into(e)}get[Symbol.species](){return J}*[Symbol.iterator](){let e=X.get(this).head;for(;e=e.next[0];)yield[e.k,e.v]}*entries(e,t=!1){const s=X.get(this);let r=s.head;const n=s.cmp;let i;if(t){for(;r=r.next[0];)if((void 0===e||(i=n(r.k,e))<=0)&&(yield[r.k,r.v],0===i))return}else for(;r=r.next[0];)(void 0===e||(i=n(r.k,e))>=0)&&(yield[r.k,r.v])}keys(e,t=!1){return i.map(e=>e[0],this.entries(e,t))}values(e,t=!1){return i.map(e=>e[1],this.entries(e,t))}get size(){return X.get(this).length}clear(){const e=X.get(this);e.head=new Q(null,null,0),e.length=0,e.h=0}empty(){return new J(null,Object.assign(Object.assign({},this.opts()),{capacity:J.DEFAULT_CAP}))}copy(){return new J(this,this.opts())}compare(e){const t=this.size,s=e.size;if(t<s)return-1;if(t>s)return 1;const r=this.entries(),n=e.entries();let i,o,a;for(;i=r.next(),o=n.next(),!i.done&&!o.done;)if(0!==(a=h.compare(i.value[0],o.value[0]))||0!==(a=h.compare(i.value[1],o.value[1])))return a;return 0}equiv(e){return c(this,e)}first(){const e=X.get(this).head.next[0];return e?[e.k,e.v]:void 0}get(e,t){const s=this.findPredNode(e).next[0];return s&&0===X.get(this).cmp(s.k,e)?s.v:t}has(e){return this.get(e,s.SEMAPHORE)!==s.SEMAPHORE}set(e,t){const s=X.get(this);let r=s.head,n=s.h,i=new Array(n);const o=s.cmp;let a;for(;n>=0;){for(;r.next[n]&&(a=o(r.next[n].k,e))<0;)r=r.next[n];if(r.next[n]&&0===a){do{r.next[n].v=t}while(--n>=0);return this}i[n--]=r}const h=this.pickHeight(s.maxh,s.h,s.p);for(r=new Q(e,t,h);s.h<h;)i[++s.h]=s.head;for(let e=0;e<=h;e++)r.next[e]=i[e].next[e],i[e].next[e]=r;return s.length++,s.length>=s.cap&&(s.cap*=2,s.maxh++),this}delete(e){const t=X.get(this);let s=t.head,r=t.h,n=!1;const i=t.cmp;let o;for(;r>=0;){for(;s.next[r]&&(o=i(s.next[r].k,e))<0;)s=s.next[r];s.next[r]&&0===o&&(n=!0,s.next[r]=s.next[r].next[r],s!=t.head||s.next[r]||(t.h=Math.max(0,t.h-1))),r--}return n&&t.length--,n}into(e){return S(this,e)}dissoc(e){return l(this,e)}forEach(e,t){for(let s of this)e.call(t,s[1],s[0],this)}$reduce(e,t){let s=X.get(this).head;for(;(s=s.next[0])&&!i.isReduced(t);)t=e(t,[s.k,s.v]);return t}opts(){const e=X.get(this);return{capacity:e.cap,compare:e.cmp,probability:e.p}}findPredNode(e){const t=X.get(this),s=t.cmp;let r=t.head,n=t.h;for(;n>=0;){for(;r.next[n]&&s(r.next[n].k,e)<0;)r=r.next[n];n--}return r}pickHeight(e,t,s){const r=Math.min(e,t+1);let n=0;for(;Math.random()<s&&n<r;)n++;return n}},e.SortedMap.DEFAULT_CAP=8,e.SortedMap.DEFAULT_P=1/Math.E,e.SortedMap=J=t.__decorate([y],e.SortedMap);const Z=new WeakMap;e.SortedSet=Y=class extends Set{constructor(t,s){super(),Z.set(this,new e.SortedMap(t?i.map(e=>[e,e],t):null,s))}[Symbol.iterator](){return this.keys()}get[Symbol.species](){return Y}get[Symbol.toStringTag](){return"SortedSet"}get size(){return Z.get(this).size}copy(){return new Y(this.keys(),this.opts())}empty(){return new Y(null,Object.assign(Object.assign({},this.opts()),{capacity:e.SortedMap.DEFAULT_CAP}))}compare(e){const t=this.size,s=e.size;if(t<s)return-1;if(t>s)return 1;const r=this.entries(),n=e.entries();let i,o,a;for(;i=r.next(),o=n.next(),!i.done&&!o.done;)if(0!==(a=h.compare(i.value[0],o.value[0])))return a;return 0}equiv(e){return p(this,e)}$reduce(e,t){return Z.get(this).$reduce((t,s)=>e(t,s[0]),t)}entries(e,t=!1){return Z.get(this).entries(e,t)}keys(e,t=!1){return Z.get(this).keys(e,t)}values(e,t=!1){return Z.get(this).values(e,t)}add(e){return Z.get(this).set(e,e),this}into(e){return S(this,e)}clear(){Z.get(this).clear()}first(){const e=Z.get(this).first();return e?e[0]:void 0}delete(e){return Z.get(this).delete(e)}disj(e){return l(this,e)}forEach(e,t){for(let s of this)e.call(t,s,s,this)}has(e){return Z.get(this).has(e)}get(e,t){return Z.get(this).get(e,t)}opts(){return Z.get(this).opts()}},e.SortedSet=Y=t.__decorate([y],e.SortedSet);const ee=new WeakMap,te=()=>u.illegalArgs("dense & sparse arrays must be of same size");e.ASparseSet=class extends Set{constructor(e,t){super(),ee.set(this,{dense:e,sparse:t,n:0})}[Symbol.iterator](){return this.keys()}get size(){return ee.get(this).n}get capacity(){return ee.get(this).dense.length}clear(){ee.get(this).n=0}equiv(e){if(this===e)return!0;if(!(e instanceof Set)||this.size!==e.size)return!1;const t=ee.get(this),s=t.dense;for(let r=t.n;--r>=0;)if(!e.has(s[r]))return!1;return!0}add(e){const t=ee.get(this),s=t.dense,r=t.sparse,n=s.length,i=r[e],o=t.n;return e<n&&o<n&&!(i<o&&s[i]===e)&&(s[o]=e,r[e]=o,t.n++),this}delete(e){const t=ee.get(this),s=t.dense,r=t.sparse,n=r[e];if(n<t.n&&s[n]===e){const e=s[--t.n];return s[n]=e,r[e]=n,!0}return!1}has(e){const t=ee.get(this),s=t.sparse[e];return s<t.n&&t.dense[s]===e}get(e,t=-1){return this.has(e)?e:t}first(){const e=ee.get(this);return e.n?e.dense[0]:void 0}into(e){return S(this,e)}disj(e){return l(this,e)}forEach(e,t){const s=ee.get(this),r=s.dense,n=s.n;for(let s=0;s<n;s++){const n=r[s];e.call(t,n,n,this)}}*entries(){const e=ee.get(this),t=e.dense,s=e.n;for(let e=0;e<s;e++)yield[t[e],t[e]]}*keys(){const e=ee.get(this),t=e.dense,s=e.n;for(let e=0;e<s;e++)yield t[e]}values(){return this.keys()}__copyTo(e){const t=ee.get(this),s=ee.get(e);return s.dense=t.dense.slice(),s.sparse=t.sparse.slice(),s.n=t.n,e}},e.ASparseSet=t.__decorate([y],e.ASparseSet);class se extends e.ASparseSet{constructor(e,t){n.isNumber(e)?super(new Uint8Array(e),new Uint8Array(e)):e.length===t.length?super(e,t):te()}get[Symbol.species](){return se}get[Symbol.toStringTag](){return"SparseSet8"}copy(){return this.__copyTo(new se(0))}empty(){return new se(this.capacity)}}class re extends e.ASparseSet{constructor(e,t){n.isNumber(e)?super(new Uint16Array(e),new Uint16Array(e)):e.length===t.length?super(e,t):te()}get[Symbol.species](){return re}get[Symbol.toStringTag](){return"SparseSet16"}copy(){return this.__copyTo(new re(0))}empty(){return new re(this.capacity)}}class ne extends e.ASparseSet{constructor(e,t){n.isNumber(e)?super(new Uint32Array(e),new Uint32Array(e)):e.length===t.length?super(e,t):te()}get[Symbol.species](){return ne}get[Symbol.toStringTag](){return"SparseSet32"}copy(){return this.__copyTo(new ne(0))}empty(){return new ne(this.capacity)}}class ie{constructor(){this.next={},this.n=0}*[Symbol.iterator](){const e=[["",this]];for(;e.length;){const[t,s]=e.pop();s.vals?yield*i.map(e=>[t,e],s.vals):s.queueChildren(e,t)}}*keys(e="",t=""){const s=[[t,this]];for(;s.length;){const[t,r]=s.pop();r.vals?yield t:r.queueChildren(s,t,e)}}*values(){const e=[this];for(;e.length;){const t=e.pop();t.vals?yield*t.vals:e.push(...i.vals(t.next))}}clear(){this.next={},this.n=0,this.vals=void 0}has(e){return!!this.get(e)}hasPrefix(e){return!!this.find(e)}*suffixes(e,t=!1){const s=this.find(e);s&&(yield*s.keys("",t?e.toString():""))}get(e){const t=this.find(e);return t?t.vals:void 0}find(e){let t=this;for(let s=0,r=e.length;s<r;s++)if(t=t.next[e[s].toString()],!t)return;return t}knownPrefix(e){let t=this;const s=[];for(let r=0,n=e.length;r<n;r++){const n=e[r].toString(),i=t.next[n];if(!i)break;s.push(n),t=i}return s}hasKnownPrefix(e){return this.knownPrefix(e).length>0}add(e,t){let s=this;for(let t=0,r=e.length;t<r;t++){const r=e[t].toString(),n=s.next[r];s=n||(s.n++,s.next[r]=this.makeChild())}s.vals||(s.vals=this.makeValueSet()),s.vals.add(t)}delete(e,t){const s=e.length;if(s<1)return!1;const r=[],n=[];let i=0,o=this;for(;i<s;i++){const t=e[i].toString();if(n.push(t),r.push(o),o=o.next[t],!o)return!1}if(void 0!==t){const e=o.vals;if(!e||!e.has(t))return!1;if(e.delete(t),e.size>0)return!0}for(;(o=r[--i])&&(delete o.next[n[i]],!--o.n););return!0}makeChild(){return new ie}makeValueSet(){return new Set}queueChildren(e,t,s=""){t=t.length?t+s:t,e.push(...i.map(e=>[t+e,this.next[e]],Object.keys(this.next)))}}const oe=(e,t,s)=>{if(e.size<t.size){const s=e;e=t,t=s}return s=s?S(s,e):M(e,Set),e===t?s:S(s,t)};e.SparseSet16=re,e.SparseSet32=ne,e.SparseSet8=se,e.Trie=ie,e.commonKeysMap=(e,t,s=[])=>{for(let r of e.keys())t.has(r)&&s.push(r);return s},e.commonKeysObj=w,e.defArraySet=(t,s)=>new e.ArraySet(t,s),e.defEquivMap=function(t,s){return new e.EquivMap(n.isPlainObject(t)?i.pairs(t):t,s)},e.defHashMap=function(t,s){if(n.isPlainObject(t)){const r=Object.keys(t);return new e.HashMap(i.map(e=>[e,t[e]],r),Object.assign({cap:r.length/(s.load||.75)},s))}return new e.HashMap(t,s)},e.defLLSet=(t,s)=>new e.LLSet(t,s),e.defSortedMap=function(t,s){if(n.isPlainObject(t)){const r=Object.keys(t);return new e.SortedMap(i.map(e=>[e,t[e]],r),Object.assign({capacity:r.length},s))}return new e.SortedMap(t,s)},e.defSortedSet=(t,s)=>new e.SortedSet(t,s),e.defSparseSet=e=>e<=256?new se(e):e<=65536?new re(e):new ne(e),e.difference=j,e.differenceR=function e(t){return q(e,j,t)},e.dissoc=l,e.dissocObj=(e,t)=>{for(let s of t)delete e[s];return e},e.indexed=L,e.intersection=R,e.intersectionR=function e(t){return q(e,R,t)},e.into=S,e.invertMap=(e,t)=>{t=t||new Map;for(let s of e)t.set(s[1],s[0]);return t},e.invertObj=U,e.join=(e,t)=>{if(e.size&&t.size){const s=w(x(e)||{},x(t)||{});let r,n;e.size<=t.size?(r=e,n=t):(r=t,n=e);const i=L(r,s),o=k(e,Set);for(let e of n){const t=i.get(T(e,s));if(t)for(let s of t)o.add(W(Object.assign({},s),e))}return o}return k(e,Set)},e.joinWith=F,e.meldApplyObj=N,e.meldDeepObj=I,e.meldObjWith=B,e.mergeApplyMap=(e,t)=>{const s=M(e,Map);for(let[e,r]of t)s.set(e,n.isFunction(r)?r(s.get(e)):r);return s},e.mergeApplyObj=(e,t)=>N(Object.assign({},e),t),e.mergeDeepObj=G,e.mergeMap=(e,...t)=>{for(let s of t)if(null!=s)for(let t of s)e.set(t[0],t[1]);return e},e.mergeMapWith=(e,t,...s)=>{const r=M(t,Map);for(let t of s)if(null!=t)for(let[s,n]of t)r.set(s,r.has(s)?e(r.get(s),n):n);return r},e.mergeObj=W,e.mergeObjWith=V,e.renameKeysMap=(e,t,s)=>{s=s||k(e,Map);for(let[r,n]of e)s.set(t.has(r)?t.get(r):r,n);return s},e.renameKeysObj=C,e.selectKeysMap=(e,t)=>{const s=k(e,Map);for(let r of t)e.has(r)&&s.set(r,e.get(r));return s},e.selectKeysObj=T,e.union=oe,e.unionR=function e(t){return q(e,oe,t)},e.withoutKeysMap=(e,t)=>{const s=O(t),r=k(e,Map);for(let t of e.entries()){const e=t[0];!s.has(e)&&r.set(e,t[1])}return r},e.withoutKeysObj=(e,t)=>{const s=O(t),r={};for(let t in e)e.hasOwnProperty(t)&&!s.has(t)&&(r[t]=e[t]);return r},Object.defineProperty(e,"__esModule",{value:!0})})); |
{ | ||
"name": "@thi.ng/associative", | ||
"version": "4.4.1", | ||
"version": "4.5.0", | ||
"description": "Alternative Map and Set implementations with customizable equality semantics & supporting operations", | ||
@@ -97,3 +97,3 @@ "module": "./index.js", | ||
}, | ||
"gitHead": "775cdb99da136625e4633e3efdc0aa15ea7a3917" | ||
"gitHead": "75eb7c46c342cf6dfccdb8745a0191a991ca619d" | ||
} |
@@ -175,3 +175,3 @@ <!-- This file is generated - DO NOT EDIT! --> | ||
Package sizes (gzipped, pre-treeshake): ESM: 5.84 KB / CJS: 6.02 KB / UMD: 5.82 KB | ||
Package sizes (gzipped, pre-treeshake): ESM: 5.90 KB / CJS: 6.08 KB / UMD: 5.88 KB | ||
@@ -178,0 +178,0 @@ ## Dependencies |
@@ -15,2 +15,10 @@ import type { IObjectOf } from "@thi.ng/api"; | ||
find(key: K): Trie<K, T> | undefined; | ||
/** | ||
* Returns longest known prefix for `key` as array. If array is | ||
* empty, the given key has no partial matches. | ||
* | ||
* @param key | ||
*/ | ||
knownPrefix(key: K): K[]; | ||
hasKnownPrefix(key: K): boolean; | ||
add(key: K, val: T): void; | ||
@@ -17,0 +25,0 @@ delete(prefix: K, val?: T): boolean; |
22
trie.js
@@ -73,2 +73,24 @@ import { map, vals } from "@thi.ng/transducers"; | ||
} | ||
/** | ||
* Returns longest known prefix for `key` as array. If array is | ||
* empty, the given key has no partial matches. | ||
* | ||
* @param key | ||
*/ | ||
knownPrefix(key) { | ||
let node = this; | ||
const prefix = []; | ||
for (let i = 0, n = key.length; i < n; i++) { | ||
const k = key[i].toString(); | ||
const next = node.next[k]; | ||
if (!next) | ||
break; | ||
prefix.push(k); | ||
node = next; | ||
} | ||
return prefix; | ||
} | ||
hasKnownPrefix(key) { | ||
return this.knownPrefix(key).length > 0; | ||
} | ||
add(key, val) { | ||
@@ -75,0 +97,0 @@ let node = this; |
Sorry, the diff of this file is not supported yet
Sorry, the diff of this file is not supported yet
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
License Policy Violation
LicenseThis package is not allowed per your license policy. Review the package's license to ensure compliance.
Found 1 instance in 1 package
310149
4523