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

   1 /*
   2  *******************************************************************************
   3  * Copyright (C) 2009, International Business Machines Corporation and         *
   4  * others. All Rights Reserved.                                                *
   5  *******************************************************************************
   6  */
   7 package com.ibm.icu.impl;
   8
   9 /**
  10  * @author aheninger
  11  *
  12  * A Trie2Writable is a modifiable, or build-time Trie2.
  13  * Functions for reading data from the Trie are all from class Trie2.
  14  *
  15  */
  16 public class Trie2Writable extends Trie2 {
  17
  18
  19     /**
  20      * Create a new, empty, writable Trie2. 32-bit data values are used.
  21      *
  22      * @param initialValueP the initial value that is set for all code points
  23      * @param errorValueP the value for out-of-range code points and illegal UTF-8
  24      */
  25     public  Trie2Writable(int initialValueP, int errorValueP) {
  26         // This constructor corresponds to utrie2_open() in ICU4C.
  27         init(initialValueP, errorValueP);
  28     }
  29
  30
  31     private void init(int initialValueP, int errorValueP) {
  32         this.initialValue = initialValueP;
  33         this.errorValue   = errorValueP;
  34         this.highStart    = 0x110000;
  35
  36         this.data           = new int[UNEWTRIE2_INITIAL_DATA_LENGTH];
  37         this.dataCapacity   = UNEWTRIE2_INITIAL_DATA_LENGTH;
  38         this.initialValue   = initialValueP;
  39         this.errorValue     = errorValueP;
  40         this.highStart      = 0x110000;
  41         this.firstFreeBlock = 0;  /* no free block in the list */
  42         this.isCompacted    = false;
  43
  44         /*
  45          * preallocate and reset
  46          * - ASCII
  47          * - the bad-UTF-8-data block
  48          * - the null data block
  49          */
  50         int i, j;
  51         for(i=0; i<0x80; ++i) {
  52             data[i] = initialValue;
  53         }
  54         for(; i<0xc0; ++i) {
  55             data[i] = errorValue;
  56         }
  57         for(i=UNEWTRIE2_DATA_NULL_OFFSET; i<UNEWTRIE2_DATA_START_OFFSET; ++i) {
  58             data[i] = initialValue;
  59         }
  60         dataNullOffset = UNEWTRIE2_DATA_NULL_OFFSET;
  61         dataLength     = UNEWTRIE2_DATA_START_OFFSET;
  62
  63         /* set the index-2 indexes for the 2=0x80>>UTRIE2_SHIFT_2 ASCII data blocks */
  64         for(i=0, j=0; j<0x80; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) {
  65             index2[i]=j;
  66             map[i]=1;
  67         }
  68
  69         /* reference counts for the bad-UTF-8-data block */
  70         for(; j<0xc0; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) {
  71             map[i]=0;
  72         }
  73
  74         /*
  75          * Reference counts for the null data block: all blocks except for the ASCII blocks.
  76          * Plus 1 so that we don't drop this block during compaction.
  77          * Plus as many as needed for lead surrogate code points.
  78          */
  79         /* i==newTrie->dataNullOffset */
  80         map[i++] =
  81             (0x110000>>UTRIE2_SHIFT_2) -
  82             (0x80>>UTRIE2_SHIFT_2) +
  83             1 +
  84             UTRIE2_LSCP_INDEX_2_LENGTH;
  85         j += UTRIE2_DATA_BLOCK_LENGTH;
  86         for(; j<UNEWTRIE2_DATA_START_OFFSET; ++i, j+=UTRIE2_DATA_BLOCK_LENGTH) {
  87             map[i]=0;
  88         }
  89
  90         /*
  91          * set the remaining indexes in the BMP index-2 block
  92          * to the null data block
  93          */
  94         for(i=0x80>>UTRIE2_SHIFT_2; i<UTRIE2_INDEX_2_BMP_LENGTH; ++i) {
  95             index2[i]=UNEWTRIE2_DATA_NULL_OFFSET;
  96         }
  97
  98         /*
  99          * Fill the index gap with impossible values so that compaction
 100          * does not overlap other index-2 blocks with the gap.
 101          */
 102         for(i=0; i<UNEWTRIE2_INDEX_GAP_LENGTH; ++i) {
 103             index2[UNEWTRIE2_INDEX_GAP_OFFSET+i]=-1;
 104         }
 105
 106         /* set the indexes in the null index-2 block */
 107         for(i=0; i<UTRIE2_INDEX_2_BLOCK_LENGTH; ++i) {
 108             index2[UNEWTRIE2_INDEX_2_NULL_OFFSET+i]=UNEWTRIE2_DATA_NULL_OFFSET;
 109         }
 110         index2NullOffset=UNEWTRIE2_INDEX_2_NULL_OFFSET;
 111         index2Length=UNEWTRIE2_INDEX_2_START_OFFSET;
 112
 113         /* set the index-1 indexes for the linear index-2 block */
 114         for(i=0, j=0;
 115             i<UTRIE2_OMITTED_BMP_INDEX_1_LENGTH;
 116             ++i, j+=UTRIE2_INDEX_2_BLOCK_LENGTH
 117         ) {
 118             index1[i]=j;
 119         }
 120
 121         /* set the remaining index-1 indexes to the null index-2 block */
 122         for(; i<UNEWTRIE2_INDEX_1_LENGTH; ++i) {
 123             index1[i]=UNEWTRIE2_INDEX_2_NULL_OFFSET;
 124         }
 125
 126         /*
 127          * Preallocate and reset data for U+0080..U+07ff,
 128          * for 2-byte UTF-8 which will be compacted in 64-blocks
 129          * even if UTRIE2_DATA_BLOCK_LENGTH is smaller.
 130          */
 131         for(i=0x80; i<0x800; i+=UTRIE2_DATA_BLOCK_LENGTH) {
 132             set(i, initialValue);
 133         }
 134
 135     }
 136
 137
 138     /**
 139      * Create a new build time (modifiable) Trie2 whose contents are the same as the source Trie2.
 140      *
 141      * @param source the source Trie2.  Its contents will be copied into the new Trie2.
 142      */
 143     public Trie2Writable(Trie2 source) {
 144         init(source.initialValue, source.errorValue);
 145
 146         for (Range r: source) {
 147             setRange(r, true);
 148         }
 149     }
 150
 151
 152     private boolean isInNullBlock(int c, boolean forLSCP) {
 153         int i2, block;
 154
 155         if(Character.isHighSurrogate((char)c) && forLSCP) {
 156             i2=(UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2))+
 157                 (c>>UTRIE2_SHIFT_2);
 158         } else {
 159             i2=index1[c>>UTRIE2_SHIFT_1]+
 160                 ((c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK);
 161         }
 162         block=index2[i2];
 163         return (block==dataNullOffset);
 164     }
 165
 166     private int allocIndex2Block() {
 167         int newBlock, newTop;
 168
 169         newBlock=index2Length;
 170         newTop=newBlock+UTRIE2_INDEX_2_BLOCK_LENGTH;
 171         if(newTop > index2.length) {
 172             throw new IllegalStateException("Internal error in Trie2 creation.");
 173             /*
 174              * Should never occur.
 175              * Either UTRIE2_MAX_BUILD_TIME_INDEX_LENGTH is incorrect,
 176              * or the code writes more values than should be possible.
 177              */
 178         }
 179         index2Length=newTop;
 180         System.arraycopy(index2, index2NullOffset, index2, newBlock, UTRIE2_INDEX_2_BLOCK_LENGTH);
 181         return newBlock;
 182     }
 183
 184     private int getIndex2Block(int c, boolean forLSCP) {
 185         int i1, i2;
 186
 187         if(c>=0xd800 && c<0xdc00 && forLSCP) {
 188             return UTRIE2_LSCP_INDEX_2_OFFSET;
 189         }
 190
 191         i1=c>>UTRIE2_SHIFT_1;
 192         i2=index1[i1];
 193         if(i2==index2NullOffset) {
 194             i2=allocIndex2Block();
 195             index1[i1]=i2;
 196         }
 197         return i2;
 198     }
 199
 200     private int allocDataBlock(int copyBlock) {
 201         int newBlock, newTop;
 202
 203         if(firstFreeBlock!=0) {
 204             /* get the first free block */
 205             newBlock=firstFreeBlock;
 206             firstFreeBlock=-map[newBlock>>UTRIE2_SHIFT_2];
 207         } else {
 208             /* get a new block from the high end */
 209             newBlock=dataLength;
 210             newTop=newBlock+UTRIE2_DATA_BLOCK_LENGTH;
 211             if(newTop>dataCapacity) {
 212                 /* out of memory in the data array */
 213                 int capacity;
 214                 int[] newData;
 215
 216                 if(dataCapacity<UNEWTRIE2_MEDIUM_DATA_LENGTH) {
 217                     capacity=UNEWTRIE2_MEDIUM_DATA_LENGTH;
 218                 } else if(dataCapacity<UNEWTRIE2_MAX_DATA_LENGTH) {
 219                     capacity=UNEWTRIE2_MAX_DATA_LENGTH;
 220                 } else {
 221                     /*
 222                      * Should never occur.
 223                      * Either UNEWTRIE2_MAX_DATA_LENGTH is incorrect,
 224                      * or the code writes more values than should be possible.
 225                      */
 226                     throw new IllegalStateException("Internal error in Trie2 creation.");
 227                 }
 228                 newData = new int[capacity];
 229                 System.arraycopy(data, 0, newData, 0, dataLength);
 230                 data=newData;
 231                 dataCapacity=capacity;
 232             }
 233             dataLength=newTop;
 234         }
 235         System.arraycopy(data, copyBlock, data, newBlock, UTRIE2_DATA_BLOCK_LENGTH);
 236         map[newBlock>>UTRIE2_SHIFT_2]=0;
 237         return newBlock;
 238     }
 239
 240
 241     /* call when the block's reference counter reaches 0 */
 242     private void releaseDataBlock(int block) {
 243         /* put this block at the front of the free-block chain */
 244         map[block>>UTRIE2_SHIFT_2]=-firstFreeBlock;
 245         firstFreeBlock=block;
 246     }
 247
 248
 249     private boolean isWritableBlock(int block) {
 250         return (block!=dataNullOffset && 1==map[block>>UTRIE2_SHIFT_2]);
 251     }
 252
 253     private void setIndex2Entry(int i2, int block) {
 254         int oldBlock;
 255         ++map[block>>UTRIE2_SHIFT_2];  /* increment first, in case block==oldBlock! */
 256         oldBlock=index2[i2];
 257         if(0 == --map[oldBlock>>UTRIE2_SHIFT_2]) {
 258             releaseDataBlock(oldBlock);
 259         }
 260         index2[i2]=block;
 261     }
 262
 263
 264     /**
 265      * No error checking for illegal arguments.
 266      *
 267      * @internal
 268      */
 269     private int getDataBlock(int c, boolean forLSCP) {
 270         int i2, oldBlock, newBlock;
 271
 272         i2=getIndex2Block(c, forLSCP);
 273
 274         i2+=(c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK;
 275         oldBlock=index2[i2];
 276         if(isWritableBlock(oldBlock)) {
 277             return oldBlock;
 278         }
 279
 280         /* allocate a new data block */
 281         newBlock=allocDataBlock(oldBlock);
 282         setIndex2Entry(i2, newBlock);
 283         return newBlock;
 284     }
 285     /**
 286      * Set a value for a code point.
 287      *
 288      * @param c the code point
 289      * @param value the value
 290      */
 291     public Trie2Writable set(int c, int value) {
 292         if (c<0 || c>0x10ffff) {
 293             throw new IllegalArgumentException("Invalid code point.");
 294         }
 295         set(c, true, value);
 296         fHash = 0;
 297         return this;
 298     }
 299
 300     private Trie2Writable set(int c, boolean forLSCP, int value) {
 301         int block;
 302         if (isCompacted) {
 303             uncompact();
 304         }
 305         block = getDataBlock(c, forLSCP);
 306         data[block + (c&UTRIE2_DATA_MASK)] = value;
 307         return this;
 308     }
 309
 310
 311     /*
 312      * Uncompact a compacted Trie2Writable.
 313      * This is needed if a the WritableTrie2 was compacted in preparation for creating a read-only
 314      * Trie2, and then is subsequently altered.
 315      *
 316      * The structure is a bit awkward - it would be cleaner to leave the original
 317      * Trie2 unaltered - but compacting in place was taken directly from the ICU4C code.
 318      *
 319      * The approach is to create a new (uncompacted) Trie2Writable from this one, then transfer
 320      * the guts from the new to the old.
 321      */
 322     private void uncompact() {
 323         Trie2Writable tempTrie = new Trie2Writable(this);
 324
 325         // Members from Trie2Writable
 326         this.index1       = tempTrie.index1;
 327         this.index2       = tempTrie.index2;
 328         this.data         = tempTrie.data;
 329         this.index2Length = tempTrie.index2Length;
 330         this.dataCapacity = tempTrie.dataCapacity;
 331         this.isCompacted  = tempTrie.isCompacted;
 332
 333         // Members From Trie2
 334         this.header           = tempTrie.header;
 335         this.index            = tempTrie.index;
 336         this.data16           = tempTrie.data16;
 337         this.data32           = tempTrie.data32;
 338         this.indexLength      = tempTrie.indexLength;
 339         this.dataLength       = tempTrie.dataLength;
 340         this.index2NullOffset = tempTrie.index2NullOffset;
 341         this.initialValue     = tempTrie.initialValue;
 342         this.errorValue       = tempTrie.errorValue;
 343         this.highStart        = tempTrie.highStart;
 344         this.highValueIndex   = tempTrie.highValueIndex;
 345         this.dataNullOffset   = tempTrie.dataNullOffset;
 346     }
 347
 348
 349     private void writeBlock(int  block, int value) {
 350         int  limit=block+UTRIE2_DATA_BLOCK_LENGTH;
 351         while(block<limit) {
 352             data[block++]=value;
 353         }
 354     }
 355
 356     /**
 357      * initialValue is ignored if overwrite=TRUE
 358      * @internal
 359      */
 360     private void fillBlock(int block, /*UChar32*/ int start, /*UChar32*/ int limit,
 361               int value, int initialValue, boolean overwrite) {
 362         int i;
 363         int pLimit = block+limit;
 364         if(overwrite) {
 365             for (i=block+start; i<pLimit; i++) {
 366                 data[i] = value;
 367             }
 368         } else {
 369             for (i=block+start; i<pLimit; i++) {
 370                 if(data[i]==initialValue) {
 371                     data[i]=value;
 372                 }
 373             }
 374         }
 375     }
 376
 377     /**
 378      * Set a value in a range of code points [start..end].
 379      * All code points c with start<=c<=end will get the value if
 380      * overwrite is TRUE or if the old value is the initial value.
 381      *
 382      * @param start the first code point to get the value
 383      * @param end the last code point to get the value (inclusive)
 384      * @param value the value
 385      * @param overwrite flag for whether old non-initial values are to be overwritten
 386      */
 387      public Trie2Writable setRange(int start, int end,
 388                            int value, boolean overwrite) {
 389          /*
 390           * repeat value in [start..end]
 391           * mark index values for repeat-data blocks by setting bit 31 of the index values
 392           * fill around existing values if any, if(overwrite)
 393           */
 394          int block, rest, repeatBlock;
 395          int /*UChar32*/ limit;
 396
 397          if(start>0x10ffff || start<0 || end>0x10ffff || end<0 || start>end) {
 398              throw new IllegalArgumentException("Invalid code point range.");
 399          }
 400          if(!overwrite && value==initialValue) {
 401              return this; /* nothing to do */
 402          }
 403          fHash = 0;
 404          if(isCompacted) {
 405              this.uncompact();
 406          }
 407
 408          limit=end+1;
 409          if((start&UTRIE2_DATA_MASK) != 0) {
 410              int  /*UChar32*/ nextStart;
 411
 412              /* set partial block at [start..following block boundary[ */
 413              block=getDataBlock(start, true);
 414
 415              nextStart=(start+UTRIE2_DATA_BLOCK_LENGTH)&~UTRIE2_DATA_MASK;
 416              if(nextStart<=limit) {
 417                  fillBlock(block, start&UTRIE2_DATA_MASK, UTRIE2_DATA_BLOCK_LENGTH,
 418                            value, initialValue, overwrite);
 419                  start=nextStart;
 420              } else {
 421                  fillBlock(block, start&UTRIE2_DATA_MASK, limit&UTRIE2_DATA_MASK,
 422                            value, initialValue, overwrite);
 423                  return this;
 424              }
 425          }
 426
 427          /* number of positions in the last, partial block */
 428          rest=limit&UTRIE2_DATA_MASK;
 429
 430          /* round down limit to a block boundary */
 431          limit&=~UTRIE2_DATA_MASK;
 432
 433          /* iterate over all-value blocks */
 434          if(value==initialValue) {
 435              repeatBlock=dataNullOffset;
 436          } else {
 437              repeatBlock=-1;
 438          }
 439
 440          while(start<limit) {
 441              int i2;
 442              boolean setRepeatBlock=false;
 443
 444              if(value==initialValue && isInNullBlock(start, true)) {
 445                  start+=UTRIE2_DATA_BLOCK_LENGTH; /* nothing to do */
 446                  continue;
 447              }
 448
 449              /* get index value */
 450              i2=getIndex2Block(start, true);
 451              i2+=(start>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK;
 452              block=index2[i2];
 453              if(isWritableBlock(block)) {
 454                  /* already allocated */
 455                  if(overwrite && block>=UNEWTRIE2_DATA_0800_OFFSET) {
 456                      /*
 457                       * We overwrite all values, and it's not a
 458                       * protected (ASCII-linear or 2-byte UTF-8) block:
 459                       * replace with the repeatBlock.
 460                       */
 461                      setRepeatBlock=true;
 462                  } else {
 463                      /* !overwrite, or protected block: just write the values into this block */
 464                      fillBlock(block,
 465                                0, UTRIE2_DATA_BLOCK_LENGTH,
 466                                value, initialValue, overwrite);
 467                  }
 468              } else if(data[block]!=value && (overwrite || block==dataNullOffset)) {
 469                  /*
 470                   * Set the repeatBlock instead of the null block or previous repeat block:
 471                   *
 472                   * If !isWritableBlock() then all entries in the block have the same value
 473                   * because it's the null block or a range block (the repeatBlock from a previous
 474                   * call to utrie2_setRange32()).
 475                   * No other blocks are used multiple times before compacting.
 476                   *
 477                   * The null block is the only non-writable block with the initialValue because
 478                   * of the repeatBlock initialization above. (If value==initialValue, then
 479                   * the repeatBlock will be the null data block.)
 480                   *
 481                   * We set our repeatBlock if the desired value differs from the block's value,
 482                   * and if we overwrite any data or if the data is all initial values
 483                   * (which is the same as the block being the null block, see above).
 484                   */
 485                  setRepeatBlock=true;
 486              }
 487              if(setRepeatBlock) {
 488                  if(repeatBlock>=0) {
 489                      setIndex2Entry(i2, repeatBlock);
 490                  } else {
 491                      /* create and set and fill the repeatBlock */
 492                      repeatBlock=getDataBlock(start, true);
 493                      writeBlock(repeatBlock, value);
 494                  }
 495              }
 496
 497              start+=UTRIE2_DATA_BLOCK_LENGTH;
 498          }
 499
 500          if(rest>0) {
 501              /* set partial block at [last block boundary..limit[ */
 502              block=getDataBlock(start, true);
 503              fillBlock(block, 0, rest, value, initialValue, overwrite);
 504          }
 505
 506          return this;
 507      }
 508
 509      /**
 510       * Set the values from a Trie2.Range.
 511       *
 512       * All code points within the range will get the value if
 513       * overwrite is TRUE or if the old value is the initial value.
 514       *
 515       * Ranges with the lead surrogate flag set will set the alternate
 516       * lead-surrogate values in the Trie, rather than the code point values.
 517       *
 518       * This function is intended to work with the ranges produced when iterating
 519       * the contents of a source Trie.
 520       *
 521       * @param range contains the range of code points and the value to be set.
 522       * @param overwrite flag for whether old non-initial values are to be overwritten
 523       */
 524       public Trie2Writable setRange(Trie2.Range range, boolean overwrite) {
 525           fHash = 0;
 526           if (range.leadSurrogate) {
 527               for (int c=range.startCodePoint; c<=range.endCodePoint; c++) {
 528                   if (overwrite || getFromU16SingleLead((char)c) == this.initialValue)  {
 529                       setForLeadSurrogateCodeUnit((char)c, range.value);
 530                   }
 531               }
 532           } else {
 533               setRange(range.startCodePoint, range.endCodePoint, range.value, overwrite);
 534           }
 535           return this;
 536       }
 537
 538      /**
 539       * Set a value for a UTF-16 code unit.
 540       * Note that a Trie2 stores separate values for
 541       * supplementary code points in the lead surrogate range
 542       * (accessed via the plain set() and get() interfaces)
 543       * and for lead surrogate code units.
 544       *
 545       * The lead surrogate code unit values are set via this function and
 546       * read by the function getFromU16SingleLead().
 547       *
 548       * For code units outside of the lead surrogate range, this function
 549       * behaves identically to set().
 550       *
 551       * @param codeUnit A UTF-16 code unit.
 552       * @param value the value to be stored in the Trie2.
 553       */
 554      public Trie2Writable setForLeadSurrogateCodeUnit(char codeUnit, int value) {
 555          fHash = 0;
 556          set(codeUnit, false, value);
 557          return this;
 558      }
 559
 560
 561      /**
 562       * Get the value for a code point as stored in the Trie2.
 563       *
 564       * @param codePoint the code point
 565       * @return the value
 566       */
 567     @Override
 568     public int get(int codePoint) {
 569         if (codePoint<0 || codePoint>0x10ffff) {
 570             return errorValue;
 571         } else {
 572             return get(codePoint, true);
 573         }
 574     }
 575
 576
 577     private int get(int c, boolean fromLSCP) {
 578         int i2, block;
 579
 580         if(c>=highStart && (!(c>=0xd800 && c<0xdc00) || fromLSCP)) {
 581             return data[dataLength-UTRIE2_DATA_GRANULARITY];
 582         }
 583
 584         if((c>=0xd800 && c<0xdc00) && fromLSCP) {
 585             i2=(UTRIE2_LSCP_INDEX_2_OFFSET-(0xd800>>UTRIE2_SHIFT_2))+
 586                 (c>>UTRIE2_SHIFT_2);
 587         } else {
 588             i2=index1[c>>UTRIE2_SHIFT_1]+
 589                 ((c>>UTRIE2_SHIFT_2)&UTRIE2_INDEX_2_MASK);
 590         }
 591         block=index2[i2];
 592         return data[block+(c&UTRIE2_DATA_MASK)];
 593     }
 594
 595     /**
 596      * Get a trie value for a UTF-16 code unit.
 597      *
 598      * This function returns the same value as get() if the input
 599      * character is outside of the lead surrogate range
 600      *
 601      * There are two values stored in a Trie for inputs in the lead
 602      * surrogate range.  This function returns the alternate value,
 603      * while Trie2.get() returns the main value.
 604      *
 605      * @param c the code point or lead surrogate value.
 606      * @return the value
 607      */
 608     @Override
 609     public int getFromU16SingleLead(char c) {
 610         return get(c, false);
 611     }
 612
 613     /* compaction --------------------------------------------------------------- */
 614
 615     private boolean equal_int(int[] a, int s, int t, int length) {
 616         for (int i=0; i<length; i++) {
 617             if (a[s+i] != a[t+i]) {
 618                 return false;
 619             }
 620         }
 621         return true;
 622     }
 623
 624
 625     private int findSameIndex2Block(int index2Length, int otherBlock) {
 626         int block;
 627
 628         /* ensure that we do not even partially get past index2Length */
 629         index2Length-=UTRIE2_INDEX_2_BLOCK_LENGTH;
 630
 631         for(block=0; block<=index2Length; ++block) {
 632             if(equal_int(index2, block, otherBlock, UTRIE2_INDEX_2_BLOCK_LENGTH)) {
 633                 return block;
 634             }
 635         }
 636         return -1;
 637     }
 638
 639
 640     private int findSameDataBlock(int dataLength, int otherBlock, int blockLength) {
 641         int block;
 642
 643         /* ensure that we do not even partially get past dataLength */
 644         dataLength-=blockLength;
 645
 646         for(block=0; block<=dataLength; block+=UTRIE2_DATA_GRANULARITY) {
 647             if(equal_int(data, block, otherBlock, blockLength)) {
 648                 return block;
 649             }
 650         }
 651         return -1;
 652     }
 653
 654     /*
 655      * Find the start of the last range in the trie by enumerating backward.
 656      * Indexes for supplementary code points higher than this will be omitted.
 657      */
 658     private int findHighStart(int highValue) {
 659
 660         int value;
 661         int c, prev;
 662         int i1, i2, j, i2Block, prevI2Block, block, prevBlock;
 663
 664
 665         /* set variables for previous range */
 666         if(highValue==initialValue) {
 667             prevI2Block=index2NullOffset;
 668             prevBlock=dataNullOffset;
 669         } else {
 670             prevI2Block=-1;
 671             prevBlock=-1;
 672         }
 673         prev=0x110000;
 674
 675         /* enumerate index-2 blocks */
 676         i1=UNEWTRIE2_INDEX_1_LENGTH;
 677         c=prev;
 678         while(c>0) {
 679             i2Block=index1[--i1];
 680             if(i2Block==prevI2Block) {
 681                 /* the index-2 block is the same as the previous one, and filled with highValue */
 682                 c-=UTRIE2_CP_PER_INDEX_1_ENTRY;
 683                 continue;
 684             }
 685             prevI2Block=i2Block;
 686             if(i2Block==index2NullOffset) {
 687                 /* this is the null index-2 block */
 688                 if(highValue!=initialValue) {
 689                     return c;
 690                 }
 691                 c-=UTRIE2_CP_PER_INDEX_1_ENTRY;
 692             } else {
 693                 /* enumerate data blocks for one index-2 block */
 694                 for(i2=UTRIE2_INDEX_2_BLOCK_LENGTH; i2>0;) {
 695                     block=index2[i2Block+ --i2];
 696                     if(block==prevBlock) {
 697                         /* the block is the same as the previous one, and filled with highValue */
 698                         c-=UTRIE2_DATA_BLOCK_LENGTH;
 699                         continue;
 700                     }
 701                     prevBlock=block;
 702                     if(block==dataNullOffset) {
 703                         /* this is the null data block */
 704                         if(highValue!=initialValue) {
 705                             return c;
 706                         }
 707                         c-=UTRIE2_DATA_BLOCK_LENGTH;
 708                     } else {
 709                         for(j=UTRIE2_DATA_BLOCK_LENGTH; j>0;) {
 710                             value=data[block+ --j];
 711                             if(value!=highValue) {
 712                                 return c;
 713                             }
 714                             --c;
 715                         }
 716                     }
 717                 }
 718             }
 719         }
 720
 721         /* deliver last range */
 722         return 0;
 723     }
 724
 725     /*
 726      * Compact a build-time trie.
 727      *
 728      * The compaction
 729      * - removes blocks that are identical with earlier ones
 730      * - overlaps adjacent blocks as much as possible (if overlap==TRUE)
 731      * - moves blocks in steps of the data granularity
 732      * - moves and overlaps blocks that overlap with multiple values in the overlap region
 733      *
 734      * It does not
 735      * - try to move and overlap blocks that are not already adjacent
 736      */
 737     private void compactData() {
 738         int start, newStart, movedStart;
 739         int blockLength, overlap;
 740         int i, mapIndex, blockCount;
 741
 742         /* do not compact linear-ASCII data */
 743         newStart=UTRIE2_DATA_START_OFFSET;
 744         for(start=0, i=0; start<newStart; start+=UTRIE2_DATA_BLOCK_LENGTH, ++i) {
 745             map[i]=start;
 746         }
 747
 748         /*
 749          * Start with a block length of 64 for 2-byte UTF-8,
 750          * then switch to UTRIE2_DATA_BLOCK_LENGTH.
 751          */
 752         blockLength=64;
 753         blockCount=blockLength>>UTRIE2_SHIFT_2;
 754         for(start=newStart; start<dataLength;) {
 755             /*
 756              * start: index of first entry of current block
 757              * newStart: index where the current block is to be moved
 758              *           (right after current end of already-compacted data)
 759              */
 760             if(start==UNEWTRIE2_DATA_0800_OFFSET) {
 761                 blockLength=UTRIE2_DATA_BLOCK_LENGTH;
 762                 blockCount=1;
 763             }
 764
 765             /* skip blocks that are not used */
 766             if(map[start>>UTRIE2_SHIFT_2]<=0) {
 767                 /* advance start to the next block */
 768                 start+=blockLength;
 769
 770                 /* leave newStart with the previous block! */
 771                 continue;
 772             }
 773
 774             /* search for an identical block */
 775             movedStart=findSameDataBlock(newStart, start, blockLength);
 776             if(movedStart >= 0) {
 777                 /* found an identical block, set the other block's index value for the current block */
 778                 for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) {
 779                     map[mapIndex++]=movedStart;
 780                     movedStart+=UTRIE2_DATA_BLOCK_LENGTH;
 781                 }
 782
 783                 /* advance start to the next block */
 784                 start+=blockLength;
 785
 786                 /* leave newStart with the previous block! */
 787                 continue;
 788             }
 789
 790             /* see if the beginning of this block can be overlapped with the end of the previous block */
 791             /* look for maximum overlap (modulo granularity) with the previous, adjacent block */
 792             for(overlap=blockLength-UTRIE2_DATA_GRANULARITY;
 793                 overlap>0 && !equal_int(data, (newStart-overlap), start, overlap);
 794                 overlap-=UTRIE2_DATA_GRANULARITY) {}
 795
 796             if(overlap>0 || newStart<start) {
 797                 /* some overlap, or just move the whole block */
 798                 movedStart=newStart-overlap;
 799                 for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) {
 800                     map[mapIndex++]=movedStart;
 801                     movedStart+=UTRIE2_DATA_BLOCK_LENGTH;
 802                 }
 803
 804                 /* move the non-overlapping indexes to their new positions */
 805                 start+=overlap;
 806                 for(i=blockLength-overlap; i>0; --i) {
 807                     data[newStart++]=data[start++];
 808                 }
 809             } else /* no overlap && newStart==start */ {
 810                 for(i=blockCount, mapIndex=start>>UTRIE2_SHIFT_2; i>0; --i) {
 811                     map[mapIndex++]=start;
 812                     start+=UTRIE2_DATA_BLOCK_LENGTH;
 813                 }
 814                 newStart=start;
 815             }
 816         }
 817
 818         /* now adjust the index-2 table */
 819         for(i=0; i<index2Length; ++i) {
 820             if(i==UNEWTRIE2_INDEX_GAP_OFFSET) {
 821                 /* Gap indexes are invalid (-1). Skip over the gap. */
 822                 i+=UNEWTRIE2_INDEX_GAP_LENGTH;
 823             }
 824             index2[i]=map[index2[i]>>UTRIE2_SHIFT_2];
 825         }
 826         dataNullOffset=map[dataNullOffset>>UTRIE2_SHIFT_2];
 827
 828         /* ensure dataLength alignment */
 829         while((newStart&(UTRIE2_DATA_GRANULARITY-1))!=0) {
 830             data[newStart++]=initialValue;
 831         }
 832
 833         if  (UTRIE2_DEBUG) {
 834             /* we saved some space */
 835             System.out.printf("compacting UTrie2: count of 32-bit data words %d->%d\n",
 836                 dataLength, newStart);
 837         }
 838
 839         dataLength=newStart;
 840     }
 841
 842     private void compactIndex2() {
 843         int i, start, newStart, movedStart, overlap;
 844
 845         /* do not compact linear-BMP index-2 blocks */
 846         newStart=UTRIE2_INDEX_2_BMP_LENGTH;
 847         for(start=0, i=0; start<newStart; start+=UTRIE2_INDEX_2_BLOCK_LENGTH, ++i) {
 848             map[i]=start;
 849         }
 850
 851         /* Reduce the index table gap to what will be needed at runtime. */
 852         newStart+=UTRIE2_UTF8_2B_INDEX_2_LENGTH+((highStart-0x10000)>>UTRIE2_SHIFT_1);
 853
 854         for(start=UNEWTRIE2_INDEX_2_NULL_OFFSET; start<index2Length;) {
 855             /*
 856              * start: index of first entry of current block
 857              * newStart: index where the current block is to be moved
 858              *           (right after current end of already-compacted data)
 859              */
 860
 861             /* search for an identical block */
 862             if( (movedStart=findSameIndex2Block(newStart, start))
 863                  >=0
 864             ) {
 865                 /* found an identical block, set the other block's index value for the current block */
 866                 map[start>>UTRIE2_SHIFT_1_2]=movedStart;
 867
 868                 /* advance start to the next block */
 869                 start+=UTRIE2_INDEX_2_BLOCK_LENGTH;
 870
 871                 /* leave newStart with the previous block! */
 872                 continue;
 873             }
 874
 875             /* see if the beginning of this block can be overlapped with the end of the previous block */
 876             /* look for maximum overlap with the previous, adjacent block */
 877             for(overlap=UTRIE2_INDEX_2_BLOCK_LENGTH-1;
 878                 overlap>0 && !equal_int(index2, newStart-overlap, start, overlap);
 879                 --overlap) {}
 880
 881             if(overlap>0 || newStart<start) {
 882                 /* some overlap, or just move the whole block */
 883                 map[start>>UTRIE2_SHIFT_1_2]=newStart-overlap;
 884
 885                 /* move the non-overlapping indexes to their new positions */
 886                 start+=overlap;
 887                 for(i=UTRIE2_INDEX_2_BLOCK_LENGTH-overlap; i>0; --i) {
 888                     index2[newStart++]=index2[start++];
 889                 }
 890             } else /* no overlap && newStart==start */ {
 891                 map[start>>UTRIE2_SHIFT_1_2]=start;
 892                 start+=UTRIE2_INDEX_2_BLOCK_LENGTH;
 893                 newStart=start;
 894             }
 895         }
 896
 897         /* now adjust the index-1 table */
 898         for(i=0; i<UNEWTRIE2_INDEX_1_LENGTH; ++i) {
 899             index1[i]=map[index1[i]>>UTRIE2_SHIFT_1_2];
 900         }
 901         index2NullOffset=map[index2NullOffset>>UTRIE2_SHIFT_1_2];
 902
 903         /*
 904          * Ensure data table alignment:
 905          * Needs to be granularity-aligned for 16-bit trie
 906          * (so that dataMove will be down-shiftable),
 907          * and 2-aligned for uint32_t data.
 908          */
 909         while((newStart&((UTRIE2_DATA_GRANULARITY-1)|1))!=0) {
 910             /* Arbitrary value: 0x3fffc not possible for real data. */
 911             index2[newStart++]=0x0000ffff<<UTRIE2_INDEX_SHIFT;
 912         }
 913
 914         if (UTRIE2_DEBUG) {
 915             /* we saved some space */
 916             System.out.printf("compacting UTrie2: count of 16-bit index-2 words %d->%d\n",
 917                     index2Length, newStart);
 918         }
 919
 920         index2Length=newStart;
 921     }
 922
 923     private void compactTrie() {
 924         int localHighStart;
 925         int suppHighStart;
 926         int highValue;
 927
 928         /* find highStart and round it up */
 929         highValue=get(0x10ffff);
 930         localHighStart=findHighStart(highValue);
 931         localHighStart=(localHighStart+(UTRIE2_CP_PER_INDEX_1_ENTRY-1))&~(UTRIE2_CP_PER_INDEX_1_ENTRY-1);
 932         if(localHighStart==0x110000) {
 933             highValue=errorValue;
 934         }
 935
 936         /*
 937          * Set trie->highStart only after utrie2_get32(trie, highStart).
 938          * Otherwise utrie2_get32(trie, highStart) would try to read the highValue.
 939          */
 940         this.highStart=localHighStart;
 941
 942         if (UTRIE2_DEBUG) {
 943             System.out.printf("UTrie2: highStart U+%04x  highValue 0x%x  initialValue 0x%x\n",
 944                 highStart, highValue, initialValue);
 945         }
 946
 947         if(highStart<0x110000) {
 948             /* Blank out [highStart..10ffff] to release associated data blocks. */
 949             suppHighStart= highStart<=0x10000 ? 0x10000 : highStart;
 950             setRange(suppHighStart, 0x10ffff, initialValue, true);
 951         }
 952
 953         compactData();
 954         if(highStart>0x10000) {
 955             compactIndex2();
 956         } else {
 957             if (UTRIE2_DEBUG) {
 958                  System.out.printf("UTrie2: highStart U+%04x  count of 16-bit index-2 words %d->%d\n",
 959                          highStart, index2Length, UTRIE2_INDEX_1_OFFSET);
 960             }
 961         }
 962
 963         /*
 964          * Store the highValue in the data array and round up the dataLength.
 965          * Must be done after compactData() because that assumes that dataLength
 966          * is a multiple of UTRIE2_DATA_BLOCK_LENGTH.
 967          */
 968         data[dataLength++]=highValue;
 969         while((dataLength&(UTRIE2_DATA_GRANULARITY-1))!=0) {
 970             data[dataLength++]=initialValue;
 971         }
 972
 973         isCompacted=true;
 974     }
 975
 976
 977     /**
 978      * Produce an optimized, read-only Trie2_16 from this writable Trie.
 979      * The data values outside of the range that will fit in a 16 bit
 980      * unsigned value will be truncated.
 981      */
 982     public Trie2_16 toTrie2_16() {
 983         Trie2_16 frozenTrie = new Trie2_16();
 984         freeze(frozenTrie, ValueWidth.BITS_16);
 985         return frozenTrie;
 986     }
 987
 988
 989     /**
 990      * Produce an optimized, read-only Trie2_32 from this writable Trie.
 991      *
 992      */
 993     public Trie2_32 toTrie2_32() {
 994         Trie2_32 frozenTrie = new Trie2_32();
 995         freeze(frozenTrie, ValueWidth.BITS_32);
 996         return frozenTrie;
 997     }
 998
 999
1000     /**
1001      * Maximum length of the runtime index array.
1002      * Limited by its own 16-bit index values, and by uint16_t UTrie2Header.indexLength.
1003      * (The actual maximum length is lower,
1004      * (0x110000>>UTRIE2_SHIFT_2)+UTRIE2_UTF8_2B_INDEX_2_LENGTH+UTRIE2_MAX_INDEX_1_LENGTH.)
1005      */
1006     private static final int UTRIE2_MAX_INDEX_LENGTH = 0xffff;
1007
1008     /**
1009      * Maximum length of the runtime data array.
1010      * Limited by 16-bit index values that are left-shifted by UTRIE2_INDEX_SHIFT,
1011      * and by uint16_t UTrie2Header.shiftedDataLength.
1012      */
1013     private static final int  UTRIE2_MAX_DATA_LENGTH = 0xffff<<UTRIE2_INDEX_SHIFT;
1014
1015     /* Compact the data and then populate an optimized read-only Trie.  */
1016     private void freeze(Trie2 dest, ValueWidth valueBits) {
1017         int  i;
1018         int  allIndexesLength;
1019         int  dataMove;  /* >0 if the data is moved to the end of the index array */
1020
1021
1022         /* compact if necessary */
1023         if(!isCompacted) {
1024             compactTrie();
1025         }
1026
1027         if(highStart<=0x10000) {
1028             allIndexesLength=UTRIE2_INDEX_1_OFFSET;
1029         } else {
1030             allIndexesLength=index2Length;
1031         }
1032         if(valueBits==ValueWidth.BITS_16) {
1033             dataMove=allIndexesLength;
1034         } else {
1035             dataMove=0;
1036         }
1037
1038         /* are indexLength and dataLength within limits? */
1039         if( /* for unshifted indexLength */
1040             allIndexesLength>UTRIE2_MAX_INDEX_LENGTH ||
1041             /* for unshifted dataNullOffset */
1042             (dataMove+dataNullOffset)>0xffff ||
1043             /* for unshifted 2-byte UTF-8 index-2 values */
1044             (dataMove+UNEWTRIE2_DATA_0800_OFFSET)>0xffff ||
1045             /* for shiftedDataLength */
1046             (dataMove+dataLength)>UTRIE2_MAX_DATA_LENGTH) {
1047                 throw new UnsupportedOperationException("Trie2 data is too large.");
1048         }
1049
1050         /* calculate the sizes of, and allocate, the index and data arrays */
1051         int indexLength = allIndexesLength;
1052         if (valueBits==ValueWidth.BITS_16) {
1053             indexLength += dataLength;
1054         } else {
1055             dest.data32 = new int[dataLength];
1056         }
1057         dest.index = new char[indexLength];
1058
1059         dest.indexLength = allIndexesLength;
1060         dest.dataLength  = dataLength;
1061         if(highStart<=0x10000) {
1062             dest.index2NullOffset = 0xffff;
1063         } else {
1064             dest.index2NullOffset = UTRIE2_INDEX_2_OFFSET + index2NullOffset;
1065         }
1066         dest.initialValue   = initialValue;
1067         dest.errorValue     = errorValue;
1068         dest.highStart      = highStart;
1069         dest.highValueIndex = dataMove + dataLength - UTRIE2_DATA_GRANULARITY;
1070         dest.dataNullOffset = (dataMove+dataNullOffset);
1071
1072         // Create a header and set the its fields.
1073         //   (This is only used in the event that we serialize the Trie, but is
1074         //    convenient to do here.)
1075         dest.header = new Trie2.UTrie2Header();
1076         dest.header.signature         = 0x54726932; /* "Tri2" */
1077         dest.header.options           = valueBits==ValueWidth.BITS_16 ? 0 : 1;
1078         dest.header.indexLength       = dest.indexLength;
1079         dest.header.shiftedDataLength = dest.dataLength>>UTRIE2_INDEX_SHIFT;
1080         dest.header.index2NullOffset  = dest.index2NullOffset;
1081         dest.header.dataNullOffset    = dest.dataNullOffset;
1082         dest.header.shiftedHighStart  = dest.highStart>>UTRIE2_SHIFT_1;
1083
1084
1085
1086         /* write the index-2 array values shifted right by UTRIE2_INDEX_SHIFT, after adding dataMove */
1087         int destIdx = 0;
1088         for(i=0; i<UTRIE2_INDEX_2_BMP_LENGTH; i++) {
1089             dest.index[destIdx++] = (char)((index2[i]+dataMove) >> UTRIE2_INDEX_SHIFT);
1090         }
1091         if (UTRIE2_DEBUG) {
1092             System.out.println("\n\nIndex2 for BMP limit is " + Integer.toHexString(destIdx));
1093         }
1094
1095         /* write UTF-8 2-byte index-2 values, not right-shifted */
1096         for(i=0; i<(0xc2-0xc0); ++i) {                                  /* C0..C1 */
1097             dest.index[destIdx++] = (char)(dataMove+UTRIE2_BAD_UTF8_DATA_OFFSET);
1098         }
1099         for(; i<(0xe0-0xc0); ++i) {                                     /* C2..DF */
1100             dest.index[destIdx++]=(char)(dataMove+index2[i<<(6-UTRIE2_SHIFT_2)]);
1101         }
1102         if (UTRIE2_DEBUG) {
1103             System.out.println("Index2 for UTF-8 2byte values limit is " + Integer.toHexString(destIdx));
1104         }
1105
1106         if(highStart>0x10000) {
1107             int index1Length = (highStart-0x10000)>>UTRIE2_SHIFT_1;
1108             int index2Offset = UTRIE2_INDEX_2_BMP_LENGTH + UTRIE2_UTF8_2B_INDEX_2_LENGTH + index1Length;
1109
1110             /* write 16-bit index-1 values for supplementary code points */
1111             //p=(uint32_t *)newTrie->index1+UTRIE2_OMITTED_BMP_INDEX_1_LENGTH;
1112             for(i=0; i<index1Length; i++) {
1113                 //*dest16++=(uint16_t)(UTRIE2_INDEX_2_OFFSET + *p++);
1114                 dest.index[destIdx++] = (char)(UTRIE2_INDEX_2_OFFSET + index1[i+UTRIE2_OMITTED_BMP_INDEX_1_LENGTH]);
1115             }
1116             if (UTRIE2_DEBUG) {
1117                 System.out.println("Index 1 for supplementals, limit is " + Integer.toHexString(destIdx));
1118             }
1119
1120             /*
1121              * write the index-2 array values for supplementary code points,
1122              * shifted right by UTRIE2_INDEX_SHIFT, after adding dataMove
1123              */
1124             for(i=0; i<index2Length-index2Offset; i++) {
1125                 dest.index[destIdx++] = (char)((dataMove + index2[index2Offset+i])>>UTRIE2_INDEX_SHIFT);
1126             }
1127             if (UTRIE2_DEBUG) {
1128                 System.out.println("Index 2 for supplementals, limit is " + Integer.toHexString(destIdx));
1129             }
1130         }
1131
1132         /* write the 16/32-bit data array */
1133         switch(valueBits) {
1134         case BITS_16:
1135             /* write 16-bit data values */
1136             assert(destIdx == dataMove);
1137             dest.data16 = destIdx;
1138             for(i=0; i<dataLength; i++) {
1139                 dest.index[destIdx++] = (char)data[i];
1140             }
1141             break;
1142         case BITS_32:
1143             /* write 32-bit data values */
1144             for (i=0; i<dataLength; i++) {
1145                 dest.data32[i] = this.data[i];
1146             }
1147             break;
1148         }
1149         // The writable, but compressed, Trie2 stays around unless the caller drops its references to it.
1150     }
1151
1152
1153     /* Start with allocation of 16k data entries. */
1154     private static final int UNEWTRIE2_INITIAL_DATA_LENGTH = 1<<14;
1155
1156     /* Grow about 8x each time. */
1157     private static final int UNEWTRIE2_MEDIUM_DATA_LENGTH = 1<<17;
1158
1159     /** The null index-2 block, following the gap in the index-2 table. */
1160     private static final int UNEWTRIE2_INDEX_2_NULL_OFFSET = UNEWTRIE2_INDEX_GAP_OFFSET + UNEWTRIE2_INDEX_GAP_LENGTH;
1161
1162     /** The start of allocated index-2 blocks. */
1163     private static final int UNEWTRIE2_INDEX_2_START_OFFSET = UNEWTRIE2_INDEX_2_NULL_OFFSET + UTRIE2_INDEX_2_BLOCK_LENGTH;
1164
1165     /**
1166      * The null data block.
1167      * Length 64=0x40 even if UTRIE2_DATA_BLOCK_LENGTH is smaller,
1168      * to work with 6-bit trail bytes from 2-byte UTF-8.
1169      */
1170     private static final int UNEWTRIE2_DATA_NULL_OFFSET = UTRIE2_DATA_START_OFFSET;
1171
1172     /** The start of allocated data blocks. */
1173     private static final int UNEWTRIE2_DATA_START_OFFSET = UNEWTRIE2_DATA_NULL_OFFSET+0x40;
1174
1175     /**
1176      * The start of data blocks for U+0800 and above.
1177      * Below, compaction uses a block length of 64 for 2-byte UTF-8.
1178      * From here on, compaction uses UTRIE2_DATA_BLOCK_LENGTH.
1179      * Data values for 0x780 code points beyond ASCII.
1180      */
1181     private static final int UNEWTRIE2_DATA_0800_OFFSET = UNEWTRIE2_DATA_START_OFFSET+0x780;
1182
1183     //
1184     // Private data members.  From struct UNewTrie2 in ICU4C
1185     //
1186     private  int[]   index1 = new int[UNEWTRIE2_INDEX_1_LENGTH];
1187     private  int[]   index2 = new int[UNEWTRIE2_MAX_INDEX_2_LENGTH];
1188     private  int[]   data;
1189
1190     private  int     index2Length;
1191     private  int     dataCapacity;
1192     private  int     firstFreeBlock;
1193     private  int     index2NullOffset;
1194     private  boolean isCompacted;
1195
1196
1197     /*
1198      * Multi-purpose per-data-block table.
1199      *
1200      * Before compacting:
1201      *
1202      * Per-data-block reference counters/free-block list.
1203      *  0: unused
1204      * >0: reference counter (number of index-2 entries pointing here)
1205      * <0: next free data block in free-block list
1206      *
1207      * While compacting:
1208      *
1209      * Map of adjusted indexes, used in compactData() and compactIndex2().
1210      * Maps from original indexes to new ones.
1211      */
1212      private  int[]   map = new int[UNEWTRIE2_MAX_DATA_LENGTH>>UTRIE2_SHIFT_2];
1213
1214
1215      private boolean UTRIE2_DEBUG = false;
1216
1217 }