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 / MergeCollation.java < prev    next >
Encoding:
Java Source  |  1999-05-28  |  11.1 KB  |  318 lines  |  [TEXT/CWIE]
  1. /*
  2.  * @(#)MergeCollation.java    1.12 98/04/22
  3.  *
  4.  * (C) Copyright Taligent, Inc. 1996, 1997 - All Rights Reserved
  5.  * (C) Copyright IBM Corp. 1996, 1997 - 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. package java.text;
  31.  
  32. import java.util.ArrayList;
  33.  
  34. /**
  35.  * Utility class for normalizing and merging patterns for collation.
  36.  * Patterns are strings of the form <entry>*, where <entry> has the
  37.  * form:
  38.  * <pattern> := <entry>*
  39.  * <entry> := <separator><chars>{"/"<extension>}
  40.  * <separator> := "=", ",", ";", "<", "&"
  41.  * <chars>, and <extension> are both arbitrary strings.
  42.  * unquoted whitespaces are ignored.
  43.  * 'xxx' can be used to quote characters
  44.  * One difference from Collator is that & is used to reset to a current
  45.  * point. Or, in other words, it introduces a new sequence which is to
  46.  * be added to the old.
  47.  * That is: "a < b < c < d" is the same as "a < b & b < c & c < d" OR
  48.  * "a < b < d & b < c"
  49.  * XXX: make '' be a single quote.
  50.  * @see PatternEntry
  51.  * @version    1.12 04/22/98
  52.  * @author             Mark Davis, Helena Shih
  53.  */
  54.  
  55. final class MergeCollation {
  56.  
  57.     /**
  58.      * Creates from a pattern
  59.      * @exception ParseException If the input pattern is incorrect.
  60.      */
  61.     public MergeCollation(String pattern) throws ParseException
  62.     {
  63.         for (int i = 0; i < statusArray.length; i++)
  64.             statusArray[i] = 0;
  65.         setPattern(pattern);
  66.     }
  67.  
  68.     /**
  69.      * recovers current pattern
  70.      */
  71.     public String getPattern() {
  72.         return getPattern(true);
  73.     }
  74.  
  75.     /**
  76.      * recovers current pattern.
  77.      * @param withWhiteSpace puts spacing around the entries, and \n
  78.      * before & and <
  79.      */
  80.     public String getPattern(boolean withWhiteSpace) {
  81.         StringBuffer result = new StringBuffer();
  82.         PatternEntry tmp = null;
  83.         ArrayList extList = null;
  84.         int i;
  85.         for (i = 0; i < patterns.size(); ++i) {
  86.             PatternEntry entry = (PatternEntry) patterns.get(i);
  87.             if (entry.extension.length() != 0) {
  88.                 if (extList == null)
  89.                     extList = new ArrayList();
  90.                 extList.add(entry);
  91.             } else {
  92.                 if (extList != null) {
  93.                     PatternEntry last = findLastWithNoExtension(i-1);
  94.                     for (int j = extList.size() - 1; j >= 0 ; j--) {
  95.                         tmp = (PatternEntry)(extList.get(j));
  96.                         tmp.addToBuffer(result, false, withWhiteSpace, last);
  97.                     }
  98.                     extList = null;
  99.                 }
  100.                 entry.addToBuffer(result, false, withWhiteSpace, null);
  101.             }
  102.         }
  103.         if (extList != null) {
  104.             PatternEntry last = findLastWithNoExtension(i-1);
  105.             for (int j = extList.size() - 1; j >= 0 ; j--) {
  106.                 tmp = (PatternEntry)(extList.get(j));
  107.                 tmp.addToBuffer(result, false, withWhiteSpace, last);
  108.             }
  109.             extList = null;
  110.         }
  111.         return result.toString();
  112.     }
  113.  
  114.     private final PatternEntry findLastWithNoExtension(int i) {
  115.         for (--i;i >= 0; --i) {
  116.             PatternEntry entry = (PatternEntry) patterns.get(i);
  117.             if (entry.extension.length() == 0) {
  118.                 return entry;
  119.             }
  120.         }
  121.         return null;
  122.     }
  123.  
  124.     /**
  125.      * emits the pattern for collation builder.
  126.      * @return emits the string in the format understable to the collation
  127.      * builder.
  128.      */
  129.     public String emitPattern() {
  130.         return emitPattern(true);
  131.     }
  132.  
  133.     /**
  134.      * emits the pattern for collation builder.
  135.      * @param withWhiteSpace puts spacing around the entries, and \n
  136.      * before & and <
  137.      * @return emits the string in the format understable to the collation
  138.      * builder.
  139.      */
  140.     public String emitPattern(boolean withWhiteSpace) {
  141.         StringBuffer result = new StringBuffer();
  142.         for (int i = 0; i < patterns.size(); ++i)
  143.         {
  144.             PatternEntry entry = (PatternEntry) patterns.get(i);
  145.             if (entry != null) {
  146.                 entry.addToBuffer(result, true, withWhiteSpace, null);
  147.             }
  148.         }
  149.         return result.toString();
  150.     }
  151.  
  152.     /**
  153.      * sets the pattern.
  154.      */
  155.     public void setPattern(String pattern) throws ParseException
  156.     {
  157.         patterns.clear();
  158.         addPattern(pattern);
  159.     }
  160.  
  161.     /**
  162.      * adds a pattern to the current one.
  163.      * @param pattern the new pattern to be added
  164.      */
  165.     public void addPattern(String pattern) throws ParseException
  166.     {
  167.         if (pattern == null)
  168.             return;
  169.         
  170.         PatternEntry.Parser parser = new PatternEntry.Parser(pattern);
  171.         
  172.         PatternEntry entry = parser.next();
  173.         while (entry != null) {
  174.             fixEntry(entry);
  175.             entry = parser.next();
  176.         }
  177.     }
  178.  
  179.     /**
  180.      * gets count of separate entries
  181.      * @return the size of pattern entries
  182.      */
  183.     public int getCount() {
  184.         return patterns.size();
  185.     }
  186.  
  187.     /**
  188.      * gets count of separate entries
  189.      * @param index the offset of the desired pattern entry
  190.      * @return the requested pattern entry
  191.      */
  192.     public PatternEntry getItemAt(int index) {
  193.         return (PatternEntry) patterns.get(index);
  194.     }
  195.  
  196.     //============================================================
  197.     // privates
  198.     //============================================================
  199.     ArrayList patterns = new ArrayList(); // a list of PatternEntries
  200.  
  201.     private transient PatternEntry saveEntry = null;
  202.     private transient PatternEntry lastEntry = null;
  203.     
  204.     // This is really used as a local variable inside fixEntry, but we cache
  205.     // it here to avoid newing it up every time the method is called.
  206.     private transient StringBuffer excess = new StringBuffer();
  207.  
  208.     //
  209.     // When building a MergeCollation, we need to do lots of searches to see
  210.     // whether a given entry is already in the table.  Since we're using an
  211.     // array, this would make the algorithm O(N*N).  To speed things up, we
  212.     // use this bit array to remember whether the array contains any entries
  213.     // starting with each Unicode character.  If not, we can avoid the search.
  214.     // Using BitSet would make this easier, but it's significantly slower.
  215.     //
  216.     private transient byte[] statusArray = new byte[8192];
  217.     private final byte BITARRAYMASK = (byte)0x1;
  218.     private final int  BYTEPOWER = 3;
  219.     private final int  BYTEMASK = (1 << BYTEPOWER) - 1;
  220.  
  221.     /*
  222.       If the strength is RESET, then just change the lastEntry to
  223.       be the current. (If the current is not in patterns, signal an error).
  224.       If not, then remove the current entry, and add it after lastEntry
  225.       (which is usually at the end).
  226.       */
  227.     private final void fixEntry(PatternEntry newEntry) throws ParseException
  228.     {
  229.         boolean changeLastEntry = true;
  230.         if (newEntry.strength != PatternEntry.RESET) {
  231.             int oldIndex = -1;
  232.  
  233.             if ((newEntry.chars.length() == 1)) {
  234.             
  235.                 char c = newEntry.chars.charAt(0);
  236.                 int statusIndex = c >> BYTEPOWER;
  237.                 byte bitClump = statusArray[statusIndex];
  238.                 byte setBit = (byte)(BITARRAYMASK << (c & BYTEMASK));
  239.                 
  240.                 if (bitClump != 0 && (bitClump & setBit) != 0) {
  241.                     oldIndex = patterns.lastIndexOf(newEntry);
  242.                 } else {
  243.                     // We're going to add an element that starts with this
  244.                     // character, so go ahead and set its bit.
  245.                     statusArray[statusIndex] = (byte)(bitClump | setBit);
  246.                 }
  247.             } else {
  248.                 oldIndex = patterns.lastIndexOf(newEntry);
  249.             }
  250.             if (oldIndex != -1) {
  251.                 patterns.remove(oldIndex);
  252.             }
  253.             
  254.             excess.setLength(0);
  255.             int lastIndex = findLastEntry(lastEntry, excess);
  256.  
  257.             if (excess.length() != 0) {
  258.                 newEntry.extension = excess + newEntry.extension;
  259.                 if (lastIndex != patterns.size()) {
  260.                     lastEntry = saveEntry;
  261.                     changeLastEntry = false;
  262.                 }
  263.             }
  264.             if (lastIndex == patterns.size()) {
  265.                 patterns.add(newEntry);
  266.                 saveEntry = newEntry;
  267.             } else {
  268.                 patterns.add(lastIndex, newEntry);
  269.             }
  270.         }
  271.         if (changeLastEntry) {
  272.             lastEntry = newEntry;
  273.         }
  274.     }
  275.  
  276.     private final int findLastEntry(PatternEntry entry,
  277.                               StringBuffer excessChars) throws ParseException
  278.     {
  279.         if (entry == null)
  280.             return 0;
  281.             
  282.         if (entry.strength != PatternEntry.RESET) {
  283.             // Search backwards for string that contains this one;
  284.             // most likely entry is last one
  285.             
  286.             int oldIndex = -1;
  287.             if ((entry.chars.length() == 1)) {
  288.                 int index = entry.chars.charAt(0) >> BYTEPOWER;
  289.                 if ((statusArray[index] &
  290.                     (BITARRAYMASK << (entry.chars.charAt(0) & BYTEMASK))) != 0) {
  291.                     oldIndex = patterns.lastIndexOf(entry);
  292.                 }
  293.             } else {
  294.                 oldIndex = patterns.lastIndexOf(entry);
  295.             }
  296.             if ((oldIndex == -1))
  297.                 throw new ParseException("couldn't find last entry: "
  298.                                           + entry, oldIndex);
  299.             return oldIndex + 1;
  300.         } else {
  301.             int i;
  302.             for (i = patterns.size() - 1; i >= 0; --i) {
  303.                 PatternEntry e = (PatternEntry) patterns.get(i);
  304.                 if (e.chars.regionMatches(0,entry.chars,0,
  305.                                               e.chars.length())) {
  306.                     excessChars.append(entry.chars.substring(e.chars.length(),
  307.                                                             entry.chars.length()));
  308.                     break;
  309.                 }
  310.             }
  311.             if (i == -1)
  312.                 throw new ParseException("couldn't find: " + entry, i);
  313.             return i + 1;
  314.         }
  315.     }
  316. }
  317.  
  318.