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 / CompactIntArray.java < prev    next >
Encoding:
Java Source  |  1999-05-28  |  11.3 KB  |  337 lines  |  [TEXT/CWIE]
  1. /*
  2.  * @(#)CompactIntArray.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                CompactShortArray
  51.  * @see                CompactByteArray
  52.  * @see                CompactCharArray
  53.  * @see                CompactStringArray
  54.  * @version            1.14 06/11/98
  55.  * @author             Helena Shih
  56.  */
  57. final class CompactIntArray implements Cloneable {
  58.  
  59.  
  60.     /**
  61.      * The total number of Unicode characters.
  62.      */
  63.     public static  final int UNICODECOUNT =65536;
  64.  
  65.     /**
  66.      * Default constructor for CompactIntArray, the default value of the
  67.      * compact array is 0.
  68.      */
  69.     public CompactIntArray()
  70.     {
  71.         this(0);
  72.     }
  73.     /**
  74.      * Constructor for CompactIntArray.
  75.      * @param defaultValue the default value of the compact array.
  76.      */
  77.  
  78.     public CompactIntArray(int defaultValue)
  79.     {
  80.         int i;
  81.         values = new int[UNICODECOUNT];
  82.         indices = new short[INDEXCOUNT];
  83.         hashes = new int[INDEXCOUNT];
  84.         
  85.         for (i = 0; i < UNICODECOUNT; ++i) {
  86.             values[i] = defaultValue;
  87.         }
  88.         for (i = 0; i < INDEXCOUNT; ++i) {
  89.             indices[i] = (short)(i<<BLOCKSHIFT);
  90.             hashes[i] = 0;
  91.         }
  92.         isCompact = false;
  93.     }
  94.  
  95.     /**
  96.      * Constructor for CompactIntArray.
  97.      * @param indexArray the indicies of the compact array.
  98.      * @param newValues the values of the compact array.
  99.      * @exception IllegalArgumentException If the index is out of range.
  100.      */
  101.     public CompactIntArray(short indexArray[],
  102.                            int newValues[])
  103.     {
  104.         int i;
  105.         if (indexArray.length != INDEXCOUNT)
  106.             throw new IllegalArgumentException("Index out of bounds.");
  107.         for (i = 0; i < INDEXCOUNT; ++i) {
  108.             short index = indexArray[i];
  109.             if ((index < 0) || (index >= newValues.length+BLOCKCOUNT))
  110.                 throw new IllegalArgumentException("Index out of bounds.");
  111.         }
  112.         indices = indexArray;
  113.         values = newValues;
  114.         isCompact = true;
  115.     }
  116.  
  117.     /**
  118.      * Get the mapped value of a Unicode character.
  119.      * @param index the character to get the mapped value with
  120.      * @return the mapped value of the given character
  121.      */
  122.     public int elementAt(char index)
  123.     {
  124.         return (values[(indices[index >> BLOCKSHIFT] & 0xFFFF)
  125.                        + (index & BLOCKMASK)]);
  126.     }
  127.  
  128.     /**
  129.      * Set a new value for a Unicode character.
  130.      * Set automatically expands the array if it is compacted.
  131.      * @param index the character to set the mapped value with
  132.      * @param value the new mapped value
  133.      */
  134.     public void setElementAt(char index, int value)
  135.     {
  136.         if (isCompact) {
  137.             expand();
  138.         }
  139.         values[(int)index] = value;
  140.         touchBlock(index >> BLOCKSHIFT, value);
  141.     }
  142.  
  143.     /**
  144.      * Set new values for a range of Unicode character.
  145.      * @param start the startting offset of the range
  146.      * @param end the ending offset of the range
  147.      * @param value the new mapped value
  148.      */
  149.     public void setElementAt(char start, char end, int value)
  150.     {
  151.         int i;
  152.         if (isCompact) {
  153.             expand();
  154.         }
  155.         for (i = start; i <= end; ++i) {
  156.             values[i] = value;
  157.             touchBlock(i >> BLOCKSHIFT, value);
  158.         }
  159.     }
  160.  
  161.     /**
  162.      * Compact the array.
  163.      */
  164.     public void compact()
  165.     {
  166.         if (!isCompact) {
  167.             int limitCompacted = 0;
  168.             int iBlockStart = 0;
  169.             short iUntouched = -1;
  170.  
  171.             for (int i = 0; i < indices.length; ++i, iBlockStart += BLOCKCOUNT) {
  172.                 indices[i] = -1;
  173.                 boolean touched = blockTouched(i);
  174.                 if (!touched && iUntouched != -1) {
  175.                     // If no values in this block were set, we can just set its
  176.                     // index to be the same as some other block with no values
  177.                     // set, assuming we've seen one yet.
  178.                     indices[i] = iUntouched;
  179.                 } else {
  180.                     int jBlockStart = 0;
  181.                     int j = 0;
  182.                     for (j=0; j < limitCompacted;
  183.                             ++j, jBlockStart += BLOCKCOUNT) {
  184.                         if (hashes[i] == hashes[j] && 
  185.                                 Utility.arrayRegionMatches(values, iBlockStart,
  186.                                 values, jBlockStart, BLOCKCOUNT)) {
  187.                             indices[i] = (short)jBlockStart;
  188.                             break;
  189.                         }
  190.                     }
  191.                     if (indices[i] == -1) {
  192.                         // we didn't match, so copy & update
  193.                         System.arraycopy(values, iBlockStart,
  194.                             values, jBlockStart, BLOCKCOUNT);
  195.                         indices[i] = (short)jBlockStart;
  196.                         hashes[j] = hashes[i];
  197.                         ++limitCompacted;
  198.  
  199.                         if (!touched) {
  200.                             // If this is the first untouched block we've seen,
  201.                             // remember its index.
  202.                             iUntouched = (short)jBlockStart;
  203.                         }
  204.                     }
  205.                 }
  206.             }
  207.  
  208.             // we are done compacting, so now make the array shorter
  209.             int newSize = limitCompacted * BLOCKCOUNT;
  210.             int[] result = new int[newSize];
  211.             System.arraycopy(values, 0, result, 0, newSize);
  212.             values = result;
  213.             isCompact = true;
  214.             hashes = null;
  215.         }
  216.     }
  217.  
  218.     /**
  219.      * Remember that a specified block was "touched", i.e. had a value set.
  220.      * Untouched blocks can be skipped when compacting the array
  221.      */
  222.     private final void touchBlock(int i, int value) {
  223.         hashes[i] = (hashes[i] + (value<<1)) | 1;
  224.     }
  225.  
  226.     /**
  227.      * Query whether a specified block was "touched", i.e. had a value set.
  228.      * Untouched blocks can be skipped when compacting the array
  229.      */
  230.     private final boolean blockTouched(int i) {
  231.         return hashes[i] != 0;
  232.     }
  233.      
  234.     /** For internal use only.  Do not modify the result, the behavior of
  235.       * modified results are undefined.
  236.       */
  237.     public short getIndexArray()[]
  238.     {
  239.         return indices;
  240.     }
  241.  
  242.     /** For internal use only.  Do not modify the result, the behavior of
  243.       * modified results are undefined.
  244.       */
  245.     public int getStringArray()[]
  246.     {
  247.         return values;
  248.     }
  249.  
  250.     /**
  251.      * Overrides Cloneable
  252.      */
  253.     public Object clone()
  254.     {
  255.         try {
  256.             CompactIntArray other = (CompactIntArray) super.clone();
  257.             other.values = (int[])values.clone();
  258.             other.indices = (short[])indices.clone();
  259.             
  260.             if (hashes != null) other.hashes = (int[])hashes.clone();
  261.             return other;
  262.         } catch (CloneNotSupportedException e) {
  263.             throw new InternalError();
  264.         }
  265.     }
  266.  
  267.     /**
  268.      * Compares the equality of two compact array objects.
  269.      * @param obj the compact array object to be compared with this.
  270.      * @return true if the current compact array object is the same
  271.      * as the compact array object obj; false otherwise.
  272.      */
  273.     public boolean equals(Object obj) {
  274.         if (obj == null) return false;
  275.         if (this == obj)                      // quick check
  276.             return true;
  277.         if (getClass() != obj.getClass())         // same class?
  278.             return false;
  279.         CompactIntArray other = (CompactIntArray) obj;
  280.         for (int i = 0; i < UNICODECOUNT; i++) {
  281.             // could be sped up later
  282.             if (elementAt((char)i) != other.elementAt((char)i))
  283.                 return false;
  284.         }
  285.         return true; // we made it through the gauntlet.
  286.     }
  287.  
  288.     /**
  289.      * Generates the hash code for the compact array object
  290.      */
  291.     public int hashCode() {
  292.         int result = 0;
  293.         int increment = Math.min(3, values.length/16);
  294.         for (int i = 0; i < values.length; i+= increment) {
  295.             result = result * 37 + values[i];
  296.         }
  297.         return result;
  298.     }
  299.  
  300.     // --------------------------------------------------------------
  301.     // private
  302.     // --------------------------------------------------------------
  303.     /**
  304.      * Expanded takes the array back to a 65536 element array
  305.      */
  306.     private void expand()
  307.     {
  308.         int i;
  309.         if (isCompact) {
  310.             int[]   tempArray;
  311.             hashes = new int[INDEXCOUNT];
  312.             tempArray = new int[UNICODECOUNT];
  313.             for (i = 0; i < UNICODECOUNT; ++i) {
  314.                 int value = elementAt((char)i);
  315.                 tempArray[i] = value;
  316.                 touchBlock(i >> BLOCKSHIFT, value);
  317.             }
  318.             for (i = 0; i < INDEXCOUNT; ++i) {
  319.                 indices[i] = (short)(i<<BLOCKSHIFT);
  320.             }
  321.             values = tempArray;
  322.             isCompact = false;
  323.         }
  324.     }
  325.  
  326.     private static  final int BLOCKSHIFT =7;
  327.     private static  final int BLOCKCOUNT =(1<<BLOCKSHIFT);
  328.     private static  final int INDEXSHIFT =(16-BLOCKSHIFT);
  329.     private static  final int INDEXCOUNT =(1<<INDEXSHIFT);
  330.     private static  final int BLOCKMASK = BLOCKCOUNT - 1;
  331.  
  332.     private int[] values;  // char -> int (char parameterized int)
  333.     private short indices[];
  334.     private boolean isCompact;
  335.     private int[] hashes;
  336. };
  337.