export function quantizeHistogram()

in packages/utilities/fast-colors/src/color-quantization.ts [105:216]
86 lines of code
19 McCabe index (conditional complexity)

export function quantizeHistogram(
    histogram: Histogram,
    config: QuantizeConfig = defaultQuantizeConfig
): QuantizedColor[] {
    const initialBox: PixelBox = new PixelBox(
        histogram,
        histogram.minRed,
        histogram.maxRed,
        histogram.minGreen,
        histogram.maxGreen,
        histogram.minBlue,
        histogram.maxBlue
    );

    const queue: PixelBox[] = [initialBox];
    let count: number = countValidBoxes(queue, config.isBoxValid);

    // For a final palette of size targetPaletteSize, we determine the first fractionByPopulation*targetPaletteSize
    // using population as the only factor when determening sort order. For the rest of the colors the
    // sort order is population * colorVolume. This helps highly contrasting colors in a small area to show
    // up in some of the final output.
    const colorsByPopulation: number = Math.floor(
        config.targetPaletteSize * config.fractionByPopulation
    );
    const popSort: (box: PixelBox) => number = (box: PixelBox): number => {
        return box.pixelCount;
    };

    let iterationCount: number = 0;
    while (iterationCount <= config.maxIterations) {
        if (queue.length > 0) {
            const currentBox: PixelBox = queue.shift()!;

            const cutBoxes: [
                PixelBox | null,
                PixelBox | null
            ] = currentBox.modifiedMedianCut();

            if (cutBoxes[0] !== null) {
                insertIntoSortedList(queue, cutBoxes[0], popSort);
            }
            if (cutBoxes[1] !== null) {
                insertIntoSortedList(queue, cutBoxes[1], popSort);
            }
        }

        count = countValidBoxes(queue, config.isBoxValid);
        if (count >= colorsByPopulation || queue.length <= 1) {
            break;
        }

        iterationCount++;
    }

    if (count < config.targetPaletteSize) {
        const popAndVolumeSort: (box: PixelBox) => number = (box: PixelBox): number => {
            return box.pixelCount * box.colorVolume;
        };

        queue.sort((a: PixelBox, b: PixelBox) => {
            const aSort: number = popAndVolumeSort(a);
            const bSort: number = popAndVolumeSort(b);
            if (aSort === bSort) {
                return 0;
            } else if (aSort > bSort) {
                return -1;
            }
            return 1;
        });

        iterationCount = 0;
        while (iterationCount <= config.maxIterations) {
            if (queue.length > 0) {
                const currentBox: PixelBox = queue.shift()!;

                const cutBoxes: [
                    PixelBox | null,
                    PixelBox | null
                ] = currentBox.modifiedMedianCut();

                if (cutBoxes[0] !== null) {
                    insertIntoSortedList(queue, cutBoxes[0], popAndVolumeSort);
                }
                if (cutBoxes[1] !== null) {
                    insertIntoSortedList(queue, cutBoxes[1], popAndVolumeSort);
                }
            }

            count = countValidBoxes(queue, config.isBoxValid);
            if (count >= config.targetPaletteSize || queue.length <= 1) {
                break;
            }

            iterationCount++;
        }
    }

    const retVal: QuantizedColor[] = new Array(count);
    let index: number = 0;
    for (let i: number = 0; i < queue.length; i++) {
        if (!config.isBoxValid || config.isBoxValid(queue[i])) {
            retVal[index] = {
                color: queue[i].averageColor,
                pixelCount: queue[i].pixelCount,
                colorVolume: queue[i].colorVolume,
            };
            index++;
        }
    }

    return retVal;
}