001    /*
002     * Licensed to the Apache Software Foundation (ASF) under one or more
003     * contributor license agreements.  See the NOTICE file distributed with
004     * this work for additional information regarding copyright ownership.
005     * The ASF licenses this file to You under the Apache License, Version 2.0
006     * (the "License"); you may not use this file except in compliance with
007     * the License.  You may obtain a copy of the License at
008     *
009     *      http://www.apache.org/licenses/LICENSE-2.0
010     *
011     * Unless required by applicable law or agreed to in writing, software
012     * distributed under the License is distributed on an "AS IS" BASIS,
013     * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014     * See the License for the specific language governing permissions and
015     * limitations under the License.
016     */
017    
018    
019    package org.apache.commons.net.nntp;
020    
021    /**
022     * This is an implementation of a message threading algorithm, as originally devised by Zamie Zawinski.
023     * See <a href="http://www.jwz.org/doc/threading.html">http://www.jwz.org/doc/threading.html</a> for details.
024     * 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>
025     *
026     * @author rwinston <rwinston@checkfree.com>
027     *
028     */
029    
030    import java.util.Arrays;
031    import java.util.HashMap;
032    import java.util.Iterator;
033    import java.util.List;
034    
035    public class Threader {
036        private ThreadContainer root;
037        private HashMap<String,ThreadContainer> idTable;
038        private int bogusIdCount = 0;
039    
040        /**
041         * The main threader entry point - The client passes in an array of Threadable objects, and
042         * the Threader constructs a connected 'graph' of messages
043         * @param messages array of messages to thread
044         * @return null if messages == null or root.child == null
045         * @deprecated (2.2) prefer {@link #thread(List)}
046         */
047        @Deprecated
048        public Threadable thread(Threadable[] messages) {
049            return thread(Arrays.asList(messages));
050        }
051    
052        /**
053         * The main threader entry point - The client passes in a list of Threadable objects, and
054         * the Threader constructs a connected 'graph' of messages
055         * @param messages list of messages to thread
056         * @return null if messages == null or root.child == null
057         * @since 2.2
058         */
059        public Threadable thread(List<? extends Threadable> messages) {
060            if (messages == null)
061                return null;
062    
063            idTable = new HashMap<String,ThreadContainer>();
064    
065            // walk through each Threadable element
066            for (Threadable t : messages) {
067                if (!t.isDummy())
068                    buildContainer(t);
069            }
070    
071            root = findRootSet();
072            idTable.clear();
073            idTable = null;
074    
075            pruneEmptyContainers(root);
076    
077            root.reverseChildren();
078            gatherSubjects();
079    
080            if (root.next != null)
081                throw new RuntimeException("root node has a next:" + root);
082    
083            for (ThreadContainer r = root.child; r != null; r = r.next) {
084                if (r.threadable == null)
085                    r.threadable = r.child.threadable.makeDummy();
086            }
087    
088            Threadable result = (root.child == null ? null : root.child.threadable);
089            root.flush();
090            root = null;
091    
092            return result;
093        }
094    
095        /**
096         *
097         * @param threadable
098         */
099        private void buildContainer(Threadable threadable) {
100            String id = threadable.messageThreadId();
101            ThreadContainer container = idTable.get(id);
102    
103            // A ThreadContainer exists for this id already. This should be a forward reference, but may
104            // be a duplicate id, in which case we will need to generate a bogus placeholder id
105            if (container != null) {
106                if (container.threadable != null) { // oops! duplicate ids...
107                    id = "<Bogus-id:" + (bogusIdCount++) + ">";
108                    container = null;
109                } else {
110                    // The container just contained a forward reference to this message, so let's
111                    // fill in the threadable field of the container with this message
112                    container.threadable = threadable;
113                }
114            }
115    
116            // No container exists for that message Id. Create one and insert it into the hash table.
117            if (container == null) {
118                container = new ThreadContainer();
119                container.threadable = threadable;
120                idTable.put(id, container);
121            }
122    
123            // Iterate through all of the references and create ThreadContainers for any references that
124            // don't have them.
125            ThreadContainer parentRef = null;
126            {
127                String[] references = threadable.messageThreadReferences();
128                for (int i = 0; i < references.length; ++i) {
129                    String refString = references[i];
130                    ThreadContainer ref = idTable.get(refString);
131    
132                    // if this id doesnt have a container, create one
133                    if (ref == null) {
134                        ref = new ThreadContainer();
135                        idTable.put(refString, ref);
136                    }
137    
138                    // Link references together in the order they appear in the References: header,
139                    // IF they dont have a have a parent already &&
140                    // IF it will not cause a circular reference
141                    if ((parentRef != null)
142                        && (ref.parent == null)
143                        && (parentRef != ref)
144                        && !(parentRef.findChild(ref))) {
145                        // Link ref into the parent's child list
146                        ref.parent = parentRef;
147                        ref.next = parentRef.child;
148                        parentRef.child = ref;
149                    }
150                    parentRef = ref;
151                }
152            }
153    
154            // parentRef is now set to the container of the last element in the references field. make that
155            // be the parent of this container, unless doing so causes a circular reference
156            if (parentRef != null
157                && (parentRef == container || container.findChild(parentRef)))
158                parentRef = null;
159    
160            // if it has a parent already, its because we saw this message in a References: field, and presumed
161            // a parent based on the other entries in that field. Now that we have the actual message, we can
162            // throw away the old parent and use this new one
163            if (container.parent != null) {
164                ThreadContainer rest, prev;
165    
166                for (prev = null, rest = container.parent.child;
167                    rest != null;
168                    prev = rest, rest = rest.next) {
169                    if (rest == container)
170                        break;
171                }
172    
173                if (rest == null) {
174                    throw new RuntimeException(
175                        "Didnt find "
176                            + container
177                            + " in parent"
178                            + container.parent);
179                }
180    
181                // Unlink this container from the parent's child list
182                if (prev == null)
183                    container.parent.child = container.next;
184                else
185                    prev.next = container.next;
186    
187                container.next = null;
188                container.parent = null;
189            }
190    
191            // If we have a parent, link container into the parents child list
192            if (parentRef != null) {
193                container.parent = parentRef;
194                container.next = parentRef.child;
195                parentRef.child = container;
196            }
197        }
198    
199        /**
200         * Find the root set of all existing ThreadContainers
201         * @return root the ThreadContainer representing the root node
202         */
203        private ThreadContainer findRootSet() {
204            ThreadContainer root = new ThreadContainer();
205            Iterator<String> iter = idTable.keySet().iterator();
206    
207            while (iter.hasNext()) {
208                Object key = iter.next();
209                ThreadContainer c = idTable.get(key);
210                if (c.parent == null) {
211                    if (c.next != null)
212                        throw new RuntimeException(
213                            "c.next is " + c.next.toString());
214                    c.next = root.child;
215                    root.child = c;
216                }
217            }
218            return root;
219        }
220    
221        /**
222         * Delete any empty or dummy ThreadContainers
223         * @param parent
224         */
225        private void pruneEmptyContainers(ThreadContainer parent) {
226            ThreadContainer container, prev, next;
227            for (prev = null, container = parent.child, next = container.next;
228                container != null;
229                prev = container,
230                    container = next,
231                    next = (container == null ? null : container.next)) {
232    
233                // Is it empty and without any children? If so,delete it
234                if (container.threadable == null && container.child == null) {
235                    if (prev == null)
236                        parent.child = container.next;
237                    else
238                        prev.next = container.next;
239    
240                    // Set container to prev so that prev keeps its same value the next time through the loop
241                    container = prev;
242                }
243    
244                // Else if empty, with kids, and (not at root or only one kid)
245                else if (
246                    container.threadable == null
247                        && container.child != null
248                        && (container.parent != null
249                            || container.child.next == null)) {
250                    // We have an invalid/expired message with kids. Promote the kids to this level.
251                    ThreadContainer tail;
252                    ThreadContainer kids = container.child;
253    
254                    // Remove this container and replace with 'kids'.
255                    if (prev == null)
256                        parent.child = kids;
257                    else
258                        prev.next = kids;
259    
260                    // 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
261                    // i.e. splice kids into the list in place of container
262                    for (tail = kids; tail.next != null; tail = tail.next)
263                        tail.parent = container.parent;
264    
265                    tail.parent = container.parent;
266                    tail.next = container.next;
267    
268                    // next currently points to the item after the inserted items in the chain - reset that so we process the newly
269                    // promoted items next time round
270                    next = kids;
271    
272                    // Set container to prev so that prev keeps its same value the next time through the loop
273                    container = prev;
274                } else if (container.child != null) {
275                    // A real message , with kids
276                    // Iterate over the children
277                    pruneEmptyContainers(container);
278                }
279            }
280        }
281    
282        /**
283         *  If any two members of the root set have the same subject, merge them. This is to attempt to accomodate messages without References: headers.
284         */
285        private void gatherSubjects() {
286    
287            int count = 0;
288    
289            for (ThreadContainer c = root.child; c != null; c = c.next)
290                count++;
291    
292            // TODO verify this will avoid rehashing
293            HashMap<String, ThreadContainer> subjectTable = new HashMap<String, ThreadContainer>((int) (count * 1.2), (float) 0.9);
294            count = 0;
295    
296            for (ThreadContainer c = root.child; c != null; c = c.next) {
297                Threadable threadable = c.threadable;
298    
299                // No threadable? If so, it is a dummy node in the root set.
300                // Only root set members may be dummies, and they alway have at least 2 kids
301                // Take the first kid as representative of the subject
302                if (threadable == null)
303                    threadable = c.child.threadable;
304    
305                String subj = threadable.simplifiedSubject();
306    
307                if (subj == null || subj == "")
308                    continue;
309    
310                ThreadContainer old = subjectTable.get(subj);
311    
312                // Add this container to the table iff:
313                // - There exists no container with this subject
314                // - or this is a dummy container and the old one is not - the dummy one is
315                // more interesting as a root, so put it in the table instead
316                // - The container in the table has a "Re:" version of this subject, and
317                // this container has a non-"Re:" version of this subject. The non-"Re:" version
318                // is the more interesting of the two.
319                if (old == null
320                    || (c.threadable == null && old.threadable != null)
321                    || (old.threadable != null
322                        && old.threadable.subjectIsReply()
323                        && c.threadable != null
324                        && !c.threadable.subjectIsReply())) {
325                    subjectTable.put(subj, c);
326                    count++;
327                }
328            }
329    
330            // If the table is empty, we're done
331            if (count == 0)
332                return;
333    
334            // subjectTable is now populated with one entry for each subject which occurs in the
335            // root set. Iterate over the root set, and gather together the difference.
336            ThreadContainer prev, c, rest;
337            for (prev = null, c = root.child, rest = c.next;
338                c != null;
339                prev = c, c = rest, rest = (rest == null ? null : rest.next)) {
340                Threadable threadable = c.threadable;
341    
342                // is it a dummy node?
343                if (threadable == null)
344                    threadable = c.child.threadable;
345    
346                String subj = threadable.simplifiedSubject();
347    
348                // Dont thread together all subjectless messages
349                if (subj == null || subj == "")
350                    continue;
351    
352                ThreadContainer old = subjectTable.get(subj);
353    
354                if (old == c) // That's us
355                    continue;
356    
357                // We have now found another container in the root set with the same subject
358                // Remove the "second" message from the root set
359                if (prev == null)
360                    root.child = c.next;
361                else
362                    prev.next = c.next;
363                c.next = null;
364    
365                if (old.threadable == null && c.threadable == null) {
366                    // both dummies - merge them
367                    ThreadContainer tail;
368                    for (tail = old.child;
369                        tail != null && tail.next != null;
370                        tail = tail.next);
371    
372                    tail.next = c.child;
373    
374                    for (tail = c.child; tail != null; tail = tail.next)
375                        tail.parent = old;
376    
377                    c.child = null;
378                } else if (
379                    old.threadable == null
380                        || (c.threadable != null
381                            && c.threadable.subjectIsReply()
382                            && !old.threadable.subjectIsReply())) {
383                    // Else if old is empty, or c has "Re:" and old does not  ==> make this message a child of old
384                    c.parent = old;
385                    c.next = old.child;
386                    old.child = c;
387                } else {
388                    // else make the old and new messages be children of a new dummy container.
389                    // We create a new container object for old.msg and empty the old container
390                    ThreadContainer newc = new ThreadContainer();
391                    newc.threadable = old.threadable;
392                    newc.child = old.child;
393    
394                    for (ThreadContainer tail = newc.child;
395                        tail != null;
396                        tail = tail.next)
397                        tail.parent = newc;
398    
399                    old.threadable = null;
400                    old.child = null;
401    
402                    c.parent = old;
403                    newc.parent = old;
404    
405                    // Old is now a dummy- give it 2 kids , c and newc
406                    old.child = c;
407                    c.next = newc;
408                }
409                // We've done a merge, so keep the same prev
410                c = prev;
411            }
412    
413            subjectTable.clear();
414            subjectTable = null;
415    
416        }
417    }