const { EventEmitter } = require('events'); const ExistsError = require('./errors/ExistsError'); const NotExistsError = require('./errors/NotExistsError'); class MinRand { /** * Creates a new MinRand instance * @param {Array} dataset An array containing the dataset * @param {Object} [usedDataPoints={}] A key-value object containing the arrays of used datapoints. Converted to a Map internally. * @throws {TypeError} */ constructor(dataset, usedDataPoints = {}) { if (!Array.isArray(dataset)) { throw new TypeError('Dataset must be an array'); } if (!(typeof usedDataPoints === 'object' && !Array.isArray(usedDataPoints))) { throw new TypeError('Used data points must be an object'); } this.dataset = dataset; this.usedDataPoints = new Map(Object.entries(usedDataPoints)); this.usedResetPercentage = 0.9; this.eventEmitter = new EventEmitter(); } /** * Returns the EventEmitter * @returns {EventEmitter} The EventEmitter * @see {@link MinRand#event:reset} */ getEventEmitter() { return this.eventEmitter; } /** * Returns the dataset * @returns {Array} An array containing the dataset */ getDataset() { return this.dataset; } /** * Sets the dataset * @param {Array} dataset An array containing the dataset * @throws {TypeError} */ setDataset(dataset) { if (!Array.isArray(dataset)) { throw new TypeError('Dataset must be an array'); } this.dataset = dataset; } /** * Returns the usage percentage at which the first half of the used datapoint store will be removed * @returns {double} The percentage in decimal form */ getUsedResetPercentage() { return this.usedResetPercentage; } /** * Sets the usage percentage at which the first half of the used datapoint store will be removed * @param {double} percentage A percentage in decimal form between 0.01 and 0.99 (inclusive) * @throws {TypeError} * @throws {RangeError} */ setUsedResetPercentage(percentage) { if (typeof percentage !== 'number' || !percentage.toString().match(/^[0-9]+(?:\.[0-9]+)?$/)) { throw new TypeError('Percentage must be numerical'); } if (percentage < 0.01 || percentage > 0.99) { throw new RangeError('Percentage must be between 0.01 and 0.99 (inclusive)'); } this.usedResetPercentage = percentage; } /** * Removes a value from the dataset array, and all used datapoint arrays * @param {*} value The value to remove */ removeDatasetPoint(value) { this.dataset = this.dataset.filter(e => e !== value); this.usedDataPoints.forEach((v, k) => { var _v = v.filter(e => e !== value); this.usedDataPoints.set(k, _v); }); } /** * Adds a value to the dataset array * @param {*} value The value to add */ addDatasetPoint(value) { this.dataset.push(value); } /** * Returns the used data points map * @returns {Map} The used data points map */ getUsedDataPoints() { return this.usedDataPoints; } /** * Gets the used datapoints for the specified key * @param {*} key The key * @returns {Array|undefined} An array of used datapoints for this key. Undefined if it does not exist */ getUsedDataPointArray(key) { return this.usedDataPoints.get(key); } /** * Sets the used datapoints for the specified key * @param {*} key The key * @param {*} array The array of datapoints * @throws {TypeError} */ setUsedDataPointArray(key, array) { if (!Array.isArray(array)) { throw new TypeError('Dataset must be an array'); } this.usedDataPoints.set(key, array); } /** * Adds a used datapoint to a key * @param {*} key The key * @param {*} datapoint The datapoint to add * @throws {NotExistsError} If the key does not exist or if the datapoint is not already in the dataset * @throws {ExistsError} If the datapoint already exists for the specified key */ addUsedDataPoint(key, datapoint) { var _dataPoints = this.usedDataPoints.get(key); if (!_dataPoints) { throw new NotExistsError(); } if (!this.dataset.includes(datapoint)) { throw new NotExistsError('That datapoint does not exist'); } if (_dataPoints.includes(datapoint)) { throw new ExistsError('That datapoint already exists'); } _dataPoints.push(datapoint); } /** * Adds an empty used data point array for the specified key * @param {*} key The key * @param {boolean} [force=false] Whether to override an existing key * @throws {ExistsError} An error thrown if the key already exists */ addUsedDataPointKey(key, force = false) { if (!force && this.usedDataPoints.has(key)) { throw new ExistsError(); } this.usedDataPoints.set(key, []); } /** * Removes a used datapoint key * @param {*} key The key * @throws {NotExistsError} */ removeUsedDataPointKey(key) { if (!this.usedDataPoints.has(key)) { throw new NotExistsError(); } this.usedDataPoints.delete(key); } /** * Removes the first half of the used datapoints for the specified key, if needed * @param {*} key The key * @returns {boolean} Whether the reset occurred * @private */ _resetIfNeeded(key) { var _thisUDP = this.usedDataPoints.get(key); if (this.dataset.length > 0) { if (_thisUDP.length >= Math.floor(this.dataset.length * this.usedResetPercentage)) { var _halfLength = Math.ceil(_thisUDP.length / 2); //console.log(`${_thisUDP.length} datapoints used. Clearing first ${_halfLength} datapoints from used datapoints array`); var _thisUDPRight = _thisUDP.slice(_halfLength); this.usedDataPoints.set(key, _thisUDPRight); return true; } } return false; } /** * Gets a random datapoint not in the used datapoint store specified by key, * and adds this to the used datapoint array for the key * @param {*} key The key * @returns {*} The random datapoint * @fires MinRand#reset * @throws {NotExistsError} */ getRandomDataPoint(key) { if (!this.usedDataPoints.has(key)) { throw new NotExistsError(); } if (this._resetIfNeeded(key)) { /** * The reset event fires when the first half of the used datapoints for the specified key is removed * @event MinRand#reset * @type {object} * @property {*} key The key that was reset */ this.eventEmitter.emit('reset', { key }); } // This was originally done using Array.prototype.filter(), // but for a native function, I expected it to be a lot faster. // The code below seems to be the fastest filtering algorithm. // Speed of getting 100000 random values: // Array.prototype.filter: 834ms // This code: 477ms // A custom C++ filtering algorithm was implemented as a test, // but due to my lack of C++ knowledge, took 1954ms to complete // and was therefore removed. var udpMap = this.usedDataPoints.get(key); var udpSet = new Set(udpMap); var randArr = []; for (var i = 0; i < this.dataset.length; i++) { // Array.prototype.includes() is slow (>1000ms for this test). Using a set is much faster. if (!udpSet.has(this.dataset[i])) { randArr.push(this.dataset[i]); } } var randDataPoint = randArr[Math.floor(Math.random() * randArr.length)]; this.usedDataPoints.get(key).push(randDataPoint); return randDataPoint; } } module.exports = MinRand;