heap.c

Stack-based sequential decoder for M-QAM modulated MIMO-type problems, i.e., of fixed tree depth.

                    double       pweight, 
                    double       utarget, 
                    double       delta, 
                    struct heap *pH) {
  struct hNodeI *pMinNodei;
  int            nSwaps = 0;

  pMinNodei = (struct hNodeI *)heapGetMin(pH);
  if (pMinNodei) {                      
    pMinNodei->key     = key;
    if (pY) { memcpy(pMinNodei->pY, pY, dim*sizeof(double)); }
    pMinNodei->pZ      = pMinNodei->pY+dim;
    if (pZ) { memcpy(pMinNodei->pZ, pZ, (pH->spdim-dim)*sizeof(double)); }
    pMinNodei->dim     = dim;

    pMinNodei->cnum    = cnum;
    pMinNodei->pweight = pweight;
    pMinNodei->utarget = utarget;
    pMinNodei->delta   = delta;

#ifdef DEBUG
    printf("Intermediate heap:\n");
    heapPrintContents(pH);
#endif

    if (pH->pRoot->pLCh) { nSwaps = heapBubbleDown(pH); }

  } else { nSwaps = heapInsertI(key, pY, pZ, dim, cnum, pweight, utarget, delta, pH); }
  
  return nSwaps;
}

int heapReplaceMinl(double       key, 
                    double      *pY, 
                    double      *pZ, 
                    int          dim, 
                    int          cnum, 
                    double       pweight, 
                    double       utarget, 
                    double       delta, 
                    double      *pA,
                    double       sqradius,
                    int          lbound,
                    int          ubound,
                    double       uoffset,
                    struct heap *pH) {
  struct hNodeL *pMinNodel;
  int            nSwaps = 0;

  pMinNodel = (struct hNodeL *)heapGetMin(pH);
  if (pMinNodel) {                      
    pMinNodel->key     = key;
    if (pY) { memcpy(pMinNodel->pY, pY, dim*sizeof(double)); }
    pMinNodel->pZ      = pMinNodel->pY+dim;
    if (pZ) { memcpy(pMinNodel->pZ, pZ, (pH->spdim-dim)*sizeof(double)); }
    pMinNodel->dim     = dim;

    pMinNodel->cnum    = cnum;
    pMinNodel->pweight = pweight;
    pMinNodel->utarget = utarget;
    pMinNodel->delta   = delta;

    if (pA) { memcpy(pMinNodel->pA, pA, dim*sizeof(double)); }
    pMinNodel->sqradius = sqradius;
    pMinNodel->lbound   = lbound;
    pMinNodel->ubound   = ubound;
    pMinNodel->uoffset  = uoffset;

#ifdef DEBUG
    printf("Intermediate heap:\n");
    heapPrintContents(pH);
#endif

    if (pH->pRoot->pLCh) { nSwaps = heapBubbleDown(pH); }

  } else { nSwaps = heapInsertI(key, pY, pZ, dim, cnum, pweight, utarget, delta, pH); }
  
  return nSwaps;
}

int heapDelMini(struct heap *pH) {
  struct hNode *pNode  = heapGetMin(pH);
  int           nSwaps = heapDelMin(pH);

  if (pNode) {
    pNode->pPar = NULL;
    pNode->pLCh = NULL;
    pNode->pRCh = NULL;
    hNodeFree(pNode);
  }

  return nSwaps;
}

int heapDelMinl(struct heap *pH) {
  struct hNode *pNode  = heapGetMin(pH);
  int           nSwaps = heapDelMin(pH);

  if (pNode) {
    pNode->pPar = NULL;
    pNode->pLCh = NULL;
    pNode->pRCh = NULL;
    hNodeLFree((struct hNodeL *)pNode);
  }

  return nSwaps;
}

int heapDelMin(struct heap *pH) {
  struct hNode *pDelNode, *pParentNode;
  int           lastNodeIndex, ii, nSwaps = 0;

  pDelNode      = heapGetMin(pH);
  lastNodeIndex = pH->nNodes;

#ifdef DEBUG
  printf("Promoting node %i: ",lastNodeIndex);
#endif

  if (pDelNode) {         /* there is at least one node in the heap */

    if (pDelNode->pLCh) { /* find which node to promote, bubble */
      pParentNode = pDelNode;

      for (ii = (int)floor(log(lastNodeIndex)/log(2)-1); ii > 0; ii--) {
        if (lastNodeIndex&(1<<ii)) {        /* follow right child path */

#ifdef DEBUG
          printf("Right "); 
#endif

          pParentNode = pParentNode->pRCh; 
        } else {                           /* follow left child path */

#ifdef DEBUG
          printf("Left "); 
#endif
        
          pParentNode = pParentNode->pLCh; 
        }
      }

      if (lastNodeIndex&1) {           /* promote right child */

#ifdef DEBUG
        printf("PromoteRight\n"); 
#endif
    
        pH->pRoot       = pParentNode->pRCh;
        pH->pRoot->pPar = NULL;

        /* link left child */
        pH->pRoot->pLCh = pDelNode->pLCh;
        if (pDelNode->pLCh) { pDelNode->pLCh->pPar = pH->pRoot; } 

        /* link right child if not circular */
        if (pDelNode->pRCh != pH->pRoot) {
          pH->pRoot->pRCh = pDelNode->pRCh;
          if (pDelNode->pRCh) { pDelNode->pRCh->pPar = pH->pRoot; }
        }

        /* unlink old parent */
        pParentNode->pRCh = NULL;

      } else {                         /* promote left child */

#ifdef DEBUG
        printf("PromoteLeft\n"); 
#endif
   
        pH->pRoot       = pParentNode->pLCh;
        pH->pRoot->pPar = NULL;

        /* link right child */
        pH->pRoot->pRCh = pDelNode->pRCh;
        if (pDelNode->pRCh) { pDelNode->pRCh->pPar = pH->pRoot; }

        /* link left child if not circular */
        if (pDelNode->pLCh != pH->pRoot) {
          pH->pRoot->pLCh = pDelNode->pLCh;
          if (pDelNode->pLCh) { pDelNode->pLCh->pPar = pH->pRoot; }
        }

        /* unlink old parent */
        pParentNode->pLCh = NULL;
      } 

#ifdef DEBUG
      printf("Intermediate heap:\n");
      heapPrintContents(pH);
#endif

      nSwaps = heapBubbleDown(pH);
    } else {             /* pDelNode != NULL, but has no children */

#ifdef DEBUG
      printf("NoNodestoPromote\n"); 
#endif

      pH->pRoot = NULL;
    }
  
    pH->nNodes--; 

  } else {               /* pDelNode == NULL */

#ifdef DEBUG
    printf("NoNodesinHeap\n"); 
#endif

  }

  return nSwaps;
}

int heapBubbleUp(struct heap *pH, struct hNode *pNewNode) {
  struct hNode *pTempPar, *pTempLCh, *pTempRCh;
  int           nSwaps = 0;

#ifdef DEBUG
  printf("BubblingUp: ");
#endif

  while (pNewNode->pPar && ( pNewNode->key < pNewNode->pPar->key ||
			     ( pNewNode->key == pNewNode->pPar->key &&
			       pNewNode->dim < pNewNode->pPar->dim) ) ) {
    pTempPar = pNewNode->pPar;
    pTempRCh = pNewNode->pRCh;
    pTempLCh = pNewNode->pLCh;
    nSwaps++;

    /* link grandparent or root as parent */
    if (pTempPar->pPar) { 
      if (pTempPar->pPar->pLCh == pTempPar) { /* TempPar was left child */
        pTempPar->pPar->pLCh = pNewNode;
      } else {                                /* TempPar was right child */
        pTempPar->pPar->pRCh = pNewNode;
      }
      pNewNode->pPar = pTempPar->pPar;
    } else {
      pH->pRoot = pNewNode;
      pNewNode->pPar = NULL;
    }

    if (pTempPar->pLCh == pNewNode) {  /* parent becomes left child */

      /* link right sibling as right child */
      pNewNode->pRCh = pTempPar->pRCh;
      if (pTempPar->pRCh) { pTempPar->pRCh->pPar = pNewNode; }

      /* link parent as left child */
      pNewNode->pLCh = pTempPar;
      pTempPar->pPar = pNewNode;

#ifdef DEBUG
      printf("SwapLeft "); 
#endif

    } else {                                 /* parent becomes right child */

      /* link left sibling as left child */
      pNewNode->pLCh = pTempPar->pLCh;
      if (pTempPar->pLCh) { pTempPar->pLCh->pPar = pNewNode; }

      /* link parent as right child */
      pNewNode->pRCh = pTempPar;
      pTempPar->pPar = pNewNode;

#ifdef DEBUG
      printf("SwapRight "); 
#endif

    }

    /* link left child as left grandchild */
    pTempPar->pLCh = pTempLCh;
    if (pTempPar->pLCh) { pTempPar->pLCh->pPar = pTempPar; }

    /* link right child as right grandchild */
    pTempPar->pRCh = pTempRCh;
    if (pTempPar->pRCh) { pTempPar->pRCh->pPar = pTempPar; }

  }  /* while */

#ifdef DEBUG
  printf("\n"); 
#endif

  return nSwaps;
}

int heapBubbleDown(struct heap *pH) {
  struct hNode *pTempNode, *pTempLCh, *pTempRCh, *pNewNode;
  bool          swapLCh, swapRCh;
  int           nSwaps = 0;

#ifdef DEBUG
  printf("BubblingDown: ");
#endif

  /* always bubble down from the root */
  pNewNode = pH->pRoot;
  swapLCh = pNewNode->pLCh && 
	      ( pNewNode->pLCh->key < pNewNode->key ||
	        ( pNewNode->pLCh->key == pNewNode->key && 
	          pNewNode->pLCh->dim < pNewNode->dim)  );
  swapRCh = pNewNode->pRCh &&
	      ( pNewNode->pRCh->key < pNewNode->key ||
	        ( pNewNode->pRCh->key == pNewNode->key && 
	          pNewNode->pRCh->dim < pNewNode->dim)  );
  if (swapLCh && swapRCh) {
    swapLCh = ( pNewNode->pLCh->key < pNewNode->pRCh->key ||
	        ( pNewNode->pLCh->key == pNewNode->pRCh->key && 
	          pNewNode->pLCh->dim <= pNewNode->pRCh->dim)  );
    swapRCh = !swapLCh;
  }

  while (swapLCh || swapRCh) {
    nSwaps++;

    if (swapLCh) {                           /* left child becomes parent */
      pTempNode = pNewNode->pLCh;
      pTempLCh  = pTempNode->pLCh;
      pTempRCh  = pTempNode->pRCh;

      /* link right child as right sibling */
      pTempNode->pRCh = pNewNode->pRCh;
      if (pNewNode->pRCh) { pNewNode->pRCh->pPar = pTempNode; }

      /* link left child as parent */
      pTempNode->pLCh = pNewNode;
      /* Can't do this here cuz still need pNewNode->pPar */
      /* pNewNode->pPar = pTempNode; */

#ifdef DEBUG
      printf("SwapLeft "); 
#endif

    } else {                                 /* right child becomes parent */
      pTempNode = pNewNode->pRCh;
      pTempLCh  = pTempNode->pLCh;
      pTempRCh  = pTempNode->pRCh;

      /* link left child as left sibling */
      pTempNode->pLCh = pNewNode->pLCh;
      if (pNewNode->pLCh) { pNewNode->pLCh->pPar = pTempNode; }

      /* link right child as parent */
      pTempNode->pRCh = pNewNode;
      /* Can't do this here cuz still need pNewNode->pPar */
      /* pNewNode->pPar = pTempNode; */