home *** CD-ROM | disk | FTP | other *** search
/ Apple Developer Connection Student Program / ADC Tools Sampler CD Disk 3 1999.iso / Metrowerks CodeWarrior / Java Support / Java_Source / Java2 / src / java / text / CompactCharArray.java < prev    next >
Encoding:
Java Source  |  1999-05-28  |  12.0 KB  |  356 lines  |  [TEXT/CWIE]
  1. /*
  2.  * @(#)CompactCharArray.java    1.14 98/06/11
  3.  *
  4.  * (C) Copyright Taligent, Inc. 1996 - All Rights Reserved
  5.  * (C) Copyright IBM Corp. 1996 - All Rights Reserved
  6.  *
  7.  * Portions copyright (c) 1996-1998 Sun Microsystems, Inc. All Rights Reserved.
  8.  *
  9.  *   The original version of this source code and documentation is copyrighted
  10.  * and owned by Taligent, Inc., a wholly-owned subsidiary of IBM. These
  11.  * materials are provided under terms of a License Agreement between Taligent
  12.  * and Sun. This technology is protected by multiple US and International
  13.  * patents. This notice and attribution to Taligent may not be removed.
  14.  *   Taligent is a registered trademark of Taligent, Inc.
  15.  *
  16.  * Permission to use, copy, modify, and distribute this software
  17.  * and its documentation for NON-COMMERCIAL purposes and without
  18.  * fee is hereby granted provided that this copyright notice
  19.  * appears in all copies. Please refer to the file "copyright.html"
  20.  * for further important copyright and licensing information.
  21.  *
  22.  * SUN MAKES NO REPRESENTATIONS OR WARRANTIES ABOUT THE SUITABILITY OF
  23.  * THE SOFTWARE, EITHER EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED
  24.  * TO THE IMPLIED WARRANTIES OF MERCHANTABILITY, FITNESS FOR A
  25.  * PARTICULAR PURPOSE, OR NON-INFRINGEMENT. SUN SHALL NOT BE LIABLE FOR
  26.  * ANY DAMAGES SUFFERED BY LICENSEE AS A RESULT OF USING, MODIFYING OR
  27.  * DISTRIBUTING THIS SOFTWARE OR ITS DERIVATIVES.
  28.  *
  29.  */
  30.  
  31. package java.text;
  32.  
  33. /**
  34.  * class CompactATypeArray : use only on primitive data types
  35.  * Provides a compact way to store information that is indexed by Unicode
  36.  * values, such as character properties, types, keyboard values, etc.This
  37.  * is very useful when you have a block of Unicode data that contains
  38.  * significant values while the rest of the Unicode data is unused in the
  39.  * application or when you have a lot of redundance, such as where all 21,000
  40.  * Han ideographs have the same value.  However, lookup is much faster than a
  41.  * hash table.
  42.  * A compact array of any primitive data type serves two purposes:
  43.  * <UL type = round>
  44.  *     <LI>Fast access of the indexed values.
  45.  *     <LI>Smaller memory footprint.
  46.  * </UL>
  47.  * A compact array is composed of a index array and value array.  The index
  48.  * array contains the indicies of Unicode characters to the value array.
  49.  *
  50.  * @see        CompactByteArray
  51.  * @see        CompactIntArray
  52.  * @see        CompactShortArray
  53.  * @see        CompactStringArray
  54.  * @version    1.14 06/11/98
  55.  * @author     Helena Shih
  56.  */
  57. final class CompactCharArray implements Cloneable{
  58.  
  59.     /**
  60.      * The total number of Unicode characters.
  61.      */
  62.     public static  final int UNICODECOUNT =65536;
  63.  
  64.     /**
  65.      * Default constructor for CompactCharArray, the default value of the
  66.      * compact array is '\u0000'.
  67.      */
  68.     public CompactCharArray()
  69.     {
  70.         this('\u0000');
  71.     }
  72.  
  73.     /**
  74.      * Contructor for CompactCharArray.
  75.      * @param defaultValue the default value of the compact array.
  76.      */
  77.     public CompactCharArray(char defaultValue)
  78.     {
  79.         int i;
  80.         values = new char[UNICODECOUNT];
  81.         indices = new short[INDEXCOUNT];
  82.         hashes = new int[INDEXCOUNT];
  83.         for (i = 0; i < UNICODECOUNT; ++i) {
  84.             values[i] = defaultValue;
  85.         }
  86.         for (i = 0; i < INDEXCOUNT; ++i) {
  87.             indices[i] = (short)(i<<BLOCKSHIFT);
  88.             hashes[i] = 0;
  89.         }
  90.         isCompact = false;
  91.     }
  92.  
  93.     /**
  94.      * Constructor for CompactCharArray.
  95.      * @param indexArray the indicies of the compact array.
  96.      * @param newValues the values of the compact array.
  97.      * @exception IllegalArgumentException If the index is out of range.
  98.      */
  99.     public CompactCharArray(short indexArray[], char newValues[])
  100.     {
  101.         int i;
  102.         if (indexArray.length != INDEXCOUNT)
  103.             throw new IllegalArgumentException("Index out of bounds.");
  104.         for (i = 0; i < INDEXCOUNT; ++i) {
  105.             short index = indexArray[i];
  106.             if ((index < 0) || (index >= newValues.length+BLOCKCOUNT))
  107.                 throw new IllegalArgumentException("Index out of bounds.");
  108.         }
  109.         indices = indexArray;
  110.         values = newValues;
  111.         isCompact = true;
  112.     }
  113.  
  114.     /**
  115.      * Get the mapped value of a Unicode character.
  116.      * @param index the character to get the mapped value with
  117.      * @return the mapped value of the given character
  118.      */
  119.    public char elementAt(char index) // parameterized on short
  120.     {
  121.         return (values[(indices[index >> BLOCKSHIFT] & 0xFFFF)
  122.                        + (index & BLOCKMASK)]);
  123.     }
  124.  
  125.     /**
  126.      * Set a new value for a Unicode character.
  127.      * Set automatically expands the array if it is compacted.
  128.      * @param index the character to set the mapped value with
  129.      * @param value the new mapped value
  130.      */
  131.     public void setElementAt(char index, char value)
  132.     {
  133.         if (isCompact)
  134.             expand();
  135.         values[(int)index] = value;
  136.         touchBlock(index >> BLOCKSHIFT, value);
  137.     }
  138.  
  139.     /**
  140.      * Set new values for a range of Unicode character.
  141.      * @param start the starting offset of the range
  142.      * @param end the endding offset of the range
  143.      * @param value the new mapped value
  144.      */
  145.     public void setElementAt(char start, char end, char value)
  146.     {
  147.         int i;
  148.         if (isCompact) {
  149.             expand();
  150.         }
  151.         for (i = start; i <= end; ++i) {
  152.             values[i] = value;
  153.             touchBlock(i >> BLOCKSHIFT, value);
  154.         }
  155.     }
  156.  
  157.     /**
  158.       *Compact the array.
  159.       */
  160.     public void compact()
  161.     {
  162.         if (!isCompact) {
  163.             int limitCompacted = 0;
  164.             int iBlockStart = 0;
  165.             short iUntouched = -1;
  166.  
  167.             for (int i = 0; i < indices.length; ++i, iBlockStart += BLOCKCOUNT) {
  168.                 indices[i] = -1;
  169.                 boolean touched = blockTouched(i);
  170.                 if (!touched && iUntouched != -1) {
  171.                     // If no values in this block were set, we can just set its
  172.                     // index to be the same as some other block with no values
  173.                     // set, assuming we've seen one yet.
  174.                     indices[i] = iUntouched;
  175.                 } else {
  176.                     int jBlockStart = 0;
  177.                     int j = 0;
  178.                     for (j = 0; j < limitCompacted;
  179.                             ++j, jBlockStart += BLOCKCOUNT) {
  180.                         if (hashes[i] == hashes[j] && 
  181.                                 arrayRegionMatches(values, iBlockStart,
  182.                                 values, jBlockStart, BLOCKCOUNT)) {
  183.                             indices[i] = (short)jBlockStart;
  184.                         }
  185.                     }
  186.                     if (indices[i] == -1) {
  187.                         // we didn't match, so copy & update
  188.                         System.arraycopy(values, iBlockStart,
  189.                             values, jBlockStart, BLOCKCOUNT);
  190.                         indices[i] = (short)jBlockStart;
  191.                         hashes[j] = hashes[i];
  192.                         ++limitCompacted;
  193.  
  194.                         if (!touched) {
  195.                             // If this is the first untouched block we've seen,
  196.                             // remember its index.
  197.                             iUntouched = (short)jBlockStart;
  198.                         }
  199.                     }
  200.                 }
  201.             }
  202.             // we are done compacting, so now make the array shorter
  203.             int newSize = limitCompacted*BLOCKCOUNT;
  204.             char[] result = new char[newSize];
  205.             System.arraycopy(values, 0, result, 0, newSize);
  206.             values = result;
  207.             isCompact = true;
  208.             hashes = null;
  209.         }
  210.     }
  211.  
  212.     /**
  213.      * Convenience utility to compare two arrays of doubles.
  214.      * @param len the length to compare.
  215.      * The start indices and start+len must be valid.
  216.      */
  217.     final static boolean arrayRegionMatches(char[] source, int sourceStart,
  218.                                             char[] target, int targetStart,
  219.                                             int len)
  220.     {
  221.         int sourceEnd = sourceStart + len;
  222.         int delta = targetStart - sourceStart;
  223.         for (int i = sourceStart; i < sourceEnd; i++) {
  224.             if (source[i] != target[i + delta])
  225.             return false;
  226.         }
  227.         return true;
  228.     }
  229.  
  230.     /**
  231.      * Remember that a specified block was "touched", i.e. had a value set.
  232.      * Untouched blocks can be skipped when compacting the array
  233.      */
  234.     private final void touchBlock(int i, int value) {
  235.         hashes[i] = (hashes[i] + (value<<1)) | 1;
  236.     }
  237.  
  238.     /**
  239.      * Query whether a specified block was "touched", i.e. had a value set.
  240.      * Untouched blocks can be skipped when compacting the array
  241.      */
  242.     private final boolean blockTouched(int i) {
  243.         return hashes[i] != 0;
  244.     }
  245.      
  246.     /** For internal use only.  Do not modify the result, the behavior of
  247.       * modified results are undefined.
  248.       */
  249.     public short getIndexArray()[]
  250.     {
  251.         return indices;
  252.     }
  253.     /** For internal use only.  Do not modify the result, the behavior of
  254.       * modified results are undefined.
  255.       */
  256.     public char getStringArray()[]
  257.     {
  258.         return values;
  259.     }
  260.     /**
  261.      * Overrides Cloneable
  262.      */
  263.     public Object clone()
  264.     {
  265.         try {
  266.             CompactCharArray other = (CompactCharArray) super.clone();
  267.             other.values = (char[])values.clone();
  268.             other.indices = (short[])indices.clone();
  269.             if (hashes != null) other.hashes = (int[])hashes.clone();
  270.             return other;
  271.         } catch (CloneNotSupportedException e) {
  272.             throw new InternalError();
  273.         }
  274.     }
  275.     /**
  276.      * Compares the equality of two compact array objects.
  277.      * @param obj the compact array object to be compared with this.
  278.      * @return true if the current compact array object is the same
  279.      * as the compact array object obj; false otherwise.
  280.      */
  281.     public boolean equals(Object obj) {
  282.         if (obj == null) return false;
  283.         if (this == obj)                      // quick check
  284.             return true;
  285.         if (getClass() != obj.getClass())         // same class?
  286.             return false;
  287.         CompactCharArray other = (CompactCharArray) obj;
  288.         for (int i = 0; i < UNICODECOUNT; i++) {
  289.             // could be sped up later
  290.             if (elementAt((char)i) != other.elementAt((char)i))
  291.                 return false;
  292.         }
  293.         return true; // we made it through the guantlet.
  294.     }
  295.     /**
  296.      * Generates the hash code for the compact array object
  297.      */
  298.  
  299.     public int hashCode() {
  300.         int result = 0;
  301.         int increment = Math.min(3, values.length/16);
  302.         for (int i = 0; i < values.length; i+= increment) {
  303.             result = result * 37 + values[i];
  304.         }
  305.         return result;
  306.     }
  307.  
  308.     // --------------------------------------------------------------
  309.     // private
  310.     // --------------------------------------------------------------
  311.     /**
  312.       * Expanding takes the array back to a 65536 element array.
  313.       */
  314.     private void expand()
  315.     {
  316.         int i;
  317.         if (isCompact) {
  318.             char[]  tempArray;
  319.             tempArray = new char[UNICODECOUNT];
  320.             hashes = new int[INDEXCOUNT];
  321.             for (i = 0; i < UNICODECOUNT; ++i) {
  322.                 char value = elementAt((char)i);
  323.                 tempArray[i] = value;
  324.                 touchBlock(i >> BLOCKSHIFT, value);
  325.             }
  326.             for (i = 0; i < INDEXCOUNT; ++i) {
  327.                 indices[i] = (short)(i<<BLOCKSHIFT);
  328.             }
  329.             values = null;
  330.             values = tempArray;
  331.             isCompact = false;
  332.         }
  333.     }
  334.  
  335.     private char getArrayValue(int n)
  336.     {
  337.         return values[n];
  338.     }
  339.  
  340.     private short getIndexArrayValue(int n)
  341.     {
  342.         return indices[n];
  343.     }
  344.  
  345.     private static  final int BLOCKSHIFT =7;
  346.     private static  final int BLOCKCOUNT =(1<<BLOCKSHIFT);
  347.     private static  final int INDEXSHIFT =(16-BLOCKSHIFT);
  348.     private static  final int INDEXCOUNT =(1<<INDEXSHIFT);
  349.     private static  final int BLOCKMASK = BLOCKCOUNT - 1;
  350.  
  351.     private char[] values;  // char -> short (char parameterized short)
  352.     private short indices[];
  353.     private int[] hashes;
  354.     private boolean isCompact;
  355. };
  356.