Coverage report

  %line %branch
org.apache.commons.net.nntp.Threader
0% 
0% 

 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.