// Bounded min-heap for top-k selection — CS 499 Enhancement Two.
//
// Used by the recommendation endpoint to keep the k highest-scoring
// trips while scanning the collection once. The heap stores AT MOST k
// items and its root is always the SMALLEST score currently kept, so
// deciding whether a new candidate belongs in the top k is an O(1)
// peek, and inserting/evicting is O(log k).
//
// Total cost of top-k over n candidates: O(n log k) time and O(k)
// space, versus O(n log n) time and O(n) space for sort-then-slice.
// With k fixed at a small number this is asymptotically better and
// the trade-off is documented for Course Outcome 3.

class BoundedMinHeap {
    /**
     * @param {number} capacity - maximum number of items to retain (k)
     * @param {Function} scoreOf - maps an item to its numeric score
     */
    constructor(capacity, scoreOf) {
        if (!Number.isInteger(capacity) || capacity <= 0) {
            throw new RangeError('capacity must be a positive integer');
        }
        this.capacity = capacity;
        this.scoreOf = scoreOf;
        this.items = [];
    }

    size() {
        return this.items.length;
    }

    peek() {
        return this.items[0];
    }

    /**
     * Offers a candidate to the heap. If the heap is full and the
     * candidate scores no higher than the current minimum, it is
     * rejected in O(1); otherwise the minimum is evicted in O(log k).
     */
    offer(item) {
        if (this.items.length < this.capacity) {
            this.items.push(item);
            this.bubbleUp(this.items.length - 1);
            return true;
        }
        if (this.scoreOf(item) <= this.scoreOf(this.items[0])) {
            return false;
        }
        this.items[0] = item;
        this.bubbleDown(0);
        return true;
    }

    // Extracts contents in DESCENDING score order (best first).
    drainDescending() {
        const out = [];
        while (this.items.length > 0) {
            out.push(this.extractMin());
        }
        out.reverse();
        return out;
    }

    extractMin() {
        const min = this.items[0];
        const last = this.items.pop();
        if (this.items.length > 0) {
            this.items[0] = last;
            this.bubbleDown(0);
        }
        return min;
    }

    bubbleUp(index) {
        while (index > 0) {
            const parent = Math.floor((index - 1) / 2);
            if (this.scoreOf(this.items[index]) >= this.scoreOf(this.items[parent])) {
                break;
            }
            [this.items[index], this.items[parent]] =
                [this.items[parent], this.items[index]];
            index = parent;
        }
    }

    bubbleDown(index) {
        const n = this.items.length;
        for (;;) {
            const left = 2 * index + 1;
            const right = 2 * index + 2;
            let smallest = index;
            if (left < n &&
                this.scoreOf(this.items[left]) < this.scoreOf(this.items[smallest])) {
                smallest = left;
            }
            if (right < n &&
                this.scoreOf(this.items[right]) < this.scoreOf(this.items[smallest])) {
                smallest = right;
            }
            if (smallest === index) {
                return;
            }
            [this.items[index], this.items[smallest]] =
                [this.items[smallest], this.items[index]];
            index = smallest;
        }
    }
}

module.exports = BoundedMinHeap;
