/* NUMstring.cpp
*
* Copyright (C) 2012 David Weenink
*
* This program is free software; you can redistribute it and/or modify
* it under the terms of the GNU General Public License as published by
* the Free Software Foundation; either version 2 of the License, or (at
* your option) any later version.
*
* This program is distributed in the hope that it will be useful, but
* WITHOUT ANY WARRANTY; without even the implied warranty of
* MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
* General Public License for more details.
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software
* Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.
*/

/*
 djmw 20121005 First version
*/

#include <ctype.h>
#include <wctype.h>
#include "Interpreter.h"
#include "NUM2.h"


int NUMstring_containsPrintableCharacter (const char32 *s) {
	long len;
	if (s == NULL || ( (len = str32len (s)) == 0)) {
		return 0;
	}
	for (long i = 0; i < len; i++) {
		if (isgraph ((int) s[i])) {
			return 1;
		}
	}
	return 0;
}

void NUMstring_chopWhiteSpaceAtExtremes_inline (char32 *string) {
	int64 start = 0;
	while (iswspace ((int) string[start]) != 0) {
		start++;
	}
	int64 end = str32len (string);
	while (end != start && iswspace((int) string[end - 1]) != 0) {
		end--;
	}
	int64 n = end - start;
	memmove (string, string + start, (size_t) (n * (int64) sizeof (char32)));
	string[n] = 0;
}

double *NUMstring_to_numbers (const char32 *s, long *numbers_found) {
	*numbers_found = Melder_countTokens (s);
	if (*numbers_found < 1) {
		Melder_throw (U"Empty string.");
	}
	autoNUMvector<double> numbers (1, *numbers_found);
	long inum = 1;
	for (char32 *token = Melder_firstToken (s); token != 0; token = Melder_nextToken (), inum++) {
		Interpreter_numericExpression (0, token, &numbers[inum]);
	}
	return numbers.transfer();
}

void NUMstrings_copyElements (char32 **from, char32 **to, long lo, long hi) {
	for (long i = lo; i <= hi; i++) {
		Melder_free (to[i]);
		if (from[i]) {
			to[i] = Melder_dup (from[i]);
		}
	}
}

void NUMstrings_free (char32 **s, long lo, long hi) {
	if (s == NULL) {
		return;
	}
	for (long i = lo; i <= hi; i++) {
		Melder_free (s[i]);
	}
	NUMvector_free<char32 *> (s, lo);
}

char32 **NUMstrings_copy (char32 **from, long lo, long hi) {
	autoNUMvector<char32 *> to (lo, hi);
	NUMstrings_copyElements (from, to.peek(), lo, hi);
	return to.transfer();
}

static char32 *appendNumberToString (const char32 *s, long number, int asArray) {
	return Melder_dup (
		asArray == 0 ? Melder_cat (s, number) :
		asArray == 1 ? Melder_cat (s, U"[", number, U"]") :
		Melder_cat (s, U"(", number, U")"));
}

int NUMstrings_setSequentialNumbering (char32 **s, long lo, long hi, const char32 *pre, long number, long increment, int asArray) {
	for (long i = lo; i <= hi; i++, number += increment) {
		char32 *newc = appendNumberToString (pre, number, asArray);
		if (newc == NULL) {
			return 0;
		}
		Melder_free (s[i]);
		s[i] = newc;
	}
	return 1;
}

#define HIGHBYTE(x) ((unsigned char) ((x) & 0xFF))
#define LOWBYTE(x)  ((unsigned char) ((x) >> 8 & 0xFF))

/* a+b=c in radix 256 */
void NUMstring_add (unsigned char *a, unsigned char *b, unsigned char *c, long n);
void NUMstring_add (unsigned char *a, unsigned char *b, unsigned char *c, long n) {
	int j;
	unsigned short reg = 0;

	for (j = n; j > 1; j--) {
		reg = a[j] + b[j] + HIGHBYTE (reg);
		c[j + 1] = LOWBYTE (reg);
	}
}

char32 *strstr_regexp (const char32 *string, const char32 *search_regexp) {
	char32 *charp = 0;
	regexp *compiled_regexp = CompileRE_throwable (search_regexp, 0);

	if (ExecRE (compiled_regexp, NULL, string, NULL, 0, '\0', '\0', NULL, NULL, NULL)) {
		charp = compiled_regexp -> startp[0];
	}

	free (compiled_regexp);
	return charp;
}

char32 *str_replace_literal (const char32 *string, const char32 *search, const char32 *replace,
                              long maximumNumberOfReplaces, long *nmatches) {
	if (string == 0 || search == 0 || replace == 0) {
		return NULL;
	}


	int len_string = str32len (string);
	if (len_string == 0) {
		maximumNumberOfReplaces = 1;
	}
	int len_search = str32len (search);
	if (len_search == 0) {
		maximumNumberOfReplaces = 1;
	}

	/*
		To allocate memory for 'result' only once, we have to know how many
		matches will occur.
	*/

	const char32 *pos = string; //current position / start of current match
	*nmatches = 0;
	if (maximumNumberOfReplaces <= 0) {
		maximumNumberOfReplaces = LONG_MAX;
	}

	if (len_search == 0) { /* Search is empty string... */
		if (len_string == 0) {
			*nmatches = 1;    /* ...only matches empty string */
		}
	} else {
		if (len_string != 0) { /* Because empty string always matches */
			while ( (pos = str32str (pos, search)) && *nmatches < maximumNumberOfReplaces) {
				pos += len_search;
				(*nmatches) ++;
			}
		}
	}

	int64 len_replace = str32len (replace);
	int64 len_result = len_string + *nmatches * (len_replace - len_search);
	char32 *result = Melder_malloc (char32, (len_result + 1) * (int64) sizeof (char32));
	result[len_result] = '\0';

	const char32 *posp = pos = string;
	int nchar = 0, result_nchar = 0;
	for (long i = 1; i <= *nmatches; i++) {
		pos = str32str (pos, search);

		/*
			Copy gap between end of previous match and start of current.
		*/

		nchar = (pos - posp);
		if (nchar > 0) {
			str32ncpy (result + result_nchar, posp, nchar);
			result_nchar += nchar;
		}

		/*
			Insert the replace string in result.
		*/

		str32ncpy (result + result_nchar, replace, len_replace);
		result_nchar += len_replace;

		/*
			Next search starts after the match.
		*/

		pos += len_search;
		posp = pos;
	}

	/*
		Copy gap between end of match and end of string.
	*/

	pos = string + len_string;
	nchar = pos - posp;
	if (nchar > 0) {
		str32ncpy (result + result_nchar, posp, nchar);
	}
	return result;
}

char32 *str_replace_regexp (const char32 *string, regexp *compiledSearchRE,
                             const char32 *replaceRE, long maximumNumberOfReplaces, long *nmatches) {
	int buf_nchar = 0;				/* # characters in 'buf' */
	int gap_copied = 0;
	int nchar, reverse = 0;
	int errorType;
	char32 prev_char = '\0';
	const char32 *pos; 	/* current position in 'string' / start of current match */
	const char32 *posp; /* end of previous match */
	autostring32 buf;

	*nmatches = 0;
	if (string == 0 || compiledSearchRE == 0 || replaceRE == 0) {
		return 0;
	}

	int string_length = str32len (string);
	//int replace_length = str32len (replaceRE);
	if (string_length == 0) {
		maximumNumberOfReplaces = 1;
	}

	long i = maximumNumberOfReplaces > 0 ? 0 : - string_length;

	/*
		We do not know the size of the replaced string in advance,
		therefor, we allocate a replace buffer twice the size of the
		original string. After all replaces have taken place we do a
		final realloc to the then exactly known size.
		If during the replace, the size of the buffer happens to be too
		small (this is signalled by the replaceRE function),
		we double its size and restart the replace.
	*/

	int buf_size = 2 * string_length;
	buf_size = buf_size < 100 ? 100 : buf_size;
	buf.resize (buf_size);

	pos = posp = string;
	while (ExecRE (compiledSearchRE, 0, pos, 0, reverse, prev_char, '\0', 0, 0, 0) && i++ < maximumNumberOfReplaces) {
		/*
			Copy gap between the end of the previous match and the start
			of the current match.
			Check buffer overflow. pos == posp ? '\0' : pos[-1],
		*/

		pos = compiledSearchRE -> startp[0];
		nchar = pos - posp;
		if (nchar > 0 && ! gap_copied) {
			if (buf_nchar + nchar + 1 > buf_size) {
				buf_size *= 2;
				buf.resize (buf_size);
			}
			str32ncpy (buf.peek() + buf_nchar, posp, nchar);
			buf_nchar += nchar;
		}

		gap_copied = 1;

		/*
			Do the substitution. We can only check afterwards for buffer
			overflow. SubstituteRE puts null byte at last replaced position and signals when overflow.
		*/

		if ( (SubstituteRE (compiledSearchRE, replaceRE, buf.peek() + buf_nchar, buf_size - buf_nchar, &errorType)) == false) {
			if (errorType == 1) { // not enough memory
				buf_size *= 2;
				buf.resize (buf_size);
				Melder_clearError ();
				i--; // retry
				continue;
			}
			Melder_throw (U"Error during substitution.");
		}

		// Buffer is not full, get number of characters added;

		nchar = str32len (buf.peek() + buf_nchar);
		buf_nchar += nchar;

		// Update next start position in search string.

		posp = pos;
		pos = (char32 *) compiledSearchRE -> endp[0];
		if (pos != posp) {
			prev_char = pos[-1];
		}
		gap_copied = 0;
		posp = pos; //pb 20080121
		(*nmatches) ++;
		// at end of string?
		// we need this because .* matches at end of a string
		if (pos - string == string_length) {
			break;
		}
	}

	// Copy last part of string to destination string

	nchar = (string + string_length) - pos;
	buf_size = buf_nchar + nchar + 1;
	buf.resize (buf_size);

	str32ncpy (buf.peek() + buf_nchar, pos, nchar);
	buf[buf_size - 1] = '\0';
	return buf.transfer();
}

static char32 **strs_replace_literal (char32 **from, long lo, long hi, const char32 *search,
	const char32 *replace, int maximumNumberOfReplaces, long *nmatches, long *nstringmatches) {
	if (search == NULL || replace == NULL) {
		return NULL;
	}
	autostring32vector result (lo, hi);

	long nmatches_sub = 0;
	*nmatches = 0; *nstringmatches = 0;
	for (long i = lo; i <= hi; i++) {
		/* Treat a NULL as an empty string */
		const char32 *string = from[i] == NULL ? U"" : from[i];

		result[i] = str_replace_literal (string, search, replace, maximumNumberOfReplaces, &nmatches_sub);
		if (nmatches_sub > 0) {
			*nmatches += nmatches_sub;
			(*nstringmatches) ++;
		}
	}
	return result.transfer();
}

static char32 **strs_replace_regexp (char32 **from, long lo, long hi, const char32 *searchRE,
	const char32 *replaceRE, int maximumNumberOfReplaces, long *nmatches, long *nstringmatches) {
	if (searchRE == NULL || replaceRE == NULL) {
		return NULL;
	}
	autostring32vector result;

	long nmatches_sub = 0;

	regexp *compiledRE = CompileRE_throwable (searchRE, 0);

	result.reset (lo, hi);

	*nmatches = 0; *nstringmatches = 0;
	for (long i = lo; i <= hi; i++) {
		/* Treat a NULL as an empty string */
		const char32 *string = from[i] == NULL ? U"" : from[i];
		result [i] = str_replace_regexp (string, compiledRE, replaceRE,
										 maximumNumberOfReplaces, &nmatches_sub);
		if (nmatches_sub > 0) {
			*nmatches += nmatches_sub;
			(*nstringmatches) ++;
		}
	}
	return result.transfer();
}

char32 **strs_replace (char32 **from, long lo, long hi, const char32 *search, const char32 *replace,
                        int maximumNumberOfReplaces, long *nmatches, long *nstringmatches, int use_regexp) {
	if (use_regexp) return strs_replace_regexp (from, lo, hi, search,
		                       replace, maximumNumberOfReplaces, nmatches, nstringmatches);
	else return strs_replace_literal (from, lo, hi, search, replace,
		                                  maximumNumberOfReplaces, nmatches, nstringmatches);
}


/*
 * Acceptable ranges e.g. "1 4 2 3:7 4:3 3:5:2" -->
 * 1, 4, 2, 3, 4, 5, 6, 7, 4, 3, 3, 4, 5, 4, 3, 2
 * Overlap is allowed. Ranges can go up and down.
 */
static long *getElementsOfRanges (const char32 *ranges, long maximumElement, long *numberOfElements, const char32 *elementType) {
	/*
	 * Count the elements.
	 */
	long previousElement = 0;
	*numberOfElements = 0;
	const char32 *p = & ranges [0];
	for (;;) {
		while (*p == U' ' || *p == U'\t') p ++;
		if (*p == U'\0') break;
		if (isdigit ((int) *p)) {
			long currentElement = Melder_atoi (p);
			if (currentElement == 0)
				Melder_throw (U"No such ", elementType, U": 0 (minimum is 1).");
			if (currentElement > maximumElement)
				Melder_throw (U"No such ", elementType, U": ", currentElement, U" (maximum is ", maximumElement, U").");
			*numberOfElements += 1;
			previousElement = currentElement;
			do { p ++; } while (isdigit ((int) *p));
		} else if (*p == ':') {
			if (previousElement == 0)
				Melder_throw (U"Cannot start range with colon.");
			do { p ++; } while (*p == U' ' || *p == U'\t');
			if (*p == U'\0')
				Melder_throw (U"Cannot end range with colon.");
			if (! isdigit ((int) *p))
				Melder_throw (U"End of range should be a positive whole number.");
			long currentElement = Melder_atoi (p);
			if (currentElement == 0)
				Melder_throw (U"No such ", elementType, U": 0 (minimum is 1).");
			if (currentElement > maximumElement)
				Melder_throw (U"No such ", elementType, U": ", currentElement, U" (maximum is ", maximumElement, U").");
			if (currentElement > previousElement) {
				*numberOfElements += currentElement - previousElement;
			} else {
				*numberOfElements += previousElement - currentElement;
			}
			previousElement = currentElement;
			do { p ++; } while (isdigit ((int) *p));
		} else {
			Melder_throw (U"Start of range should be a positive whole number.");
		}
	}
	/*
	 * Create room for the elements.
	 */
	autoNUMvector <long> elements (1, *numberOfElements);
	/*
	 * Store the elements.
	 */
	previousElement = 0;
	*numberOfElements = 0;
	p = & ranges [0];
	for (;;) {
		while (*p == U' ' || *p == U'\t') p ++;
		if (*p == U'\0') break;
		if (isdigit ((int) *p)) {
			long currentElement = Melder_atoi (p);
			elements [++ *numberOfElements] = currentElement;
			previousElement = currentElement;
			do { p ++; } while (isdigit ((int) *p));
		} else if (*p == U':') {
			do { p ++; } while (*p == U' ' || *p == U'\t');
			long currentElement = Melder_atoi (p);
			if (currentElement > previousElement) {
				for (long ielement = previousElement + 1; ielement <= currentElement; ielement ++) {
					elements [++ *numberOfElements] = ielement;
				}
			} else {
				for (long ielement = previousElement - 1; ielement >= currentElement; ielement --) {
					elements [++ *numberOfElements] = ielement;
				}
			}
			previousElement = currentElement;
			do { p ++; } while (isdigit ((int) *p));
		}
	}
	return elements.transfer();
}

static void NUMlvector_getUniqueNumbers (long *numbers, long *numberOfElements, long *numberOfMultiples) {

	autoNUMvector<long> sorted (NUMvector_copy<long> (numbers, 1, *numberOfElements), 1);
	NUMsort_l (*numberOfElements, sorted.peek());
	if (numberOfMultiples != 0) {
		*numberOfMultiples = 0;
	}
	numbers[1] = sorted[1];
	long i = 2, n = 1;
	while (i <= *numberOfElements) {
		if (sorted[i] != sorted[i - 1]) {
			numbers[++n] = sorted[i];
		} else {
			if ((i > 2 && sorted[i - 1] != sorted[i - 1]) || i == 2) {
				if (numberOfMultiples) {
					(*numberOfMultiples)++;
				}
			}
		}
		i++;
	}
	*numberOfElements = n;
}

long *NUMstring_getElementsOfRanges (const char32 *ranges, long maximumElement, long *numberOfElements, long *numberOfMultiples, const char32 *elementType, bool sortedUniques) {
	autoNUMvector<long> elements (getElementsOfRanges (ranges, maximumElement, numberOfElements, elementType), 1);
	if (sortedUniques) {
		NUMlvector_getUniqueNumbers (elements.peek(), numberOfElements, numberOfMultiples);
	}
	return elements.transfer();
}

char32 * NUMstring_timeNoDot (double time) {
	static char32 string[100];
	long seconds = (long) floor (time);
	long ms = lround ((time - seconds) * 1000.0);
	Melder_sprint (string,100, U"_", seconds, U"_", ms);
	return string;
}

/* End of file NUMstring.cpp */
