// ABU
// building stext is a computational heavy task.
// Be sure you build it only on demand .. ( if requested..))   That's the way it is ! ok


// This code was extracted from MuPDF (v1.14) - source/fitz/stext-search.c
// and then adapted..
// Function  xfz_search_stext_page() derives from fz_search_stext_page()
//  adding the capability to start searching from an advanced position; 
//  moreover this new function return also the last searched position.
//
// November 2018 - A.Buratti

#include <string.h>
#include <limits.h>
#include "xfz_search_stext.h"

static float hdist(fz_point *dir, fz_point *a, fz_point *b)
{
	float dx = b->x - a->x;
	float dy = b->y - a->y;
	return fz_abs(dx * dir->x + dy * dir->y);
}

static float vdist(fz_point *dir, fz_point *a, fz_point *b)
{
	float dx = b->x - a->x;
	float dy = b->y - a->y;
	return fz_abs(dx * dir->y + dy * dir->x);
}

/* Highlight selection */

struct highlight
{
	int len, cap;
	fz_quad *box;
	float hfuzz, vfuzz;
};

 // some useful typedef
typedef int UniChar;       //  the 32-bit value of an Unicode charater (also know as a "Rune")
typedef const char *UTF8String ; //  string made of sequence varying-length Unicode characters



static 
int on_highlight_char(struct highlight *hits, fz_stext_line *line, fz_stext_char *ch)
{
	float vfuzz = ch->size * hits->vfuzz;
	float hfuzz = ch->size * hits->hfuzz;

	if (hits->len > 0)	{
		fz_quad *end = &hits->box[hits->len-1];
		if (hdist(&line->dir, &end->lr, &ch->quad.ll) < hfuzz
			&& vdist(&line->dir, &end->lr, &ch->quad.ll) < vfuzz
			&& hdist(&line->dir, &end->ur, &ch->quad.ul) < hfuzz
			&& vdist(&line->dir, &end->ur, &ch->quad.ul) < vfuzz)
		{
			end->ur = ch->quad.ur;
			end->lr = ch->quad.lr;
			return 0;
		}
	}

	if (hits->len >= hits->cap) return -1;  // stop searching
	
	hits->box[hits->len++] = ch->quad;
	return 0;
}


/* String search */

 // convert a (unicode) character:
 //   'A' ..'Z'  ->  'a' .. 'z'
 //   [whites]   ->  ' '
static inline UniChar canon(UniChar c)
{
	/* TODO: proper unicode case folding */
	/* TODO: character equivalence (a matches ä, etc) */
	if (c == 0xA0 || c == 0x2028 || c == 0x2029)
		return ' ';
	if (c == '\r' || c == '\n' || c == '\t')
		return ' ';
	if (c >= 'A' && c <= 'Z')
		return c - 'A' + 'a';
	return c;
}

 // convert the UTF8 'character' *s and place its 'canonized' unicode in *c.
 // returns the number of bytes consumed.  
static inline int chartocanon(UniChar *c, UTF8String s)
{
	int nBytes = fz_chartorune(c, s);  // NOTE: 'rune' === 'code-point === 'Unicode'
	*c = canon(*c);
	return nBytes;
}

 // search Unicode string (needle) in Unicode string (haystack)
 // both needle and haystack are compared with respect to their 'canonical' form
 // If found, return a pointer to the last character of needle in haystack,
 //  else NULL  ....
static const char *match_string(UTF8String haystack, UTF8String needle)
{
	UniChar hc, nc;
	UTF8String e = haystack;
	haystack += chartocanon(&hc, haystack);
	needle += chartocanon(&nc, needle);
	while (hc == nc)
	{
		e = haystack;
		if (hc == ' ')
			do
				haystack += chartocanon(&hc, haystack);
			while (hc == ' ');
		else
			haystack += chartocanon(&hc, haystack);
		if (nc == ' ')
			do
				needle += chartocanon(&nc, needle);
			while (nc == ' ');
		else
			needle += chartocanon(&nc, needle);
	}
	return nc == 0 ? e : NULL;
}

// return NULL if needle is not in haystack,
//  else return a pointer to the char in haystack just after the end of needle
static const char *find_string(UTF8String s, UTF8String needle, UTF8String *endp)
{
	UTF8String end;
	while (*s)
	{
		end = match_string(s, needle);
		if (end)
			return *endp = end, s;
		++s;
	}
	return *endp = NULL, NULL;
}

 
 // returns number of hits found
int
xfz_search_stext_page(fz_context *ctx, fz_stext_page *stext, int startRuneIdx, int *plastRuneIdx, const char *needle, fz_quad *quads, int max_quads)
{
	struct highlight hits;
	fz_stext_block *block;
	fz_stext_line *line;
	fz_stext_char *ch;
	fz_buffer *buffer = NULL; // a dynamic array for collecting all the runes

	UniChar dummy;

*plastRuneIdx = startRuneIdx;

	if (strlen(needle) == 0)
		return 0;

	hits.len = 0;
	hits.cap = max_quads;
	hits.box = quads;
	hits.hfuzz = 0.1f;
	hits.vfuzz = 0.1f;

	fz_try(ctx)
	{
		// ==
		// == STEP 0 - scan the stext structure and skip the first startRuneIdx runes
		//				( don't count implicit end-of-lines..)
		int runeCount = 0;
		for (block = stext->first_block; block; block = block->next) {
			if (block->type != FZ_STEXT_BLOCK_TEXT) continue;
			for (line = block->u.t.first_line; line; line = line->next)	{
				for (ch = line->first_char; ch; ch = ch->next) {
					if (runeCount == startRuneIdx) goto endOfSkip;
					++runeCount;
				}
			}
		}
	endOfSkip:
		if (runeCount < startRuneIdx) {
			// not enough runes ..
		    return 0;
		}

		 /* save the new start of stext scanning */
		fz_stext_block *block0 = block;
		fz_stext_line  *line0 = line;
		fz_stext_char  *ch0 = ch;

		// ==
        // == STEP 1 - load all remaining runes from stext to buffer
        // ==          (also add '\n' for implicit end-of-line)
        // ==         This is a smarter (Doh!) variant of fz_new_buffer_from_stext_page()
		// ==
		buffer = fz_new_buffer(ctx, 1024);
		for ( /*block*/ ; block ; block = block->next) {
			if (block->type != FZ_STEXT_BLOCK_TEXT) continue;
			if ( line == NULL ) { line = block->u.t.first_line; }
			for ( /*line*/ ; line; line = line->next)	{
				if( ch == NULL ) { ch = line->first_char; }
				for ( /*ch*/ ; ch; ch = ch->next) {
					fz_append_rune(ctx, buffer, ch->c);
				}
				fz_append_byte(ctx, buffer, '\n');
			}
			fz_append_byte(ctx, buffer, '\n');
		}

		// == from buffer, extract the UTF8String 'haystack'
		//    note that haystack is just a reference to some buffer's internal;
		//    we don't need to free it.
		UTF8String haystack = fz_string_from_buffer(ctx, buffer);

		// == STEP 2 - start the search
		UTF8String begin, end;
		begin = find_string(haystack, needle, &end);
		if (!begin)
			goto no_more_matches;
		//  now rescan haystring till 'needle'
		//  and at the same time rescan stext (starting from block0, line0, ch0).
		//  At every step (rune read), discared the top rune from haystack ..
		block = block0;
		line = line0;
		ch = ch0;

        int isInside = 0;
		*plastRuneIdx = startRuneIdx;
		for ( /*block*/ ; block ; block = block->next) {
			if (block->type != FZ_STEXT_BLOCK_TEXT) continue;
			if ( line == NULL ) { line = block->u.t.first_line; }
			for ( /*line*/ ; line; line = line->next)	{
				if( ch == NULL ) { ch = line->first_char; }
				for ( /*ch*/ ; ch; ch = ch->next) {
					++*plastRuneIdx; // just count 'pure' runes (don't count implicit newlines)
				 try_new_match:
					if (!isInside) {
						if (haystack >= begin)
							isInside = 1;
					}
					if (isInside) {
						if (haystack < end) {
							if (on_highlight_char(&hits, line, ch) == -1) {
								goto no_more_matches; // stop searching
							}
						} else {
							isInside = 0;
							if (hits.len >= hits.cap) goto no_more_matches; // stop searching
							begin = find_string(haystack, needle, &end);
							if (!begin)
								goto no_more_matches;
							else
								goto try_new_match;
						}
					}
					haystack += fz_chartorune(&dummy, haystack);
				}  // end of ch loop
				++haystack ; // skip the newline
			} // end of line loop
			++haystack ; // skip the newline
		} // end of block loop
no_more_matches:
			;
	}
	fz_always(ctx)
		fz_drop_buffer(ctx, buffer);
	fz_catch(ctx)
		fz_rethrow(ctx);

	return hits.len;
}
