/*	Copyright (C) 1990 Free Software Foundation, Inc.

This file is part of Oleo, the GNU Spreadsheet.

Oleo 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 1, or (at your option)
any later version.

Oleo 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 Oleo; see the file COPYING.  If not, write to
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */

#include "funcdef.h"

#include <stdio.h>

#define obstack_chunk_alloc ck_malloc
#define obstack_chunk_free free
#include "obstack.h"

#include "sysdef.h"

#include "global.h"
#include "cell.h"

/* How many rows/columns to allocate to either side of an allocated cell */
#ifdef __TURBOC__
#define ROW_BUFF	0
#define COL_BUFF	0
#else
#define ROW_BUFF	4
#define COL_BUFF	2
#endif

#ifdef REVERSE
#define MIN_R MIN_COL
#define MAX_R MAX_COL
#define MIN_C MIN_ROW
#define MAX_C MAX_ROW
#else
#define MIN_R MIN_ROW
#define MAX_R MAX_ROW
#define MIN_C MIN_COL
#define MAX_C MAX_COL
#endif

extern void byte_free EXT1(unsigned char *);
extern void flush_variables EXT0();

typedef struct col COL;
typedef struct row ROW;

/* Cells are stored in a two-dimentional sparse array.  This allows us to have
   a fair-sized namespace (255x255 or 65535x65535) without using incredible
   amounts of memory.  (64Kx64K cells would use up 120GIG of memory just for
   the cell structures. . .)

   Note that the sparse arrays are not currently garbage collected, although
   flush_everything will free all the row and column structures, as well
   as everything in them. . .
 */
struct row {
	ROW *row_next;
	CELLREF	row_low;
	CELLREF	row_high;
	COL *cols[1];
};

static ROW *the_rows;

struct col {
	struct col *col_next;
	CELLREF	col_low;
	CELLREF	col_high;
	CELL cells[1];
};

static ROW *make_row_at EXT3(CELLREF, ROW *, ROW **);
static ROW *row_alloc EXT3N(CELLREF, CELLREF, ROW *);

static void out_of_date EXT0();

static COL *col_alloc EXT3N(CELLREF, CELLREF, COL *);

extern CELL *my_cell;
extern CELLREF cur_row,cur_col;

#define row_free(x)	out_of_date(),free(x)
#define col_free(x)	\
	do{\
		out_of_date();\
		if(   my_cell \
 		   && my_cell>= &(x->cells[0]) \
 		   && my_cell<=&(x->cells[x->col_high-x->col_low])) \
		   	my_cell=find_cell(cur_row,cur_col); \
		free(x); \
	} while (0)

#define MIN(x,y)	((x)<(y) ? (x) : (y))
#define MAX(x,y)	((x)>=(y) ? (x) : (y))

/* find_cell() returns a pointer to a cell at 'row', 'col'.  If there is no
   cell currently allocated there, it returns 0. */

CELL *
find_cell FUN2(CELLREF, row, CELLREF, col)
{
	ROW *row_ptr;
	COL *col_ptr;

#ifdef REVERSE
	CELLREF tmp;

	tmp=row;
	row=col;
	col=tmp;
#endif
#ifdef TEST
	if(row<MIN_R || row>MAX_R || col<MIN_C || col>MAX_C)
		panic("%u,%u out of range in find_cell",row,col);
#endif

	for(row_ptr=the_rows;row_ptr;row_ptr=row_ptr->row_next) {
		if(row_ptr->row_low<=row && row_ptr->row_high>=row)
			break;
		if(row_ptr->row_low>row) {
			row_ptr=0;
			break;
		}
	}
	if(!row_ptr)
		return 0;

	for(col_ptr=row_ptr->cols[row-row_ptr->row_low];col_ptr;col_ptr=col_ptr->col_next) {
		if(col_ptr->col_low<=col && col_ptr->col_high>=col)
			break;
		if(col_ptr->col_low>col) {
			col_ptr=0;
			break;
		}
	}

	if(!col_ptr)
		return 0;
	return &(col_ptr->cells[col-col_ptr->col_low]);
}

/* find_or_make_cell() is like find_cell(), except that if there is no cell
   allocated there, it allocates one.  It should never return zero. */

CELL *
find_or_make_cell FUN2(CELLREF, row, CELLREF, col)
{
	ROW *row_ptr;

	COL *col_ptr;
	COL **col_prev;
#ifdef REVERSE
	CELLREF tmp;

	tmp=row;
	row=col;
	col=tmp;
#endif
#ifdef TEST
	if(row<MIN_R || row>MAX_R || col<MIN_C || col>MAX_C)
		panic("%u,%u out of range in find_or_make_cell",row,col);
#endif

	row_ptr=make_row_at(row,the_rows,&the_rows);

	/* cdr down the list of cols until we find the one we want */
	col_prev= &(row_ptr->cols[row-row_ptr->row_low]);
	for(col_ptr= *col_prev;col_ptr;col_ptr= *col_prev) {

		/* Have we found the right place? */
		if(col_ptr->col_low<=col && col_ptr->col_high>=col)
			break;

		if(col_ptr->col_low>col) {
			/* We've cdr'd past the place in the list where
			   the column goes */
			if(col_ptr->col_low>col+COL_BUFF+1) {
				/* There isn't anything nearby. */
				col_ptr=0;
			} else {
				int new_low;
				int old_num_cols;
				COL *new_col;

				/* Grow the column structure down a bit so
				   that this column will fit in it */
				new_low=col-COL_BUFF;
				if(new_low<MIN_C)
					new_low=MIN_C;
				old_num_cols=1+col_ptr->col_high-col_ptr->col_low;

				new_col=col_alloc(new_low,
						col_ptr->col_high,
						col_ptr->col_next,

						old_num_cols,
						col_ptr->col_low,
						&(col_ptr->cells[0]),

						0);

				*col_prev=new_col;

				col_free(col_ptr);
				col_ptr=new_col;
			}
			break;
		}
		if(col_ptr->col_high+COL_BUFF+1>=col) {
			/* The column doesn't fit in the current
			   col structure, but it can be made to by stretching
			   or by merging two col structures.
			   So do it. */
			if(col_ptr->col_next && col_ptr->col_next->col_low<=col+COL_BUFF+1) {
				/* This col structure is close enough to the
				   next one that they should just be merged */
				COL *the_next;
				COL *new_col;

				the_next=col_ptr->col_next;
				if(the_next->col_low<=col) {
					col_ptr=the_next;
					break;
				}

				new_col=col_alloc(col_ptr->col_low,
						the_next->col_high,
						the_next->col_next,

						1+col_ptr->col_high-col_ptr->col_low,
						col_ptr->col_low,
						&(col_ptr->cells[0]),

						1+the_next->col_high-the_next->col_low,
						the_next->col_low,
						&(the_next->cells[0]),

						0);

				*col_prev=new_col;

				col_free(col_ptr);
				col_free(the_next);
				col_ptr=new_col;
			} else {
				int new_high;
				COL *new_col;

				/* Stretch the col structure a little */
				if(col>MAX_C-COL_BUFF)
					new_high=MAX_C;
				else
					new_high=col+COL_BUFF;

				new_col=col_alloc(col_ptr->col_low,
						new_high,
						col_ptr->col_next,

						1+col_ptr->col_high-col_ptr->col_low,
						col_ptr->col_low,
						&(col_ptr->cells[0]),

						0);

				*col_prev=new_col;

				col_free(col_ptr);
				col_ptr=new_col;
			}
			break;
		}
		col_prev= &(col_ptr->col_next);
	}
	if(!col_ptr) {
		/* We couldn't find any columns.  Create some */

		if(col<MIN_C+COL_BUFF)
			col_ptr=col_alloc(MIN_C,
					col+COL_BUFF,
					*col_prev,

					0);
		else if(col>MAX_C-COL_BUFF)
			col_ptr=col_alloc(col-COL_BUFF,
					MAX_C,
					*col_prev,

					0);
		else
			col_ptr=col_alloc(col-COL_BUFF,
					col+COL_BUFF,
					*col_prev,

					0);
		*col_prev= col_ptr;
	}

	return &(col_ptr->cells[col-col_ptr->col_low]);
}

/* These two return the maximum row/column allocated at the given column/row
   Because of the way the sparse array works, one of them will return the
   same value for all possible inputs.
 */
   
CELLREF
#ifdef REVERSE
max_col FUN1(CELLREF, row)
#else
max_row FUN1(CELLREF, col)
#endif
{
	ROW *rr;

	if(!the_rows)
		return MIN_R;
	for(rr=the_rows;rr->row_next;rr=rr->row_next)
		;
	return rr->row_high;
}

CELLREF
#ifdef REVERSE
max_row FUN1(CELLREF, row)
#else
max_col FUN1(CELLREF, row)
#endif
{
	ROW *rr;
	COL *cc;

	if(!the_rows)
		return MIN_C;
	for(rr=the_rows;rr;rr=rr->row_next)
		if(rr->row_low<=row && rr->row_high>=row)
			break;
	if(!rr)
		return MIN_C;
	for(cc=rr->cols[row-rr->row_low];cc && cc->col_next;cc=cc->col_next)
		;
	if(!cc)
		return MIN_C;
	return cc->col_high;
}

/* These two return the highest row/column allocated anywhere in the
   spreadsheet.  One of them is easy to find, but the other requires scanning
   the entire sparse array
 */
CELLREF
#ifdef REVERSE
highest_col FUN0()
#else
highest_row FUN0()
#endif
{
	ROW *rr;

	if(!the_rows)
		return MIN_R;
	for(rr=the_rows;rr->row_next;rr=rr->row_next)
		;
	return rr->row_high;
}

CELLREF
#ifdef REVERSE
highest_row FUN0()
#else
highest_col FUN0()
#endif
{
	CELLREF ret;
	int n;
	ROW *rr;
	COL *cc;

	if(!the_rows)
		return MIN_C;
	ret=MIN_C;
	for(rr=the_rows;rr;rr=rr->row_next) {
		for(n=0;n<rr->row_high-rr->row_low;n++) {
			for(cc=rr->cols[n];cc && cc->col_next;cc=cc->col_next)
				;
			if(cc && cc->col_high>ret)
				ret=cc->col_high;
		}
	}
	return ret;
}

/* This is a complicated function.  It takes four or more args.
   The first three are
   The lowest row value we should create
   The highest row value we should create
   the next row structure in the list
   and groups of
     how many col ptrs are in this group (N_IN)
     what row value this group starts at (ROW_IN)
     and a pointer to an array of struct col *s (COL_IN)
   The groups end with a (partial) group whose N_IN is zero
 */

static ROW *
row_alloc FUN3N(CELLREF,r_low,CELLREF,r_high,ROW *,r_next)
{
	ROW *ret;
	int	num_rows;
	int	our_row;
	COL **colp;
	int	n_in;
	int	row_in;
	COL **col_in;
	va_list args;

#ifdef TEST
	if(r_next && r_next->row_low==r_high+1)
		error_msg("Warning: Consecutive rows allocated");
#endif
	out_of_date();
	num_rows=1+r_high-r_low;
	ret=(ROW *)ck_malloc(sizeof(ROW)+(num_rows-1)*sizeof(ROW *));
	ret->row_low=r_low;
	ret->row_high=r_high;
	ret->row_next=r_next;

/*  printf("row_alloc(%d,%d,%d,",r_low,r_high,r_next); */
	var_start(args,r_next);
	our_row=r_low;
	colp= &(ret->cols[0]);
	while(n_in=va_arg(args,int)) {
		row_in=va_arg(args,/* CELLREF */ int);
		while(our_row<row_in) {
			our_row++;
			*colp++=0;
		}
		col_in=(COL **)va_arg(args,COL **);
/*  printf(" %d,%d,%d,",n_in,row_in,col_in); */
		while(n_in--) {
			our_row++;
			*colp++ = *col_in++;
		}
	}
	while(our_row++<=r_high)
		*colp++=0;
/*  printf("0)\n"); */
	va_end(args);

	return ret;
}

/* This is like row_alloc(), but it allocates columns instead */
static COL *
col_alloc FUN3N(CELLREF,c_low,CELLREF,c_high,COL *,c_next)
{
	COL *ret;
	int	num_cols;
	int	our_col;
	CELL	*cellp;
	int	n_in;
	int	col_in;
	CELL	*cell_in;
	va_list args;

#ifdef TEST
	if(c_next && c_next->col_low==c_high+1)
		error_msg("Warning: Consecutive cols allocated");
#endif
	out_of_date();
	num_cols=1+c_high-c_low;
	ret=(COL *)ck_malloc(sizeof(COL)+(num_cols-1)*sizeof(CELL));
	ret->col_low=c_low;
	ret->col_high=c_high;
	ret->col_next=c_next;

/*  printf("col_alloc(%d,%d,%d,",c_low,c_high,c_next); */
	var_start(args,c_next);
	our_col=c_low;
	cellp= &(ret->cells[0]);
	while(n_in=va_arg(args,int)) {
		col_in=va_arg(args,/* CELLREF */ int);
		while(our_col<col_in) {
			our_col++;
			/* cellp->cell_string=0; */
			cellp->cell_refs_from=0;
			cellp->cell_refs_to=0;
			cellp->cell_cycle=0;
			cellp->cell_formula=0;
			cellp++->cell_flags=0;
		}
		cell_in=(CELL *)va_arg(args,CELL *);
/*  printf(" %d,%d,%d,",n_in,col_in,cell_in); */
		bcopy(cell_in,cellp,n_in*sizeof(CELL));
		our_col+=n_in;
		cellp+=n_in;
	}

/*  printf(" 0)\n"); */
	while(our_col++<=c_high) {
		/* cellp->cell_string=0; */
		cellp->cell_refs_from=0;
		cellp->cell_refs_to=0;
		cellp->cell_cycle=0;
		cellp->cell_formula=0;
		cellp++->cell_flags=0;
	}

	return ret;
}

/* This function returns a pointer to a row structure that has a row defined
   at ROW.  PREVP points to a row structure somewhere before ROW.  PREVPP
   points to the place where the pointer to PREVP is stored (for use if
   we have to realloc(PREVP,...) */
static ROW *
make_row_at FUN3(CELLREF,row,ROW *,prevp,ROW **,prevpp)
{
	ROW *postp;
	ROW *new_row;
	CELLREF rowhi,rowlo;

	while(prevp && prevp->row_next && prevp->row_next->row_low < row) {
		prevpp = &(prevp->row_next);
		prevp=prevp->row_next;
	}

	if(prevp && prevp->row_low<=row && prevp->row_high>=row)
		return prevp;

	rowhi= (row>MAX_R-ROW_BUFF) ? MAX_R : row+ROW_BUFF;
	rowlo= (row<MIN_R+ROW_BUFF) ? MIN_R : row-ROW_BUFF;

	if(   !prevp
 	   || (    prevp->row_high < rowlo-1
	       && (!prevp->row_next || prevp->row_next->row_low-1>rowhi))) {

		/* There's no row structure there.  Therefore, create one */
		new_row=row_alloc(rowlo,
				rowhi,
				prevp ? prevp->row_next : *prevpp,

				0);
		if(prevp)
			prevp->row_next=new_row;
		else
			*prevpp=new_row;
		return new_row;
	}

	if(prevp->row_high+1>=rowlo) {
		if(prevp->row_next && prevp->row_next->row_low-1<=rowhi) {
			/* This row is (nearly) midway between two row
			   structures.  Merge them */
			postp=prevp->row_next;
			new_row=row_alloc(prevp->row_low,
					postp->row_high,
					postp->row_next,

					1+prevp->row_high-prevp->row_low,
					prevp->row_low,
					&(prevp->cols[0]),

					1+postp->row_high-postp->row_low,
					postp->row_low,
					&(postp->cols[0]),

					0);

			*prevpp=new_row;

			row_free(prevp);
			row_free(postp);
			return new_row;
		} else if(prevp->row_low>rowlo) {
			/* The first row struct must be stretched up a bit */
			new_row=row_alloc(rowlo,prevp->row_high,prevp->row_next,
					1+prevp->row_high-prevp->row_low,
					prevp->row_low,
					&(prevp->cols[0]),

					0);
			*prevpp=new_row;
			row_free(prevp);
			return new_row;
		} else {
			/* This row is just past the end of a row
			   structure.  Stretch the structure a bit so
			   that it'll fit */
			new_row=row_alloc(prevp->row_low,
					rowhi,
					prevp->row_next,

					1+prevp->row_high-prevp->row_low,
					prevp->row_low,
					&(prevp->cols[0]),

					0);

			*prevpp=new_row;

			row_free(prevp);
			return new_row;
		}
	}

	if(prevp->row_next && prevp->row_next->row_low-1<=rowhi) {
		/* Grow the old row_structure down just a
		   little so that this one will fit in it */
		prevpp= &(prevp->row_next);
		postp=prevp->row_next;

		new_row=row_alloc(rowlo,
				postp->row_high,
				postp->row_next,

				1+postp->row_high-postp->row_low,
				postp->row_low,
				&(postp->cols[0]),

				0);

		*prevpp=new_row;

		row_free(postp);
		return new_row;
	}
#ifdef TEST
	if(prevp->row_low<row || prevp->row_high>row)
		panic("Make row at: %u not in %u %u",row,prevp->row_low,prevp->row_high);
#endif
	return prevp;
}


/* The next group of routines deal with finding groups of cells in the
   spreadsheet.  They should be smart enough to deal with the spreadsheet
   changing under them.  */
struct find {
	CELLREF lr,lc,hr,hc;
	CELLREF cr,cc;
	int flags;

	ROW *nowrow;
	COL **colpptr;
	COL *nowcol;
	int colsleft;
	CELL *nowcell;
	int cellsleft;
	struct find *next;
};
static struct find *f;
static struct obstack find_stack;

void
init_cells FUN0()
{
	obstack_begin(&find_stack,sizeof(struct find)*15);
}

/* This sets things up so that the next gzillion calls to next_cell_in_range()
   will return one of the cells in the region delineated by RNG.  If
   This will skip over any gaps in the region, but will return zeroed cells
   in the region.  If there are no cells in the region, the first call to
   next_cell_in_range() will return 0
 */
void
find_cells_in_range FUN1(struct rng *,rng)
{
	struct find *oldf;
#ifdef REVERSE
#define	LR	rng->lc
#define LC	rng->lr
#define HR	rng->hc
#define HC	rng->hr
#else
#define LR	rng->lr
#define LC	rng->lc
#define HR	rng->hr
#define HC	rng->hc
#endif
#ifdef TEST
	if(   LR<MIN_R || LR>MAX_R || HR<MIN_R || HR>MAX_R
	   || LC<MIN_C || LC>MAX_C || HC<MIN_C || HC>MAX_C)
		panic("find_cells_in_range(%u:%u %u:%u) out of range",LR,HR,LC,HC);
#endif

	oldf=f;
	f=obstack_alloc(&find_stack,sizeof(struct find));
	bzero(f,sizeof(struct find));
	f->next=oldf;
	f->lr=LR;
	f->hr=HR;
	f->lc=LC;
	f->hc=HC;
	for(f->nowrow=the_rows;f->nowrow;f->nowrow=f->nowrow->row_next)
		if(f->nowrow->row_high>=f->lr)
			break;
	while(f->nowrow && f->nowrow->row_low<=f->hr) {
		f->cr=f->lr<=f->nowrow->row_low ? f->nowrow->row_low : f->lr;
		f->colpptr= &(f->nowrow->cols[f->cr-f->nowrow->row_low]);
		f->colsleft=1+MIN(f->hr,f->nowrow->row_high)-f->cr;
		while(f->colsleft) {
			--(f->colsleft);
			f->nowcol= *(f->colpptr)++;
			while(f->nowcol && f->nowcol->col_high<f->lc)
				f->nowcol=f->nowcol->col_next;
			if(f->nowcol && f->nowcol->col_low<=f->hc) {
				/* Found something */
				f->cc=(f->lc<f->nowcol->col_low) ? f->nowcol->col_low : f->lc;
				f->nowcell= &(f->nowcol->cells[f->cc-f->nowcol->col_low]);
				f->cellsleft=1+MIN(f->hc,f->nowcol->col_high)-f->cc;
				--(f->cc);
#ifdef TEST
				if(f->cellsleft<1)
					panic("Cellsleft %d<1",f->cellsleft);
#endif
				f->flags=0;
				return;
			}
			(f->cr)++;
		}
		f->nowrow=f->nowrow->row_next;
	}
	/* If we get here, we searched through the entire range, and didn't
	   find *any* cells.  We lose */
	f->flags=1;
}

/* This is like find_cells_in_range, except that if the cells don't exist,
   it makes them! */
void
make_cells_in_range FUN1(struct rng *,rng)
{
	ROW **prevpp;
	ROW *myrow;
	int n;
	COL **colpp;
	COL *mycol;
	struct find *oldf;
	CELLREF lr,hr,lc,hc;

#ifdef TEST
	if(   LR<MIN_R || LR>MAX_R || HR<MIN_R || HR>MAX_R
	   || LC<MIN_C || LC>MAX_C || HC<MIN_C || HC>MAX_C)
		panic("make_cells_in_range(%u:%u %u:%u) out of range",LR,HR,LC,HC);
#endif
	oldf=f;
	f=obstack_alloc(&find_stack,sizeof(struct find));
	bzero(f,sizeof(struct find));
	f->next=oldf;
	f->lr=LR;
	f->lc=LC;
	f->hr=HR;
	f->hc=HC;

	f->colsleft=f->hr-f->lr;
	f->cr=f->lr;
	f->cellsleft=1+f->hc-f->lc;
	f->cc=f->lc-1;

	lr= f->lr<=MIN_R+ROW_BUFF ? MIN_R : f->lr-ROW_BUFF;
	hr= f->hr>=MAX_R-ROW_BUFF ? MAX_R : f->hr+ROW_BUFF;

	if(!the_rows) {
		myrow=the_rows=row_alloc(lr,hr,0,0);
	} else {
		myrow=the_rows;
		prevpp= &the_rows;
		while(myrow && myrow->row_high<lr-1) {
			prevpp= &(myrow->row_next);
			myrow=myrow->row_next;
		}
		if(!myrow || myrow->row_low-1>hr)
			myrow= *prevpp=row_alloc(lr,hr,myrow,0);
		else if(myrow->row_high<hr) {
			ROW *t1,*t2;

			while(myrow->row_high<hr && myrow->row_next && myrow->row_next->row_low<=hr+1) {
				t1=myrow;
				t2=myrow->row_next;
				myrow= *prevpp=row_alloc(t1->row_low,t2->row_high,t2->row_next,
							1+t1->row_high-t1->row_low,t1->row_low,&(t1->cols[0]),
							1+t2->row_high-t2->row_low,t2->row_low,&(t2->cols[0]),
							0);
				row_free(t1);
				row_free(t2);
			}
			if(myrow->row_high<hr) {
				t1=myrow;
				myrow= *prevpp=row_alloc(t1->row_low,hr,t1->row_next,
							1+t1->row_high-t1->row_low,t1->row_low,&(t1->cols[0]),
							0);
				row_free(t1);
			}
		} else if(myrow->row_low>lr) {
			ROW *t1;

			t1=myrow;
			myrow= *prevpp=row_alloc(lr,t1->row_high,t1->row_next,
						1+t1->row_high-t1->row_low,t1->row_low,&(t1->cols[0]),
						0);
			row_free(t1);
		}
	}
#ifdef TEST
	if(myrow->row_low>f->lr || myrow->row_high<f->hr)
		panic("Myrow isn't big enough");
#endif
	lc= f->lc<=MIN_C+COL_BUFF ? MIN_C : f->lc-COL_BUFF;
	hc= f->hc>=MAX_C-COL_BUFF ? MAX_C : f->hc+COL_BUFF;

	for(n=lr-myrow->row_low;n<=hr-myrow->row_low;n++) {

		colpp= &(myrow->cols[n]);
		if(!*colpp) {
			*colpp=col_alloc(lc,hc,0,0);
		} else {
			for(mycol= *colpp;mycol;colpp= &(mycol->col_next),mycol= *colpp)
				if(mycol->col_high+1>=lc)
					break;
			if(!mycol || mycol->col_low>hc+1)
				*colpp=col_alloc(lc,hc,mycol,0);
			else if(mycol->col_low<=lc && mycol->col_high>=hc)
				;	/* Easy */
			else /* if(mycol->col_low>lc && mycol->col_high>hc) {
				COL *t1;

				t1=mycol;
				mycol= *colpp=col_alloc(lc,t1->col_high,t1->col_next,
							1+t1->col_high-t1->col_low,t1->col_low,&(t1->cells[0]),
							0);
				col_free(t1);
			} else */ {
				COL *t1,*t2;

				while(mycol->col_high<=hc+1
 				      && mycol->col_next
 				      && mycol->col_next->col_low<=hc+1) {
					t1=mycol;
					t2=mycol->col_next;
					mycol= *colpp=col_alloc(MIN(lc,t1->col_low),t2->col_high,t2->col_next,
								1+t1->col_high-t1->col_low,t1->col_low,&(t1->cells[0]),
								1+t2->col_high-t2->col_low,t2->col_low,&(t2->cells[0]),
								0);
					col_free(t1);
					col_free(t2);
				}
				if(mycol->col_low>lc || mycol->col_high<hc) {
					t1=mycol;
					mycol= *colpp=col_alloc(MIN(lc,t1->col_low),MAX(hc,mycol->col_high),t1->col_next,
								1+t1->col_high-t1->col_low,t1->col_low,&(t1->cells[0]),
								0);
					col_free(t1);
				}
			}
		}
	}
	f->nowrow=myrow;
	f->colpptr= &(f->nowrow->cols[f->lr-f->nowrow->row_low]);
	f->nowcol= *(f->colpptr)++;
	while(f->nowcol->col_high<f->lc)
		f->nowcol=f->nowcol->col_next;
	f->nowcell= &(f->nowcol->cells[f->lc-f->nowcol->col_low]);

#ifdef TEST
	if(f->cellsleft<1)
		panic("Cellsleft %d<1",f->cellsleft);
#endif
	f->flags=0;
}

/* Return the next cell in the range previously selected by
   find_cells_in_range() or make_cells_in_range()  If row_alloc(),
   row_free(), col_alloc(), or col_free() has been called, re-sync to the
   current state of the spreadsheet. */

CELL *
next_cell_in_range FUN0()
{
	struct find *oldf;

#ifdef TEST
	if(!f)
		panic("No 'f' in next_cells_in_range!");
#endif
	if(f->flags) {
		if(f->flags&1) {
 done:
			oldf=f->next;
			(void)obstack_free(&find_stack,f);
			f=oldf;
			return 0;
		}
		f->flags=0;
		if(f->cr==f->hr && f->cc==f->hc)
			goto done;
		if(f->cc==f->hc) {	/* JF was f->cc=f->hc */
			f->cc=f->lc-1;
			(f->cr)++;
		}
		for(f->nowrow=the_rows;f->nowrow;f->nowrow=f->nowrow->row_next)
			if(f->nowrow->row_high>=f->cr)
				break;
		if(!f->nowrow)
			goto done;
		f->colpptr= &(f->nowrow->cols[f->cr-f->nowrow->row_low]);
		f->colsleft= 1+MIN(f->hr,f->nowrow->row_high)-f->cr;
		if(f->colsleft) {
			--(f->colsleft);
			f->nowcol= *(f->colpptr)++;
			while(f->nowcol && f->nowcol->col_high<f->cc)
				f->nowcol=f->nowcol->col_next;
			if(f->nowcol && f->nowcol->col_low<=f->cc) {
				(f->cc)++;
				f->nowcell= &(f->nowcol->cells[f->cc-f->nowcol->col_low]);
				f->cellsleft=1+MIN(f->hc,f->nowcol->col_high)-f->cc;
				--(f->cc);
			}
		}
	}

	if(f->cellsleft) {
#ifdef TEST
		if(f->cellsleft<1)
			panic("Cellsleft %d<1",f->cellsleft);
#endif
		--(f->cellsleft);
		(f->cc)++;
		return (f->nowcell)++;
	}

	/* There are no more cells in the current COL structure.  If there
	   might be cells in the next one, try there */
	if(f->nowcol->col_high<f->hc) {
		f->nowcol=f->nowcol->col_next;
		if(f->nowcol && f->nowcol->col_low<=f->hc) {
			f->nowcell= &(f->nowcol->cells[0]);
			f->cellsleft=MIN(f->hc,f->nowcol->col_high)-f->nowcol->col_low;
			f->cc=f->nowcol->col_low;
#ifdef TEST
			if(f->cellsleft<0)
				panic("Cellsleft %d<1",f->cellsleft);
#endif
			return (f->nowcell)++;
		}
	}
 try_cols:
	/* See if there are any more COLS in the current row structure
	   If there are, scan through them for useful cells.  */
	while(f->colsleft) {
		--(f->colsleft);
		(f->cr)++;
		f->nowcol= *(f->colpptr)++;
		while(f->nowcol && f->nowcol->col_high<f->lc)
			f->nowcol=f->nowcol->col_next;
		if(f->nowcol && f->nowcol->col_low<=f->hc) {	/* Found something */
			f->cc=f->lc<f->nowcol->col_low ? f->nowcol->col_low : f->lc;
			f->nowcell= &(f->nowcol->cells[f->cc-f->nowcol->col_low]);
			f->cellsleft=MIN(f->hc,f->nowcol->col_high)-f->cc;
#ifdef TEST
			if(f->cellsleft<0)
				panic("Cellsleft %d<1",f->cellsleft);
#endif
			return (f->nowcell)++;
		}
	}

	/* Have we run out of rows? */
	if(f->nowrow->row_high>=f->hr)
		goto done;

	/* Check in the next ROW structure.  There's nothing in this one */
	f->nowrow=f->nowrow->row_next;
	if(!f->nowrow || f->nowrow->row_low>f->hr)
		goto done;

	f->colpptr= &(f->nowrow->cols[0]);
	f->colsleft= 1 + MIN(f->hr,f->nowrow->row_high)-f->nowrow->row_low;
	f->cr=f->nowrow->row_low-1;
	goto try_cols;
}

/* This is a wrapper to next_cell_in_range that also returns (through
   PUTROW and PUTCOL information about where the cell actually *is*
 */
CELL *
next_row_col_in_range FUN2(CELLREF *,putrow, CELLREF *,putcol)
{
	CELL *nxt;

	nxt=next_cell_in_range();
	if(nxt) {
#ifdef REVERSE
		*putcol=f->cr;
		*putrow=f->cc;
#else
		*putrow=f->cr;
		*putcol=f->cc;
#endif
	} else {
		*putrow=MIN_R-1;
		*putcol=MIN_C-1;
	}
	return nxt;
}

/* This should be called if a function called {find,make}_cells_in_range()
   and wants to stop calling next_{cell,row_col}_in_range() before they
   encounter the end of the range */
void
no_more_cells FUN0()
{
	struct find *oldf;

	oldf=f->next;
	(void)obstack_free(&find_stack,f);
	f=oldf;
}

/* This is called by row_alloc and col_alloc to tell
   next_{cell,row_col}_in_range() that some part of the spreadsheet has
   changed.
 */
static void
out_of_date FUN0()
{
	struct find *tmpf;

	for(tmpf=f;tmpf;tmpf=tmpf->next)
		tmpf->flags|=2;
}

/* this is your basic trash-the-world function. */
void
flush_everything FUN0()
{
	ROW *rp,*rnxt;
	COL *cp,*cnxt;
	CELL *sp;

	int nrn;
#ifndef SPLIT_REFS
	extern void flush_refs();
#endif

	for(rp= the_rows;rp;rp=rnxt) {
		rnxt=rp->row_next;
		for(nrn=rp->row_low;nrn<=rp->row_high;nrn++) {
			for(cp= rp->cols[nrn-rp->row_low];cp;cp= cnxt) {
				cnxt=cp->col_next;
				for(sp= &(cp->cells[0]);sp<=&(cp->cells[cp->col_high-cp->col_low]);sp++) {
#ifdef SPLIT_REFS
					if(sp->cell_refs_from)
						free(sp->cell_refs_from);
					if(sp->cell_refs_to)
						free(sp->cell_refs_to);
#endif
					if(sp->cell_formula)
						byte_free(sp->cell_formula);
					if(GET_TYP(sp)==TYP_STR)
						free(sp->cell_str);
				}
				free(cp);
			}
		}
		free(rp);
		the_rows=0;
	}
	flush_variables();
#ifndef SPLIT_REFS
	flush_refs();
#endif
}

#ifdef TEST
extern char *bname[];
extern char *dbg_print_formula();
extern char *dbg_print_ref_fm();
extern char *dbg_print_ref_to();

extern char print_buf[];

extern char *bname[];

void dbg_print_cell();

/* These debugging functions store useful text about the sparse array
   in the buffer pointed to by BUF.  If it isn't big enough, you lose. */

void
dbg_print_rows FUN0()
{
	ROW *row_ptr;
	CELLREF n,maxx;
	char *buf;

	for(row_ptr=the_rows;row_ptr;row_ptr=row_ptr->row_next) {
		text_line("Row %p:  next %p, low %u, high %u",
			row_ptr,row_ptr->row_next,row_ptr->row_low,
			row_ptr->row_high);
		maxx=row_ptr->row_high-row_ptr->row_low;
		for(buf=print_buf,n=0;n<=maxx;n++) {
			(void)sprintf(buf," %p",row_ptr->cols[n]);
			if(n%8==7) {
				text_line(print_buf);
				buf=print_buf;
			} else
				buf+=strlen(buf);
		}
		if(n%8)
			text_line(print_buf);
	}
}

void
dbg_print_cols FUN1(CELLREF, row)
{
	ROW *row_ptr;
	COL *col_ptr;
	CELLREF maxc,nc;
	CELL *cp;
	char *buf;

	for(row_ptr=the_rows;row_ptr;row_ptr=row_ptr->row_next)
		if(row_ptr->row_low<=row && row_ptr->row_high>=row)
			break;
	if(!row_ptr)
		return;

	for(col_ptr=row_ptr->cols[row-row_ptr->row_low];col_ptr;col_ptr=col_ptr->col_next) {
		text_line("Col %p:  Next %p, low %u, high %u",
			col_ptr,col_ptr->col_next,col_ptr->col_low,
			col_ptr->col_high);
		maxc=col_ptr->col_high-col_ptr->col_low;

		for(cp= &(col_ptr->cells[0]),buf=print_buf,nc=0;nc<=maxc;nc++,cp++) {
			switch(GET_TYP(cp)) {
			case 0:
				(void)strcpy(buf,"         .");
				break;
			case TYP_FLT:
				(void)sprintf(buf," %8gf",cp->cell_flt);
				break;
			case TYP_INT:
				(void)sprintf(buf," %8ldi",cp->cell_int);
				break;
			case TYP_ERR:
				(void)sprintf(buf," %8.8se",ename[cp->cell_err]);
				break;
			case TYP_BOL:
				(void)sprintf(buf," %8sb",bname[cp->cell_bol]);
				break;
			case TYP_STR:
				(void)sprintf(buf," %8.8ss",cp->cell_str);
				break;
			default:
				(void)sprintf(buf," %8dU",GET_TYP(cp));
				break;
			}
			if(nc%8==7) {
				text_line(print_buf);
				buf=print_buf;
			} else
				buf+=strlen(buf);
		}
		if(nc%8)
			text_line(print_buf);
	}
}

void
dbg_print_array FUN0()
{
	int maxx;
	int nr;
	int maxc;
	int nc;
	COL *col_ptr;
	CELL *cp;
	ROW * row_ptr;
	char *buf;

	for(row_ptr=the_rows;row_ptr;row_ptr=row_ptr->row_next) {
		text_line("Row %p:  next %p, low %u, high %u",
			row_ptr,row_ptr->row_next,row_ptr->row_low,
			row_ptr->row_high);
		maxx=row_ptr->row_high-row_ptr->row_low;
		for(nr=0,buf=print_buf;nr<=maxx;nr++) {
			(void)sprintf(buf," %p",row_ptr->cols[nr]);
			if(nr%8==7) {
				text_line(print_buf);
				buf=print_buf;
			} else
				buf+=strlen(buf);
		}
		if(nr%8)
			text_line(print_buf);

		for(nr=0;nr<=maxx;nr++) {
			for(col_ptr=row_ptr->cols[nr];col_ptr;col_ptr=col_ptr->col_next) {
				text_line("Col %p:  Next %p, low %u, high %u",
					col_ptr,col_ptr->col_next,col_ptr->col_low,
					col_ptr->col_high);
				maxc=col_ptr->col_high-col_ptr->col_low;

				for(cp= &(col_ptr->cells[0]),buf=print_buf,nc=0;nc<=maxc;nc++,cp++) {
					(void)sprintf(buf," %p",cp);
					if(nc%8==7) {
						text_line(print_buf);
						buf=print_buf;
					} else
						buf+=strlen(buf);
				}
				if(nc%8)
					text_line(print_buf);

				for(cp= &(col_ptr->cells[0]),nc=0;nc<=maxc;nc++,cp++)
					dbg_print_cell(cp);
			}
		}
	}
}

void
dbg_print_cell FUN1(CELL *,cp)
{
	char *ptr1,*ptr2;
	char tmpbuf[30];

	switch(GET_TYP(cp)) {
	case 0:
		ptr1="(null)";
		ptr2="";
		break;
	case TYP_FLT:
		sprintf(tmpbuf,"Float: %.16g",cp->cell_flt);
		ptr1=tmpbuf;
		ptr2="";
		break;
	case TYP_INT:
		sprintf(tmpbuf,"Int: %ld",cp->cell_int);
		ptr1=tmpbuf;
		ptr2="";
		break;
	case TYP_ERR:
		sprintf(tmpbuf,"Error: %d: ",cp->cell_err);
		ptr1=tmpbuf;
		ptr2=ename[cp->cell_err];
		break;
	case TYP_BOL:
		sprintf(tmpbuf,"Bool: %d: ",cp->cell_bol);
		ptr1=tmpbuf;
		ptr2=bname[cp->cell_bol];
		break;
	case TYP_STR:
		sprintf(tmpbuf,"String: %p: ",cp->cell_str);
		ptr1=tmpbuf;
		ptr2=cp->cell_str;
		break;
	default:
		sprintf(tmpbuf,"Unknown: %d",GET_TYP(cp));
		ptr1=tmpbuf;
		ptr2="";
		break;
	}
	text_line("Cell %p: flags %#lx, cycle %u, formula %p, value %s%s",
		cp,cp->cell_flags,cp->cell_cycle,cp->cell_formula,
		ptr1,ptr2);
	dbg_print_formula(cp->cell_formula);
	dbg_print_ref_fm(cp->cell_refs_from);
	dbg_print_ref_to(cp->cell_refs_to);
}

#endif