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