e70152e44cc66cc599ff6b699eb8adc07f3e656a
kent
  Sat May 24 21:09:34 2014 -0700
Adding Copyright NNNN Regents of the University of California to all files I believe with reasonable certainty were developed under UCSC employ or as part of Genome Browser copyright assignment.
diff --git src/lib/boxLump.c src/lib/boxLump.c
index 0fdfbc9..0fdc67c 100644
--- src/lib/boxLump.c
+++ src/lib/boxLump.c
@@ -1,159 +1,162 @@
 /* boxLump - This will lump together boxes that overlap into the smallest
  * box that encompasses the overlap.  It will put other boxes that 
  * fit in the encompassing box in there too. 
  *   It works by projecting the box list along one dimension at a
  * time looking for gaps between boxes. This is similar in function
  * to boxFindClumps, but a bit less precise, and quite a bit faster.
  * in some important cases. */
 
+/* Copyright (C) 2011 The Regents of the University of California 
+ * See README in this or parent directory for licensing information. */
+
 #include "common.h"
 #include "hash.h"
 #include "boxClump.h"
 #include "boxLump.h"
 
 
 int boxInCmpQuery(const void *va, const void *vb)
 /* Compare to sort based on query start. */
 {
 const struct boxIn *a = *((struct boxIn **)va);
 const struct boxIn *b = *((struct boxIn **)vb);
 return a->qStart - b->qStart;
 }
 
 int boxInCmpTarget(const void *va, const void *vb)
 /* Compare to sort based on query start. */
 {
 const struct boxIn *a = *((struct boxIn **)va);
 const struct boxIn *b = *((struct boxIn **)vb);
 return a->tStart - b->tStart;
 }
 
 struct boxClump *lumpOneDimension(struct boxIn *boxList, boolean onQuery)
 /* Build box clump list on one dimension. */
 {
 struct boxClump *clump = NULL, *clumpList = NULL;
 struct boxIn *box, *nextBox;
 if (onQuery)
     slSort(&boxList, boxInCmpQuery);
 else
     slSort(&boxList, boxInCmpTarget);
 for (box = boxList; box != NULL; box = nextBox)
     {
     nextBox = box->next;
     /* Make new clump containing current box. */
     if (clump == NULL || 
         (onQuery && clump->qEnd < box->qStart) ||
 	(!onQuery && clump->tEnd < box->tStart) )
         {
 	AllocVar(clump);
 	slAddHead(&clumpList, clump);
 	clump->qStart = box->qStart;
 	clump->qEnd = box->qEnd;
 	clump->tStart = box->tStart;
 	clump->tEnd = box->tEnd;
 	clump->boxCount = 1;
 	clump->boxList = box;
 	box->next = NULL;
 	}
     else
         {
 	if (clump->tStart > box->tStart)
 	     clump->tStart = box->tStart;
 	if (clump->tEnd < box->tEnd)
 	     clump->tEnd = box->tEnd;
 	if (clump->qEnd < box->qEnd)
 	     clump->qEnd = box->qEnd;
 	if (clump->qStart > box->qStart)
 	     clump->qStart = box->qStart;
 	clump->boxCount += 1;
 	slAddHead(&clump->boxList, box);
 	}
     }
 return clumpList;
 }
 
 struct boxClump *boxLump(struct boxIn **pBoxList)
 /* Convert list of boxes to a list of lumps.  The lumps
  * are a smaller number of boxes that between them contain
  * all of the input boxes.  Note that
  * the original boxList is overwritten as the boxes
  * are moved from it to the lumps. */
 {
 struct boxClump *qClumpList = NULL, *tClumpList = NULL, 
 	*tClump;
 
 if (*pBoxList == NULL)
     return NULL;
 tClumpList = lumpOneDimension(*pBoxList, FALSE);
 
 for (tClump = tClumpList; tClump != NULL; tClump = tClump->next)
     {
     struct boxClump *oneList = lumpOneDimension(tClump->boxList, TRUE);
     if (slCount(oneList) > 1)
         {
 	struct boxClump *clump;
 	for (clump = oneList; clump != NULL; clump = clump->next)
 	    {
 	    struct boxClump *subList = boxLump(&clump->boxList);
 	    qClumpList = slCat(subList, qClumpList);
 	    }
 	boxClumpFreeList(&oneList);
 	}
     else
 	{
 	qClumpList = slCat(oneList, qClumpList);
 	}
     tClump->boxList = NULL;
     }
 
 boxClumpFreeList(&tClumpList);
 *pBoxList = NULL;
 return qClumpList;
 }
 
 #ifdef DEBUG
 
 int testData[][4] = 
     {
 	/* qStart, qEnd, tStart, tEnd */
 	{0, 100,     0, 100},
 	{50, 150,    50, 150},
 	{200, 300,   200, 300},
 	{250, 350,   250, 350},
 	{0, 100,     200, 300},
 	{50, 150,    250, 350},
 	{200,300,    0, 100},
 	{250,350,    50, 150},
 	{500,600,    100,300},
 	{500,600,    500, 600},
 	{500,700,    500, 700},
 	{1000,1100,  1000,1100},
 	{1000,1100,  2000,2100},
     };
 
 
 void testBoxLump()
 /* Test boxLump routine. */
 {
 struct boxIn *boxList = NULL, *box;
 struct boxClump *clumpList, *clump;
 int i;
 
 for (i=0; i<ArraySize(testData); ++i)
     {
     AllocVar(box);
     box->qStart = testData[i][0];
     box->qEnd = testData[i][1];
     box->tStart = testData[i][2];
     box->tEnd = testData[i][3];
     slAddHead(&boxList, box);
     }
 clumpList = boxLump(&boxList);
 for (clump = clumpList; clump != NULL; clump = clump->next)
     {
     printf("%d,%d,\t%d,%d\n", clump->qStart, clump->qEnd, clump->tStart, clump->tEnd);
     for (box = clump->boxList; box != NULL; box = box->next)
 	printf("\t%d,%d\t%d,%d\n", box->qStart, box->qEnd, box->tStart, box->tEnd);
     }
 }
 #endif /* DEBUG */