🚀 Big News: Socket Acquires Coana to Bring Reachability Analysis to Every Appsec Team.Learn more →
Socket
Book a DemoInstallSign in
Socket
Book a DemoInstallSign in

@x-oasis/prefix-interval-tree

Package Overview
Dependencies
Maintainers
0
Versions
50
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@x-oasis/prefix-interval-tree - npm Package Compare versions

Comparing version

0.1.35
to
0.2.0

9

dist/index.d.ts

@@ -5,3 +5,3 @@ declare class PrefixIntervalTree {

private _heap;
private _maxUsefulLength;
private _actualSize;
private _onUpdateItemLayout;

@@ -18,5 +18,10 @@ private _onUpdateIntervalTree;

stretch(): void;
isValidIndex(index: number): boolean;
reflowHeap(startIndex: number, endIndex?: number): void;
remove(index: number): void;
set(index: number, value: number): void;
batchRemove(indices: number[]): void;
removeV0(index: number): void;
set(index: number, value: number): boolean;
getMaxUsefulLength(): number;
getActualSize(): number;
get(index: number): number;

@@ -23,0 +28,0 @@ getSize(): number;

101

dist/prefix-interval-tree.cjs.development.js

@@ -37,3 +37,3 @@ 'use strict';

this._heap = createArray(2 * this._half);
this._maxUsefulLength = 0;
this._actualSize = 0;
};

@@ -51,2 +51,3 @@ _proto.initWithArray = function initWithArray(arr) {

}
this._actualSize = arr.length;
};

@@ -76,4 +77,62 @@ PrefixIntervalTree.uniform = function uniform(size, initialValue) {

};
_proto.isValidIndex = function isValidIndex(index) {
return typeof index === 'number' && index >= 0 && index < this._actualSize;
};
_proto.reflowHeap = function reflowHeap(startIndex, endIndex) {
var _this = this;
if (endIndex === void 0) {
endIndex = this._half * 2 - 2;
}
var len = Math.log2(this._size);
Array.from({
length: len
}, function (v, i) {
return i;
}).reduce(function (acc) {
var startIndex = acc.startIndex,
endIndex = acc.endIndex;
var _nextStart = parent(startIndex);
var _nextEnd = parent(endIndex);
for (var idx = _nextStart; idx <= _nextEnd; idx++) {
_this._heap[idx] = _this._heap[2 * idx] + _this._heap[2 * idx + 1];
}
return {
startIndex: _nextStart,
endIndex: _nextEnd
};
}, {
startIndex: startIndex,
endIndex: endIndex
});
};
_proto.remove = function remove(index) {
if (typeof index !== 'number' || index >= this._maxUsefulLength) return;
this.batchRemove([index]);
};
_proto.batchRemove = function batchRemove(indices) {
var _this2 = this;
indices.sort(function (a, b) {
return a - b;
});
indices.forEach(function (index) {
if (!_this2.isValidIndex(index)) return;
if (isNaN(index)) {
console.warn('Passing a NaN value as interval tree index');
return;
}
_this2._heap.splice(_this2._half + index, 1);
_this2._heap.push(0);
_this2._actualSize = _this2._actualSize - 1;
});
this.reflowHeap(indices[0] + this._half);
if (typeof this._onUpdateIntervalTree === 'function') {
this._onUpdateIntervalTree(this._heap);
}
if (typeof this._onUpdateItemLayout === 'function') {
for (var idx = indices[0]; idx < this._half; idx++) {
this._onUpdateItemLayout(idx, this.get(idx));
}
}
};
_proto.removeV0 = function removeV0(index) {
if (!this.isValidIndex(index)) return;
if (isNaN(index)) {

@@ -92,10 +151,10 @@ console.warn('Passing a NaN value as interval tree index');

}
this._maxUsefulLength = this._maxUsefulLength - 1;
this._actualSize = this._actualSize - 1;
this._heap = nextHeap;
};
_proto.set = function set(index, value) {
if (typeof index !== 'number') return;
if (typeof index !== 'number' || index < 0) return false;
if (isNaN(index)) {
console.warn('Passing a NaN value as interval tree index');
return;
return false;
}

@@ -111,4 +170,4 @@ while (index >= this._half) {

}
if (index + 1 > this._maxUsefulLength) {
this._maxUsefulLength = index + 1;
if (index + 1 > this._actualSize) {
this._actualSize = index + 1;
}

@@ -121,6 +180,10 @@ if (typeof this._onUpdateIntervalTree === 'function') {

}
return true;
};
_proto.getMaxUsefulLength = function getMaxUsefulLength() {
return this._maxUsefulLength;
return this.getActualSize();
};
_proto.getActualSize = function getActualSize() {
return this._actualSize;
};
_proto.get = function get(index) {

@@ -167,3 +230,3 @@ var node = this._half + index;

if (this._heap[node] < t) {
return Math.max(this._maxUsefulLength - 1, 0);
return Math.max(this._actualSize - 1, 0);
}

@@ -179,3 +242,3 @@ while (node < this._half) {

}
return Math.min(node - this._half, this._maxUsefulLength - 1);
return Math.min(node - this._half, this._actualSize - 1);
};

@@ -188,3 +251,3 @@ _proto.greatestStrictLowerBound = function greatestStrictLowerBound(t) {

if (this._heap[node] < t) {
return Math.max(this._maxUsefulLength - 1, 0);
return Math.max(this._actualSize - 1, 0);
}

@@ -200,3 +263,3 @@ while (node < this._half) {

}
return Math.min(node - this._half, this._maxUsefulLength - 1);
return Math.min(node - this._half, this._actualSize - 1);
};

@@ -206,18 +269,16 @@ _proto.computeRange = function computeRange(minOffset, maxOffset) {

return {
startIndex: this._maxUsefulLength - 1,
endIndex: this._maxUsefulLength - 1
startIndex: this._actualSize,
endIndex: this._actualSize
};
}
var startIndex = this.leastStrictUpperBound(minOffset);
var endIndex = Math.min(this.leastStrictUpperBound(maxOffset), Math.max(this._maxUsefulLength - 1, 0));
return {
startIndex: endIndex >= 0 ? Math.max(startIndex, 0) : -1,
endIndex: endIndex
startIndex: this.greatestLowerBound(minOffset),
endIndex: this.leastStrictUpperBound(maxOffset)
};
};
_proto.leastUpperBound = function leastUpperBound(t) {
return this.greatestLowerBound(t) + 1;
return this.greatestStrictLowerBound(t) + 1;
};
_proto.leastStrictUpperBound = function leastStrictUpperBound(t) {
return this.greatestStrictLowerBound(t);
return this.greatestLowerBound(t) + 1;
};

@@ -224,0 +285,0 @@ return PrefixIntervalTree;

2

dist/prefix-interval-tree.cjs.production.min.js

@@ -1,2 +0,2 @@

"use strict";Object.defineProperty(exports,"__esModule",{value:!0});var t=function(t){return Math.floor(t/2)},e=function(t){for(var e=[],i=t-1;i>=0;--i)e[i]=0;return e};function i(t){for(var e=1;e<t;)e*=2;return e}exports.default=function(){function h(t,e){"number"==typeof t&&this.initWithNumber(t),Array.isArray(t)&&this.initWithArray(t);var i=e||{},h=i.onUpdateItemLayout;this._onUpdateIntervalTree=i.onUpdateIntervalTree,this._onUpdateItemLayout=h}var n=h.prototype;return n.initWithNumber=function(t){this._half=i(t),this._size=this._half,this._heap=e(2*this._half),this._maxUsefulLength=0},n.initWithArray=function(t){var h;for(this._half=i(t.length),this._size=this._half,this._heap=e(2*this._half),h=0;h<this._size;++h)this._heap[this._half+h]=t[h];for(h=this._half-1;h>0;--h)this._heap[h]=this._heap[2*h]+this._heap[2*h+1]},h.uniform=function(t,e){for(var i=[],n=t-1;n>=0;--n)i[n]=e;return new h(i)},h.empty=function(t){return h.uniform(t,0)},n.stretch=function(){for(var t=e(2*this._half*2),i=2*this._half,h=0;h<this._size;h++)t[i+h]=this._heap[this._half+h]||0;for(var n=i-1;n>0;n--)t[n]=t[2*n]+t[2*n+1];this._half=i,this._size=i,this._heap=t},n.remove=function(t){if(!("number"!=typeof t||t>=this._maxUsefulLength))if(isNaN(t))console.warn("Passing a NaN value as interval tree index");else{var i=e(2*this._half),h=this._heap.slice(this._half);h.splice(t,1);for(var n=this._half;n<2*this._half;n++)i[n]=h[n-this._half]||0;for(var a=this._half-1;a>0;a--)i[a]=i[2*a]+i[2*a+1];this._maxUsefulLength=this._maxUsefulLength-1,this._heap=i}},n.set=function(e,i){if("number"==typeof e)if(isNaN(e))console.warn("Passing a NaN value as interval tree index");else{for(;e>=this._half;)this.stretch();var h=this._half+e;for(this._heap[h]=i,h=t(h);0!==h;h=t(h))this._heap[h]=this._heap[2*h]+this._heap[2*h+1];e+1>this._maxUsefulLength&&(this._maxUsefulLength=e+1),"function"==typeof this._onUpdateIntervalTree&&this._onUpdateIntervalTree(this._heap),"function"==typeof this._onUpdateItemLayout&&this._onUpdateItemLayout(e,i)}},n.getMaxUsefulLength=function(){return this._maxUsefulLength},n.get=function(t){return this._heap[this._half+t]},n.getSize=function(){return this._size},n.getHalf=function(){return this._half},n.getHeap=function(){return this._heap},n.getMaxValue=function(){return this._heap[1]},n.sumUntil=function(e){if(e<=0)return 0;for(var i=this._half+e-1,h=this._heap[i];1!==i;i=t(i))i%2==1&&(h+=this._heap[i-1]);return h},n.sumTo=function(t){return this.sumUntil(t+1)},n.sum=function(t,e){return this.sumUntil(e)-this.sumUntil(t)},n.greatestLowerBound=function(t){if(t<0)return-1;var e=1;if(this._heap[e]<t)return Math.max(this._maxUsefulLength-1,0);for(;e<this._half;){var i=this._heap[2*e];t<i?e*=2:(e=2*e+1,t-=i)}return Math.min(e-this._half,this._maxUsefulLength-1)},n.greatestStrictLowerBound=function(t){if(t<=0)return-1;var e=1;if(this._heap[e]<t)return Math.max(this._maxUsefulLength-1,0);for(;e<this._half;){var i=this._heap[2*e];t<=i?e*=2:(e=2*e+1,t-=i)}return Math.min(e-this._half,this._maxUsefulLength-1)},n.computeRange=function(t,e){if(this.getHeap()[1]<t)return{startIndex:this._maxUsefulLength-1,endIndex:this._maxUsefulLength-1};var i=this.leastStrictUpperBound(t),h=Math.min(this.leastStrictUpperBound(e),Math.max(this._maxUsefulLength-1,0));return{startIndex:h>=0?Math.max(i,0):-1,endIndex:h}},n.leastUpperBound=function(t){return this.greatestLowerBound(t)+1},n.leastStrictUpperBound=function(t){return this.greatestStrictLowerBound(t)},h}();
"use strict";Object.defineProperty(exports,"__esModule",{value:!0});var t=function(t){return Math.floor(t/2)},e=function(t){for(var e=[],i=t-1;i>=0;--i)e[i]=0;return e};function i(t){for(var e=1;e<t;)e*=2;return e}exports.default=function(){function a(t,e){"number"==typeof t&&this.initWithNumber(t),Array.isArray(t)&&this.initWithArray(t);var i=e||{},a=i.onUpdateItemLayout;this._onUpdateIntervalTree=i.onUpdateIntervalTree,this._onUpdateItemLayout=a}var n=a.prototype;return n.initWithNumber=function(t){this._half=i(t),this._size=this._half,this._heap=e(2*this._half),this._actualSize=0},n.initWithArray=function(t){var a;for(this._half=i(t.length),this._size=this._half,this._heap=e(2*this._half),a=0;a<this._size;++a)this._heap[this._half+a]=t[a];for(a=this._half-1;a>0;--a)this._heap[a]=this._heap[2*a]+this._heap[2*a+1];this._actualSize=t.length},a.uniform=function(t,e){for(var i=[],n=t-1;n>=0;--n)i[n]=e;return new a(i)},a.empty=function(t){return a.uniform(t,0)},n.stretch=function(){for(var t=e(2*this._half*2),i=2*this._half,a=0;a<this._size;a++)t[i+a]=this._heap[this._half+a]||0;for(var n=i-1;n>0;n--)t[n]=t[2*n]+t[2*n+1];this._half=i,this._size=i,this._heap=t},n.isValidIndex=function(t){return"number"==typeof t&&t>=0&&t<this._actualSize},n.reflowHeap=function(e,i){var a=this;void 0===i&&(i=2*this._half-2);var n=Math.log2(this._size);Array.from({length:n},(function(t,e){return e})).reduce((function(e){for(var i=e.endIndex,n=t(e.startIndex),h=t(i),r=n;r<=h;r++)a._heap[r]=a._heap[2*r]+a._heap[2*r+1];return{startIndex:n,endIndex:h}}),{startIndex:e,endIndex:i})},n.remove=function(t){this.batchRemove([t])},n.batchRemove=function(t){var e=this;if(t.sort((function(t,e){return t-e})),t.forEach((function(t){e.isValidIndex(t)&&(isNaN(t)?console.warn("Passing a NaN value as interval tree index"):(e._heap.splice(e._half+t,1),e._heap.push(0),e._actualSize=e._actualSize-1))})),this.reflowHeap(t[0]+this._half),"function"==typeof this._onUpdateIntervalTree&&this._onUpdateIntervalTree(this._heap),"function"==typeof this._onUpdateItemLayout)for(var i=t[0];i<this._half;i++)this._onUpdateItemLayout(i,this.get(i))},n.removeV0=function(t){if(this.isValidIndex(t))if(isNaN(t))console.warn("Passing a NaN value as interval tree index");else{var i=e(2*this._half),a=this._heap.slice(this._half);a.splice(t,1);for(var n=this._half;n<2*this._half;n++)i[n]=a[n-this._half]||0;for(var h=this._half-1;h>0;h--)i[h]=i[2*h]+i[2*h+1];this._actualSize=this._actualSize-1,this._heap=i}},n.set=function(e,i){if("number"!=typeof e||e<0)return!1;if(isNaN(e))return console.warn("Passing a NaN value as interval tree index"),!1;for(;e>=this._half;)this.stretch();var a=this._half+e;for(this._heap[a]=i,a=t(a);0!==a;a=t(a))this._heap[a]=this._heap[2*a]+this._heap[2*a+1];return e+1>this._actualSize&&(this._actualSize=e+1),"function"==typeof this._onUpdateIntervalTree&&this._onUpdateIntervalTree(this._heap),"function"==typeof this._onUpdateItemLayout&&this._onUpdateItemLayout(e,i),!0},n.getMaxUsefulLength=function(){return this.getActualSize()},n.getActualSize=function(){return this._actualSize},n.get=function(t){return this._heap[this._half+t]},n.getSize=function(){return this._size},n.getHalf=function(){return this._half},n.getHeap=function(){return this._heap},n.getMaxValue=function(){return this._heap[1]},n.sumUntil=function(e){if(e<=0)return 0;for(var i=this._half+e-1,a=this._heap[i];1!==i;i=t(i))i%2==1&&(a+=this._heap[i-1]);return a},n.sumTo=function(t){return this.sumUntil(t+1)},n.sum=function(t,e){return this.sumUntil(e)-this.sumUntil(t)},n.greatestLowerBound=function(t){if(t<0)return-1;var e=1;if(this._heap[e]<t)return Math.max(this._actualSize-1,0);for(;e<this._half;){var i=this._heap[2*e];t<i?e*=2:(e=2*e+1,t-=i)}return Math.min(e-this._half,this._actualSize-1)},n.greatestStrictLowerBound=function(t){if(t<=0)return-1;var e=1;if(this._heap[e]<t)return Math.max(this._actualSize-1,0);for(;e<this._half;){var i=this._heap[2*e];t<=i?e*=2:(e=2*e+1,t-=i)}return Math.min(e-this._half,this._actualSize-1)},n.computeRange=function(t,e){return this.getHeap()[1]<t?{startIndex:this._actualSize,endIndex:this._actualSize}:{startIndex:this.greatestLowerBound(t),endIndex:this.leastStrictUpperBound(e)}},n.leastUpperBound=function(t){return this.greatestStrictLowerBound(t)+1},n.leastStrictUpperBound=function(t){return this.greatestLowerBound(t)+1},a}();
//# sourceMappingURL=prefix-interval-tree.cjs.production.min.js.map

101

dist/prefix-interval-tree.esm.js

@@ -33,3 +33,3 @@ var parent = function parent(node) {

this._heap = createArray(2 * this._half);
this._maxUsefulLength = 0;
this._actualSize = 0;
};

@@ -47,2 +47,3 @@ _proto.initWithArray = function initWithArray(arr) {

}
this._actualSize = arr.length;
};

@@ -72,4 +73,62 @@ PrefixIntervalTree.uniform = function uniform(size, initialValue) {

};
_proto.isValidIndex = function isValidIndex(index) {
return typeof index === 'number' && index >= 0 && index < this._actualSize;
};
_proto.reflowHeap = function reflowHeap(startIndex, endIndex) {
var _this = this;
if (endIndex === void 0) {
endIndex = this._half * 2 - 2;
}
var len = Math.log2(this._size);
Array.from({
length: len
}, function (v, i) {
return i;
}).reduce(function (acc) {
var startIndex = acc.startIndex,
endIndex = acc.endIndex;
var _nextStart = parent(startIndex);
var _nextEnd = parent(endIndex);
for (var idx = _nextStart; idx <= _nextEnd; idx++) {
_this._heap[idx] = _this._heap[2 * idx] + _this._heap[2 * idx + 1];
}
return {
startIndex: _nextStart,
endIndex: _nextEnd
};
}, {
startIndex: startIndex,
endIndex: endIndex
});
};
_proto.remove = function remove(index) {
if (typeof index !== 'number' || index >= this._maxUsefulLength) return;
this.batchRemove([index]);
};
_proto.batchRemove = function batchRemove(indices) {
var _this2 = this;
indices.sort(function (a, b) {
return a - b;
});
indices.forEach(function (index) {
if (!_this2.isValidIndex(index)) return;
if (isNaN(index)) {
console.warn('Passing a NaN value as interval tree index');
return;
}
_this2._heap.splice(_this2._half + index, 1);
_this2._heap.push(0);
_this2._actualSize = _this2._actualSize - 1;
});
this.reflowHeap(indices[0] + this._half);
if (typeof this._onUpdateIntervalTree === 'function') {
this._onUpdateIntervalTree(this._heap);
}
if (typeof this._onUpdateItemLayout === 'function') {
for (var idx = indices[0]; idx < this._half; idx++) {
this._onUpdateItemLayout(idx, this.get(idx));
}
}
};
_proto.removeV0 = function removeV0(index) {
if (!this.isValidIndex(index)) return;
if (isNaN(index)) {

@@ -88,10 +147,10 @@ console.warn('Passing a NaN value as interval tree index');

}
this._maxUsefulLength = this._maxUsefulLength - 1;
this._actualSize = this._actualSize - 1;
this._heap = nextHeap;
};
_proto.set = function set(index, value) {
if (typeof index !== 'number') return;
if (typeof index !== 'number' || index < 0) return false;
if (isNaN(index)) {
console.warn('Passing a NaN value as interval tree index');
return;
return false;
}

@@ -107,4 +166,4 @@ while (index >= this._half) {

}
if (index + 1 > this._maxUsefulLength) {
this._maxUsefulLength = index + 1;
if (index + 1 > this._actualSize) {
this._actualSize = index + 1;
}

@@ -117,6 +176,10 @@ if (typeof this._onUpdateIntervalTree === 'function') {

}
return true;
};
_proto.getMaxUsefulLength = function getMaxUsefulLength() {
return this._maxUsefulLength;
return this.getActualSize();
};
_proto.getActualSize = function getActualSize() {
return this._actualSize;
};
_proto.get = function get(index) {

@@ -163,3 +226,3 @@ var node = this._half + index;

if (this._heap[node] < t) {
return Math.max(this._maxUsefulLength - 1, 0);
return Math.max(this._actualSize - 1, 0);
}

@@ -175,3 +238,3 @@ while (node < this._half) {

}
return Math.min(node - this._half, this._maxUsefulLength - 1);
return Math.min(node - this._half, this._actualSize - 1);
};

@@ -184,3 +247,3 @@ _proto.greatestStrictLowerBound = function greatestStrictLowerBound(t) {

if (this._heap[node] < t) {
return Math.max(this._maxUsefulLength - 1, 0);
return Math.max(this._actualSize - 1, 0);
}

@@ -196,3 +259,3 @@ while (node < this._half) {

}
return Math.min(node - this._half, this._maxUsefulLength - 1);
return Math.min(node - this._half, this._actualSize - 1);
};

@@ -202,18 +265,16 @@ _proto.computeRange = function computeRange(minOffset, maxOffset) {

return {
startIndex: this._maxUsefulLength - 1,
endIndex: this._maxUsefulLength - 1
startIndex: this._actualSize,
endIndex: this._actualSize
};
}
var startIndex = this.leastStrictUpperBound(minOffset);
var endIndex = Math.min(this.leastStrictUpperBound(maxOffset), Math.max(this._maxUsefulLength - 1, 0));
return {
startIndex: endIndex >= 0 ? Math.max(startIndex, 0) : -1,
endIndex: endIndex
startIndex: this.greatestLowerBound(minOffset),
endIndex: this.leastStrictUpperBound(maxOffset)
};
};
_proto.leastUpperBound = function leastUpperBound(t) {
return this.greatestLowerBound(t) + 1;
return this.greatestStrictLowerBound(t) + 1;
};
_proto.leastStrictUpperBound = function leastStrictUpperBound(t) {
return this.greatestStrictLowerBound(t);
return this.greatestLowerBound(t) + 1;
};

@@ -220,0 +281,0 @@ return PrefixIntervalTree;

5

package.json
{
"name": "@x-oasis/prefix-interval-tree",
"version": "0.1.35",
"version": "0.2.0",
"description": "prefix interval tree function",

@@ -13,2 +13,5 @@ "main": "dist/index.js",

],
"publishConfig": {
"access": "public"
},
"author": "",

@@ -15,0 +18,0 @@ "license": "ISC",

56

README.md

@@ -19,2 +19,58 @@ # @x-oasis/prefix-interval-tree

$ pnpm test
```
# API
## PrefixIntervalTree Constructor
```ts
const intervalTree = new PrefixIntervalTree([2,5,7])
const intervalTree = new PrefixIntervalTree(10)
```
Total interval tree array length is power of `2`, such as 8, 16, 32; and the input length value means the half size, which means `10` will result in `2^4 = 16` first, then patch on interval tree, it will be total `2 * 16 = 32`.
## getActualSize
Basically, interval tree's size is this._half, they all have default `0` value. when you want to get the actual size which has been set with value, then call this method.
## get(index: number)
```ts
get(index: number): number
```
get the index value
## set(index: number)
```ts
set (index: number): boolean
```
To update the index value in interval tree, its parent will be updated as accordingly.
## computeRange(minValue: number, maxValue: number)
```ts
computeRange(minValue: number, maxValue: number): {
startIndex: number
endIndex: number
}
```
- `startIndex`: the biggest index less than or equal minValue;
- `endIndex`: the smallest index greater than maxValue;
when using the return value, endIndex item should not be included.
```ts
const arr = []
const intervalTree = new PrefixIntervalTree(arr)
const { startIndex, endIndex } = intervalTree.computeRange(100, 200);
const itemsInViewport = arr.slice(startIndex, endIndex)
```

151

src/index.ts

@@ -1,3 +0,1 @@

// import invariant from 'invariant';
const parent = (node: number) => Math.floor(node / 2);

@@ -48,3 +46,3 @@

private _maxUsefulLength: number;
private _actualSize: number;

@@ -73,3 +71,3 @@ private _onUpdateItemLayout: Function;

this._heap = createArray(2 * this._half);
this._maxUsefulLength = 0;
this._actualSize = 0;
}

@@ -81,3 +79,2 @@

this._heap = createArray(2 * this._half);
// this._maxUsefulLength = arr.length;
let i;

@@ -91,2 +88,3 @@ for (i = 0; i < this._size; ++i) {

}
this._actualSize = arr.length;
}

@@ -107,2 +105,5 @@

/**
* the length should be 2
*/
stretch() {

@@ -127,5 +128,67 @@ const nextHeap = createArray(2 * this._half * 2);

isValidIndex(index: number) {
return typeof index === 'number' && index >= 0 && index < this._actualSize;
}
reflowHeap(startIndex: number, endIndex = this._half * 2 - 2) {
const len = Math.log2(this._size);
Array.from({ length: len }, (v, i) => i).reduce(
(acc) => {
const { startIndex, endIndex } = acc;
const _nextStart = parent(startIndex);
const _nextEnd = parent(endIndex);
for (let idx = _nextStart; idx <= _nextEnd; idx++) {
this._heap[idx] = this._heap[2 * idx] + this._heap[2 * idx + 1];
}
return {
startIndex: _nextStart,
endIndex: _nextEnd,
};
},
{
startIndex,
endIndex,
}
);
}
remove(index: number) {
// if typeof index === 'undefined', then it will go into looooooooop
if (typeof index !== 'number' || index >= this._maxUsefulLength) return;
this.batchRemove([index]);
}
batchRemove(indices: number[]) {
indices.sort((a, b) => a - b);
indices.forEach((index) => {
if (!this.isValidIndex(index)) return;
if (isNaN(index)) {
console.warn('Passing a NaN value as interval tree index');
return;
}
this._heap.splice(this._half + index, 1);
this._heap.push(0);
this._actualSize = this._actualSize - 1;
});
this.reflowHeap(indices[0] + this._half);
if (typeof this._onUpdateIntervalTree === 'function') {
this._onUpdateIntervalTree(this._heap);
}
if (typeof this._onUpdateItemLayout === 'function') {
for (let idx = indices[0]; idx < this._half; idx++) {
this._onUpdateItemLayout(idx, this.get(idx));
}
}
}
removeV0(index: number) {
// if typeof index === 'undefined', then it will go into looooooooop
if (!this.isValidIndex(index)) return;
if (isNaN(index)) {

@@ -139,2 +202,3 @@ console.warn('Passing a NaN value as interval tree index');

copy.splice(index, 1);
for (let index = this._half; index < this._half * 2; index++) {

@@ -148,3 +212,3 @@ nextHeap[index] = copy[index - this._half] || 0;

this._maxUsefulLength = this._maxUsefulLength - 1;
this._actualSize = this._actualSize - 1;
this._heap = nextHeap;

@@ -154,7 +218,6 @@ }

set(index: number, value: number) {
// if typeof index === 'undefined', then it will go into looooooooop
if (typeof index !== 'number') return;
if (typeof index !== 'number' || index < 0) return false;
if (isNaN(index)) {
console.warn('Passing a NaN value as interval tree index');
return;
return false;
}

@@ -174,4 +237,4 @@

if (index + 1 > this._maxUsefulLength) {
this._maxUsefulLength = index + 1;
if (index + 1 > this._actualSize) {
this._actualSize = index + 1;
}

@@ -186,11 +249,15 @@

}
return true;
}
getMaxUsefulLength() {
return this._maxUsefulLength;
return this.getActualSize();
}
getActualSize() {
return this._actualSize;
}
get(index: number) {
// invariant(index >= 0 && index < this._size, 'Index out of range %s', index);
const node = this._half + index;

@@ -253,2 +320,3 @@ return this._heap[node];

* Returns the sum get(begin) + get(begin + 1) + ... + get(end - 1).
* end length is not included
*/

@@ -261,4 +329,4 @@ sum(begin: number, end: number) {

/**
* Returns the smallest i such that 0 <= i <= size and sumUntil(i) <= t, or
* -1 if no such i exists.
* return the biggest i, sumUntil(i) === t
* return the biggest i, subUntil(i) < t
*/

@@ -273,10 +341,5 @@ greatestLowerBound(t: number) {

// not use this._size；this._size always be a big value
return Math.max(this._maxUsefulLength - 1, 0);
return Math.max(this._actualSize - 1, 0);
}
// 这种写法的结果就是，如果中间一个item的length为0的话，那么它会一直往右边查；
// 比如初始化的时候是[0, 0, 0, 0, 0, 0, 0, 0]；
// 你会发现node最后会是7，this._half为4；最终即使data没有数据，那么它的index算出来的也是
// 7 - 4 = 3；所以，考虑到会存在一些item length为0的情况，所以，这个其实是比较合理的方式，
// 拿右边的
while (node < this._half) {

@@ -291,8 +354,9 @@ const leftSum = this._heap[2 * node];

}
return Math.min(node - this._half, this._maxUsefulLength - 1);
return Math.min(node - this._half, this._actualSize - 1);
}
/**
* Returns the smallest i such that 0 <= i <= size and sumUntil(i) < t, or
* -1 if no such i exists.
* Return the biggest i, subUntil(i) < t
* or -1 if no such i exists.
*/

@@ -306,3 +370,3 @@ greatestStrictLowerBound(t: number) {

if (this._heap[node] < t) {
return Math.max(this._maxUsefulLength - 1, 0);
return Math.max(this._actualSize - 1, 0);
}

@@ -320,3 +384,3 @@

return Math.min(node - this._half, this._maxUsefulLength - 1);
return Math.min(node - this._half, this._actualSize - 1);
}

@@ -331,5 +395,8 @@

* pending issue:
* when item with length list [100, 100, 100, 100, 100].
* this.leastStrictUpperBound(330) = 3
* this.leastStrictUpperBound(400) = 3 (should be 4....)
* when item with length list [100, 0, 100, 0, 0, 100].
* then computeRange(100, 200) => { startIndex: 2, endIndex: 6 }
*
* item index in viewport will be [2, 3, 4, 5], index 6 is not
* included just like Array.slice(start, end)
*
*/

@@ -339,17 +406,13 @@ computeRange(minOffset: number, maxOffset: number) {

return {
startIndex: this._maxUsefulLength - 1,
endIndex: this._maxUsefulLength - 1,
startIndex: this._actualSize,
endIndex: this._actualSize,
};
}
const startIndex = this.leastStrictUpperBound(minOffset);
// end的话，需要把index + 1，这样才能够把自个也加进去
const endIndex = Math.min(
this.leastStrictUpperBound(maxOffset),
Math.max(this._maxUsefulLength - 1, 0)
);
return {
// the biggest item, value <= minOffset
startIndex: this.greatestLowerBound(minOffset),
return {
startIndex: endIndex >= 0 ? Math.max(startIndex, 0) : -1,
endIndex,
// the smallest item, value > maxOffset
endIndex: this.leastStrictUpperBound(maxOffset),
};

@@ -363,11 +426,11 @@ }

leastUpperBound(t: number) {
return this.greatestLowerBound(t) + 1;
return this.greatestStrictLowerBound(t) + 1;
}
/**
* Returns the smallest i such that 0 <= i <= size and t < sumUntil(i), or
* Returns the smallest i, t < sumUntil(i), it should be used as range end
* size + 1 if no such i exists.
*/
leastStrictUpperBound(t: number) {
return this.greatestStrictLowerBound(t);
return this.greatestLowerBound(t) + 1;
}

@@ -374,0 +437,0 @@ }

dist/prefix-interval-tree.cjs.development.js.map

Sorry, the diff of this file is not supported yet

dist/prefix-interval-tree.cjs.production.min.js.map

Sorry, the diff of this file is not supported yet

dist/prefix-interval-tree.esm.js.map

Sorry, the diff of this file is not supported yet