1
2
3
4
5
6
7
8
9
10
11
12
13
14
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 public class Threader {
32 private ThreadContainer root;
33 private HashMap idTable;
34 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 if (messages == null)
44 return null;
45
46 idTable = new HashMap();
47
48
49 for (int i = 0; i < messages.length; ++i) {
50 if (!messages[i].isDummy())
51 buildContainer(messages[i]);
52 }
53
54 root = findRootSet();
55 idTable.clear();
56 idTable = null;
57
58 pruneEmptyContainers(root);
59
60 root.reverseChildren();
61 gatherSubjects();
62
63 if (root.next != null)
64 throw new RuntimeException("root node has a next:" + root);
65
66 for (ThreadContainer r = root.child; r != null; r = r.next) {
67 if (r.threadable == null)
68 r.threadable = r.child.threadable.makeDummy();
69 }
70
71 Threadable result = (root.child == null ? null : root.child.threadable);
72 root.flush();
73 root = null;
74
75 return result;
76 }
77
78 /**
79 *
80 * @param threadable
81 */
82 private void buildContainer(Threadable threadable) {
83 String id = threadable.messageThreadId();
84 ThreadContainer container = (ThreadContainer) idTable.get(id);
85
86
87
88 if (container != null) {
89 if (container.threadable != null) {
90 id = "<Bogus-id:" + (bogusIdCount++) + ">";
91 container = null;
92 } else {
93
94
95 container.threadable = threadable;
96 }
97 }
98
99
100 if (container == null) {
101 container = new ThreadContainer();
102 container.threadable = threadable;
103 idTable.put(id, container);
104 }
105
106
107
108 ThreadContainer parentRef = null;
109 {
110 String[] references = threadable.messageThreadReferences();
111 for (int i = 0; i < references.length; ++i) {
112 String refString = references[i];
113 ThreadContainer ref = (ThreadContainer) idTable.get(refString);
114
115
116 if (ref == null) {
117 ref = new ThreadContainer();
118 idTable.put(refString, ref);
119 }
120
121
122
123
124 if ((parentRef != null)
125 && (ref.parent == null)
126 && (parentRef != ref)
127 && !(parentRef.findChild(ref))) {
128
129 ref.parent = parentRef;
130 ref.next = parentRef.child;
131 parentRef.child = ref;
132 }
133 parentRef = ref;
134 }
135 }
136
137
138
139 if (parentRef != null
140 && (parentRef == container || container.findChild(parentRef)))
141 parentRef = null;
142
143
144
145
146 if (container.parent != null) {
147 ThreadContainer rest, prev;
148
149 for (prev = null, rest = container.parent.child;
150 rest != null;
151 prev = rest, rest = rest.next) {
152 if (rest == container)
153 break;
154 }
155
156 if (rest == null) {
157 throw new RuntimeException(
158 "Didnt find "
159 + container
160 + " in parent"
161 + container.parent);
162 }
163
164
165 if (prev == null)
166 container.parent.child = container.next;
167 else
168 prev.next = container.next;
169
170 container.next = null;
171 container.parent = null;
172 }
173
174
175 if (parentRef != null) {
176 container.parent = parentRef;
177 container.next = parentRef.child;
178 parentRef.child = container;
179 }
180 }
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 ThreadContainer root = new ThreadContainer();
188 Iterator iter = idTable.keySet().iterator();
189
190 while (iter.hasNext()) {
191 Object key = iter.next();
192 ThreadContainer c = (ThreadContainer) idTable.get(key);
193 if (c.parent == null) {
194 if (c.next != null)
195 throw new RuntimeException(
196 "c.next is " + c.next.toString());
197 c.next = root.child;
198 root.child = c;
199 }
200 }
201 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 for (prev = null, container = parent.child, next = container.next;
211 container != null;
212 prev = container,
213 container = next,
214 next = (container == null ? null : container.next)) {
215
216
217 if (container.threadable == null && container.child == null) {
218 if (prev == null)
219 parent.child = container.next;
220 else
221 prev.next = container.next;
222
223
224 container = prev;
225 }
226
227
228 else if (
229 container.threadable == null
230 && container.child != null
231 && (container.parent != null
232 || container.child.next == null)) {
233
234 ThreadContainer tail;
235 ThreadContainer kids = container.child;
236
237
238 if (prev == null)
239 parent.child = kids;
240 else
241 prev.next = kids;
242
243
244
245 for (tail = kids; tail.next != null; tail = tail.next)
246 tail.parent = container.parent;
247
248 tail.parent = container.parent;
249 tail.next = container.next;
250
251
252
253 next = kids;
254
255
256 container = prev;
257 } else if (container.child != null) {
258
259
260 pruneEmptyContainers(container);
261 }
262 }
263 }
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 int count = 0;
271
272 for (ThreadContainer c = root.child; c != null; c = c.next)
273 count++;
274
275
276 HashMap subjectTable = new HashMap((int) (count * 1.2), (float) 0.9);
277 count = 0;
278
279 for (ThreadContainer c = root.child; c != null; c = c.next) {
280 Threadable threadable = c.threadable;
281
282
283
284
285 if (threadable == null)
286 threadable = c.child.threadable;
287
288 String subj = threadable.simplifiedSubject();
289
290 if (subj == null || subj == "")
291 continue;
292
293 ThreadContainer old = (ThreadContainer) subjectTable.get(subj);
294
295
296
297
298
299
300
301
302 if (old == null
303 || (c.threadable == null && old.threadable != null)
304 || (old.threadable != null
305 && old.threadable.subjectIsReply()
306 && c.threadable != null
307 && !c.threadable.subjectIsReply())) {
308 subjectTable.put(subj, c);
309 count++;
310 }
311 }
312
313
314 if (count == 0)
315 return;
316
317
318
319 ThreadContainer prev, c, rest;
320 for (prev = null, c = root.child, rest = c.next;
321 c != null;
322 prev = c, c = rest, rest = (rest == null ? null : rest.next)) {
323 Threadable threadable = c.threadable;
324
325
326 if (threadable == null)
327 threadable = c.child.threadable;
328
329 String subj = threadable.simplifiedSubject();
330
331
332 if (subj == null || subj == "")
333 continue;
334
335 ThreadContainer old = (ThreadContainer) subjectTable.get(subj);
336
337 if (old == c)
338 continue;
339
340
341
342 if (prev == null)
343 root.child = c.next;
344 else
345 prev.next = c.next;
346 c.next = null;
347
348 if (old.threadable == null && c.threadable == null) {
349
350 ThreadContainer tail;
351 for (tail = old.child;
352 tail != null && tail.next != null;
353 tail = tail.next);
354
355 tail.next = c.child;
356
357 for (tail = c.child; tail != null; tail = tail.next)
358 tail.parent = old;
359
360 c.child = null;
361 } else if (
362 old.threadable == null
363 || (c.threadable != null
364 && c.threadable.subjectIsReply()
365 && !old.threadable.subjectIsReply())) {
366
367 c.parent = old;
368 c.next = old.child;
369 old.child = c;
370 } else {
371
372
373 ThreadContainer newc = new ThreadContainer();
374 newc.threadable = old.threadable;
375 newc.child = old.child;
376
377 for (ThreadContainer tail = newc.child;
378 tail != null;
379 tail = tail.next)
380 tail.parent = newc;
381
382 old.threadable = null;
383 old.child = null;
384
385 c.parent = old;
386 newc.parent = old;
387
388
389 old.child = c;
390 c.next = newc;
391 }
392
393 c = prev;
394 }
395
396 subjectTable.clear();
397 subjectTable = null;
398
399 }
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
432
433 void flush() {
434 if (parent != null && threadable == null)
435 throw new RuntimeException("no threadable in " + this.toString());
436
437 parent = null;
438
439 if (threadable != null)
440 threadable.setChild(child == null ? 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 ? 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 = (rest == null ? null : rest.next))
470 kid.next = prev;
471
472 child = prev;
473
474
475 for (kid = child; kid != null; kid = kid.next)
476 kid.reverseChildren();
477 }
478 }
479 }