structures.h

#define HASH_SIZE 256

typedef struct node
{
    unsigned char item;
    long int q;
    struct node *left;
    struct node *right;
    struct node *next;
    struct node *previous;
}node;

typedef struct byte
{
    unsigned char item;
    long int position;
}byte;

typedef struct pq
{
    node *head;
}pq;

typedef struct queue
{
    node *front;
    node *rear;
}queue;

typedef struct hash_node
{
    queue *fila;
    struct hash_node *next;
}hn;

typedef struct hash_table
{
    hn *table[HASH_SIZE];
}hash_table;

byte * create_byte(unsigned char item)
{
    byte *new_byte = (byte*) malloc(sizeof(new_byte));
    new_byte->item = item;
    new_byte->position = 7;
    return new_byte;
}

hash_table *create_hash_table()
{
    int i;
    hash_table *new_hash_table = (hash_table*) malloc(sizeof(hash_table));
    for (i = 0; i < HASH_SIZE; ++i)
    {
        new_hash_table->table[i] = NULL;
    }
    return new_hash_table;
}

hn *create_hash_node(hn *head, queue *fila)
{
    hn *new_node = (hn*) malloc(sizeof(hn));
    new_node->fila = fila;
    return new_node;
}

void put(hash_table *ht,unsigned char item,queue *fila)
{
    long int h = (long int) item;
    ht->table[h] = create_hash_node(ht->table[h],fila);
}


pq *create_pq()
{
    pq *new_pq = (pq*) malloc(sizeof(pq));
    new_pq->head = NULL;
    return new_pq;
}

queue *create_queue()
{
    queue *new_queue = (queue*) malloc(sizeof(queue));
    new_queue->front = new_queue->rear = NULL;
    return new_queue;
}

node *create_empty_node()
{
    return NULL;
}

node *create_node(unsigned char l, long int q)
{
    node *new_node = (node*) malloc(sizeof(node));
    new_node->item = l;
    new_node->q = q;
    new_node->left = NULL;
    new_node->right = NULL;
    new_node->next = NULL;
    return new_node;
}

node *create_tree_node(unsigned char item, long int q, node *left, node *right)
{
    node *new_node = (node*) malloc(sizeof(node));
    new_node->item = item;
    new_node->q = q;
    new_node->left = left;
    new_node->right = right;
    return new_node;
}

node *add(node *head,unsigned char item)
{
    if(head!=NULL)
    {
        if (head->item == item)
        {
            head->q++;
            return head;
        }
        head->next = add(head->next,item);
        return head;
    }

    node *new_node = malloc(sizeof(node));
    new_node->item = item;
    new_node->q = 1;
    new_node->next = NULL;
    return new_node;
}

void enqueue(queue *queue,char item)
{
    node *new_node = (node*) malloc(sizeof(node));
    new_node->item = item;
    new_node->next = NULL;
    new_node->previous = queue->rear;
    if (queue->front == NULL && queue->rear == NULL)
    {
        queue->rear = queue->front = new_node;
    }
    else
    {
        queue->rear->next = new_node;
        queue->rear = new_node;
    }
}   

void enqueue_pq(pq *queue, node *head)
{
        node *new_node = (node*) malloc(sizeof(node));
        new_node->item = head->item;
        new_node->q = head->q;
        if (queue->head == NULL ||(head->q < queue->head->q))
        {
                new_node->next = queue->head;
                queue->head = new_node;
        }
        else
        {
            node *temp = queue->head;
            while((temp->next != NULL) && (temp->next->q < head->q))
            {
                temp = temp->next;
            }
                new_node->next = temp->next;
                temp->next = new_node;
        }
}

void enqueue_tree(pq *queue, node *head,node*left,node *right)
{
        node *new_node = create_tree_node(head->item,head->q,left,right);
        if (queue->head == NULL  || (head->q < queue->head->q))
        {
                new_node->next = queue->head;
                queue->head = new_node;
        }
        else if (head->q == queue->head->q)
        {
            if (head->item == '*')
            {
                new_node->next = queue->head;
                queue->head = new_node;
            }
        }
        else
        {
            node *temp = queue->head;
            while((temp->next != NULL) && (temp->next->q < head->q))
            {
                temp = temp->next;
            }
                new_node->next = temp->next;
                temp->next = new_node;
        }
}

node *dequeue_pq(pq *queue)
{
    if (queue->head != NULL)
    {
        //printf("aqui\n");
        node *temp = queue->head;
        queue->head = queue->head->next;
        return temp;
    }
    else
    {
        return NULL;
    }
}

unsigned char dequeue(queue *queue)
{
    node *temp = queue->rear;
    if(queue->front == NULL)
    {
        return 1;
    }
    if (queue->front == queue->rear)
    {
        queue->front = queue->rear = NULL;
    }
    else
    {
        queue->rear = queue->rear->previous;
        queue->rear->next = NULL;
    }

    return temp->item;

}

void merge(node *bt,node *left, node *right,pq *queue)
{
    bt = create_node('*', left->q + right->q);
    bt->left = left;
    bt->right = right;
    enqueue_tree(queue,bt,bt->left,bt->right);
}

void print(node *head)
{
    node *temp = head;
    while(temp != NULL)
    {
        printf("%c %ld\n",temp->item,temp->q);
        temp = temp->next;
    }
}

void print_queue(queue *queue)
{
    node *temp = queue->front;
    while(temp != NULL)
    {
        printf("%c",temp->item );
        temp = temp->next;
    }
    printf("\n");
}

void print_pq(pq *queue)
{
    node *temp = queue->head;
    while(temp != NULL)
    {
        printf("%c",temp->item );
        temp = temp->next;
    }
    printf("\n");
}


void print_tree(node *head)
{
    if(head != NULL)
    {
        printf("%c",head->item);
        print_tree(head->left);
        print_tree(head->right);
    }
}

void print_tree_file(node *head,FILE *new)
{
    unsigned char scape = '\\';
    if(head != NULL)
    {
        if (head->left == NULL && head->right == NULL)
        {
            if (head->item == '*' || head->item == '\\')
            {
                fputc(scape,new);
            }
        }
        fprintf(new,"%c",head->item);
        print_tree_file(head->left,new);
        print_tree_file(head->right,new);
    }
}

void print_hash_table(hash_table *ht)
{
    int i;
    for (i = 65; i < 71; ++i)
    {
        printf("%c ->",i);
        hn *temp = ht->table[i];
        while(temp != NULL)
        {
            node *temp2 = temp->fila->front;
            while (temp2 != NULL)
            {
                printf("%c",temp2->item);
                temp2 = temp2->next;
            }
            temp = temp->next;
        }
        printf("\n");
    }
}