home *** CD-ROM | disk | FTP | other *** search
/ Chip 1998 November / Chip_1998-11_cd.bin / tema / Cafe / main.bin / CompactShortArray.java < prev    next >
Text File  |  1997-05-20  |  15KB  |  405 lines
  1. /*
  2.  * @(#)CompactShortArray.java    1.8 97/01/27
  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 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.  * @see                CompactByteArray
  50.  * @see                CompactIntArray
  51.  * @see                CompactCharArray
  52.  * @see                CompactStringArray
  53.  * @version            1.8 01/27/97
  54.  * @author             Helena Shih
  55.  */
  56. final class CompactShortArray implements Cloneable {
  57.  
  58.  
  59.     /**
  60.      * The total number of Unicode characters.
  61.      */
  62.     public static  final int UNICODECOUNT =65536;
  63.  
  64.     /**
  65.      * Default constructor for CompactShortArray, the default value of the
  66.      * compact array is 0.
  67.      */
  68.     public CompactShortArray()
  69.     {
  70.         this((short)0);
  71.     }
  72.     /**
  73.      * Constructor for CompactShortArray.
  74.      * @param defaultValue the default value of the compact array.
  75.      */
  76.     public CompactShortArray(short defaultValue)
  77.     {
  78.         int i;
  79.         values = new short[UNICODECOUNT];
  80.         indices = new short[INDEXCOUNT];
  81.         for (i = 0; i < UNICODECOUNT; ++i) {
  82.             values[i] = defaultValue;
  83.         }
  84.         for (i = 0; i < INDEXCOUNT; ++i) {
  85.             indices[i] = (short)(i<<BLOCKSHIFT);
  86.         }
  87.         isCompact = false;
  88.     }
  89.     /**
  90.      * Constructor for CompactShortArray.
  91.      * @param indexArray the indicies of the compact array.
  92.      * @param newValues the values of the compact array.
  93.      * @exception IllegalArgumentException If the index is out of range.
  94.      */
  95.     public CompactShortArray(short indexArray[],
  96.                              short newValues[])
  97.     {
  98.         int i;
  99.         if (indexArray.length != INDEXCOUNT)
  100.             throw new IllegalArgumentException("Index out of bounds.");
  101.         for (i = 0; i < INDEXCOUNT; ++i) {
  102.             short index = indexArray[i];
  103.             if ((index < 0) || (index >= newValues.length+BLOCKCOUNT))
  104.                 throw new IllegalArgumentException("Index out of bounds.");
  105.         }
  106.         indices = indexArray;
  107.         values = newValues;
  108.     }
  109.     /**
  110.      * Get the mapped value of a Unicode character.
  111.      * @param index the character to get the mapped value with
  112.      * @return the mapped value of the given character
  113.      */
  114.     public short elementAt(char index) // parameterized on short
  115.     {
  116.         return (values[(indices[index >> BLOCKSHIFT] & 0xFFFF)
  117.                        + (index & BLOCKMASK)]);
  118.     }
  119.     /**
  120.      * Set a new value for a Unicode character.
  121.      * Set automatically expands the array if it is compacted.
  122.      * @param index the character to set the mapped value with
  123.      * @param value the new mapped value
  124.      */
  125.     public void setElementAt(char index, short value)
  126.     {
  127.         if (isCompact)
  128.             expand();
  129.         values[(int)index] = value;
  130.     }
  131.     /**
  132.      * Set new values for a range of Unicode character.
  133.      * @param start the starting offset of the range
  134.      * @param end the ending offset of the range
  135.      * @param value the new mapped value
  136.      */
  137.     public void setElementAt(char start, char end, short value)
  138.     {
  139.         int i;
  140.         if (isCompact) {
  141.             expand();
  142.         }
  143.         for (i = start; i <= end; ++i) {
  144.             values[i] = value;
  145.         }
  146.     }
  147.     /**
  148.       *Compact the array.
  149.       */
  150.     public void compact()
  151.     {
  152.         if (isCompact == false) {
  153.             char[]      tempIndex;
  154.             int                     tempIndexCount;
  155.             short[]         tempArray;
  156.             short           iBlock, iIndex;
  157.  
  158.             // make temp storage, larger than we need
  159.             tempIndex = new char[UNICODECOUNT];
  160.             // set up first block.
  161.             tempIndexCount = BLOCKCOUNT;
  162.             for (iIndex = 0; iIndex < BLOCKCOUNT; ++iIndex) {
  163.                 tempIndex[iIndex] = (char)iIndex;
  164.             }; // endfor (iIndex = 0; .....)
  165.             indices[0] = (short)0;
  166.  
  167.             // for each successive block, find out its first position
  168.             // in the compacted array
  169.             for (iBlock = 1; iBlock < INDEXCOUNT; ++iBlock) {
  170.                 int     newCount, firstPosition, block;
  171.                 block = iBlock<<BLOCKSHIFT;
  172.                 if (DEBUGSMALL) if (block > DEBUGSMALLLIMIT) break;
  173.                 firstPosition = FindOverlappingPosition(block, tempIndex,
  174.                                                         tempIndexCount);
  175.  
  176.                 newCount = firstPosition + BLOCKCOUNT;
  177.                 if (newCount > tempIndexCount) {
  178.                     for (iIndex = (short)tempIndexCount;
  179.                          iIndex < newCount;
  180.                          ++iIndex) {
  181.                         tempIndex[iIndex]
  182.                             = (char)(iIndex - firstPosition + block);
  183.                     } // endfor (iIndex = tempIndexCount....)
  184.                     tempIndexCount = newCount;
  185.                 } // endif (newCount > tempIndexCount)
  186.                 indices[iBlock] = (short)firstPosition;
  187.             } // endfor (iBlock = 1.....)
  188.  
  189.             // now allocate and copy the items into the array
  190.             tempArray = new short[tempIndexCount];
  191.             for (iIndex = 0; iIndex < tempIndexCount; ++iIndex) {
  192.                 tempArray[iIndex] = values[tempIndex[iIndex]];
  193.             }
  194.             values = null;
  195.             values = tempArray;
  196.             isCompact = true;
  197.         } // endif (isCompact != false)
  198.     }
  199.     /** For internal use only.  Do not modify the result, the behavior of
  200.       * modified results are undefined.
  201.       */
  202.     public short getIndexArray()[]
  203.     {
  204.         return indices;
  205.     }
  206.     /** For internal use only.  Do not modify the result, the behavior of
  207.       * modified results are undefined.
  208.       */
  209.     public short getStringArray()[]
  210.     {
  211.         return values;
  212.     }
  213.     /**
  214.      * Overrides Cloneable
  215.      */
  216.     public Object clone()
  217.     {
  218.         try {
  219.             CompactShortArray other = (CompactShortArray) super.clone();
  220.             other.values = (short[])values.clone();
  221.             other.indices = (short[])indices.clone();
  222.             return other;
  223.         } catch (CloneNotSupportedException e) {
  224.             throw new InternalError();
  225.         }
  226.     }
  227.     /**
  228.      * Compares the equality of two compact array objects.
  229.      * @param obj the compact array object to be compared with this.
  230.      * @return true if the current compact array object is the same
  231.      * as the compact array object obj; false otherwise.
  232.      */
  233.     public boolean equals(Object obj) {
  234.         if (this == obj)                      // quick check
  235.             return true;
  236.         if (getClass() != obj.getClass())         // same class?
  237.             return false;
  238.         CompactShortArray other = (CompactShortArray) obj;
  239.         for (int i = 0; i < UNICODECOUNT; i++) {
  240.             // could be sped up later
  241.             if (elementAt((char)i) != other.elementAt((char)i))
  242.                 return false;
  243.         }
  244.         return true; // we made it through the guantlet.
  245.     }
  246.     /**
  247.      * Generates the hash code for the compact array object
  248.      */
  249.  
  250.     public int hashCode() {
  251.         int result = 0;
  252.         int increment = Math.min(3, values.length/16);
  253.         for (int i = 0; i < values.length; i+= increment) {
  254.             result = result * 37 + values[i];
  255.         }
  256.         return result;
  257.     }
  258.     // --------------------------------------------------------------
  259.     // package private
  260.     // --------------------------------------------------------------
  261.     void writeArrays()
  262.     {
  263.         int i;
  264.         int cnt = ((values.length > 0) ? values.length :
  265.                    (values.length + UNICODECOUNT));
  266.         System.out.println("{");
  267.         for (i = 0; i < INDEXCOUNT-1; i++)
  268.         {
  269.             System.out.print("(short)" + (int)((getIndexArrayValue(i) >= 0) ?
  270.                 (int)getIndexArrayValue(i) :
  271.                 (int)(getIndexArrayValue(i)+UNICODECOUNT)) + ", ");
  272.             if (i != 0)
  273.                 if (i % 10 == 0)
  274.                     System.out.println();
  275.         }
  276.         System.out.println("(short)" +
  277.                            (int)((getIndexArrayValue(INDEXCOUNT-1) >= 0) ?
  278.                                  (int)getIndexArrayValue(i) :
  279.                                  (int)(getIndexArrayValue(i)+UNICODECOUNT)) +
  280.                            " }");
  281.         System.out.println("{");
  282.         for (i = 0; i < cnt-1; i++)
  283.         {
  284.             System.out.print("(short)" + (int)getArrayValue(i) + ", ");
  285.             if (i != 0)
  286.                 if (i % 10 == 0)
  287.                     System.out.println();
  288.         }
  289.         System.out.println("(short)" + (int)getArrayValue(cnt-1) + " }");
  290.     }
  291.     // Print char Array  : Debug only
  292.     void printIndex(short start, short count)
  293.     {
  294.         int i;
  295.         for (i = start; i < count; ++i)
  296.         {
  297.             System.out.println(i + " -> : " +
  298.                                (int)((indices[i] >= 0) ?
  299.                                      indices[i] :
  300.                                      indices[i] + UNICODECOUNT));
  301.         }
  302.         System.out.println();
  303.     }
  304.     void printPlainArray(int start,int count, char[] tempIndex)
  305.     {
  306.         int iIndex;
  307.         if (tempIndex != null)
  308.         {
  309.             for (iIndex     = start; iIndex < start + count; ++iIndex)
  310.             {
  311.                 System.out.print(" " + (int)getArrayValue(tempIndex[iIndex]));
  312.             }
  313.         }
  314.         else
  315.         {
  316.             for (iIndex = start; iIndex < start + count; ++iIndex)
  317.             {
  318.                 System.out.print(" " + (int)getArrayValue(iIndex));
  319.             }
  320.         }
  321.         System.out.println("    Range: start " + start + " , count " + count);
  322.     }
  323.     // --------------------------------------------------------------
  324.     // private
  325.     // --------------------------------------------------------------
  326.     /**
  327.       * Expanding takes the array back to a 65536 element array.
  328.       */
  329.     private void expand()
  330.     {
  331.         int i;
  332.         if (isCompact) {
  333.             short[] tempArray;
  334.             tempArray = new short[UNICODECOUNT];
  335.             for (i = 0; i < UNICODECOUNT; ++i) {
  336.                 tempArray[i] = elementAt((char)i);
  337.             }
  338.             for (i = 0; i < INDEXCOUNT; ++i) {
  339.                 indices[i] = (short)(i<<BLOCKSHIFT);
  340.             }
  341.             values = null;
  342.             values = tempArray;
  343.             isCompact = false;
  344.         }
  345.     }
  346.     // # of elements in the indexed array
  347.     private short capacity()
  348.     {
  349.         return (short)values.length;
  350.     }
  351.     private short getArrayValue(int n)
  352.     {
  353.         return values[n];
  354.     }
  355.     private short getIndexArrayValue(int n)
  356.     {
  357.         return indices[n];
  358.     }
  359.     private int
  360.     FindOverlappingPosition(int start, char[] tempIndex, int tempIndexCount)
  361.     {
  362.         int i;
  363.         short j;
  364.         short currentCount;
  365.  
  366.         if (DEBUGOVERLAP && start < DEBUGSHOWOVERLAPLIMIT) {
  367.             printPlainArray(start, BLOCKCOUNT, null);
  368.             printPlainArray(0, tempIndexCount, tempIndex);
  369.         }
  370.         for (i = 0; i < tempIndexCount; i += BLOCKCOUNT) {
  371.             currentCount = (short)BLOCKCOUNT;
  372.             if (i + BLOCKCOUNT > tempIndexCount) {
  373.                 currentCount = (short)(tempIndexCount - i);
  374.             }
  375.             for (j = 0; j < currentCount; ++j) {
  376.                 if (values[start + j] != values[tempIndex[i + j]]) break;
  377.             }
  378.             if (j == currentCount) break;
  379.         }
  380.         if (DEBUGOVERLAP && start < DEBUGSHOWOVERLAPLIMIT) {
  381.             for (j = 1; j < i; ++j) {
  382.                 System.out.print(" ");
  383.             }
  384.             printPlainArray(start, BLOCKCOUNT, null);
  385.             System.out.println("    Found At: " + i);
  386.         }
  387.         return i;
  388.     }
  389.  
  390.     private static  final int DEBUGSHOWOVERLAPLIMIT = 100;
  391.     private static  final boolean DEBUGTRACE = false;
  392.     private static  final boolean DEBUGSMALL = false;
  393.     private static  final boolean DEBUGOVERLAP = false;
  394.     private static  final int DEBUGSMALLLIMIT = 30000;
  395.     private static  final int BLOCKSHIFT =7;
  396.     private static  final int BLOCKCOUNT =(1<<BLOCKSHIFT);
  397.     private static  final int INDEXSHIFT =(16-BLOCKSHIFT);
  398.     private static  final int INDEXCOUNT =(1<<INDEXSHIFT);
  399.     private static  final int BLOCKMASK = BLOCKCOUNT - 1;
  400.  
  401.     private short values[];  // char -> short (char parameterized short)
  402.     private short indices[];
  403.     private boolean isCompact;
  404. };
  405.