File Explorer

1/*2 * Copyright Amazon.com, Inc. or its affiliates. All Rights Reserved.3 * SPDX-License-Identifier: Apache-2.0.4 */5 6import * as heap from "./heap";7 8interface ElementType {9    timestamp: number;10    id: number;11}12 13function compareElements(lhs: ElementType, rhs: ElementType) {14    if (lhs.timestamp < rhs.timestamp) {15        return true;16    } else if (lhs.timestamp > rhs.timestamp) {17        return false;18    } else {19        return lhs.id < rhs.id;20    }21}22 23test('empty', async () => {24    let testHeap : heap.MinHeap<ElementType> = new heap.MinHeap<ElementType>(compareElements);25    expect(testHeap.empty()).toBeTruthy();26    expect(testHeap.peek()).toBeUndefined();27 28    testHeap.push({timestamp: 0, id: 1});29    expect(testHeap.empty()).toBeFalsy();30    expect(testHeap.peek()).toBeDefined();31 32    testHeap.pop();33    expect(testHeap.empty()).toBeTruthy();34    expect(testHeap.peek()).toBeUndefined();35});36 37function doSimplePushPopTest(testHeap : heap.MinHeap<ElementType>, timestamps: Array<number>) {38    let currentId = 1;39    for (let timestamp of timestamps) {40        testHeap.push({timestamp: timestamp, id: currentId++});41    }42 43    let peekedIds : Array<number> = [];44    let poppedIds : Array<number> = [];45    let poppedTimestamps : Array<number> = [];46    let peekedTimestamps : Array<number> = [];47    while (!testHeap.empty()) {48        // @ts-ignore49        peekedTimestamps.push(testHeap.peek().timestamp);50        // @ts-ignore51        peekedIds.push(testHeap.peek().id);52 53        let entry = testHeap.pop();54        poppedTimestamps.push(entry.timestamp);55        poppedIds.push(entry.id);56    }57 58    let sortedTimestamps = timestamps.sort((lhs, rhs) => {59        if (lhs < rhs) {60            return -1;61        } else if (lhs > rhs) {62            return 1;63        } else {64            return 0;65        }66    });67 68    expect(poppedTimestamps).toEqual(sortedTimestamps);69    expect(peekedTimestamps).toEqual(sortedTimestamps);70 71    // when there are timestamps ties, we expect the ids to be in increasing order72    for (let i = 0; i + 1 < timestamps.length; i++) {73        if (poppedTimestamps[i] == poppedTimestamps[i + 1]) {74            expect(poppedIds[i] < poppedIds[i + 1]).toBeTruthy();75        }76    }77}78 79test('reverseOrderPushPop', async () => {80    let testHeap : heap.MinHeap<ElementType> = new heap.MinHeap<ElementType>(compareElements);81 82    let timestamps = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];83    doSimplePushPopTest(testHeap, timestamps);84});85 86test('alternatingOrderPushPop', async () => {87    let testHeap : heap.MinHeap<ElementType> = new heap.MinHeap<ElementType>(compareElements);88 89    let timestamps = [10, -10, 9, -9, 8, -8, 7, -7, 6, -6, 5, -5, 4, -4, 3, -3, 2, -2, 1, -1, 0];90    doSimplePushPopTest(testHeap, timestamps);91});92 93test('randomOrderPushPop', async () => {94    let testHeap : heap.MinHeap<ElementType> = new heap.MinHeap<ElementType>(compareElements);95 96    let timestamps = [];97 98    for (let i = 0; i < 100; i++) {99        timestamps.push(Math.floor(Math.random() * 1000 + .5));100    }101 102    doSimplePushPopTest(testHeap, timestamps);103});104 105test('duplicate timestamps', async () => {106    let testHeap : heap.MinHeap<ElementType> = new heap.MinHeap<ElementType>(compareElements);107 108    let timestamps = [7, 2, 5, 2, -1, 0, 5, 0];109    doSimplePushPopTest(testHeap, timestamps);110});111 112test('peek empty', async () => {113    let testHeap : heap.MinHeap<ElementType> = new heap.MinHeap<ElementType>(compareElements);114 115    expect(() => { testHeap.pop(); }).toThrow("empty");116});117 118test('clear', async () => {119    let testHeap : heap.MinHeap<ElementType> = new heap.MinHeap<ElementType>(compareElements);120 121    let timestamps = [10, 9, 8, 7, 6, 5, 4, 3, 2, 1, 0];122    let currentId = 1;123    for (let timestamp of timestamps) {124        testHeap.push({timestamp: timestamp, id: currentId++});125    }126 127    expect(testHeap.empty()).toBeFalsy();128 129    testHeap.clear();130 131    expect(testHeap.empty()).toBeTruthy();132    expect(() => { testHeap.pop(); }).toThrow("empty");133});