rangetoken.java

来自「JAVA的一些源码 JAVA2 STANDARD EDITION DEVELO」· Java 代码 · 共 652 行 · 第 1/2 页

/*
 * The Apache Software License, Version 1.1
 *
 *
 * Copyright (c) 1999-2002 The Apache Software Foundation.  All rights 
 * reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 *
 * 1. Redistributions of source code must retain the above copyright
 *    notice, this list of conditions and the following disclaimer. 
 *
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice, this list of conditions and the following disclaimer in
 *    the documentation and/or other materials provided with the
 *    distribution.
 *
 * 3. The end-user documentation included with the redistribution,
 *    if any, must include the following acknowledgment:  
 *       "This product includes software developed by the
 *        Apache Software Foundation (http://www.apache.org/)."
 *    Alternately, this acknowledgment may appear in the software itself,
 *    if and wherever such third-party acknowledgments normally appear.
 *
 * 4. The names "Xerces" and "Apache Software Foundation" must
 *    not be used to endorse or promote products derived from this
 *    software without prior written permission. For written 
 *    permission, please contact [e-mail].
 *
 * 5. Products derived from this software may not be called "Apache",
 *    nor may "Apache" appear in their name, without prior written
 *    permission of the Apache Software Foundation.
 *
 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
 * DISCLAIMED.  IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
 * SUCH DAMAGE.
 * ====================================================================
 *
 * This software consists of voluntary contributions made by many
 * individuals on behalf of the Apache Software Foundation and was
 * originally based on software copyright (c) 1999, International
 * Business Machines, Inc., http://www.apache.org.  For more
 * information on the Apache Software Foundation, please see
 * <http://www.apache.org/>.
 */

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

/**
 * This class represents a character class such as [a-z] or a period.
 *
 * @version $Id: RangeToken.java,v 1.4 2002/08/09 15:18:17 neilg Exp $
 */
final class RangeToken extends Token implements java.io.Serializable {

    int[] ranges;
    boolean sorted;
    boolean compacted;
    RangeToken icaseCache = null;
    int[] map = null;
    int nonMapIndex;

    RangeToken(int type) {
        super(type);
        this.setSorted(false);
    }

                                                // for RANGE or NRANGE
    protected void addRange(int start, int end) {
        this.icaseCache = null;
        //System.err.println("Token#addRange(): "+start+" "+end);
        int r1, r2;
        if (start <= end) {
            r1 = start;
            r2 = end;
        } else {
            r1 = end;
            r2 = start;
        }

        int pos = 0;
        if (this.ranges == null) {
            this.ranges = new int[2];
            this.ranges[0] = r1;
            this.ranges[1] = r2;
            this.setSorted(true);
        } else {
            pos = this.ranges.length;
            if (this.ranges[pos-1]+1 == r1) {
                this.ranges[pos-1] = r2;
                return;
            }
            int[] temp = new int[pos+2];
            System.arraycopy(this.ranges, 0, temp, 0, pos);
            this.ranges = temp;
            if (this.ranges[pos-1] >= r1)
                this.setSorted(false);
            this.ranges[pos++] = r1;
            this.ranges[pos] = r2;
            if (!this.sorted)
                this.sortRanges();
        }
    }

    private final boolean isSorted() {
        return this.sorted;
    }
    private final void setSorted(boolean sort) {
        this.sorted = sort;
        if (!sort)  this.compacted = false;
    }
    private final boolean isCompacted() {
        return this.compacted;
    }
    private final void setCompacted() {
        this.compacted = true;
    }

    protected void sortRanges() {
        if (this.isSorted())
            return;
        if (this.ranges == null)
            return;
        //System.err.println("Do sorting: "+this.ranges.length);

                                                // Bubble sort
                                                // Why? -- In many cases,
                                                //         this.ranges has few elements.
        for (int i = this.ranges.length-4;  i >= 0;  i -= 2) {
            for (int j = 0;  j <= i;  j += 2) {
                if (this.ranges[j] > this.ranges[j+2]
                    || this.ranges[j] == this.ranges[j+2] && this.ranges[j+1] > this.ranges[j+3]) {
                    int tmp;
                    tmp = this.ranges[j+2];
                    this.ranges[j+2] = this.ranges[j];
                    this.ranges[j] = tmp;
                    tmp = this.ranges[j+3];
                    this.ranges[j+3] = this.ranges[j+1];
                    this.ranges[j+1] = tmp;
                }
            }
        }
        this.setSorted(true);
    }

    /**
     * this.ranges is sorted.
     */
    protected void compactRanges() {
        boolean DEBUG = false;
        if (this.ranges == null || this.ranges.length <= 2)
            return;
        if (this.isCompacted())
            return;
        int base = 0;                           // Index of writing point
        int target = 0;                         // Index of processing point

        while (target < this.ranges.length) {
            if (base != target) {
                this.ranges[base] = this.ranges[target++];
                this.ranges[base+1] = this.ranges[target++];
            } else
                target += 2;
            int baseend = this.ranges[base+1];
            while (target < this.ranges.length) {
                if (baseend+1 < this.ranges[target])
                    break;
                if (baseend+1 == this.ranges[target]) {
                    if (DEBUG)
                        System.err.println("Token#compactRanges(): Compaction: ["+this.ranges[base]
                                           +", "+this.ranges[base+1]
                                           +"], ["+this.ranges[target]
                                           +", "+this.ranges[target+1]
                                           +"] -> ["+this.ranges[base]
                                           +", "+this.ranges[target+1]
                                           +"]");
                    this.ranges[base+1] = this.ranges[target+1];
                    baseend = this.ranges[base+1];
                    target += 2;
                } else if (baseend >= this.ranges[target+1]) {
                    if (DEBUG)
                        System.err.println("Token#compactRanges(): Compaction: ["+this.ranges[base]
                                           +", "+this.ranges[base+1]
                                           +"], ["+this.ranges[target]
                                           +", "+this.ranges[target+1]
                                           +"] -> ["+this.ranges[base]
                                           +", "+this.ranges[base+1]
                                           +"]");
                    target += 2;
                } else if (baseend < this.ranges[target+1]) {
                    if (DEBUG)
                        System.err.println("Token#compactRanges(): Compaction: ["+this.ranges[base]
                                           +", "+this.ranges[base+1]
                                           +"], ["+this.ranges[target]
                                           +", "+this.ranges[target+1]
                                           +"] -> ["+this.ranges[base]
                                           +", "+this.ranges[target+1]
                                           +"]");
                    this.ranges[base+1] = this.ranges[target+1];
                    baseend = this.ranges[base+1];
                    target += 2;
                } else {
                    throw new RuntimeException("Token#compactRanges(): Internel Error: ["
                                               +this.ranges[base]
                                               +","+this.ranges[base+1]
                                               +"] ["+this.ranges[target]
                                               +","+this.ranges[target+1]+"]");
                }
            } // while
            base += 2;
        }

        if (base != this.ranges.length) {
            int[] result = new int[base];
            System.arraycopy(this.ranges, 0, result, 0, base);
            this.ranges = result;
        }
        this.setCompacted();
    }

    protected void mergeRanges(Token token) {
        RangeToken tok = (RangeToken)token;
        this.sortRanges();
        tok.sortRanges();
        if (tok.ranges == null)
            return;
        this.icaseCache = null;
        this.setSorted(true);
        if (this.ranges == null) {
            this.ranges = new int[tok.ranges.length];
            System.arraycopy(tok.ranges, 0, this.ranges, 0, tok.ranges.length);
            return;
        }
        int[] result = new int[this.ranges.length+tok.ranges.length];
        for (int i = 0, j = 0, k = 0;  i < this.ranges.length || j < tok.ranges.length;) {
            if (i >= this.ranges.length) {
                result[k++] = tok.ranges[j++];
                result[k++] = tok.ranges[j++];
            } else if (j >= tok.ranges.length) {
                result[k++] = this.ranges[i++];
                result[k++] = this.ranges[i++];
            } else if (tok.ranges[j] < this.ranges[i]
                       || tok.ranges[j] == this.ranges[i] && tok.ranges[j+1] < this.ranges[i+1]) {
                result[k++] = tok.ranges[j++];
                result[k++] = tok.ranges[j++];
            } else {
                result[k++] = this.ranges[i++];
                result[k++] = this.ranges[i++];
            }
        }
        this.ranges = result;
    }

    protected void subtractRanges(Token token) {
        if (token.type == NRANGE) {
            this.intersectRanges(token);
            return;
        }
        RangeToken tok = (RangeToken)token;
        if (tok.ranges == null || this.ranges == null)
            return;
        this.icaseCache = null;
        this.sortRanges();
        this.compactRanges();
        tok.sortRanges();
        tok.compactRanges();

        //System.err.println("Token#substractRanges(): Entry: "+this.ranges.length+", "+tok.ranges.length);

        int[] result = new int[this.ranges.length+tok.ranges.length];
        int wp = 0, src = 0, sub = 0;
        while (src < this.ranges.length && sub < tok.ranges.length) {
            int srcbegin = this.ranges[src];
            int srcend = this.ranges[src+1];
            int subbegin = tok.ranges[sub];
            int subend = tok.ranges[sub+1];
            if (srcend < subbegin) {            // Not overlapped
                                                // src: o-----o
                                                // sub:         o-----o
                                                // res: o-----o
                                                // Reuse sub
                result[wp++] = this.ranges[src++];
                result[wp++] = this.ranges[src++];
            } else if (srcend >= subbegin
                       && srcbegin <= subend) { // Overlapped
                                                // src:    o--------o
                                                // sub:  o----o
                                                // sub:      o----o
                                                // sub:          o----o
                                                // sub:  o------------o
                if (subbegin <= srcbegin && srcend <= subend) {
                                                // src:    o--------o
                                                // sub:  o------------o
                                                // res: empty
                                                // Reuse sub
                    src += 2;
                } else if (subbegin <= srcbegin) {
                                                // src:    o--------o
                                                // sub:  o----o
                                                // res:       o-----o
                                                // Reuse src(=res)
                    this.ranges[src] = subend+1;
                    sub += 2;
                } else if (srcend <= subend) {
                                                // src:    o--------o
                                                // sub:          o----o
                                                // res:    o-----o
                                                // Reuse sub
                    result[wp++] = srcbegin;
                    result[wp++] = subbegin-1;
                    src += 2;
                } else {
                                                // src:    o--------o
                                                // sub:      o----o
                                                // res:    o-o    o-o