Source: index.js

'use strict';
const TimeWindow = require('./timeWindow');



/**
 * User-supplied callback that extracts a timestamp from an element in a time-ordered array of events.
 * 
 * @callback timestampSelector
 * @param {any} elem - Timestamped element in a time-ordered array of events.
 * @returns {number} The time that the elem argument occurred, represented as milliseconds elapsed since January 1, 1970 00:00:00 UTC.
 */

/**
 * Transforms an ordered array into an array of sliding windows. The source array must be sorted chronologically.
 * @param {Array} sourceArray - Array of time-ordered elements to transform.
 * @param {timestampSelector} timestampSelector - Function to extract a timestamp from elements in the source array.
 * @param {number} windowDuration - Duration of each time window in milliseconds. This is a maximum value that will be shortened for the last window(s) in the returned sequence.
 * @param {number} every - The period of time, in milliseconds, between the start of each sliding window.
 * @param {number} start - Start time (inclusive) of the first sliding window, expressed as milliseconds elapsed since January 1, 1970 00:00:00 UTC. If undefined, the timestamp of the array's first element will be used.
 * @param {number} end - End time (exclusive) for the last sliding window(s), expressed as milliseconds elapsed since January 1, 1970 00:00:00 UTC. If undefined, the timestamp of the array's last element will be used, and the last window's end time will be inclusive.
 * @returns {TimeWindow[]} An array of TimeWindow instances.
 */
function toSlidingWindows(sourceArray, timestampSelector, windowDuration, every, start, end) {
    if (!Array.isArray(sourceArray)) {
        throw new TypeError('sourceArray must be an Array instance');
    }
    if (typeof timestampSelector !== 'function') {
        throw new TypeError(timestampSelector + ' is not a function');
    }
    if (every == null || !Number.isInteger(every)) {
        throw new TypeError('The "every" argument must be an integer representing a duration in milliseconds.');
    }
    if (sourceArray.length === 0) {
        return [];
    }

    // Automatically deduce start/end times if none are provided:
    if (start == null) {
        start = timestampSelector(sourceArray[0]);
    }

    let autoEndTime = false;
    if (end == null) {
        // Look at the last item's timestamp and use it as the 
        // end time for this transform (we also make the end date inclusive for the
        // final window(s)--otherwise the last item wouldn't be included).
        end = timestampSelector(sourceArray[sourceArray.length -1]);
        autoEndTime = true;
    }
    if (!Number.isInteger(start) || !Number.isInteger(end)) {
        throw new TypeError('start and end time arguments must be integers (typically milliseconds elapsed since January 1, 1970 00:00:00 UTC.');
    }
    if (start > end) {
        throw new TypeError('start time occurs after end time.');
    }

    // create (empty) windows
    const windows = [];
    let winStart = start;
    while (winStart < end)
    {
        let actualDur = windowDuration;
        if ((winStart + windowDuration) > end) {
            actualDur = end - winStart;
        }

        const isLastWindow = ((winStart + every) < end) ? false : true;

        let isEndInclusive = false;
        if (autoEndTime && isLastWindow) {
            // this window bumps up agains the final endDate, and the user is letting
            // the algorithm automatically pick the end time. In this
            // scenario, we make the end time of the final window inclusive.
            isEndInclusive = true;
        }

        // Leaving the TimeWindow's sourceIndex & length members undefined here--will populate them
        // in the next loop that does a pass through the sourceArray.
        windows.push(new TimeWindow(sourceArray, winStart, winStart + actualDur, isEndInclusive));
        winStart += every;
    }

    // calculate each Window's offset and length in the source array. We memoize
    // the prior window's starting point so we don't have to traverse the entire
    // array to find each window's starting point.
    let startingIndexMemo = 0;
    
    for (const win of windows) {
        let foundStart = false;
        for (let i = startingIndexMemo; i < sourceArray.length; i++) {
            const timestamp = timestampSelector(sourceArray[i]);
            
            if (!foundStart) {
                win.sourceIndex = i;
                if (timestamp < win.start) {
                    continue; // keep looking for a start index in the source array.
                }
                else
                {
                    // We found the starting index for the window.
                    foundStart = true;
                    startingIndexMemo = i;
                }
            }

            if ((win.isEndInclusive && timestamp > win.end) ||
               (!win.isEndInclusive && timestamp >= win.end)) {
                // Element is outside of the window's end time. Close it out and move on to
                // the next window.
                win.length = (i - win.sourceIndex);
                break;
            }

            if (i === (sourceArray.length - 1)) {
                // Last element in the source array. Close out the window.
                win.length = (sourceArray.length - win.sourceIndex);
                break;
            }

        }
    }
    

    return windows;
}

/**
 * Transforms an ordered array into an array of non-overlapped, fixed-time windows. The source array must be sorted chronologically.
 * @param {Array} sourceArray - Array of time-ordered elements to transform.
 * @param {timestampSelector} timestampSelector - Function to extract a timestamp from elements in the source array.
 * @param {number} windowDuration - Duration of each time window in milliseconds. This is a maximum value that may be shortened for the last window in the returned sequence.
 * @param {number} start - Start time (inclusive) of the first sliding window, expressed as milliseconds elapsed since January 1, 1970 00:00:00 UTC. If undefined, the timestamp of the array's first element will be used.
 * @param {number} end - End time (exclusive) for the last sliding window(s), expressed as milliseconds elapsed since January 1, 1970 00:00:00 UTC. If undefined, the timestamp of the array's last element will be used, and the last window's end time will be inclusive.
 * @returns {TimeWindow[]} An array of TimeWindow instances.
 */
function toTumblingWindows(sourceArray, timestampSelector, windowDuration, start, end) {
    return toSlidingWindows(sourceArray, timestampSelector, windowDuration, windowDuration, start, end);
}

/**
 * Transforms an ordered array into an array of session windows. The source array must be sorted chronologically.
 * @param {Array} sourceArray - Array of time-ordered elements to transform.
 * @param {timestampSelector} timestampSelector - Function to extract a timestamp from elements in the source array.
 * @param {number} idleThreshold - max allowed time gap between elements before a new session is started, in milliseconds.
 * @returns {TimeWindow[]} An array of TimeWindow instances.
 */
function toSessionWindows(sourceArray, timestampSelector, idleThreshold) {
    if (!Array.isArray(sourceArray)) {
        throw new TypeError('sourceArray must be an Array instance');
    }
    if (typeof timestampSelector !== 'function') {
        throw new TypeError(timestampSelector + ' is not a function');
    }
    if (!Number.isInteger(idleThreshold) || idleThreshold <= 0) {
        throw new TypeError('The "idleThreshold" argument must be a positive integer representing a duration in milliseconds.');
    }
    if (sourceArray.length === 0) {
        return [];
    }
    const windows = [];
    const firstTimestamp = timestampSelector(sourceArray[0]);
    let currentWindowStartTime = firstTimestamp;
    let currentWindowEndTime = firstTimestamp;
    let currentWindowStartIndex = 0;

    for (let i = 1; i < sourceArray.length; i++) {
        const elem = sourceArray[i];
        const timestamp = timestampSelector(elem);
            
        if (timestamp - currentWindowEndTime > idleThreshold) {
            // idle threshold exceeded; close out current window and create a new one for this element.
            windows.push(new TimeWindow(sourceArray, currentWindowStartTime, currentWindowEndTime, true, currentWindowStartIndex, i - currentWindowStartIndex));
            currentWindowStartTime = currentWindowEndTime = timestamp;
            currentWindowStartIndex = i;
        }
        else {
            currentWindowEndTime = timestamp;
        }
    }

    // close out the last window.
    windows.push(new TimeWindow(sourceArray, currentWindowStartTime, currentWindowEndTime, true, currentWindowStartIndex, sourceArray.length - currentWindowStartIndex));

    return windows;
}

/**
 * Adds one or more elements to a time-ordered array of items, inserting them in chronological order.
 * @param {Array} arr - destination array for new element(s).
 * @param {timestampSelector} timestampSelector - function to extract a timestamp from an element.
 * @param {...any} values - value(s) to add to the array.
 */
function addToOrdered(arr, timestampSelector, ...values) {
    if (!Array.isArray(arr)) {
        throw new TypeError('arr must be an Array instance');
    }
    if (typeof timestampSelector !== 'function') {
        throw new TypeError(timestampSelector + ' is not a function');
    }

    for (let i = 0; i < values.length; i++) {
        const timestamp = timestampSelector(values[i]);
        if (timestamp == null) {
            throw new Error('timestampSelector returned null/undefined.');
        }

        // We assume that the incoming values are the newest events and will
        // therefore be inserted at/near the end of the array. So rather than sorting
        // the entire array every time we do an add, we do a reverse linear search to
        // find the location. If our assumption holds then performance will be near O(1).
        let insertPosition = arr.length;
        while (insertPosition > 0) {
            if (timestamp < timestampSelector(arr[insertPosition - 1]))
                insertPosition--;
            else
                break;
        }
        arr.splice(insertPosition, 0, values[i]);
    }
}

/**
 * Adds one or more elements to a time-ordered array of items, inserting them in chronological order. If
 * the size of the destination array exceeds the supplied maxArraySize argument, the oldest elements in
 * the destination array will be evicted.
 * @param {Array} arr - destination array for new element(s).
 * @param {number} maxArraySize - max allowed size of destination array before eviction begins.
 * @param {timestampSelector} timestampSelector - function to extract a timestamp from an element.
 * @param {...any} values - value(s) to add to the array.
 */
function addToOrderedAndEvictOldest(arr, maxArraySize, timestampSelector, ...values) {
    if (!Number.isInteger(maxArraySize) || maxArraySize <= 0) {
        throw new RangeError('maxArraySize must be a positive integer.');
    }

    addToOrdered(arr, timestampSelector, ...values);

    const removeCount = arr.length - maxArraySize;
    if (removeCount > 0) {
        removeFirstItems(arr, removeCount);
    }
}

/**
 * Adds one or more elements to a time-ordered array of items, inserting them in chronological order. Any
 * elements in the array with a timestamp prior to the supplied startTime argument will be evicted from the 
 * destination array.
 * @param {Array} arr - destination array for new element(s).
 * @param {Date|number} startTime - start time (inclusive) of the first allowed element in the destination array.
 * @param {timestampSelector} timestampSelector - function to extract a timestamp from an element.
 * @param {...any} values - value(s) to add to the array.
 */
function addToOrderedAndEvictBefore(arr, startTime, timestampSelector, ...values) {
    addToOrdered(arr, timestampSelector, ...values);
    
    // find index of first element to keep.
    let removeCount = 0;
    while (removeCount < arr.length)
    {
        if (timestampSelector(arr[removeCount]) < startTime)
            removeCount++;
        else
            break;
    }

    if (removeCount > 0)
        removeFirstItems(arr, removeCount);
}

/**
 * Adds one or more elements to a time-ordered array of items, inserting them in chronological order. If
 * the number of sessions in the destination array exceeds the supplied maxSessionCount argument, elements 
 * in the oldest session(s) in the destination array will be evicted.
 * @param {Array} arr - destination array for new element(s).
 * @param {number} maxSessionCount - max allowed number of sessions.
 * @param {timestampSelector} timestampSelector - function to extract a timestamp from an element.
 * @param {number} idleThreshold - max allowed time gap between elements before a new session is started, in milliseconds.
 * @param {...any} values - value(s) to add to the array.
 */
function addToOrderedAndEvictSessions(arr, maxSessionCount, timestampSelector, idleThreshold, ...values) {
    if (!Number.isInteger(maxSessionCount) || maxSessionCount < 1) {
        throw new RangeError('maxSessionCount must be a positive integer.');
    }
    if (!Number.isInteger(idleThreshold) || idleThreshold <= 0) {
        throw new TypeError('The "idleThreshold" argument must be a positive integer representing a duration in milliseconds.');
    }

    addToOrdered(arr, timestampSelector, ...values);
    const sessions = toSessionWindows(arr, timestampSelector, idleThreshold);
    const sessionRemoveCount = sessions.length - maxSessionCount;
    if (sessionRemoveCount > 0) {
        const removeCount = sessions[sessionRemoveCount].sourceIndex;
        removeFirstItems(arr, removeCount);
    }
}

/**
 * Perform in-place removal of the first N elements in an array.
 * @param {Array} arr - array to be modified.
 * @param {number} count - Number of elements to remove from the front of the array.
 */
function removeFirstItems(arr, count) {
    if (!Array.isArray(arr)) {
        throw new TypeError('arr must be an Array instance');
    }
    if (!Number.isInteger(count) || count < 0) {
        throw new RangeError('count must be a positive integer.');
    }
    if (count > arr.length) {
        throw new RangeError('count cannot be larger than array\'s length');
    }

    if (count === 1) {
        arr.shift();
    }
    else if (count >= 1) {
        // Instead of repeatedly making the expensive shift() call,
        // we manually shift elements in a single pass:
        for (let from = count, to = 0; from < arr.length; from++, to++) {
            arr[to] = arr[from];
        }
        // Use Array.length to truncate leftover elements:
        arr.length = arr.length - count;
    }

}

module.exports = {
    toSlidingWindows: toSlidingWindows,
    toTumblingWindows: toTumblingWindows,
    toSessionWindows: toSessionWindows,
    addToOrdered: addToOrdered,
    addToOrderedAndEvictOldest: addToOrderedAndEvictOldest,
    addToOrderedAndEvictBefore: addToOrderedAndEvictBefore,
    addToOrderedAndEvictSessions: addToOrderedAndEvictSessions,
    removeFirstItems: removeFirstItems
};