#scope_module

EvenOdd :: 1;
OddEven :: -1;
EvenOddSkip :: 1<<30;
OddEvenSkip :: EvenOddSkip + 1;

CaseFold :: struct {
	lo: Rune;
	hi: Rune;
	delta: s32;
}

// Searches the case folding tables and returns the CaseFold* that contains r.
// If there isn't one, returns the CaseFold* with smallest f.lo bigger than r.
// If there isn't one, returns null.
lookup_casefold :: (folds: [] CaseFold, r: Rune) -> *CaseFold {
	// Binary search for entry containing r.
	f := folds;
	while f.count {
		m := f.count / 2;
		if f[m].lo <= r && r <= f[m].hi {
			return *f[m];
		}
		if r < f[m].lo {
			f.count = m;
		} else {
			f.data += m + 1;
			f.count -= m + 1;
		}
	}

	// There is no entry that contains r, but f points
	// where it would have been.  Unless f points at
	// the end of the array, it points at the next entry
	// after r.
	if f.count	 return *f[0];

	// No entry contains r; no entry contains runes > r.
	return null;
}

// Returns the result of applying the fold f to the rune r.
apply_fold :: (f: *CaseFold, r: Rune) -> Rune {
	if f.delta ==  {
		case;
			return r + f.delta;

		case EvenOddSkip;  // even <-> odd but only applies to every other
			if (r - f.lo) % 2	return r;
			#through;
		case EvenOdd;  // even <-> odd
			if r % 2 == 0		return r + 1;

			return r - 1;

		case OddEvenSkip;  // odd <-> even but only applies to every other
			if (r - f.lo) % 2	return r;
			#through;
		case OddEven;  // odd <-> even
			if r%2 == 1			return r + 1;

			return r - 1;
	}
}

// Returns the next Rune in r's folding cycle (see unicode_casefold.h).
// Examples:
//   CycleFoldRune('A') = 'a'
//   CycleFoldRune('a') = 'A'
//
//   CycleFoldRune('K') = 'k'
//   CycleFoldRune('k') = 0x212A (Kelvin)
//   CycleFoldRune(0x212A) = 'K'
//
//   CycleFoldRune('?') = '?'
cycle_fold_rune :: (r: Rune) -> Rune {
	f:= lookup_casefold(unicode_casefold, r);
	if f == null || r < f.lo		return r;

	return apply_fold(f, r);
}

unicode_casefold :: CaseFold.[
	.{65, 90, 32 },
	.{97, 106, -32 },
	.{107, 107, 8383 },
	.{108, 114, -32 },
	.{115, 115, 268 },
	.{116, 122, -32 },
	.{181, 181, 743 },
	.{192, 214, 32 },
	.{216, 222, 32 },
	.{223, 223, 7615 },
	.{224, 228, -32 },
	.{229, 229, 8262 },
	.{230, 246, -32 },
	.{248, 254, -32 },
	.{255, 255, 121 },
	.{256, 303, EvenOdd },
	.{306, 311, EvenOdd },
	.{313, 328, OddEven },
	.{330, 375, EvenOdd },
	.{376, 376, -121 },
	.{377, 382, OddEven },
	.{383, 383, -300 },
	.{384, 384, 195 },
	.{385, 385, 210 },
	.{386, 389, EvenOdd },
	.{390, 390, 206 },
	.{391, 392, OddEven },
	.{393, 394, 205 },
	.{395, 396, OddEven },
	.{398, 398, 79 },
	.{399, 399, 202 },
	.{400, 400, 203 },
	.{401, 402, OddEven },
	.{403, 403, 205 },
	.{404, 404, 207 },
	.{405, 405, 97 },
	.{406, 406, 211 },
	.{407, 407, 209 },
	.{408, 409, EvenOdd },
	.{410, 410, 163 },
	.{412, 412, 211 },
	.{413, 413, 213 },
	.{414, 414, 130 },
	.{415, 415, 214 },
	.{416, 421, EvenOdd },
	.{422, 422, 218 },
	.{423, 424, OddEven },
	.{425, 425, 218 },
	.{428, 429, EvenOdd },
	.{430, 430, 218 },
	.{431, 432, OddEven },
	.{433, 434, 217 },
	.{435, 438, OddEven },
	.{439, 439, 219 },
	.{440, 441, EvenOdd },
	.{444, 445, EvenOdd },
	.{447, 447, 56 },
	.{452, 452, EvenOdd },
	.{453, 453, OddEven },
	.{454, 454, -2 },
	.{455, 455, OddEven },
	.{456, 456, EvenOdd },
	.{457, 457, -2 },
	.{458, 458, EvenOdd },
	.{459, 459, OddEven },
	.{460, 460, -2 },
	.{461, 476, OddEven },
	.{477, 477, -79 },
	.{478, 495, EvenOdd },
	.{497, 497, OddEven },
	.{498, 498, EvenOdd },
	.{499, 499, -2 },
	.{500, 501, EvenOdd },
	.{502, 502, -97 },
	.{503, 503, -56 },
	.{504, 543, EvenOdd },
	.{544, 544, -130 },
	.{546, 563, EvenOdd },
	.{570, 570, 10795 },
	.{571, 572, OddEven },
	.{573, 573, -163 },
	.{574, 574, 10792 },
	.{575, 576, 10815 },
	.{577, 578, OddEven },
	.{579, 579, -195 },
	.{580, 580, 69 },
	.{581, 581, 71 },
	.{582, 591, EvenOdd },
	.{592, 592, 10783 },
	.{593, 593, 10780 },
	.{594, 594, 10782 },
	.{595, 595, -210 },
	.{596, 596, -206 },
	.{598, 599, -205 },
	.{601, 601, -202 },
	.{603, 603, -203 },
	.{604, 604, 42319 },
	.{608, 608, -205 },
	.{609, 609, 42315 },
	.{611, 611, -207 },
	.{613, 613, 42280 },
	.{614, 614, 42308 },
	.{616, 616, -209 },
	.{617, 617, -211 },
	.{618, 618, 42308 },
	.{619, 619, 10743 },
	.{620, 620, 42305 },
	.{623, 623, -211 },
	.{625, 625, 10749 },
	.{626, 626, -213 },
	.{629, 629, -214 },
	.{637, 637, 10727 },
	.{640, 640, -218 },
	.{642, 642, 42307 },
	.{643, 643, -218 },
	.{647, 647, 42282 },
	.{648, 648, -218 },
	.{649, 649, -69 },
	.{650, 651, -217 },
	.{652, 652, -71 },
	.{658, 658, -219 },
	.{669, 669, 42261 },
	.{670, 670, 42258 },
	.{837, 837, 84 },
	.{880, 883, EvenOdd },
	.{886, 887, EvenOdd },
	.{891, 893, 130 },
	.{895, 895, 116 },
	.{902, 902, 38 },
	.{904, 906, 37 },
	.{908, 908, 64 },
	.{910, 911, 63 },
	.{913, 929, 32 },
	.{931, 931, 31 },
	.{932, 939, 32 },
	.{940, 940, -38 },
	.{941, 943, -37 },
	.{945, 945, -32 },
	.{946, 946, 30 },
	.{947, 948, -32 },
	.{949, 949, 64 },
	.{950, 951, -32 },
	.{952, 952, 25 },
	.{953, 953, 7173 },
	.{954, 954, 54 },
	.{955, 955, -32 },
	.{956, 956, -775 },
	.{957, 959, -32 },
	.{960, 960, 22 },
	.{961, 961, 48 },
	.{962, 962, EvenOdd },
	.{963, 965, -32 },
	.{966, 966, 15 },
	.{967, 968, -32 },
	.{969, 969, 7517 },
	.{970, 971, -32 },
	.{972, 972, -64 },
	.{973, 974, -63 },
	.{975, 975, 8 },
	.{976, 976, -62 },
	.{977, 977, 35 },
	.{981, 981, -47 },
	.{982, 982, -54 },
	.{983, 983, -8 },
	.{984, 1007, EvenOdd },
	.{1008, 1008, -86 },
	.{1009, 1009, -80 },
	.{1010, 1010, 7 },
	.{1011, 1011, -116 },
	.{1012, 1012, -92 },
	.{1013, 1013, -96 },
	.{1015, 1016, OddEven },
	.{1017, 1017, -7 },
	.{1018, 1019, EvenOdd },
	.{1021, 1023, -130 },
	.{1024, 1039, 80 },
	.{1040, 1071, 32 },
	.{1072, 1073, -32 },
	.{1074, 1074, 6222 },
	.{1075, 1075, -32 },
	.{1076, 1076, 6221 },
	.{1077, 1085, -32 },
	.{1086, 1086, 6212 },
	.{1087, 1088, -32 },
	.{1089, 1090, 6210 },
	.{1091, 1097, -32 },
	.{1098, 1098, 6204 },
	.{1099, 1103, -32 },
	.{1104, 1119, -80 },
	.{1120, 1122, EvenOdd },
	.{1123, 1123, 6180 },
	.{1124, 1153, EvenOdd },
	.{1162, 1215, EvenOdd },
	.{1216, 1216, 15 },
	.{1217, 1230, OddEven },
	.{1231, 1231, -15 },
	.{1232, 1327, EvenOdd },
	.{1329, 1366, 48 },
	.{1377, 1414, -48 },
	.{4256, 4293, 7264 },
	.{4295, 4295, 7264 },
	.{4301, 4301, 7264 },
	.{4304, 4346, 3008 },
	.{4349, 4351, 3008 },
	.{5024, 5103, 38864 },
	.{5104, 5109, 8 },
	.{5112, 5117, -8 },
	.{7296, 7296, -6254 },
	.{7297, 7297, -6253 },
	.{7298, 7298, -6244 },
	.{7299, 7299, -6242 },
	.{7300, 7300, EvenOdd },
	.{7301, 7301, -6243 },
	.{7302, 7302, -6236 },
	.{7303, 7303, -6181 },
	.{7304, 7304, 35266 },
	.{7312, 7354, -3008 },
	.{7357, 7359, -3008 },
	.{7545, 7545, 35332 },
	.{7549, 7549, 3814 },
	.{7566, 7566, 35384 },
	.{7680, 7776, EvenOdd },
	.{7777, 7777, 58 },
	.{7778, 7829, EvenOdd },
	.{7835, 7835, -59 },
	.{7838, 7838, -7615 },
	.{7840, 7935, EvenOdd },
	.{7936, 7943, 8 },
	.{7944, 7951, -8 },
	.{7952, 7957, 8 },
	.{7960, 7965, -8 },
	.{7968, 7975, 8 },
	.{7976, 7983, -8 },
	.{7984, 7991, 8 },
	.{7992, 7999, -8 },
	.{8000, 8005, 8 },
	.{8008, 8013, -8 },
	.{8017, 8017, 8 },
	.{8019, 8019, 8 },
	.{8021, 8021, 8 },
	.{8023, 8023, 8 },
	.{8025, 8025, -8 },
	.{8027, 8027, -8 },
	.{8029, 8029, -8 },
	.{8031, 8031, -8 },
	.{8032, 8039, 8 },
	.{8040, 8047, -8 },
	.{8048, 8049, 74 },
	.{8050, 8053, 86 },
	.{8054, 8055, 100 },
	.{8056, 8057, 128 },
	.{8058, 8059, 112 },
	.{8060, 8061, 126 },
	.{8064, 8071, 8 },
	.{8072, 8079, -8 },
	.{8080, 8087, 8 },
	.{8088, 8095, -8 },
	.{8096, 8103, 8 },
	.{8104, 8111, -8 },
	.{8112, 8113, 8 },
	.{8115, 8115, 9 },
	.{8120, 8121, -8 },
	.{8122, 8123, -74 },
	.{8124, 8124, -9 },
	.{8126, 8126, -7289 },
	.{8131, 8131, 9 },
	.{8136, 8139, -86 },
	.{8140, 8140, -9 },
	.{8144, 8145, 8 },
	.{8152, 8153, -8 },
	.{8154, 8155, -100 },
	.{8160, 8161, 8 },
	.{8165, 8165, 7 },
	.{8168, 8169, -8 },
	.{8170, 8171, -112 },
	.{8172, 8172, -7 },
	.{8179, 8179, 9 },
	.{8184, 8185, -128 },
	.{8186, 8187, -126 },
	.{8188, 8188, -9 },
	.{8486, 8486, -7549 },
	.{8490, 8490, -8415 },
	.{8491, 8491, -8294 },
	.{8498, 8498, 28 },
	.{8526, 8526, -28 },
	.{8544, 8559, 16 },
	.{8560, 8575, -16 },
	.{8579, 8580, OddEven },
	.{9398, 9423, 26 },
	.{9424, 9449, -26 },
	.{11264, 11310, 48 },
	.{11312, 11358, -48 },
	.{11360, 11361, EvenOdd },
	.{11362, 11362, -10743 },
	.{11363, 11363, -3814 },
	.{11364, 11364, -10727 },
	.{11365, 11365, -10795 },
	.{11366, 11366, -10792 },
	.{11367, 11372, OddEven },
	.{11373, 11373, -10780 },
	.{11374, 11374, -10749 },
	.{11375, 11375, -10783 },
	.{11376, 11376, -10782 },
	.{11378, 11379, EvenOdd },
	.{11381, 11382, OddEven },
	.{11390, 11391, -10815 },
	.{11392, 11491, EvenOdd },
	.{11499, 11502, OddEven },
	.{11506, 11507, EvenOdd },
	.{11520, 11557, -7264 },
	.{11559, 11559, -7264 },
	.{11565, 11565, -7264 },
	.{42560, 42570, EvenOdd },
	.{42571, 42571, -35267 },
	.{42572, 42605, EvenOdd },
	.{42624, 42651, EvenOdd },
	.{42786, 42799, EvenOdd },
	.{42802, 42863, EvenOdd },
	.{42873, 42876, OddEven },
	.{42877, 42877, -35332 },
	.{42878, 42887, EvenOdd },
	.{42891, 42892, OddEven },
	.{42893, 42893, -42280 },
	.{42896, 42899, EvenOdd },
	.{42900, 42900, 48 },
	.{42902, 42921, EvenOdd },
	.{42922, 42922, -42308 },
	.{42923, 42923, -42319 },
	.{42924, 42924, -42315 },
	.{42925, 42925, -42305 },
	.{42926, 42926, -42308 },
	.{42928, 42928, -42258 },
	.{42929, 42929, -42282 },
	.{42930, 42930, -42261 },
	.{42931, 42931, 928 },
	.{42932, 42943, EvenOdd },
	.{42946, 42947, EvenOdd },
	.{42948, 42948, -48 },
	.{42949, 42949, -42307 },
	.{42950, 42950, -35384 },
	.{42951, 42954, OddEven },
	.{42997, 42998, OddEven },
	.{43859, 43859, -928 },
	.{43888, 43967, -38864 },
	.{65313, 65338, 32 },
	.{65345, 65370, -32 },
	.{66560, 66599, 40 },
	.{66600, 66639, -40 },
	.{66736, 66771, 40 },
	.{66776, 66811, -40 },
	.{68736, 68786, 64 },
	.{68800, 68850, -64 },
	.{71840, 71871, 32 },
	.{71872, 71903, -32 },
	.{93760, 93791, 32 },
	.{93792, 93823, -32 },
	.{125184, 125217, 34 },
	.{125218, 125251, -34 },
];

// 1384 groups, 1414 pairs, 200 ranges
unicode_tolower :: CaseFold.[
	.{65, 90, 32 },
	.{181, 181, 775 },
	.{192, 214, 32 },
	.{216, 222, 32 },
	.{256, 302, EvenOddSkip },
	.{306, 310, EvenOddSkip },
	.{313, 327, OddEvenSkip },
	.{330, 374, EvenOddSkip },
	.{376, 376, -121 },
	.{377, 381, OddEvenSkip },
	.{383, 383, -268 },
	.{385, 385, 210 },
	.{386, 388, EvenOddSkip },
	.{390, 390, 206 },
	.{391, 391, OddEven },
	.{393, 394, 205 },
	.{395, 395, OddEven },
	.{398, 398, 79 },
	.{399, 399, 202 },
	.{400, 400, 203 },
	.{401, 401, OddEven },
	.{403, 403, 205 },
	.{404, 404, 207 },
	.{406, 406, 211 },
	.{407, 407, 209 },
	.{408, 408, EvenOdd },
	.{412, 412, 211 },
	.{413, 413, 213 },
	.{415, 415, 214 },
	.{416, 420, EvenOddSkip },
	.{422, 422, 218 },
	.{423, 423, OddEven },
	.{425, 425, 218 },
	.{428, 428, EvenOdd },
	.{430, 430, 218 },
	.{431, 431, OddEven },
	.{433, 434, 217 },
	.{435, 437, OddEvenSkip },
	.{439, 439, 219 },
	.{440, 440, EvenOdd },
	.{444, 444, EvenOdd },
	.{452, 452, 2 },
	.{453, 453, OddEven },
	.{455, 455, 2 },
	.{456, 456, EvenOdd },
	.{458, 458, 2 },
	.{459, 475, OddEvenSkip },
	.{478, 494, EvenOddSkip },
	.{497, 497, 2 },
	.{498, 500, EvenOddSkip },
	.{502, 502, -97 },
	.{503, 503, -56 },
	.{504, 542, EvenOddSkip },
	.{544, 544, -130 },
	.{546, 562, EvenOddSkip },
	.{570, 570, 10795 },
	.{571, 571, OddEven },
	.{573, 573, -163 },
	.{574, 574, 10792 },
	.{577, 577, OddEven },
	.{579, 579, -195 },
	.{580, 580, 69 },
	.{581, 581, 71 },
	.{582, 590, EvenOddSkip },
	.{837, 837, 116 },
	.{880, 882, EvenOddSkip },
	.{886, 886, EvenOdd },
	.{895, 895, 116 },
	.{902, 902, 38 },
	.{904, 906, 37 },
	.{908, 908, 64 },
	.{910, 911, 63 },
	.{913, 929, 32 },
	.{931, 939, 32 },
	.{962, 962, EvenOdd },
	.{975, 975, 8 },
	.{976, 976, -30 },
	.{977, 977, -25 },
	.{981, 981, -15 },
	.{982, 982, -22 },
	.{984, 1006, EvenOddSkip },
	.{1008, 1008, -54 },
	.{1009, 1009, -48 },
	.{1012, 1012, -60 },
	.{1013, 1013, -64 },
	.{1015, 1015, OddEven },
	.{1017, 1017, -7 },
	.{1018, 1018, EvenOdd },
	.{1021, 1023, -130 },
	.{1024, 1039, 80 },
	.{1040, 1071, 32 },
	.{1120, 1152, EvenOddSkip },
	.{1162, 1214, EvenOddSkip },
	.{1216, 1216, 15 },
	.{1217, 1229, OddEvenSkip },
	.{1232, 1326, EvenOddSkip },
	.{1329, 1366, 48 },
	.{4256, 4293, 7264 },
	.{4295, 4295, 7264 },
	.{4301, 4301, 7264 },
	.{5112, 5117, -8 },
	.{7296, 7296, -6222 },
	.{7297, 7297, -6221 },
	.{7298, 7298, -6212 },
	.{7299, 7300, -6210 },
	.{7301, 7301, -6211 },
	.{7302, 7302, -6204 },
	.{7303, 7303, -6180 },
	.{7304, 7304, 35267 },
	.{7312, 7354, -3008 },
	.{7357, 7359, -3008 },
	.{7680, 7828, EvenOddSkip },
	.{7835, 7835, -58 },
	.{7838, 7838, -7615 },
	.{7840, 7934, EvenOddSkip },
	.{7944, 7951, -8 },
	.{7960, 7965, -8 },
	.{7976, 7983, -8 },
	.{7992, 7999, -8 },
	.{8008, 8013, -8 },
	.{8025, 8025, -8 },
	.{8027, 8027, -8 },
	.{8029, 8029, -8 },
	.{8031, 8031, -8 },
	.{8040, 8047, -8 },
	.{8072, 8079, -8 },
	.{8088, 8095, -8 },
	.{8104, 8111, -8 },
	.{8120, 8121, -8 },
	.{8122, 8123, -74 },
	.{8124, 8124, -9 },
	.{8126, 8126, -7173 },
	.{8136, 8139, -86 },
	.{8140, 8140, -9 },
	.{8152, 8153, -8 },
	.{8154, 8155, -100 },
	.{8168, 8169, -8 },
	.{8170, 8171, -112 },
	.{8172, 8172, -7 },
	.{8184, 8185, -128 },
	.{8186, 8187, -126 },
	.{8188, 8188, -9 },
	.{8486, 8486, -7517 },
	.{8490, 8490, -8383 },
	.{8491, 8491, -8262 },
	.{8498, 8498, 28 },
	.{8544, 8559, 16 },
	.{8579, 8579, OddEven },
	.{9398, 9423, 26 },
	.{11264, 11310, 48 },
	.{11360, 11360, EvenOdd },
	.{11362, 11362, -10743 },
	.{11363, 11363, -3814 },
	.{11364, 11364, -10727 },
	.{11367, 11371, OddEvenSkip },
	.{11373, 11373, -10780 },
	.{11374, 11374, -10749 },
	.{11375, 11375, -10783 },
	.{11376, 11376, -10782 },
	.{11378, 11378, EvenOdd },
	.{11381, 11381, OddEven },
	.{11390, 11391, -10815 },
	.{11392, 11490, EvenOddSkip },
	.{11499, 11501, OddEvenSkip },
	.{11506, 11506, EvenOdd },
	.{42560, 42604, EvenOddSkip },
	.{42624, 42650, EvenOddSkip },
	.{42786, 42798, EvenOddSkip },
	.{42802, 42862, EvenOddSkip },
	.{42873, 42875, OddEvenSkip },
	.{42877, 42877, -35332 },
	.{42878, 42886, EvenOddSkip },
	.{42891, 42891, OddEven },
	.{42893, 42893, -42280 },
	.{42896, 42898, EvenOddSkip },
	.{42902, 42920, EvenOddSkip },
	.{42922, 42922, -42308 },
	.{42923, 42923, -42319 },
	.{42924, 42924, -42315 },
	.{42925, 42925, -42305 },
	.{42926, 42926, -42308 },
	.{42928, 42928, -42258 },
	.{42929, 42929, -42282 },
	.{42930, 42930, -42261 },
	.{42931, 42931, 928 },
	.{42932, 42942, EvenOddSkip },
	.{42946, 42946, EvenOdd },
	.{42948, 42948, -48 },
	.{42949, 42949, -42307 },
	.{42950, 42950, -35384 },
	.{42951, 42953, OddEvenSkip },
	.{42997, 42997, OddEven },
	.{43888, 43967, -38864 },
	.{65313, 65338, 32 },
	.{66560, 66599, 40 },
	.{66736, 66771, 40 },
	.{68736, 68786, 64 },
	.{71840, 71871, 32 },
	.{93760, 93791, 32 },
	.{125184, 125217, 34 },
];