/* Simple span buffer manager V3.44 10/9/04
   See span.h for docs
   Copyright 2008 Jeffrey Lee
   This file is part of WOUM.
   WOUM 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 3 of the License, or
   (at your option) any later version.
   WOUM 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 WOUM.  If not, see <http://www.gnu.org/licenses/>.
*/

#ifndef _SPAN_C
#define _SPAN_C

#include <stdlib.h>
#include <stdio.h>
#include <math.h>
#include "span.h"
#include "cbma.h"
#include "error.h"

/*#define DEBUG*/
/*#define DUMP*/
/*#define TREE*/
#define DEPTHCHECKS
/*#define COUNT*/

/* invz handling gumpf */

invz f1616_to_invz(f1616 a)
{
	return F16_TO_INVZ(a);
}

f1616 invz_to_f1616(invz a)
{
	return INVZ_TO_F16(a);
}

/* General buffer data */

int span_lines,span_width;
void *span_buf;
int span_gap,span_ps;

int span_id;

/* Spans */

#ifdef TREE
struct _node;
#endif

typedef struct _span {
	int x_start;
	invz iz_start,iz_grad;
	int col;
	int id;
	struct _span *next; /* Linear list */
#ifdef TREE
	struct _span *prev;
	struct _node *parent; /* The parent node */
#endif
} span;

static cbma_heap spanchunks = 0;

#define SPANCHUNK_SIZE 1024

#ifdef COUNT
static int numspan;
#endif

static inline span *allocspan()
{
#ifdef COUNT
	numspan++;
#endif
	return (span *) cbma_alloc(spanchunks);
}

static inline void freespan(span *s)
{
#ifdef COUNT
	numspan--;
#endif
	cbma_free(spanchunks,s);
}

/* Span trees */

#ifdef TREE
typedef struct _node {
	int mask,twiddle,pos;
	void *zero,*one; /* If twiddle == 1, they are span ptrs else node ptrs */
	struct _node *parent; /* The parent node */
} node; /* Node in the span tree */

static node **nodes; /* Array of node ptrs, one per screen row */

static cbma_heap nodechunks = 0;

#define NODECHUNK_SIZE 256

static inline node *allocnode()
{
	return (node *) cbma_alloc(nodechunks);
}

static inline void freenode(node *n) /* Assumes there are no children! */
{
	cbma_free(nodechunks,n);
}
#else
span **spans; /* Array of span ptrs, one per screen row */
#endif

/* Return the Z value at 'x' for span 's' */
#define ZAT(s,x) (s->iz_start+s->iz_grad*(x-s->x_start))

/* Span sets */

typedef struct {
#ifdef TREE
	node **nodes;
	cbma_heap nodechunks;
#else
	span **spans;
#endif
	cbma_heap spanchunks;
} _spanset;

#define SWP(a,b) tmp = (void *) (a); a = b; b = (typeof(b)) (tmp)

void span_swapset(spanset s)
{
	_spanset *ss;
	void *tmp;
	if (s == 0)
		return; /* Give up */
	ss = (_spanset *) s;
#ifdef TREE
	SWP(ss->nodes,nodes);
	SWP(ss->nodechunks,nodechunks);
#else
	SWP(ss->spans,spans);
#endif
	SWP(ss->spanchunks,spanchunks);
}

#undef SWP

spanset span_saveset()
{
	_spanset *ss;
	ss = malloc(sizeof(_spanset));
#ifdef TREE
	ss->nodes = nodes;
	ss->nodechunks = nodechunks;
#else
	ss->spans = spans;
#endif
	ss->spanchunks = spanchunks;
	/* Clear current set */
#ifdef TREE
	nodes = 0;
	nodechunks = 0;
#else
	spans = 0;
#endif
	spanchunks = 0;
	/* Return */
	return (spanset) ss;
}

/* System init/shutdown */

void span_free(spanset s)
{
	if (s)
		span_swapset(s);
#ifdef TREE
	if (nodes)
	{
		free(nodes);
		nodes = 0;
	}
	/* Node chunks */
	if (nodechunks)
	{
		cbma_delete(nodechunks);
		nodechunks = 0;
	}
#else
	if (spans)
	{
		free(spans);
		spans = 0;
	}
#endif
	/* Destroy free span chunks */
	if (spanchunks)
	{
		cbma_delete(spanchunks);
		spanchunks = 0;
	}
	if (s)
	{
		span_swapset(s);
		free(s);
	}
#ifdef COUNT
	printf("%d\n",numspan);
	numspan = 0;
#endif
}

void span_init(int col)
{
	int i;
#ifdef TREE
	int mask,twiddle;
	node *n;
#endif
	span *s,*ss;
	invz minz,maxz;
#ifdef COUNT
	numspan = 0;
#endif
	/* Initialise system */
	if (spanchunks == 0)
		spanchunks = cbma_new(sizeof(span),SPANCHUNK_SIZE);
#ifdef TREE
	if (nodechunks == 0)
		nodechunks = cbma_new(sizeof(node),NODECHUNK_SIZE);
	nodes = malloc(sizeof(node *)*span_lines);
	/* Calculate top level mask to use */
	mask = ~1;
	twiddle = 1;
	while ((mask & span_width) != 0)
	{
		twiddle *= 2;
		mask ^= twiddle;
	}
#else
	spans = malloc(sizeof(span *)*span_lines);
#endif
	minz = F16_TO_INVZ(FARTHEST_Z); /* Note that these are back to front, as inverting them will make the farthest (i.e. biggest Z) the smallest of the two */
	maxz = F16_TO_INVZ(CLOSEST_Z);
#ifndef TREE
	ss = allocspan();
	ss->next = 0;
	ss->x_start = span_width;
	ss->iz_start = maxz;
	ss->iz_grad = 0;
	ss->col = ss->id = 0;
#endif
	/* Now fill with initial nodes */
	for (i=0;i<span_lines;i++)
	{
#ifdef TREE
		nodes[i] = allocnode();
		nodes[i]->parent = 0;
		nodes[i]->mask = mask;
		nodes[i]->twiddle = twiddle;
		nodes[i]->pos = mask & span_width;
		nodes[i]->zero = n = allocnode();
		n->parent = nodes[i];
		n->mask = ~1;
		n->twiddle = 1;
		n->pos = 0;
		n->one = 0;
		n->zero = s = allocspan();
		s->parent = n;
		s->prev = 0;
#else
		spans[i] = s = allocspan();
#endif
		s->x_start = 0;
		s->iz_start = minz;
		s->iz_grad = 0;
		s->col = col;
		s->id = span_id;
#ifdef TREE
		nodes[i]->one = n = allocnode();
		n->parent = nodes[i];
		n->mask = ~1;
		n->twiddle = 1;
		n->pos = span_width & n->mask;
		if (span_width & 1)
		{
			n->zero = 0;
			n->one = ss = allocspan();
		}
		else
		{
			n->one = 0;
			n->zero = ss = allocspan();
		}
		ss->parent = n;
		ss->prev = s;
		s->next = ss;
		ss->next = 0;
		ss->x_start = span_width;
		ss->iz_start = maxz;
		ss->iz_grad = 0;
		ss->col = ss->id = 0;
#else
		s->next = ss;
#endif
	}
}

/* Rendering */

#define DITHERING

#ifdef DITHERING
#define ROTCOL(col,y,ps) ((ps == 0) && (y & 1) ? ((y & 2) ? (col >> 24) + (col << 8) : (col >> 8) + (col << 24)) : ((ps <= 1) && (y & (2-ps)) ? (col >> 16) + (col << 16) : col))
#else
#define ROTCOL(col,y,ps) col
#endif


void span_do()
{
	/* Traverse LH edge until span list reached
	   Then draw using the linear ptrs */
	int y;
#ifdef TREE
	node *n;
#endif
	register span *cspan;
	register int x,len,col;
	register char *scr;
#ifdef SAFE
	int loop;
#endif
	for (y=0;y<span_lines;y++)
	{
		scr = (char *) (span_buf+y*((span_width << span_ps)+span_gap));
#ifdef TREE
		n = nodes[y];
		while (n->twiddle != 1)
			n = n->zero;
		cspan = n->zero;
#else
		cspan = spans[y];
#endif
#ifdef SAFE
		loop = 0;
		while ((cspan->next) && (loop++ < 10000))
#else
		while (cspan->next) /* Ensure we don't draw the end one */
#endif
		{
			x = cspan->x_start;
			len = cspan->next->x_start - x;
			col = cspan->col;
#ifdef SAFE
			if (x + len > span_width)
				warning("Line too long at %d,%d",x,y);
			else if (x < 0)
				warning("Line starts before 0 at %d,%d",x,y);
			else if (len <= 0)
				warning("Line too short on line %d, x %d to %d, col %d to %d",y,x,cspan->next->x_start,col,cspan->next->col);
			else
#endif
#ifdef SKIPID
			if (cspan->id == SKIPID)
			{
				x += len;
				scr += len << span_ps;
			}
			else
#endif
			if (span_ps == 0)
				do {
					scr[x++] = col;
				} while (len--);
			else if (span_ps == 1)
				do {
					scr[x*2] = col;
					scr[x++*2+1] = col >> 8;
				} while (len--);
			else /* Assume 2 */
				do {
					scr[x*4] = col;
					scr[x*4 + 1] = col >> 8;
					scr[x*4 + 2] = col >> 16;
					scr[x++*4 + 3] = col >> 24;
				} while (len--);
			cspan = cspan->next;
		}
#ifdef SAFE
		if (loop >= 10000)
			warning("Too many spans on line %d",y);
#endif
	}
}

void span_do2(void (*func)(int,void *,int))
{
	register int y;
#ifdef TREE
	register node *n;
#endif
	register span *cspan;
	register void *buf;
	buf = span_buf;
	for (y=0;y<span_lines;y++)
	{
#ifdef TREE
		n = nodes[y];
		while (n->twiddle != 1)
			n = n->zero;
		cspan = n->zero;
#else
		cspan = spans[y];
#endif
		while (cspan->next) /* Ensure we don't draw the end one */
		{
#ifdef SKIPID
			if (cspan->id != SKIPID)
#endif
				(func)(ROTCOL(((unsigned int) cspan->col),y,span_ps),buf+(cspan->x_start << span_ps),cspan->next->x_start - cspan->x_start);
			cspan = cspan->next;
		}
		buf += (span_width << span_ps)+span_gap;
	}
}

spanset span_do3(void (*func)(int,void *,int),spanset s)
{
	register int y;
#ifdef TREE
	register node *n;
#endif
	register span *cspan,*cspan2;
	register int x; /* X to draw from */
	register void *buf; /* Pointer into screen buffer for current Y pos */
	_spanset *ss;
	if (s == 0)
	{
		span_do2(func); /* Draw them all */
		/* copy current set as new */
		ss = malloc(sizeof(_spanset));
#ifdef TREE
		ss->nodes = nodes;
		ss->nodechunks = nodechunks;
#else
		ss->spans = spans;
#endif
		ss->spanchunks = spanchunks;
		/* Clear current set */
#ifdef TREE
		nodes = 0;
		nodechunks = cbma_new(sizeof(node),NODECHUNK_SIZE);
#else
		spans = 0;
#endif
		spanchunks = cbma_new(sizeof(span),SPANCHUNK_SIZE);
		/* Return */
		return (spanset) ss;
	}
	/* Else draw difference */
	buf = span_buf;
	ss = (_spanset *) s;
	for (y=0;y<span_lines;y++)
	{
#ifdef TREE
		n = nodes[y];
		while (n->twiddle != 1)
			n = n->zero;
		cspan = n->zero;
		n = ss->nodes[y];
		while (n->twiddle != 1)
			n = n->zero;
		cspan2 = n->zero; /* one we are writing over */
#else
		cspan = spans[y];
		cspan2 = ss->spans[y];
#endif
		while (cspan->next)
		{
			/* Need to split up on each cspan2... */
			/* Hmm */
			/* cspan2 guaranteed to start on or before cspan */
			/* So check draw till cspan2->next->x_start-1 inclusive until cspan2->next->x_start >= cspan->next->x_start */
			/* Then check one more time if needed */
			x = cspan->x_start; /* Drawing starts from here */
			while (cspan2->next->x_start < cspan->next->x_start)
			{
				if (((cspan2->col != cspan->col)
#ifdef SKIPID
						|| (cspan2->id == SKIPID)
#endif
						) && (x != cspan2->next->x_start)
#ifdef SKIPID
						&& (cspan->id != SKIPID)
#endif
						)
					(func)(ROTCOL(((unsigned int) cspan->col),y,span_ps),buf+(x << span_ps),cspan2->next->x_start-x);
				x = cspan2->next->x_start;
				cspan2 = cspan2->next;
			}
			if (cspan2->x_start < cspan->next->x_start) /* Gap at end */
				if (((cspan2->col != cspan->col)
#ifdef SKIPID
						|| (cspan2->id == SKIPID)
#endif
						)
#ifdef SKIPID
						&& (cspan->id != SKIPID)
#endif
						)
					(func)(ROTCOL(((unsigned int) cspan->col),y,span_ps),buf+(x << span_ps),cspan->next->x_start-x);
			cspan = cspan->next;
		}
		buf += (span_width << span_ps)+span_gap; /* Move pointer to next line */
	}
	/* Now update 's', by swapping between the two sets */
	span_swapset(s);
	return s;
}

/* Interrogation */

#ifdef TREE
static span *findspan(node *n,int x) /* Return the span that x lies in */
{
	span *s;
#ifdef PARANOID
	if (n == 0)
		error("findspan called with null node ptr");
	if ((n->mask & x) != n->pos)
		error("findspan called with pos not in initial node");
#endif
	while (n->twiddle != 1)
	{
		if (x >= n->pos + n->twiddle)
			n = n->one; /* Head right, either because (x & twiddle) or we've overshot to the left */
		else
			n = n->zero; /* Head left, either because (x & twiddle) == 0 or we've overshot to the right */
	}
	if ((x > n->pos) && (n->one))
		return (span *) n->one; /* Right branch wanted and available */
	else if (n->zero)
		s = (span *) n->zero; /* Else left branch must be taken */
	else
		s = (span *) n->one; /* Or right branch if left branch was wanted and wasn't available */
	if (s->x_start > x) /* Do we need to backtrack? */
		return s->prev; /* Yes */
	return s; /* No */
}
#else
static span *findspan(span *s,int x) /* Return the span that x lies in */
{
	while (s->next->x_start <= x)
		s = s->next;
	return s;
}
#endif

int span_readcol(spanset si,int x,int y)
{
	span *s;
	if ((x < 0) || (x >= span_width) || (y < 0) || (y >= span_lines))
		return 0;
#ifdef TREE
	if (si)
		s = findspan(((_spanset *) si)->nodes[y],x);
	else
		s = findspan(nodes[y],x);
#else
	if (si)
		s = findspan(((_spanset *) si)->spans[y],x);
	else
		s = findspan(spans[y],x);
#endif
	return s->col;
}

f1616 span_readdepth(spanset si,int x,int y)
{
	span *s;
	if ((x < 0) || (x >= span_width) || (y < 0) || (y >= span_lines))
		return 0;
#ifdef TREE
	if (si)
		s = findspan(((_spanset *) si)->nodes[y],x);
	else
		s = findspan(nodes[y],x);
#else
	if (si)
		s = findspan(((_spanset *) si)->spans[y],x);
	else
		s = findspan(spans[y],x);
#endif
	return INVZ_TO_F16(ZAT(s,x));
}

int span_readid(spanset si,int x,int y)
{
	span *s;
	if ((x < 0) || (x >= span_width) || (y < 0) || (y >= span_lines))
		return 0;
#ifdef TREE
	if (si)
		s = findspan(((_spanset *) si)->nodes[y],x);
	else
		s = findspan(nodes[y],x);
#else
	if (si)
		s = findspan(((_spanset *) si)->spans[y],x);
	else
		s = findspan(spans[y],x);
#endif
	return s->id;
}

int span_readstart(void *si,int x,int y)
{
	span *s;
	if ((x < 0) || (x >= span_width) || (y < 0) || (y >= span_lines))
		return 0;
#ifdef TREE
	if (si)
		s = findspan(((_spanset *) si)->nodes[y],x);
	else
		s = findspan(nodes[y],x);
#else
	if (si)
		s = findspan(((_spanset *) si)->spans[y],x);
	else
		s = findspan(spans[y],x);
#endif
	return s->x_start;
}

int span_readlen(void *si,int x,int y)
{
	span *s;
	if ((x < 0) || (x >= span_width) || (y < 0) || (y >= span_lines))
		return 0;
#ifdef TREE
	if (si)
		s = findspan(((_spanset *) si)->nodes[y],x);
	else
		s = findspan(nodes[y],x);
#else
	if (si)
		s = findspan(((_spanset *) si)->spans[y],x);
	else
		s = findspan(spans[y],x);
#endif
#ifdef PARANOID
	if (s->next == 0)
	{
		warning("s->next == 0 in span_readlen (%d)",span_width);
		return span_width - s->x_start; /* Return distance to last span */
	}
#endif
	return s->next->x_start - s->x_start; /* s->next should exist since the last span is protected from being read */
}

/* Span insertion */

#define MIN(a,b) ((a) < (b) ? (a) : (b))
#define MAX(a,b) ((a) > (b) ? (a) : (b))

/* return a copy of src at x, linked with 'prev' as its predecessor */
static span *copyof_prev(span *src,span *prev,int x)
{
	register span *s;
#ifdef TREE
	register node *n,*newb;
#endif
	s = allocspan();
	s->x_start = x;
	s->iz_start = ZAT(src,x);
	s->iz_grad = src->iz_grad;
	s->col = src->col;
	s->id = src->id;
	s->next = prev->next;
	prev->next = s;
#ifdef TREE
	s->prev = prev;
	s->next->prev = s;
	/* Link it into the tree which prev is part of */
	n = prev->parent;
	/* We need to climb until n contains x, i.e. n->pos + n->twiddle*2 > x */
	while (n->pos + n->twiddle*2 <= x)
		n = n->parent;
	/* Then descend and insert as per usual */
	while ((x & n->mask) == n->pos) /* While we're still on track... */
	{
		if (n->twiddle == 1)
		{
			if (x & 1)
				n->one = s;
			else
				n->zero = s;
			s->parent = n;
			return s;
		}
		if (x & n->twiddle)
			n = (node *) n->one;
		else
			n = (node *) n->zero;
	}
	/* Insert new branch, above n */
	newb = allocnode();
	newb->parent = n->parent;
	if (n->parent->one == n) /* n should always have a parent */
		n->parent->one = newb; /* Relink n's parent to point to newb instead of n */
	else
		n->parent->zero = newb;
	n->parent = newb; /* Relink n to be below newb */
	newb->mask = n->mask; /* Copy initial position info */
	newb->twiddle = n->twiddle;
	newb->pos = n->pos;
	while ((x & newb->mask) != (newb->pos & newb->mask)) /* Widen newb until x fits */
	{
		newb->twiddle *= 2;
		newb->mask ^= newb->twiddle;
	}
	newb->pos &= newb->mask;
	/* Give newb its children */
	if (n->pos & newb->twiddle)
	{
		newb->one = n;
		newb = newb->zero = allocnode();
	}
	else
	{
		newb->zero = n;
		newb = newb->one = allocnode();
	}
	/* Now fill in the new newb with a terminating branch */
	newb->parent = n->parent; /* AKA original newb */
	newb->mask = ~1;
	newb->twiddle = 1;
	newb->pos = x & ~1;
	if (x & 1)
	{
		newb->zero = 0;
		newb->one = (void *) s;
	}
	else
	{
		newb->one = 0;
		newb->zero = (void *) s;
	}
	s->parent = newb;
#endif
	return s;
}

#ifdef TREE
static void removespan(span *s)
{
	/* Remove s from the tree and delete it
	   Must only be called if there are spans before and after s */
	register node *n,*r,*p,*sv;
	n = s->parent;
	s->next->prev = s->prev;
	s->prev->next = s->next;
	freespan(s);
	if (n->zero == s)
	{
		if (n->one)
		{
			n->zero = 0;
			return;
		}
		/* ... else continue and delete node */
	}
	else
	{ /* Must be n->one */
		if (n->zero)
		{
			n->one = 0;
			return;
		}
	}
	/* If we've reached here, then n and its parent needs removing */
	/* This might cause problems if the root node is r
	   But is this possible?
	   No, the tree must be 3 layers deep in order for removespan to be called to delete a node */
	r = n->parent; /* r = remove node */
	p = r->parent; /* p = parent of remove node */
	if (r->one == n)
		sv = r->zero; /* Survivor of r */
	else
		sv = r->one;
	if (p->one == r) /* Work out which bit of p to relink */
		p->one = sv;
	else
		p->zero = sv;
	sv->parent = p;
	freenode(n);
	freenode(r);
}
#else
static void removenextspan(span *s)
{
	/* remove the span after s from the tree */
	span *sn;
	sn = s->next;
	s->next = sn->next;
	freespan(sn);
}
#endif

static int add_span_returncode;

static inline void linear_insert(span *s,span *sn,int in_xe)
{
	register int xe; /* X end we are interested in */
	register span *ns; /* Next span to play with */
	register span *wasus; /* Was the last span part of the insertion span? */
	/* Insert s into the tree sn is in, by traversing the linear span list
	   sn should already be the span which s starts in */
	/* Handle the initial span if sn->x_start != s->x_start */
	wasus = 0;
	if (sn->x_start != s->x_start)
	{
#ifdef DEBUG
		printf("I");
#endif
		ns = sn->next;
		xe = MIN(in_xe,ns->x_start-1);
#ifdef DEPTHCHECKS
		if (ZAT(sn,s->x_start) < s->iz_start)
		{
#endif
			/* Left edge infront */
			copyof_prev(s,sn,s->x_start);
			add_span_returncode = SPAN_OK;
#ifdef DEPTHCHECKS
			if (ZAT(sn,xe) < ZAT(s,xe)) /* Right edge infront? */
				xe++; /* Return to sn here */
			else
				xe = (gen_move2d(s->iz_start - ZAT(sn,s->x_start),s->x_start << 16,ZAT(s,xe) - ZAT(sn,xe),xe << 16,0) >> 16) + 1; /* .. else return to sn here */
#else
			xe++;
#endif
			if (xe < ns->x_start)
				copyof_prev(sn,sn->next,xe); /* Resume sn */
			else
				wasus = sn->next; /* Set wasus to point to the inserted span */
#ifdef DEPTHCHECKS
		}
		else if (ZAT(sn,xe) < ZAT(s,xe)) /* Right edge infront? */
		{
			copyof_prev(s,sn,(gen_move2d(s->iz_start - ZAT(sn,s->x_start),s->x_start << 16,ZAT(s,xe) - ZAT(sn,xe),xe << 16,0) >> 16) + 1); /* Insert s at the appropriate place */
			add_span_returncode = SPAN_OK;
			if (xe < ns->x_start)
				copyof_prev(sn,sn->next,xe); /* Resume sn */
			else
				wasus = sn->next;
		}
#endif
		s->iz_start = ZAT(s,ns->x_start);
		s->x_start = ns->x_start;
		sn = ns;
	}
	/* Now merge the list with s, until sn->x_start > in_xe */
	while (sn->x_start <= in_xe)
	{
#ifdef DEBUG
		printf("M");
#endif
		ns = sn->next;
		xe = MIN(in_xe,ns->x_start-1);
#ifdef DEPTHCHECKS
		if (sn->iz_start < s->iz_start)
		{
			/* Left edge infront */
			if (ZAT(sn,xe) < ZAT(s,xe)) /* Right edge infront? */
				xe++;
			else
				xe = (gen_move2d(s->iz_start - sn->iz_start,s->x_start << 16,ZAT(s,xe) - ZAT(sn,xe),xe << 16,0) >> 16) + 1;
#else
			xe++;
#endif
			if (xe < ns->x_start)
				copyof_prev(sn,sn,xe); /* Must resume sn afterwards */
			/* Now overwrite sn with s */
			if (wasus)
#ifdef TREE
				removespan(sn); /* Don't duplicate existing efforts */
#else
				removenextspan(wasus);
#endif
			else
			{
				sn->iz_start = s->iz_start;
				sn->iz_grad = s->iz_grad;
				sn->col = s->col;
				sn->id = s->id;
				add_span_returncode = SPAN_OK;
			}
			if (xe < ns->x_start)
				wasus = 0;
			else if (wasus == 0)
				wasus = sn;
#ifdef DEPTHCHECKS
		}
		else if (ZAT(sn,xe) < ZAT(s,xe)) /* Right edge infront? */
		{
			copyof_prev(s,sn,(gen_move2d(s->iz_start - sn->iz_start,s->x_start << 16,ZAT(s,xe) - ZAT(sn,xe),xe << 16,0) >> 16) + 1); /* Insert s at the appropriate place */
			add_span_returncode = SPAN_OK;
			if (xe < ns->x_start)
			{
				copyof_prev(sn,sn->next,xe); /* Resume sn */
				wasus = 0;
			}
			else
				wasus = sn->next;
		}
		else
			wasus = 0; /* Hard to be us if we weren't even there */
#endif
		s->iz_start = ZAT(s,ns->x_start);
		s->x_start = ns->x_start;
		sn = ns;
	}
}

int span_add(int in_xs,int in_xe,invz in_izs,invz in_izg,int col,int y)
{
	span s;
	if (in_xe < in_xs)
		return SPAN_OCCLUDED; /* Or WRONGWAYROUND? */
#ifdef PARANOID
	if ((in_xs < 0) || (in_xs >= span_width))
	{
		warning("Bad span x start: %d,%d,%d,%d,%d,%d",in_xs,in_xe,in_izs,in_izg,col,y);
		return SPAN_OCCLUDED;
	}
	else if (in_xe >= span_width)
	{
		warning("Bad span x end: %d,%d,%d,%d,%d,%d",in_xs,in_xe,in_izs,in_izg,col,y);
		return SPAN_OCCLUDED;
	}
	else if ((y < 0) || (y >= span_lines))
	{
		warning("Bad span y: %d,%d,%d,%d,%d,%d",in_xs,in_xe,in_izs,in_izg,col,y);
		return SPAN_OFFSCREEN;
	}
#endif
	/* Right, you orrible maggot... */
	add_span_returncode = SPAN_OCCLUDED; /* Set to OK whenever something makes it through */
	s.x_start = in_xs;
	s.iz_start = in_izs;
	s.iz_grad = in_izg;
	s.col = col;
	s.id = span_id;
	/* Dump the span to stderr so another prog can feed it back in */
#ifdef DUMP
	fprintf(stderr,"%d\t%d\t%08x\t%08x\t%08x\t%d\n",in_xs,in_xe,in_izs,in_izg,col,y);
#endif
#ifdef DEBUG
	printf("{");
#endif
#ifdef TREE
	linear_insert(&s,findspan(nodes[y],in_xs),in_xe);
#else
	linear_insert(&s,findspan(spans[y],in_xs),in_xe);
#endif
#ifdef DEBUG
	printf("}");
#endif
	return add_span_returncode;
}

#ifdef TREE
void recurse_dump(node *n)
{
	if (n == 0)
		return;
	printf("node\t%08x:\n",(int) n);
	printf("\tmask\t%08x (%d)\n",n->mask,n->mask);
	printf("\ttwiddle\t%08x (%d)\n",n->twiddle,n->twiddle);
	printf("\tpos\t%08x (%d)\n",n->pos,n->pos);
	printf("\tzero\t%08x\n",(int) n->zero);
	printf("\tone\t%08x\n",(int) n->one);
	printf("\tparent\t%08x\n",(int) n->parent);
	if (n->twiddle != 1)
	{
		recurse_dump(n->zero);
		recurse_dump(n->one);
	}
}
#endif

void dumptree(int y)
{
	span *s;
#ifdef TREE
	node *n;
	recurse_dump(nodes[y]);
	n = nodes[y];
	while (n->twiddle != 1)
		n = (node *) n->zero;
	s = (span *) n->zero;
#else
	s = spans[y];
#endif
	while (s)
	{
		printf("span\t%08x:\n",(int) s);
		printf("\tx_start\t%08x (%d)\n",s->x_start,s->x_start);
		printf("\tz_start\t%08x (%.2f)\n",s->iz_start,f1616_ToFloat(INVZ_TO_F16(s->iz_start)));
		printf("\tiz_grad\t%08x\n",s->iz_grad);
		printf("\tcol\t%08x\n",s->col);
		printf("\tid\t%d\n",s->id);
		printf("\tnext\t%08x\n",(int) s->next);
#ifdef TREE
		printf("\tprev\t%08x\n",(int) s->prev);
		printf("\tparent\t%08x\n",(int) s->parent);
#endif
		s = s->next;
	}
}

#endif
