COLLATION

COLLATION MODULE
================

Standard: UTS #10 (Unicode Collation Algorithm)
Files:    src/lingenic_text-collation_spec.ads   (ghost specification)
          src/lingenic_text-collation.ads        (public API)
          src/lingenic_text-collation.adb        (implementation)


PURPOSE
-------

The Collation module implements the Unicode Collation Algorithm using
the Default Unicode Collation Element Table (DUCET).  It provides
linguistically correct string comparison and sort key generation.


GHOST SPECIFICATION (Collation_Spec)
------------------------------------

Types:

  subtype Weight_16 is Natural range 0 .. 65535;
    16-bit collation weight.

  type Collation_Element is record
    Primary   : Weight_16;
    Secondary : Weight_16;
    Tertiary  : Weight_16;
    Variable  : Boolean;
  end record;

  type Variable_Weight_Option is (Non_Ignorable, Shifted);
    Non_Ignorable: variable-weight elements retain their weights.
    Shifted: variable-weight elements are shifted to a quaternary level.

  type Comparison_Result is (Less, Equal, Greater);

Implicit Weight Ranges (UTS #10, Section 10.1.3, Unicode 17.0):

  For codepoints not in the DUCET, implicit weights are computed
  algorithmically based on the codepoint's block:

  Core Han:   U+4E00..U+9FFF (CJK Unified Ideographs) and specific
              ranges in CJK_Compatibility_Ideographs
  Other Han:  CJK Extensions A through J
  Siniform:   Tangut, Tangut Components, Nushu, Khitan Small Script


INITIALIZATION
--------------

  procedure Initialize
    (UCD_Dir : String;
     Success : out Boolean);

    Pre:  Normalization.Initialized
    Post: if Success then Initialized

Reads from UCD_Dir:

  allkeys.txt    Default Unicode Collation Element Table (DUCET)
                 ~2.3 MB, contains collation elements for every
                 assigned codepoint plus contractions

Builds internal data tables:

  CE_Index/CE_Data          Per-codepoint collation element lookup
  Contraction_Starter       Boolean array: True if CP starts a contraction
  Starter_Index/Entries     Contraction matching tables
  Implicit_Ranges           @implicitweights ranges from allkeys.txt


PUBLIC API
----------

Compare:

  procedure Compare
    (Left    : Byte_Array;
     Right   : Byte_Array;
     Option  : Variable_Weight_Option;
     Result  : out Comparison_Result;
     Success : out Boolean);

    Pre:  Initialized, Normalization.Initialized,
          Normalization.Data_All_Terminal
          Left'Length >= 1, Right'Length >= 1
    Post: (none beyond Success semantics)

  Compares two UTF-8 strings using DUCET collation.

  Algorithm:
    1. Both inputs are NFD-normalized internally
    2. Collation elements are produced for each codepoint
       (including contraction handling and implicit weights)
    3. Multi-level comparison per UTS #10:
       - Level 1: Primary weights (base character differences)
       - Level 2: Secondary weights (accent differences)
       - Level 3: Tertiary weights (case differences)
       - Level 4: Quaternary weights (Shifted mode only)
    4. Result: Less, Equal, or Greater

  Variable weighting:
    Non_Ignorable: variable elements (punctuation, symbols) use their
    actual weights at all levels.
    Shifted: variable elements are ignored at levels 1-3, compared at
    a quaternary level (sorts punctuation as very low priority).

  Success is False if either input is invalid UTF-8, too long, or
  an internal buffer overflows.

Sort_Key:

  procedure Sort_Key
    (Input   : Byte_Array;
     Option  : Variable_Weight_Option;
     Key     : in out Byte_Array;
     Last    : out Natural;
     Success : out Boolean);

    Pre:  Initialized, Normalization.Initialized,
          Normalization.Data_All_Terminal
          Input'Length >= 1, Key'Length >= 1
    Post: if Success then
            Last in Key'First..Key'Last
          else
            Last = Key'First - 1

  Builds a binary sort key from a UTF-8 string.

  Sort keys can be compared byte-by-byte (like memcmp) for correct
  ordering.  This is useful when the same string must be compared
  against many others: compute the sort key once, then compare keys.

  The sort key format follows UTS #10: primary weights concatenated,
  then a separator, secondary weights, separator, tertiary weights,
  and (for Shifted mode) quaternary weights.


DEPENDENCIES
------------

The Collation module depends on:

  Normalization    NFD normalization of input strings
  Properties       (transitively, through Normalization)

Both must be initialized before Collation.Initialize is called.
Normalization must be initialized before Compare or Sort_Key is called
(enforced by preconditions requiring Normalization.Initialized and
Normalization.Data_All_Terminal).


CONTRACTION HANDLING
--------------------

Some collation elements span multiple codepoints (e.g., "ch" in some
languages).  The DUCET includes these as contractions.

The implementation uses:
  - Contraction_Starter: flat Boolean array indexed by codepoint.
    True if a codepoint can start a contraction sequence.
  - Starter_Index/Entries: for contraction starters, a table of
    possible continuations and their collation elements.

When a contraction starter is encountered, the algorithm attempts
longest-match against the continuation table.  If no match, the
single-codepoint CE is used.


IMPLICIT WEIGHTS
----------------

Codepoints not in the DUCET receive implicit weights computed from
their codepoint value.  The algorithm follows UTS #10 Section 10.1.3:

  - Classify the codepoint into a weight range (Core Han, Other Han,
    Siniform, or Unassigned)
  - Compute primary weight from the codepoint value using range-specific
    base values and offsets
  - Secondary and tertiary weights are fixed (0020h and 0002h)

This ensures all codepoints have a defined sort order even without
explicit DUCET entries.