<commit_before>/*
 * Module implementing a priority queue in the C programming language.
 * <NAME> - mbabic
 * Some details cribbed from rosettacode.rog/wiki/Priority_queue
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include "pqueue.h"

/**
 * Prints memory allocation error message.
 */
static void
pqueue_allocation_error() {
        fprintf(stderr, "Memory allocation failed.\n %s: %d\n", __FILE__,
                        __LINE__);
        exit(1);
}

/**
 * Allocates more memory to accomodate growing pqueue.
 * @param PQueue *pq
 *      Pointer to the pqueue to be grown.
 */
static void
pqueue_grow(PQueue *pq) {

        PQueueElement *tmp;
        pq->sz *= 2;

        tmp = realloc(pq->elements, pq->sz * sizeof(PQueueElement));
        if (!tmp) pqueue_allocation_error();

        pq->elements = tmp;

}

PQueue *
pqueue_init(int sz, double (*calculate_priority)(void *)) {

        PQueue *pq;

        pq = malloc(sizeof(PQueue));
        if (!pq) pqueue_allocation_error();
        
        sz = sz < MIN_PQUEUE_SIZE ? MIN_PQUEUE_SIZE : sz;
        pq->sz = sz;

        pq->elements = malloc(pq->sz * sizeof(PQueueElement));
        if (!pq->elements) pqueue_allocation_error();

        pq->nElements = 1;
        pq->calculate_priority = calculate_priority;

        return pq;
}


void
pqueue_enqueue(PQueue *pq, void *pqueue_elem_data) {

        double element_priority;
        int k, level;

        assert(pq->nElements <= pq->sz);

        if (pq->nElements == pq->sz) pqueue_grow(pq);

        k = pq->nElements++;
               
        element_priority = pq->calculate_priority(pqueue_elem_data);

        printf("%f\n", element_priority);

        /* Bubble new element up the heap into correct position. */
        while ((level =  k / 2) && 
                        (element_priority < pq->elements[level].priority)) {
                
                pq->elements[k].data = pq->elements[level].data;
                pq->elements[k].priority = pq->elements[level].priority;
                k = level;
        }
        pq->elements[k].data = pqueue_elem_data;
        pq->elements[k].priority = element_priority;
}

void 
pqueue_dequeue(PQueue *pq, void **data, double *priority) {

        int k, level;
        /* If queue is empty, return null pointer. */
        if (pq->nElements <= 1 && data) *data = NULL;
        else if (pq->nElements <= 1) return;

        if (data) *data = pq->elements[1].data; 
        if (priority) *priority = pq->elements[1].priority;

        /* Re-order queue. */
        pq->nElements--;
        k = 1;
        while ((level = k * 2) < pq->nElements) {
                if (level+1 < pq->nElements &&
                    (pq->elements[level].priority > 
                     pq->elements[level+1].priority)) 
                        level++;

                if (pq->elements[pq->nElements].priority <=
                    pq->elements[level].priority) break;

                pq->elements[k].data = pq->elements[level].data;
                pq->elements[k].priority = pq->elements[level].priority;<commit_msg>pqueue adt implementation changed such that it is now a max-priority queue.<commit_after>/*
 * Module implementing a max priority queue in the C programming language.
 * <NAME> - mbabic
 * Some details cribbed from rosettacode.rog/wiki/Priority_queue
 */

#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include "pqueue.h"

/**
 * Prints memory allocation error message.
 */
static void
pqueue_allocation_error() {
        fprintf(stderr, "Memory allocation failed.\n %s: %d\n", __FILE__,
                        __LINE__);
        exit(1);
}

/**
 * Allocates more memory to accomodate growing pqueue.
 * @param PQueue *pq
 *      Pointer to the pqueue to be grown.
 */
static void
pqueue_grow(PQueue *pq) {

        PQueueElement *tmp;
        pq->sz *= 2;

        tmp = realloc(pq->elements, pq->sz * sizeof(PQueueElement));
        if (!tmp) pqueue_allocation_error();

        pq->elements = tmp;

}

PQueue *
pqueue_init(int sz, double (*calculate_priority)(void *)) {

        PQueue *pq;

        pq = malloc(sizeof(PQueue));
        if (!pq) pqueue_allocation_error();
        
        sz = sz < MIN_PQUEUE_SIZE ? MIN_PQUEUE_SIZE : sz;
        pq->sz = sz;

        pq->elements = malloc(pq->sz * sizeof(PQueueElement));
        if (!pq->elements) pqueue_allocation_error();

        pq->nElements = 1;
        pq->calculate_priority = calculate_priority;

        return pq;
}


void
pqueue_enqueue(PQueue *pq, void *pqueue_elem_data) {

        double element_priority;
        int k, level;

        assert(pq->nElements <= pq->sz);

        if (pq->nElements == pq->sz) pqueue_grow(pq);

        k = pq->nElements++;
               
        element_priority = pq->calculate_priority(pqueue_elem_data);

        printf("%f\n", element_priority);

        /* Bubble new element up the heap into correct position. */
        while ((level =  k / 2) && 
                        (element_priority > pq->elements[level].priority)) {
                
                pq->elements[k].data = pq->elements[level].data;
                pq->elements[k].priority = pq->elements[level].priority;
                k = level;
        }
        pq->elements[k].data = pqueue_elem_data;
        pq->elements[k].priority = element_priority;
}

void 
pqueue_dequeue(PQueue *pq, void **data, double *priority) {

        int k, level;
        /* If queue is empty, return null pointer. */
        if (pq->nElements <= 1 && data) *data = NULL;
        else if (pq->nElements <= 1) return;

        if (data) *data = pq->elements[1].data; 
        if (priority) *priority = pq->elements[1].priority;

        /* Re-order queue. */
        pq->nElements--;
        k = 1;
        while ((level = k * 2) < pq->nElements) {
                if (level+1 < pq->nElements &&
                    (pq->elements[level].priority < 
                     pq->elements[level+1].priority)) 
                        level++;

                if (pq->elements[pq->nElements].priority >=
                    pq->elements[level].priority) break;

                pq->elements[k].data = pq->elements[level].data;
                pq->elements[k].priority = pq->elements[level].priority;
{'fraction_non_alphanumeric': 0.1365231259968102, 'fraction_numerical': 0.003827751196172249, 'mean_word_length': 2.0250844187168355, 'pattern_counts': {'":': 0, '<': 26, '<?xml version=': 0, '>': 92, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '2719197', 'n_tokens_mistral': 2039, 'n_tokens_neox': 1875, 'n_words': 441}