heap.h

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

/*
 * heap.h
 *
 * Header file for an implementation of a heap to be used by the accompanying
 * Matlab lattice decoders. Can be compiled into a standalone library or using
 * mex into a Matlab library. Pre-compiled for Matlab 7.0.1 R14SP1 (Linux) and
 * Matlab 6.5 R13 (Windows); for best effect, re-compile for other releases.
 *
 * Version 1.0, copyright 2006 by Karen Su ([e-mail]).
 * Version 1.1
 *   Fixed heapDelMin; added heapGetMaxSize, heapGetDim and appropriate interfaces.
 * Version 1.2
 *   Fixed heapInsert; added heap.pLastDel to replace global pLastDelNode;
 *   modified heapGetMin to return key == -1 (invalid value) if heap is empty.
 */

#ifndef __heap_h__
#define __heap_h__

#include "mex.h"

enum HTYPE { BASIC   = 0,
             LATTICE = 1, 
             LAST    = 2 };

struct heap {
  struct hNode* pRoot;
  int           nNodes;
  int           spdim;
  int           maxNodes;
  int           type;
  struct hNode* pLastDel;
};

struct hNode {
  double  key;
  double* pY;
  double* pZ;
  int     dim;

  struct hNode* pPar;
  struct hNode* pLCh;
  struct hNode* pRCh;
};

struct hNodeI {
  double  key;
  double* pY;
  double* pZ;
  int     dim;

  struct hNode* pPar;
  struct hNode* pLCh;
  struct hNode* pRCh;

  int     cnum;
  double  pweight;
  double  utarget;
  double  delta;
};

struct hNodeL {
  double  key;
  double* pY;
  double* pZ;
  int     dim;

  struct hNode* pPar;
  struct hNode* pLCh;
  struct hNode* pRCh;

  int     cnum;
  double  pweight;
  double  utarget;
  double  delta;

  double* pA;
  double  sqradius;
  int     lbound;
  int     ubound;
  double  uoffset;
};

struct hNodeS {
  double  key;
  double* pY;
  double* pZ;
  int     dim;

  struct hNode* pPar;
  struct hNode* pLCh;
  struct hNode* pRCh;

  int     cnum;
  double  pweight;
  double  utarget;
  double  delta;
  
  double  fgchild;
  double  bweight;
  double* pProj;
};

struct heap  *heapInit(int M, int type);
struct heap  *heapInitT(int M, int T, int type);

int           heapInsertB(double       key,  
                          double      *pY,      
                          double      *pZ,      
                          int          dim, 
                          struct heap *pH);
int           heapInsertI(double       key,  
                          double      *pY,      
                          double      *pZ,      
                          int          dim, 
                          int          cnum, 
                          double       pweight, 
                          double       utarget, 
                          double       delta, 
                          struct heap *pH);
int           heapInsertL(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 hNode *heapNewNode(double       key,  
                          double      *pY,      
                          double      *pZ,      
                          int          dim, 
                          struct heap *pH);
int           heapInsert(struct hNode *pNewNode, struct heap *pH);

struct hNode *heapGetMin(struct heap *pH);
int           heapReplaceMinb(double       key,  
                              double      *pY,      
                              double      *pZ,      
                              int          dim, 
                              struct heap *pH);
int           heapReplaceMini(double       key,  
                              double      *pY,      
                              double      *pZ,      
                              int          dim, 
                              int          cnum, 
                              double       pweight, 
                              double       utarget, 
                              double       delta, 
                              struct heap *pH);
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);

int           heapDelMin(struct heap *pH);

int           heapBubbleUp(struct heap *pH, struct hNode *pNewNode);
int           heapBubbleDown(struct heap *pH);

void          hNodeFree(struct hNode *pNode);
void          hNodeLFree(struct hNodeL *pNode);
void          heapClear(struct heap *pH);
void          heapDelete(struct heap *pH);

void          hNodePrintContents(struct hNode *pNode, int dim, int spdim);
void          heapPrintContents(struct heap *pH);
void          heapPrintUsage();

int           heapGetSize(struct heap *pH);
int           heapGetMaxSize(struct heap *pH);
int           heapGetDim(struct heap *pH);

#endif /* __heap_h__ */