KickJava   Java API By Example, From Geeks To Geeks.

Java > Open Source Codes > com > jcorporate > expresso > core > security > filters > FilterTree


1 /* ====================================================================
2  * The Jcorporate Apache Style Software License, Version 1.2 05-07-2002
3  *
4  * Copyright (c) 1995-2002 Jcorporate Ltd. All rights reserved.
5  *
6  * Redistribution and use in source and binary forms, with or without
7  * modification, are permitted provided that the following conditions
8  * are met:
9  *
10  * 1. Redistributions of source code must retain the above copyright
11  * notice, this list of conditions and the following disclaimer.
12  *
13  * 2. Redistributions in binary form must reproduce the above copyright
14  * notice, this list of conditions and the following disclaimer in
15  * the documentation and/or other materials provided with the
16  * distribution.
17  *
18  * 3. The end-user documentation included with the redistribution,
19  * if any, must include the following acknowledgment:
20  * "This product includes software developed by Jcorporate Ltd.
21  * (http://www.jcorporate.com/)."
22  * Alternately, this acknowledgment may appear in the software itself,
23  * if and wherever such third-party acknowledgments normally appear.
24  *
25  * 4. "Jcorporate" and product names such as "Expresso" must
26  * not be used to endorse or promote products derived from this
27  * software without prior written permission. For written permission,
28  * please contact info@jcorporate.com.
29  *
30  * 5. Products derived from this software may not be called "Expresso",
31  * or other Jcorporate product names; nor may "Expresso" or other
32  * Jcorporate product names appear in their name, without prior
33  * written permission of Jcorporate Ltd.
34  *
35  * 6. No product derived from this software may compete in the same
36  * market space, i.e. framework, without prior written permission
37  * of Jcorporate Ltd. For written permission, please contact
38  * partners@jcorporate.com.
39  *
40  * THIS SOFTWARE IS PROVIDED ``AS IS'' AND ANY EXPRESSED OR IMPLIED
41  * WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES
42  * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
43  * DISCLAIMED. IN NO EVENT SHALL JCORPORATE LTD OR ITS CONTRIBUTORS
44  * BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
45  * EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED
46  * TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF
47  * USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND
48  * ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
49  * OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT
50  * OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
51  * SUCH DAMAGE.
52  * ====================================================================
53  *
54  * This software consists of voluntary contributions made by many
55  * individuals on behalf of the Jcorporate Ltd. Contributions back
56  * to the project(s) are encouraged when you make modifications.
57  * Please send them to support@jcorporate.com. For more information
58  * on Jcorporate Ltd. and its products, please see
59  * <http://www.jcorporate.com/>.
60  *
61  * Portions of this software are based upon other open source
62  * products and are subject to their respective licenses.
63  */
64
65 package com.jcorporate.expresso.core.security.filters;
66
67 import com.jcorporate.expresso.core.misc.ReusableChar;
68 import com.jcorporate.expresso.kernel.util.FastStringBuffer;
69
70
71 /**
72  * A filter tree is a data structure that allows for quick matching and replacement
73  * of strings. Use it for a fast 'search and replace' system. Construction
74  * and setup is a fairly expensive operation in comparison to the actual searching,
75  * so use it for static types of filters that are usually instantiated for a long time.
76  *
77  * @author Michael Rimov
78  */
79 public class FilterTree {
80     protected FilterTreeNode root;
81
82     public FilterTree() {
83         root = new FilterTreeNode();
84     }
85
86     /**
87      * Insert a filtering string into the parse tree.
88      *
89      * @param specialString the string to look for
90      * @param replacementString the string to replace it with.
91      * @throws Exception if insertNode() or setReplacementstring() fails
92      */
93     public void addFilterString(String JavaDoc specialString, String JavaDoc replacementString)
94             throws Exception JavaDoc {
95         FilterTreeNode insertNode = root;
96
97         for (int i = 0; i < specialString.length(); i++) {
98
99             //
100 //We push both upper and lower case versions onto the tree so that
101 //we effectively have case insensitive searches. Note that both
102 //upper and lower case point to the same subnode.
103 //
104 ReusableChar c = new ReusableChar(ReusableChar.toLowerCase(specialString.charAt(i)));
105             ReusableChar uc = new ReusableChar(ReusableChar.toUpperCase(c.charValue()));
106
107             if (insertNode.subnodeExists(c) || insertNode.subnodeExists(uc)) {
108                 insertNode = insertNode.getSubnode(c);
109             } else {
110                 FilterTreeNode newNode = new FilterTreeNode();
111                 insertNode.setSubnode(c, newNode);
112                 insertNode.setSubnode(uc, newNode);
113                 insertNode = newNode;
114             }
115         }
116
117         //Once we get here, we'll insert at the insertnode the appropriate
118 //Replacement String
119 insertNode.setReplacementString(replacementString);
120     }
121
122     public FilterTreeNode getRootNode() {
123         return root;
124     }
125
126     /**
127      * Filters a string in a search and replace algorithm. Uses a "greedy" approach
128      * so that it gets the biggest "fitting" string to cut.
129      *
130      * @param input character array to examine.
131      * @return The filtered string
132      */
133     public String JavaDoc replaceFilter(char[] input) {
134         FastStringBuffer fsb = FastStringBuffer.getInstance();
135         String JavaDoc returnValue = null;
136         try {
137             int mark = -1;
138             ReusableChar c = new ReusableChar('a'); //Dummy Value
139 FilterTreeNode insertNode = root;
140             FilterTreeNode lastMatch = null;
141             String JavaDoc s = null;
142
143             if (input.length == 0) {
144                 return ("");
145             }
146             for (int i = 0; i < input.length; i++) {
147                 c.setCharValue(input[i]);
148
149                 FilterTreeNode n = pushOntoParseTree(c, insertNode);
150
151                 if (n == null) {
152
153                     //We're at a leaf and we have to do something.
154 if (insertNode == root) {
155                         fsb.append(c.charValue());
156
157                         //If this node is root - just dump the character.
158 } else if (s != null) {
159                         fsb.append(s);
160                         i--;
161
162                         //If there was a match further up the tree.
163 } else if (lastMatch != null) {
164                         fsb.append(lastMatch.getReplacementString());
165                         i = mark; //We have to rewind to the last match because
166
167                         //what follows may have been in the root of the
168 //tree.
169 //False alarm, append everything that has been in this tree.
170 } else {
171                         i = mark; //Rewind to the last marked place
172 fsb.append(input, mark, i - mark + 1);
173                     }
174
175                     insertNode = root;
176                     mark = -1;
177                     lastMatch = null;
178                     s = null;
179                 } else {
180                     insertNode = n;
181
182                     //Check to see if there's any match for what we've got so far.
183 s = insertNode.getReplacementString();
184
185                     if (s != null) {
186                         lastMatch = insertNode;
187                         mark = i;
188                     } else if (mark == -1) {
189                         mark = i;
190                     }
191                 }
192             }
193             //We just ran out of characters. We have to dump any last matches
194 //on the tree and the rest of the characters.
195 if (s != null) {
196                 fsb.append(s);
197
198                 //If this node is root - just dump the character.
199 //If there was a match further up the tree.
200 } else if (lastMatch != null) {
201                 fsb.append(lastMatch.getReplacementString());
202
203                 if (mark < input.length && mark != -1) {
204                     fsb.append(input, mark + 1, input.length - (mark + 1));
205                 }
206
207                 //False alarm, append everything that has been in this tree.
208 } else {
209                 if (mark != -1) {
210                     fsb.append(input, mark, input.length - mark);
211                 }
212             }
213
214             returnValue = fsb.toString();
215         } finally {
216             fsb.release();
217             fsb = null;
218         }
219
220         return returnValue;
221     }
222
223     /**
224      * Function moves things into the parse tree, modifying insertNode, etc
225      * Returns true, if able to push anything into tree. false if no subnodes
226      * exist for this particular character. <br />
227      * <p/>
228      * Note that this is case insensitive.
229      */
230     private FilterTreeNode pushOntoParseTree(ReusableChar c,
231                                              FilterTreeNode insertNode) {
232         if (insertNode.subnodeExists(c)) {
233             return insertNode.getSubnode(c);
234         } else {
235             return null;
236         }
237     }
238 }
Popular Tags