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

Comparing version 0.1.35 to 0.2.0

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;

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;

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

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;

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",

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)
 ```

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 @@ }

No alert changes

Improved metrics

Total package byte prevSize

94879

increased by19.73%

Lines of code

963

increased by22.99%

Number of lines in readme file

75

increased by294.74%

No dependency changes