/*************************************************************/
/**** Header file for data types used in the EMST program ****/
/****        Created by Abhijit Das on 29-Oct-2012        ****/
/*************************************************************/

/* Data types for graphs and spanning forests */
typedef int vertex;                  /* A vertex is labeled by an integer */
typedef struct {
   vertex u, v;                      /* Vertex labels */
   double cost;                      /* Euclidean distance between u1 and u2 */
} edge;
typedef struct _adjnode {
   vertex v;                         /* Vertex label */
   double cost;                      /* Cost of the edge */
   struct _adjnode *next;            /* Pointer to next neighbor */
} adjNode;
typedef struct {
   int n;                            /* Count of vertices */
   int e;                            /* Count of edges */
   adjNode **E;                      /* Adjacency list headers */
} graph;
typedef struct {
   int n;                            /* Cuont of vertices */
   int e;                            /* Cuont of edges */
   double cost;                      /* Cost of the spanning forest */
   edge *E;                          /* Array of edges in the MSF */
} SF;                                /* Data type for spanning forest */

/* Data types for two-dimensional hash table */
typedef struct _node {
   vertex v;                          /* Vertex label */
   struct _node *next;                /* Pointer to next node */
} hashNode;
typedef hashNode *hashNodePointer;
typedef struct {
   int n;                             /* Count of points */
   int m;                             /* Dimension (m x m) of the hash table */
   double *x, *y;                     /* Coordinates of all points */
   hashNodePointer **hdr;             /* Two-dimensional array of headers */
} hashTable;

/* Data types for min-priority queues */
typedef struct {
   int size;                         /* Number of elements in the size */
   edge *E;                          /* Edges in contiguous representation */
} heap;

/* Data types for merge-find sets */
typedef struct _treenode {
   int size;                         /* Count of nodes in the MF tree */
   struct _treenode *parent;         /* Only the parent pointer is needed */
} treeNode;
typedef treeNode **MFSet;            /* Headers to nodes in the MF trees */

#define C1 1.5
#define C2 1.1

/* End of EMST.h */