/* SPDX-License-Identifier: LGPL-2.1-only */

/* Copyright (C) 2020 Gediminas Jakutis */

#include <errno.h>
#include <stdlib.h>
#include "defs.h"
#include "stream.h"
#include "mergesort.h"

static int merge(struct stream * const dest, struct stream * const A, struct stream * const B);

/* bottom-up variantas */

int merge_sort(struct stream * const src, struct stream * const dest)
{
	int ret = 0;
	struct stream tmp[4] = {0}; /* I can't into stream reuse, hence four. A yeet, followed by a dab. */
	size_t i;

	try(!src || !dest, err, EINVAL, "cannot sort what's not there");

	try_s((ret = stream_shallow_copy(src, dest)), err);

	if (src->n > 1) {
		src->split(src, tmp, tmp + 2); /* split stream in half */
		merge_sort(tmp, tmp + 1); /* recurse-sort first half */
		merge_sort(tmp + 2, tmp + 3); /* recurse-sort second half */
		merge(dest, tmp + 1, tmp + 3); /* merge the two halves back */
		dest->rewind(dest);

		for (i = 0; i < (sizeof(tmp) / sizeof(*tmp)); ++i) {
			stream_close(tmp + i);
		}
	} else { /* stream of size one is inherently sorted, simply src with dest */
		*tmp = *dest;
		*dest = *src;
		*src = *tmp;
	}

err:
	return ret;
}

static int merge(struct stream * const dest, struct stream * const A, struct stream * const B)
{
	int ret = 0;
	struct entry_l *a;
	struct entry_l *b;

	a = get(A);
	b = get(B);

	while (a || b) {
		if (a && (!b || a->val <= b->val)) {
			put(dest, a);
			a = get(A);
		} else {
			put(dest, b);
			b = get(B);
		}
	}

	return ret;
}