1. /*

  2.  * The Apache Software License, Version 1.1

  3.  *

  4.  *

  5.  * Copyright (c) 1999-2002 The Apache Software Foundation.  All rights 

  6.  * reserved.

  7.  *

  8.  * Redistribution and use in source and binary forms, with or without

  9.  * modification, are permitted provided that the following conditions

  10.  * are met:

  11.  *

  12.  * 1. Redistributions of source code must retain the above copyright

  13.  *    notice, this list of conditions and the following disclaimer. 

  14.  *

  15.  * 2. Redistributions in binary form must reproduce the above copyright

  16.  *    notice, this list of conditions and the following disclaimer in

  17.  *    the documentation and/or other materials provided with the

  18.  *    distribution.

  19.  *

  20.  * 3. The end-user documentation included with the redistribution,

  21.  *    if any, must include the following acknowledgment:  

  22.  *       "This product includes software developed by the

  23.  *        Apache Software Foundation (http://www.apache.org/)."

  24.  *    Alternately, this acknowledgment may appear in the software itself,

  25.  *    if and wherever such third-party acknowledgments normally appear.

  26.  *

  27.  * 4. The names "Xerces" and "Apache Software Foundation" must

  28.  *    not be used to endorse or promote products derived from this

  29.  *    software without prior written permission. For written 

  30.  *    permission, please contact apache@apache.org.

  31.  *

  32.  * 5. Products derived from this software may not be called "Apache",

  33.  *    nor may "Apache" appear in their name, without prior written

  34.  *    permission of the Apache Software Foundation.

  35.  *

  36.  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED

  37.  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES

  38.  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE

  39.  * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR

  40.  * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

  41.  * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

  42.  * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF

  43.  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND

  44.  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,

  45.  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT

  46.  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF

  47.  * SUCH DAMAGE.

  48.  * ====================================================================

  49.  *

  50.  * This software consists of voluntary contributions made by many

  51.  * individuals on behalf of the Apache Software Foundation and was

  52.  * originally based on software copyright (c) 1999, International

  53.  * Business Machines, Inc., http://www.apache.org.  For more

  54.  * information on the Apache Software Foundation, please see

  55.  * <http://www.apache.org/>.

  56.  */

  57. 

  58. package com.sun.org.apache.xerces.internal.impl.xpath.regex;

  59. 

  60. import java.text.CharacterIterator;

  61. 

  62. /**

  63.  * Boyer-Moore searcher.

  64.  *

  65.  * @version $Id: BMPattern.java,v 1.3 2002/08/09 15:18:17 neilg Exp $

  66.  */

  67. public class BMPattern {

  68.     char[] pattern;

  69.     int[] shiftTable;

  70.     boolean ignoreCase;

  71. 

  72.     public BMPattern(String pat, boolean ignoreCase) {

  73.         this(pat, 256, ignoreCase);

  74.     }

  75. 

  76.     public BMPattern(String pat, int tableSize, boolean ignoreCase) {

  77.         this.pattern = pat.toCharArray();

  78.         this.shiftTable = new int[tableSize];

  79.         this.ignoreCase = ignoreCase;

  80. 

  81.         int length = pattern.length;

  82.         for (int i = 0;  i < this.shiftTable.length;  i ++)

  83.             this.shiftTable[i] = length;

  84. 

  85.         for (int i = 0;  i < length;  i ++) {

  86.             char ch = this.pattern[i];

  87.             int diff = length-i-1;

  88.             int index = ch % this.shiftTable.length;

  89.             if (diff < this.shiftTable[index])

  90.                 this.shiftTable[index] = diff;

  91.             if (this.ignoreCase) {

  92.                 ch = Character.toUpperCase(ch);

  93.                 index = ch % this.shiftTable.length;

  94.                 if (diff < this.shiftTable[index])

  95.                     this.shiftTable[index] = diff;

  96.                 ch = Character.toLowerCase(ch);

  97.                 index = ch % this.shiftTable.length;

  98.                 if (diff < this.shiftTable[index])

  99.                     this.shiftTable[index] = diff;

  100.             }

  101.         }

  102.     }

  103. 

  104.     /**

  105.      *

  106.      * @return -1 if <var>iterator</var> does not contain this pattern.

  107.      */

  108.     public int matches(CharacterIterator iterator, int start, int limit) {

  109.         if (this.ignoreCase)  return this.matchesIgnoreCase(iterator, start, limit);

  110.         int plength = this.pattern.length;

  111.         if (plength == 0)  return start;

  112.         int index = start+plength;

  113.         while (index <= limit) {

  114.             int pindex = plength;

  115.             int nindex = index+1;

  116.             char ch;

  117.             do {

  118.                 if ((ch = iterator.setIndex(--index)) != this.pattern[--pindex])

  119.                     break;

  120.                 if (pindex == 0)

  121.                     return index;

  122.             } while (pindex > 0);

  123.             index += this.shiftTable[ch % this.shiftTable.length]+1;

  124.             if (index < nindex)  index = nindex;

  125.         }

  126.         return -1;

  127.     }

  128. 

  129.     /**

  130.      *

  131.      * @return -1 if <var>str</var> does not contain this pattern.

  132.      */

  133.     public int matches(String str, int start, int limit) {

  134.         if (this.ignoreCase)  return this.matchesIgnoreCase(str, start, limit);

  135.         int plength = this.pattern.length;

  136.         if (plength == 0)  return start;

  137.         int index = start+plength;

  138.         while (index <= limit) {

  139.             //System.err.println("Starts at "+index);

  140.             int pindex = plength;

  141.             int nindex = index+1;

  142.             char ch;

  143.             do {

  144.                 if ((ch = str.charAt(--index)) != this.pattern[--pindex])

  145.                     break;

  146.                 if (pindex == 0)

  147.                     return index;

  148.             } while (pindex > 0);

  149.             index += this.shiftTable[ch % this.shiftTable.length]+1;

  150.             if (index < nindex)  index = nindex;

  151.         }

  152.         return -1;

  153.     }

  154.     /**

  155.      *

  156.      * @return -1 if <var>chars</char> does not contain this pattern.

  157.      */

  158.     public int matches(char[] chars, int start, int limit) {

  159.         if (this.ignoreCase)  return this.matchesIgnoreCase(chars, start, limit);

  160.         int plength = this.pattern.length;

  161.         if (plength == 0)  return start;

  162.         int index = start+plength;

  163.         while (index <= limit) {

  164.             //System.err.println("Starts at "+index);

  165.             int pindex = plength;

  166.             int nindex = index+1;

  167.             char ch;

  168.             do {

  169.                 if ((ch = chars[--index]) != this.pattern[--pindex])

  170.                     break;

  171.                 if (pindex == 0)

  172.                     return index;

  173.             } while (pindex > 0);

  174.             index += this.shiftTable[ch % this.shiftTable.length]+1;

  175.             if (index < nindex)  index = nindex;

  176.         }

  177.         return -1;

  178.     }

  179. 

  180.     int matchesIgnoreCase(CharacterIterator iterator, int start, int limit) {

  181.         int plength = this.pattern.length;

  182.         if (plength == 0)  return start;

  183.         int index = start+plength;

  184.         while (index <= limit) {

  185.             int pindex = plength;

  186.             int nindex = index+1;

  187.             char ch;

  188.             do {

  189.                 char ch1 = ch = iterator.setIndex(--index);

  190.                 char ch2 = this.pattern[--pindex];

  191.                 if (ch1 != ch2) {

  192.                     ch1 = Character.toUpperCase(ch1);

  193.                     ch2 = Character.toUpperCase(ch2);

  194.                     if (ch1 != ch2 && Character.toLowerCase(ch1) != Character.toLowerCase(ch2))

  195.                         break;

  196.                 }

  197.                 if (pindex == 0)

  198.                     return index;

  199.             } while (pindex > 0);

  200.             index += this.shiftTable[ch % this.shiftTable.length]+1;

  201.             if (index < nindex)  index = nindex;

  202.         }

  203.         return -1;

  204.     }

  205.     

  206.     int matchesIgnoreCase(String text, int start, int limit) {

  207.         int plength = this.pattern.length;

  208.         if (plength == 0)  return start;

  209.         int index = start+plength;

  210.         while (index <= limit) {

  211.             int pindex = plength;

  212.             int nindex = index+1;

  213.             char ch;

  214.             do {

  215.                 char ch1 = ch = text.charAt(--index);

  216.                 char ch2 = this.pattern[--pindex];

  217.                 if (ch1 != ch2) {

  218.                     ch1 = Character.toUpperCase(ch1);

  219.                     ch2 = Character.toUpperCase(ch2);

  220.                     if (ch1 != ch2 && Character.toLowerCase(ch1) != Character.toLowerCase(ch2))

  221.                         break;

  222.                 }

  223.                 if (pindex == 0)

  224.                     return index;

  225.             } while (pindex > 0);

  226.             index += this.shiftTable[ch % this.shiftTable.length]+1;

  227.             if (index < nindex)  index = nindex;

  228.         }

  229.         return -1;

  230.     }

  231.     int matchesIgnoreCase(char[] chars, int start, int limit) {

  232.         int plength = this.pattern.length;

  233.         if (plength == 0)  return start;

  234.         int index = start+plength;

  235.         while (index <= limit) {

  236.             int pindex = plength;

  237.             int nindex = index+1;

  238.             char ch;

  239.             do {

  240.                 char ch1 = ch = chars[--index];

  241.                 char ch2 = this.pattern[--pindex];

  242.                 if (ch1 != ch2) {

  243.                     ch1 = Character.toUpperCase(ch1);

  244.                     ch2 = Character.toUpperCase(ch2);

  245.                     if (ch1 != ch2 && Character.toLowerCase(ch1) != Character.toLowerCase(ch2))

  246.                         break;

  247.                 }

  248.                 if (pindex == 0)

  249.                     return index;

  250.             } while (pindex > 0);

  251.             index += this.shiftTable[ch % this.shiftTable.length]+1;

  252.             if (index < nindex)  index = nindex;

  253.         }

  254.         return -1;

  255.     }

  256. 

  257.     /*

  258.     public static void main(String[] argv) {

  259.         try {

  260.             int[] shiftTable = new int[256];

  261.             initializeBoyerMoore(argv[0], shiftTable, true);

  262.             int o = -1;

  263.             CharacterIterator ite = new java.text.StringCharacterIterator(argv[1]);

  264.             long start = System.currentTimeMillis();

  265.             //for (int i = 0;  i < 10000;  i ++)

  266.                 o = searchIgnoreCasesWithBoyerMoore(ite, 0, argv[0], shiftTable);

  267.             start = System.currentTimeMillis()-start;

  268.             System.out.println("Result: "+o+", Elapsed: "+start);

  269.         } catch (Exception ex) {

  270.             ex.printStackTrace();

  271.         }

  272.     }*/

  273. }

  274.