Huge News!Announcing our $40M Series B led by Abstract Ventures.Learn More →
Socket
Sign inDemoInstall
Socket
Sign inDemoInstall

@x-oasis/integer-buffer-set

Package Overview
Dependencies
Maintainers
3
Versions
36
Alerts
File Explorer

Advanced tools

License
Socket logo

Install Socket

Detect and block malicious and high-risk dependencies

Install

@x-oasis/integer-buffer-set - npm Package Compare versions

Comparing version 0.1.19 to 0.1.20

dist/types.d.ts
src/types.ts

82

dist/index.d.ts
import Heap from '@x-oasis/heap';
declare type HeapItem = {
position: number;
value: number;
};
declare class IntegerBufferSet {
import { HeapItem, SafeRange, IntegerBufferSetProps, MetaToIndexMap, MetaToPositionMap } from './types';
export declare const defaultBufferSize = 10;
declare class IntegerBufferSet<Meta = any> {
private _size;
private _valueToPositionMap;
private _name;
private _bufferSize;
private _indexToMetaMap;
private _metaToPositionMap;
private _positionToMetaList;
private _metaToIndexMap;
private _smallValues;
private _largeValues;
private _vacantPositions;
constructor();
private _metaExtractor;
private _indexExtractor;
private _onTheFlyIndices;
private _isOnTheFlyFull;
private _isOnTheFlyFullReturnHook;
private _loopMS;
private _lastUpdatedMS;
constructor(props?: IntegerBufferSetProps<Meta>);
getSize(): number;
get indices(): any[];
getValuePosition(value: number): null | number;
getNewPositionForValue(value: number): number;
get bufferSize(): number;
setIsOnTheFlyFull(val: any): void;
get isBufferFull(): boolean;
getOnTheFlyUncriticalPosition(safeRange: SafeRange): number;
initialize(): {
smallValues: Heap<any>;
largeValues: Heap<any>;
valueToPositionObject: {};
};
getIndexMeta(index: number): Meta;
getMetaIndex(meta: Meta): number;
setMetaIndex(meta: Meta, index: number): false | MetaToIndexMap<Meta>;
deleteMetaIndex(meta: Meta): boolean;
replaceMetaToIndexMap(newMetaToIndexMap: MetaToIndexMap<Meta>): false | MetaToIndexMap<Meta>;
getIndexPosition(index: number): undefined | number;
getNewPositionForIndex(index: number): number;
getMinValue(): number;
getMaxValue(): number;
setPositionValue(position: number, value: number): void;
replaceFurthestValuePosition(lowValue: number, highValue: number, newValue: number, useMinValueFn?: (options: {
safeRange: {
lowValue: number;
highValue: number;
};
bufferSetRange: {
maxValue: number;
minValue: number;
};
currentIndex: number;
}) => boolean): null | number;
setValuePosition(value: number, position: number): void;
findPositionMeta(position: number): Meta;
rebuildHeapsWithMeta(metaToPositionMap: MetaToPositionMap<Meta>): void;
setPositionIndex(position: number, index: number): boolean;
getMetaPosition(meta: Meta): number;
replacePositionInFliedIndices(newIndex: number, safeRange: SafeRange): number;
getFliedPosition(newIndex: number, safeRange: SafeRange): any;
getPosition(newIndex: number, safeRange?: SafeRange): any;
replaceFurthestIndexPosition(newIndex: number, safeRange?: {
startIndex: number;
endIndex: number;
}): any;
_replaceFurthestIndexPosition(newIndex: number, safeRange?: {
startIndex: number;
endIndex: number;
}): any;
shuffle(): any[];
getIndices(): any[];
_pushToHeaps(position: number, value: number): void;
_setMetaPosition(meta: Meta, position: number): void;
_setMetaIndex(meta: Meta, index: number): boolean;
readyToStartNextLoop(): void;
prepare(): void;
_cleanHeaps(): void;
rebuildHeapsWithValues(arr: Array<{
position: number;
value: number;
}>): void;
_recreateHeaps(): void;

@@ -34,0 +70,0 @@ _cleanHeap(heap: Heap<HeapItem>): void;

521

dist/integer-buffer-set.cjs.development.js

@@ -8,2 +8,5 @@ 'use strict';

var Heap = _interopDefault(require('@x-oasis/heap'));
var isClamped = _interopDefault(require('@x-oasis/is-clamped'));
var invariant = _interopDefault(require('@x-oasis/invariant'));
var returnHook = _interopDefault(require('@x-oasis/return-hook'));

@@ -27,2 +30,33 @@ function _defineProperties(target, props) {

}
function _unsupportedIterableToArray(o, minLen) {
if (!o) return;
if (typeof o === "string") return _arrayLikeToArray(o, minLen);
var n = Object.prototype.toString.call(o).slice(8, -1);
if (n === "Object" && o.constructor) n = o.constructor.name;
if (n === "Map" || n === "Set") return Array.from(o);
if (n === "Arguments" || /^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(n)) return _arrayLikeToArray(o, minLen);
}
function _arrayLikeToArray(arr, len) {
if (len == null || len > arr.length) len = arr.length;
for (var i = 0, arr2 = new Array(len); i < len; i++) arr2[i] = arr[i];
return arr2;
}
function _createForOfIteratorHelperLoose(o, allowArrayLike) {
var it = typeof Symbol !== "undefined" && o[Symbol.iterator] || o["@@iterator"];
if (it) return (it = it.call(o)).next.bind(it);
if (Array.isArray(o) || (it = _unsupportedIterableToArray(o)) || allowArrayLike && o && typeof o.length === "number") {
if (it) o = it;
var i = 0;
return function () {
if (i >= o.length) return {
done: true
};
return {
done: false,
value: o[i++]
};
};
}
throw new TypeError("Invalid attempt to iterate non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.");
}
function _toPrimitive(input, hint) {

@@ -43,22 +77,39 @@ if (typeof input !== "object" || input === null) return input;

var defaultUseMinValueFn = function defaultUseMinValueFn(options) {
var safeRange = options.safeRange,
bufferSetRange = options.bufferSetRange;
var lowValue = safeRange.lowValue,
highValue = safeRange.highValue;
var maxValue = bufferSetRange.maxValue,
minValue = bufferSetRange.minValue;
return lowValue - minValue > maxValue - highValue;
var defaultMetaExtractor = function defaultMetaExtractor(value) {
return value;
};
var defaultBufferSize = 10;
var IntegerBufferSet = /*#__PURE__*/function () {
function IntegerBufferSet() {
this._valueToPositionMap = {};
function IntegerBufferSet(props) {
if (props === void 0) {
props = {};
}
var _props = props,
_props$name = _props.name,
name = _props$name === void 0 ? 'default_buffer' : _props$name,
indexExtractor = _props.indexExtractor,
_props$bufferSize = _props.bufferSize,
bufferSize = _props$bufferSize === void 0 ? defaultBufferSize : _props$bufferSize,
_props$metaExtractor = _props.metaExtractor,
metaExtractor = _props$metaExtractor === void 0 ? defaultMetaExtractor : _props$metaExtractor;
this._metaExtractor = metaExtractor;
this._indexExtractor = indexExtractor;
this._name = name;
this._indexToMetaMap = new Map();
this._metaToPositionMap = new Map();
this._positionToMetaList = [];
this._metaToIndexMap = new Map();
this._onTheFlyIndices = [];
this._size = 0;
this._bufferSize = bufferSize;
this._smallValues = new Heap([], this._smallerComparator);
this._largeValues = new Heap([], this._greaterComparator);
this.getNewPositionForValue = this.getNewPositionForValue.bind(this);
this.getValuePosition = this.getValuePosition.bind(this);
this.getNewPositionForIndex = this.getNewPositionForIndex.bind(this);
this.getIndexPosition = this.getIndexPosition.bind(this);
this.getSize = this.getSize.bind(this);
this.replaceFurthestValuePosition = this.replaceFurthestValuePosition.bind(this);
this._vacantPositions = [];
this.replacePositionInFliedIndices = this.replacePositionInFliedIndices.bind(this);
this.replaceFurthestIndexPosition = this.replaceFurthestIndexPosition.bind(this);
this._isOnTheFlyFullReturnHook = returnHook(this.setIsOnTheFlyFull.bind(this));
this._loopMS = Date.now();
this._lastUpdatedMS = this._loopMS;
}

@@ -69,16 +120,61 @@ var _proto = IntegerBufferSet.prototype;

};
_proto.getValuePosition = function getValuePosition(value) {
if (this._valueToPositionMap[value] === undefined) {
return null;
_proto.setIsOnTheFlyFull = function setIsOnTheFlyFull(val) {
if (val != null) {
var data = this._onTheFlyIndices.filter(function (v) {
return v;
});
this._isOnTheFlyFull = data.length === this._bufferSize;
}
return this._valueToPositionMap[value];
};
_proto.getNewPositionForValue = function getNewPositionForValue(value) {
if (this._valueToPositionMap[value] !== undefined) {
console.warn("Shouldn't try to find new position for value already stored in BufferSet");
_proto.getOnTheFlyUncriticalPosition = function getOnTheFlyUncriticalPosition(safeRange) {
var startIndex = safeRange.startIndex,
endIndex = safeRange.endIndex;
for (var idx = 0; idx < this._onTheFlyIndices.length; idx++) {
var meta = this._onTheFlyIndices[idx];
var metaIndex = this._metaToIndexMap.get(meta);
if (!isClamped(startIndex, metaIndex, endIndex)) {
return idx;
}
}
var newPosition = this._size;
this._size++;
this._pushToHeaps(newPosition, value);
this._valueToPositionMap[value] = newPosition;
return null;
};
_proto.initialize = function initialize() {
return {
smallValues: new Heap([], this._smallerComparator),
largeValues: new Heap([], this._greaterComparator),
valueToPositionObject: {}
};
};
_proto.getIndexMeta = function getIndexMeta(index) {
return this._metaExtractor(index);
};
_proto.getMetaIndex = function getMetaIndex(meta) {
if (this._indexExtractor) return this._indexExtractor(meta);
return this._metaToIndexMap.get(meta);
};
_proto.setMetaIndex = function setMetaIndex(meta, index) {
if (!this._indexExtractor) {
return this._metaToIndexMap.set(meta, index);
}
return false;
};
_proto.deleteMetaIndex = function deleteMetaIndex(meta) {
return this._metaToIndexMap["delete"](meta);
};
_proto.replaceMetaToIndexMap = function replaceMetaToIndexMap(newMetaToIndexMap) {
if (!this._indexExtractor) {
return this._metaToIndexMap = newMetaToIndexMap;
}
return false;
};
_proto.getIndexPosition = function getIndexPosition(index) {
return this.getMetaIndex(this.getIndexMeta(index));
};
_proto.getNewPositionForIndex = function getNewPositionForIndex(index) {
var meta = this.getIndexMeta(index);
!(this._metaToPositionMap.get(meta) === undefined) ? invariant(false, "Shouldn't try to find new position for value already stored in BufferSet") : void 0;
var newPosition = this._positionToMetaList.length;
this._pushToHeaps(newPosition, index);
this._setMetaIndex(meta, index);
this._setMetaPosition(meta, newPosition);
return newPosition;

@@ -94,63 +190,269 @@ };

};
_proto.setPositionValue = function setPositionValue(position, value) {
var originalPosition = this._valueToPositionMap[value];
_proto.setValuePosition = function setValuePosition(value, position) {};
_proto.findPositionMeta = function findPositionMeta(position) {
for (var _iterator = _createForOfIteratorHelperLoose(this._metaToPositionMap), _step; !(_step = _iterator()).done;) {
var _step$value = _step.value,
meta = _step$value[0],
pos = _step$value[1];
if (pos === position) return meta;
}
return null;
};
_proto.rebuildHeapsWithMeta = function rebuildHeapsWithMeta(metaToPositionMap) {
var _this$initialize = this.initialize(),
smallValues = _this$initialize.smallValues,
largeValues = _this$initialize.largeValues;
for (var _iterator2 = _createForOfIteratorHelperLoose(metaToPositionMap), _step2; !(_step2 = _iterator2()).done;) {
var _step2$value = _step2.value,
meta = _step2$value[0],
position = _step2$value[1];
var index = this.getMetaIndex(meta);
var token = {
index: index,
position: position
};
smallValues.push(token);
largeValues.push(token);
}
this._smallValues = smallValues;
this._largeValues = largeValues;
};
_proto.setPositionIndex = function setPositionIndex(position, index) {
var meta = this._metaExtractor(index);
var originalPosition = this._metaToPositionMap.get(meta);
if (originalPosition !== undefined) {
var index = this._vacantPositions.findIndex(function (v) {
return v === originalPosition;
});
if (index === -1) this._vacantPositions.push(originalPosition);
delete this._valueToPositionMap[value];
this._valueToPositionMap[value] = position;
if (originalPosition === position) return true;
this.deleteMetaIndex(meta);
}
var metaToReplace = this.findPositionMeta(position);
if (metaToReplace) this._metaToPositionMap["delete"](metaToReplace);
this._metaToPositionMap.set(meta, position);
this.rebuildHeapsWithMeta(this._metaToPositionMap);
return true;
};
_proto.replaceFurthestValuePosition = function replaceFurthestValuePosition(lowValue, highValue, newValue, useMinValueFn) {
if (useMinValueFn === void 0) {
useMinValueFn = defaultUseMinValueFn;
_proto.getMetaPosition = function getMetaPosition(meta) {
return this._metaToPositionMap.get(meta);
};
_proto.replacePositionInFliedIndices = function replacePositionInFliedIndices(newIndex, safeRange) {
var startIndex = safeRange.startIndex,
endIndex = safeRange.endIndex;
if (this._isOnTheFlyFull) {
if (!isClamped(startIndex, newIndex, endIndex)) {
return null;
}
var pos = this.getOnTheFlyUncriticalPosition(safeRange);
if (pos != null) return pos;
}
if (this._valueToPositionMap[newValue] !== undefined) {
console.warn("Shouldn't try to replace values with value already stored value in " + 'BufferSet');
return null;
};
_proto.getFliedPosition = function getFliedPosition(newIndex, safeRange) {
var pos = this.replacePositionInFliedIndices(newIndex, safeRange);
if (pos != null) {
var meta = this.getIndexMeta(newIndex);
this._onTheFlyIndices[pos] = meta;
this._setMetaIndex(meta, newIndex);
return this._isOnTheFlyFullReturnHook(pos);
}
this._cleanHeaps();
if (this._smallValues.empty() || this._largeValues.empty()) {
return null;
return null;
};
_proto.getPosition = function getPosition(newIndex, safeRange) {
this.prepare();
var meta = this.getIndexMeta(newIndex);
var prevMetaPosition = this._metaToPositionMap.get(meta);
if (prevMetaPosition !== undefined) {
var onTheFlyPositionMeta = this._onTheFlyIndices[prevMetaPosition];
if (onTheFlyPositionMeta) {
if (onTheFlyPositionMeta === meta) {
return prevMetaPosition;
}
var _positionToReplace = this._replaceFurthestIndexPosition(newIndex, safeRange);
if (this._isOnTheFlyFull) return this.getFliedPosition(newIndex, safeRange);
while (this._onTheFlyIndices[_positionToReplace]) {
_positionToReplace = this._replaceFurthestIndexPosition(newIndex, safeRange);
}
if (_positionToReplace != null) {
this._setMetaIndex(meta, newIndex);
this._onTheFlyIndices[_positionToReplace] = onTheFlyPositionMeta;
return this._isOnTheFlyFullReturnHook(_positionToReplace);
}
}
this._onTheFlyIndices[prevMetaPosition] = meta;
return this._isOnTheFlyFullReturnHook(prevMetaPosition);
}
if (this._vacantPositions.length) {
var _position = this._vacantPositions.pop();
this._valueToPositionMap[newValue] = _position;
this._pushToHeaps(_position, newValue);
return _position;
if (!this.isBufferFull) return this._isOnTheFlyFullReturnHook(this.getNewPositionForIndex(newIndex));
if (this._isOnTheFlyFull) return this.getFliedPosition(newIndex, safeRange);
var positionToReplace;
var prevIndexMeta = this._indexToMetaMap.get(newIndex);
if (!prevIndexMeta) {
this._cleanHeaps();
positionToReplace = this._replaceFurthestIndexPosition(newIndex, safeRange);
} else {
positionToReplace = this._metaToPositionMap.get(prevIndexMeta);
}
this._onTheFlyIndices[positionToReplace] = meta;
this._setMetaIndex(meta, newIndex);
this._setMetaPosition(meta, positionToReplace);
return this._isOnTheFlyFullReturnHook(positionToReplace);
};
_proto.replaceFurthestIndexPosition = function replaceFurthestIndexPosition(newIndex, safeRange) {
if (!this.isBufferFull) {
return this._isOnTheFlyFullReturnHook(this.getNewPositionForIndex(newIndex));
}
return this._replaceFurthestIndexPosition(newIndex, safeRange);
};
_proto._replaceFurthestIndexPosition = function _replaceFurthestIndexPosition(newIndex, safeRange) {
if (this._largeValues.empty() || this._smallValues.empty()) {
return this._isOnTheFlyFullReturnHook(this.getNewPositionForIndex(newIndex));
}
var minValue = this._smallValues.peek().value;
var maxValue = this._largeValues.peek().value;
if (minValue >= lowValue && maxValue <= highValue) {
var indexToReplace;
if (!safeRange) {
if (Math.abs(newIndex - minValue) > Math.abs(newIndex - maxValue)) {
indexToReplace = minValue;
this._smallValues.pop();
} else {
indexToReplace = maxValue;
this._largeValues.pop();
}
var _replacedMeta = this._indexToMetaMap.get(indexToReplace);
var _position = this._metaToPositionMap.get(_replacedMeta);
return _position;
}
var lowValue = safeRange.startIndex,
highValue = safeRange.endIndex;
if (isClamped(lowValue, minValue, highValue) && isClamped(lowValue, maxValue, highValue)) {
return null;
}
var valueToReplace;
if (useMinValueFn({
safeRange: {
lowValue: lowValue,
highValue: highValue
},
bufferSetRange: {
minValue: minValue,
maxValue: maxValue
},
currentIndex: newValue
})) {
valueToReplace = minValue;
} else if (isClamped(lowValue, minValue, highValue) && !isClamped(lowValue, maxValue, highValue)) {
indexToReplace = maxValue;
this._largeValues.pop();
} else if (!isClamped(lowValue, minValue, highValue) && isClamped(lowValue, maxValue, highValue)) {
indexToReplace = minValue;
this._smallValues.pop();
} else if (lowValue - minValue > maxValue - highValue) {
indexToReplace = minValue;
this._smallValues.pop();
} else {
valueToReplace = maxValue;
indexToReplace = maxValue;
this._largeValues.pop();
}
var position = this._valueToPositionMap[valueToReplace];
delete this._valueToPositionMap[valueToReplace];
this._valueToPositionMap[newValue] = position;
this._pushToHeaps(position, newValue);
var _i = this._vacantPositions.findIndex(function (v) {
return v === position;
});
if (_i !== -1) this._vacantPositions.splice(_i, 1);
var replacedMeta = this._indexToMetaMap.get(indexToReplace);
var position = this._metaToPositionMap.get(replacedMeta);
return position;
};
_proto.shuffle = function shuffle() {
var _this = this;
var indices = new Array(this.bufferSize);
for (var idx = 0; idx < indices.length; idx++) {
var meta = this._onTheFlyIndices[idx] || this._positionToMetaList[idx];
var targetIndex = this.getMetaIndex(meta);
indices[idx] = targetIndex;
}
var _arr = new Array(indices.length);
var _available = [];
var indexToMetaMap = new Map();
var metaToIndexMap = new Map();
var metaToPositionMap = new Map();
var _loop = function _loop() {
var currentIndex = indices[_idx];
var currentMeta = _this._metaExtractor(currentIndex);
if (currentMeta == null) return "continue";
indexToMetaMap.set(currentIndex, currentMeta);
metaToIndexMap.set(currentMeta, currentIndex);
if (currentMeta === _this._positionToMetaList[_idx]) {
_arr[_idx] = currentMeta;
return "continue";
}
var _i = _this._positionToMetaList.findIndex(function (v) {
return v === currentMeta;
});
if (_i !== -1) {
_arr[_i] = currentMeta;
return "continue";
}
_available.push(currentMeta);
};
for (var _idx = 0; _idx < indices.length; _idx++) {
var _ret = _loop();
if (_ret === "continue") continue;
}
var _this$initialize2 = this.initialize(),
smallValues = _this$initialize2.smallValues,
largeValues = _this$initialize2.largeValues;
var positionToMetaList = [];
for (var position = 0; position < indices.length; position++) {
var value = indices[position];
if (_arr[position] != null) {
positionToMetaList[position] = _arr[position];
metaToPositionMap.set(_arr[position], position);
var element = {
position: position,
value: value
};
smallValues.push(element);
largeValues.push(element);
continue;
}
var _meta = _available.shift();
if (_meta != null) {
positionToMetaList[position] = _meta;
metaToPositionMap.set(_meta, position);
var _element = {
position: position,
value: value
};
smallValues.push(_element);
largeValues.push(_element);
}
}
this._positionToMetaList = positionToMetaList;
this._smallValues = smallValues;
this._largeValues = largeValues;
this._indexToMetaMap = indexToMetaMap;
this.replaceMetaToIndexMap(metaToIndexMap);
this._metaToPositionMap = metaToPositionMap;
this._onTheFlyIndices = [];
try {
var _indices = new Array(this.bufferSize);
for (var _idx2 = 0; _idx2 < _indices.length; _idx2++) {
var _meta2 = this._onTheFlyIndices[_idx2] || this._positionToMetaList[_idx2];
var _targetIndex = this.getMetaIndex(_meta2);
if (_meta2 != null) {
_indices[_idx2] = {
meta: _meta2,
targetIndex: _targetIndex,
recyclerKey: this._name + "_" + _idx2
};
}
}
return _indices;
} catch (err) {
this.readyToStartNextLoop();
return this._positionToMetaList;
}
};
_proto.getIndices = function getIndices() {
try {
var indices = new Array(this.bufferSize);
for (var idx = 0; idx < indices.length; idx++) {
var meta = this._onTheFlyIndices[idx] || this._positionToMetaList[idx];
var targetIndex = this.getMetaIndex(meta);
if (meta !== this.getIndexMeta(targetIndex)) {
return this.shuffle();
}
if (meta != null) {
indices[idx] = {
meta: meta,
targetIndex: targetIndex,
recyclerKey: this._name + "_" + idx
};
}
}
this._onTheFlyIndices = [];
return indices;
} catch (err) {
this.readyToStartNextLoop();
return this._positionToMetaList;
}
};
_proto._pushToHeaps = function _pushToHeaps(position, value) {

@@ -164,2 +466,26 @@ var element = {

};
_proto._setMetaPosition = function _setMetaPosition(meta, position) {
var prevMetaOnPosition = this._positionToMetaList[position];
if (prevMetaOnPosition) this._metaToPositionMap["delete"](prevMetaOnPosition);
this._positionToMetaList[position] = meta;
this._metaToPositionMap.set(meta, position);
};
_proto._setMetaIndex = function _setMetaIndex(meta, index) {
var prevMetaIndex = this.getMetaIndex(meta);
if (prevMetaIndex !== undefined) {
this._indexToMetaMap["delete"](prevMetaIndex);
}
this.setMetaIndex(meta, index);
this._indexToMetaMap.set(index, meta);
return false;
};
_proto.readyToStartNextLoop = function readyToStartNextLoop() {
this._lastUpdatedMS = Date.now();
};
_proto.prepare = function prepare() {
if (this._loopMS === this._lastUpdatedMS) return;
this._loopMS = this._lastUpdatedMS;
this._onTheFlyIndices = [];
this._isOnTheFlyFull = false;
};
_proto._cleanHeaps = function _cleanHeaps() {

@@ -174,2 +500,38 @@ this._cleanHeap(this._smallValues);

};
_proto.rebuildHeapsWithValues = function rebuildHeapsWithValues(arr) {
var valueToPositionObject = {};
var newSmallValues = new Heap([], this._smallerComparator);
var newLargeValues = new Heap([], this._greaterComparator);
arr.forEach(function (element) {
var position = element.position,
value = element.value;
if (value !== undefined) {
var _element2 = {
position: position,
value: value
};
newSmallValues.push(_element2);
newLargeValues.push(_element2);
valueToPositionObject[value] = position;
}
});
var _arr = new Array(this._bufferSize).fill(2);
Object.keys(valueToPositionObject).map(function (key) {
return _arr[valueToPositionObject[key]] = 1;
});
_arr.forEach(function (_i, position) {
if (_i === 2) {
var value = Number.MAX_SAFE_INTEGER - position;
var element = {
position: position,
value: value
};
newSmallValues.push(element);
newLargeValues.push(element);
valueToPositionObject[value] = position;
}
});
this._smallValues = newSmallValues;
this._largeValues = newLargeValues;
};
_proto._recreateHeaps = function _recreateHeaps() {

@@ -181,3 +543,3 @@ var sourceHeap = this._smallValues.size() < this._largeValues.size() ? this._smallValues : this._largeValues;

var element = sourceHeap.pop();
if (this._valueToPositionMap[element.value] !== undefined) {
if (this._metaToPositionMap.get(this._indexToMetaMap.get(element.value)) != null) {
newSmallValues.push(element);

@@ -191,3 +553,3 @@ newLargeValues.push(element);

_proto._cleanHeap = function _cleanHeap(heap) {
while (!heap.empty() && this._valueToPositionMap[heap.peek().value] === undefined) {
while (!heap.empty() && this._metaToPositionMap.get(this._indexToMetaMap.get(heap.peek().value)) == null) {
heap.pop();

@@ -203,11 +565,11 @@ }

_createClass(IntegerBufferSet, [{
key: "indices",
key: "bufferSize",
get: function get() {
var indices = [];
for (var key in this._valueToPositionMap) {
var value = this._valueToPositionMap[key];
indices[value] = key;
}
return indices;
return this._bufferSize;
}
}, {
key: "isBufferFull",
get: function get() {
return this._positionToMetaList.length >= this._bufferSize;
}
}]);

@@ -218,2 +580,3 @@ return IntegerBufferSet;

exports.default = IntegerBufferSet;
exports.defaultBufferSize = defaultBufferSize;
//# sourceMappingURL=integer-buffer-set.cjs.development.js.map

2

dist/integer-buffer-set.cjs.production.min.js

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

"use strict";Object.defineProperty(exports,"__esModule",{value:!0});var e,t=(e=require("@x-oasis/heap"))&&"object"==typeof e&&"default"in e?e.default:e,i=function(e){var t=e.safeRange,i=e.bufferSetRange;return t.lowValue-i.minValue>i.maxValue-t.highValue};exports.default=function(){function e(){this._valueToPositionMap={},this._size=0,this._smallValues=new t([],this._smallerComparator),this._largeValues=new t([],this._greaterComparator),this.getNewPositionForValue=this.getNewPositionForValue.bind(this),this.getValuePosition=this.getValuePosition.bind(this),this.getSize=this.getSize.bind(this),this.replaceFurthestValuePosition=this.replaceFurthestValuePosition.bind(this),this._vacantPositions=[]}var a,s,o=e.prototype;return o.getSize=function(){return this._size},o.getValuePosition=function(e){return void 0===this._valueToPositionMap[e]?null:this._valueToPositionMap[e]},o.getNewPositionForValue=function(e){void 0!==this._valueToPositionMap[e]&&console.warn("Shouldn't try to find new position for value already stored in BufferSet");var t=this._size;return this._size++,this._pushToHeaps(t,e),this._valueToPositionMap[e]=t,t},o.getMinValue=function(){var e;return null==(e=this._smallValues.peek())?void 0:e.value},o.getMaxValue=function(){var e;return null==(e=this._largeValues.peek())?void 0:e.value},o.setPositionValue=function(e,t){var i=this._valueToPositionMap[t];void 0!==i&&(-1===this._vacantPositions.findIndex((function(e){return e===i}))&&this._vacantPositions.push(i),delete this._valueToPositionMap[t],this._valueToPositionMap[t]=e)},o.replaceFurthestValuePosition=function(e,t,a,s){if(void 0===s&&(s=i),void 0!==this._valueToPositionMap[a]&&console.warn("Shouldn't try to replace values with value already stored value in BufferSet"),this._cleanHeaps(),this._smallValues.empty()||this._largeValues.empty())return null;if(this._vacantPositions.length){var o=this._vacantPositions.pop();return this._valueToPositionMap[a]=o,this._pushToHeaps(o,a),o}var l,n=this._smallValues.peek().value,r=this._largeValues.peek().value;if(n>=e&&r<=t)return null;s({safeRange:{lowValue:e,highValue:t},bufferSetRange:{minValue:n,maxValue:r},currentIndex:a})?(l=n,this._smallValues.pop()):(l=r,this._largeValues.pop());var u=this._valueToPositionMap[l];delete this._valueToPositionMap[l],this._valueToPositionMap[a]=u,this._pushToHeaps(u,a);var h=this._vacantPositions.findIndex((function(e){return e===u}));return-1!==h&&this._vacantPositions.splice(h,1),u},o._pushToHeaps=function(e,t){var i={position:e,value:t};this._smallValues.push(i),this._largeValues.push(i)},o._cleanHeaps=function(){this._cleanHeap(this._smallValues),this._cleanHeap(this._largeValues);var e=Math.min(this._smallValues.size(),this._largeValues.size());Math.max(this._smallValues.size(),this._largeValues.size())>10*e&&this._recreateHeaps()},o._recreateHeaps=function(){for(var e=this._smallValues.size()<this._largeValues.size()?this._smallValues:this._largeValues,i=new t([],this._smallerComparator),a=new t([],this._greaterComparator);!e.empty();){var s=e.pop();void 0!==this._valueToPositionMap[s.value]&&(i.push(s),a.push(s))}this._smallValues=i,this._largeValues=a},o._cleanHeap=function(e){for(;!e.empty()&&void 0===this._valueToPositionMap[e.peek().value];)e.pop()},o._smallerComparator=function(e,t){return e.value<t.value},o._greaterComparator=function(e,t){return e.value>t.value},a=e,(s=[{key:"indices",get:function(){var e=[];for(var t in this._valueToPositionMap)e[this._valueToPositionMap[t]]=t;return e}}])&&function(e,t){for(var i=0;i<t.length;i++){var a=t[i];a.enumerable=a.enumerable||!1,a.configurable=!0,"value"in a&&(a.writable=!0),Object.defineProperty(e,"symbol"==typeof(s=function(e,t){if("object"!=typeof e||null===e)return e;var i=e[Symbol.toPrimitive];if(void 0!==i){var a=i.call(e,"string");if("object"!=typeof a)return a;throw new TypeError("@@toPrimitive must return a primitive value.")}return String(e)}(a.key))?s:String(s),a)}var s}(a.prototype,s),Object.defineProperty(a,"prototype",{writable:!1}),e}();
"use strict";function t(t){return t&&"object"==typeof t&&"default"in t?t.default:t}Object.defineProperty(exports,"__esModule",{value:!0});var e=t(require("@x-oasis/heap")),i=t(require("@x-oasis/is-clamped")),n=t(require("@x-oasis/invariant")),s=t(require("@x-oasis/return-hook"));function a(t,e){(null==e||e>t.length)&&(e=t.length);for(var i=0,n=new Array(e);i<e;i++)n[i]=t[i];return n}function r(t,e){var i="undefined"!=typeof Symbol&&t[Symbol.iterator]||t["@@iterator"];if(i)return(i=i.call(t)).next.bind(i);if(Array.isArray(t)||(i=function(t,e){if(t){if("string"==typeof t)return a(t,void 0);var i=Object.prototype.toString.call(t).slice(8,-1);return"Object"===i&&t.constructor&&(i=t.constructor.name),"Map"===i||"Set"===i?Array.from(t):"Arguments"===i||/^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(i)?a(t,void 0):void 0}}(t))||e&&t&&"number"==typeof t.length){i&&(t=i);var n=0;return function(){return n>=t.length?{done:!0}:{done:!1,value:t[n++]}}}throw new TypeError("Invalid attempt to iterate non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.")}var o=function(t){return t};exports.default=function(){function t(t){void 0===t&&(t={});var i=t.name,n=void 0===i?"default_buffer":i,a=t.indexExtractor,r=t.bufferSize,l=void 0===r?10:r,u=t.metaExtractor;this._metaExtractor=void 0===u?o:u,this._indexExtractor=a,this._name=n,this._indexToMetaMap=new Map,this._metaToPositionMap=new Map,this._positionToMetaList=[],this._metaToIndexMap=new Map,this._onTheFlyIndices=[],this._size=0,this._bufferSize=l,this._smallValues=new e([],this._smallerComparator),this._largeValues=new e([],this._greaterComparator),this.getNewPositionForIndex=this.getNewPositionForIndex.bind(this),this.getIndexPosition=this.getIndexPosition.bind(this),this.getSize=this.getSize.bind(this),this.replacePositionInFliedIndices=this.replacePositionInFliedIndices.bind(this),this.replaceFurthestIndexPosition=this.replaceFurthestIndexPosition.bind(this),this._isOnTheFlyFullReturnHook=s(this.setIsOnTheFlyFull.bind(this)),this._loopMS=Date.now(),this._lastUpdatedMS=this._loopMS}var a,l,u=t.prototype;return u.getSize=function(){return this._size},u.setIsOnTheFlyFull=function(t){if(null!=t){var e=this._onTheFlyIndices.filter((function(t){return t}));this._isOnTheFlyFull=e.length===this._bufferSize}},u.getOnTheFlyUncriticalPosition=function(t){for(var e=t.startIndex,n=t.endIndex,s=0;s<this._onTheFlyIndices.length;s++){var a=this._metaToIndexMap.get(this._onTheFlyIndices[s]);if(!i(e,a,n))return s}return null},u.initialize=function(){return{smallValues:new e([],this._smallerComparator),largeValues:new e([],this._greaterComparator),valueToPositionObject:{}}},u.getIndexMeta=function(t){return this._metaExtractor(t)},u.getMetaIndex=function(t){return this._indexExtractor?this._indexExtractor(t):this._metaToIndexMap.get(t)},u.setMetaIndex=function(t,e){return!this._indexExtractor&&this._metaToIndexMap.set(t,e)},u.deleteMetaIndex=function(t){return this._metaToIndexMap.delete(t)},u.replaceMetaToIndexMap=function(t){return!this._indexExtractor&&(this._metaToIndexMap=t)},u.getIndexPosition=function(t){return this.getMetaIndex(this.getIndexMeta(t))},u.getNewPositionForIndex=function(t){var e=this.getIndexMeta(t);void 0!==this._metaToPositionMap.get(e)&&n(!1);var i=this._positionToMetaList.length;return this._pushToHeaps(i,t),this._setMetaIndex(e,t),this._setMetaPosition(e,i),i},u.getMinValue=function(){var t;return null==(t=this._smallValues.peek())?void 0:t.value},u.getMaxValue=function(){var t;return null==(t=this._largeValues.peek())?void 0:t.value},u.setValuePosition=function(t,e){},u.findPositionMeta=function(t){for(var e,i=r(this._metaToPositionMap);!(e=i()).done;){var n=e.value;if(n[1]===t)return n[0]}return null},u.rebuildHeapsWithMeta=function(t){for(var e,i=this.initialize(),n=i.smallValues,s=i.largeValues,a=r(t);!(e=a()).done;){var o=e.value,l=o[1],u={index:this.getMetaIndex(o[0]),position:l};n.push(u),s.push(u)}this._smallValues=n,this._largeValues=s},u.setPositionIndex=function(t,e){var i=this._metaExtractor(e),n=this._metaToPositionMap.get(i);if(void 0!==n){if(n===t)return!0;this.deleteMetaIndex(i)}var s=this.findPositionMeta(t);return s&&this._metaToPositionMap.delete(s),this._metaToPositionMap.set(i,t),this.rebuildHeapsWithMeta(this._metaToPositionMap),!0},u.getMetaPosition=function(t){return this._metaToPositionMap.get(t)},u.replacePositionInFliedIndices=function(t,e){if(this._isOnTheFlyFull){if(!i(e.startIndex,t,e.endIndex))return null;var n=this.getOnTheFlyUncriticalPosition(e);if(null!=n)return n}return null},u.getFliedPosition=function(t,e){var i=this.replacePositionInFliedIndices(t,e);if(null!=i){var n=this.getIndexMeta(t);return this._onTheFlyIndices[i]=n,this._setMetaIndex(n,t),this._isOnTheFlyFullReturnHook(i)}return null},u.getPosition=function(t,e){this.prepare();var i,n=this.getIndexMeta(t),s=this._metaToPositionMap.get(n);if(void 0!==s){var a=this._onTheFlyIndices[s];if(a){if(a===n)return s;var r=this._replaceFurthestIndexPosition(t,e);if(this._isOnTheFlyFull)return this.getFliedPosition(t,e);for(;this._onTheFlyIndices[r];)r=this._replaceFurthestIndexPosition(t,e);if(null!=r)return this._setMetaIndex(n,t),this._onTheFlyIndices[r]=a,this._isOnTheFlyFullReturnHook(r)}return this._onTheFlyIndices[s]=n,this._isOnTheFlyFullReturnHook(s)}if(!this.isBufferFull)return this._isOnTheFlyFullReturnHook(this.getNewPositionForIndex(t));if(this._isOnTheFlyFull)return this.getFliedPosition(t,e);var o=this._indexToMetaMap.get(t);return o?i=this._metaToPositionMap.get(o):(this._cleanHeaps(),i=this._replaceFurthestIndexPosition(t,e)),this._onTheFlyIndices[i]=n,this._setMetaIndex(n,t),this._setMetaPosition(n,i),this._isOnTheFlyFullReturnHook(i)},u.replaceFurthestIndexPosition=function(t,e){return this.isBufferFull?this._replaceFurthestIndexPosition(t,e):this._isOnTheFlyFullReturnHook(this.getNewPositionForIndex(t))},u._replaceFurthestIndexPosition=function(t,e){if(this._largeValues.empty()||this._smallValues.empty())return this._isOnTheFlyFullReturnHook(this.getNewPositionForIndex(t));var n,s=this._smallValues.peek().value,a=this._largeValues.peek().value;if(!e){Math.abs(t-s)>Math.abs(t-a)?(n=s,this._smallValues.pop()):(n=a,this._largeValues.pop());var r=this._indexToMetaMap.get(n);return this._metaToPositionMap.get(r)}var o=e.startIndex,l=e.endIndex;if(i(o,s,l)&&i(o,a,l))return null;i(o,s,l)&&!i(o,a,l)?(n=a,this._largeValues.pop()):!i(o,s,l)&&i(o,a,l)||o-s>a-l?(n=s,this._smallValues.pop()):(n=a,this._largeValues.pop());var u=this._indexToMetaMap.get(n);return this._metaToPositionMap.get(u)},u.shuffle=function(){for(var t=this,e=new Array(this.bufferSize),i=0;i<e.length;i++){var n=this.getMetaIndex(this._onTheFlyIndices[i]||this._positionToMetaList[i]);e[i]=n}for(var s=new Array(e.length),a=[],r=new Map,o=new Map,l=new Map,u=function(){var i=e[h],n=t._metaExtractor(i);if(null==n)return"continue";if(r.set(i,n),o.set(n,i),n===t._positionToMetaList[h])return s[h]=n,"continue";var l=t._positionToMetaList.findIndex((function(t){return t===n}));if(-1!==l)return s[l]=n,"continue";a.push(n)},h=0;h<e.length;h++)u();for(var p=this.initialize(),_=p.smallValues,d=p.largeValues,f=[],c=0;c<e.length;c++){var M=e[c];if(null==s[c]){var v=a.shift();if(null!=v){f[c]=v,l.set(v,c);var g={position:c,value:M};_.push(g),d.push(g)}}else{f[c]=s[c],l.set(s[c],c);var x={position:c,value:M};_.push(x),d.push(x)}}this._positionToMetaList=f,this._smallValues=_,this._largeValues=d,this._indexToMetaMap=r,this.replaceMetaToIndexMap(o),this._metaToPositionMap=l,this._onTheFlyIndices=[];try{for(var m=new Array(this.bufferSize),T=0;T<m.length;T++){var I=this._onTheFlyIndices[T]||this._positionToMetaList[T],y=this.getMetaIndex(I);null!=I&&(m[T]={meta:I,targetIndex:y,recyclerKey:this._name+"_"+T})}return m}catch(t){return this.readyToStartNextLoop(),this._positionToMetaList}},u.getIndices=function(){try{for(var t=new Array(this.bufferSize),e=0;e<t.length;e++){var i=this._onTheFlyIndices[e]||this._positionToMetaList[e],n=this.getMetaIndex(i);if(i!==this.getIndexMeta(n))return this.shuffle();null!=i&&(t[e]={meta:i,targetIndex:n,recyclerKey:this._name+"_"+e})}return this._onTheFlyIndices=[],t}catch(t){return this.readyToStartNextLoop(),this._positionToMetaList}},u._pushToHeaps=function(t,e){var i={position:t,value:e};this._smallValues.push(i),this._largeValues.push(i)},u._setMetaPosition=function(t,e){var i=this._positionToMetaList[e];i&&this._metaToPositionMap.delete(i),this._positionToMetaList[e]=t,this._metaToPositionMap.set(t,e)},u._setMetaIndex=function(t,e){var i=this.getMetaIndex(t);return void 0!==i&&this._indexToMetaMap.delete(i),this.setMetaIndex(t,e),this._indexToMetaMap.set(e,t),!1},u.readyToStartNextLoop=function(){this._lastUpdatedMS=Date.now()},u.prepare=function(){this._loopMS!==this._lastUpdatedMS&&(this._loopMS=this._lastUpdatedMS,this._onTheFlyIndices=[],this._isOnTheFlyFull=!1)},u._cleanHeaps=function(){this._cleanHeap(this._smallValues),this._cleanHeap(this._largeValues);var t=Math.min(this._smallValues.size(),this._largeValues.size());Math.max(this._smallValues.size(),this._largeValues.size())>10*t&&this._recreateHeaps()},u.rebuildHeapsWithValues=function(t){var i={},n=new e([],this._smallerComparator),s=new e([],this._greaterComparator);t.forEach((function(t){var e=t.position,a=t.value;if(void 0!==a){var r={position:e,value:a};n.push(r),s.push(r),i[a]=e}}));var a=new Array(this._bufferSize).fill(2);Object.keys(i).map((function(t){return a[i[t]]=1})),a.forEach((function(t,e){if(2===t){var a=Number.MAX_SAFE_INTEGER-e,r={position:e,value:a};n.push(r),s.push(r),i[a]=e}})),this._smallValues=n,this._largeValues=s},u._recreateHeaps=function(){for(var t=this._smallValues.size()<this._largeValues.size()?this._smallValues:this._largeValues,i=new e([],this._smallerComparator),n=new e([],this._greaterComparator);!t.empty();){var s=t.pop();null!=this._metaToPositionMap.get(this._indexToMetaMap.get(s.value))&&(i.push(s),n.push(s))}this._smallValues=i,this._largeValues=n},u._cleanHeap=function(t){for(;!t.empty()&&null==this._metaToPositionMap.get(this._indexToMetaMap.get(t.peek().value));)t.pop()},u._smallerComparator=function(t,e){return t.value<e.value},u._greaterComparator=function(t,e){return t.value>e.value},a=t,(l=[{key:"bufferSize",get:function(){return this._bufferSize}},{key:"isBufferFull",get:function(){return this._positionToMetaList.length>=this._bufferSize}}])&&function(t,e){for(var i=0;i<e.length;i++){var n=e[i];n.enumerable=n.enumerable||!1,n.configurable=!0,"value"in n&&(n.writable=!0),Object.defineProperty(t,"symbol"==typeof(s=function(t,e){if("object"!=typeof t||null===t)return t;var i=t[Symbol.toPrimitive];if(void 0!==i){var n=i.call(t,"string");if("object"!=typeof n)return n;throw new TypeError("@@toPrimitive must return a primitive value.")}return String(t)}(n.key))?s:String(s),n)}var s}(a.prototype,l),Object.defineProperty(a,"prototype",{writable:!1}),t}(),exports.defaultBufferSize=10;
//# sourceMappingURL=integer-buffer-set.cjs.production.min.js.map

521

dist/integer-buffer-set.esm.js
import Heap from '@x-oasis/heap';
import isClamped from '@x-oasis/is-clamped';
import invariant from '@x-oasis/invariant';
import returnHook from '@x-oasis/return-hook';

@@ -20,2 +23,33 @@ function _defineProperties(target, props) {

}
function _unsupportedIterableToArray(o, minLen) {
if (!o) return;
if (typeof o === "string") return _arrayLikeToArray(o, minLen);
var n = Object.prototype.toString.call(o).slice(8, -1);
if (n === "Object" && o.constructor) n = o.constructor.name;
if (n === "Map" || n === "Set") return Array.from(o);
if (n === "Arguments" || /^(?:Ui|I)nt(?:8|16|32)(?:Clamped)?Array$/.test(n)) return _arrayLikeToArray(o, minLen);
}
function _arrayLikeToArray(arr, len) {
if (len == null || len > arr.length) len = arr.length;
for (var i = 0, arr2 = new Array(len); i < len; i++) arr2[i] = arr[i];
return arr2;
}
function _createForOfIteratorHelperLoose(o, allowArrayLike) {
var it = typeof Symbol !== "undefined" && o[Symbol.iterator] || o["@@iterator"];
if (it) return (it = it.call(o)).next.bind(it);
if (Array.isArray(o) || (it = _unsupportedIterableToArray(o)) || allowArrayLike && o && typeof o.length === "number") {
if (it) o = it;
var i = 0;
return function () {
if (i >= o.length) return {
done: true
};
return {
done: false,
value: o[i++]
};
};
}
throw new TypeError("Invalid attempt to iterate non-iterable instance.\nIn order to be iterable, non-array objects must have a [Symbol.iterator]() method.");
}
function _toPrimitive(input, hint) {

@@ -36,22 +70,39 @@ if (typeof input !== "object" || input === null) return input;

var defaultUseMinValueFn = function defaultUseMinValueFn(options) {
var safeRange = options.safeRange,
bufferSetRange = options.bufferSetRange;
var lowValue = safeRange.lowValue,
highValue = safeRange.highValue;
var maxValue = bufferSetRange.maxValue,
minValue = bufferSetRange.minValue;
return lowValue - minValue > maxValue - highValue;
var defaultMetaExtractor = function defaultMetaExtractor(value) {
return value;
};
var defaultBufferSize = 10;
var IntegerBufferSet = /*#__PURE__*/function () {
function IntegerBufferSet() {
this._valueToPositionMap = {};
function IntegerBufferSet(props) {
if (props === void 0) {
props = {};
}
var _props = props,
_props$name = _props.name,
name = _props$name === void 0 ? 'default_buffer' : _props$name,
indexExtractor = _props.indexExtractor,
_props$bufferSize = _props.bufferSize,
bufferSize = _props$bufferSize === void 0 ? defaultBufferSize : _props$bufferSize,
_props$metaExtractor = _props.metaExtractor,
metaExtractor = _props$metaExtractor === void 0 ? defaultMetaExtractor : _props$metaExtractor;
this._metaExtractor = metaExtractor;
this._indexExtractor = indexExtractor;
this._name = name;
this._indexToMetaMap = new Map();
this._metaToPositionMap = new Map();
this._positionToMetaList = [];
this._metaToIndexMap = new Map();
this._onTheFlyIndices = [];
this._size = 0;
this._bufferSize = bufferSize;
this._smallValues = new Heap([], this._smallerComparator);
this._largeValues = new Heap([], this._greaterComparator);
this.getNewPositionForValue = this.getNewPositionForValue.bind(this);
this.getValuePosition = this.getValuePosition.bind(this);
this.getNewPositionForIndex = this.getNewPositionForIndex.bind(this);
this.getIndexPosition = this.getIndexPosition.bind(this);
this.getSize = this.getSize.bind(this);
this.replaceFurthestValuePosition = this.replaceFurthestValuePosition.bind(this);
this._vacantPositions = [];
this.replacePositionInFliedIndices = this.replacePositionInFliedIndices.bind(this);
this.replaceFurthestIndexPosition = this.replaceFurthestIndexPosition.bind(this);
this._isOnTheFlyFullReturnHook = returnHook(this.setIsOnTheFlyFull.bind(this));
this._loopMS = Date.now();
this._lastUpdatedMS = this._loopMS;
}

@@ -62,16 +113,61 @@ var _proto = IntegerBufferSet.prototype;

};
_proto.getValuePosition = function getValuePosition(value) {
if (this._valueToPositionMap[value] === undefined) {
return null;
_proto.setIsOnTheFlyFull = function setIsOnTheFlyFull(val) {
if (val != null) {
var data = this._onTheFlyIndices.filter(function (v) {
return v;
});
this._isOnTheFlyFull = data.length === this._bufferSize;
}
return this._valueToPositionMap[value];
};
_proto.getNewPositionForValue = function getNewPositionForValue(value) {
if (this._valueToPositionMap[value] !== undefined) {
console.warn("Shouldn't try to find new position for value already stored in BufferSet");
_proto.getOnTheFlyUncriticalPosition = function getOnTheFlyUncriticalPosition(safeRange) {
var startIndex = safeRange.startIndex,
endIndex = safeRange.endIndex;
for (var idx = 0; idx < this._onTheFlyIndices.length; idx++) {
var meta = this._onTheFlyIndices[idx];
var metaIndex = this._metaToIndexMap.get(meta);
if (!isClamped(startIndex, metaIndex, endIndex)) {
return idx;
}
}
var newPosition = this._size;
this._size++;
this._pushToHeaps(newPosition, value);
this._valueToPositionMap[value] = newPosition;
return null;
};
_proto.initialize = function initialize() {
return {
smallValues: new Heap([], this._smallerComparator),
largeValues: new Heap([], this._greaterComparator),
valueToPositionObject: {}
};
};
_proto.getIndexMeta = function getIndexMeta(index) {
return this._metaExtractor(index);
};
_proto.getMetaIndex = function getMetaIndex(meta) {
if (this._indexExtractor) return this._indexExtractor(meta);
return this._metaToIndexMap.get(meta);
};
_proto.setMetaIndex = function setMetaIndex(meta, index) {
if (!this._indexExtractor) {
return this._metaToIndexMap.set(meta, index);
}
return false;
};
_proto.deleteMetaIndex = function deleteMetaIndex(meta) {
return this._metaToIndexMap["delete"](meta);
};
_proto.replaceMetaToIndexMap = function replaceMetaToIndexMap(newMetaToIndexMap) {
if (!this._indexExtractor) {
return this._metaToIndexMap = newMetaToIndexMap;
}
return false;
};
_proto.getIndexPosition = function getIndexPosition(index) {
return this.getMetaIndex(this.getIndexMeta(index));
};
_proto.getNewPositionForIndex = function getNewPositionForIndex(index) {
var meta = this.getIndexMeta(index);
!(this._metaToPositionMap.get(meta) === undefined) ? process.env.NODE_ENV !== "production" ? invariant(false, "Shouldn't try to find new position for value already stored in BufferSet") : invariant(false) : void 0;
var newPosition = this._positionToMetaList.length;
this._pushToHeaps(newPosition, index);
this._setMetaIndex(meta, index);
this._setMetaPosition(meta, newPosition);
return newPosition;

@@ -87,63 +183,269 @@ };

};
_proto.setPositionValue = function setPositionValue(position, value) {
var originalPosition = this._valueToPositionMap[value];
_proto.setValuePosition = function setValuePosition(value, position) {};
_proto.findPositionMeta = function findPositionMeta(position) {
for (var _iterator = _createForOfIteratorHelperLoose(this._metaToPositionMap), _step; !(_step = _iterator()).done;) {
var _step$value = _step.value,
meta = _step$value[0],
pos = _step$value[1];
if (pos === position) return meta;
}
return null;
};
_proto.rebuildHeapsWithMeta = function rebuildHeapsWithMeta(metaToPositionMap) {
var _this$initialize = this.initialize(),
smallValues = _this$initialize.smallValues,
largeValues = _this$initialize.largeValues;
for (var _iterator2 = _createForOfIteratorHelperLoose(metaToPositionMap), _step2; !(_step2 = _iterator2()).done;) {
var _step2$value = _step2.value,
meta = _step2$value[0],
position = _step2$value[1];
var index = this.getMetaIndex(meta);
var token = {
index: index,
position: position
};
smallValues.push(token);
largeValues.push(token);
}
this._smallValues = smallValues;
this._largeValues = largeValues;
};
_proto.setPositionIndex = function setPositionIndex(position, index) {
var meta = this._metaExtractor(index);
var originalPosition = this._metaToPositionMap.get(meta);
if (originalPosition !== undefined) {
var index = this._vacantPositions.findIndex(function (v) {
return v === originalPosition;
});
if (index === -1) this._vacantPositions.push(originalPosition);
delete this._valueToPositionMap[value];
this._valueToPositionMap[value] = position;
if (originalPosition === position) return true;
this.deleteMetaIndex(meta);
}
var metaToReplace = this.findPositionMeta(position);
if (metaToReplace) this._metaToPositionMap["delete"](metaToReplace);
this._metaToPositionMap.set(meta, position);
this.rebuildHeapsWithMeta(this._metaToPositionMap);
return true;
};
_proto.replaceFurthestValuePosition = function replaceFurthestValuePosition(lowValue, highValue, newValue, useMinValueFn) {
if (useMinValueFn === void 0) {
useMinValueFn = defaultUseMinValueFn;
_proto.getMetaPosition = function getMetaPosition(meta) {
return this._metaToPositionMap.get(meta);
};
_proto.replacePositionInFliedIndices = function replacePositionInFliedIndices(newIndex, safeRange) {
var startIndex = safeRange.startIndex,
endIndex = safeRange.endIndex;
if (this._isOnTheFlyFull) {
if (!isClamped(startIndex, newIndex, endIndex)) {
return null;
}
var pos = this.getOnTheFlyUncriticalPosition(safeRange);
if (pos != null) return pos;
}
if (this._valueToPositionMap[newValue] !== undefined) {
console.warn("Shouldn't try to replace values with value already stored value in " + 'BufferSet');
return null;
};
_proto.getFliedPosition = function getFliedPosition(newIndex, safeRange) {
var pos = this.replacePositionInFliedIndices(newIndex, safeRange);
if (pos != null) {
var meta = this.getIndexMeta(newIndex);
this._onTheFlyIndices[pos] = meta;
this._setMetaIndex(meta, newIndex);
return this._isOnTheFlyFullReturnHook(pos);
}
this._cleanHeaps();
if (this._smallValues.empty() || this._largeValues.empty()) {
return null;
return null;
};
_proto.getPosition = function getPosition(newIndex, safeRange) {
this.prepare();
var meta = this.getIndexMeta(newIndex);
var prevMetaPosition = this._metaToPositionMap.get(meta);
if (prevMetaPosition !== undefined) {
var onTheFlyPositionMeta = this._onTheFlyIndices[prevMetaPosition];
if (onTheFlyPositionMeta) {
if (onTheFlyPositionMeta === meta) {
return prevMetaPosition;
}
var _positionToReplace = this._replaceFurthestIndexPosition(newIndex, safeRange);
if (this._isOnTheFlyFull) return this.getFliedPosition(newIndex, safeRange);
while (this._onTheFlyIndices[_positionToReplace]) {
_positionToReplace = this._replaceFurthestIndexPosition(newIndex, safeRange);
}
if (_positionToReplace != null) {
this._setMetaIndex(meta, newIndex);
this._onTheFlyIndices[_positionToReplace] = onTheFlyPositionMeta;
return this._isOnTheFlyFullReturnHook(_positionToReplace);
}
}
this._onTheFlyIndices[prevMetaPosition] = meta;
return this._isOnTheFlyFullReturnHook(prevMetaPosition);
}
if (this._vacantPositions.length) {
var _position = this._vacantPositions.pop();
this._valueToPositionMap[newValue] = _position;
this._pushToHeaps(_position, newValue);
return _position;
if (!this.isBufferFull) return this._isOnTheFlyFullReturnHook(this.getNewPositionForIndex(newIndex));
if (this._isOnTheFlyFull) return this.getFliedPosition(newIndex, safeRange);
var positionToReplace;
var prevIndexMeta = this._indexToMetaMap.get(newIndex);
if (!prevIndexMeta) {
this._cleanHeaps();
positionToReplace = this._replaceFurthestIndexPosition(newIndex, safeRange);
} else {
positionToReplace = this._metaToPositionMap.get(prevIndexMeta);
}
this._onTheFlyIndices[positionToReplace] = meta;
this._setMetaIndex(meta, newIndex);
this._setMetaPosition(meta, positionToReplace);
return this._isOnTheFlyFullReturnHook(positionToReplace);
};
_proto.replaceFurthestIndexPosition = function replaceFurthestIndexPosition(newIndex, safeRange) {
if (!this.isBufferFull) {
return this._isOnTheFlyFullReturnHook(this.getNewPositionForIndex(newIndex));
}
return this._replaceFurthestIndexPosition(newIndex, safeRange);
};
_proto._replaceFurthestIndexPosition = function _replaceFurthestIndexPosition(newIndex, safeRange) {
if (this._largeValues.empty() || this._smallValues.empty()) {
return this._isOnTheFlyFullReturnHook(this.getNewPositionForIndex(newIndex));
}
var minValue = this._smallValues.peek().value;
var maxValue = this._largeValues.peek().value;
if (minValue >= lowValue && maxValue <= highValue) {
var indexToReplace;
if (!safeRange) {
if (Math.abs(newIndex - minValue) > Math.abs(newIndex - maxValue)) {
indexToReplace = minValue;
this._smallValues.pop();
} else {
indexToReplace = maxValue;
this._largeValues.pop();
}
var _replacedMeta = this._indexToMetaMap.get(indexToReplace);
var _position = this._metaToPositionMap.get(_replacedMeta);
return _position;
}
var lowValue = safeRange.startIndex,
highValue = safeRange.endIndex;
if (isClamped(lowValue, minValue, highValue) && isClamped(lowValue, maxValue, highValue)) {
return null;
}
var valueToReplace;
if (useMinValueFn({
safeRange: {
lowValue: lowValue,
highValue: highValue
},
bufferSetRange: {
minValue: minValue,
maxValue: maxValue
},
currentIndex: newValue
})) {
valueToReplace = minValue;
} else if (isClamped(lowValue, minValue, highValue) && !isClamped(lowValue, maxValue, highValue)) {
indexToReplace = maxValue;
this._largeValues.pop();
} else if (!isClamped(lowValue, minValue, highValue) && isClamped(lowValue, maxValue, highValue)) {
indexToReplace = minValue;
this._smallValues.pop();
} else if (lowValue - minValue > maxValue - highValue) {
indexToReplace = minValue;
this._smallValues.pop();
} else {
valueToReplace = maxValue;
indexToReplace = maxValue;
this._largeValues.pop();
}
var position = this._valueToPositionMap[valueToReplace];
delete this._valueToPositionMap[valueToReplace];
this._valueToPositionMap[newValue] = position;
this._pushToHeaps(position, newValue);
var _i = this._vacantPositions.findIndex(function (v) {
return v === position;
});
if (_i !== -1) this._vacantPositions.splice(_i, 1);
var replacedMeta = this._indexToMetaMap.get(indexToReplace);
var position = this._metaToPositionMap.get(replacedMeta);
return position;
};
_proto.shuffle = function shuffle() {
var _this = this;
var indices = new Array(this.bufferSize);
for (var idx = 0; idx < indices.length; idx++) {
var meta = this._onTheFlyIndices[idx] || this._positionToMetaList[idx];
var targetIndex = this.getMetaIndex(meta);
indices[idx] = targetIndex;
}
var _arr = new Array(indices.length);
var _available = [];
var indexToMetaMap = new Map();
var metaToIndexMap = new Map();
var metaToPositionMap = new Map();
var _loop = function _loop() {
var currentIndex = indices[_idx];
var currentMeta = _this._metaExtractor(currentIndex);
if (currentMeta == null) return "continue";
indexToMetaMap.set(currentIndex, currentMeta);
metaToIndexMap.set(currentMeta, currentIndex);
if (currentMeta === _this._positionToMetaList[_idx]) {
_arr[_idx] = currentMeta;
return "continue";
}
var _i = _this._positionToMetaList.findIndex(function (v) {
return v === currentMeta;
});
if (_i !== -1) {
_arr[_i] = currentMeta;
return "continue";
}
_available.push(currentMeta);
};
for (var _idx = 0; _idx < indices.length; _idx++) {
var _ret = _loop();
if (_ret === "continue") continue;
}
var _this$initialize2 = this.initialize(),
smallValues = _this$initialize2.smallValues,
largeValues = _this$initialize2.largeValues;
var positionToMetaList = [];
for (var position = 0; position < indices.length; position++) {
var value = indices[position];
if (_arr[position] != null) {
positionToMetaList[position] = _arr[position];
metaToPositionMap.set(_arr[position], position);
var element = {
position: position,
value: value
};
smallValues.push(element);
largeValues.push(element);
continue;
}
var _meta = _available.shift();
if (_meta != null) {
positionToMetaList[position] = _meta;
metaToPositionMap.set(_meta, position);
var _element = {
position: position,
value: value
};
smallValues.push(_element);
largeValues.push(_element);
}
}
this._positionToMetaList = positionToMetaList;
this._smallValues = smallValues;
this._largeValues = largeValues;
this._indexToMetaMap = indexToMetaMap;
this.replaceMetaToIndexMap(metaToIndexMap);
this._metaToPositionMap = metaToPositionMap;
this._onTheFlyIndices = [];
try {
var _indices = new Array(this.bufferSize);
for (var _idx2 = 0; _idx2 < _indices.length; _idx2++) {
var _meta2 = this._onTheFlyIndices[_idx2] || this._positionToMetaList[_idx2];
var _targetIndex = this.getMetaIndex(_meta2);
if (_meta2 != null) {
_indices[_idx2] = {
meta: _meta2,
targetIndex: _targetIndex,
recyclerKey: this._name + "_" + _idx2
};
}
}
return _indices;
} catch (err) {
this.readyToStartNextLoop();
return this._positionToMetaList;
}
};
_proto.getIndices = function getIndices() {
try {
var indices = new Array(this.bufferSize);
for (var idx = 0; idx < indices.length; idx++) {
var meta = this._onTheFlyIndices[idx] || this._positionToMetaList[idx];
var targetIndex = this.getMetaIndex(meta);
if (meta !== this.getIndexMeta(targetIndex)) {
return this.shuffle();
}
if (meta != null) {
indices[idx] = {
meta: meta,
targetIndex: targetIndex,
recyclerKey: this._name + "_" + idx
};
}
}
this._onTheFlyIndices = [];
return indices;
} catch (err) {
this.readyToStartNextLoop();
return this._positionToMetaList;
}
};
_proto._pushToHeaps = function _pushToHeaps(position, value) {

@@ -157,2 +459,26 @@ var element = {

};
_proto._setMetaPosition = function _setMetaPosition(meta, position) {
var prevMetaOnPosition = this._positionToMetaList[position];
if (prevMetaOnPosition) this._metaToPositionMap["delete"](prevMetaOnPosition);
this._positionToMetaList[position] = meta;
this._metaToPositionMap.set(meta, position);
};
_proto._setMetaIndex = function _setMetaIndex(meta, index) {
var prevMetaIndex = this.getMetaIndex(meta);
if (prevMetaIndex !== undefined) {
this._indexToMetaMap["delete"](prevMetaIndex);
}
this.setMetaIndex(meta, index);
this._indexToMetaMap.set(index, meta);
return false;
};
_proto.readyToStartNextLoop = function readyToStartNextLoop() {
this._lastUpdatedMS = Date.now();
};
_proto.prepare = function prepare() {
if (this._loopMS === this._lastUpdatedMS) return;
this._loopMS = this._lastUpdatedMS;
this._onTheFlyIndices = [];
this._isOnTheFlyFull = false;
};
_proto._cleanHeaps = function _cleanHeaps() {

@@ -167,2 +493,38 @@ this._cleanHeap(this._smallValues);

};
_proto.rebuildHeapsWithValues = function rebuildHeapsWithValues(arr) {
var valueToPositionObject = {};
var newSmallValues = new Heap([], this._smallerComparator);
var newLargeValues = new Heap([], this._greaterComparator);
arr.forEach(function (element) {
var position = element.position,
value = element.value;
if (value !== undefined) {
var _element2 = {
position: position,
value: value
};
newSmallValues.push(_element2);
newLargeValues.push(_element2);
valueToPositionObject[value] = position;
}
});
var _arr = new Array(this._bufferSize).fill(2);
Object.keys(valueToPositionObject).map(function (key) {
return _arr[valueToPositionObject[key]] = 1;
});
_arr.forEach(function (_i, position) {
if (_i === 2) {
var value = Number.MAX_SAFE_INTEGER - position;
var element = {
position: position,
value: value
};
newSmallValues.push(element);
newLargeValues.push(element);
valueToPositionObject[value] = position;
}
});
this._smallValues = newSmallValues;
this._largeValues = newLargeValues;
};
_proto._recreateHeaps = function _recreateHeaps() {

@@ -174,3 +536,3 @@ var sourceHeap = this._smallValues.size() < this._largeValues.size() ? this._smallValues : this._largeValues;

var element = sourceHeap.pop();
if (this._valueToPositionMap[element.value] !== undefined) {
if (this._metaToPositionMap.get(this._indexToMetaMap.get(element.value)) != null) {
newSmallValues.push(element);

@@ -184,3 +546,3 @@ newLargeValues.push(element);

_proto._cleanHeap = function _cleanHeap(heap) {
while (!heap.empty() && this._valueToPositionMap[heap.peek().value] === undefined) {
while (!heap.empty() && this._metaToPositionMap.get(this._indexToMetaMap.get(heap.peek().value)) == null) {
heap.pop();

@@ -196,11 +558,11 @@ }

_createClass(IntegerBufferSet, [{
key: "indices",
key: "bufferSize",
get: function get() {
var indices = [];
for (var key in this._valueToPositionMap) {
var value = this._valueToPositionMap[key];
indices[value] = key;
}
return indices;
return this._bufferSize;
}
}, {
key: "isBufferFull",
get: function get() {
return this._positionToMetaList.length >= this._bufferSize;
}
}]);

@@ -211,2 +573,3 @@ return IntegerBufferSet;

export default IntegerBufferSet;
export { defaultBufferSize };
//# sourceMappingURL=integer-buffer-set.esm.js.map

8

package.json
{
"name": "@x-oasis/integer-buffer-set",
"version": "0.1.19",
"version": "0.1.20",
"description": "IntegerBufferSet function",

@@ -19,6 +19,10 @@ "main": "dist/index.js",

"dependencies": {
"@x-oasis/heap": "0.1.19"
"@x-oasis/heap": "0.1.20",
"@x-oasis/invariant": "^0.1.19",
"@x-oasis/is-clamped": "^0.1.19",
"@x-oasis/return-hook": "^0.1.19"
},
"scripts": {
"build": "tsdx build --tsconfig tsconfig.build.json",
"watch": "tsdx watch --tsconfig tsconfig.build.json",
"clean": "rimraf ./dist",

@@ -25,0 +29,0 @@ "test": "vitest",

24

README.md

@@ -19,2 +19,24 @@ # @x-oasis/integer-buffer-set

$ pnpm test
```
```
## Usage
## Philosophy
Basically, we only compare index value, such as
create a `onTheFlyIndices` as a slave buffer. theoretically, at most buffer size's new
item could occupy a position.
`IndexExtractor` is the key point of design.
if you do not delete/reorder an an array, `indexExtractor` is useless.
## bad case
when getIndices..
`positionToMetaIndices` may used as a supplement. but when has multiple buffer. index refer to meta may changed to other buffer..
const data = [0, 1, 2, 3, 4, 5] only reuse `m % 3 === 0`, but when an item is deleted..
all these index after delete index value will be invalid, because `m % 2 === 0` could not be reused.

794

src/index.ts

@@ -1,25 +0,23 @@

// import invariant from 'invariant';
import Heap from '@x-oasis/heap';
import isClamped from '@x-oasis/is-clamped';
import invariant from '@x-oasis/invariant';
import returnHook, { ReturnHook } from '@x-oasis/return-hook';
import {
HeapItem,
SafeRange,
MetaExtractor,
IndexExtractor,
IntegerBufferSetProps,
MetaToIndexMap,
MetaToPositionMap,
IndexToMetaMap,
} from './types';
type HeapItem = {
position: number;
value: number;
};
const defaultMetaExtractor = (value) => value;
export const defaultBufferSize = 10;
const defaultUseMinValueFn = (options: {
safeRange: {
lowValue: number;
highValue: number;
};
bufferSetRange: {
maxValue: number;
minValue: number;
};
currentIndex: number;
}) => {
const { safeRange, bufferSetRange } = options;
const { lowValue, highValue } = safeRange;
const { maxValue, minValue } = bufferSetRange;
return lowValue - minValue > maxValue - highValue;
};
// !!!!! should do meta validation...meta should has an index...
// value: original data `index` value
// value(index) => meta => position
// `index to getIndices, meta to find index`

@@ -37,24 +35,68 @@ // Data structure that allows to store values and assign positions to them

// the set.
class IntegerBufferSet {
// feature: add / delete / update item will also in consider..
class IntegerBufferSet<Meta = any> {
private _size: number;
private _valueToPositionMap: {
[key: string]: number;
};
private _name: string;
private _bufferSize: number;
// private _positionToValueObject: ValueToPositionObject;
private _indexToMetaMap: IndexToMetaMap<Meta>;
private _metaToPositionMap: MetaToPositionMap<Meta>;
private _positionToMetaList: Array<Meta>;
private _metaToIndexMap: MetaToIndexMap<Meta>;
private _smallValues: Heap<HeapItem>;
private _largeValues: Heap<HeapItem>;
private _vacantPositions: Array<number>;
private _metaExtractor: MetaExtractor<Meta>;
private _indexExtractor: IndexExtractor<Meta>;
constructor() {
this._valueToPositionMap = {};
private _onTheFlyIndices: Array<Meta>;
private _isOnTheFlyFull: boolean;
private _isOnTheFlyFullReturnHook: ReturnHook;
private _loopMS: number;
private _lastUpdatedMS: number;
constructor(props: IntegerBufferSetProps<Meta> = {}) {
const {
name = 'default_buffer',
indexExtractor,
bufferSize = defaultBufferSize,
metaExtractor = defaultMetaExtractor,
} = props;
this._metaExtractor = metaExtractor;
this._indexExtractor = indexExtractor;
this._name = name;
// this._positionToValueObject = {};
/**
* this._indexToMetaMap is used to find the prev meta when finding a position for index.
*/
this._indexToMetaMap = new Map();
this._metaToPositionMap = new Map();
this._positionToMetaList = [];
this._metaToIndexMap = new Map();
this._onTheFlyIndices = [];
this._size = 0;
this._bufferSize = bufferSize;
this._smallValues = new Heap([], this._smallerComparator);
this._largeValues = new Heap([], this._greaterComparator);
this.getNewPositionForValue = this.getNewPositionForValue.bind(this);
this.getValuePosition = this.getValuePosition.bind(this);
this.getNewPositionForIndex = this.getNewPositionForIndex.bind(this);
this.getIndexPosition = this.getIndexPosition.bind(this);
this.getSize = this.getSize.bind(this);
this.replaceFurthestValuePosition =
this.replaceFurthestValuePosition.bind(this);
this.replacePositionInFliedIndices =
this.replacePositionInFliedIndices.bind(this);
this.replaceFurthestIndexPosition =
this.replaceFurthestIndexPosition.bind(this);
this._isOnTheFlyFullReturnHook = returnHook(
this.setIsOnTheFlyFull.bind(this)
);
this._vacantPositions = [];
this._loopMS = Date.now();
this._lastUpdatedMS = this._loopMS;
}

@@ -66,32 +108,80 @@

get indices() {
const indices = [];
for (const key in this._valueToPositionMap) {
const value = this._valueToPositionMap[key];
indices[value] = key;
get bufferSize() {
return this._bufferSize;
}
setIsOnTheFlyFull(val: any) {
if (val != null) {
const data = this._onTheFlyIndices.filter((v) => v);
this._isOnTheFlyFull = data.length === this._bufferSize;
}
return indices;
}
getValuePosition(value: number): null | number {
if (this._valueToPositionMap[value] === undefined) {
return null;
get isBufferFull() {
return this._positionToMetaList.length >= this._bufferSize;
}
getOnTheFlyUncriticalPosition(safeRange: SafeRange) {
const { startIndex, endIndex } = safeRange;
for (let idx = 0; idx < this._onTheFlyIndices.length; idx++) {
const meta = this._onTheFlyIndices[idx];
const metaIndex = this._metaToIndexMap.get(meta);
if (!isClamped(startIndex, metaIndex, endIndex)) {
return idx;
}
}
return this._valueToPositionMap[value];
return null;
}
getNewPositionForValue(value: number) {
if (this._valueToPositionMap[value] !== undefined) {
console.warn(
"Shouldn't try to find new position for value already stored in BufferSet"
);
initialize() {
return {
smallValues: new Heap([], this._smallerComparator),
largeValues: new Heap([], this._greaterComparator),
valueToPositionObject: {},
};
}
getIndexMeta(index: number) {
return this._metaExtractor(index);
}
getMetaIndex(meta: Meta) {
if (this._indexExtractor) return this._indexExtractor(meta);
return this._metaToIndexMap.get(meta);
}
setMetaIndex(meta: Meta, index: number) {
if (!this._indexExtractor) {
return this._metaToIndexMap.set(meta, index);
}
// invariant(
// this._valueToPositionMap[value] === undefined,
// "Shouldn't try to find new position for value already stored in BufferSet"
// );
const newPosition = this._size;
this._size++;
this._pushToHeaps(newPosition, value);
this._valueToPositionMap[value] = newPosition;
return false;
}
deleteMetaIndex(meta: Meta) {
return this._metaToIndexMap.delete(meta);
}
replaceMetaToIndexMap(newMetaToIndexMap: MetaToIndexMap<Meta>) {
if (!this._indexExtractor) {
return (this._metaToIndexMap = newMetaToIndexMap);
}
return false;
}
getIndexPosition(index: number): undefined | number {
return this.getMetaIndex(this.getIndexMeta(index));
}
getNewPositionForIndex(index: number) {
const meta = this.getIndexMeta(index);
invariant(
this._metaToPositionMap.get(meta) === undefined,
"Shouldn't try to find new position for value already stored in BufferSet"
);
const newPosition = this._positionToMetaList.length;
this._pushToHeaps(newPosition, index);
this._setMetaIndex(meta, index);
this._setMetaPosition(meta, newPosition);
return newPosition;

@@ -108,92 +198,303 @@ }

setPositionValue(position: number, value: number) {
const originalPosition = this._valueToPositionMap[value];
/**
* values actually is the position of original data.
*/
setValuePosition(value: number, position: number) {}
findPositionMeta(position: number) {
for (const [meta, pos] of this._metaToPositionMap) {
if (pos === position) return meta;
}
return null;
}
rebuildHeapsWithMeta(metaToPositionMap: MetaToPositionMap<Meta>) {
const { smallValues, largeValues } = this.initialize();
for (const [meta, position] of metaToPositionMap) {
const index = this.getMetaIndex(meta);
const token = { index, position };
smallValues.push(token);
largeValues.push(token);
}
this._smallValues = smallValues;
this._largeValues = largeValues;
}
/**
*
* @param position
* @param value
*
*
*/
setPositionIndex(position: number, index: number) {
const meta = this._metaExtractor(index);
const originalPosition = this._metaToPositionMap.get(meta);
// current index has a position
if (originalPosition !== undefined) {
const index = this._vacantPositions.findIndex(
(v) => v === originalPosition
);
if (index === -1) this._vacantPositions.push(originalPosition);
delete this._valueToPositionMap[value];
this._valueToPositionMap[value] = position;
if (originalPosition === position) return true;
this.deleteMetaIndex(meta);
}
const metaToReplace = this.findPositionMeta(position);
if (metaToReplace) this._metaToPositionMap.delete(metaToReplace);
this._metaToPositionMap.set(meta, position);
this.rebuildHeapsWithMeta(this._metaToPositionMap);
return true;
}
replaceFurthestValuePosition(
lowValue: number,
highValue: number,
newValue: number,
useMinValueFn: (options: {
safeRange: {
lowValue: number;
highValue: number;
};
bufferSetRange: {
maxValue: number;
minValue: number;
};
currentIndex: number;
}) => boolean = defaultUseMinValueFn
): null | number {
if (this._valueToPositionMap[newValue] !== undefined) {
console.warn(
"Shouldn't try to replace values with value already stored value in " +
'BufferSet'
getMetaPosition(meta: Meta) {
return this._metaToPositionMap.get(meta);
}
// performRangeUpdate(
// startIndex: number,
// endIndex: number,
// safeRange: {
// startIndex: number;
// endIndex: number;
// }
// ) {
// const _start = Math.max(startIndex, safeRange.startIndex);
// const _end = Math.min(endIndex, safeRange.endIndex);
// const primaryMetaList = [];
// const secondaryMetaList = [];
// const locationStartIndex = startIndex;
// const targetIndices = new Array(this._bufferSize);
// const _valueToPositionObject = {};
// const _positionToValueObject = {};
// const _valueToMetaObject = {};
// const _metaToIndexMap = new Map();
// for (let value = startIndex; value <= endIndex; value++) {
// const meta = this._metaExtractor(value);
// if (meta) {
// const _i = value - locationStartIndex;
// if (isClamped(value, safeRange.startIndex, safeRange.endIndex)) {
// primaryMetaList[_i] = meta;
// const targetIndex = this.getMetaPosition(meta);
// if (isNumber(targetIndex)) {
// targetIndices[targetIndex] = value;
// _valueToPositionObject[value] = targetIndex;
// _valueToMetaObject[value] = meta;
// _metaToIndexMap.set(meta, value);
// _positionToValueObject[targetIndex] = value;
// }
// } else {
// secondaryMetaList[_i] = meta;
// }
// }
// }
// for (let idx = _start; idx <= _end; idx++) {
// const meta = this._metaExtractor(idx);
// if (_metaToIndexMap.get(meta) !== undefined) continue;
// let p;
// while (
// (p =
// targetIndices[
// this.resolvePosition(safeRange.startIndex, safeRange.endIndex, idx)
// ]) === undefined
// ) {
// targetIndices[p] = idx;
// }
// }
// }
replacePositionInFliedIndices(newIndex: number, safeRange: SafeRange) {
const { startIndex, endIndex } = safeRange;
if (this._isOnTheFlyFull) {
// newIndex is not critical index, do nothing
if (!isClamped(startIndex, newIndex, endIndex)) {
return null;
}
// if `newIndex` is critical index, replace an un-committed
// index value from _onTheFlyIndices.
const pos = this.getOnTheFlyUncriticalPosition(safeRange);
if (pos != null) return pos;
}
return null;
}
getFliedPosition(newIndex: number, safeRange: SafeRange) {
const pos = this.replacePositionInFliedIndices(newIndex, safeRange);
if (pos != null) {
const meta = this.getIndexMeta(newIndex);
this._onTheFlyIndices[pos] = meta;
this._setMetaIndex(meta, newIndex);
return this._isOnTheFlyFullReturnHook(pos);
}
return null;
}
/**
*
* @param newIndex
* @param safeRange
* @returns
*
*
* _positionToMetaList maybe undefined on next loop
*/
getPosition(newIndex: number, safeRange?: SafeRange) {
this.prepare();
const meta = this.getIndexMeta(newIndex);
const prevMetaPosition = this._metaToPositionMap.get(meta);
if (prevMetaPosition !== undefined) {
const onTheFlyPositionMeta = this._onTheFlyIndices[prevMetaPosition];
// the occupied meta should change position
if (onTheFlyPositionMeta) {
// such as place item 11 twice...
if (onTheFlyPositionMeta === meta) {
return prevMetaPosition;
}
let positionToReplace = this._replaceFurthestIndexPosition(
newIndex,
safeRange
);
if (this._isOnTheFlyFull)
return this.getFliedPosition(newIndex, safeRange);
while (this._onTheFlyIndices[positionToReplace]) {
positionToReplace = this._replaceFurthestIndexPosition(
newIndex,
safeRange
);
}
if (positionToReplace != null) {
this._setMetaIndex(meta, newIndex);
this._onTheFlyIndices[positionToReplace] = onTheFlyPositionMeta;
return this._isOnTheFlyFullReturnHook(positionToReplace);
}
}
this._onTheFlyIndices[prevMetaPosition] = meta;
return this._isOnTheFlyFullReturnHook(prevMetaPosition);
}
// placed on new buffered position
if (!this.isBufferFull)
return this._isOnTheFlyFullReturnHook(
this.getNewPositionForIndex(newIndex)
);
// console.log('this. fly ', this._isOnTheFlyFull)
if (this._isOnTheFlyFull) return this.getFliedPosition(newIndex, safeRange);
let positionToReplace;
const prevIndexMeta = this._indexToMetaMap.get(newIndex);
// console.log('this. is ', this.isBufferFull, prevIndexMeta);
// Index has already been stored, but we cant use its old position directly...
// 1：index -> meta, meta may be reused later
// 2: temp use index -> meta -> position, this issue should exist for follows...
if (!prevIndexMeta) {
this._cleanHeaps();
positionToReplace = this._replaceFurthestIndexPosition(
newIndex,
safeRange
);
} else {
positionToReplace = this._metaToPositionMap.get(prevIndexMeta);
}
// invariant(
// this._valueToPositionMap[newValue] === undefined,
// "Shouldn't try to replace values with value already stored value in " +
// 'BufferSet'
// );
this._cleanHeaps();
if (this._smallValues.empty() || this._largeValues.empty()) {
// Threre are currently no values stored. We will have to create new
// position for this value.
return null;
this._onTheFlyIndices[positionToReplace] = meta;
this._setMetaIndex(meta, newIndex);
this._setMetaPosition(meta, positionToReplace);
// should not push to heap, pop only
// this._pushToHeaps(positionToReplace, newIndex)
return this._isOnTheFlyFullReturnHook(positionToReplace);
}
replaceFurthestIndexPosition(
newIndex: number,
safeRange?: {
startIndex: number;
endIndex: number;
}
) {
if (!this.isBufferFull) {
return this._isOnTheFlyFullReturnHook(
this.getNewPositionForIndex(newIndex)
);
}
if (this._vacantPositions.length) {
const position = this._vacantPositions.pop();
this._valueToPositionMap[newValue] = position;
this._pushToHeaps(position, newValue);
return position;
return this._replaceFurthestIndexPosition(newIndex, safeRange);
}
_replaceFurthestIndexPosition(
newIndex: number,
safeRange?: {
startIndex: number;
endIndex: number;
}
) {
if (this._largeValues.empty() || this._smallValues.empty()) {
return this._isOnTheFlyFullReturnHook(
this.getNewPositionForIndex(newIndex)
);
}
const minValue = this._smallValues.peek()!.value;
const maxValue = this._largeValues.peek()!.value;
if (minValue >= lowValue && maxValue <= highValue) {
// All values currently stored are necessary, we can't reuse any of them.
return null;
// console.log('mxa ', maxValue, minValue);
let indexToReplace;
if (!safeRange) {
// far from min
if (Math.abs(newIndex - minValue) > Math.abs(newIndex - maxValue)) {
indexToReplace = minValue;
this._smallValues.pop();
} else {
indexToReplace = maxValue;
this._largeValues.pop();
}
const replacedMeta = this._indexToMetaMap.get(indexToReplace);
const position = this._metaToPositionMap.get(replacedMeta);
return position;
}
let valueToReplace;
const { startIndex: lowValue, endIndex: highValue } = safeRange;
// All values currently stored are necessary, we can't reuse any of them.
if (
useMinValueFn({
safeRange: {
lowValue,
highValue,
},
bufferSetRange: {
minValue,
maxValue,
},
currentIndex: newValue,
})
isClamped(lowValue, minValue, highValue) &&
isClamped(lowValue, maxValue, highValue)
) {
// if (lowValue - minValue > maxValue - highValue) {
return null;
} else if (
isClamped(lowValue, minValue, highValue) &&
!isClamped(lowValue, maxValue, highValue)
) {
indexToReplace = maxValue;
this._largeValues.pop();
} else if (
!isClamped(lowValue, minValue, highValue) &&
isClamped(lowValue, maxValue, highValue)
) {
indexToReplace = minValue;
this._smallValues.pop();
} else if (lowValue - minValue > maxValue - highValue) {
// minValue is further from provided range. We will reuse it's position.
valueToReplace = minValue;
indexToReplace = minValue;
this._smallValues.pop();
} else {
valueToReplace = maxValue;
indexToReplace = maxValue;
this._largeValues.pop();
}
const position = this._valueToPositionMap[valueToReplace];
delete this._valueToPositionMap[valueToReplace];
this._valueToPositionMap[newValue] = position;
this._pushToHeaps(position, newValue);
const _i = this._vacantPositions.findIndex((v) => v === position);
if (_i !== -1) this._vacantPositions.splice(_i, 1);
const replacedMeta = this._indexToMetaMap.get(indexToReplace);
const position = this._metaToPositionMap.get(replacedMeta);

@@ -203,7 +504,129 @@ return position;

shuffle() {
const indices = new Array(this.bufferSize);
for (let idx = 0; idx < indices.length; idx++) {
const meta = this._onTheFlyIndices[idx] || this._positionToMetaList[idx];
const targetIndex = this.getMetaIndex(meta);
indices[idx] = targetIndex;
}
// console.log(
// 'position xxx ',
// this._positionToMetaList,
// this._onTheFlyIndices
// );
const _arr = new Array(indices.length);
const _available = [];
const indexToMetaMap = new Map();
const metaToIndexMap = new Map();
const metaToPositionMap = new Map();
for (let idx = 0; idx < indices.length; idx++) {
const currentIndex = indices[idx];
const currentMeta = this._metaExtractor(currentIndex);
if (currentMeta == null) continue;
indexToMetaMap.set(currentIndex, currentMeta);
metaToIndexMap.set(currentMeta, currentIndex);
if (currentMeta === this._positionToMetaList[idx]) {
_arr[idx] = currentMeta;
continue;
}
const _i = this._positionToMetaList.findIndex((v) => v === currentMeta);
if (_i !== -1) {
_arr[_i] = currentMeta;
continue;
}
_available.push(currentMeta);
}
const { smallValues, largeValues } = this.initialize();
const positionToMetaList = [];
for (let position = 0; position < indices.length; position++) {
const value = indices[position];
if (_arr[position] != null) {
positionToMetaList[position] = _arr[position];
metaToPositionMap.set(_arr[position], position);
const element = { position, value };
smallValues.push(element);
largeValues.push(element);
continue;
}
const meta = _available.shift();
if (meta != null) {
positionToMetaList[position] = meta;
metaToPositionMap.set(meta, position);
const element = { position, value };
smallValues.push(element);
largeValues.push(element);
}
}
// console.log('position ', positionToMetaList, largeValues.peek().value);
this._positionToMetaList = positionToMetaList;
this._smallValues = smallValues;
this._largeValues = largeValues;
this._indexToMetaMap = indexToMetaMap;
this.replaceMetaToIndexMap(metaToIndexMap);
this._metaToPositionMap = metaToPositionMap;
this._onTheFlyIndices = [];
try {
const indices = new Array(this.bufferSize);
for (let idx = 0; idx < indices.length; idx++) {
const meta =
this._onTheFlyIndices[idx] || this._positionToMetaList[idx];
const targetIndex = this.getMetaIndex(meta);
if (meta != null) {
indices[idx] = {
meta,
targetIndex,
recyclerKey: `${this._name}_${idx}`,
};
}
}
return indices;
} catch (err) {
this.readyToStartNextLoop();
return this._positionToMetaList;
}
}
// key point: `meta` should be preserved..
getIndices() {
try {
const indices = new Array(this.bufferSize);
for (let idx = 0; idx < indices.length; idx++) {
const meta =
this._onTheFlyIndices[idx] || this._positionToMetaList[idx];
const targetIndex = this.getMetaIndex(meta);
// which means source data has changed. such as one element has been deleted
if (meta !== this.getIndexMeta(targetIndex)) {
return this.shuffle();
}
if (meta != null) {
indices[idx] = {
meta,
targetIndex,
recyclerKey: `${this._name}_${idx}`,
};
}
}
// clear on the fly indices after return indices.
this._onTheFlyIndices = [];
return indices;
} catch (err) {
this.readyToStartNextLoop();
return this._positionToMetaList;
}
}
_pushToHeaps(position: number, value: number) {
const element = {
position,
value,
};
const element = { position, value };
// We can reuse the same object in both heaps, because we don't mutate them

@@ -214,2 +637,42 @@ this._smallValues.push(element);

_setMetaPosition(meta: Meta, position: number) {
const prevMetaOnPosition = this._positionToMetaList[position];
if (prevMetaOnPosition) this._metaToPositionMap.delete(prevMetaOnPosition);
this._positionToMetaList[position] = meta;
this._metaToPositionMap.set(meta, position);
}
/**
*
* @param meta
* @param index
* @returns true means index not changed
*/
_setMetaIndex(meta: Meta, index: number) {
const prevMetaIndex = this.getMetaIndex(meta);
if (prevMetaIndex !== undefined) {
// no need to set
// if (prevMetaIndex === index) return true;
this._indexToMetaMap.delete(prevMetaIndex);
}
this.setMetaIndex(meta, index);
this._indexToMetaMap.set(index, meta);
return false;
}
readyToStartNextLoop() {
this._lastUpdatedMS = Date.now();
}
prepare() {
if (this._loopMS === this._lastUpdatedMS) return;
this._loopMS = this._lastUpdatedMS;
this._onTheFlyIndices = [];
this._isOnTheFlyFull = false;
const len = this._positionToMetaList.length;
for (let index = 0; index < len; index++) {}
}
_cleanHeaps() {

@@ -235,2 +698,68 @@ // We not usually only remove object from one heap while moving value.

rebuildHeapsWithValues(
arr: Array<{
position: number;
value: number;
}>
) {
const valueToPositionObject = {};
const newSmallValues = new Heap<HeapItem>([], this._smallerComparator);
const newLargeValues = new Heap<HeapItem>([], this._greaterComparator);
arr.forEach((element) => {
const { position, value } = element;
if (value !== undefined) {
const element = {
position,
value,
};
newSmallValues.push(element);
newLargeValues.push(element);
valueToPositionObject[value] = position;
}
});
const _arr = new Array(this._bufferSize).fill(2);
Object.keys(valueToPositionObject).map(
(key) => (_arr[valueToPositionObject[key]] = 1)
);
_arr.forEach((_i, position) => {
if (_i === 2) {
const value = Number.MAX_SAFE_INTEGER - position;
const element = {
position,
value,
};
newSmallValues.push(element);
newLargeValues.push(element);
valueToPositionObject[value] = position;
}
});
this._smallValues = newSmallValues;
this._largeValues = newLargeValues;
}
// rebuildHeaps() {
// const valueToPositionObject = {};
// const newSmallValues = new Heap<HeapItem>([], this._smallerComparator);
// const newLargeValues = new Heap<HeapItem>([], this._greaterComparator);
// const keys = Object.keys(this._positionToValueObject);
// for (let position = 0; position < keys.length; position++) {
// const value = this._positionToValueObject[position];
// if (value !== undefined) {
// const element = {
// position,
// value,
// };
// valueToPositionObject[value] = position;
// newSmallValues.push(element);
// newLargeValues.push(element);
// }
// }
// this._smallValues = newSmallValues;
// this._largeValues = newLargeValues;
// }
_recreateHeaps() {

@@ -251,4 +780,7 @@ const sourceHeap =

const element = sourceHeap.pop()!;
// Push all stil valid elements to new heaps
if (this._valueToPositionMap[element.value] !== undefined) {
// Push all still valid elements to new heaps
if (
this._metaToPositionMap.get(this._indexToMetaMap.get(element.value)) !=
null
) {
newSmallValues.push(element);

@@ -265,3 +797,5 @@ newLargeValues.push(element);

!heap.empty() &&
this._valueToPositionMap[heap.peek()!.value] === undefined
this._metaToPositionMap.get(
this._indexToMetaMap.get(heap.peek()!.value)
) == null
) {

@@ -268,0 +802,0 @@ heap.pop();

dist/integer-buffer-set.cjs.development.js.map

Sorry, the diff of this file is not supported yet

dist/integer-buffer-set.cjs.production.min.js.map

Sorry, the diff of this file is not supported yet

dist/integer-buffer-set.esm.js.map

Sorry, the diff of this file is not supported yet

SocketSocket SOC 2 Logo

Product

  • Package Alerts
  • Integrations
  • Docs
  • Pricing
  • FAQ
  • Roadmap
  • Changelog

About

Packages

npm

Go

Maven

PyPI

Rubygems

Stay in touch

Get open source security insights delivered straight into your inbox.

  • Terms
  • Privacy
  • Security

Made with ⚡️ by Socket Inc