%line | %branch | |||||||||
---|---|---|---|---|---|---|---|---|---|---|
org.apache.commons.net.nntp.Threader |
|
|
1 | /* |
|
2 | * Copyright 2001-2005 The Apache Software Foundation |
|
3 | * |
|
4 | * Licensed under the Apache License, Version 2.0 (the "License"); |
|
5 | * you may not use this file except in compliance with the License. |
|
6 | * You may obtain a copy of the License at |
|
7 | * |
|
8 | * http://www.apache.org/licenses/LICENSE-2.0 |
|
9 | * |
|
10 | * Unless required by applicable law or agreed to in writing, software |
|
11 | * distributed under the License is distributed on an "AS IS" BASIS, |
|
12 | * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
|
13 | * See the License for the specific language governing permissions and |
|
14 | * limitations under the License. |
|
15 | */ |
|
16 | ||
17 | package org.apache.commons.net.nntp; |
|
18 | ||
19 | /** |
|
20 | * This is an implementation of a message threading algorithm, as originally devised by Zamie Zawinski. |
|
21 | * See <a href="http://www.jwz.org/doc/threading.html">http://www.jwz.org/doc/threading.html</a> for details. |
|
22 | * For his Java implementation, see <a href="http://lxr.mozilla.org/mozilla/source/grendel/sources/grendel/view/Threader.java">http://lxr.mozilla.org/mozilla/source/grendel/sources/grendel/view/Threader.java</a> |
|
23 | * |
|
24 | * @author rwinston <rwinston@checkfree.com> |
|
25 | * |
|
26 | */ |
|
27 | ||
28 | import java.util.HashMap; |
|
29 | import java.util.Iterator; |
|
30 | ||
31 | 0 | public class Threader { |
32 | private ThreadContainer root; |
|
33 | private HashMap idTable; |
|
34 | 0 | private int bogusIdCount = 0; |
35 | ||
36 | /** |
|
37 | * The main threader entry point - The client passes in an array of Threadable objects, and |
|
38 | * the Threader constructs a connected 'graph' of messages |
|
39 | * @param messages |
|
40 | * @return |
|
41 | */ |
|
42 | public Threadable thread(Threadable[] messages) { |
|
43 | 0 | if (messages == null) |
44 | 0 | return null; |
45 | ||
46 | 0 | idTable = new HashMap(); |
47 | ||
48 | // walk through each Threadable element |
|
49 | 0 | for (int i = 0; i < messages.length; ++i) { |
50 | 0 | if (!messages[i].isDummy()) |
51 | 0 | buildContainer(messages[i]); |
52 | } |
|
53 | ||
54 | 0 | root = findRootSet(); |
55 | 0 | idTable.clear(); |
56 | 0 | idTable = null; |
57 | ||
58 | 0 | pruneEmptyContainers(root); |
59 | ||
60 | 0 | root.reverseChildren(); |
61 | 0 | gatherSubjects(); |
62 | ||
63 | 0 | if (root.next != null) |
64 | 0 | throw new RuntimeException("root node has a next:" + root); |
65 | ||
66 | 0 | for (ThreadContainer r = root.child; r != null; r = r.next) { |
67 | 0 | if (r.threadable == null) |
68 | 0 | r.threadable = r.child.threadable.makeDummy(); |
69 | } |
|
70 | ||
71 | 0 | Threadable result = (root.child == null ? class="keyword">null : root.child.threadable); |
72 | 0 | root.flush(); |
73 | 0 | root = null; |
74 | ||
75 | 0 | return result; |
76 | } |
|
77 | ||
78 | /** |
|
79 | * |
|
80 | * @param threadable |
|
81 | */ |
|
82 | private void buildContainer(Threadable threadable) { |
|
83 | 0 | String id = threadable.messageThreadId(); |
84 | 0 | ThreadContainer container = (ThreadContainer) idTable.get(id); |
85 | ||
86 | // A ThreadContainer exists for this id already. This should be a forward reference, but may |
|
87 | // be a duplicate id, in which case we will need to generate a bogus placeholder id |
|
88 | 0 | if (container != null) { |
89 | 0 | if (container.threadable != null) { // oops! duplicate ids... |
90 | 0 | id = "<Bogus-id:" + (bogusIdCount++) + ">"; |
91 | 0 | container = null; |
92 | } else { |
|
93 | // The container just contained a forward reference to this message, so let's |
|
94 | // fill in the threadable field of the container with this message |
|
95 | 0 | container.threadable = threadable; |
96 | } |
|
97 | } |
|
98 | ||
99 | // No container exists for that message Id. Create one and insert it into the hash table. |
|
100 | 0 | if (container == null) { |
101 | 0 | container = new ThreadContainer(); |
102 | 0 | container.threadable = threadable; |
103 | 0 | idTable.put(id, container); |
104 | } |
|
105 | ||
106 | // Iterate through all of the references and create ThreadContainers for any references that |
|
107 | // don't have them. |
|
108 | 0 | ThreadContainer parentRef = null; |
109 | { |
|
110 | 0 | String[] references = threadable.messageThreadReferences(); |
111 | 0 | for (int i = 0; i < references.length; ++i) { |
112 | 0 | String refString = references[i]; |
113 | 0 | ThreadContainer ref = (ThreadContainer) idTable.get(refString); |
114 | ||
115 | // if this id doesnt have a container, create one |
|
116 | 0 | if (ref == null) { |
117 | 0 | ref = new ThreadContainer(); |
118 | 0 | idTable.put(refString, ref); |
119 | } |
|
120 | ||
121 | // Link references together in the order they appear in the References: header, |
|
122 | // IF they dont have a have a parent already && |
|
123 | // IF it will not cause a circular reference |
|
124 | 0 | if ((parentRef != null) |
125 | && (ref.parent == null) |
|
126 | && (parentRef != ref) |
|
127 | && !(parentRef.findChild(ref))) { |
|
128 | // Link ref into the parent's child list |
|
129 | 0 | ref.parent = parentRef; |
130 | 0 | ref.next = parentRef.child; |
131 | 0 | parentRef.child = ref; |
132 | } |
|
133 | 0 | parentRef = ref; |
134 | } |
|
135 | } |
|
136 | ||
137 | // parentRef is now set to the container of the last element in the references field. make that |
|
138 | // be the parent of this container, unless doing so causes a circular reference |
|
139 | 0 | if (parentRef != null |
140 | && (parentRef == container || container.findChild(parentRef))) |
|
141 | 0 | parentRef = null; |
142 | ||
143 | // if it has a parent already, its because we saw this message in a References: field, and presumed |
|
144 | // a parent based on the other entries in that field. Now that we have the actual message, we can |
|
145 | // throw away the old parent and use this new one |
|
146 | 0 | if (container.parent != null) { |
147 | ThreadContainer rest, prev; |
|
148 | ||
149 | 0 | for (prev = null, rest = container.parent.child; |
150 | 0 | rest != null; |
151 | 0 | prev = rest, class="keyword">rest = class="keyword">rest.next) { |
152 | 0 | if (rest == container) |
153 | 0 | break; |
154 | } |
|
155 | ||
156 | 0 | if (rest == null) { |
157 | 0 | throw new RuntimeException( |
158 | "Didnt find " |
|
159 | + container |
|
160 | + " in parent" |
|
161 | + container.parent); |
|
162 | } |
|
163 | ||
164 | // Unlink this container from the parent's child list |
|
165 | 0 | if (prev == null) |
166 | 0 | container.parent.child = container.next; |
167 | else |
|
168 | 0 | prev.next = container.next; |
169 | ||
170 | 0 | container.next = null; |
171 | 0 | container.parent = null; |
172 | } |
|
173 | ||
174 | // If we have a parent, link container into the parents child list |
|
175 | 0 | if (parentRef != null) { |
176 | 0 | container.parent = parentRef; |
177 | 0 | container.next = parentRef.child; |
178 | 0 | parentRef.child = container; |
179 | } |
|
180 | 0 | } |
181 | ||
182 | /** |
|
183 | * Find the root set of all existing ThreadContainers |
|
184 | * @return root the ThreadContainer representing the root node |
|
185 | */ |
|
186 | private ThreadContainer findRootSet() { |
|
187 | 0 | ThreadContainer root = new ThreadContainer(); |
188 | 0 | Iterator iter = idTable.keySet().iterator(); |
189 | ||
190 | 0 | while (iter.hasNext()) { |
191 | 0 | Object key = iter.next(); |
192 | 0 | ThreadContainer c = (ThreadContainer) idTable.get(key); |
193 | 0 | if (c.parent == null) { |
194 | 0 | if (c.next != null) |
195 | 0 | throw new RuntimeException( |
196 | "c.next is " + c.next.toString()); |
|
197 | 0 | c.next = root.child; |
198 | 0 | root.child = c; |
199 | } |
|
200 | } |
|
201 | 0 | return root; |
202 | } |
|
203 | ||
204 | /** |
|
205 | * Delete any empty or dummy ThreadContainers |
|
206 | * @param parent |
|
207 | */ |
|
208 | private void pruneEmptyContainers(ThreadContainer parent) { |
|
209 | ThreadContainer container, prev, next; |
|
210 | 0 | for (prev = null, container = parent.child, next = container.next; |
211 | 0 | container != null; |
212 | 0 | prev = container, |
213 | 0 | container = next, |
214 | 0 | next = (container == null ? class="keyword">null : container.next)) { |
215 | ||
216 | // Is it empty and without any children? If so,delete it |
|
217 | 0 | if (container.threadable == null && container.child == class="keyword">null) { |
218 | 0 | if (prev == null) |
219 | 0 | parent.child = container.next; |
220 | else |
|
221 | 0 | prev.next = container.next; |
222 | ||
223 | // Set container to prev so that prev keeps its same value the next time through the loop |
|
224 | 0 | container = prev; |
225 | } |
|
226 | ||
227 | // Else if empty, with kids, and (not at root or only one kid) |
|
228 | 0 | else if ( |
229 | container.threadable == null |
|
230 | && container.child != null |
|
231 | && (container.parent != null |
|
232 | || container.child.next == null)) { |
|
233 | // We have an invalid/expired message with kids. Promote the kids to this level. |
|
234 | ThreadContainer tail; |
|
235 | 0 | ThreadContainer kids = container.child; |
236 | ||
237 | // Remove this container and replace with 'kids'. |
|
238 | 0 | if (prev == null) |
239 | 0 | parent.child = kids; |
240 | else |
|
241 | 0 | prev.next = kids; |
242 | ||
243 | // Make each child's parent be this level's parent -> i.e. promote the children. Make the last child's next point to this container's next |
|
244 | // i.e. splice kids into the list in place of container |
|
245 | 0 | for (tail = kids; tail.next != null; tail = tail.next) |
246 | 0 | tail.parent = container.parent; |
247 | ||
248 | 0 | tail.parent = container.parent; |
249 | 0 | tail.next = container.next; |
250 | ||
251 | // next currently points to the item after the inserted items in the chain - reset that so we process the newly |
|
252 | // promoted items next time round |
|
253 | 0 | next = kids; |
254 | ||
255 | // Set container to prev so that prev keeps its same value the next time through the loop |
|
256 | 0 | container = prev; |
257 | 0 | } else if (container.child != null) { |
258 | // A real message , with kids |
|
259 | // Iterate over the children |
|
260 | 0 | pruneEmptyContainers(container); |
261 | } |
|
262 | } |
|
263 | 0 | } |
264 | ||
265 | /** |
|
266 | * If any two members of the root set have the same subject, merge them. This is to attempt to accomodate messages without References: headers. |
|
267 | */ |
|
268 | private void gatherSubjects() { |
|
269 | ||
270 | 0 | int count = 0; |
271 | ||
272 | 0 | for (ThreadContainer c = root.child; c != null; c = c.next) |
273 | 0 | count++; |
274 | ||
275 | // TODO verify this will avoid rehashing |
|
276 | 0 | HashMap subjectTable = new HashMap((int) (count * 1.2), (float) 0.9); |
277 | 0 | count = 0; |
278 | ||
279 | 0 | for (ThreadContainer c = root.child; c != null; c = c.next) { |
280 | 0 | Threadable threadable = c.threadable; |
281 | ||
282 | // No threadable? If so, it is a dummy node in the root set. |
|
283 | // Only root set members may be dummies, and they alway have at least 2 kids |
|
284 | // Take the first kid as representative of the subject |
|
285 | 0 | if (threadable == null) |
286 | 0 | threadable = c.child.threadable; |
287 | ||
288 | 0 | String subj = threadable.simplifiedSubject(); |
289 | ||
290 | 0 | if (subj == null || subj == "") |
291 | 0 | continue; |
292 | ||
293 | 0 | ThreadContainer old = (ThreadContainer) subjectTable.get(subj); |
294 | ||
295 | // Add this container to the table iff: |
|
296 | // - There exists no container with this subject |
|
297 | // - or this is a dummy container and the old one is not - the dummy one is |
|
298 | // more interesting as a root, so put it in the table instead |
|
299 | // - The container in the table has a "Re:" version of this subject, and |
|
300 | // this container has a non-"Re:" version of this subject. The non-"Re:" version |
|
301 | // is the more interesting of the two. |
|
302 | 0 | if (old == null |
303 | || (c.threadable == null && old.threadable != class="keyword">null) |
|
304 | || (old.threadable != null |
|
305 | && old.threadable.subjectIsReply() |
|
306 | && c.threadable != null |
|
307 | && !c.threadable.subjectIsReply())) { |
|
308 | 0 | subjectTable.put(subj, c); |
309 | 0 | count++; |
310 | } |
|
311 | } |
|
312 | ||
313 | // If the table is empty, we're done |
|
314 | 0 | if (count == 0) |
315 | 0 | return; |
316 | ||
317 | // subjectTable is now populated with one entry for each subject which occurs in the |
|
318 | // root set. Iterate over the root set, and gather together the difference. |
|
319 | ThreadContainer prev, c, rest; |
|
320 | 0 | for (prev = null, c = root.child, rest = c.next; |
321 | 0 | c != null; |
322 | 0 | prev = c, c = rest, class="keyword">rest = (class="keyword">rest == null ? null : class="keyword">rest.next)) { |
323 | 0 | Threadable threadable = c.threadable; |
324 | ||
325 | // is it a dummy node? |
|
326 | 0 | if (threadable == null) |
327 | 0 | threadable = c.child.threadable; |
328 | ||
329 | 0 | String subj = threadable.simplifiedSubject(); |
330 | ||
331 | // Dont thread together all subjectless messages |
|
332 | 0 | if (subj == null || subj == "") |
333 | 0 | continue; |
334 | ||
335 | 0 | ThreadContainer old = (ThreadContainer) subjectTable.get(subj); |
336 | ||
337 | 0 | if (old == c) // That's us |
338 | 0 | continue; |
339 | ||
340 | // We have now found another container in the root set with the same subject |
|
341 | // Remove the "second" message from the root set |
|
342 | 0 | if (prev == null) |
343 | 0 | root.child = c.next; |
344 | else |
|
345 | 0 | prev.next = c.next; |
346 | 0 | c.next = null; |
347 | ||
348 | 0 | if (old.threadable == null && c.threadable == class="keyword">null) { |
349 | // both dummies - merge them |
|
350 | ThreadContainer tail; |
|
351 | 0 | for (tail = old.child; |
352 | 0 | tail != null && tail.next != class="keyword">null; |
353 | 0 | tail = tail.next); |
354 | ||
355 | 0 | tail.next = c.child; |
356 | ||
357 | 0 | for (tail = c.child; tail != null; tail = tail.next) |
358 | 0 | tail.parent = old; |
359 | ||
360 | 0 | c.child = null; |
361 | 0 | } else if ( |
362 | old.threadable == null |
|
363 | || (c.threadable != null |
|
364 | && c.threadable.subjectIsReply() |
|
365 | && !old.threadable.subjectIsReply())) { |
|
366 | // Else if old is empty, or c has "Re:" and old does not ==> make this message a child of old |
|
367 | 0 | c.parent = old; |
368 | 0 | c.next = old.child; |
369 | 0 | old.child = c; |
370 | } else { |
|
371 | // else make the old and new messages be children of a new dummy container. |
|
372 | // We create a new container object for old.msg and empty the old container |
|
373 | 0 | ThreadContainer newc = new ThreadContainer(); |
374 | 0 | newc.threadable = old.threadable; |
375 | 0 | newc.child = old.child; |
376 | ||
377 | 0 | for (ThreadContainer tail = newc.child; |
378 | 0 | tail != null; |
379 | 0 | tail = tail.next) |
380 | 0 | tail.parent = newc; |
381 | ||
382 | 0 | old.threadable = null; |
383 | 0 | old.child = null; |
384 | ||
385 | 0 | c.parent = old; |
386 | 0 | newc.parent = old; |
387 | ||
388 | // Old is now a dummy- give it 2 kids , c and newc |
|
389 | 0 | old.child = c; |
390 | 0 | c.next = newc; |
391 | } |
|
392 | // We've done a merge, so keep the same prev |
|
393 | 0 | c = prev; |
394 | } |
|
395 | ||
396 | 0 | subjectTable.clear(); |
397 | 0 | subjectTable = null; |
398 | ||
399 | 0 | } |
400 | } |
|
401 | ||
402 | /** |
|
403 | * A placeholder utility class, used for constructing a tree of Threadables |
|
404 | * Originall implementation by Jamie Zawinski. |
|
405 | * See the Grendel source for more details <a href="http://lxr.mozilla.org/mozilla/source/grendel/sources/grendel/view/Threader.java#511">here</a> |
|
406 | * Threadable objects |
|
407 | * @author Rory Winston <rwinston@checkfree.com> |
|
408 | */ |
|
409 | class ThreadContainer { |
|
410 | Threadable threadable; |
|
411 | ThreadContainer parent; |
|
412 | ThreadContainer prev; |
|
413 | ThreadContainer next; |
|
414 | ThreadContainer child; |
|
415 | ||
416 | /** |
|
417 | * |
|
418 | * @param container |
|
419 | * @return true if child is under self's tree. Detects circular references |
|
420 | */ |
|
421 | boolean findChild(ThreadContainer target) { |
|
422 | if (child == null) |
|
423 | return false; |
|
424 | ||
425 | else if (child == target) |
|
426 | return true; |
|
427 | else |
|
428 | return child.findChild(target); |
|
429 | } |
|
430 | ||
431 | // Copy the ThreadContainer tree structure down into the underlying Threadable objects |
|
432 | // (Make the Threadable tree look like the ThreadContainer tree) |
|
433 | void flush() { |
|
434 | if (parent != null && threadable == class="keyword">null) |
|
435 | throw new RuntimeException("no threadable in " + this.toString()); |
|
436 | ||
437 | parent = null; |
|
438 | ||
439 | if (threadable != null) |
|
440 | threadable.setChild(child == null ? class="keyword">null : child.threadable); |
|
441 | ||
442 | if (child != null) { |
|
443 | child.flush(); |
|
444 | child = null; |
|
445 | } |
|
446 | ||
447 | if (threadable != null) |
|
448 | threadable.setNext(next == null ? class="keyword">null : next.threadable); |
|
449 | ||
450 | if (next != null) { |
|
451 | next.flush(); |
|
452 | next = null; |
|
453 | } |
|
454 | ||
455 | threadable = null; |
|
456 | } |
|
457 | ||
458 | /** |
|
459 | * Reverse the entire set of children |
|
460 | * |
|
461 | */ |
|
462 | void reverseChildren() { |
|
463 | if (child != null) { |
|
464 | ThreadContainer kid, prev, rest; |
|
465 | for (prev = null, kid = child, rest = kid.next; |
|
466 | kid != null; |
|
467 | prev = kid, |
|
468 | kid = rest, |
|
469 | rest = (class="keyword">rest == null ? null : class="keyword">rest.next)) |
|
470 | kid.next = prev; |
|
471 | ||
472 | child = prev; |
|
473 | ||
474 | // Do it for the kids |
|
475 | for (kid = child; kid != null; kid = kid.next) |
|
476 | kid.reverseChildren(); |
|
477 | } |
|
478 | } |
|
479 | } |
This report is generated by jcoverage, Maven and Maven JCoverage Plugin. |