lib/boxClump.c File Reference

#include "common.h"
#include "dlist.h"
#include "localmem.h"
#include "boxClump.h"

Include dependency graph for boxClump.c:

Go to the source code of this file.

Data Structures
struct	cluster
struct	box
struct	boxRef
Functions
void	boxClumpFree (struct boxClump **pClump)
void	boxClumpFreeList (struct boxClump **pList)
int	boxClumpCmpCount (const void *va, const void *vb)
static void	mergeClusters (struct cluster *a, struct cluster *b)
static boolean	allStartBy (struct boxRef *refList, int qStart, int tStart)
static boolean	allSameCluster (struct boxRef *refList)
static void	rBoxJoin (struct boxRef *refList, int qStart, int qEnd, int tStart, int tEnd)
boxClump *	boxFindClumps (struct boxIn **pBoxList)
Variables
static char const	rcsid [] = "$Id: boxClump.c,v 1.5 2005/01/10 00:11:34 kent Exp $"
static struct lm *	lm

---

Function Documentation

static boolean allSameCluster

(

struct boxRef *

refList

)

[static]

Definition at line 112 of file boxClump.c.

References boxRef::box, box::cluster, FALSE, boxRef::next, and TRUE.

Referenced by rBoxJoin().

{
struct boxRef *ref;
struct cluster *cluster = refList->box->cluster;
for (ref = refList->next; ref != NULL; ref = ref->next)
    {
    if (ref->box->cluster != cluster)
        return FALSE;
    }
return TRUE;
}

Here is the caller graph for this function:

static boolean allStartBy	(	struct boxRef *	refList,
		int	qStart,
		int	tStart
	)			[static]

Definition at line 96 of file boxClump.c.

References boxRef::box, FALSE, box::in, boxRef::next, and TRUE.

Referenced by rBoxJoin().

{
struct boxRef *ref;
for (ref = refList; ref != NULL; ref = ref->next)
    {
    struct boxIn *box = ref->box->in;
    if (box->qStart > qStart || box->tStart > tStart)
        return FALSE;
    }
return TRUE;
}

Here is the caller graph for this function:

int boxClumpCmpCount	(	const void *	va,
		const void *	vb
	)

Definition at line 39 of file boxClump.c.

References boxClump::boxCount.

{
const struct boxClump *a = *((struct boxClump **)va);
const struct boxClump *b = *((struct boxClump **)vb);
return b->boxCount - a->boxCount;
}

void boxClumpFree

(

struct boxClump **

pClump

)

Some simple utility function on globally declared data structures.

Definition at line 15 of file boxClump.c.

References boxClump::boxList, freez(), and slFreeList().

Referenced by boxClumpFreeList().

{
struct boxClump *clump = *pClump;
if (clump != NULL)
    {
    slFreeList(&clump->boxList);
    freez(pClump);
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

void boxClumpFreeList

(

struct boxClump **

pList

)

Definition at line 26 of file boxClump.c.

References boxClumpFree(), and boxClump::next.

Referenced by boxLump().

{
struct boxClump *el, *next;

for (el = *pList; el != NULL; el = next)
    {
    next = el->next;
    boxClumpFree(&el);
    }
*pList = NULL;
}

Here is the call graph for this function:

Here is the caller graph for this function:

struct boxClump* boxFindClumps

(

struct boxIn **

pBoxList

)

[read]

Definition at line 234 of file boxClump.c.

References AllocVar, BIGNUM, cluster::boxList, box::cluster, dlAddTail(), dlEnd, dlListInit(), dlList::head, box::in, lm, lmAllocVar, lmInit(), box::next, dlNode::next, boxIn::next, cluster::node, boxIn::qEnd, boxIn::qStart, rBoxJoin(), slAddHead, boxIn::tEnd, boxIn::tStart, and dlNode::val.

{
struct boxIn *in;
struct boxClump *clumpList = NULL, *clump;
struct boxRef *refList = NULL, *ref;
struct box *box;
struct cluster *cluster;
struct dlNode *node;
struct dlList clusterList;
int qStart = BIGNUM, qEnd = -BIGNUM;
int tStart = BIGNUM, tEnd = -BIGNUM;


dlListInit(&clusterList);
lm = lmInit(0);

/* Make local box structure, cluster, and reference
 * for each input box.  Calculate overall bounds. */
for (in = *pBoxList; in != NULL; in = in->next)
    {
    lmAllocVar(lm, box);
    box->in = in;
    if (in->qStart < qStart) qStart = in->qStart;
    if (in->qEnd > qEnd) qEnd = in->qEnd;
    if (in->tStart < tStart) tStart = in->tStart;
    if (in->tEnd > tEnd) tEnd = in->tEnd;
    lmAllocVar(lm,cluster);
    lmAllocVar(lm, cluster->node);
    cluster->node->val = cluster;
    dlAddTail(&clusterList, cluster->node);
    cluster->boxList = box;
    box->cluster = cluster;
    lmAllocVar(lm, ref);
    ref->box = box;
    slAddHead(&refList, ref);
    }

/* Call to recursive joiner. */
rBoxJoin(refList, qStart, qEnd, tStart, tEnd);

/* Copy from local memory and local data structures
 * to global memory and global data structures. */
for (node = clusterList.head; !dlEnd(node); node = node->next)
    {
    int boxCount = 0;
    int qStart = BIGNUM, qEnd = -BIGNUM;
    int tStart = BIGNUM, tEnd = -BIGNUM;
    struct boxIn *boxList = NULL;
    cluster = node->val;
    for (box = cluster->boxList; box != NULL; box = box->next)
        {
        in = box->in;
        slAddHead(&boxList, in);
        if (in->qStart < qStart) qStart = in->qStart;
        if (in->qEnd > qEnd) qEnd = in->qEnd;
        if (in->tStart < tStart) tStart = in->tStart;
        if (in->tEnd > tEnd) tEnd = in->tEnd;
        ++boxCount;
        }
    if (boxCount > 0)
        {
        AllocVar(clump);
        slAddHead(&clumpList, clump);
        clump->boxList = boxList;
        clump->boxCount = boxCount;
        clump->qStart = qStart;
        clump->qEnd = qEnd;
        clump->tStart = tStart;
        clump->tEnd = tEnd;
        }
    }
*pBoxList = NULL;
lmCleanup(&lm);
return clumpList;
}

Here is the call graph for this function:

static void mergeClusters	(	struct cluster *	a,
		struct cluster *	b
	)			[static]

Routines that cluster using mostly the local data structures.

Definition at line 76 of file boxClump.c.

References cluster::boxList, box::cluster, dlRemove(), box::next, cluster::node, and slCat().

Referenced by rBoxJoin().

{
struct box *box;

/* Merging with yourself is always problematic. */
if (a == b)
    return;

/* Point all boxes in b to a. */
for (box = b->boxList; box != NULL; box = box->next)
    box->cluster = a;

/* Add b's boxList to end of a's. */
a->boxList = slCat(a->boxList, b->boxList);

/* Remove b from master cluster list. */
dlRemove(b->node);
}

Here is the call graph for this function:

Here is the caller graph for this function:

static void rBoxJoin	(	struct boxRef *	refList,
		int	qStart,
		int	qEnd,
		int	tStart,
		int	tEnd
	)			[static]

Definition at line 128 of file boxClump.c.

References allSameCluster(), allStartBy(), boxRef::box, box::cluster, box::in, lm, lmAllocVar, mergeClusters(), box::next, boxRef::next, boxIn::qEnd, boxIn::qStart, rangeIntersection(), slAddHead, slCount(), boxIn::tEnd, and boxIn::tStart.

Referenced by boxFindClumps().

{
int boxCount = slCount(refList);

if (boxCount <= 1)
    {
    /* Easy: no merging required. */
    }
else if (boxCount == 2)
    {
    /* Decide if pair overlaps and if so merge. */
    struct box *a = refList->box;
    struct box *b = refList->next->box;
    if (rangeIntersection(a->in->qStart, a->in->qEnd, b->in->qStart, b->in->qEnd) > 0 &&
        rangeIntersection(a->in->tStart, a->in->tEnd, b->in->tStart, b->in->tEnd) > 0 )
        {
        mergeClusters(a->cluster, b->cluster);
        }
    else
        {
        /* Two non-overlapping boxes, we don't have to do anything. */
        }
    }
else if (allStartBy(refList, qStart, tStart))
    {
    /* If everybody contains the upper left corner, then they all can 
     * be merged.   This is the route taken often by clumps with lots
     * of overlap. */
    struct cluster *aCluster = refList->box->cluster;
    struct boxRef *ref;
    for (ref = refList->next; ref != NULL; ref = ref->next)
        {
        struct cluster *bCluster = ref->box->cluster;
        mergeClusters(aCluster, bCluster);
        }
    }
else if (allSameCluster(refList))
    {
    /* Everything is in the same cluster, no action required. */
    }
else
    {
    /* We can't yet figure out clumping, so break
     * up our window in two along larger dimension and
     * recurse on both subwindows. */
    struct boxRef *list1 = NULL, *list2 = NULL, *ref, *next;
    if (qEnd - qStart > tEnd - tStart)
        {
        int mid = (qStart + qEnd)>>1;
        for (ref = refList; ref != NULL; ref = next)
            {
            struct box *box = ref->box;
            next = ref->next;
            if (box->in->qEnd <= mid)
                {
                slAddHead(&list1, ref);
                }
            else if (box->in->qStart >= mid)
                {
                slAddHead(&list2, ref);
                }
            else
                {
                /* Box crosses boundary, have to put it on both lists. */
                slAddHead(&list1, ref);
                lmAllocVar(lm, ref);
                ref->box = box;
                slAddHead(&list2, ref);
                }
            }
        rBoxJoin(list1, qStart, mid, tStart, tEnd);
        rBoxJoin(list2, mid, qEnd, tStart, tEnd);
        }
    else
        {
        int mid = (tStart + tEnd)>>1;
        for (ref = refList; ref != NULL; ref = next)
            {
            struct box *box = ref->box;
            next = ref->next;
            if (box->in->tEnd <= mid)
                {
                slAddHead(&list1, ref);
                }
            else if (box->in->tStart >= mid)
                {
                slAddHead(&list2, ref);
                }
            else
                {
                /* Box crosses boundary, have to put it on both lists. */
                slAddHead(&list1, ref);
                lmAllocVar(lm, ref);
                ref->box = box;
                slAddHead(&list2, ref);
                }
            }
        rBoxJoin(list1, qStart, qEnd, tStart, mid);
        rBoxJoin(list2, qStart, qEnd, mid, tEnd);
        }
    }
}

Here is the call graph for this function:

Here is the caller graph for this function:

---

Variable Documentation

struct lm* lm [static]

Definition at line 125 of file boxClump.c.

Referenced by bandExt(), bandExtFf(), boxFindClumps(), chainBlocks(), cleanupMem(), dnaQuery(), ffAliFromSym(), ffFindExtendNmers(), ffSeedExtInMem(), genoFindDirect(), getHitsFromServer(), gfAlignTrans(), gfAlignTransTrans(), gfFastFindDnaHits(), gfFindAlignAaTrans(), gfFindClumps(), gfFindClumpsWithQmask(), gfFindHitsInRegion(), gfFindHitsWithQmask(), gfQuerySeqTrans(), gfQuerySeqTransTrans(), gfSegmentedFindHits(), gfSegmentedFindNearHits(), gfStraightFindHits(), gfStraightFindNearHits(), gfTransFindClumps(), gfTransTransFindBundles(), gfTransTransFindClumps(), initMem(), kdBuild(), kdTreeMake(), lmAlloc(), lmCleanup(), lmCloneMem(), lmCloneString(), lmInit(), lmSlName(), localNeedMem(), newBlock(), pslLoadLm(), pslxLoadLm(), rangeTreeNewDetailed(), rBoxJoin(), rbTreeNew(), rbTreeNewDetailed(), refineBundle(), scanIndexForSmallExons(), searchOneProt(), ssFindBestBig(), and transQuery().

char const rcsid[] = "$Id: boxClump.c,v 1.5 2005/01/10 00:11:34 kent Exp $" [static]

Definition at line 9 of file boxClump.c.

---