jars/icu4j-52_1/main/classes/core/src/com/ibm/icu/impl/PropsVectors.java

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