<div style="width: 100vw; height: 100vh;">
    <canvas id = 'graph'></canvas>
</div>
<script src="./main.js"></script>

/**
 * 
 * @param array ソート対象の配列
 * @param compareFunction 比較関数(昇順: a < b)
 * @param option ソートの範囲やステップごとに呼ばれる関数など
 * @returns 
 */
async function qsort<T>(array: T[], compareFunction: (a: T, b: T) => boolean, option?: { start?: number, end?: number, fn?: (array: T[], i: number, pivot: number) => Promise<void> }): Promise<T[]> {
    //ソート対象の範囲
    const start = (option?.start != undefined) ? option.start : 0;
    const end = (option?.end != undefined) ? option.end : array.length;

    //基準値
    let pivot = start;

    //要素数が2以下であれば返す
    if (end - start < 2) return array;

    for (let i = Math.max(start, 0) + 1; i < Math.min(end, array.length); i++) {
        //比較した結果に応じて配列を並び変える(本来なら2つの配列に分ける)
        if (compareFunction(array[i], array[pivot])) {
            array.splice(pivot, 0, array[i]);
            array.splice(i + 1, 1);
            pivot++;
        }

        //オプションで関数が与えられていた場合呼び出す
        if (option?.fn) await option.fn(array, i, pivot);
    }

    //再帰的にソート関数を呼び出す
    array = await qsort(array, compareFunction, { start: start, end: pivot, fn: option?.fn })
    array = await qsort(array, compareFunction, { start: pivot + 1, end: end, fn: option?.fn });

    return array;
}

class Graph {
    private canvas: HTMLCanvasElement;
    private parent: HTMLElement;
    private data: {
        value: number,
        color: string,
    }[];
    private size: { width: number, height: number };
    private max: number;

    /**
     * 
     * @param graphID 
     * @param max グラフの最大値
     */
    constructor(graphID: string, max: number) {
        let graph = document.getElementById(graphID);
        if (graph && graph.tagName == 'CANVAS') {
            this.canvas = graph as HTMLCanvasElement;
        }
        else {
            throw new Error("graph is not canvas");
        }

        const parent = this.canvas.parentElement;
        if (!parent) {
            throw new Error("parent is null");
        }
        this.parent = parent;

        this.size = { width: 0, height: 0 };
        this.data = new Array();
        this.max = max;
    }

    private resize() {
        this.size.width = this.parent.clientWidth;
        this.size.height = this.parent.clientHeight;

        this.canvas.setAttribute('width', this.size.width.toString());
        this.canvas.setAttribute('height', this.size.height.toString());
        this.canvas.width = this.size.width;
        this.canvas.height = this.size.height;
    }

    draw() {
        this.resize();
        const context = this.canvas.getContext('2d');
        if (!context) {
            return;
        }

        //背景を黒で塗りつぶす
        context.beginPath();
        context.rect(0, 0, this.size.width, this.size.height);
        context.fillStyle = "black";
        context.fill();
        context.closePath();

        //サイズの計算
        const width = this.size.width / this.data.length;
        const heightScale = this.max / this.size.height;

        //棒グラフの描画
        for (let i = 0; i < this.data.length; i++) {
            context.beginPath();
            context.rect(i * width, this.size.height - (this.data[i].value / heightScale), width, this.size.height);
            context.fillStyle = this.data[i].color;
            context.fill();
            context.closePath();
        }
    }

    /**
     * 
     * @param data グラフの値と色の配列
     * @param max 最大値
     */
    setData(data: { value: number, color: string, }[], max?: number) {
        this.data = data;
        if (max) this.max = max;
    }
}

const wait = async (ms: number) => new Promise(resolve => setTimeout(resolve, ms));

async function main() {
    //配列の初期化
    let array: number[] = new Array();
    for (let i = 0; i < 256; i++) {
        array.push(i);
    }

    const g = new Graph('graph', array.length);

    async function draw(a: number[], _i: number, pivot: number) {
        const data: { value: number, color: string, }[] = new Array();
        for (let i = 0; i < a.length; i++) {
            if (i == _i) {
                data.push({ value: a[i], color: "green" });
            }
            else if (i == pivot) {
                data.push({ value: a[i], color: "red" });
            }
            else {
                data.push({ value: a[i], color: "lightblue" });
            }
        }
        await wait((1 / a.length) * 10000);
        g.setData(data);
        g.draw();

        return;
    }

    while (true) {
        //シャッフル
        array = await qsort(array, () => { return Math.random() - 0.5 < 0 });

        //ソート
        array = await qsort(array, (a, b) => { return a < b }, { fn: draw });
    }
}

main();