queue-property-check.ts

import fc = require('fast-check')
import isArraySorted = require('is-array-sorted')

class AsyncSemaphore {
    private promises = Array<() => void>()

    constructor(private permits: number) {}

    signal() {
        this.permits += 1
        if (this.promises.length > 0) this.promises.pop()!()
    }

    async wait() {
        this.permits -= 1
        if (this.permits < 0 || this.promises.length > 0)
            await new Promise(r => this.promises.unshift(r))
    }
}

class AsyncQueue<T> {
    private queue = Array<T>()
    private waitingEnqueue: AsyncSemaphore

    constructor() {
        this.waitingEnqueue = new AsyncSemaphore(0)
    }

    enqueue(x: T) {
        this.queue.unshift(x)
        this.waitingEnqueue.signal()
    }

    async dequeue() {
        await this.waitingEnqueue.wait()
        return this.queue.pop()! 
    }
}

async function testAsyncQueueBehavior(ops: Array<boolean>): Promise<boolean> {
    const result = new Array<number>()
    const q = new AsyncQueue<number>()

    const enqueue = (m: number) => q.enqueue(m)
    const dequeue = () => q.dequeue()
    const promises = Array<Promise<void>>()

    let enqueues = 0
    let dequeues = 0

    for (const op of ops) {
        if (op) { // True is Enqueue
            enqueues += 1 
            enqueue(enqueues)
        } else {  // False is Dequeue
            dequeues += 1 
            promises.push(dequeue().then(v => { result.push(v) }))
        }
    }

    const pending = Math.min(enqueues, dequeues) 
    await Promise.all(promises.slice(0, pending))

    // Length should be equal minimum between enqueues and dequeues
    const isLengthOk = pending === result.length 

    // Messages should be ordered
    const isSorted = isArraySorted(result) 

    return isLengthOk && isSorted
}

fc.assert(
    fc.asyncProperty(
        fc.array(fc.boolean(), 1000), 
        async (ns) => testAsyncQueueBehavior(ns)), { numRuns: 1000 }); //?

semaphore-property-check.ts

import fc = require('fast-check')
import isArraySorted = require('is-array-sorted')

class AsyncSemaphore {
    private promises = Array<() => void>()

    constructor(private permits: number) {}

    signal() {
        this.permits += 1 
        if (this.promises.length > 0) this.promises.pop()!()
    }

    async wait() {
        this.permits -= 1 
        if (this.permits < 0 || this.promises.length > 0) 
            await new Promise(r => this.promises.unshift(r))
    }
}

async function testSemaphore(size: number, ops: Array<boolean>) {
    const sem = new AsyncSemaphore(size)
    const res = Array<boolean>()
    const promises = Array<Promise<number>>()
    const signals = ops.filter(op => op).length
    const waits = ops.filter(op => !op).length

    for (const op of ops) {
        if (op) {
            sem.signal()
        } else {
            promises.push(sem.wait().then(() => res.push(true)))
        }
    }

    await Promise.all(promises.slice(0, signals + size))
    
    return res.length === Math.min(signals + size, waits)
}

fc.assert(
    fc.asyncProperty(
        fc.nat(10),
        fc.array(fc.boolean(), 100),
        async (size, ops) => testSemaphore(size, ops)),
        { numRuns: 1000 }) //?