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

/* Copyright (C) 2020 Gediminas Jakutis */

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

/* bottom-up variantas */

int merge_sort(struct stream * const src, struct stream * const dest)
{
	int ret = 0;
	struct stream tmp[4]; /* 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");

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

	for (i = 0; i < (sizeof(tmp) / sizeof(*tmp)); ++i) {
		stream_close(tmp + i);
	}

err:
	return ret;
}

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;

	try(A->parentid != B->parentid, err, EINVAL, "cannot merge blocks: uncommon parent!");

	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);
		}
	}

err:
	return ret;
}