001: /*
002: * $Id: SyntaxTree.java,v 1.8 2003/11/07 20:16:24 dfs Exp $
003: *
004: * ====================================================================
005: * The Apache Software License, Version 1.1
006: *
007: * Copyright (c) 2000 The Apache Software Foundation. All rights
008: * reserved.
009: *
010: * Redistribution and use in source and binary forms, with or without
011: * modification, are permitted provided that the following conditions
012: * are met:
013: *
014: * 1. Redistributions of source code must retain the above copyright
015: * notice, this list of conditions and the following disclaimer.
016: *
017: * 2. Redistributions in binary form must reproduce the above copyright
018: * notice, this list of conditions and the following disclaimer in
019: * the documentation and/or other materials provided with the
020: * distribution.
021: *
022: * 3. The end-user documentation included with the redistribution,
023: * if any, must include the following acknowledgment:
024: * "This product includes software developed by the
025: * Apache Software Foundation (http://www.apache.org/)."
026: * Alternately, this acknowledgment may appear in the software itself,
027: * if and wherever such third-party acknowledgments normally appear.
028: *
029: * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro"
030: * must not be used to endorse or promote products derived from this
031: * software without prior written permission. For written
032: * permission, please contact apache@apache.org.
033: *
034: * 5. Products derived from this software may not be called "Apache"
035: * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their
036: * name, without prior written permission of the Apache Software Foundation.
037: *
038: * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
039: * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
040: * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
041: * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR
042: * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
043: * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
044: * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
045: * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
046: * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
047: * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
048: * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
049: * SUCH DAMAGE.
050: * ====================================================================
051: *
052: * This software consists of voluntary contributions made by many
053: * individuals on behalf of the Apache Software Foundation. For more
054: * information on the Apache Software Foundation, please see
055: * <http://www.apache.org/>.
056: */
057:
058: package org.apache.oro.text.awk;
059:
060: import java.util.*;
061:
062: /*
063: * IMPORTANT!!!!!!!!!!!!!
064: * Don't forget to optimize this module. The calculation of follow can
065: * be accelerated by calculating first and last only once for each node and
066: * saving instead of doing dynamic calculation every time.
067: */
068:
069: /**
070: * @version @version@
071: * @since 1.0
072: */
073: final class SyntaxTree {
074: int _positions;
075: SyntaxNode _root;
076: LeafNode[] _nodes;
077: BitSet[] _followSet;
078:
079: SyntaxTree(SyntaxNode root, int positions) {
080: _root = root;
081: _positions = positions;
082: }
083:
084: void _computeFollowPositions() {
085: int index;
086:
087: _followSet = new BitSet[_positions];
088: _nodes = new LeafNode[_positions];
089: index = _positions;
090:
091: while (0 < index--)
092: _followSet[index] = new BitSet(_positions);
093:
094: _root._followPosition(_followSet, _nodes);
095: }
096:
097: private void __addToFastMap(BitSet pos, boolean[] fastMap,
098: boolean[] done) {
099: int token, node;
100:
101: for (node = 0; node < _positions; node++) {
102: if (pos.get(node) && !done[node]) {
103: done[node] = true;
104:
105: for (token = 0; token < LeafNode._NUM_TOKENS; token++) {
106: if (!fastMap[token])
107: fastMap[token] = _nodes[node]
108: ._matches((char) token);
109: }
110: }
111: }
112: }
113:
114: boolean[] createFastMap() {
115: boolean[] fastMap, done;
116:
117: fastMap = new boolean[LeafNode._NUM_TOKENS];
118: done = new boolean[_positions];
119: __addToFastMap(_root._firstPosition(), fastMap, done);
120:
121: return fastMap;
122: }
123: }
|