3 abstract class Collation
{
9 static function singleton() {
10 if ( !self
::$instance ) {
11 global $wgCategoryCollation;
12 self
::$instance = self
::factory( $wgCategoryCollation );
14 return self
::$instance;
19 * @param $collationName string
22 static function factory( $collationName ) {
23 switch( $collationName ) {
25 return new UppercaseCollation
;
27 return new IcuCollation( 'root' );
29 # Provide a mechanism for extensions to hook in.
30 if ( class_exists( $collationName ) ) {
31 $collationObject = new $collationName;
32 if ( $collationObject instanceof Collation
) {
33 return $collationObject;
35 throw new MWException( __METHOD__
.": collation type \"$collationName\""
36 . " is not a subclass of Collation." );
39 throw new MWException( __METHOD__
.": unknown collation type \"$collationName\"" );
45 * Given a string, convert it to a (hopefully short) key that can be used
46 * for efficient sorting. A binary sort according to the sortkeys
47 * corresponds to a logical sort of the corresponding strings. Current
48 * code expects that a line feed character should sort before all others, but
49 * has no other particular expectations (and that one can be changed if
52 * @param string $string UTF-8 string
53 * @return string Binary sortkey
55 abstract function getSortKey( $string );
58 * Given a string, return the logical "first letter" to be used for
59 * grouping on category pages and so on. This has to be coordinated
60 * carefully with convertToSortkey(), or else the sorted list might jump
61 * back and forth between the same "initial letters" or other pathological
62 * behavior. For instance, if you just return the first character, but "a"
63 * sorts the same as "A" based on getSortKey(), then you might get a
75 * etc., assuming for the sake of argument that $wgCapitalLinks is false.
77 * @param string $string UTF-8 string
78 * @return string UTF-8 string corresponding to the first letter of input
80 abstract function getFirstLetter( $string );
83 class UppercaseCollation
extends Collation
{
85 function __construct() {
86 // Get a language object so that we can use the generic UTF-8 uppercase
88 $this->lang
= Language
::factory( 'en' );
91 function getSortKey( $string ) {
92 return $this->lang
->uc( $string );
95 function getFirstLetter( $string ) {
96 if ( $string[0] == "\0" ) {
97 $string = substr( $string, 1 );
99 return $this->lang
->ucfirst( $this->lang
->firstChar( $string ) );
103 class IcuCollation
extends Collation
{
104 var $primaryCollator, $mainCollator, $locale;
105 var $firstLetterData;
108 * Unified CJK blocks.
110 * The same definition of a CJK block must be used for both Collation and
111 * generateCollationData.php. These blocks are omitted from the first
112 * letter data, as an optimisation measure and because the default UCA table
113 * is pretty useless for sorting Chinese text anyway. Japanese and Korean
114 * blocks are not included here, because they are smaller and more useful.
116 static $cjkBlocks = array(
117 array( 0x2E80, 0x2EFF ), // CJK Radicals Supplement
118 array( 0x2F00, 0x2FDF ), // Kangxi Radicals
119 array( 0x2FF0, 0x2FFF ), // Ideographic Description Characters
120 array( 0x3000, 0x303F ), // CJK Symbols and Punctuation
121 array( 0x31C0, 0x31EF ), // CJK Strokes
122 array( 0x3200, 0x32FF ), // Enclosed CJK Letters and Months
123 array( 0x3300, 0x33FF ), // CJK Compatibility
124 array( 0x3400, 0x4DBF ), // CJK Unified Ideographs Extension A
125 array( 0x4E00, 0x9FFF ), // CJK Unified Ideographs
126 array( 0xF900, 0xFAFF ), // CJK Compatibility Ideographs
127 array( 0xFE30, 0xFE4F ), // CJK Compatibility Forms
128 array( 0x20000, 0x2A6DF ), // CJK Unified Ideographs Extension B
129 array( 0x2A700, 0x2B73F ), // CJK Unified Ideographs Extension C
130 array( 0x2B740, 0x2B81F ), // CJK Unified Ideographs Extension D
131 array( 0x2F800, 0x2FA1F ), // CJK Compatibility Ideographs Supplement
134 const RECORD_LENGTH
= 14;
136 function __construct( $locale ) {
137 if ( !extension_loaded( 'intl' ) ) {
138 throw new MWException( 'An ICU collation was requested, ' .
139 'but the intl extension is not available.' );
141 $this->locale
= $locale;
142 $this->mainCollator
= Collator
::create( $locale );
143 if ( !$this->mainCollator
) {
144 throw new MWException( "Invalid ICU locale specified for collation: $locale" );
147 $this->primaryCollator
= Collator
::create( $locale );
148 $this->primaryCollator
->setStrength( Collator
::PRIMARY
);
151 function getSortKey( $string ) {
152 // intl extension produces non null-terminated
153 // strings. Appending '' fixes it so that it doesn't generate
154 // a warning on each access in debug php.
155 wfSuppressWarnings();
156 $key = $this->mainCollator
->getSortKey( $string ) . '';
161 function getPrimarySortKey( $string ) {
162 wfSuppressWarnings();
163 $key = $this->primaryCollator
->getSortKey( $string ) . '';
168 function getFirstLetter( $string ) {
169 $string = strval( $string );
170 if ( $string === '' ) {
175 $firstChar = mb_substr( $string, 0, 1, 'UTF-8' );
176 if ( ord( $firstChar ) > 0x7f
177 && self
::isCjk( utf8ToCodepoint( $firstChar ) ) )
182 $sortKey = $this->getPrimarySortKey( $string );
184 // Do a binary search to find the correct letter to sort under
185 $min = $this->findLowerBound(
186 array( $this, 'getSortKeyByLetterIndex' ),
187 $this->getFirstLetterCount(),
191 if ( $min === false ) {
192 // Before the first letter
195 return $this->getLetterByIndex( $min );
198 function getFirstLetterData() {
199 if ( $this->firstLetterData
!== null ) {
200 return $this->firstLetterData
;
203 $cache = wfGetCache( CACHE_ANYTHING
);
204 $cacheKey = wfMemcKey( 'first-letters', $this->locale
);
205 $cacheEntry = $cache->get( $cacheKey );
208 $this->firstLetterData
= $cacheEntry;
209 return $this->firstLetterData
;
212 // Generate data from serialized data file
214 $letters = wfGetPrecompiledData( "first-letters-{$this->locale}.ser" );
215 if ( $letters === false ) {
216 throw new MWException( "MediaWiki does not support ICU locale " .
217 "\"{$this->locale}\"" );
222 // It's impossible to have the precompiled data file properly sorted,
223 // because the sort order changes depending on ICU version. If the
224 // array is not properly sorted, the binary search will return random
227 // We also take this opportunity to remove primary collisions.
228 $letterMap = array();
229 foreach ( $letters as $letter ) {
230 $key = $this->getPrimarySortKey( $letter );
231 if ( isset( $letterMap[$key] ) ) {
233 // Keep whichever one sorts first in the main collator
234 if ( $this->mainCollator
->compare( $letter, $letterMap[$key] ) < 0 ) {
235 $letterMap[$key] = $letter;
238 $letterMap[$key] = $letter;
241 ksort( $letterMap, SORT_STRING
);
243 'chars' => array_values( $letterMap ),
244 'keys' => array_keys( $letterMap )
247 // Reduce memory usage before caching
251 $this->firstLetterData
= $data;
252 $cache->set( $cacheKey, $data, 86400 * 7 /* 1 week */ );
256 function getLetterByIndex( $index ) {
257 if ( $this->firstLetterData
=== null ) {
258 $this->getFirstLetterData();
260 return $this->firstLetterData
['chars'][$index];
263 function getSortKeyByLetterIndex( $index ) {
264 if ( $this->firstLetterData
=== null ) {
265 $this->getFirstLetterData();
267 return $this->firstLetterData
['keys'][$index];
270 function getFirstLetterCount() {
271 if ( $this->firstLetterData
=== null ) {
272 $this->getFirstLetterData();
274 return count( $this->firstLetterData
['chars'] );
278 * Do a binary search, and return the index of the largest item that sorts
279 * less than or equal to the target value.
281 * @param $valueCallback array A function to call to get the value with
282 * a given array index.
283 * @param $valueCount int The number of items accessible via $valueCallback,
284 * indexed from 0 to $valueCount - 1
285 * @param $comparisonCallback array A callback to compare two values, returning
286 * -1, 0 or 1 in the style of strcmp().
287 * @param $target string The target value to find.
289 * @return The item index of the lower bound, or false if the target value
290 * sorts before all items.
292 function findLowerBound( $valueCallback, $valueCount, $comparisonCallback, $target ) {
294 $max = $valueCount - 1;
296 $mid = $min +
( ( $max - $min ) >> 1 );
297 $item = call_user_func( $valueCallback, $mid );
298 $comparison = call_user_func( $comparisonCallback, $target, $item );
299 if ( $comparison > 0 ) {
301 } elseif ( $comparison == 0 ) {
307 } while ( $min < $max - 1 );
309 if ( $min == 0 && $max == 0 && $comparison > 0 ) {
310 // Before the first item
317 static function isCjk( $codepoint ) {
318 foreach ( self
::$cjkBlocks as $block ) {
319 if ( $codepoint >= $block[0] && $codepoint <= $block[1] ) {