(function(h,c){typeof exports=="object"&&typeof module<"u"?module.exports=c():typeof define=="function"&&define.amd?define(c):(h=typeof globalThis<"u"?globalThis:h||self,h.SplayTree=c())})(this,(function(){"use strict";class h{constructor(t,e){this.next=null,this.key=t,this.data=e,this.left=null,this.right=null}}function c(n,t){return n>t?1:n<t?-1:0}function u(n,t,e){const r=new h(null,null);let i=r,l=r;for(;;){const o=e(n,t.key);if(o<0){if(t.left===null)break;if(e(n,t.left.key)<0){const s=t.left;if(t.left=s.right,s.right=t,t=s,t.left===null)break}l.left=t,l=t,t=t.left}else if(o>0){if(t.right===null)break;if(e(n,t.right.key)>0){const s=t.right;if(t.right=s.left,s.left=t,t=s,t.right===null)break}i.right=t,i=t,t=t.right}else break}return i.right=t.left,l.left=t.right,t.left=r.right,t.right=r.left,t}function _(n,t,e,r){const i=new h(n,t);if(e===null)return i.left=i.right=null,i;e=u(n,e,r);const l=r(n,e.key);return l<0?(i.left=e.left,i.right=e,e.left=null):l>=0&&(i.right=e.right,i.left=e,e.right=null),i}function d(n,t,e){let r=null,i=null;if(t){t=u(n,t,e);const l=e(t.key,n);l===0?(r=t.left,i=t.right):l<0?(i=t.right,t.right=null,r=t):(r=t.left,t.left=null,i=t)}return{left:r,right:i}}function w(n,t,e){return t===null?n:(n===null||(t=u(n.key,t,e),t.left=n),t)}function a(n,t,e,r,i){if(n){r(`${t}${e?"└── ":"├── "}${i(n)}
`);const l=t+(e?"    ":"│   ");n.left&&a(n.left,l,!1,r,i),n.right&&a(n.right,l,!0,r,i)}}class x{constructor(t=c){this._root=null,this._size=0,this._comparator=t}insert(t,e){return this._size++,this._root=_(t,e,this._root,this._comparator)}add(t,e){const r=new h(t,e);this._root===null&&(r.left=r.right=null,this._size++,this._root=r);const i=this._comparator,l=u(t,this._root,i),o=i(t,l.key);return o===0?this._root=l:(o<0?(r.left=l.left,r.right=l,l.left=null):o>0&&(r.right=l.right,r.left=l,l.right=null),this._size++,this._root=r),this._root}remove(t){this._root=this._remove(t,this._root,this._comparator)}_remove(t,e,r){let i;return e===null?null:(e=u(t,e,r),r(t,e.key)===0?(e.left===null?i=e.right:(i=u(t,e.left,r),i.right=e.right),this._size--,i):e)}pop(){let t=this._root;if(t){for(;t.left;)t=t.left;return this._root=u(t.key,this._root,this._comparator),this._root=this._remove(t.key,this._root,this._comparator),{key:t.key,data:t.data}}return null}findStatic(t){let e=this._root;const r=this._comparator;for(;e;){const i=r(t,e.key);if(i===0)return e;i<0?e=e.left:e=e.right}return null}find(t){return this._root&&(this._root=u(t,this._root,this._comparator),this._comparator(t,this._root.key)!==0)?null:this._root}contains(t){let e=this._root;const r=this._comparator;for(;e;){const i=r(t,e.key);if(i===0)return!0;i<0?e=e.left:e=e.right}return!1}forEach(t,e){let r=this._root;const i=[];let l=!1;for(;!l;)r!==null?(i.push(r),r=r.left):i.length!==0?(r=i.pop(),t.call(e,r),r=r.right):l=!0;return this}range(t,e,r,i){const l=[],o=this._comparator;let s=this._root,f;for(;l.length!==0||s;)if(s)l.push(s),s=s.left;else{if(s=l.pop(),f=o(s.key,e),f>0)break;if(o(s.key,t)>=0&&r.call(i,s))return this;s=s.right}return this}keys(){const t=[];return this.forEach(({key:e})=>{t.push(e)}),t}values(){const t=[];return this.forEach(({data:e})=>{t.push(e)}),t}min(){return this._root?this.minNode(this._root).key:null}max(){return this._root?this.maxNode(this._root).key:null}minNode(t=this._root){if(t)for(;t.left;)t=t.left;return t}maxNode(t=this._root){if(t)for(;t.right;)t=t.right;return t}at(t){let e=this._root,r=!1,i=0;const l=[];for(;!r;)if(e)l.push(e),e=e.left;else if(l.length>0){if(e=l.pop(),i===t)return e;i++,e=e.right}else r=!0;return null}next(t){let e=this._root,r=null;if(t.right){for(r=t.right;r.left;)r=r.left;return r}const i=this._comparator;for(;e;){const l=i(t.key,e.key);if(l===0)break;l<0?(r=e,e=e.left):e=e.right}return r}prev(t){let e=this._root,r=null;if(t.left!==null){for(r=t.left;r.right;)r=r.right;return r}const i=this._comparator;for(;e;){const l=i(t.key,e.key);if(l===0)break;l<0?e=e.left:(r=e,e=e.right)}return r}clear(){return this._root=null,this._size=0,this}toList(){return y(this._root)}load(t,e=[],r=!1){let i=t.length;const l=this._comparator;if(r&&m(t,e,0,i-1,l),this._root===null)this._root=p(t,e,0,i),this._size=i;else{const o=z(this.toList(),k(t,e),l);i=this._size+i,this._root=g({head:o},0,i)}return this}isEmpty(){return this._root===null}get size(){return this._size}get root(){return this._root}toString(t=e=>String(e.key)){const e=[];return a(this._root,"",!0,r=>e.push(r),t),e.join("")}update(t,e,r){const i=this._comparator;let{left:l,right:o}=d(t,this._root,i);i(t,e)<0?o=_(e,r,o,i):l=_(e,r,l,i),this._root=w(l,o,i)}split(t){return d(t,this._root,this._comparator)}*[Symbol.iterator](){let t=this._root;const e=[];let r=!1;for(;!r;)t!==null?(e.push(t),t=t.left):e.length!==0?(t=e.pop(),yield t,t=t.right):r=!0}}function p(n,t,e,r){const i=r-e;if(i>0){const l=e+Math.floor(i/2),o=n[l],s=t[l],f=new h(o,s);return f.left=p(n,t,e,l),f.right=p(n,t,l+1,r),f}return null}function k(n,t){const e=new h(null,null);let r=e;for(let i=0;i<n.length;i++)r=r.next=new h(n[i],t[i]);return r.next=null,e.next}function y(n){let t=n;const e=[];let r=!1;const i=new h(null,null);let l=i;for(;!r;)t?(e.push(t),t=t.left):e.length>0?(t=l=l.next=e.pop(),t=t.right):r=!0;return l.next=null,i.next}function g(n,t,e){const r=e-t;if(r>0){const i=t+Math.floor(r/2),l=g(n,t,i),o=n.head;return o.left=l,n.head=n.head.next,o.right=g(n,i+1,e),o}return null}function z(n,t,e){const r=new h(null,null);let i=r,l=n,o=t;for(;l!==null&&o!==null;)e(l.key,o.key)<0?(i.next=l,l=l.next):(i.next=o,o=o.next),i=i.next;return l!==null?i.next=l:o!==null&&(i.next=o),r.next}function m(n,t,e,r,i){if(e>=r)return;const l=n[e+r>>1];let o=e-1,s=r+1;for(;;){do o++;while(i(n[o],l)<0);do s--;while(i(n[s],l)>0);if(o>=s)break;let f=n[o];n[o]=n[s],n[s]=f,f=t[o],t[o]=t[s],t[s]=f}m(n,t,e,s,i),m(n,t,s+1,r,i)}return x}));
//# sourceMappingURL=splaytree.umd.cjs.map