1 /* 2 * $Id: SyntaxTree.java,v 1.8 2003/11/07 20:16:24 dfs Exp $ 3 * 4 * ==================================================================== 5 * The Apache Software License, Version 1.1 6 * 7 * Copyright (c) 2000 The Apache Software Foundation. All rights 8 * reserved. 9 * 10 * Redistribution and use in source and binary forms, with or without 11 * modification, are permitted provided that the following conditions 12 * are met: 13 * 14 * 1. Redistributions of source code must retain the above copyright 15 * notice, this list of conditions and the following disclaimer. 16 * 17 * 2. Redistributions in binary form must reproduce the above copyright 18 * notice, this list of conditions and the following disclaimer in 19 * the documentation and/or other materials provided with the 20 * distribution. 21 * 22 * 3. The end-user documentation included with the redistribution, 23 * if any, must include the following acknowledgment: 24 * "This product includes software developed by the 25 * Apache Software Foundation (http://www.apache.org/)." 26 * Alternately, this acknowledgment may appear in the software itself, 27 * if and wherever such third-party acknowledgments normally appear. 28 * 29 * 4. The names "Apache" and "Apache Software Foundation", "Jakarta-Oro" 30 * must not be used to endorse or promote products derived from this 31 * software without prior written permission. For written 32 * permission, please contact apache@apache.org. 33 * 34 * 5. Products derived from this software may not be called "Apache" 35 * or "Jakarta-Oro", nor may "Apache" or "Jakarta-Oro" appear in their 36 * name, without prior written permission of the Apache Software Foundation. 37 * 38 * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED 39 * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES 40 * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 41 * DISCLAIMED. IN NO EVENT SHALL THE APACHE SOFTWARE FOUNDATION OR 42 * ITS CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 43 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 44 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF 45 * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND 46 * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 47 * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT 48 * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF 49 * SUCH DAMAGE. 50 * ==================================================================== 51 * 52 * This software consists of voluntary contributions made by many 53 * individuals on behalf of the Apache Software Foundation. For more 54 * information on the Apache Software Foundation, please see 55 * <http://www.apache.org/>. 56 */ 57 58 59 package org.apache.oro.text.awk; 60 61 import java.util.*; 62 63 /* 64 * IMPORTANT!!!!!!!!!!!!! 65 * Don't forget to optimize this module. The calculation of follow can 66 * be accelerated by calculating first and last only once for each node and 67 * saving instead of doing dynamic calculation every time. 68 */ 69 70 /** 71 * @version @version@ 72 * @since 1.0 73 */ 74 final class SyntaxTree { 75 int _positions; 76 SyntaxNode _root; 77 LeafNode[] _nodes; 78 BitSet[] _followSet; 79 SyntaxTree(SyntaxNode root, int positions)80 SyntaxTree(SyntaxNode root, int positions) { 81 _root = root; 82 _positions = positions; 83 } 84 _computeFollowPositions()85 void _computeFollowPositions() { 86 int index; 87 88 _followSet = new BitSet[_positions]; 89 _nodes = new LeafNode[_positions]; 90 index = _positions; 91 92 while(0 < index--) 93 _followSet[index] = new BitSet(_positions); 94 95 _root._followPosition(_followSet, _nodes); 96 } 97 __addToFastMap(BitSet pos, boolean[] fastMap, boolean[] done)98 private void __addToFastMap(BitSet pos, boolean[] fastMap, boolean[] done){ 99 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]._matches((char)token); 108 } 109 } 110 } 111 } 112 createFastMap()113 boolean[] createFastMap(){ 114 boolean[] fastMap, done; 115 116 fastMap = new boolean[LeafNode._NUM_TOKENS]; 117 done = new boolean[_positions]; 118 __addToFastMap(_root._firstPosition(), fastMap, done); 119 120 return fastMap; 121 } 122 } 123