31857342d47d49372089fe3b5aa802932313f3ef
kent
  Sat Jun 18 06:30:38 2022 -0700
Fixed bug in rangeTreeAddToCoverageDepth.  Added parallel rangeTreeAddToCoverageList.

diff --git src/lib/rangeTree.c src/lib/rangeTree.c
index e9a2f03..1415152 100644
--- src/lib/rangeTree.c
+++ src/lib/rangeTree.c
@@ -153,69 +153,184 @@
      */
         {
 	struct range *existingList = rangeTreeAllOverlapping(tree, start, end);
 
 #ifdef DEBUG
 	/* Make sure that list is really sorted for debugging... */
 	int lastStart = existingList->start;
 	for (r = existingList; r != NULL; r = r->next)
 	    {
 	    int start = r->start;
 	    if (start < lastStart)
 	        internalErr();
 	    }
 #endif /* DEBUG */
 
-	int s = start, e = end;
+	int s = start;
 	for (existing = existingList; existing != NULL; existing = existing->next)
 	    {
 	    /* Deal with start of new range that comes before existing */
 	    if (s < existing->start)
 	        {
 		lmAllocVar(tree->lm, r);
 		r->start = s;
 		r->end = existing->start;
 		r->val = intToPt(1);
 		s = existing->start;
 		rbTreeAdd(tree, r);
 		}
 	    else if (s > existing->start)
 	        {
 		lmAllocVar(tree->lm, r);
 		r->start = existing->start;
 		r->end = s;
 		r->val = existing->val;
 		existing->start = s;
 		rbTreeAdd(tree, r);
 		}
+	    if (existing->start < end && existing->end > end)
+	        {
+		lmAllocVar(tree->lm, r);
+		r->start = end;
+		r->end = existing->end;
+		r->val = existing->val;
+		existing->end = end;
+		rbTreeAdd(tree, r);
+		}
 	    existing->val = (char *)(existing->val) + 1;
 	    s = existing->end;
 	    }
-	if (s < e)
+	if (s < end)
 	/* Deal with end of new range that doesn't overlap with anything. */
 	    {
 	    lmAllocVar(tree->lm, r);
 	    r->start = s;
-	    r->end = e;
+	    r->end = end;
 	    r->val = intToPt(1);
 	    rbTreeAdd(tree, r);
 	    }
 	}
     }
 
 }
 
+void rangeTreeAddToCoverageList(struct rbTree *tree, int start, int end, void *val)
+/* Add area from start to end to a tree that is being built up to store the
+ * list of items in each range. Recover list by looking at range->val as list head */
+{
+struct range q;
+q.start = start;
+q.end = end;
+
+struct lm *lm = tree->lm;
+struct range *r, *existing = rbTreeFind(tree, &q);
+if (existing == NULL)
+    {
+    lmAllocVar(lm, r);
+    r->start = start;
+    r->end = end;
+    r->val = lmSlRef(lm, val);
+    rbTreeAdd(tree, r);
+    }
+else
+    {
+    if (existing->start <= start && existing->end >= end)
+    /* The existing one completely encompasses us */
+        {
+	/* Make a new section for the bit before start. */
+	if (existing->start < start)
+	    {
+	    lmAllocVar(lm, r);
+	    r->start = existing->start;
+	    r->end = start;
+	    r->val = existing->val;
+	    existing->start = start;
+	    rbTreeAdd(tree, r);
+	    }
+	/* Make a new section for the bit after end. */
+	if (existing->end > end)
+	    {
+	    lmAllocVar(lm, r);
+	    r->start = end;
+	    r->end = existing->end;
+	    r->val = existing->val;
+	    existing->end = end;
+	    rbTreeAdd(tree, r);
+	    }
+	lmRefAdd(lm, (struct slRef **)&existing->val, val);
+	}
+    else
+    /* In general case fetch list of regions that overlap us. 
+       Remaining cases to handle are: 
+	     r >> e     rrrrrrrrrrrrrrrrrrrr
+			     eeeeeeeeee
+
+	     e < r           rrrrrrrrrrrrrrr
+			eeeeeeeeeeee
+
+	     r < e      rrrrrrrrrrrr
+			     eeeeeeeeeeeee
+     */
+	{
+	struct range *existingList = rangeTreeAllOverlapping(tree, start, end);
+	int s = start;
+	for (existing = existingList; existing != NULL; existing = existing->next)
+	    {
+	    /* Deal with start of new range that comes before existing */
+	    if (s < existing->start)
+	        {
+		lmAllocVar(tree->lm, r);
+		r->start = s;
+		r->end = existing->start;
+		r->val = lmSlRef(lm, val);
+		s = existing->start;
+		rbTreeAdd(tree, r);
+		}
+	    else if (s > existing->start)
+	        {
+		lmAllocVar(tree->lm, r);
+		r->start = existing->start;
+		r->end = s;
+		r->val = existing->val;
+		existing->start = s;
+		rbTreeAdd(tree, r);
+		}
+	    if (existing->start < end && existing->end > end)
+	        {
+		lmAllocVar(tree->lm, r);
+		r->start = end;
+		r->end = existing->end;
+		r->val = existing->val;
+		existing->end = end;
+		rbTreeAdd(tree, r);
+		}
+	    lmRefAdd(lm, (struct slRef **)&existing->val, val);
+	    s = existing->end;
+	    }
+	if (s < end)
+	/* Deal with end of new range that doesn't overlap with anything. */
+	    {
+	    lmAllocVar(tree->lm, r);
+	    r->start = s;
+	    r->end = end;
+	    r->val = lmSlRef(lm, val);
+	    rbTreeAdd(tree, r);
+	    }
+	}
+    }
+}
+
 boolean rangeTreeOverlaps(struct rbTree *tree, int start, int end)
 /* Return TRUE if start-end overlaps anything in tree */
 {
 struct range tempR;
 tempR.start = start;
 tempR.end = end;
 tempR.val = NULL;
 return rbTreeFind(tree, &tempR) != NULL;
 }
 
 static void rangeListAdd(void *v, void *context)
 /* Callback to add item to range list. */
 {
 struct range *r = v;
 struct range **list = (struct range **)context;