jars/icu4j-4_4_2-src/main/classes/core/src/com/ibm/icu/text/CanonicalIterator.java

   1 /*\r
   2  *******************************************************************************\r
   3  * Copyright (C) 1996-2010, International Business Machines Corporation and    *\r
   4  * others. All Rights Reserved.                                                *\r
   5  *******************************************************************************\r
   6  */\r
   7 package com.ibm.icu.text;\r
   8 \r
   9 import java.util.ArrayList;\r
  10 import java.util.HashSet;\r
  11 import java.util.Iterator;\r
  12 import java.util.List;\r
  13 import java.util.Set;\r
  14 \r
  15 import com.ibm.icu.impl.Norm2AllModes;\r
  16 import com.ibm.icu.impl.Normalizer2Impl;\r
  17 import com.ibm.icu.impl.Utility;\r
  18 import com.ibm.icu.lang.UCharacter;\r
  19 \r
  20 /**\r
  21  * This class allows one to iterate through all the strings that are canonically equivalent to a given\r
  22  * string. For example, here are some sample results:\r
  23  * Results for: {A WITH RING ABOVE}{d}{DOT ABOVE}{CEDILLA}\r
  24  * <pre>\r
  25  1: {A}{RING ABOVE}{d}{DOT ABOVE}{CEDILLA}\r
  26  2: {A}{RING ABOVE}{d}{CEDILLA}{DOT ABOVE}\r
  27  3: {A}{RING ABOVE}{d WITH DOT ABOVE}{CEDILLA}\r
  28  4: {A}{RING ABOVE}{d WITH CEDILLA}{DOT ABOVE}\r
  29  5: {A WITH RING ABOVE}{d}{DOT ABOVE}{CEDILLA}\r
  30  6: {A WITH RING ABOVE}{d}{CEDILLA}{DOT ABOVE}\r
  31  7: {A WITH RING ABOVE}{d WITH DOT ABOVE}{CEDILLA}\r
  32  8: {A WITH RING ABOVE}{d WITH CEDILLA}{DOT ABOVE}\r
  33  9: {ANGSTROM SIGN}{d}{DOT ABOVE}{CEDILLA}\r
  34 10: {ANGSTROM SIGN}{d}{CEDILLA}{DOT ABOVE}\r
  35 11: {ANGSTROM SIGN}{d WITH DOT ABOVE}{CEDILLA}\r
  36 12: {ANGSTROM SIGN}{d WITH CEDILLA}{DOT ABOVE}\r
  37  *</pre>\r
  38  *<br>Note: the code is intended for use with small strings, and is not suitable for larger ones,\r
  39  * since it has not been optimized for that situation.\r
  40  * @author M. Davis\r
  41  * @stable ICU 2.4\r
  42  */\r
  43 \r
  44 public final class CanonicalIterator {\r
  45     /**\r
  46      * Construct a CanonicalIterator object\r
  47      * @param source string to get results for\r
  48      * @stable ICU 2.4\r
  49      */\r
  50     public CanonicalIterator(String source) {\r
  51         Norm2AllModes allModes = Norm2AllModes.getNFCInstance();\r
  52         nfd = allModes.decomp;\r
  53         nfcImpl = allModes.impl.ensureCanonIterData();\r
  54         setSource(source);\r
  55     }\r
  56 \r
  57     /**\r
  58      * Gets the NFD form of the current source we are iterating over.\r
  59      * @return gets the source: NOTE: it is the NFD form of the source originally passed in\r
  60      * @stable ICU 2.4\r
  61      */\r
  62     public String getSource() {\r
  63       return source;\r
  64     }\r
  65 \r
  66     /**\r
  67      * Resets the iterator so that one can start again from the beginning.\r
  68      * @stable ICU 2.4\r
  69      */\r
  70     public void reset() {\r
  71         done = false;\r
  72         for (int i = 0; i < current.length; ++i) {\r
  73             current[i] = 0;\r
  74         }\r
  75     }\r
  76 \r
  77     /**\r
  78      * Get the next canonically equivalent string.\r
  79      * <br><b>Warning: The strings are not guaranteed to be in any particular order.</b>\r
  80      * @return the next string that is canonically equivalent. The value null is returned when\r
  81      * the iteration is done.\r
  82      * @stable ICU 2.4\r
  83      */\r
  84     public String next() {\r
  85         if (done) return null;\r
  86 \r
  87         // construct return value\r
  88 \r
  89         buffer.setLength(0); // delete old contents\r
  90         for (int i = 0; i < pieces.length; ++i) {\r
  91             buffer.append(pieces[i][current[i]]);\r
  92         }\r
  93         String result = buffer.toString();\r
  94 \r
  95         // find next value for next time\r
  96 \r
  97         for (int i = current.length - 1; ; --i) {\r
  98             if (i < 0) {\r
  99                 done = true;\r
 100                 break;\r
 101             }\r
 102             current[i]++;\r
 103             if (current[i] < pieces[i].length) break; // got sequence\r
 104             current[i] = 0;\r
 105         }\r
 106         return result;\r
 107     }\r
 108 \r
 109     /**\r
 110      * Set a new source for this iterator. Allows object reuse.\r
 111      * @param newSource the source string to iterate against. This allows the same iterator to be used\r
 112      * while changing the source string, saving object creation.\r
 113      * @stable ICU 2.4\r
 114      */\r
 115     public void setSource(String newSource) {\r
 116         source = nfd.normalize(newSource);\r
 117         done = false;\r
 118 \r
 119         // catch degenerate case\r
 120         if (newSource.length() == 0) {\r
 121             pieces = new String[1][];\r
 122             current = new int[1];\r
 123             pieces[0] = new String[]{""};\r
 124             return;\r
 125         }\r
 126 \r
 127         // find the segments\r
 128         List<String> segmentList = new ArrayList<String>();\r
 129         int cp;\r
 130         int start = 0;\r
 131 \r
 132         // i should be the end of the first code point\r
 133         // break up the string into segements\r
 134 \r
 135         int i = UTF16.findOffsetFromCodePoint(source, 1);\r
 136 \r
 137         for (; i < source.length(); i += Character.charCount(cp)) {\r
 138             cp = source.codePointAt(i);\r
 139             if (nfcImpl.isCanonSegmentStarter(cp)) {\r
 140                 segmentList.add(source.substring(start, i)); // add up to i\r
 141                 start = i;\r
 142             }\r
 143         }\r
 144         segmentList.add(source.substring(start, i)); // add last one\r
 145 \r
 146         // allocate the arrays, and find the strings that are CE to each segment\r
 147         pieces = new String[segmentList.size()][];\r
 148         current = new int[segmentList.size()];\r
 149         for (i = 0; i < pieces.length; ++i) {\r
 150             if (PROGRESS) System.out.println("SEGMENT");\r
 151             pieces[i] = getEquivalents(segmentList.get(i));\r
 152         }\r
 153     }\r
 154 \r
 155     /**\r
 156      * Simple implementation of permutation.\r
 157      * <br><b>Warning: The strings are not guaranteed to be in any particular order.</b>\r
 158      * @param source the string to find permutations for\r
 159      * @param skipZeros set to true to skip characters with canonical combining class zero\r
 160      * @param output the set to add the results to\r
 161      * @internal\r
 162      * @deprecated This API is ICU internal only.\r
 163      */\r
 164     public static void permute(String source, boolean skipZeros, Set<String> output) {\r
 165         // TODO: optimize\r
 166         //if (PROGRESS) System.out.println("Permute: " + source);\r
 167 \r
 168         // optimization:\r
 169         // if zero or one character, just return a set with it\r
 170         // we check for length < 2 to keep from counting code points all the time\r
 171         if (source.length() <= 2 && UTF16.countCodePoint(source) <= 1) {\r
 172             output.add(source);\r
 173             return;\r
 174         }\r
 175 \r
 176         // otherwise iterate through the string, and recursively permute all the other characters\r
 177         Set<String> subpermute = new HashSet<String>();\r
 178         int cp;\r
 179         for (int i = 0; i < source.length(); i += UTF16.getCharCount(cp)) {\r
 180             cp = UTF16.charAt(source, i);\r
 181 \r
 182             // optimization:\r
 183             // if the character is canonical combining class zero,\r
 184             // don't permute it\r
 185             if (skipZeros && i != 0 && UCharacter.getCombiningClass(cp) == 0) {\r
 186                 //System.out.println("Skipping " + Utility.hex(UTF16.valueOf(source, i)));\r
 187                 continue;\r
 188             }\r
 189 \r
 190             // see what the permutations of the characters before and after this one are\r
 191             subpermute.clear();\r
 192             permute(source.substring(0,i)\r
 193                 + source.substring(i + UTF16.getCharCount(cp)), skipZeros, subpermute);\r
 194 \r
 195             // prefix this character to all of them\r
 196             String chStr = UTF16.valueOf(source, i);\r
 197             for (String s : subpermute) {\r
 198                 String piece = chStr + s;\r
 199                 //if (PROGRESS) System.out.println("  Piece: " + piece);\r
 200                 output.add(piece);\r
 201             }\r
 202         }\r
 203     }\r
 204 \r
 205     // FOR TESTING\r
 206 \r
 207     /*\r
 208      *@return the set of "safe starts", characters that are class zero AND are never non-initial in a decomposition.\r
 209      *\r
 210     public static UnicodeSet getSafeStart() {\r
 211         return (UnicodeSet) SAFE_START.clone();\r
 212     }\r
 213     */\r
 214     /*\r
 215      *@return the set of characters whose decompositions start with the given character\r
 216      *\r
 217     public static UnicodeSet getStarts(int cp) {\r
 218         UnicodeSet result = AT_START.get(cp);\r
 219         if (result == null) result = EMPTY;\r
 220         return (UnicodeSet) result.clone();\r
 221     }\r
 222     */\r
 223 \r
 224     // ===================== PRIVATES ==============================\r
 225 \r
 226     // debug\r
 227     private static boolean PROGRESS = false; // debug progress\r
 228     //private static Transliterator NAME = PROGRESS ? Transliterator.getInstance("name") : null;\r
 229     private static boolean SKIP_ZEROS = true;\r
 230 \r
 231     // fields\r
 232     private final Normalizer2 nfd;\r
 233     private final Normalizer2Impl nfcImpl;\r
 234     private String source;\r
 235     private boolean done;\r
 236     private String[][] pieces;\r
 237     private int[] current;\r
 238     // Note: C will need two more fields, since arrays there don't have lengths\r
 239     // int pieces_length;\r
 240     // int[] pieces_lengths;\r
 241 \r
 242     // transient fields\r
 243     private transient StringBuilder buffer = new StringBuilder();\r
 244 \r
 245 \r
 246     // we have a segment, in NFD. Find all the strings that are canonically equivalent to it.\r
 247     private String[] getEquivalents(String segment) {\r
 248         Set<String> result = new HashSet<String>();\r
 249         Set<String> basic = getEquivalents2(segment);\r
 250         Set<String> permutations = new HashSet<String>();\r
 251 \r
 252         // now get all the permutations\r
 253         // add only the ones that are canonically equivalent\r
 254         // TODO: optimize by not permuting any class zero.\r
 255         Iterator<String> it = basic.iterator();\r
 256         while (it.hasNext()) {\r
 257             String item = it.next();\r
 258             permutations.clear();\r
 259             permute(item, SKIP_ZEROS, permutations);\r
 260             Iterator<String> it2 = permutations.iterator();\r
 261             while (it2.hasNext()) {\r
 262                 String possible = it2.next();\r
 263 \r
 264 /*\r
 265                 String attempt = Normalizer.normalize(possible, Normalizer.DECOMP, 0);\r
 266                 if (attempt.equals(segment)) {\r
 267 */\r
 268                 if (Normalizer.compare(possible, segment,0)==0) {\r
 269 \r
 270                     if (PROGRESS) System.out.println("Adding Permutation: " + Utility.hex(possible));\r
 271                     result.add(possible);\r
 272 \r
 273                 } else {\r
 274                     if (PROGRESS) System.out.println("-Skipping Permutation: " + Utility.hex(possible));\r
 275                 }\r
 276             }\r
 277         }\r
 278 \r
 279         // convert into a String[] to clean up storage\r
 280         String[] finalResult = new String[result.size()];\r
 281         result.toArray(finalResult);\r
 282         return finalResult;\r
 283     }\r
 284 \r
 285 \r
 286     private Set<String> getEquivalents2(String segment) {\r
 287 \r
 288         Set<String> result = new HashSet<String>();\r
 289 \r
 290         if (PROGRESS) System.out.println("Adding: " + Utility.hex(segment));\r
 291 \r
 292         result.add(segment);\r
 293         StringBuffer workingBuffer = new StringBuffer();\r
 294         UnicodeSet starts = new UnicodeSet();\r
 295 \r
 296         // cycle through all the characters\r
 297         int cp;\r
 298         for (int i = 0; i < segment.length(); i += Character.charCount(cp)) {\r
 299 \r
 300             // see if any character is at the start of some decomposition\r
 301             cp = segment.codePointAt(i);\r
 302             if (!nfcImpl.getCanonStartSet(cp, starts)) {\r
 303               continue;\r
 304             }\r
 305             // if so, see which decompositions match\r
 306             for(UnicodeSetIterator iter = new UnicodeSetIterator(starts); iter.next();) {\r
 307                 int cp2 = iter.codepoint;\r
 308                 Set<String> remainder = extract(cp2, segment, i, workingBuffer);\r
 309                 if (remainder == null) {\r
 310                     continue;\r
 311                 }\r
 312 \r
 313                 // there were some matches, so add all the possibilities to the set.\r
 314                 String prefix= segment.substring(0,i);\r
 315                 prefix += UTF16.valueOf(cp2);\r
 316                 for (String item : remainder) {\r
 317                     result.add(prefix + item);\r
 318                 }\r
 319             }\r
 320         }\r
 321         return result;\r
 322         /*\r
 323         Set result = new HashSet();\r
 324         if (PROGRESS) System.out.println("Adding: " + NAME.transliterate(segment));\r
 325         result.add(segment);\r
 326         StringBuffer workingBuffer = new StringBuffer();\r
 327 \r
 328         // cycle through all the characters\r
 329         int cp;\r
 330 \r
 331         for (int i = 0; i < segment.length(); i += UTF16.getCharCount(cp)) {\r
 332             // see if any character is at the start of some decomposition\r
 333             cp = UTF16.charAt(segment, i);\r
 334             NormalizerImpl.getCanonStartSet(c,fillSet)\r
 335             UnicodeSet starts = AT_START.get(cp);\r
 336             if (starts == null) continue;\r
 337             UnicodeSetIterator usi = new UnicodeSetIterator(starts);\r
 338             // if so, see which decompositions match\r
 339             while (usi.next()) {\r
 340                 int cp2 = usi.codepoint;\r
 341                 // we know that there are no strings in it\r
 342                 // so we don't have to check CharacterIterator.IS_STRING\r
 343                 Set remainder = extract(cp2, segment, i, workingBuffer);\r
 344                 if (remainder == null) continue;\r
 345 \r
 346                 // there were some matches, so add all the possibilities to the set.\r
 347                 String prefix = segment.substring(0, i) + UTF16.valueOf(cp2);\r
 348                 Iterator it = remainder.iterator();\r
 349                 while (it.hasNext()) {\r
 350                     String item = (String) it.next();\r
 351                     if (PROGRESS) System.out.println("Adding: " + NAME.transliterate(prefix + item));\r
 352                     result.add(prefix + item);\r
 353                 }\r
 354             }\r
 355         }\r
 356         return result;\r
 357         */\r
 358     }\r
 359 \r
 360     /**\r
 361      * See if the decomposition of cp2 is at segment starting at segmentPos\r
 362      * (with canonical rearrangment!)\r
 363      * If so, take the remainder, and return the equivalents\r
 364      */\r
 365     private Set<String> extract(int comp, String segment, int segmentPos, StringBuffer buf) {\r
 366         if (PROGRESS) System.out.println(" extract: " + Utility.hex(UTF16.valueOf(comp))\r
 367             + ", " + Utility.hex(segment.substring(segmentPos)));\r
 368 \r
 369         String decomp = nfcImpl.getDecomposition(comp);\r
 370         if (decomp == null) {\r
 371             decomp = UTF16.valueOf(comp);\r
 372         }\r
 373 \r
 374         // See if it matches the start of segment (at segmentPos)\r
 375         boolean ok = false;\r
 376         int cp;\r
 377         int decompPos = 0;\r
 378         int decompCp = UTF16.charAt(decomp,0);\r
 379         decompPos += UTF16.getCharCount(decompCp); // adjust position to skip first char\r
 380         //int decompClass = getClass(decompCp);\r
 381         buf.setLength(0); // initialize working buffer, shared among callees\r
 382 \r
 383         for (int i = segmentPos; i < segment.length(); i += UTF16.getCharCount(cp)) {\r
 384             cp = UTF16.charAt(segment, i);\r
 385             if (cp == decompCp) { // if equal, eat another cp from decomp\r
 386                 if (PROGRESS) System.out.println("  matches: " + Utility.hex(UTF16.valueOf(cp)));\r
 387                 if (decompPos == decomp.length()) { // done, have all decomp characters!\r
 388                     buf.append(segment.substring(i + UTF16.getCharCount(cp))); // add remaining segment chars\r
 389                     ok = true;\r
 390                     break;\r
 391                 }\r
 392                 decompCp = UTF16.charAt(decomp, decompPos);\r
 393                 decompPos += UTF16.getCharCount(decompCp);\r
 394                 //decompClass = getClass(decompCp);\r
 395             } else {\r
 396                 if (PROGRESS) System.out.println("  buffer: " + Utility.hex(UTF16.valueOf(cp)));\r
 397                 // brute force approach\r
 398                 UTF16.append(buf, cp);\r
 399                 /* TODO: optimize\r
 400                 // since we know that the classes are monotonically increasing, after zero\r
 401                 // e.g. 0 5 7 9 0 3\r
 402                 // we can do an optimization\r
 403                 // there are only a few cases that work: zero, less, same, greater\r
 404                 // if both classes are the same, we fail\r
 405                 // if the decomp class < the segment class, we fail\r
 406 \r
 407                 segClass = getClass(cp);\r
 408                 if (decompClass <= segClass) return null;\r
 409                 */\r
 410             }\r
 411         }\r
 412         if (!ok) return null; // we failed, characters left over\r
 413         if (PROGRESS) System.out.println("Matches");\r
 414         if (buf.length() == 0) return SET_WITH_NULL_STRING; // succeed, but no remainder\r
 415         String remainder = buf.toString();\r
 416 \r
 417         // brute force approach\r
 418         // to check to make sure result is canonically equivalent\r
 419         /*\r
 420         String trial = Normalizer.normalize(UTF16.valueOf(comp) + remainder, Normalizer.DECOMP, 0);\r
 421         if (!segment.regionMatches(segmentPos, trial, 0, segment.length() - segmentPos)) return null;\r
 422         */\r
 423 \r
 424         if (0!=Normalizer.compare(UTF16.valueOf(comp) + remainder, segment.substring(segmentPos), 0)) return null;\r
 425 \r
 426         // get the remaining combinations\r
 427         return getEquivalents2(remainder);\r
 428     }\r
 429 \r
 430     /*\r
 431     // TODO: fix once we have a codepoint interface to get the canonical combining class\r
 432     // TODO: Need public access to canonical combining class in UCharacter!\r
 433     private static int getClass(int cp) {\r
 434         return Normalizer.getClass((char)cp);\r
 435     }\r
 436     */\r
 437 \r
 438    // ================= BUILDER =========================\r
 439     // TODO: Flatten this data so it doesn't have to be reconstructed each time!\r
 440 \r
 441     //private static final UnicodeSet EMPTY = new UnicodeSet(); // constant, don't change\r
 442     private static final Set<String> SET_WITH_NULL_STRING = new HashSet<String>(); // constant, don't change\r
 443     static {\r
 444         SET_WITH_NULL_STRING.add("");\r
 445     }\r
 446 \r
 447   //  private static UnicodeSet SAFE_START = new UnicodeSet();\r
 448   //  private static CharMap AT_START = new CharMap();\r
 449 \r
 450         // TODO: WARNING, NORMALIZER doesn't have supplementaries yet !!;\r
 451         // Change FFFF to 10FFFF in C, and in Java when normalizer is upgraded.\r
 452   //  private static int LAST_UNICODE = 0x10FFFF;\r
 453     /*\r
 454     static {\r
 455         buildData();\r
 456     }\r
 457     */\r
 458     /*\r
 459     private static void buildData() {\r
 460 \r
 461         if (PROGRESS) System.out.println("Getting Safe Start");\r
 462         for (int cp = 0; cp <= LAST_UNICODE; ++cp) {\r
 463             if (PROGRESS & (cp & 0x7FF) == 0) System.out.print('.');\r
 464             int cc = UCharacter.getCombiningClass(cp);\r
 465             if (cc == 0) SAFE_START.add(cp);\r
 466             // will fix to be really safe below\r
 467         }\r
 468         if (PROGRESS) System.out.println();\r
 469 \r
 470         if (PROGRESS) System.out.println("Getting Containment");\r
 471         for (int cp = 0; cp <= LAST_UNICODE; ++cp) {\r
 472             if (PROGRESS & (cp & 0x7FF) == 0) System.out.print('.');\r
 473 \r
 474             if (Normalizer.isNormalized(cp, Normalizer.NFD)) continue;\r
 475 \r
 476             //String istr = UTF16.valueOf(cp);\r
 477             String decomp = Normalizer.normalize(cp, Normalizer.NFD);\r
 478             //if (decomp.equals(istr)) continue;\r
 479 \r
 480             // add each character in the decomposition to canBeIn\r
 481 \r
 482             int component;\r
 483             for (int i = 0; i < decomp.length(); i += UTF16.getCharCount(component)) {\r
 484                 component = UTF16.charAt(decomp, i);\r
 485                 if (i == 0) {\r
 486                     AT_START.add(component, cp);\r
 487                 } else if (UCharacter.getCombiningClass(component) == 0) {\r
 488                     SAFE_START.remove(component);\r
 489                 }\r
 490             }\r
 491         }\r
 492         if (PROGRESS) System.out.println();\r
 493     }\r
 494         // the following is just for a map from characters to a set of characters\r
 495 \r
 496     private static class CharMap {\r
 497         Map storage = new HashMap();\r
 498         MutableInt probe = new MutableInt();\r
 499         boolean converted = false;\r
 500 \r
 501         public void add(int cp, int whatItIsIn) {\r
 502             UnicodeSet result = (UnicodeSet) storage.get(probe.set(cp));\r
 503             if (result == null) {\r
 504                 result = new UnicodeSet();\r
 505                 storage.put(probe, result);\r
 506             }\r
 507             result.add(whatItIsIn);\r
 508         }\r
 509 \r
 510         public UnicodeSet get(int cp) {\r
 511             return (UnicodeSet) storage.get(probe.set(cp));\r
 512         }\r
 513     }\r
 514 \r
 515     private static class MutableInt {\r
 516         public int contents;\r
 517         public int hashCode() { return contents; }\r
 518         public boolean equals(Object other) {\r
 519             return ((MutableInt)other).contents == contents;\r
 520         }\r
 521         // allows chaining\r
 522         public MutableInt set(int contents) {\r
 523             this.contents = contents;\r
 524             return this;\r
 525         }\r
 526     }\r
 527     */\r
 528 \r
 529 }\r