1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20 package org.xnap.commons.gui.completion;
21
22 import java.util.Arrays;
23 import java.util.Collection;
24 import java.util.Comparator;
25 import java.util.LinkedList;
26 import java.util.List;
27 import java.util.Stack;
28 import javax.swing.DefaultComboBoxModel;
29
30 /***
31 * This classl uses a ternary search tree for completion.
32 * <p>
33 * You can easily add arrays of objects to it and remove single object if
34 * they should not show up as possible completions anymore.
35 * <p>
36 * A {@link #toArray()} method gives access to all objects stored in the model
37 * and can be used for serialization.
38 * <p>
39 * See also {@link org.xnap.commons.settings.CompletionSettingDirector}.
40 *
41 * @author Felix Berger
42 */
43 public class DefaultCompletionModel extends DefaultComboBoxModel
44 implements CompletionModel
45 {
46 private CharNode root = null;
47
48 /***
49 * Constructs a new model with no items.
50 */
51 public DefaultCompletionModel()
52 {
53 }
54
55 /***
56 * Constructs a new model using the given items for completion.
57 *
58 * @param items the objects used for completion
59 */
60 public DefaultCompletionModel(Object[] items)
61 {
62 this(items, false);
63 }
64
65 /***
66 * Constructs a new model using the given items for completion.
67 *
68 * @param items the array of objects used for completion
69 * @param sorted whether the array of items is sorted or not
70 */
71 public DefaultCompletionModel(Object[] items, boolean sorted)
72 {
73 insert(items, sorted);
74 }
75
76 public boolean complete(String prefix)
77 {
78 removeAllElements();
79
80 if (prefix.length() == 0) {
81
82 }
83 else {
84 CharNode node = search(prefix);
85
86 if (node != null) {
87 if (node.obj != null) {
88 addElement(node.obj);
89 }
90 collectElements(node.eqkid);
91 }
92 }
93 return getSize() > 0;
94 }
95
96 public String completeUniquePrefix(String prefix)
97 {
98 CharNode node = search(prefix);
99
100 if (node != null && node.obj == null && node.eqkid != null) {
101 StringBuilder sb = new StringBuilder(prefix);
102 node = node.eqkid;
103
104 while ((node != null) && (node.lokid == null)
105 && (node.hikid == null)) {
106 sb.append(node.splitchar);
107 if (node.obj != null) {
108 break;
109 }
110 node = node.eqkid;
111 }
112 return sb.toString();
113 }
114 return prefix;
115 }
116
117 /***
118 * Adds an object to the completion model's ternary search tree.
119 *
120 * The object is inserted using its {@link Object#toString()} method. If
121 * another object with the same name exists it is simply replaced by this
122 * one, no equality tests are carried out.
123 *
124 * @param object the object which is completed using its {@link
125 * Object#toString()} method
126 */
127 public void insert(Object object)
128 {
129 char[] key = object.toString().toCharArray();
130 root = insert(root, key, 0, object);
131 }
132
133 /***
134 * Adds an array of objects to the completion model's ternary search tree.
135 *
136 * For large arrays adding the items in one chunk is recommended, this
137 * ensures the search tree is more balanced.
138 *
139 * @param items the array of objects used for completion
140 * @param sorted whether the array of items is sorted or not
141 */
142 public void insert(Object[] items, boolean sorted)
143 {
144 if (!sorted) {
145 Arrays.sort(items, new StringComparator());
146 }
147 insert(items, 0, items.length);
148 }
149
150 /***
151 * Adds an array of objects to the completion model's ternary search tree.
152 *
153 * The array will be sorted before it is added.
154 *
155 * @param items the array of objects used for completion
156 * @see #insert(Object[], boolean)
157 */
158 public void insert(Object[] items)
159 {
160 insert(items, false);
161 }
162
163 /***
164 * Removes the object from the ternary search tree.
165 *
166 * Equality is tested with the {@link Object#equals(Object)} method.
167 *
168 * @param object the object to be removed from the search tree
169 */
170 public void remove(Object object)
171 {
172 CharNode node = root;
173 int index = 0;
174 Stack<CharNode> stack = new Stack<CharNode>();
175 String prefix = object.toString();
176 int prefixLength = prefix.length();
177
178 while (node != null && index < prefixLength) {
179 stack.push(node);
180 char c = prefix.charAt(index);
181
182 if (c < node.splitchar) {
183 node = node.lokid;
184 }
185 else if (c == node.splitchar) {
186 if (index == (prefixLength - 1)) {
187 break;
188 }
189 else {
190 node = node.eqkid;
191 index++;
192 }
193 }
194 else {
195 node = node.hikid;
196 }
197 }
198
199
200 if (node != null && node.obj.equals(object)) {
201 node.obj = null;
202 stack.pop();
203 while (node.obj == null && node.lokid == null
204 && node.hikid == null && !stack.empty()) {
205 node.eqkid = null;
206 node = stack.pop();
207 }
208 }
209 }
210
211 /***
212 * Returns an array containing all of the elements in this completion model.
213 *
214 * The array's elements are sorted alphabetically according to the return
215 * values of {@link Object#toString()}.
216 *
217 * @return an array containing all of the elements in this completion model
218 */
219 public Object[] toArray()
220 {
221 List<Object> list = new LinkedList<Object>();
222 collectElements(root, list);
223 return list.toArray();
224 }
225
226 /***
227 * Clears the model.
228 * <p>
229 * Subsequent calls to {@link #complete(String)} will return
230 * <code>false</code>.
231 */
232 public void clear()
233 {
234 root = null;
235 }
236
237 /***
238 * Adds all child elements of the node to a collection in preorder fashion.
239 * @param node
240 * @param col
241 */
242 private void collectElements(CharNode node, Collection<Object> col)
243 {
244 if (node != null) {
245 collectElements(node.lokid, col);
246 if (node.obj != null) {
247 col.add(node.obj);
248 }
249 collectElements(node.eqkid, col);
250 collectElements(node.hikid, col);
251 }
252 }
253
254 /***
255 * Traverses the tree preorder wise and adds all elements to the model.
256 */
257 private void collectElements(CharNode node)
258 {
259 if (node != null) {
260 collectElements(node.lokid);
261
262 if (node.obj != null) {
263 addElement(node.obj);
264 }
265 collectElements(node.eqkid);
266 collectElements(node.hikid);
267 }
268 }
269
270 private void insert(Object[] items, int left, int right)
271 {
272 if (left < right) {
273 int m = left + (int)Math.floor((right - left) / 2);
274 insert(items[m]);
275 insert(items, left, m);
276 insert(items, m + 1, right);
277 }
278 }
279
280 private CharNode insert(CharNode node, char[] key, int index, Object object)
281 {
282 if (node == null) {
283 node = new CharNode(key[index]);
284
285 if (index == (key.length - 1)) {
286 node.obj = object;
287 }
288 }
289
290 if (key[index] < node.splitchar) {
291 node.lokid = insert(node.lokid, key, index, object);
292 }
293 else if (key[index] == node.splitchar) {
294 if (++index < key.length) {
295 node.eqkid = insert(node.eqkid, key, index, object);
296 }
297 else {
298
299 node.obj = object;
300 }
301 }
302 else {
303 node.hikid = insert(node.hikid, key, index, object);
304 }
305
306 return node;
307 }
308
309 /***
310 * Returns node.
311 */
312 private CharNode search(String prefix)
313 {
314 CharNode node = root;
315 int index = 0;
316 int prefixLength = prefix.length();
317
318
319 while (node != null && index < prefixLength) {
320
321
322 char c = prefix.charAt(index);
323
324
325 if (c < node.splitchar) {
326 node = node.lokid;
327 }
328 else if (c == node.splitchar) {
329 if (index == (prefixLength - 1)) {
330 return node;
331 }
332 else {
333 node = node.eqkid;
334 index++;
335 }
336 }
337 else {
338 node = node.hikid;
339 }
340 }
341
342 return node;
343 }
344
345 /***
346 * Implementation of ternary search trees.
347 */
348 private class CharNode
349 {
350 public char splitchar;
351 public CharNode lokid;
352 public CharNode eqkid;
353 public CharNode hikid;
354 public Object obj;
355
356 public CharNode(char value)
357 {
358 splitchar = value;
359 }
360 }
361
362 /***
363 * Comparator used for sorting the elements which are inserted.
364 */
365 private class StringComparator implements Comparator<Object>
366 {
367 public int compare(Object obj1, Object obj2)
368 {
369 return obj1.toString().compareTo(obj2.toString());
370
371 }
372 }
373 }