jars/icu4j-4_4_2-src/main/classes/core/src/com/ibm/icu/impl/PropsVectors.java

   1 /*\r
   2  ******************************************************************************\r
   3  * Copyright (C) 1996-2009, International Business Machines Corporation and   *\r
   4  * others. All Rights Reserved.                                               *\r
   5  ******************************************************************************\r
   6  */\r
   7 \r
   8 /**\r
   9  * Store bits (Unicode character properties) in bit set vectors.\r
  10  * \r
  11  * This is a port of the C++ class UPropsVectors from ICU4C\r
  12  * \r
  13  * @author Shaopeng Jia\r
  14  * @internal\r
  15  */\r
  16 \r
  17 package com.ibm.icu.impl;\r
  18 \r
  19 import java.util.Arrays;\r
  20 import java.util.Comparator;\r
  21 \r
  22 /**\r
  23  * Unicode Properties Vectors associated with code point ranges.\r
  24  * \r
  25  * Rows of primitive integers in a contiguous array store the range limits and\r
  26  * the properties vectors.\r
  27  * \r
  28  * In each row, row[0] contains the start code point and row[1] contains the\r
  29  * limit code point, which is the start of the next range.\r
  30  * \r
  31  * Initially, there is only one range [0..0x110000] with values 0.\r
  32  * \r
  33  * It would be possible to store only one range boundary per row, but\r
  34  * self-contained rows allow to later sort them by contents.\r
  35  */\r
  36 public class PropsVectors {\r
  37     private int v[];\r
  38     private int columns; // number of columns, plus two for start\r
  39     // and limit values\r
  40     private int maxRows;\r
  41     private int rows;\r
  42     private int prevRow; // search optimization: remember last row seen\r
  43     private boolean isCompacted;\r
  44 \r
  45     // internal function to compare elements in v and target. Return true iff\r
  46     // elements in v starting from index1 to index1 + length - 1 \r
  47     // are exactly the same as elements in target\r
  48     // starting from index2 to index2 + length - 1\r
  49     private boolean areElementsSame(int index1, int[] target, int index2, \r
  50             int length) {\r
  51         for (int i = 0; i < length; ++i) {\r
  52             if (v[index1 + i] != target[index2 + i]) {\r
  53                 return false;\r
  54             }\r
  55         }\r
  56         return true;\r
  57     }\r
  58     \r
  59     // internal function which given rangeStart, returns\r
  60     // index where v[index]<=rangeStart<v[index+1].\r
  61     // The returned index is a multiple of columns, and therefore\r
  62     // points to the start of a row.\r
  63     private int findRow(int rangeStart) {\r
  64         int index = 0;\r
  65 \r
  66         // check the vicinity of the last-seen row (start\r
  67         // searching with an unrolled loop)\r
  68 \r
  69         index = prevRow * columns;\r
  70         if (rangeStart >= v[index]) {\r
  71             if (rangeStart < v[index + 1]) {\r
  72                 // same row as last seen\r
  73                 return index;\r
  74             } else {\r
  75                 index += columns;\r
  76                 if (rangeStart < v[index + 1]) {\r
  77                     ++prevRow;\r
  78                     return index;\r
  79                 } else {\r
  80                     index += columns;\r
  81                     if (rangeStart < v[index + 1]) {\r
  82                         prevRow += 2;\r
  83                         return index;\r
  84                     } else if ((rangeStart - v[index + 1]) < 10) {\r
  85                         // we are close, continue looping\r
  86                         prevRow += 2;\r
  87                         do {\r
  88                             ++prevRow;\r
  89                             index += columns;\r
  90                         } while (rangeStart >= v[index + 1]);\r
  91                         return index;\r
  92                     }\r
  93                 }\r
  94             }\r
  95         } else if (rangeStart < v[1]) {\r
  96             // the very first row\r
  97             prevRow = 0;\r
  98             return 0;\r
  99         }\r
 100 \r
 101         // do a binary search for the start of the range\r
 102         int start = 0;\r
 103         int mid = 0;\r
 104         int limit = rows;\r
 105         while (start < limit - 1) {\r
 106             mid = (start + limit) / 2;\r
 107             index = columns * mid;\r
 108             if (rangeStart < v[index]) {\r
 109                 limit = mid;\r
 110             } else if (rangeStart < v[index + 1]) {\r
 111                 prevRow = mid;\r
 112                 return index;\r
 113             } else {\r
 114                 start = mid;\r
 115             }\r
 116         }\r
 117 \r
 118         // must be found because all ranges together always cover\r
 119         // all of Unicode\r
 120         prevRow = start;\r
 121         index = start * columns;\r
 122         return index;\r
 123     }\r
 124 \r
 125     /*\r
 126      * Special pseudo code points for storing the initialValue and the\r
 127      * errorValue which are used to initialize a Trie or similar.\r
 128      */\r
 129     public final static int FIRST_SPECIAL_CP = 0x110000;\r
 130     public final static int INITIAL_VALUE_CP = 0x110000;\r
 131     public final static int ERROR_VALUE_CP = 0x110001;\r
 132     public final static int MAX_CP = 0x110001;\r
 133 \r
 134     public final static int INITIAL_ROWS = 1 << 12;\r
 135     public final static int MEDIUM_ROWS = 1 << 16;\r
 136     public final static int MAX_ROWS = MAX_CP + 1;\r
 137 \r
 138     /*\r
 139      * Constructor.\r
 140      * @param numOfColumns Number of value integers (32-bit int) per row.\r
 141      */\r
 142     public PropsVectors(int numOfColumns) {\r
 143         if (numOfColumns < 1) {\r
 144             throw new IllegalArgumentException("numOfColumns need to be no "\r
 145                     + "less than 1; but it is " + numOfColumns);\r
 146         }\r
 147         columns = numOfColumns + 2; // count range start and limit columns\r
 148         v = new int[INITIAL_ROWS * columns];\r
 149         maxRows = INITIAL_ROWS;\r
 150         rows = 2 + (MAX_CP - FIRST_SPECIAL_CP);\r
 151         prevRow = 0;\r
 152         isCompacted = false;\r
 153         v[0] = 0;\r
 154         v[1] = 0x110000;\r
 155         int index = columns;\r
 156         for (int cp = FIRST_SPECIAL_CP; cp <= MAX_CP; ++cp) {\r
 157             v[index] = cp;\r
 158             v[index + 1] = cp + 1;\r
 159             index += columns;\r
 160         }\r
 161     }\r
 162 \r
 163     /*\r
 164      * In rows for code points [start..end], select the column, reset the mask\r
 165      * bits and set the value bits (ANDed with the mask).\r
 166      * \r
 167      * @throws IllegalArgumentException\r
 168      * \r
 169      * @throws IllegalStateException\r
 170      * \r
 171      * @throws IndexOutOfBoundsException\r
 172      */\r
 173     public void setValue(int start, int end, int column, int value, int mask) {\r
 174         if (start < 0 || start > end || end > MAX_CP || column < 0\r
 175                 || column >= (columns - 2)) {\r
 176             throw new IllegalArgumentException();\r
 177         }\r
 178         if (isCompacted) {\r
 179             throw new IllegalStateException("Shouldn't be called after"\r
 180                     + "compact()!");\r
 181         }\r
 182 \r
 183         int firstRow, lastRow;\r
 184         int limit = end + 1;\r
 185         boolean splitFirstRow, splitLastRow;\r
 186         // skip range start and limit columns\r
 187         column += 2;\r
 188         value &= mask;\r
 189 \r
 190         // find the rows whose ranges overlap with the input range\r
 191         // find the first and last row, always successful\r
 192         firstRow = findRow(start);\r
 193         lastRow = findRow(end);\r
 194 \r
 195         /*\r
 196          * Rows need to be split if they partially overlap with the input range\r
 197          * (only possible for the first and last rows) and if their value\r
 198          * differs from the input value.\r
 199          */\r
 200         splitFirstRow = (start != v[firstRow] && value != (v[firstRow + column] & mask));\r
 201         splitLastRow = (limit != v[lastRow + 1] && value != (v[lastRow + column] & mask));\r
 202 \r
 203         // split first/last rows if necessary\r
 204         if (splitFirstRow || splitLastRow) {\r
 205             int rowsToExpand = 0;\r
 206             if (splitFirstRow) {\r
 207                 ++rowsToExpand;\r
 208             }\r
 209             if (splitLastRow) {\r
 210                 ++rowsToExpand;\r
 211             }\r
 212             int newMaxRows = 0;\r
 213             if ((rows + rowsToExpand) > maxRows) {\r
 214                 if (maxRows < MEDIUM_ROWS) {\r
 215                     newMaxRows = MEDIUM_ROWS;\r
 216                 } else if (maxRows < MAX_ROWS) {\r
 217                     newMaxRows = MAX_ROWS;\r
 218                 } else {\r
 219                     throw new IndexOutOfBoundsException(\r
 220                             "MAX_ROWS exceeded! Increase it to a higher value" +\r
 221                             "in the implementation");\r
 222                 }\r
 223                 int[] temp = new int[newMaxRows * columns];\r
 224                 System.arraycopy(v, 0, temp, 0, rows * columns);\r
 225                 v = temp;\r
 226                 maxRows = newMaxRows;\r
 227             }\r
 228 \r
 229             // count the number of row cells to move after the last row,\r
 230             // and move them\r
 231             int count = (rows * columns) - (lastRow + columns);\r
 232             if (count > 0) {\r
 233                 System.arraycopy(v, lastRow + columns, v, lastRow\r
 234                         + (1 + rowsToExpand) * columns, count);\r
 235             }\r
 236             rows += rowsToExpand;\r
 237 \r
 238             // split the first row, and move the firstRow pointer\r
 239             // to the second part\r
 240             if (splitFirstRow) {\r
 241                 // copy all affected rows up one and move the lastRow pointer\r
 242                 count = lastRow - firstRow + columns;\r
 243                 System.arraycopy(v, firstRow, v, firstRow + columns, count);\r
 244                 lastRow += columns;\r
 245 \r
 246                 // split the range and move the firstRow pointer\r
 247                 v[firstRow + 1] = v[firstRow + columns] = start;\r
 248                 firstRow += columns;\r
 249             }\r
 250 \r
 251             // split the last row\r
 252             if (splitLastRow) {\r
 253                 // copy the last row data\r
 254                 System.arraycopy(v, lastRow, v, lastRow + columns, columns);\r
 255 \r
 256                 // split the range and move the firstRow pointer\r
 257                 v[lastRow + 1] = v[lastRow + columns] = limit;\r
 258             }\r
 259         }\r
 260 \r
 261         // set the "row last seen" to the last row for the range\r
 262         prevRow = lastRow / columns;\r
 263 \r
 264         // set the input value in all remaining rows\r
 265         firstRow += column;\r
 266         lastRow += column;\r
 267         mask = ~mask;\r
 268         for (;;) {\r
 269             v[firstRow] = (v[firstRow] & mask) | value;\r
 270             if (firstRow == lastRow) {\r
 271                 break;\r
 272             }\r
 273             firstRow += columns;\r
 274         }\r
 275     }\r
 276 \r
 277     /*\r
 278      * Always returns 0 if called after compact().\r
 279      */\r
 280     public int getValue(int c, int column) {\r
 281         if (isCompacted || c < 0 || c > MAX_CP || column < 0\r
 282                 || column >= (columns - 2)) {\r
 283             return 0;\r
 284         }\r
 285         int index = findRow(c);\r
 286         return v[index + 2 + column];\r
 287     }\r
 288 \r
 289     /*\r
 290      * Returns an array which contains value elements\r
 291      * in row rowIndex. \r
 292      *\r
 293      * @throws IllegalStateException\r
 294      * @throws IllegalArgumentException\r
 295      */\r
 296     public int[] getRow(int rowIndex) {\r
 297         if (isCompacted) {\r
 298             throw new IllegalStateException(\r
 299                     "Illegal Invocation of the method after compact()");\r
 300         }\r
 301         if (rowIndex < 0 || rowIndex > rows) {\r
 302             throw new IllegalArgumentException("rowIndex out of bound!");\r
 303         }\r
 304         int[] rowToReturn = new int[columns - 2];\r
 305         System.arraycopy(v, rowIndex * columns + 2, rowToReturn, 0,\r
 306                          columns - 2);\r
 307         return rowToReturn;\r
 308     }\r
 309 \r
 310     /*\r
 311      * Returns an int which is the start codepoint\r
 312      * in row rowIndex.\r
 313      * \r
 314      * @throws IllegalStateException\r
 315      * \r
 316      * @throws IllegalArgumentException\r
 317      */\r
 318     public int getRowStart(int rowIndex) {\r
 319         if (isCompacted) {\r
 320             throw new IllegalStateException(\r
 321                     "Illegal Invocation of the method after compact()");\r
 322         }\r
 323         if (rowIndex < 0 || rowIndex > rows) {\r
 324             throw new IllegalArgumentException("rowIndex out of bound!");\r
 325         }\r
 326         return v[rowIndex * columns];\r
 327     }\r
 328 \r
 329     /*\r
 330      * Returns an int which is the limit codepoint \r
 331      * minus 1 in row rowIndex.\r
 332      * \r
 333      * @throws IllegalStateException\r
 334      * \r
 335      * @throws IllegalArgumentException\r
 336      */\r
 337     public int getRowEnd(int rowIndex) {\r
 338         if (isCompacted) {\r
 339             throw new IllegalStateException(\r
 340                     "Illegal Invocation of the method after compact()");\r
 341         }\r
 342         if (rowIndex < 0 || rowIndex > rows) {\r
 343             throw new IllegalArgumentException("rowIndex out of bound!");\r
 344         }\r
 345         return v[rowIndex * columns + 1] - 1;\r
 346     }\r
 347     \r
 348     /*\r
 349      * Compact the vectors:\r
 350      * - modify the memory\r
 351      * - keep only unique vectors\r
 352      * - store them contiguously from the beginning of the memory\r
 353      * - for each (non-unique) row, call the respective function in \r
 354      *   CompactHandler\r
 355      *\r
 356      * The handler's rowIndex is the index of the row in the compacted\r
 357      * memory block. Therefore, it starts at 0 increases in increments of the \r
 358      * columns value.\r
 359      *\r
 360      * In a first phase, only special values are delivered (each exactly once).\r
 361      * Then CompactHandler::startRealValues() is called\r
 362      * where rowIndex is the length of the compacted array.\r
 363      * Then, in the second phase, the CompactHandler::setRowIndexForRange() is \r
 364      * called for each row of real values.\r
 365      */\r
 366     public void compact(CompactHandler compactor) {\r
 367         if (isCompacted) {\r
 368             return;\r
 369         }\r
 370 \r
 371         // Set the flag now: Sorting and compacting destroys the builder\r
 372         // data structure.\r
 373         isCompacted = true;\r
 374         int valueColumns = columns - 2; // not counting start & limit\r
 375 \r
 376         // sort the properties vectors to find unique vector values\r
 377         Integer[] indexArray = new Integer[rows];\r
 378         for (int i = 0; i < rows; ++i) {\r
 379             indexArray[i] = new Integer(columns * i);\r
 380         }\r
 381 \r
 382         Arrays.sort(indexArray, new Comparator<Integer>() {\r
 383             public int compare(Integer o1, Integer o2) {\r
 384                 int indexOfRow1 = o1.intValue();\r
 385                 int indexOfRow2 = o2.intValue();\r
 386                 int count = columns; // includes start/limit columns\r
 387 \r
 388                 // start comparing after start/limit\r
 389                 // but wrap around to them\r
 390                 int index = 2;\r
 391                 do {\r
 392                     if (v[indexOfRow1 + index] != v[indexOfRow2 + index]) {\r
 393                         return v[indexOfRow1 + index] < v[indexOfRow2 + index] ? -1\r
 394                                 : 1;\r
 395                     }\r
 396                     if (++index == columns) {\r
 397                         index = 0;\r
 398                     }\r
 399                 } while (--count > 0);\r
 400 \r
 401                 return 0;\r
 402             }\r
 403         });\r
 404 \r
 405         /*\r
 406          * Find and set the special values. This has to do almost the same work\r
 407          * as the compaction below, to find the indexes where the special-value\r
 408          * rows will move.\r
 409          */\r
 410         int count = -valueColumns;\r
 411         for (int i = 0; i < rows; ++i) {\r
 412             int start = v[indexArray[i].intValue()];\r
 413 \r
 414             // count a new values vector if it is different\r
 415             // from the current one\r
 416             if (count < 0 || !areElementsSame(indexArray[i].intValue() + 2, v,\r
 417                     indexArray[i-1].intValue() + 2, valueColumns)) {\r
 418                 count += valueColumns;\r
 419             }\r
 420 \r
 421             if (start == INITIAL_VALUE_CP) {\r
 422                 compactor.setRowIndexForInitialValue(count);\r
 423             } else if (start == ERROR_VALUE_CP) {\r
 424                 compactor.setRowIndexForErrorValue(count);\r
 425             }\r
 426         }\r
 427 \r
 428         // count is at the beginning of the last vector,\r
 429         // add valueColumns to include that last vector\r
 430         count += valueColumns;\r
 431 \r
 432         // Call the handler once more to signal the start of\r
 433         // delivering real values.\r
 434         compactor.startRealValues(count);\r
 435 \r
 436         /*\r
 437          * Move vector contents up to a contiguous array with only unique \r
 438          * vector values, and call the handler function for each vector.\r
 439          * \r
 440          * This destroys the Properties Vector structure and replaces it \r
 441          * with an array of just vector values.\r
 442          */\r
 443         int[] temp = new int[count];\r
 444         count = -valueColumns;\r
 445         for (int i = 0; i < rows; ++i) {\r
 446             int start = v[indexArray[i].intValue()];\r
 447             int limit = v[indexArray[i].intValue() + 1];\r
 448 \r
 449             // count a new values vector if it is different\r
 450             // from the current one\r
 451             if (count < 0 || !areElementsSame(indexArray[i].intValue() + 2, \r
 452                     temp, count, valueColumns)) {\r
 453                 count += valueColumns;\r
 454                 System.arraycopy(v, indexArray[i].intValue() + 2, temp, count,\r
 455                         valueColumns);\r
 456             }\r
 457 \r
 458             if (start < FIRST_SPECIAL_CP) {\r
 459                 compactor.setRowIndexForRange(start, limit - 1, count);\r
 460             }\r
 461         }\r
 462         v = temp;\r
 463         \r
 464         // count is at the beginning of the last vector,\r
 465         // add one to include that last vector\r
 466         rows = count / valueColumns + 1;\r
 467     }\r
 468 \r
 469     /*\r
 470      * Get the vectors array after calling compact().\r
 471      * \r
 472      * @throws IllegalStateException\r
 473      */\r
 474     public int[] getCompactedArray() {\r
 475         if (!isCompacted) {\r
 476             throw new IllegalStateException(\r
 477                     "Illegal Invocation of the method before compact()");\r
 478         }\r
 479         return v;\r
 480     }\r
 481 \r
 482     /*\r
 483      * Get the number of rows for the compacted array.\r
 484      * \r
 485      * @throws IllegalStateException\r
 486      */\r
 487     public int getCompactedRows() {\r
 488         if (!isCompacted) {\r
 489             throw new IllegalStateException(\r
 490                     "Illegal Invocation of the method before compact()");\r
 491         }\r
 492         return rows;\r
 493     }\r
 494 \r
 495     /*\r
 496      * Get the number of columns for the compacted array.\r
 497      * \r
 498      * @throws IllegalStateException\r
 499      */\r
 500     public int getCompactedColumns() {\r
 501         if (!isCompacted) {\r
 502             throw new IllegalStateException(\r
 503                     "Illegal Invocation of the method before compact()");\r
 504         }\r
 505         return columns - 2;\r
 506     }\r
 507 \r
 508     /*\r
 509      * Call compact(), create a IntTrie with indexes into the compacted\r
 510      * vectors array.\r
 511      */\r
 512     public IntTrie compactToTrieWithRowIndexes() {\r
 513         PVecToTrieCompactHandler compactor = new PVecToTrieCompactHandler();\r
 514         compact(compactor);\r
 515         return compactor.builder.serialize(new DefaultGetFoldedValue(\r
 516                 compactor.builder), new DefaultGetFoldingOffset());\r
 517     }\r
 518 \r
 519     // inner class implementation of Trie.DataManipulate\r
 520     private static class DefaultGetFoldingOffset implements Trie.DataManipulate {\r
 521         public int getFoldingOffset(int value) {\r
 522             return value;\r
 523         }\r
 524     }\r
 525 \r
 526     // inner class implementation of TrieBuilder.DataManipulate\r
 527     private static class DefaultGetFoldedValue implements\r
 528             TrieBuilder.DataManipulate {\r
 529         private IntTrieBuilder builder;\r
 530 \r
 531         public DefaultGetFoldedValue(IntTrieBuilder inBuilder) {\r
 532             builder = inBuilder;\r
 533         }\r
 534 \r
 535         public int getFoldedValue(int start, int offset) {\r
 536             int initialValue = builder.m_initialValue_; \r
 537             int limit = start + 0x400;\r
 538             while (start < limit) {\r
 539                 boolean[] inBlockZero = new boolean[1];\r
 540                 int value = builder.getValue(start, inBlockZero);\r
 541                 if (inBlockZero[0]) {\r
 542                     start += TrieBuilder.DATA_BLOCK_LENGTH;\r
 543                 } else if (value != initialValue) {\r
 544                     return offset;\r
 545                 } else {\r
 546                     ++start;\r
 547                 }\r
 548             }\r
 549             return 0;\r
 550         }\r
 551     }\r
 552     \r
 553     public static interface CompactHandler {\r
 554         public void setRowIndexForRange(int start, int end, int rowIndex);\r
 555         public void setRowIndexForInitialValue(int rowIndex);\r
 556         public void setRowIndexForErrorValue(int rowIndex);\r
 557         public void startRealValues(int rowIndex);\r
 558     }\r
 559 }