View Javadoc

1   /*
2    *  XNap - A P2P framework and client.
3    *
4    *  See the file AUTHORS for copyright information.
5    *
6    *  This program is free software; you can redistribute it and/or modify
7    *  it under the terms of the GNU General Public License as published by
8    *  the Free Software Foundation.
9    *
10   *  This program is distributed in the hope that it will be useful,
11   *  but WITHOUT ANY WARRANTY; without even the implied warranty of
12   *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
13   *  GNU General Public License for more details.
14   *
15   *  You should have received a copy of the GNU General Public License
16   *  along with this program; if not, write to the Free Software
17   *  Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA  02111-1307  USA
18   */
19  
20  package org.xnap.util;
21  
22  import java.util.HashSet;
23  import java.util.Iterator;
24  import java.util.LinkedList;
25  import java.util.List;
26  import java.util.Map;
27  import java.util.StringTokenizer;
28  import java.util.TreeMap;
29  
30  public class SearchTree {
31  
32      //--- Constant(s) ---
33      
34      // --- Data Field(s) ---
35  
36      private Node root = new Node();
37      
38      // --- Constructor(s) ---
39      
40      public SearchTree()
41      {
42      }
43  
44      // --- Method(s) ---
45  
46      /***
47       * Adds <code>f</code> to search tree.
48       */
49      public void add(String text, Object o)
50      {
51  		text = StringHelper.stripExtra(text);
52  		StringTokenizer t = new StringTokenizer(text.toLowerCase(), " ");
53  		while (t.hasMoreTokens()) {
54  			Node node = root;
55  			String s = t.nextToken();
56  			for (int i = 0; i < s.length(); i++) {
57  				Character c = new Character(s.charAt(i));
58  				Node child = (Node)node.children.get(c);
59  				if (child == null) {
60  					child = new Node();
61  					node.children.put(c, child);
62  				}
63  				node = child;
64  			}
65  			node.objects.add(o);
66  		}
67      }
68  
69  	public boolean contains(String searchText, Object o) 
70  	{
71  		HashSet results = search(searchText);
72  		for (Iterator i = results.iterator(); i.hasNext();) {
73  			if (o.equals(i.next())) {
74  				return true;
75  			}
76  		}
77  		return false;
78  	}
79  
80      public HashSet search(String searchText)
81      {
82  		HashSet results = new HashSet();
83  		searchText = StringHelper.stripExtra(searchText);
84  		StringTokenizer t 
85  			= new StringTokenizer(searchText.toLowerCase(), " ");
86  
87  		boolean firstRun = true;
88  		while (t.hasMoreTokens()) {
89  			Node node = root;
90  			String s = t.nextToken();
91  			for (int i = 0; i < s.length(); i++) {
92  				Character c = new Character(s.charAt(i));
93  				node = (Node)node.children.get(c);
94  				if (node == null) {
95  					return null;
96  				}
97  			}
98  			if (firstRun) {
99  				for (Iterator i = node.objects.iterator(); i.hasNext();) {
100 					results.add(i.next());
101 				}
102 			}
103 			else {
104 				// tokens are AND related
105 				// build intersection between results of last run and results of
106 				// this run 
107 				HashSet newResults = new HashSet();
108 				for (Iterator i = node.objects.iterator(); i.hasNext();) {
109 					Object o = i.next();
110 					if (results.contains(o)) {
111 						newResults.add(o);
112 					}
113 				}
114 				results = newResults;
115 
116 				if (results.size() == 0) {
117 					return null;
118 				}
119 			}
120 			firstRun = false;
121 		}
122 
123 		return results;
124     }
125 
126     //--- Inner Class(es) ---
127 
128     private class Node {
129 	
130 		List objects = new LinkedList();
131 		Map children = new TreeMap();
132 
133     }
134 
135 }