/* Copyright (C) 2002 Timo Sirainen */

/* Implementation of draft-ietf-imapext-sort-10 sorting algorithm */

#include "lib.h"
#include "buffer.h"
#include "ostream.h"
#include "imap-base-subject.h"
#include "mail-sort.h"

#include <stdlib.h>

struct mail_sort_context {
	enum mail_sort_type output[MAX_SORT_PROGRAM_SIZE];
	enum mail_sort_type common_mask;

	const struct mail_sort_callbacks *callbacks;
	void *func_context;

	buffer_t *sort_buffer;
	pool_t temp_pool;

	time_t last_arrival, last_date;
	uoff_t last_size;
	char *last_cc, *last_from, *last_subject, *last_to;
};

static void mail_sort_flush(struct mail_sort_context *ctx);

static enum mail_sort_type
mail_sort_normalize(const enum mail_sort_type *input, buffer_t *output)
{
        enum mail_sort_type type, mask = 0;
	int pos, reverse;

	reverse = FALSE;
	for (pos = 0; *input != MAIL_SORT_END; input++) {
		if (*input == MAIL_SORT_REVERSE)
			reverse = !reverse;
		else {
			if ((mask & *input) == 0) {
				if (reverse) {
					type = MAIL_SORT_REVERSE;
					buffer_append(output,
						      &type, sizeof(type));
				}

				buffer_append(output, input, sizeof(*input));
				mask |= *input;
			}

			reverse = FALSE;
		}
	}

	type = MAIL_SORT_END;
	buffer_append(output, &type, sizeof(type));

	return mask;
}

static enum mail_sort_type
mail_sort_get_common_mask(const enum mail_sort_type *input,
			  enum mail_sort_type **output)
{
	enum mail_sort_type mask = 0;

	while (*input == **output && *input != MAIL_SORT_END) {
		if (*input != MAIL_SORT_REVERSE)
			mask |= *input;
		input++; (*output)++;
	}

	return mask;
}

struct mail_sort_context *
mail_sort_init(const enum mail_sort_type *input, enum mail_sort_type *output,
	       const struct mail_sort_callbacks *callbacks, void *context)
{
	struct mail_sort_context *ctx;
	enum mail_sort_type norm_input[MAX_SORT_PROGRAM_SIZE];
	enum mail_sort_type norm_output[MAX_SORT_PROGRAM_SIZE];
	buffer_t *buf;
	int i;

	ctx = i_new(struct mail_sort_context, 1);

	t_push();
	buf = buffer_create_data(data_stack_pool,
				 norm_input, sizeof(norm_input));
	mail_sort_normalize(input, buf);

	buf = buffer_create_data(data_stack_pool,
				 norm_output, sizeof(norm_output));
	mail_sort_normalize(output, buf);
	t_pop();

	/* remove the common part from output, we already know input is sorted
	   that much so we don't have to worry about it. */
	output = norm_output;
        ctx->common_mask = mail_sort_get_common_mask(norm_input, &output);

	for (i = 0; output[i] != MAIL_SORT_END; i++)
		ctx->output[i] = output[i];
	ctx->output[i] = MAIL_SORT_END;

	ctx->sort_buffer = buffer_create_dynamic(system_pool,
						 128 * sizeof(unsigned int),
						 (size_t)-1);

	ctx->temp_pool = pool_alloconly_create("Sort", 8192);
	ctx->callbacks = callbacks;
	ctx->func_context = context;
	return ctx;
}

void mail_sort_deinit(struct mail_sort_context *ctx)
{
	mail_sort_flush(ctx);
	buffer_free(ctx->sort_buffer);
	pool_unref(ctx->temp_pool);

	i_free(ctx->last_cc);
	i_free(ctx->last_from);
	i_free(ctx->last_subject);
	i_free(ctx->last_to);

	i_free(ctx);
}

static int addr_strcmp(const char *s1, const char *s2)
{
	if (s1 == NULL)
		return s2 == NULL ? 0 : -1;
	if (s2 == NULL)
		return 1;

	/* FIXME: maybe create ascii_strcasecmp()? strcasecmp() may compare
	   non-ASCII too if locale is set. We don't do that now though. */
	return strcasecmp(s1, s2);
}

static int subject_cmp(pool_t pool, const char *s1, const char *s2)
{
	int ret;

	if (s1 == NULL)
		return s2 == NULL ? 0 : -1;
	if (s2 == NULL)
		return 1;

	p_clear(pool);
	ret = strcmp(imap_get_base_subject_cased(pool, s1, NULL),
		     imap_get_base_subject_cased(pool, s2, NULL));
	return ret;
}

static void mail_sort_check_flush(struct mail_sort_context *ctx,
				  unsigned int id)
{
	const char *str;
	time_t t;
	uoff_t size;
	int changed = FALSE;

	if (ctx->common_mask & MAIL_SORT_ARRIVAL) {
		t = ctx->callbacks->input_time(MAIL_SORT_ARRIVAL, id,
					       ctx->func_context);
		if (t != ctx->last_arrival) {
			ctx->last_arrival = t;
			changed = TRUE;
		}
	}

	if (ctx->common_mask & MAIL_SORT_CC) {
		str = ctx->callbacks->input_str(MAIL_SORT_CC, id,
						ctx->func_context);
		if (addr_strcmp(str, ctx->last_cc) != 0) {
			i_free(ctx->last_cc);
			ctx->last_cc = i_strdup(str);
			changed = TRUE;
		}
	}

	if (ctx->common_mask & MAIL_SORT_DATE) {
		t = ctx->callbacks->input_time(MAIL_SORT_DATE, id,
					       ctx->func_context);
		if (t != ctx->last_date) {
			ctx->last_date = t;
			changed = TRUE;
		}
	}

	if (ctx->common_mask & MAIL_SORT_FROM) {
		str = ctx->callbacks->input_str(MAIL_SORT_FROM, id,
						ctx->func_context);
		if (addr_strcmp(str, ctx->last_from) != 0) {
			i_free(ctx->last_from);
			ctx->last_from = i_strdup(str);
			changed = TRUE;
		}
	}

	if (ctx->common_mask & MAIL_SORT_SIZE) {
		size = ctx->callbacks->input_time(MAIL_SORT_SIZE, id,
						  ctx->func_context);
		if (size != ctx->last_size) {
			ctx->last_size = size;
			changed = TRUE;
		}
	}

	if (ctx->common_mask & MAIL_SORT_SUBJECT) {
		str = ctx->callbacks->input_str(MAIL_SORT_SUBJECT, id,
						ctx->func_context);
		if (subject_cmp(ctx->temp_pool, str, ctx->last_subject) != 0) {
			i_free(ctx->last_subject);
			ctx->last_subject = i_strdup(str);
			changed = TRUE;
		}
	}

	if (ctx->common_mask & MAIL_SORT_TO) {
		str = ctx->callbacks->input_str(MAIL_SORT_TO, id,
						ctx->func_context);
		if (addr_strcmp(str, ctx->last_to) != 0) {
			i_free(ctx->last_to);
			ctx->last_to = i_strdup(str);
			changed = TRUE;
		}
	}

	if (changed)
		mail_sort_flush(ctx);
}

void mail_sort_input(struct mail_sort_context *ctx, unsigned int id)
{
	if (ctx->common_mask != 0)
		mail_sort_check_flush(ctx, id);

	buffer_append(ctx->sort_buffer, &id, sizeof(id));
}

static struct mail_sort_context *mail_sort_qsort_context;

static int mail_sort_qsort_func(const void *p1, const void *p2)
{
	const unsigned int *i1 = p1;
	const unsigned int *i2 = p2;
	enum mail_sort_type *output;
        const struct mail_sort_callbacks *cb;
	void *ctx;
	int ret, reverse = FALSE;

	output = mail_sort_qsort_context->output;
	cb = mail_sort_qsort_context->callbacks;
	ctx = mail_sort_qsort_context->func_context;

	t_push();

	ret = 0;
	for (; *output != MAIL_SORT_END && ret == 0; output++) {
		if (*output == MAIL_SORT_REVERSE) {
			reverse = !reverse;
			continue;
		}

		switch (*output) {
		case MAIL_SORT_ARRIVAL:
		case MAIL_SORT_DATE: {
			time_t r1, r2;

			r1 = cb->input_time(*output, *i1, ctx);
			r2 = cb->input_time(*output, *i2, ctx);
			ret = r1 < r2 ? -1 : r1 > r2 ? 1 : 0;
			break;
		}
		case MAIL_SORT_SIZE: {
			uoff_t r1, r2;

			r1 = cb->input_uofft(*output, *i1, ctx);
			r2 = cb->input_uofft(*output, *i2, ctx);
			ret = r1 < r2 ? -1 : r1 > r2 ? 1 : 0;
			break;
		}
		case MAIL_SORT_CC:
		case MAIL_SORT_FROM:
		case MAIL_SORT_TO: {
			const char *a1, *a2;

			a1 = cb->input_mailbox(*output, *i1, ctx);
			a2 = cb->input_mailbox(*output, *i2, ctx);
			ret = addr_strcmp(a1, a2);
			break;
		}
		case MAIL_SORT_SUBJECT:
			ret = subject_cmp(mail_sort_qsort_context->temp_pool,
					  cb->input_str(*output, *i1, ctx),
					  cb->input_str(*output, *i2, ctx));
			break;
		default:
			i_unreached();
		}

		if (reverse) {
			if (ret > 0)
				ret = -1;
			else if (ret < 0)
				ret = 1;
		}

		reverse = FALSE;
	}

	cb->input_reset(ctx);

	t_pop();

	return ret != 0 ? ret : (*i1 < *i2 ? -1 : 1);
}

static void mail_sort_flush(struct mail_sort_context *ctx)
{
	unsigned int *arr;
	size_t count;

	mail_sort_qsort_context = ctx;

	arr = buffer_get_modifyable_data(ctx->sort_buffer, NULL);
	count = buffer_get_used_size(ctx->sort_buffer) / sizeof(unsigned int);
	qsort(arr, count, sizeof(unsigned int), mail_sort_qsort_func);

	ctx->callbacks->output(arr, count, ctx->func_context);
	buffer_set_used_size(ctx->sort_buffer, 0);
}