I have implemented a Moving Median Filter and I would like a review.

I am using a linked list to keep track of the oldest value in the kernel and an array of nodes sorted which is sorted.

The sorted pointed is stored along the MedfiltNode because it saves one array. It is a bit ugly though.

Regarding the sorting algorithm. It is a half-bubble-sort implementation where the value is either bubbled toward the top of the bottom of the sorted list. Average complexity is N/2. Depending on the kernel size it might worth using a binary-insertion-sort algorithm instead, but I would like to avoid to use any recursive algorithm.

Header

/**
* Moving Median Filter.
*
* This algorithm is iterative. Each call will compute the next point.
* In the example below, the kernel has a size of 3. Notice that the
* values in the kernel are alway sorted. The left value is therefore
* the minimum in the kernel, the center value is the median and the
* right value is the maximum value.
*
* Input data:         0 1 2 5 4 8 3
* Kernel:      |0 0 0|            .   (min=0, med=0, max=0)
*                |0 0 0|          .   (min=0, med=0, max=0)
*                  |0 0 1|        .   (min=0, med=0, max=1)
*                    |0 1 2|      .   (min=0, med=1, max=2)
*                      |1 2 5|    .   (min=1, med=2, max=5)
*                        |2 4 5|  .   (min=2, med=4, max=5)
*                          |4 5 8|.   (min=4, med=5, max=8)
*                            |3 4 8|  (min=3, med=4, max=8)
*/
#pragma once
#include <stdlib.h>

typedef struct MedfiltNode {
    float value;
    size_t index; // Node index in the sorted table
    struct MedfiltNode* parent;
    struct MedfiltNode* sorted;
} MedfiltNode;

typedef struct MedfiltData {
    MedfiltNode *kernel; // Working filter memory
    MedfiltNode *oldest; // Reference to the oldest value in the kernel
    size_t length; // Number of nodes
} MedfiltData;

void median_init(MedfiltData *data, MedfiltNode *nodes, size_t length);
void median(float input, MedfiltData *data, float *median, float *min, float *max);

Source Code

/**
 * Moving Median Filter.
 * @author CHEVALLIER Yves <[email protected]>
 */
#include <stdint.h>
#include <stdlib.h>
#include "medfilt.h"

static void swap(MedfiltNode **a, MedfiltNode **b)
{
    // Swap two node references in the sorted table.
    MedfiltNode *temp = *a;
    *a = *b;
    *b = temp;

    // Preserve index. Used to retrive the node position in the sorted table.
    size_t index = (*a)->index;
    (*a)->index = (*b)->index;
    (*b)->index = index;
}

void median(float input, MedfiltData *data, float *median, float *min, float *max)
{
    // New value replaces the oldest
    MedfiltNode *n = data->kernel;
    MedfiltNode *node = data->oldest;
    node->value = input;
    data->oldest = node->parent;

    // Sort the kernel
    #define VAL(x) (n[x].sorted->value)
    for (size_t i = node->index; i < data->length - 1 && VAL(i) > VAL(i + 1); i++) {
        swap(&n[i].sorted, &n[i + 1].sorted);
    }

    for (size_t i = node->index; i > 0 && VAL(i) < VAL(i - 1); i++) {
        swap(&n[i].sorted, &n[i - 1].sorted);
    }

    // Get kernel information from sorted entries
    *min = n[0].sorted->value;
    *max = n[data->length - 1].sorted->value;
    *median = n[data->length / 2].sorted->value;
}

void median_init(MedfiltData *data, MedfiltNode *nodes, size_t length)
{
    data->kernel = nodes;
    data->length = length;

    // Linked list initialization
    data->oldest = &data->kernel[length - 1];
    for (size_t i = 0; i < length; data->oldest = &data->kernel[i], i++) {
        data->kernel[i] = (MedfiltNode) {
            .value = 0,
            .parent = data->oldest,
            .index = i,
            .sorted = &data->kernel[i]
        };
    }
}