/*
   netrik -- The ANTRIK Internet Viewer
   Copyright (C) Olaf D. Buddenhagen AKA antrik, et al (see AUTHORS)
   Published under the GNU GPL; see LICENSE for details.
*/
/*
 * pre-render.c -- this one assigns page positions to all items.
 *
 * (C) 2001, 2002 antrik
 *
 * It takes the item tree generated by parse_struct, which contains only the
 * structure of the page, and assigns actual sizes and coordinates to the
 * items. It also breaks text blocks into lines. Finally it creates the page
 * allocation map, which allows quick finding of all items which show up in
 * some line.
 */
#include <assert.h>
#include <stdio.h>
#include <stdlib.h>

#include "debug.h"
#include "items.h"
#include "cfg.h"

static void calc_width(struct Item *item_tree);    /* calculate minimal x-size of all items */
static void assign_width(struct Item *item_tree);    /* assign x-coordinates to all items */
static void calc_ywidth(struct Item *item_tree);    /* calculate minimal y-size of all items */
static void assign_ywidth(struct Item *item_tree);    /* assign y-coordinates to all items */
static struct Item_list *create_map(struct Item *item_tree);    /* create page usage map */

/* calculate minimal x-size of all items
 * (longest word size for text blocks; widest sub-item for boxes) */
static void calc_width(item_tree)
struct Item	*item_tree;
{
   struct Item	*cur_item;

   for(cur_item=item_tree->parent; cur_item!=NULL; cur_item=cur_item->list_next)    /* all items (starting from bottom) */
      switch(cur_item->type) {

	 case ITEM_TEXT: {    /* find longest word length */
	    int		len=0;    /* chars found up to now in currently tested word */
	    int		longest=0;    /* longest word up to now */
	    char	*pos;    /* currently processed char */

	    for(pos=cur_item->data.string->text; *pos; ++pos) {    /* whole text block */
	       ++len;    /* add current letter */
	       if((unsigned)*pos<=' ')    /* word end -> start new */
		  len=0;
	       if(len>longest)
		  longest=len;
	    }

	    cur_item->x_end=longest;    /* store minimal width */
	    break;
	 }

	 case ITEM_BLANK:
	 case ITEM_BLOCK_ANCHOR:
	 case ITEM_INLINE_ANCHOR:
	    cur_item->x_end=0;    /* blank lines and anchors need no width... */
	    break;

	 case ITEM_BOX:
	 case ITEM_FORM: {    /* find widest sub-item */
	    struct Item	*item;    /* currently tested sub-item */
	    int		widest=0;

	    for(item=cur_item->first_child; item!=NULL; item=item->next)    /* all sub-items */
	       if(item->x_end>widest)
		  widest=item->x_end;

	    cur_item->x_end=widest;    /* store min size of box (== min size of widest element) */
	    break;
	 }

      }    /* switch item_type */
}

/* assign x-coordinates to all items;
 * also breaks text blocks into lines and stores line counts */
static void assign_width(item_tree)
struct Item	*item_tree;
{
   struct Item	*cur_item;

   /* for all items (starting from top) */
   cur_item=item_tree;
   do {    /* until back at top */

      switch(cur_item->type) {
	 
	 case ITEM_TEXT: {    /* split into lines */
	    const int	width=cur_item->x_end-cur_item->x_start;    /* x_width of text block */
	    const char	*string_start=cur_item->data.string->text;

	    char	*word_start;
	    char	*word_end;    /* points to space (or string end) terminating currently processed word */
	    char	*next_word_start;
	    char	*line_start;

	    int		num_lines;    /* number of *full* lines (== number of line breaks) */
	    int		*line_table;    /* positions of line breaks */

	    /* process whole text block */
	    num_lines=0; line_table=NULL;
	    word_start=line_start=(char *)string_start;
	    do {    /* until string end */

	       for(word_end=word_start; (unsigned)*word_end > ' '; ++word_end);    /* scan for ' ', '\n' or '\0' */
	       next_word_start=word_end+1;    /* next word starts after the ' ' terminating current one */

	       if(word_start > string_start && word_start[-1]=='\n')    /* after newline -> force line wrap */
		  word_end=word_start+width;    /* pretend a word having exactly the line width, to ensure current word will be put on a new line (but keep "next_word_start", so processing will continue normally in next iteration) */

	       if(word_end > line_start+width) {    /* word does not fit on current line -> line wrap */
		  char	*trunc_word_end;

		  for(trunc_word_end=word_end; trunc_word_end > word_start+width; trunc_word_end-=width-1);    /* if word is longer than line width, truncate (width-1, because every word break inserts one additional character) */

		  if(trunc_word_end <= line_start+width)    /* truncated, and remaining part fits on line */
		     line_start=line_start+width-1;    /* -> wrap word at line end (put beginning of word on current line) */
		  else    /* not truncated, or didn't help */
		     line_start=word_start;    /* -> wrap at word start */

		  if(next_word_start-1 > line_start+width)    /* word doesn't fit on new line completely (can't use "word_end" here as it may be faked by '\n' handling!) */
		     next_word_start=line_start+width-1;    /* -> don't continue processing in next iteration with next word, but with the remaining word part that doesn't fit (and needs to be wrapped again) */

		  /* add new line wrap to line table */
		  line_table=realloc(line_table, ++num_lines*sizeof(int));
		  if(line_table==NULL) {
		     fprintf(stderr, "memory allocation error while pre-rendering (in function assign_width)\n");
		     exit(1);
		  }
		  line_table[num_lines-1]=line_start-string_start;    /* position of line break relative to string start */
	       }    /* line wrap */

	       word_start=next_word_start;    /* proceed with next word */
	    } while(*(word_start-1));    /* until string end */

	    cur_item->y_end=num_lines+1;    /* store number of lines (linebreaks+1) as y-width of text block */
	    cur_item->data.string->line_table=line_table;
	    break;
	 }

	 case ITEM_BOX:
	 case ITEM_FORM: {    /* pass on x-width to sub-items */
	    struct Item	*child_item;

	    for(child_item=cur_item->first_child; child_item!=NULL; child_item=child_item->next) {    /* all immediate children */
	       child_item->x_start=cur_item->x_start;
	       child_item->x_end=cur_item->x_end;
	    }
	    break;
	 }

	 case ITEM_BLANK:    /* blank lines and anchors have no children => nothing to do */
	 case ITEM_BLOCK_ANCHOR:
	 case ITEM_INLINE_ANCHOR:
	    break;

      }    /* switch item_type */

      /* next item */
      if(cur_item->first_child==NULL) {    /* no children -> go to next item */
	 while(cur_item->next==NULL)    /* no further items at this depth -> ascend before following "next" */
	    cur_item=cur_item->parent;
	 cur_item=cur_item->next;
      } else    /* has children -> descend */
	 cur_item=cur_item->first_child;
   } while(cur_item!=item_tree);    /* for all items (until back at top) */

}

/* calculate minimal y-size of all items
 * (sum of y-sizes of all sub-items) */
static void calc_ywidth(item_tree)
struct Item	*item_tree;
{
   struct Item	*cur_item;

   for(cur_item=item_tree->parent; cur_item!=NULL; cur_item=cur_item->list_next)    /* all items (starting from bottom) */
      switch(cur_item->type) {

	 case ITEM_TEXT:    /* ywidth already calculated during line splitting in "assign_width" */
	    break;

	 case ITEM_BLANK:
	    cur_item->y_end=1;    /* blank lines have constant ywidth */
	    break;

	 case ITEM_BOX:
	 case ITEM_FORM: {    /* sum up sizes of all sub-items */
	    struct Item	*item;    /* currently handled sub-item */
	    int		ywidth=0;

	    for(item=cur_item->first_child; item!=NULL; item=item->next)    /* all sub-items */
	       ywidth+=item->y_end;

	    cur_item->y_end=ywidth;    /* store sum as min y-width of box */
	    break;
	 }

	 case ITEM_BLOCK_ANCHOR:
	 case ITEM_INLINE_ANCHOR:
	    cur_item->y_end=0;    /* anchors need no space */
	    break;
	    
      }    /* switch item_type */
}

/* assign y-coordinates to all items;
 * also assigns coordinates of links and anchors */
static void assign_ywidth(item_tree)
struct Item	*item_tree;
{
   struct Item	*cur_item;

   item_tree->y_start=0;    /* global box item starts at top of page */

   /* for all items (starting from top) */
   cur_item=item_tree;
   do {    /* until back at top */

      switch(cur_item->type) {
	 
	 case ITEM_TEXT: {    /* assign coordinates to all links */
	    int	link;
	    int	line;    /* line in which last link ended */

	    line=cur_item->y_start;    /* begin scanning at first line of text block */

	    for(link=0; link<cur_item->data.string->link_count; ++link) {
	       /* find line containing link start */
	       for(; line<cur_item->y_end; ++line) {
		  if(cur_item->data.string->link[link].start < line_end(cur_item, line))    /* link starts in this line */
		     break;    /* -> don't search further */
	       }

	       /* store link start position */
	       cur_item->data.string->link[link].y_start=line;
	       cur_item->data.string->link[link].x_start=line_pos(cur_item, line)+cur_item->data.string->link[link].start-line_start(cur_item, line);    /* line start+(link position inside line=link position inside text block-line start position inside text block) */

	       /* find line containing link end */
	       for(; line<cur_item->y_end; ++line) {
		  if(cur_item->data.string->link[link].end <= line_end(cur_item, line))    /* link ends in this line */
		     break;    /* -> don't search further */
	       }

	       /* store link end position */
	       cur_item->data.string->link[link].y_end=line+1;    /* y_end points after last link line */
	       cur_item->data.string->link[link].x_end=line_pos(cur_item, line)+cur_item->data.string->link[link].end-line_start(cur_item, line);
	    }    /* for all links */
	    break;
	 }    /* ITEM_TEXT */

	 case ITEM_BOX:
	 case ITEM_FORM: {    /* give every sub-item its minimal size */
	    struct Item	*child_item;
	    int		y_pos;    /* y-position to be assigned to next sub-item */

	    y_pos=cur_item->y_start;    /* first sub-item starts at beginning of block */
	    for(child_item=cur_item->first_child; child_item!=NULL; child_item=child_item->next) {    /* all immediate children */
	       child_item->y_start=y_pos;    /* begins at current position */
	       child_item->y_end=child_item->y_start+child_item->y_end;    /* ends at start position + y-width */
	       y_pos=child_item->y_end;    /* next sub-item starts where this one ends */
	    }
	    break;
	 }

	 case ITEM_BLANK:    /* blank items have no children -> nothing to be done */
	    break;

	 case ITEM_BLOCK_ANCHOR: {    /* find outer bounds of virtual box */
	    int		x_start=(unsigned)-1>>1;    /* biggest possible positive int */
	    int		x_end=-1;
	    int		y_start=(unsigned)-1>>1;
	    int		y_end=-1;
	    
	    struct Item	*item;

	    /* find */
	    for(item=cur_item->data.block_anchor->virtual_child; item!=cur_item; item=item->list_next) {    /* all virtual children */
	       if(item->x_start < x_start)
		  x_start=item->x_start;
	       if(item->x_end > x_end)
		  x_end=item->x_end;
	       if(item->y_start < y_start)
		  y_start=item->y_start;
	       if(item->y_end > y_end)
		  y_end=item->y_end;
	    }

	    /* store */
	    if(x_end>=0) {    /* any coordintes found (virutal box not empty) -> store them (otherwise keep coordinates assigned by parent) */
	       cur_item->x_start=x_start;
	       cur_item->x_end=x_end;
	       cur_item->y_start=y_start;
	       cur_item->y_end=y_end;
	    }

	    break;
	 }    /* ITEM_BLOCK_ANCHOR */

	 case ITEM_INLINE_ANCHOR: {    /* find out anchor coordinates from string coordinates/line wraps */
	    const struct Item	*string_item=cur_item->data.inline_anchor->virtual_parent;    /* text block containing the anchor */
	    const struct String	*string=string_item->data.string;

	    int	line;    /* currently scanned line (absolute page coordinates) */

	    /* find line containing anchor start */
	    for(line=string_item->y_start; line < string_item->y_end; ++line) {    /* all lines in text block */
	       if(cur_item->data.inline_anchor->start < line_end(string_item, line))    /* anchor starts in this line */
		  break;    /* -> don't search further */

	       /* special case: (empty) anchor at string end is considered to be at end of last line, not beginning of (non-existant) next line... */
	       if(line==string_item->y_end-1)
		  break;
	    }

	    /* store anchor start position */
	    cur_item->y_start=line;
	    cur_item->x_start=line_pos(string_item, line)+cur_item->data.inline_anchor->start-line_start(string_item, line);    /* line start+(anchor position inside line=anchor position inside text block-line start position inside text block) */

	    /* find line containing anchor end */
	    for(; line < string_item->y_end; ++line) {    /* all remaining lines */
	       if(cur_item->data.inline_anchor->end <= line_end(string_item, line))    /* anchor ends in this line */
		  break;    /* -> don't search further */
	    }
	    assert(line < string_item->y_end);    /* always should find it */

	    /* store anchor end position */
	    cur_item->y_end=line+1;    /* y_end points after last anchor line */
	    cur_item->x_end=line_pos(string_item, line)+cur_item->data.inline_anchor->end-line_start(string_item, line);

	    break;
	 }    /* ITEM_INLINE_ANCHOR */

      }    /* switch item_type */

      /* next item */
      if(cur_item->first_child==NULL) {    /* no children -> go to next item */
	 while(cur_item->next==NULL)    /* if last item at this depth: ascend before going to next item */
	    cur_item=cur_item->parent;
	 cur_item=cur_item->next;
      } else    /* has children -> descend */
	 cur_item=cur_item->first_child;
   } while(cur_item!=item_tree);    /* for all items (until back at top) */

}

/* create page usage map
 * (stores a reference for every item to all lines in "page_map" it spans) */
static struct Item_list *create_map(item_tree)
struct Item	*item_tree;
{
   struct Item		*cur_item;
   struct Item_list	*page_map;    /* page usage map */

   /* alloc usage lists for all lines */
   page_map=calloc(item_tree->y_end, sizeof(struct Item_list));    /* page_map[].num need to be 0-initialized */
   if(page_map==NULL) {
      fprintf(stderr, "memory allocation error while pre-rendering (in function create_map)\n");
      exit(1);
   }

   for(cur_item=item_tree->parent; cur_item!=NULL; cur_item=cur_item->list_next)    /* all items (starting from bottom) */
      switch(cur_item->type) {

	 case ITEM_TEXT: {    /* add text item to all lines it spans */
	    int	y_pos;    /* currently processed line */

	    for(y_pos=cur_item->y_start; y_pos<cur_item->y_end; ++y_pos) {    /* all spanned lines */

	       /* alloc new element in line_list of current line */
	       page_map[y_pos].item=realloc(page_map[y_pos].item, ++page_map[y_pos].count*sizeof(struct Item *));
	       if(page_map[y_pos].item==NULL) {
		  fprintf(stderr, "memory allocation error while pre-rendering (in function create_map)\n");
		  exit(1);
	       }

	       page_map[y_pos].item[page_map[y_pos].count-1]=cur_item;    /* insert pointer to item as the new (last) element */
	    }
	    break;
	 }

	 case ITEM_BLANK:
	    break;    /* blank lines needn't be displayed... */

	 case ITEM_BOX:
	 case ITEM_FORM:
	    break;    /* boxes are invisible... */

	 case ITEM_BLOCK_ANCHOR:
	 case ITEM_INLINE_ANCHOR:
	    break;    /* virtual items are invisible... */

      }    /* switch item_type */

   return page_map;
}

/* place all items on page;
 * includes calculating minimal widths, line breaking, and generating a space usage map */
struct Item_list *pre_render(item_tree, width)
struct Item	*item_tree;
int		width;
{
   struct Item_list	*page_map;    /* page usage map */

   DMSG(("width: %d\n", width));

   DMSG(("   calculating minimal width...\n"));
   calc_width(item_tree);
   item_tree->x_start=0;
   if(!cfg.dump) {    /* use pager */
      if(cfg.term_width)    /* force page width to screen width, even if wants to be wider */
	 item_tree->x_end=width;
      else {    /* don't force screen width */
	 if(item_tree->x_end<width)    /* smaller than screen -> grow */
	    item_tree->x_end=width;
      }
   } else    /* dump -> always force width */
      item_tree->x_end=width;
   DMSG(("   assigning width (%d)...\n", item_tree->x_end));
   assign_width(item_tree);

   DMSG(("   calculating y-width...\n"));
   calc_ywidth(item_tree);
   DMSG(("   assigning y-width...\n"));
   assign_ywidth(item_tree);

   DMSG(("   creating page usage map...\n"));
   page_map=create_map(item_tree);

   return page_map;
}

/* unallocate page usage map;
 * frees item lists of all lines, and then the map array */
void free_map(item_tree, page_map)
struct Item		*item_tree;    /* need to know page length... */
struct Item_list	*page_map;
{
   int	line;

   for(line=0; line<item_tree->y_end; ++line)
      free(page_map[line].item);

   free(page_map);
}