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

#include "dlist.h"

size_t max(size_t a, size_t b)
{
    if (a >= b)
    {
        return a;
    }
    return b;
}

size_t min(size_t a, size_t b)
{
    if (a <= b)
    {
        return a;
    }
    return b;
}

size_t min_3(size_t a, size_t b, size_t c)
{
    if (a <= b)
    {
        if (a <= c)
        {
            return a;
        }
        return c;
    }
    else
    {
        if (b <= c)
        {
            return b;
        }
        return c;
    }
}

size_t my_strlen(const int *s)
{
    size_t i;
    for (i = 0; s[i] != -1; i++)
    {
        continue;
    }
    return i;
}

size_t levenshtein(const int *s1, const int *s2)
{
    size_t l1 = my_strlen(s1);
    size_t l2 = my_strlen(s2);
    if (min(l1, l2) == 0)
    {
        return max(l1, l2);
    }

    if (s1[0] == s2[0])
    {
        return levenshtein(s1 + 1, s2 + 1);
    }

    size_t lev1 = levenshtein(s1 + 1, s2);
    size_t lev2 = levenshtein(s1, s2 + 1);
    size_t lev3 = levenshtein(s1 + 1, s2 + 1);

    return 1 + min_3(lev1, lev2, lev3);
}

int *to_str(const struct dlist *l)
{
    int *res = malloc((l->size + 1) * sizeof(int));
    res[l->size] = -1;
    size_t j = 0;
    for (struct dlist_item *i = l->head; i; i = i->next, j++)
    {
        res[j] = i->data;
    }
    return res;
}

unsigned int dlist_levenshtein(const struct dlist *list1,
                               const struct dlist *list2)
{
    int *l1 = to_str(list1);
    int *l2 = to_str(list2);

    unsigned int res = levenshtein(l1, l2);
    free(l1);
    free(l2);
    return res;
}