4
\$\begingroup\$

When I saw this amazing data structure I couldn't stop myself from trying it! I first sought resources such as this and an article about it here. It basically works as a Max-Heap and a Min-Heap at the same time. I was heavily based on these amazing Java implementations here and here.

This implementation is a macro that generates code for whichever data type you wish to work with and it is part of the C Macro Collections library currently hosted on GitHub and further to be improved when needed.

The main macro is INTERVALHEAP_GENERATE with the following parameters:

  • PFX - Functions prefix
  • SNAME - The struct name
  • FMOD - Function modifier (currently only static or empty)
  • V - Data type you wish to work with

All you need to get started is the header intervalheap.h. Now since a question is limited to 65536 characters I had to strip down a lot of code and lines so that it could fit in this question since the macro takes a lot of characters. The code might seem a bit squished together but you can find the original code (and maybe in the future, updated) here.

intervalheap.h

#ifndef CMC_INTERVALHEAP_H
#define CMC_INTERVALHEAP_H

#include <stdlib.h>
#include <stdbool.h>
#include <string.h>

#define INTERVALHEAP_GENERATE(PFX, SNAME, FMOD, V)    \
    INTERVALHEAP_GENERATE_HEADER(PFX, SNAME, FMOD, V) \
    INTERVALHEAP_GENERATE_SOURCE(PFX, SNAME, FMOD, V)

/* HEADER ********************************************************************/
#define INTERVALHEAP_GENERATE_HEADER(PFX, SNAME, FMOD, V)                    \
                                                                             \
    /* Heap Structure */                                                     \
    typedef struct SNAME##_s                                                 \
    {                                                                        \
        /* Dynamic array of nodes */                                         \
        struct SNAME##_node_s *buffer;                                       \
        /* Current array capacity (how many nodes can be stored) */          \
        size_t capacity;                                                     \
        /* Current amount of nodes in the dynamic array */                   \
        size_t size;                                                         \
        /* Current amount of elements in the heap */                         \
        size_t count;                                                        \
        /* Element comparison function */                                    \
        int (*cmp)(V, V);                                                    \
        /* Function that returns an iterator to the start of the heap */     \
        struct SNAME##_iter_s (*it_start)(struct SNAME##_s *);               \
        /* Function that returns an iterator to the end of the heap */       \
        struct SNAME##_iter_s (*it_end)(struct SNAME##_s *);                 \
    } SNAME, *SNAME##_ptr;                                                   \
                                                                             \
    /* Heap Node */                                                          \
    typedef struct SNAME##_node_s                                            \
    {                                                                        \
        /* 0 - Value belonging to the MinHeap */                             \
        /* 1 - Value belonging to the MaxHeap */                             \
        V data[2];                                                           \
    } SNAME##_node, *SNAME##_node_ptr;                                       \
                                                                             \
    /* Heap Iterator */                                                      \
    typedef struct SNAME##_iter_s                                            \
    {                                                                        \
        /* Target heap */                                                    \
        struct SNAME##_s *target;                                            \
        /* Cursor's position (index) */                                      \
        size_t cursor;                                                       \
        /* If the iterator has reached the start of the iteration */         \
        bool start;                                                          \
        /* If the iterator has reached the end of the iteration */           \
        bool end;                                                            \
    } SNAME##_iter, *SNAME##_iter_ptr;                                       \
                                                                             \
    FMOD SNAME *PFX##_new(size_t capacity, int (*compare)(V, V));            \
    FMOD void PFX##_clear(SNAME *_heap_);                                    \
    FMOD void PFX##_free(SNAME *_heap_);                                     \
    FMOD bool PFX##_insert(SNAME *_heap_, V element);                        \
    FMOD bool PFX##_remove_max(SNAME *_heap_, V *result);                    \
    FMOD bool PFX##_remove_min(SNAME *_heap_, V *result);                    \
    FMOD bool PFX##_insert_if(SNAME *_heap_, V element, bool condition);     \
    FMOD bool PFX##_remove_max_if(SNAME *_heap_, V *result, bool condition); \
    FMOD bool PFX##_remove_min_if(SNAME *_heap_, V *result, bool condition); \
    FMOD bool PFX##_update_max(SNAME *_heap_, V element);                    \
    FMOD bool PFX##_update_min(SNAME *_heap_, V element);                    \
    FMOD bool PFX##_max(SNAME *_heap_, V *value);                            \
    FMOD bool PFX##_min(SNAME *_heap_, V *value);                            \
    FMOD bool PFX##_contains(SNAME *_heap_, V element);                      \
    FMOD bool PFX##_empty(SNAME *_heap_);                                    \
    FMOD bool PFX##_full(SNAME *_heap_);                                     \
    FMOD size_t PFX##_count(SNAME *_heap_);                                  \
    FMOD size_t PFX##_capacity(SNAME *_heap_);                               \
                                                                             \
    FMOD SNAME##_iter *PFX##_iter_new(SNAME *target);                        \
    FMOD void PFX##_iter_free(SNAME##_iter *iter);                           \
    FMOD void PFX##_iter_init(SNAME##_iter *iter, SNAME *target);            \
    FMOD bool PFX##_iter_start(SNAME##_iter *iter);                          \
    FMOD bool PFX##_iter_end(SNAME##_iter *iter);                            \
    FMOD void PFX##_iter_to_start(SNAME##_iter *iter);                       \
    FMOD void PFX##_iter_to_end(SNAME##_iter *iter);                         \
    FMOD bool PFX##_iter_next(SNAME##_iter *iter);                           \
    FMOD bool PFX##_iter_prev(SNAME##_iter *iter);                           \
    FMOD V PFX##_iter_value(SNAME##_iter *iter);                             \
    FMOD size_t PFX##_iter_index(SNAME##_iter *iter);                        \
                                                                             \
    /* Default Value */                                                      \
    static inline V PFX##_impl_default_value(void)                           \
    {                                                                        \
        V _empty_value_;                                                     \
                                                                             \
        memset(&_empty_value_, 0, sizeof(V));                                \
                                                                             \
        return _empty_value_;                                                \
    }

#define INTERVALHEAP_GENERATE_SOURCE(PFX, SNAME, FMOD, V)                                   \
                                                                                            \
    /* Implementation Detail Functions */                                                   \
    static bool PFX##_impl_grow(SNAME *_heap_);                                             \
    static void PFX##_impl_float_up_max(SNAME *_heap_);                                     \
    static void PFX##_impl_float_up_min(SNAME *_heap_);                                     \
    static void PFX##_impl_float_down_max(SNAME *_heap_);                                   \
    static void PFX##_impl_float_down_min(SNAME *_heap_);                                   \
    static SNAME##_iter PFX##_impl_it_start(SNAME *_heap_);                                 \
    static SNAME##_iter PFX##_impl_it_end(SNAME *_heap_);                                   \
                                                                                            \
    FMOD SNAME *PFX##_new(size_t capacity, int (*compare)(V, V))                            \
    {                                                                                       \
        SNAME *_heap_ = malloc(sizeof(SNAME));                                              \
        if (!_heap_)                                                                        \
            return NULL;                                                                    \
                                                                                            \
        /* Since each node can store two elements, divide the actual capacity by 2 */       \
        /* Round the capacity of nodes up */                                                \
        capacity = capacity % 2 == 0 ? capacity / 2 : (capacity + 1) / 2;                   \
        _heap_->buffer = malloc(sizeof(SNAME##_node) * capacity);                           \
                                                                                            \
        if (!_heap_->buffer)                                                                \
        {                                                                                   \
            free(_heap_);                                                                   \
            return NULL;                                                                    \
        }                                                                                   \
        memset(_heap_->buffer, 0, sizeof(SNAME##_node) * capacity);                         \
        _heap_->capacity = capacity;                                                        \
        _heap_->size = 0;                                                                   \
        _heap_->count = 0;                                                                  \
        _heap_->cmp = compare;                                                              \
        _heap_->it_start = PFX##_impl_it_start;                                             \
        _heap_->it_end = PFX##_impl_it_end;                                                 \
        return _heap_;                                                                      \
    }                                                                                       \
                                                                                            \
    FMOD void PFX##_clear(SNAME *_heap_)                                                    \
    {                                                                                       \
        memset(_heap_->buffer, 0, sizeof(V) * _heap_->capacity);                            \
        _heap_->size = 0;                                                                   \
        _heap_->count = 0;                                                                  \
    }                                                                                       \
                                                                                            \
    FMOD void PFX##_free(SNAME *_heap_)                                                     \
    {                                                                                       \
        free(_heap_->buffer);                                                               \
        free(_heap_);                                                                       \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_insert(SNAME *_heap_, V element)                                        \
    {                                                                                       \
        if (PFX##_full(_heap_))                                                             \
        {                                                                                   \
            if (!PFX##_impl_grow(_heap_))                                                   \
                return false;                                                               \
        }                                                                                   \
                                                                                            \
        if (PFX##_count(_heap_) % 2 == 0)                                                   \
        {                                                                                   \
            /* Occupying a new node */                                                      \
            _heap_->buffer[_heap_->size].data[0] = element;                                 \
            _heap_->buffer[_heap_->size].data[1] = PFX##_impl_default_value();              \
                                                                                            \
            _heap_->size++;                                                                 \
        }                                                                                   \
        else                                                                                \
        {                                                                                   \
            SNAME##_node *curr_node = &(_heap_->buffer[_heap_->size - 1]);                  \
                                                                                            \
            if (_heap_->cmp(curr_node->data[0], element) > 0)                               \
            {                                                                               \
                curr_node->data[1] = curr_node->data[0];                                    \
                curr_node->data[0] = element;                                               \
            }                                                                               \
            else                                                                            \
            {                                                                               \
                curr_node->data[1] = element;                                               \
            }                                                                               \
        }                                                                                   \
                                                                                            \
        _heap_->count++;                                                                    \
                                                                                            \
        if (PFX##_count(_heap_) <= 2)                                                       \
            return true;                                                                    \
                                                                                            \
        SNAME##_node *parent = &(_heap_->buffer[(_heap_->size - 1) / 2]);                   \
                                                                                            \
        if (_heap_->cmp(parent->data[0], element) > 0)                                      \
            PFX##_impl_float_up_min(_heap_);                                                \
        else if (_heap_->cmp(parent->data[1], element) < 0)                                 \
            PFX##_impl_float_up_max(_heap_);                                                \
                                                                                            \
        return true;                                                                        \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_remove_max(SNAME *_heap_, V *result)                                    \
    {                                                                                       \
        if (PFX##_empty(_heap_))                                                            \
            return false;                                                                   \
                                                                                            \
        if (PFX##_count(_heap_) == 1)                                                       \
        {                                                                                   \
            *result = _heap_->buffer[0].data[0];                                            \
            _heap_->buffer[0].data[0] = PFX##_impl_default_value();                         \
            _heap_->count--;                                                                \
            return true;                                                                    \
        }                                                                                   \
        else                                                                                \
            *result = _heap_->buffer[0].data[1];                                            \
                                                                                            \
        SNAME##_node *last_node = &(_heap_->buffer[_heap_->size - 1]);                      \
                                                                                            \
        if (PFX##_count(_heap_) % 2 == 1)                                                   \
        {                                                                                   \
            _heap_->buffer[0].data[1] = last_node->data[0];                                 \
            last_node->data[0] = PFX##_impl_default_value();                                \
            _heap_->size--;                                                                 \
        }                                                                                   \
        else                                                                                \
        {                                                                                   \
            _heap_->buffer[0].data[1] = last_node->data[1];                                 \
                                                                                            \
            last_node->data[1] = PFX##_impl_default_value();                                \
        }                                                                                   \
                                                                                            \
        _heap_->count--;                                                                    \
                                                                                            \
        PFX##_impl_float_down_max(_heap_);                                                  \
                                                                                            \
        return true;                                                                        \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_remove_min(SNAME *_heap_, V *result)                                    \
    {                                                                                       \
        if (PFX##_empty(_heap_))                                                            \
            return false;                                                                   \
                                                                                            \
        *result = _heap_->buffer[0].data[0];                                                \
                                                                                            \
        if (PFX##_count(_heap_) == 1)                                                       \
        {                                                                                   \
            _heap_->buffer[0].data[0] = PFX##_impl_default_value();                         \
                                                                                            \
            _heap_->count--;                                                                \
                                                                                            \
            return true;                                                                    \
        }                                                                                   \
                                                                                            \
        SNAME##_node *last_node = &(_heap_->buffer[_heap_->size - 1]);                      \
                                                                                            \
        _heap_->buffer[0].data[0] = last_node->data[0];                                     \
                                                                                            \
        if (PFX##_count(_heap_) % 2 == 1)                                                   \
        {                                                                                   \
            last_node->data[0] = PFX##_impl_default_value();                                \
                                                                                            \
            _heap_->size--;                                                                 \
        }                                                                                   \
        else                                                                                \
        {                                                                                   \
            last_node->data[0] = last_node->data[1];                                        \
            last_node->data[1] = PFX##_impl_default_value();                                \
        }                                                                                   \
                                                                                            \
        _heap_->count--;                                                                    \
                                                                                            \
        PFX##_impl_float_down_min(_heap_);                                                  \
                                                                                            \
        return true;                                                                        \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_insert_if(SNAME *_heap_, V element, bool condition)                     \
    {                                                                                       \
        if (condition)                                                                      \
            return PFX##_insert(_heap_, element);                                           \
                                                                                            \
        return false;                                                                       \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_remove_max_if(SNAME *_heap_, V *result, bool condition)                 \
    {                                                                                       \
        if (condition)                                                                      \
            return PFX##_remove_max(_heap_, result);                                        \
                                                                                            \
        return false;                                                                       \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_remove_min_if(SNAME *_heap_, V *result, bool condition)                 \
    {                                                                                       \
        if (condition)                                                                      \
            return PFX##_remove_min(_heap_, result);                                        \
                                                                                            \
        return false;                                                                       \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_update_max(SNAME *_heap_, V element)                                    \
    {                                                                                       \
        if (PFX##_empty(_heap_))                                                            \
            return false;                                                                   \
                                                                                            \
        if (PFX##_count(_heap_) == 1)                                                       \
        {                                                                                   \
            _heap_->buffer[0].data[0] = element;                                            \
        }                                                                                   \
        else if (_heap_->cmp(element, _heap_->buffer[0].data[0]) < 0)                       \
        {                                                                                   \
            _heap_->buffer[0].data[1] = _heap_->buffer[0].data[0];                          \
            _heap_->buffer[0].data[0] = element;                                            \
                                                                                            \
            PFX##_impl_float_down_max(_heap_);                                              \
        }                                                                                   \
        else                                                                                \
        {                                                                                   \
            _heap_->buffer[0].data[1] = element;                                            \
                                                                                            \
            PFX##_impl_float_down_max(_heap_);                                              \
        }                                                                                   \
                                                                                            \
        return true;                                                                        \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_update_min(SNAME *_heap_, V element)                                    \
    {                                                                                       \
        if (PFX##_empty(_heap_))                                                            \
            return false;                                                                   \
                                                                                            \
        if (PFX##_count(_heap_) == 1)                                                       \
        {                                                                                   \
            _heap_->buffer[0].data[0] = element;                                            \
        }                                                                                   \
        else if (_heap_->cmp(element, _heap_->buffer[0].data[1]) > 0)                       \
        {                                                                                   \
            _heap_->buffer[0].data[0] = _heap_->buffer[0].data[1];                          \
            _heap_->buffer[0].data[1] = element;                                            \
                                                                                            \
            PFX##_impl_float_down_min(_heap_);                                              \
        }                                                                                   \
        else                                                                                \
        {                                                                                   \
            _heap_->buffer[0].data[0] = element;                                            \
                                                                                            \
            PFX##_impl_float_down_min(_heap_);                                              \
        }                                                                                   \
                                                                                            \
        return true;                                                                        \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_max(SNAME *_heap_, V *value)                                            \
    {                                                                                       \
        if (PFX##_empty(_heap_))                                                            \
            return false;                                                                   \
                                                                                            \
        if (PFX##_count(_heap_) == 1)                                                       \
            *value = _heap_->buffer[0].data[0];                                             \
        else                                                                                \
            *value = _heap_->buffer[0].data[1];                                             \
                                                                                            \
        return true;                                                                        \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_min(SNAME *_heap_, V *value)                                            \
    {                                                                                       \
        if (PFX##_empty(_heap_))                                                            \
            return false;                                                                   \
                                                                                            \
        *value = _heap_->buffer[0].data[0];                                                 \
                                                                                            \
        return true;                                                                        \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_contains(SNAME *_heap_, V element)                                      \
    {                                                                                       \
        for (size_t i = 0; i < _heap_->count; i++)                                          \
        {                                                                                   \
            if (_heap_->cmp(_heap_->buffer[i / 2].data[i % 2], element) == 0)               \
                return true;                                                                \
        }                                                                                   \
                                                                                            \
        return false;                                                                       \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_empty(SNAME *_heap_)                                                    \
    {                                                                                       \
        return _heap_->count == 0;                                                          \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_full(SNAME *_heap_)                                                     \
    {                                                                                       \
        /* The heap is full if all nodes are completely filled */                           \
        return _heap_->size >= _heap_->capacity && _heap_->count % 2 == 0;                  \
    }                                                                                       \
                                                                                            \
    FMOD size_t PFX##_count(SNAME *_heap_)                                                  \
    {                                                                                       \
        return _heap_->count;                                                               \
    }                                                                                       \
                                                                                            \
    FMOD size_t PFX##_capacity(SNAME *_heap_)                                               \
    {                                                                                       \
        /* Multiply by 2 since each node can store two elements */                          \
        return _heap_->capacity * 2;                                                        \
    }                                                                                       \
                                                                                            \
    FMOD SNAME##_iter *PFX##_iter_new(SNAME *target)                                        \
    {                                                                                       \
        SNAME##_iter *iter = malloc(sizeof(SNAME##_iter));                                  \
                                                                                            \
        if (!iter)                                                                          \
            return NULL;                                                                    \
                                                                                            \
        PFX##_iter_init(iter, target);                                                      \
                                                                                            \
        return iter;                                                                        \
    }                                                                                       \
                                                                                            \
    FMOD void PFX##_iter_free(SNAME##_iter *iter)                                           \
    {                                                                                       \
        free(iter);                                                                         \
    }                                                                                       \
                                                                                            \
    FMOD void PFX##_iter_init(SNAME##_iter *iter, SNAME *target)                            \
    {                                                                                       \
        iter->target = target;                                                              \
        iter->cursor = 0;                                                                   \
        iter->start = true;                                                                 \
        iter->end = PFX##_empty(target);                                                    \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_iter_start(SNAME##_iter *iter)                                          \
    {                                                                                       \
        return PFX##_empty(iter->target) || iter->start;                                    \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_iter_end(SNAME##_iter *iter)                                            \
    {                                                                                       \
        return PFX##_empty(iter->target) || iter->end;                                      \
    }                                                                                       \
                                                                                            \
    FMOD void PFX##_iter_to_start(SNAME##_iter *iter)                                       \
    {                                                                                       \
        iter->cursor = 0;                                                                   \
        iter->start = true;                                                                 \
        iter->end = PFX##_empty(iter->target);                                              \
    }                                                                                       \
                                                                                            \
    FMOD void PFX##_iter_to_end(SNAME##_iter *iter)                                         \
    {                                                                                       \
        iter->cursor = iter->target->count - 1;                                             \
        iter->start = PFX##_empty(iter->target);                                            \
        iter->end = true;                                                                   \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_iter_next(SNAME##_iter *iter)                                           \
    {                                                                                       \
        if (iter->end)                                                                      \
            return false;                                                                   \
                                                                                            \
        iter->start = false;                                                                \
                                                                                            \
        if (iter->cursor == iter->target->count - 1)                                        \
            iter->end = true;                                                               \
        else                                                                                \
            iter->cursor++;                                                                 \
                                                                                            \
        return true;                                                                        \
    }                                                                                       \
                                                                                            \
    FMOD bool PFX##_iter_prev(SNAME##_iter *iter)                                           \
    {                                                                                       \
        if (iter->start)                                                                    \
            return false;                                                                   \
                                                                                            \
        iter->end = false;                                                                  \
                                                                                            \
        if (iter->cursor == 0)                                                              \
            iter->start = true;                                                             \
        else                                                                                \
            iter->cursor--;                                                                 \
                                                                                            \
        return true;                                                                        \
    }                                                                                       \
                                                                                            \
    FMOD V PFX##_iter_value(SNAME##_iter *iter)                                             \
    {                                                                                       \
        if (PFX##_empty(iter->target))                                                      \
            return PFX##_impl_default_value();                                              \
                                                                                            \
        return iter->target->buffer[iter->cursor / 2].data[iter->cursor % 2];               \
    }                                                                                       \
                                                                                            \
    FMOD size_t PFX##_iter_index(SNAME##_iter *iter)                                        \
    {                                                                                       \
        return iter->cursor;                                                                \
    }                                                                                       \
                                                                                            \
    static bool PFX##_impl_grow(SNAME *_heap_)                                              \
    {                                                                                       \
        size_t new_cap = _heap_->capacity * 2;                                              \
                                                                                            \
        SNAME##_node *new_buffer = realloc(_heap_->buffer, sizeof(SNAME##_node) * new_cap); \
                                                                                            \
        if (!new_buffer)                                                                    \
            return false;                                                                   \
                                                                                            \
        memset(new_buffer + _heap_->capacity, 0, sizeof(SNAME##_node) * _heap_->capacity);  \
                                                                                            \
        _heap_->buffer = new_buffer;                                                        \
        _heap_->capacity = new_cap;                                                         \
                                                                                            \
        return true;                                                                        \
    }                                                                                       \
                                                                                            \
    static void PFX##_impl_float_up_max(SNAME *_heap_)                                      \
    {                                                                                       \
        size_t index = _heap_->size - 1;                                                    \
                                                                                            \
        SNAME##_node *curr_node = &(_heap_->buffer[index]);                                 \
                                                                                            \
        while (index > 0)                                                                   \
        {                                                                                   \
            /* Parent index */                                                              \
            size_t P_index = (index - 1) / 2;                                               \
                                                                                            \
            SNAME##_node *parent = &(_heap_->buffer[P_index]);                              \
                                                                                            \
            if (index == _heap_->size - 1 && PFX##_count(_heap_) % 2 != 0)                  \
            {                                                                               \
                if (_heap_->cmp(curr_node->data[0], parent->data[1]) < 0)                   \
                    break;                                                                  \
                                                                                            \
                V tmp = curr_node->data[0];                                                 \
                curr_node->data[0] = parent->data[1];                                       \
                parent->data[1] = tmp;                                                      \
            }                                                                               \
            else                                                                            \
            {                                                                               \
                if (_heap_->cmp(curr_node->data[1], parent->data[1]) < 0)                   \
                    break;                                                                  \
                                                                                            \
                V tmp = curr_node->data[1];                                                 \
                curr_node->data[1] = parent->data[1];                                       \
                parent->data[1] = tmp;                                                      \
            }                                                                               \
                                                                                            \
            index = P_index;                                                                \
            curr_node = parent;                                                             \
        }                                                                                   \
    }                                                                                       \
                                                                                            \
    static void PFX##_impl_float_up_min(SNAME *_heap_)                                      \
    {                                                                                       \
        size_t index = _heap_->size - 1;                                                    \
        SNAME##_node *curr_node = &(_heap_->buffer[index]);                                 \
                                                                                            \
        while (index > 0)                                                                   \
        {                                                                                   \
            size_t P_index = (index - 1) / 2;                                               \
            SNAME##_node *parent = &(_heap_->buffer[P_index]);                              \
                                                                                            \
            if (_heap_->cmp(curr_node->data[0], parent->data[0]) >= 0)                      \
                break;                                                                      \
                                                                                            \
            V tmp = curr_node->data[0];                                                     \
            curr_node->data[0] = parent->data[0];                                           \
            parent->data[0] = tmp;                                                          \
            index = P_index;                                                                \
            curr_node = parent;                                                             \
        }                                                                                   \
    }                                                                                       \
                                                                                            \
    static void PFX##_impl_float_down_max(SNAME *_heap_)                                    \
    {                                                                                       \
        size_t index = 0;                                                                   \
        SNAME##_node *curr_node = &(_heap_->buffer[index]);                                 \
                                                                                            \
        while (true)                                                                        \
        {                                                                                   \
            if (2 * index + 1 >= _heap_->size)                                              \
                break;                                                                      \
                                                                                            \
            size_t child;                                                                   \
            size_t L_index = index * 2 + 1;                                                 \
            size_t R_index = index * 2 + 2;                                                 \
                                                                                            \
            if (R_index < _heap_->size)                                                     \
            {                                                                               \
                SNAME##_node *L = &(_heap_->buffer[L_index]);                               \
                SNAME##_node *R = &(_heap_->buffer[R_index]);                               \
                                                                                            \
                if (R_index == _heap_->size - 1 && PFX##_count(_heap_) % 2 != 0)            \
                    child = _heap_->cmp(L->data[1], R->data[0]) > 0 ? L_index : R_index;    \
                else                                                                        \
                    child = _heap_->cmp(L->data[1], R->data[1]) > 0 ? L_index : R_index;    \
            }                                                                               \
            else                                                                            \
                child = L_index;                                                            \
                                                                                            \
            SNAME##_node *child_node = &(_heap_->buffer[child]);                            \
                                                                                            \
            if (child == _heap_->size - 1 && PFX##_count(_heap_) % 2 != 0)                  \
            {                                                                               \
                if (_heap_->cmp(curr_node->data[1], child_node->data[0]) >= 0)              \
                    break;                                                                  \
                                                                                            \
                V tmp = child_node->data[0];                                                \
                child_node->data[0] = curr_node->data[1];                                   \
                curr_node->data[1] = tmp;                                                   \
            }                                                                               \
            else                                                                            \
            {                                                                               \
                if (_heap_->cmp(curr_node->data[1], child_node->data[1]) >= 0)              \
                    break;                                                                  \
                                                                                            \
                V tmp = child_node->data[1];                                                \
                child_node->data[1] = curr_node->data[1];                                   \
                curr_node->data[1] = tmp;                                                   \
                                                                                            \
                if (_heap_->cmp(child_node->data[0], child_node->data[1]) > 0)              \
                {                                                                           \
                    tmp = child_node->data[0];                                              \
                    child_node->data[0] = child_node->data[1];                              \
                    child_node->data[1] = tmp;                                              \
                }                                                                           \
            }                                                                               \
            index = child;                                                                  \
            curr_node = child_node;                                                         \
        }                                                                                   \
    }                                                                                       \
                                                                                            \
    static void PFX##_impl_float_down_min(SNAME *_heap_)                                    \
    {                                                                                       \
        size_t index = 0;                                                                   \
                                                                                            \
        SNAME##_node *curr_node = &(_heap_->buffer[index]);                                 \
                                                                                            \
        while (true)                                                                        \
        {                                                                                   \
            if (2 * index + 1 >= _heap_->size)                                              \
                break;                                                                      \
                                                                                            \
            size_t child;                                                                   \
            size_t L_index = index * 2 + 1;                                                 \
            size_t R_index = index * 2 + 2;                                                 \
                                                                                            \
            if (R_index < _heap_->size)                                                     \
            {                                                                               \
                SNAME##_node *L = &(_heap_->buffer[L_index]);                               \
                SNAME##_node *R = &(_heap_->buffer[R_index]);                               \
                child = _heap_->cmp(L->data[0], R->data[0]) < 0 ? L_index : R_index;        \
            }                                                                               \
            else                                                                            \
                child = L_index;                                                            \
                                                                                            \
            SNAME##_node *child_node = &(_heap_->buffer[child]);                            \
                                                                                            \
            if (_heap_->cmp(curr_node->data[0], child_node->data[0]) < 0)                   \
                break;                                                                      \
                                                                                            \
            V tmp = child_node->data[0];                                                    \
            child_node->data[0] = curr_node->data[0];                                       \
            curr_node->data[0] = tmp;                                                       \
                                                                                            \
            if (child != _heap_->size - 1 || PFX##_count(_heap_) % 2 == 0)                  \
            {                                                                               \
                if (_heap_->cmp(child_node->data[0], child_node->data[1]) > 0)              \
                {                                                                           \
                    tmp = child_node->data[0];                                              \
                    child_node->data[0] = child_node->data[1];                              \
                    child_node->data[1] = tmp;                                              \
                }                                                                           \
            }                                                                               \
            index = child;                                                                  \
            curr_node = child_node;                                                         \
        }                                                                                   \
    }                                                                                       \
                                                                                            \
    static SNAME##_iter PFX##_impl_it_start(SNAME *_heap_)                                  \
    {                                                                                       \
        SNAME##_iter iter;                                                                  \
        PFX##_iter_init(&iter, _heap_);                                                     \
        PFX##_iter_to_start(&iter);                                                         \
        return iter;                                                                        \
    }                                                                                       \
                                                                                            \
    static SNAME##_iter PFX##_impl_it_end(SNAME *_heap_)                                    \
    {                                                                                       \
        SNAME##_iter iter;                                                                  \
        PFX##_iter_init(&iter, _heap_);                                                     \
        PFX##_iter_to_end(&iter);                                                           \
        return iter;                                                                        \
    }

#endif /* CMC_INTERVALHEAP_H */

test.c

#include "intervalheap.h"
#include <stdio.h>

/* Generate the Interval Heap */
INTERVALHEAP_GENERATE(h, heap, , int)

/* Comparison function */
int intcmp(int a, int b)
{
    return (a > b) - (a < b);
}

#define TOTAL 100

int main(void)
{
    heap *my_heap = h_new(50, intcmp);

    for (size_t i = 1; i <= TOTAL; i++)
    {
        h_insert(my_heap, i);
    }

    size_t half = h_count(my_heap) / 2;

    for (size_t i = 0; !h_empty(my_heap); i++)
    {
        int r;

        i < half ? h_remove_max(my_heap, &r) : h_remove_min(my_heap, &r);

        printf("%d ", r);
    }

    h_free(my_heap);

    return 0;
}
\$\endgroup\$
  • \$\begingroup\$ I would say that intcmp isn't very straightforward, and it would be more obvious with ifs and branches. Let the compiler optimize the code \$\endgroup\$ – Cacahuete Frito Jul 6 at 12:57
  • \$\begingroup\$ And don't use ?: unless it's for a very obvious thing. Function calls aren't very obvious things. A good place for ?: is GCC's compound expression macros \$\endgroup\$ – Cacahuete Frito Jul 6 at 13:02

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.