path: root/mcs/class/corlib/Mono.Globalization.Unicode/Collation-notes.txt

* String collation Notes

** Summary

	We are going to implement Windows-like collation, apart from ICU (that
	implements UCA, Unicode Collation Algorithm).


** Tasks

	* create collation element table(s)
		- infer how Windows collation element table is composed
		  : mostly analyzed.
		- write table generator source(s)
		  : mostly implemented. Need to fix nearly 400 mappings.
		    They are mainly 1) IPA extensions (U+250-U+300),
		    2) Latin extensions (U+1E00-U+1F00), 3) Letterlike
		    symbols (U+2100-U+2140), 4) some Cyrillic letters
		    (U+460-U+500), and 5) some Hangul characters.
		- culture-specific sortkey data
		  : They are defined in mono-tailoring-source.txt.
		    All single sortkey remapping in all cultures are filled.
		    Contractions are not fully checked yet (should be filled
		    from UCA tailorings via create-tailorings.exe).


** How to implement CompareInfo members

	GetSortKey() : done
		Compute sort key for every character elements into byte[].
	Compare() : done
		Find first difference and compare it.
		"Larger/smaller" matters (beyond "different").
	IsPrefix()
		It calls CompareInternal() which also answers if the target
		is fully consumed, so it just returns true if it says that
		the target is fully consumed.
	IsSuffix()
		It tries CompareInternal() to compare source and target at
		the end, where source varies from minimum tail to the
		original args.
	IndexOf(), LastIndexOf()
		For character search, it finds the matching character element
		to the end (or start) of the string to find.
		For string search, it invokes one of private IndexOf() (or
		LastIndexOf()) overload passing the first character element
		of the target, and if found, tests if the sequence is a valid
		start point, using IsPrefix() (or IsSuffix()).

*** Optimizations

	For Compare() and IsPrefix(), it uses forward iteration, which moves
	forward and don't stop until either it finds next "primary" character
	or it reached the end of the string, checking with IsSafe(char).

	For IndexOf(char) and LastIndexOf(char), there is no special 
	optimization (since the codepoints usually do not match, while they
	often matches as a natural collation), but it omits extraneous sortkey
	value computation.

	IsSuffix() reuses Compare() and returns false if it does not consume
	the target string more than 3 times. 3 is kind of magic number that
	represents the longest expansion.

	IndexOf(string) is implemented as a combination of IndexOf(char) and
	IsPrefix().

	LastIndexOf(string) is implemented as a combination of
	LastIndexOf(char) and IsPrefix().

	Porting them to C code is an alternative possible approach, but from
	Compare() optimization experience, it is quick enough.

** How to support CompareOptions

	There are two kind of "ignorance" : strippers' ignorance and
	normalizers' ignorance.

	The strippers will "filter characters out" and there will be no
	corresponding character elements in SortKey binaries.

	Normalizers, on the other hand, will result in certain characters 
	that is still in effect between irrelevant character and itself.
	For example, with IgnoreKanaType Hiragana "A" and Katakana "A" are
	not distinguished, but Hiragana "A" and Hiragana "I" are.

	Actually, even without any IgnoreXXX flags (i.e. "None"), there are 
	many characters that are ignored ("completely ignorable").

	Except for LCID 101/1125(div), '\ufdf2' is completely ignorable.
	This rule even applies to CompareOptions.None.

*** Normalizers

	IgnoreCase
		Maybe culture-dependent TextInfo.ToLower() could be used.

		Unlike ICU (specialCaseToLower()), even with tr-TR(LCID 31)
		and IgnoreCase, I\u0307 is not regarded as equal to i.

	IgnoreKanaType
		ToKanaTypeInsensitive(). Note that this does not cover the
		whole "level 4" differences described later.

	IgnoreWidth
		ToWidthInsensitive(), which is likely to be culture
		independent. See also "Notes".

	IgnoreNonSpace (see also Strippers; this flag works in both sides)
		For some cultures this logic is still incomplete. All culture-
		dependent collators must handle valid "replacement" of "one or
		more characters" which might be related to specific
		CompareOptions.
		For example, there is a Japanese text sorting rule that
		however applies to InvariantCulture. Concretely to say,
		"\u3042\u30FC" is equivalent to "\u3042\u3042" only when
		IgnoreNonSpace is specified.

		I'll take those items from CLDR (those items which has
		<reset before="..." />), case by case though.

*** Strippers

	I already wrote all the required strippers which should be MS
	compatible (at least with .NET 1.1 invariant culture).

	IgnoreNonSpace
		IsIgnorableNonSpacing().
		Some Diacritic characters are covered by this flag.

		There are some culture *dependent* characters:
			LCID 90/1114(syr) : 64b, 652, 670

	IgnoreSymbols
		IsIgnorableSymbol().
		UnicodeCategory does not work here.

		There are some culture *dependent* characters:
			LCID 17/1041(ja) : 2015
			LCID 90/1114(syr) : 64b, 652

*** StringSort

	See "sort order categories" section.

** ICU and UCA

	First to note: we won't use collation element table from unicode.org.

	There are many differences between ICU/UCA and Windows despite they
	look so similar; having collation keys in different levels, culture
	dependent composition, etc. In the history, Windows collation is 
	designed before UCA was specified, so basically Windows is obsolete
	in this area. 
	
	- Logic: Unlike UCA it has no concept of "blocked" combining marks,
	  and combining marks are never considered as an independent character
	  (thus combining in Windows is buggy).
	- Data: Windows is based on old Unicode standard (even older than 1.1).
	  It ignores minor cultures. Character property values differ as well
	  as those from the default Unicode collation element table (DUCET).
	  In a few cultures Windows collation is close to the native language
	  (e.g. Tamil, while it does not conform to TAM).

	IgnoreWidth/IgnoreSymbols is processed after Kana voice mark
	decomposition (something like NFD, but not equivalent. Example: \u304C
	is completely equivalent to \u304B\u309B, which is not part of NFKD).
	<del>This means, if there is a combined Kana characters, it will be
	first decomposed and then compared.<del> It scarcely matters since
	there are special weight data for Japanese.

*** Microsoft design problem

	Microsoft implementation seems to have a serious problem that many,
	many characters that are used in for each specific culture, such as
	Myanmar, Mongolian, Cherokee, Etiopic, Tagalog, Khmer, are regarded as
	"completely ignorable".

	I tagged many LAMESPEC items in the implementation (both in collator
	and table generator).


** MS collation design inference

*** Levels

	Each character has several "weights". It is a common concept between
	Windows and UCA.

	There are 5 levels:

	- level 1: primary difference
	  The first byte of level 1 means the category of the character.
	- level 2: diacritic difference, including Japanese voice mark countup
	- level 3: case/width sensitivity, and Hangul properties
	- level 4: kana weight (all of them have primary category 22, at least
	  in InvariantCulture)
	- level 5: shift weight (apostrophe, hyphens etc.)

	Note that these levels does not digitally match IgnoreXXX flags. Thus
	it is not OK that we omit some levels of sortkey values in reflection
	to CompareOptions.

	String comparison is done from level 1 to 5. The comparison won't
	stop until either it found the primary difference, or it reached to
	the end (thus upper level differences are returned).

	For example, "e" is smaller than "E", but "eB" is bigger than "EA".
	If the collator just returned case difference at first 'e' and 'E',
	"eB" is still smaller than "EA".

**** level 5: shift weight by StringSort

	There are some characters that are treated specially. Namely they are
	apostrophe and hyphens. The sortkeys for them is put after level 4
	(thus here I write them as "level 5"). It has different sort key
	format. See immediate below. There is no level 5 characters when 
	StringSort is specified.

*** sort key format

	00 means the end of sort key.
	01 means the end of the level.
	02-FF means the value.
	Actually '2' could be cut when all the following values are
	also '2' (i.e. the sort key binary won't contain extraneous '2').

	Every level has different key layout.

**** level 2

	It looks like all level 2 keys are just accumulated, however without
	considering overflow. It sometimes makes sense (e.g. diaeresis and
	acute) but it causes many conflicts (e.g. "A\u0308\u0301" and "\u1EA6"
	are incorrectly regarded as equal).

	Anyways since Japanese voice mark has level 2 value as 1 it just
	looked like the sum of voice marks.

**** level 3

	The actual value analysis is not complete in this document. See the
	actual generator code.

	The actual values are + 2 (e.g. for Hangul Normal Jamo, the value is 4)

	For Korean letters:
		- 2: Jongseong (11A8-11F9)
		- 4: Half width? (FFA0-FFDC) and Compatibility Jamo? (3165-318E)
		- 5: Compatibility Jamo (3130-3164)?
		     TODO: Learn about Korean characters.

	For numbers:
		- 4 circled inverse (2776-277F)
		- 8 circled sans serif (2780-2789)
		- C circled inverse && sans serif (278A-2793)
		- 47 roman (2160-2182)

	For Arabic letters:
		- 2 Isolated form in presentation form B in FE80-FE8D
		- 4 Alef/Bet/Gimel/Dalet (2135-2138)
		- 8 Final form in presentation form B in FE82-FEF2
		- 18 Medial form in presentation form B in FE8C-FEF4
		     Grep "ISOLATED", "FINAL" or "MEDIAL" on UnicodeData.txt
		     (and filter by codepoints).
		     or alternatively, see DerivedDecompositionType.txt.
		- 22 6A9 (TODO: what is it?)
		- 28 6AA (TODO: what is it?)

	For other letters:
		- 1 Fullwidth. UnicodeData.txt has <full>.
		- 2 Subscript. UnicodeData.txt has <sub>.
		- 8 Small capital, 03C2 (TODO: why?),
		    2104, 212B(flag=1A) (TODO: why?)
		    grep "SMALL CAPITAL" against UnicodeData.txt.
		- C only FE42. TODO: what is this?
		- E Superscripts. UnicodeData.txt has <super>.
		- 10 Uppercase.
		     DerivedCoreProperties.txt has Uppercase property.

	Note that simple 02 (value is 00) could be omitted.

	Summary: at least 7 bits are required as to represent a table -
	smallCapital, uppercase, normalization forms (2 bits:full/sub/super),
	arabic forms (2 bits:isolated/medial/final)

**** level 4

	Those sortkey data is collected only for Japanese (category 22)
	characters.

	There are 3 sections each of them ends with FF. Each of them
	represents the values for character by character:
	- small letter type (kogaki moji); C4 (small) or E4 (normal)
	- category middle section:
		two subsections separated by 0x02
		- char type;
		  3 (normal)
		  or 4 (voice mark - \u309D,\u309E,\u30FD,\u30FE, \uFF70)
		  or 5 (dash mark - \u30FC)
		- kana type; C4 (katakana) or E4 (hiragana)
	- width; 2 (normal) or C5 (full) or C4 (half)

	  LAMESPEC: those characters of value '4' of middle section differs
	  in level 2 wrt voice marks, but does not differetiate kana types
	  (bug). It is ignored when IgnoreNonSpace applies.

**** level 5

	UPDATED: I noticed offsetL does not exist, so removed it from here.

	[offsetM + 0x80]? [const 3 + (offsetS + 1) * 4] [category] [level1]

	where "offsetM" and "offsetS" represents the offset in the input
	string. "offsetM" is always larger than 0x80.
	LAMESPEC: This design results in a buggy overflow.

	<xmp>
	byte [] data = new CultureInfo ("").CompareInfo.GetSortKey (s).KeyData;
	int idx = 0;
	for (int i = 0; i < 4; i++, idx++)
		for (; data [idx] != 1; idx++)
		        ;
	for (; idx < data.Length; idx++)
		Console.Write ("{0:X02} ", data [idx]);
	Console.WriteLine ();
	</xmp>

	inputs (s) and results:

	80 07 06 82 80 2F 06 82 00 // '-' + new string ('A', 10) + '-'
	80 07 06 82 81 97 06 82 00 // (100)
	80 07 06 82 8F A7 06 82 00 // (1000)
	80 07 06 82 9C 47 06 82 00 // (10000)
	80 07 06 82 9A 87 06 82 00 // (100000)
	80 07 06 82 89 07 06 82 00 // (1000000)

	The actual offset is 63 * offsetM + offsetS

	(const '3' may actually vary but no idea.
	At least 00, 01 and 02 are not acceptable since they are reserved.
	02 is not reserved by definition above, but the key-size optimizer
	uses it as a special mark, as mentioned above.)

*** sort key table

	Here is the simple sortkey dumper:

	public static void Main (string [] args)
	{
		CultureInfo culture = args.Length > 0 ?
			new CultureInfo (args [0]) :
			CultureInfo.InvariantCulture;
		CompareInfo ci = culture.CompareInfo;
		for (int i = 0; i < char.MaxValue; i++) {
			string s = new string ((char) i, 1);
			if (ci.Compare (s, "") == 0)
				continue; // ignored
			byte [] data = ci.GetSortKey (s).KeyData;
			foreach (byte b in data) {
				Console.Write ("{0:X02}", b);
				Console.Write (' ');
			}
			Console.WriteLine (" : {0:X}, {1} {2}",
				i,
				Char.GetUnicodeCategory ((char) i),
				data [2] != 1 ? '!' : ' ');
		}
	}

*** multiple character mappings

	Some sequence of characters are considered as a "composite" that is
	to be composed either as another character or another sequence of 
	characters. Those "composite" might not have corresponding equivalent
	character in sortkey.
	Similarly, some single characters are expanded to a sequence of
	characters.

**** diacritic characters

	Except for those shift-weight characters, there are only
	diacritical (or other kinds of nonspacing) characters that don't
	have primary weights.

	Diacritics are not regarded as a base character when placed after 
	(maybe some kind of) letters.

	The behavior is diacritic character dependent. For example, Japanese
	combination of a Kana character and a voice mark is compulsory (the
	resulting sort key is regarded as identical to the corresponding
	single character. Try \u304B\u309B with \u304C. It is invariant).

	In French cultures, diacritic orderings are checked from right to left.

**** Composite character processing

	There are some sequences of characters that are treated as another
	character or another sequence of characters.

	By default, there is no composite form.
	http://www.microsoft.com/globaldev/dis_v1/disv1.asp?DID=dis33d&File=S24C2.asp
	(Note that composite is different from expansion.)

	Note that composite characters is likely to not have equivalent
	codepoint.

**** Expanded character processing

	Some characters are expanded to two or more characters:

	C6 (AE), E6 (ae), 1F1-1F3 (dz), 1C4-1C6 (Dz), FB00-FB06 (ff, fi),
	132-133 (IJ), 1C7-1C9 (LJ), 1CA-1CC (NJ), 152-153 (OE),
	DF (ss), FB06 (st), FB05 (\u017Ft), FE, DE, 5F0-5F2,
	1113-115F (hangul)
	(CJK extension is not really expanded)

	They don't match with any of Unicode normalization.

	Some alphabetic cultures have different mappings, but mostly small
	(at least da-DK, lt-LT, fr-FR, es-ES have tiny differences).

	Invariant culture also puts Czech unique character \u0161 between s
	and t, unlike described here:
	http://www.microsoft.com/globaldev/dis_v1/disv1.asp?DID=dis33d&File=S24C0.asp

*** default sort key table

**** StringSort

	When CompareOptions.StringSort is specified, then it modifies
	characters in category 2 from "1 1 1 1 80 07 06 xx" to
	"06 xx yy zz" and some characters become case sensitive.

	For details, "level 5" description above.

	To handle them simply, they are laid out as "category 0x01" (which
	never happens in the actual sortkeys) for those shift-weight ones
	in the table.

	There seems no further differences between StringSort and None.

**** level 2 details

	The value analysis is not complete in this document. See the
	actual generator code.

	Known value maps:
		-0A: Korean parenthesized numbers (3200-321C)
		-0C: Korean circled numbers (3260-327B)

		-03: Japanese voice mark

		<primary category 13 : Arabic>
		-08: 627-648 (basic Abjad letters)
		-09: madda (622)
		-05: waw with hamza (624)
		-07: yeh with hamza (626. ignore Presentation Form A area)
		-0A: alef with hamza above (623)
		-0A: alef with hamza below (625)

		<primary category 0E : diacritics>
		Characters in non "0E" category are out of scope.
		They can be grepped in UnicodeData.txt.
		-0E: acute
		-0F: grave
		-10: dot above
		-11: middle dot
		-12: circumflex
		-13: diaeresis
		-14: caron
		     Note that 1C4-1C6 are covered but they are also expanded.
		-15: breve (cyrillic are also covered? at least 4C1/4C2 are.)
		-16: dialytika and tonos (category 0F though)
		-17: macron
		-19: tilde
		-1A: ring above | 212B
		-1B: ogonek ("WITH OGONEK;")
		-1C: cedilla (WITH CEDILLA;")
		-1D: double acute | acute and dot above
		-1E: stroke, except for 0E[1F] and cp{19B, 1BE} |
		     circumflex and acute | 18B,18C,19A,289
		     (i.e. they not one-to-one mapping. Neither that every
		     "stroke" are mapped to 1E, nor not every 1E are mapped to
		     "stroke".)
		-1F: diaeresis and acute | with circumflex and grave | l slash
			beware "symbol slash"
		-20: diaeresis and grave | 19B,19F
		-21: breve and acute | D8,F8
		-22: caron and dot above | breve and grave
		-23: macron and acute
		-24: macron and grave
		-25: diaeresis and caron | dot above and macron | tilde and acute
		-26: ring above and acute
		-28: diaeresis and macron | cedilla and acute |
		     macron and diaeresis
		-29: circumflex and tilde
		-2A: tilde and diaeresis
		-2B: stroke and acute
		-2C: breve and tilde
		-2F: cedilla and breve
		-30: ogonek and macron
		-43: hook, except for cp{192,1B2,25A,25D,27B,28B,2B1,2B5} |
		     left hook | with hook above except for cp{1EF6,1EF7} |
		     27D,284
		-44: double grave | 1EF6,1EF7
		-46: inverted breve
		-48: preceded by apostrophe (actually only 149)
		-52: horn
		-55: line below | circumflex and hook above
		-57: palatal hook (actually only 1AB)
		-58: dot below except for cp{1EA0,1EA1}
		-59: "retroflex" (without "WITH") | diaeresis below | 1EA0,1EA1
		-5A: ring below | 1E76,1E77
		-60: circumflex below except for cp{1E76,1E77} | horn and acute
		-61: breve below | horn and grave
		-63: tilde below | 2125
		-68: D0,F0,182,183 | dot below and dot above | topbar
		-69: right half ring | horn and tilde
		-6A: circumflex and dot below
		-6D: breve and dot below
		-6E: dot below and macron
		-95: horn and hook above
		-AA: horn and dot

		(for 01-0D and 7B-8A, they are not related to diacritics.)

		<category BlahBlahNumbers from 0100 to 1000>
		-38: Arabic-Indic numbers (660-669)
		-39: extended Arabic-Indic numbers (6F0-6F9)
		-3A: Devanagari numbers (966-96F)
		-3B: Bengali numbers (9E6-9EF)
		-3C: Bengali currency enumerators (9F4-9F9)
		-3D: Gurmukhi numbers (A66-A6F)
		-3E: Gujarati numbesr (AE6-AEF)
		-3F: Oriya digit numbers (B66-B6F)
		-40: Tamil numbers (BE7-BF2)
		-41: Telugu numbers (C66-C6F)
		-42: Kannada numbers (CE6-CEF)
		-43: Malayam numbers (D66-D6F)
		-44: Thai numbers (E50-E59)
		-45: Lao numbers (ED0-ED9)
		<miscellaneous numbers>
		-47: Roman numbers (2160-2182)
		-4E: Hangchou numbers (3021-3029)

		-E0[64]: 2107 (Eurer)
		-E0[87]: some Tone letters (TONE TWO / TONE SIX)
		-EE: Circled letter-or-digits and katakanas
			CIRCLED {DIGIT|NUMBER|LATIN|KATAKANA}
			numbers (2460-2473,2776-2793,24EA)
			latin (24B6-24E9)
			katakana (32D0-32FE)
		-F3: Parenthesized enumerations
			numbers (2474-2487)
			latin (249C-24B5)
			PARENTHESIZED {DIGIT|NUMBER|LATIN}
		-F4: Numbers with dot (2488-249B)
			{DIGIT|NUMBER} * FULL STOP

		<miscellaneous>
		-258,25C-25E,285,286,29A,297 -> 0E[80-86,88]
		-27F,2B3-2B6 -> 0E 8A[80-84]
		-3D3 -> 0F[44]
		-476,477 -> 10[46]
		-215F -> 0C[03]

		-20D0-20E1 -> 01[DD-F0]
		-483-486 -> 01[94-97]
		-559,55A -> 01[98,99]
		-711 -> 01[9A]

		-346-348,2BE-2C5,2CE-2CF -> 01[74-7F]
		-2D1-2D3,2DE,2E4-2E9 -> 01[81-8A]

		-342,343 -> 01[8D,8E]
		-345 -> 01[90]

		-700-780 01[8D-AF]. Maybe there is some kind of traditional
		order in Estrangela, but for now am not sure.
		/*
		-740-742 -> 01[8D-8F]
		-747,748,732,735,738,739,73C,73F,743-746,730 -> 01[90,91,94-9F]
		-731,733,734,736,737,73A,73B,73D,73E,749,74A,7A6-7A9
		 -> 01[A0-AA,AC-AF]
		*/
		-7AA-7B0 -> 01[B0-B6]

		-591-5C2 except for 5BA,5BE -> 01[03-33] in order

		No further patterns for >= 80

		TODO: Below are not done yet:
			- x < 0x80 in non-"0E" part
			- 03 <= x <= 0D in "0E" part
			- 7B <= x <= 7F in "0E" part

**** sortkey details by category

	The actual value analysis is not complete in this document. See the
	actual generator code.

	1 specially ignored ones (Japanese, Tamil, Thai)

		IdentifyBy: constants
		Unicode: 3099-309C, BCD, E47, E4C, FF9E, FF9F
		SortKey: 01 01 01 01 00

	2 shift weight characters
	
	They are either at 01 01 01 01 or 06, depending on StringSort. For
	convenience, I use 06 to describe them.

	2.1 control characters (specified as such in Unicode), except for
	whitespaces (0009-000D).

		ProcessAfter: 4.1
		IdentifyBy: UnicodeCategory.Control
		Unicode: 0001-000F minus 0009-000D, 007F-009F
		SortKey: 06 03 - 06 3D

	2.2 Apostrophe
		IdentifyBy: constant
		Unicode: 0027,FF07 (')
		SortKey: 06 80 (and width insensitive equivalents)

	2.3  minus sign, hyphen, dash
	  minus signs: FE63, 207B (super), 208B (sub), 002D, 00FD (full-width)
	  hyphens: 00AD (soft), 2010, 2011 (nonbreaking) ... Unicode HYPHEN?
	  dashes, horizontal bars: FE58 ... UnicodeCategory.DashPunctuation

		IdentifyBy: UnicodeCategory.DashPunctuation
		SortKey: 06 81 - 06 90 (and nonspace equivalents)

	2.4 Arabic spacing and equivalents (64B-652, FE70-FE7F)
	  They are part of nonspacing mark, but not equal.

		SortKey: 06 A0 - 06 A7 (and nonspace equivalents)

	3 nonprimary characters, mixed.

	  ModifierSymbol, except for that are not in category 0 and "07" area
	  (i.e. < 128) nor those equivalents

	  NonSpacingMark which is ignorable (IsIgnorableNonSpacing())
	  // 30D, CD5-CD6, ABD, 2B9-2C5, 2C8, 2CB-2CD, 591-5C2. NonSpacingMark in
	  // 981-A3C. A4D, A70, A71, ABC ...

	  TODO: I need more insight to write table generator.

	  SortKey: 01 03 01 - 01 B6 01

	  This part of MS table design is problematic (buggy): \u0592 should
	  not be equal to \u09BC.

	  I guess, this buggy design is because Microsoft first thought that
	  there won't be more than 255 characters in this area. Or they might be
	  aware of the problem but prefer table optimization.

	  Ideal solutions:

	  1) We should not mix those code (make things sequential) and expands
	     level 2 length to 2 bytes. Instead of having direct value, we
	     could use index (pointer) to zero-terminating level 2 table.

	  2) Include those charactors from minor cultures here.

	  If in "discriminatory mode", those tables could be still provided
	  as to be compatible to Windows.

	  Additionally there seems some bugs around Modifier letter collection.
	  For example, 2C6 should be nonspacing diacritical character but it
	  is regarded as a primary character. The same applies to Mandarin
	  tone marks (2C9-2CB) (and there's a plenty of such characters).

	4 space separators and some kind of marks

	4.1 whitespaces, paragraph separator etc.
	  UnicodeCategory.SpaceSeparator : 20, 3000, A0, 9-D, 2000-200B

	  SortKey : 07 02 - 07 18

	4.2 some OtherSymbols: 2422-2423
	
	  SortKey : 07 19 - 07 1A

	4.3 ASCII compatible marks ('!', '^', ...)
	  Non-alpha-numeric < 0x7F except for [[+-<=>']]
	  small compatibility equivalents -> itself, wide

	4.3 other marks
	  FIXME: how to identify them?
	  some Punctuations: InitialQuote/FinalQuote/Open/Close/Connector
	  some OtherSymbols: 2400-2424
	  3003, 3006, 2D0, 10FB
	  remaining Puncuations: 9xx, 7xx
	  70F (Format)

	  SortKey : 07 1B - 07 F0

	5 mathmatical symbols
	  InitialQuotePunctuation and FinalQuotePunctuation in ASCII
	  (not Quotation_Mark property in PropList.txt ; 22, 27)

	  byte area MathSymbol: 2B,3C,3D,3E,AB,B1,BB,D7,F7 except for AC
	  some MathSymbol (2044, 208A, 208C, 207A, 207C)
	  OtherLetter (1C0-1C2)
	  2200-22FF MathSymbol except for 221E (INF. ; regarded as a number)

	  SortKey : 08 02 - 08 F8

	6 Arrows and Box drawings
	  09 02 .. 09 7C : 2300-237A
			only primary differences
	  09 BC ... 09 FE : 25A0-AB, 25E7-EB, 25AC-B5, 25EC-EF, 25B6-B9,
			25BC-C3, 25BA-25BB, 25C4-25D8, 25E6, 25DA-25E5
			21*,25*,26*,27*
			This area contains level 2 values.
	  2190- (non-codepoint order)
		note that there are many compatibility equivalents
	  2500- except for 266F (#)

	  SortKey : 09 02 - 09 7C, 09 BC 01 03 - 09 BC 01 13,
		    09 {BD|BE|BF} 01 {03|04}, ...
		    TODO: fill the patterns

	7 currency sumbols and some punctuations
	  byte CurrencySymbols except for 24 ($)
	  byte OtherSymbols (A7-B6) 
	  ConnectorPunctuation - 2040 (i.e. FF65, 30FB)
	  OtherPunct/ConnectorPunct/CurrencyCymbol 2020-20AC - 20AC
	  OtherSymbol 3012-303F,3004,327F
	  MathSymbol/OtherSymbol 2600-2767 (math = 266F)
	  OtherSymbol 2440-244A, 2117
	  20AC (CurrencySymbol)

	  Sortey : 0A 02 - 0A FB

	8 (C) numbers
	  all DecimalDigitNumber, LetterNumber, non-CJK OtherNumber.
	  9F8.
	  digits, in numeric order. We can use NET_2_0 CharUnicodeInfo.
	  221E. (INF.)

	  SortKey : 0C 02 (9F8), 0C 03 - 0C E1 (normal numbers), 0C FF (INF.)

	9 (E) latin letters (alphabets), mixing alphabetical symbols
	  Alphabets, A to Z, mixing alphabetical symbols. See below.
	  F8-2B8 except for (1BB-1BD and 1C0-1C3), but not sequential.
	  2E0-2E3.

	  For diacritical orders, see level 2.

	  For 'A' it is "0E 02", for 'B' "0E 09" ... 'Z' "0E A9", ezh "0E AA".
	  0E B3 (1BE), 0E B4 (298)

	  There are CJK compatibility characters (3800-) and letterlike
	  symbols (2100-) in those A-to-Z area, ordered by character name.

	  Primary weights are sometimes culture-dependent.
		FIXME: [0E 0D], [0E 0E], [0E 4B], [0E 75], [0E B2] are unknown
		02: A
		03: C4 in sk|vi
		04: C1 in is|pl|vi
		05-08: CJKext
		09: B
		0A: C
		0B: 10D in hr|lt|lv|pl, 107 in pl
		0C: C7 in az|tr, 10D in cs|sk, 106 in hr
		0F-19: CJKext
		1A: D
		1B: 189 (African D)
		1C: 2A3 (DZ Digraph)
		1D: 1C6 (dz) in hr
		1E: 110 (D with stroke) in hr
		1F-20: CJKext
		21: E
		22: 18F=259 in az, E9 in is, 119 in pl, EA in vi, 1EBE-1EC7 in vi
		23: F
		24: CJKext
		25: G
		26: 11F in az|tr, 123 in lv
		28-2B: CJKext
		2C: H
		2D: 267 (Heng with hook)
		2E: 33CB in az, 33CA in tr
		2F-31: CJKext
		32: I
		33: CD in is, 79 in lt
		34: CJKext
		35: J
		36: K
		37-47: CJKext
		48: L
		49: 2114
		4A: 1C9 in hr
		4C: 142 in pl
		4D-50: CJKext
		51: M
		52-6F: CJKext
		70: N
		71: 2116
		72: 144 in pl
		73: F1 in es, 1CC in hr
		74: 14B
		76-7B: CJKext
		7C: O
		7D: F6 in az|hu|tr, 151 in hu, F3 in is|pl, F4 in sk|vi, 1ED0-1ED9 in vi
		7E: P
		7F-88: CJKext
		89: Q
		8A: R
		8B: 211E
		8C: 211F
		8D: 159 in cs|sk
		8E-90: CJKext
		91: S
		92: 2108
		93: 2120
		94-95: CJKext
		96: 17F (LATIN SMALL LONG S)
		97: 15F in az|tr, 161 in cs|hr|lt|lv|sk|sl, 7A,179-17C in et, 15B in pl
		98: 17E in et, 15F in ro, 15B in sl
		99: T
		9A: 2121
		9B: CJKext
		9C: 2122
		9D: 2A6
		9E: 166
		9F: U
		A0: FA in is, 1B0,1EE8-1EF1 in vi
		A1: FC in az|tr, 56,57 in et, FC,171 in hu, FB in vi
		A2: V
		A3: 2123
		A4: W
		A5: CJKext
		A6: X
		A7: Y
		A8: FD in is
		A9: Z
		AA: 292
		AB: DE in is, 17E in lt|lv, 17A in pl
		AC: E6 in da|is, 1E3 in is, 17C in pl, 17E in sl
		AD: 17E in cs|hr|sk, E5 in fi, F6,F8 in is 17A in sl
		AE: F6,F8,151 in da
		AF: E4 in fi
		B0: F6,F8,151 in fi
		B1: E5 in da, "aa" in da
		B3: 1BE
		B4: 298

	10 culture dependent letters (general)
	  0F: 386-3F2 ... Greek and Coptic
		386-3CF: [0F 02] - [0F 19] (consider primary equivalents)
		3D0-3EF: [0F 40] - [0F 54]
	  10: 400-4E9 ... Cyrillic.
		For 400-45F and 4B1, they are mostly UCA DUCET order.
		After that 460-481 follows, by codepoint.
		(490-4FF except for 4B1 and Cyrillic supplementary are unused.)
	  11: 531-586 ... Armenian.
		Simply sorted by codepoint (handle case).
	  12: 5D0-5F2 ... Hebrew.
		Codepoint order (handle case).
	  13: 621-6D5 plus 670 (NonSpacingMark) ... Arabic
		Area 1:
		They look like ordered by Arabic Presentation Form B except
		for FE95, and considering diacritical equivalents maybe based
		on the primary character area (621-6D5).
		There are still some special characters: 67E,686,698,6AF ...
		which might not have equivalent characters (I wonder how they
		are inserted into the presentation form B map).

			Solution:
			- hamza, waw, yeh (621,624,626) are special: [13 07]
			- For all remaining letters, get primary letter name
			  and store it into dictionary. If unique, then
			  increment index by 4 from [13 0B]
		Area 2:
		674-6D5 : by codepoint from [13 84].
	  14: 901-963 exc. 93A-93D 950-954 ... Devanagari.
		For <905 codepoint order, x2 from [14 04].
		For 905-939 codepoint order, x4 from [14 0B].
		For 93E-94D codepoint order, x2 from [14 DA].
	  15: 982-9FA ... Bengali. Actually all UnicodeCategories except for
		NonSpacingMark, DecimalDigitNumber and OtherNumber.
		For <9E0 simple codepoint order from [15 02].
		For >9E0 simple codepoint order from [15 3B].
	  16: A05-A74 exc. A3C A4D A66-A71 ... Gurmukhi.
		The same as UCA order, x4 from [16 04].
	  17: A81-AE0 exc. ABC-ABD ... Gujarati.
		Mostly equivalent to UCA, but insert {AB3,A81-A83} before AB9,
		x4 from [17 04].
	  18: B00-B70 ... Oriya
		All but NonSpacingMark and DecimalDigitNumber, by codepoint.
	  19: B80-BFF ... Tamil
		BD7 is special : [19 02].
		B82-B93 (vowels) : x2 from [19 0A].
		B94 (vowel AU) : [19 24]
		For consonant order Windows has native Tamil order which is
		different from UCA.
		http://www.nationmaster.com/encyclopedia/Tamil-alphabet
		(The order is still different in "Grantha" order from TAM.)
		So, we should just hold constant array for consonants.
		And put them in order, x4 form [19 26].
		BBE-BCC : SpacingCombiningMark and BC0 ... x2 from [19 82].
	  1A: C00-C61 ... Telugu.
		C55 and C56 are ignored (C5x line and remaining part of C6x
		line just look like ignored).
		C60 and C61 are specially placed. C60 after C0B, C61 after C0C.
		Except for above, by codepoint, x3 from [1A 04].
	  1B: C80-CE5 ... Kannada.
		CD5,CD6 (and CE6-CEF: DecimalDigitNumber) are ignored.
		by codepoint, 3x from [1B 04].
	  1C: D02-D40 ... Malayalam.
		by simple codepoint from [1C 02].
	  (1D: Sinhala ... totally ignored?)
	  1E: E00-E44 ... Thai.
		preceding vowels (E40-E44) by codepoint [1E 02 - 1E 06]
		consonants (E01-E2A) by codepoint, x6 from [1E 07].
	  1F: E2B-E5B,E80-EDF ... Thai / Lao. (Thai breaks the category wall.)
		Thai:
		remaining consonants (E2B-E2E) by codepoint, x6 from [1E 07].
		remaining vowels (E2F-E3A) by codepoint.
		E45,E46,E4E,E4F,E5A,E5B
		Lao:
		E80-EDF by codepoint from [1F 02].
	  21: 10A0-10FF ... Georgian
		Mostly equal to UCA order, but swap 10E3 <-> 10F3,
		x5 from [21 05].

	11 (22) japanese kana letters and symbols, not in codepoint order

	  For single character, the sortkeys look like:
	  - Katakana normal A, Half Width (FF71) : FF 02 C4 FF C4 FF 01 00
	  - Katakana normal A, Full Width (30A2) : FF C4 FF 01 00
	  - Hiragana normal A, Full Width (3042) : FF FF 01 00

	  Actually for level 4 weights, there is a different rule (see
	  "level 4" format above).

	  There is also 32D0 (normal katakana A with circle) that have
	  diacritic difference.

	  For primary weights, 'A' to 'O' are mapped to 22-26, 'Ka' to 'Ko'
	  are to 2A-2E, 'Sa' to 'So' are to 32-36 ... and follows.
	  'Nn' is special: [22 80].

	  After Kana characters, there are CJK compat characters.
	  From 22 97 01 01 01 01 00 (3349) to 22 A6 01 01 01 01 00 (333B) are
	  sorted in JIS table order (CP932.TXT). Remaining square characters
	  are maybe sorted in Alphabetic order.

	  UCA DUCET also does not apply here.

	12 (23) bopomofo letters
		3105-312C: simple codepoint order from [23 02].

	13 culture dependent letters 2
		710-72C : Estrangela (ancient Syriac).
			codepoint order.
			711 is excluded (superscript).
			714,716,71C,724 and 727 are "alternative" characters.
			SortKey: [24 0B]-[24 60], by x where x is 2 for those
			which is "alternative" defined above, otherwise 4.

		780-7A5 : Thaana
			Equals to UCA order, x2 from [24 6E].

	(Maybe we should add remaining minor-culture characters here. Tibetan,
	Limbu, Tagalog, Hanunoo, Buhid, Tagbanwa, Myanmar, Kumer, Tai-Le,
	Mongolian, Cherokee, Canadian-Aboriginal, Ogham, Runic are ignored)

	14 (41-45) surrogate Pt.1

	15 (52 02-7E C8) hangul, mixing combined ones

	  It starts from 1100. After width-insensitive equivalents, those
	  syllables (from AC00) follow (until <del>AE4B</del>D7A3).
	  It follows kinda based on some formula (sometimes it looks not
	  e.g. 1117). FIXME: this area should be clarified more.

	  Hangle Syllables should not be filled in the table. Instead, they
	  can be easily computed by the following formulum:

		// rc is the codepoint for the input Syllable
		// (p holds "category << 8 + level1weight")
		int ri = ((int) rc - 0xAC00) + 1;
		ushort p = (ushort)
			((ri / 254) * 256 + (ri % 254) + 2);

	  Hangul Jamo cannot be filled in the table directly, since
	  U+1113 - U+159 holds additional primary key bytes.
	  FIXME: find out how they can be computed.
	  See http://dev.icu-project.org/cgi-bin/viewcvs.cgi/*checkout*/icuhtml/design/collation/ICU_collation_design.htm?rev=HEAD&content-type=text/html#Hangul_Implicit_CEs

	16 (9E 02-F1 E4) CJK

	   9E 02-F0 B4 [3192-319F,3220-3243,3280-32B0,4E00-9FA5] : CJK mark,
		parenthesized CJK (part), circled CJK (part), CJK ideograph.
		Ordered but condidering compatible characters (i.e. there is
		no other way than having massive mapping).
	   F0 B5-F1 E4 [F900-FA2D]. CJK compatibility ideograph.

	   LAMESPEC: in the latest spec CJK ends at 9F BB. Since MS table
	   joins these two categories without any consideration, it is
	   impossible to insert those new characters without breaking binary
	   compatibility.

	17 (E5 02-FE 33) PrivateUse.

	   In fact it overlaps to CJK characters (maybe layout design failure).

	18 (F2 01-F2 31) surrogate Pt.2

	   In fact it overlaps to PrivateUse (maybe layout design failure).

	19 (FE FF 10 02 - FE FF 29 E9) CJK extensions

	   3400-4DB5. Ordered.

	   They should be computed, since this range should be anyways
	   checked (to not directly acquire the sortkey values but needs
	   FE FF part) and anyways it can be computed.

	20 (FF FF 01 01 01 01 00) special.
	   Japanese extender marks:
	   	3005, 3031, 3032, 309D, 309E, 30FC, 30FD, 30FE, FF70

	   LAMESPEC: In native context Microsoft's understanding of Japanese 
	   3031 and 3032 is wrong. They can never be used to repeat *just
	   previous one* character, but are usually used to repeat two or
	   more characters. Also, 3005 is not always used to repeat exactly
	   one character but sometimes used to repeat two (or possibly more)
	   characters.

	   Arabic shadda: FE7C (isolated), FE7D (medium)
	   (Actually they are not extender in Unicode PropList.txt)


	- by UnicodeCategory -

	DashPunctuation		6 (no exception)
	DecimalDigitNumber	C (no exception)
	EnclosingMark		1 E (no exception)
	Format			7 (only 70F)
	LetterNumber		C (no exception)
	LineSeparator		7 (only 2028)
	ParagraphSeparator	7 (only 2029)
	PrivateUse
	SpaceSeparator		7 (no exception)
	Surrogate

	OtherNumber		C(<3192), 9E-A7 (3124<)

	Control			6 except for 9-D (7)
	FinalQuotePunctuation	7 except for BB (8)
	InitialQuotePunctuation	7 except for AB (8)
	ClosePunctuation	7 except for 232A (9)
	OpenPunctuation		7 except for 2329 (9)
	ConnectorPunctuation	7 except for FF65, 30FB, 2040 (A)

	OtherLetter		1, 7, 8 (1C0-1C2), C, 12-FF
	MathSymbol		8, 9, 6, 7, A, C
	OtherSymbol		7, 9, A, C, E, F, <22, 52<
	CurrencySymbol		A except for FF69,24,FF04 (7) and 9F2,9F3 (15)

	LowercaseLetter		E-11 except for B5 (A) and 1BD (C)
	TitlecaseLetter		E (no exception)
	UppercaseLetter		E,F,10,11,21 except for 1BC (C)
	ModifierLetter		1, 7, E, 1F, FF
	ModifierSymbol		1, 6, 7
	NonSpacingMark		1, 6, 13-1F
	OtherPunctuation	1, 7, A, 1F
	SpacingCombiningMark	1, 14-22

*** Culture dependent design

	(To assure this section, run the simple dumper code shown above,
	with all the supported cultures.)

**** primary cultures and non-primary cultures

	This code is used to iterate character dump through all cultures,
	using sort key dumper put above.

	public static void Main ()
	{
		foreach (CultureInfo ci in CultureInfo.GetCultures (
			CultureTypes.AllCultures)) {
			ProcessStartInfo psi = new ProcessStartInfo ();
			psi.FileName = "../allsortkey.exe";
			psi.Arguments = ci.Name;
			psi.RedirectStandardOutput = true;
			psi.UseShellExecute = false;
			Process p = new Process ();
			p.StartInfo = psi;
			p.Start ();
			string s = p.StandardOutput.ReadToEnd ();
			StreamWriter sw = new StreamWriter (ci.Name + ".txt", false, Encoding.UTF8);
			sw.Write (s);
			sw.Close ();
		}
	}

	For each sub culture (that has a parent culture), its collation
	mapping is identical to that of its parent, except for az-AZ-Cyrl.

	Additionally,

	- zh-CHS = zh-CN = zh-SG = zh-MO : pronounciation
	- zh-TW = zh-HK = zh-CHT : stroke count
	- da = no
	- fi = sv
	- hr = sr

	(UCA implies that there are some cultures that sorts alphabets from
	large to small, but as long as I see there is no such CultureInfo.)

**** Latin characters and NonSpacingMark order tailorings

	div : FDF2 is 24 83 01 01 01 01 00 (only 1 difference)
	syr : some NonSpacingMarks are totally ignorable.
	tt,kk,mk,az-AZ-Cyrl,uk : cyrillic difference
	az,et,lt,lv,sl,tr,sv,ro,pl,no,is,hu,fi,es,da : latin difference
	fr : 1C4-1C6.
	sk,hr,cs : latin and NonSpacingMark differences

	ja,ko : 5C

**** CJK character order tailorings

	<how many tables?>

	There are five different CJK orderings:
	default, ko(-KR), ja(-JP), zh-CHS and zh-CHT
	They have very different CJK mapping for each.

	Since they seems based on traditional encodings, we are likely to
	provide other constant tables and switch depending on the culture.

	<what characters are different from the invariant culture?>

	ko : CJK layout difference (52 -> 80)
	ja,zh-CHS,zh-TW : dash (5C), CJK layout difference.

	Target characters are : CJK misc (3190-), Parenthesized CJK
	(3200-), CJK compat (3300-), CJK ideographs (4E00-),
	CJK compat ideograph (F900-), Half/Full width compat (FF00-)

	Additionally for Korean: Jamo (1100-), Hangle syllables (AC00)

	<how do they consist of?>

	Japanese CJK order looks based on JIS table order. Those characters
	which are also in JIS table are moved to 80 xx. Those which are *not*
	in JIS table are left as is (9E-FE).

	Additionally, Windows has different order for characters below:
	4EDD,337B,337E,337D,337D,337C
	They come in front of the first CJK character.

	Maybe Korean CJK order respects KS C 5619. Note that Korean mixes
	Hangul and CJK in their order so it's not flat order without indexes
	(thus, for CJK they are not computable). Also, there is an extra
	level2 values for Korean CJK map.

	For some Chinese such as zh-CHS, character order is based on pinyin.
	And for remaining Chinese such as zh-TW, it is stroke count based.

	CLDR of unicode.org has reference ordering of those characters, so
	our collation table extracts the sorting order from it.
	http://www.unicode.org/cldr/

**** Accent evaluation order

	With French cultures, diacritical marks are counted in reverse order.
	French ordering does not affect only on some diacritics (Japanese
	voice mark is not affected - FIXME: I doubt it, because the algorithm
	does not seem to allow it).

	Some other cultures might also have different ones, but not obvious.


** Mono implementation plans

*** Collator

	CompareInfo contains many overloaded methods that are just for 
	convenience. This class contains almost only required members.

	This class also provices access to tailoring information which is
	culture instance dependent:

	- French sorting
	- contractions/expansions - returns contraction or expansion
	- diacritical remapping
	- CJK custom mapping

	For data area, see CollationDataStructures.txt for now.

*** UnicodeTable (for now MSCompatUnicodeTable)

	Provides several access to character information with related to
	the collation element table (of our own).
	FIXME: I want to fix some bugs in Windows collation table especially
	to not ignore some characters, but it requires table modification
	which results in further memory allocation. Maybe it would be done
	as a patch for the runtime (or classlib) sources.

	- ignorable, ignorable nonspace, normalize width, normalize kanatype
	- level 4 sortkey provision method(s)

**** character comparison

	Since composite character is likely to *not have* equivalent
	codepoint, character comparison could not just be done by expecting
	"resulting char" value.
	In contrast, since composite character is likely to *do have*
	equivalent codepoint, character comparison could not also just be done
	by comparing "source char" value.

***** future optimizations

	From where those codepoints differ, for each strings it adjusts the
	position so that it represents exactly one character element. That is,
	find primary character as the start of the range and the last
	nonprimary character as the end of the range.

	Once Compare() adjusted the character location to be valid
	comparison position, further comparison is done as usual comparison,
	i.e. sortkey comparison considering comparisonLevel.

**** Characters in the table / characters computed

	Currently I plan not to contain following characters in the table
	but compute on demand:

	- PrivateUse
	- Surrogate

**** CJK Unified Ideographs

	For CJK unified ideographs, I had to make those culture-dependent
	tables in memory. Since they came from some classical encodings, they
	are not computed. Thus, they are in separate table.

**** Level 4: Kana type

	The table does not contain level 4 (kanatype) properties for
	the whole characters. They can be simply computed.

**** Level 3: Case/Width properties

	Case properties will be stored as a byte array, with limited areas of
	codepoint (cp < 3120 || FE00 < cp).

	For Hangul characters, it will be computed by codepoint areas.

**** Level 2: Diacritical properties

	The table will be composed as a byte for a character. If we provide
	non-buggy mode (Windows is buggy here by design; it just sums
	secondary weight values up), the values will come from UCA and
	non-blocking check will be introduced.

	Note that Japanese voice marks are considered at level 2 but no need to
	have maps.


** Reference materials

	Developing International Software for Windows 95 and Windows NT
	Appendix D Sort Order for Selected Languages
	http://www.microsoft.com/globaldev/dis_v1/disv1.asp?DID=dis33d&File=S24BF.asp

	UTR#10 Unicode Collation Algorithm (It is still informative)
	http://www.unicode.org/reports/tr10/

	UAX#15 Unicode Normalization
	http://www.unicode.org/reports/tr15/
	especially its canonical/compatibility equivalent characters might
	be informative to get those equivalent characters.
	
	To know which character can be expanded, Unicode Character Database
	(UCD) is informative (it's informative but not normative to us)
	http://www.unicode.org/Public/UNIDATA/UCD.html

	Decent char-by-char explaination is available here:
	http://www.fileformat.info/info/unicode/

	Wine uses UCA default element table, but has windows-like character
	filterings support in their LCMapString implementation:
	http://cvs.winehq.com/cvsweb/wine/dlls/kernel/locale.c
	http://cvs.winehq.com/cvsweb/wine/libs/unicode/sortkey.c

	Mimer has decent materials on culture specific collations:
	http://developer.mimer.com/collations/

	This is written in Japanese, but awesome analysis on MS Access
	string sorting:
	http://www.asahi-net.or.jp/~ez3k-msym/comp/acccoll.htm