/**
Binary search on a sorted flat array of [start, end] pairs.

@param {number[]} ranges - Flat array of inclusive [start, end] range pairs, e.g. [0, 5, 10, 20].
@param {number} codePoint - The value to search for.
@returns {boolean} Whether the value falls within any of the ranges.
*/
export const isInRange = (ranges, codePoint) => {
  let low = 0;
  let high = Math.floor(ranges.length / 2) - 1;
  while (low <= high) {
    const mid = Math.floor((low + high) / 2);
    const i = mid * 2;
    if (codePoint < ranges[i]) {
      high = mid - 1;
    } else if (codePoint > ranges[i + 1]) {
      low = mid + 1;
    } else {
      return true;
    }
  }

  return false;
};

export function binarySearch(flatRanges) {
	return (codePoint) => {
		let low = 0;
		let high = Math.floor(flatRanges.length / 2) - 1;
		while (low <= high) {
			const mid = Math.floor((low + high) / 2);
			const i = mid * 2;
			if (codePoint < flatRanges[i]) {
				high = mid - 1;
			} else if (codePoint > flatRanges[i + 1]) {
				low = mid + 1;
			} else {
				return true;
			}
		}

		return false;
	};
}

const key = (codePoint) => (codePoint >>> 8) & 0xff;
export function trieSearch(flatRanges) {
	const map = new Map();
	function addRange(key, range) {
		const ranges = map.get(key) ?? map.set(key, []).get(key);
		ranges.push(range);
	}

	const min = Math.min(...flatRanges);
	const max = Math.max(...flatRanges);

	for (let i = 0; i < flatRanges.length; i += 2) {
		const range = [flatRanges[i], flatRanges[i + 1]];
		const keyStart = key(range[0]);
		const keyEnd = key(range[1]);
		for (let k = keyStart; k <= keyEnd; k++) {
			addRange(k, range);
		}
	}

	return (codePoint) => {
		if (codePoint < min || codePoint > max) {
			return false;
		}

		return (
			map
				.get(key(codePoint))
				?.find(([low, high]) => codePoint >= low && codePoint <= high) !==
			undefined
		);
	};
}

export function setSearch(flatRanges) {
	const set = new Set();
	for (let i = 0; i < flatRanges.length; i += 2) {
		const from = flatRanges[i];
		const to = flatRanges[i + 1];
		for (let j = from; j <= to; j++) {
			set.add(j);
		}
	}

	return (codePoint) => set.has(codePoint);
}

export function bitflagSearch(flatRanges) {
	const max_range = flatRanges.at(-1);
	const flags = new Uint32Array((max_range >>> 5) + 1);

	for (let i = 0, length = flatRanges.length; i < length; i += 2) {
		const from = flatRanges[i];
		const to = flatRanges[i + 1];
		for (let j = from; j <= to; j++) {
			flags[j >>> 5] |= 1 << (j & 31);
		}
	}

	return (codePoint) =>
		((flags[codePoint >>> 5] >>> (codePoint & 31)) & 1) === 1;
}

const WORD = 0xff_ff_ff_ff;
export function offsetBitflagSearch(flatRanges) {
	const [min, max] = [flatRanges.at(0), flatRanges.at(-1)];
	const [firstWord, lastWord] = [min >>> 5, (max >>> 5) + 1];
	const flags = new Uint32Array(lastWord - firstWord);
	const offset = firstWord << 5;

	for (let i = 0, length = flatRanges.length; i < length; i += 2) {
		const from = flatRanges[i] - offset;
		const to = flatRanges[i + 1] - offset;
		const fromWord = from >>> 5;
		const toWord = to >>> 5;

		if (fromWord === toWord) {
			flags[fromWord] |= (WORD << (from & 31)) & (WORD >>> (31 - (to & 31)));
		} else {
			flags[fromWord] |= WORD << (from & 31);
			flags.fill(WORD, fromWord + 1, toWord);
			flags[toWord] |= WORD >>> (31 - (to & 31));
		}
	}

	return (codePoint) => {
		if (codePoint < min || codePoint > max) {
			return false;
		}

		return ((flags[(codePoint - offset) >>> 5] >>> (codePoint & 31)) & 1) !== 0;
	};
}

import test from "ava";
import {
	bitflagSearch,
	biSearch,
	offsetBitflagSearch,
	setSearch,
	trieSearch,
} from "./lookup.js";
import {
	ambiguousRanges,
	fullwidthRanges,
	halfwidthRanges,
	narrowRanges,
	wideRanges,
} from "./lookup-data.js";

const ranges = Object.entries({
	ambiguousRanges,
	fullwidthRanges,
	halfwidthRanges,
	narrowRanges,
	wideRanges,
});
const lookups = Object.entries({
	bitflagSearch,
	offsetBitflagSearch,
	setSearch,
	trieSearch,
});

const max_range = Math.max(
	ambiguousRanges.at(-1),
	fullwidthRanges.at(-1),
	halfwidthRanges.at(-1),
	narrowRanges.at(-1),
	wideRanges.at(-1),
);
for (let [rangeName, range] of ranges) {
	const binarySearch = biSearch(range);
	for (let [lookupName, lookup] of lookups) {
		test(`${lookupName}(${rangeName}) matches binarySearch(${rangeName})`, (t) => {
			const lookupDiff = [];
			const search = lookup(range);

			for (let codePoint = 0; codePoint <= max_range + 1; codePoint++) {
				if (search(codePoint) !== binarySearch(codePoint)) {
					lookupDiff.push(
						`Expected ${lookupName}(${codePoint}) === ${binarySearch(codePoint)}`,
					);
				}
			}

			t.deepEqual(lookupDiff, [], "Expect no difference in lookup values");
		});
	}
}

import { run, bench, summary } from "mitata";
import {
	bitflagSearch,
	binarySearch,
	offsetBitflagSearch,
	setSearch,
	trieSearch,
} from "./lookup.js";
import { ambiguousRanges } from "./lookup-data.js";

const searches = Object.entries({
	binarySearch,
	bitflagSearch,
	offsetBitflagSearch,
	setSearch,
	trieSearch,
});

const max_range = ambiguousRanges.at(-1);

summary(() => {
	for (const [searchName, searchFunction] of searches) {
		bench(`${searchName}`, function* () {
			const lookup = searchFunction(ambiguousRanges);

			yield () => {
				let checksum = 0;
				for (let cp = 0; cp <= max_range; cp++) {
					checksum ^= lookup(cp);
				}
				return checksum;
			};
		});
	}
});

await run();

import { run, bench, summary } from "mitata";
import { eastAsianWidth } from "./index.js";
import { load, binarySearch, bitflagSearch } from "./lookup.js";

const corpora = Object.entries({
	en: "Software engineering is the systematic application of engineering approaches to the development of software. It encompasses a wide range of disciplines, from requirement analysis and system design to implementation, testing, and maintenance. High-performance computing requires careful optimization of data structures, algorithms, and memory management to ensure efficient execution at scale. The quick brown fox jumps over the lazy dog repeatedly while developers analyze the underlying bytecode.",
	zh: "软件工程是将工程学的方法系统地应用于软件开发的过程。它涵盖了从需求分析、系统设计到代码实现、测试和维护的广泛领域。在高性能计算环境中，必须仔细优化数据结构、算法和内存管理，以确保在大规模运行时的执行效率。东亚字符的宽度处理在终端模拟器、文本编辑器和命令行界面中尤为关键，因为全角和半角字符在屏幕上占据的空间不同。你好，这是一个包含多种字符的测试文本。",
	es: "La ingeniería de software es la aplicación sistemática de enfoques de ingeniería para el desarrollo de software. Abarca una amplia gama de disciplinas, desde el análisis de requisitos y el diseño del sistema hasta la implementación, las pruebas y el mantenimiento. La informática de alto rendimiento requiere una cuidadosa optimización de las estructuras de datos, los algoritmos y la gestión de la memoria para garantizar una ejecución eficiente a gran escala. El pingüino vivió en el ártico; mañana será un gran día para programar.",
	emoji:
		"🚀🌟👩‍💻🏳️‍🌈🔥✨🎉🎈🍕🍔🍣🚗✈️🌍🌙☀️😎🤔😂😭❤️👍🙌🙏💪🏃‍♀️🚶‍♂️🐶🐱🐼🐒🌸🌺🌲🌵⚡️💧🌪️📱💻⌚️🕹️💡📚✂️📍👨‍👩‍👧‍👦🤦🏽‍♀️🇺🇳🥷🏿🧟‍♂️🧙‍♀️🧚‍♂️🧜‍♀️🧛‍♂️",
	mixed:
		"Agent v2.0 🚀: 欢迎使用 (Welcome to) the terminal framework. Loading configuration... [100%] ✅. 用户配置已加载。Warning: 内存使用率 (Memory usage) exceeds 80% ⚠️. Proceeding with optimization ártico.",
});
const algorithms = Object.entries({ binarySearch, bitflagSearch });

for (const [language, initialText] of corpora) {
	summary(() => {
		for (const [lookupName, lookup] of algorithms) {
			bench(`${lookupName}::${language}`, function* (state) {
				const size = state.get("size");
				const codePoints = [...text.repeat(size)].map((c) => c.codePointAt(0));
				load(lookup);

				yield () => {
					return codePoints.reduce((sum, cp) => sum + eastAsianWidth(cp));
				};
			}).range("size", 256, 1024);
		}
	});
}

await run();