1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18 package org.apache.commons.net.nntp;
19
20 import java.util.Arrays;
21 import java.util.HashMap;
22 import java.util.List;
23 import java.util.Map;
24
25
26
27
28
29
30
31
32 public class Threader {
33
34
35
36
37
38
39 private void buildContainer(final Threadable threadable, final HashMap<String, NntpThreadContainer> idTable) {
40 String id = threadable.messageThreadId();
41 NntpThreadContainer container = idTable.get(id);
42 int bogusIdCount = 0;
43
44
45
46 if (container != null) {
47 if (container.threadable != null) {
48 bogusIdCount++;
49 id = "<Bogus-id:" + bogusIdCount + ">";
50 container = null;
51 } else {
52
53
54 container.threadable = threadable;
55 }
56 }
57
58
59 if (container == null) {
60 container = new NntpThreadContainer();
61 container.threadable = threadable;
62 idTable.put(id, container);
63 }
64
65
66
67 NntpThreadContainer parentRef = null;
68 {
69 final String[] references = threadable.messageThreadReferences();
70 for (final String refString : references) {
71 NntpThreadContainer ref = idTable.get(refString);
72
73
74 if (ref == null) {
75 ref = new NntpThreadContainer();
76 idTable.put(refString, ref);
77 }
78
79
80
81
82 if (parentRef != null && ref.parent == null && parentRef != ref && !ref.findChild(parentRef)) {
83
84 ref.parent = parentRef;
85 ref.next = parentRef.child;
86 parentRef.child = ref;
87 }
88 parentRef = ref;
89 }
90 }
91
92
93
94 if (parentRef != null && (parentRef == container || container.findChild(parentRef))) {
95 parentRef = null;
96 }
97
98
99
100
101 if (container.parent != null) {
102 NntpThreadContainer rest, prev;
103
104 for (prev = null, rest = container.parent.child; rest != null; prev = rest, rest = rest.next) {
105 if (rest == container) {
106 break;
107 }
108 }
109
110 if (rest == null) {
111 throw new IllegalStateException("Didnt find " + container + " in parent " + container.parent);
112 }
113
114
115 if (prev == null) {
116 container.parent.child = container.next;
117 } else {
118 prev.next = container.next;
119 }
120
121 container.next = null;
122 container.parent = null;
123 }
124
125
126 if (parentRef != null) {
127 container.parent = parentRef;
128 container.next = parentRef.child;
129 parentRef.child = container;
130 }
131 }
132
133
134
135
136
137
138
139 private NntpThreadContainer findRootSet(final HashMap<String, NntpThreadContainer> idTable) {
140 final NntpThreadContainer root = new NntpThreadContainer();
141 for (final Map.Entry<String, NntpThreadContainer> entry : idTable.entrySet()) {
142 final NntpThreadContainer c = entry.getValue();
143 if (c.parent == null) {
144 if (c.next != null) {
145 throw new IllegalStateException("c.next is " + c.next.toString());
146 }
147 c.next = root.child;
148 root.child = c;
149 }
150 }
151 return root;
152 }
153
154
155
156
157
158
159 private void gatherSubjects(final NntpThreadContainer root) {
160
161 int count = 0;
162
163 for (NntpThreadContainer c = root.child; c != null; c = c.next) {
164 count++;
165 }
166
167
168 HashMap<String, NntpThreadContainer> subjectTable = new HashMap<>((int) (count * 1.2), (float) 0.9);
169 count = 0;
170
171 for (NntpThreadContainer c = root.child; c != null; c = c.next) {
172 Threadable threadable = c.threadable;
173
174
175
176
177 if (threadable == null) {
178 threadable = c.child.threadable;
179 }
180
181 final String subj = threadable.simplifiedSubject();
182
183 if (subj == null || subj.isEmpty()) {
184 continue;
185 }
186
187 final NntpThreadContainer old = subjectTable.get(subj);
188
189
190
191
192
193
194
195
196 if (old == null || c.threadable == null && old.threadable != null
197 || old.threadable != null && old.threadable.subjectIsReply() && c.threadable != null && !c.threadable.subjectIsReply()) {
198 subjectTable.put(subj, c);
199 count++;
200 }
201 }
202
203
204 if (count == 0) {
205 return;
206 }
207
208
209
210 NntpThreadContainer prev, c, rest;
211 for (prev = null, c = root.child, rest = c.next; c != null; prev = c, c = rest, rest = rest == null ? null : rest.next) {
212 Threadable threadable = c.threadable;
213
214
215 if (threadable == null) {
216 threadable = c.child.threadable;
217 }
218
219 final String subj = threadable.simplifiedSubject();
220
221
222 if (subj == null || subj.isEmpty()) {
223 continue;
224 }
225
226 final NntpThreadContainer old = subjectTable.get(subj);
227
228 if (old == c) {
229 continue;
230 }
231
232
233
234 if (prev == null) {
235 root.child = c.next;
236 } else {
237 prev.next = c.next;
238 }
239 c.next = null;
240
241 if (old.threadable == null && c.threadable == null) {
242
243 NntpThreadContainer tail;
244 for (tail = old.child; tail != null && tail.next != null; tail = tail.next) {
245
246 }
247
248 if (tail != null) {
249 tail.next = c.child;
250 }
251
252 for (tail = c.child; tail != null; tail = tail.next) {
253 tail.parent = old;
254 }
255
256 c.child = null;
257 } else if (old.threadable == null || c.threadable != null && c.threadable.subjectIsReply() && !old.threadable.subjectIsReply()) {
258
259 c.parent = old;
260 c.next = old.child;
261 old.child = c;
262 } else {
263
264
265 final NntpThreadContainer newc = new NntpThreadContainer();
266 newc.threadable = old.threadable;
267 newc.child = old.child;
268
269 for (NntpThreadContainer tail = newc.child; tail != null; tail = tail.next) {
270 tail.parent = newc;
271 }
272
273 old.threadable = null;
274 old.child = null;
275
276 c.parent = old;
277 newc.parent = old;
278
279
280 old.child = c;
281 c.next = newc;
282 }
283
284 c = prev;
285 }
286
287 subjectTable.clear();
288 subjectTable = null;
289
290 }
291
292
293
294
295
296
297 private void pruneEmptyContainers(final NntpThreadContainer parent) {
298 NntpThreadContainer container, prev, next;
299 for (prev = null, container = parent.child, next = container.next; container != null; prev = container, container = next, next = container == null
300 ? null
301 : container.next) {
302
303
304 if (container.threadable == null && container.child == null) {
305 if (prev == null) {
306 parent.child = container.next;
307 } else {
308 prev.next = container.next;
309 }
310
311
312 container = prev;
313 }
314
315
316 else if (container.threadable == null && (container.parent != null || container.child.next == null)) {
317
318 NntpThreadContainer tail;
319 final NntpThreadContainer kids = container.child;
320
321
322 if (prev == null) {
323 parent.child = kids;
324 } else {
325 prev.next = kids;
326 }
327
328
329
330
331 for (tail = kids; tail.next != null; tail = tail.next) {
332 tail.parent = container.parent;
333 }
334
335 tail.parent = container.parent;
336 tail.next = container.next;
337
338
339
340 next = kids;
341
342
343 container = prev;
344 } else if (container.child != null) {
345
346
347 pruneEmptyContainers(container);
348 }
349 }
350 }
351
352
353
354
355
356
357
358
359 public Threadable thread(final Iterable<? extends Threadable> messages) {
360 if (messages == null) {
361 return null;
362 }
363
364 HashMap<String, NntpThreadContainer> idTable = new HashMap<>();
365
366
367 for (final Threadable t : messages) {
368 if (!t.isDummy()) {
369 buildContainer(t, idTable);
370 }
371 }
372
373 if (idTable.isEmpty()) {
374 return null;
375 }
376
377 final NntpThreadContainer root = findRootSet(idTable);
378 idTable.clear();
379 idTable = null;
380
381 pruneEmptyContainers(root);
382
383 root.reverseChildren();
384 gatherSubjects(root);
385
386 if (root.next != null) {
387 throw new IllegalStateException("root node has a next:" + root);
388 }
389
390 for (NntpThreadContainer r = root.child; r != null; r = r.next) {
391 if (r.threadable == null) {
392 r.threadable = r.child.threadable.makeDummy();
393 }
394 }
395
396 final Threadable result = root.child == null ? null : root.child.threadable;
397 root.flush();
398
399 return result;
400 }
401
402
403
404
405
406
407
408
409 public Threadable thread(final List<? extends Threadable> messages) {
410 return thread((Iterable<? extends Threadable>) messages);
411 }
412
413
414
415
416
417
418
419
420
421
422 @Deprecated
423 public Threadable thread(final Threadable[] messages) {
424 if (messages == null) {
425 return null;
426 }
427 return thread(Arrays.asList(messages));
428 }
429
430 }