/** predator.c *****************************************
 *
 * CS661, Algorithms
 * University of Virginia Department of Computer Science
 * Copyright (C) 1999
 *
 * Program which presents animation of five sorting
 * algorithms: insertion, shell, bubble, merge & quick.
 * by,
 *   John Haskins, Jr. (predator@cs.virginia.edu)
 *******************************************************/

#include <stdio.h>
#include <string.h>
#include <stdlib.h>


#define ESC     27
#define SPACE   32
#define NSCRBUF 64004
#define XSCRLEN 320
#define YSCRLEN 200
#define NSTAR   256
#define NFGSTAR 5
#define NBAR    75

#define SVGALO  0x13
#define TTY     0x02
#define __u16   unsigned int
#define __u8    unsigned char

#define INSSRT  0x01
#define SHLSRT  0x02
#define BBLSRT  0x03
#define MRGSRT  0x04
#define QUKSRT  0x05

#define bar_t   int
typedef struct  {
	__u16   xcoord;
	__u16   ycoord;
} star_t;


int     main(int,char **);
void    gb_graphsetvideo(__u8);
void    gb_scroll(char far *,__u16,__u16,__u16,__u16,__u8,__u8);
void    gb_putpixel(char far *,__u16,__u16,__u8);
void    gb_bar(char far *,__u16,__u16,__u16,__u16,__u8);
void    gb_waitretrace(void);
void    scrollstar(star_t *,__u8);
void    renderbar(char far *,bar_t *,__u8);
void    renderframe(char far *,__u8);
char    insertionsort(char far *,bar_t *,__u8);
char    shellsort(char far *,bar_t *,__u8);
void    swap(bar_t *,bar_t *);
char    bubblesort(char far *,bar_t *,__u8);
char    msort(bar_t *,bar_t *,__u8,__u8,__u8);
char    merge(bar_t *,bar_t *,__u8,__u8,__u8,__u8);
char    mergesort(char far *,bar_t *,__u8);
char    partition(bar_t *,__u8,__u8,int *,__u8);
char    qksort(bar_t *,__u8,__u8,__u8);
char    quicksort(char far *,bar_t *,__u8);


char *  bkgrnd;
char *  scrbuf;
char *  screen=(char *)0xa0000000;      
star_t	bgstar[NSTAR];
star_t	bgstar2[NSTAR];
star_t  mgstar[NSTAR];
star_t  fgstar[NSTAR];
bar_t   bar[NBAR];


int     main(int argc,char ** argv)
{
	__u16   n;
	__u8    nbar=0;
	char    c=0;
	__u8    srt=0;

	if (argc!=3) {
		fprintf(stderr,"usage: predator #bars ");
		fprintf(stderr,"[insertion|shell|bubble|merge|quick]\n");
		exit(1);
	}
	nbar=atoi(argv[1]);
	if ((nbar < 1) || (nbar > NBAR)) {
		fprintf(stderr,"Nice try, Gabe!\n");
		fprintf(stderr,"predator: # of bars must be [1..%d]\n",NBAR);
		exit(1);
	}
	if (!strcmp(argv[2],"insertion")) {
		srt=INSSRT;
	}
	else if (!strcmp(argv[2],"shell")) {
		srt=SHLSRT;
	}
	else if (!strcmp(argv[2],"bubble")) {
		srt=BBLSRT;
	}
	else if (!strcmp(argv[2],"merge")) {
		srt=MRGSRT;
	}
	else if (!strcmp(argv[2],"quick")) {
		srt=QUKSRT;
	}
	else {
		fprintf(stderr,"Nice try, Gabe!\n");
		fprintf(stderr,"predator: algorithm must be,",NBAR);
		fprintf(stderr," insertion,shell,bubble,merge or quick\n",NBAR);
		exit(1);
	}

	if (!(bkgrnd=(char *)malloc(NSCRBUF))) {
		fprintf(stderr,"predator: ");
		fprintf(stderr,"Cannot allocate background buffer.\n");
		exit(1);
	}
	if (!(scrbuf=(char *)malloc(NSCRBUF))) {
		fprintf(stderr,"predator: Cannot allocate screen buffer.\n");
		exit(1);
	}

	gb_graphsetvideo(SVGALO);
	memset((void *)bkgrnd,0,NSCRBUF);
#if	0
	for(n=0;n<NSCRBUF;n++)
		if (!random(0x100)) *(bkgrnd+n)=random(4)+32;
#endif
	for(n=0;n<NSTAR;n++) {
		bgstar[n].xcoord=random(XSCRLEN);
		bgstar[n].ycoord=random(YSCRLEN);
	}
	for(n=0;n<NSTAR;n++) {
		bgstar2[n].xcoord=random(XSCRLEN);
		bgstar2[n].ycoord=random(YSCRLEN);
	}
	for(n=0;n<NSTAR;n++) {
		mgstar[n].xcoord=random(XSCRLEN);
		mgstar[n].ycoord=random(YSCRLEN);
	}
	for(n=0;n<NFGSTAR;n++) {
		fgstar[n].xcoord=random(XSCRLEN);
		fgstar[n].ycoord=random(YSCRLEN);
	}
	for(n=0;n<atoi(argv[1]);n++)
		bar[n]=random(YSCRLEN-50+1)-((YSCRLEN-50)/2);
	while (c!=ESC) {
		for(;!kbhit();) renderframe(scrbuf,nbar);
		switch (srt) {
		case INSSRT:    {
			c=insertionsort(scrbuf,bar,nbar);
			break;
			}
		case SHLSRT:    {
			c=shellsort(scrbuf,bar,nbar);
			break;
			}
		case BBLSRT:    {
			c=bubblesort(scrbuf,bar,nbar);
			break;
			}
		case MRGSRT:    {
			c=mergesort(scrbuf,bar,nbar);
			break;
			}
		case QUKSRT:    {
			c=quicksort(scrbuf,bar,nbar);
			break;
			}
		}
		if (c!=ESC) {
			for(n=0;n<atoi(argv[1]);n++)
				bar[n]=random(YSCRLEN-50+1)-((YSCRLEN-50)/2);
			for(;!kbhit();) renderframe(scrbuf,nbar);
		}
	}
	gb_graphsetvideo(TTY);

	return 0;
}

void    gb_graphsetvideo(__u8 mode)
{
	asm     {
		mov     ah,0x00
		mov     al,mode
		int     0x10
	}
}

void    gb_scroll(char far * src,
		__u16 x, __u16 xlen, __u16 y, __u16 ylen,
		__u8 rate, __u8 wrap)
{
	__u8    line;
	__u8    tmp[XSCRLEN];
	__u16   sptr;

	if (rate>xlen) return;
	for(line=y;line<y+ylen;line++) {
		sptr=line*XSCRLEN;
		if (wrap) memcpy((void *)tmp,(void *)(src+sptr),rate);
		memcpy((void *)(src+sptr),(void *)(src+sptr+rate),xlen-rate);
		if (wrap) memcpy((void *)(src+sptr+xlen-1-rate),(void *)tmp,rate);
	}
}

void    gb_putpixel(char far * dest,__u16 x,__u16 y,__u8 c)
{
	if (y>=YSCRLEN || x>=XSCRLEN) return;
	*(dest+(y*XSCRLEN)+x)=c;
}

void    gb_bar(char far * dest,__u16 x,__u16 xlen,__u16 y,__u16 ylen,__u8 c)
{
	char tmp[XSCRLEN];
	__u16 xcoord;
	__u16 ycoord;
	__u16 length;

	if (y>=YSCRLEN || x>=XSCRLEN) return;
	memset((void *)tmp,c,XSCRLEN);
	if ((x+xlen-1)>XSCRLEN)
		length=XSCRLEN-x-1;
	else
		length=xlen;
	for(ycoord=y;ycoord<y+ylen && ycoord<YSCRLEN;ycoord++)
		memcpy((void *)(dest+(ycoord*XSCRLEN)+x),(void *)tmp,length);
}

void    gb_waitretrace(void)
{
	while (!(_AL & 0x08)) 
		asm     {
			mov     dx,0x03da
			in      al,dx
		}
}

void    scrollstar(star_t * star,__u8 disp)
{
	int     n;

	for(n=0;n<NSTAR;n++) {
		star[n].xcoord-=disp;
		if (star[n].xcoord>XSCRLEN) {
			star[n].xcoord=XSCRLEN;
			star[n].ycoord=random(YSCRLEN);
		}
	}
}

void    renderbar(char far * dest,bar_t * bar,__u8 nbar)
{
	int     n;
	__u8    xdisp=(XSCRLEN-(4*nbar))/2;

	for(n=0;n<nbar;n++)
		if (bar[n]<0)
			gb_bar(dest,xdisp+(4*n),3,100,-bar[n],32);
		else
			gb_bar(dest,xdisp+(4*n),3,100-bar[n],bar[n],48);
}

void    renderframe(char far * dest,__u8 nbar)
{
	int     n;

#if	0
	gb_scroll((void *)bkgrnd,0,XSCRLEN,0,YSCRLEN,1,0);
#endif
	memcpy((void *)dest,(void *)bkgrnd,NSCRBUF);
	scrollstar(bgstar,1);
	scrollstar(bgstar2,2);
	scrollstar(mgstar,3);
	for(n=0;n<NSTAR;n++) {
		gb_putpixel((void *)dest,
			bgstar[n].xcoord,bgstar[n].ycoord, 1);
		gb_putpixel((void *)dest,
			bgstar2[n].xcoord,bgstar2[n].ycoord, 32);
		gb_putpixel((void *)dest,
			mgstar[n].xcoord,mgstar[n].ycoord, 29);
	}
	renderbar(dest,bar,nbar);
	for(n=0;n<NFGSTAR;n++) {
		fgstar[n].xcoord-=(n+5);
		if (fgstar[n].xcoord>XSCRLEN) {
			fgstar[n].xcoord=XSCRLEN;
			fgstar[n].ycoord=random(YSCRLEN);
		}
		gb_putpixel((void *)dest,
			fgstar[n].xcoord,fgstar[n].ycoord, 15);
		gb_putpixel((void *)dest,
			fgstar[n].xcoord+1,fgstar[n].ycoord, 15);
		gb_putpixel((void *)dest,
			fgstar[n].xcoord+2,fgstar[n].ycoord, 9);
		gb_putpixel((void *)dest,
			fgstar[n].xcoord+3,fgstar[n].ycoord, 1);
		gb_putpixel((void *)dest,
			fgstar[n].xcoord+4,fgstar[n].ycoord, 18);
	}
	gb_waitretrace();
	memcpy((void *)screen,(void *)dest,NSCRBUF);
}

char    insertionsort(char far * dest,bar_t * bar,__u8 nbar)
{
	int     j,n;
	bar_t   tmp;

	for(n=1;n<nbar;n++) {
		j=n; tmp=bar[n];
		while (j>0 && tmp<bar[j-1]) {
			bar[j]=bar[j-1];
			j--;
			renderframe(dest,nbar);
			if (kbhit() && (getch()==ESC)) return ESC;
		}
		bar[j]=tmp;
		renderframe(dest,nbar);
		if (kbhit() && (getch()==ESC)) return ESC;
	}
	for(;!kbhit();) renderframe(dest,nbar);
	return getch();
}

char    shellsort(char far * dest,bar_t * bar,__u8 nbar)
{
	int     i,j,incr=nbar/2;
	bar_t   tmp;
	__u8    exitwhile=0;

	while (incr>0) {
		for(i=incr;i<nbar;i++) {
			tmp=bar[i]; j=i;
			while (!exitwhile && j-incr>=0) {
				if (tmp<bar[j-incr]) {
					bar[j]=bar[j-incr];
					j-=incr;
					bar[j]=tmp;
					renderframe(dest,nbar);
					if (kbhit() && (getch()==ESC))
						return ESC;
				}
				else exitwhile=1;
			}
			exitwhile=0;
			bar[j]=tmp;
			renderframe(dest,nbar);
			if (kbhit() && (getch()==ESC)) return ESC;
		}
		incr/=2;
		renderframe(dest,nbar);
		if (kbhit() && (getch()==ESC)) return ESC;
	}
	for(;!kbhit();) renderframe(dest,nbar);
	return getch();
}

void    swap(bar_t * elem1,bar_t * elem2)
{
	bar_t   tmp;

	tmp=*elem1;
	*elem1=*elem2;
	*elem2=tmp;
}

char    bubblesort(char far * dest,bar_t * bar,__u8 nbar)
{
	int     m,n;

	for(n=nbar-1;n>0;n--) {
		for(m=0;m<n;m++) {
			if (bar[m+1]<bar[m]) swap(&bar[m+1],&bar[m]);
			renderframe(dest,nbar);
			if (kbhit() && (getch()==ESC)) return ESC;
		}
		renderframe(dest,nbar);
		if (kbhit() && (getch()==ESC)) return ESC;
	}
	for(;!kbhit();) renderframe(dest,nbar);
	return getch();
}

char    merge(bar_t * bar,bar_t * tmp,
		__u8 lpos,__u8 rpos,
		__u8 rightend,__u8 nbar)
{
	int     leftend=rpos-1;
	int     tmppos=lpos;
	bar_t   tmpbar[NBAR];

	while (lpos<=leftend && rpos<=rightend) {
		if (bar[lpos]<bar[rpos])
			tmp[tmppos++]=bar[lpos++];
		else
			tmp[tmppos++]=bar[rpos++];
		memcpy((void *)tmpbar,(void *)bar,(rightend+1)*sizeof(bar_t));
		memcpy((void *)bar,(void *)tmp,(rightend+1)*sizeof(bar_t));
		renderframe(scrbuf,nbar);
		memcpy((void *)bar,(void *)tmpbar,(rightend+1)*sizeof(bar_t));
		if (kbhit() && (getch()==ESC)) return ESC;
	}
	while (lpos<=leftend) {
		tmp[tmppos++]=bar[lpos++];
		memcpy((void *)tmpbar,(void *)bar,(rightend+1)*sizeof(bar_t));
		memcpy((void *)bar,(void *)tmp,(rightend+1)*sizeof(bar_t));
		renderframe(scrbuf,nbar);
		memcpy((void *)bar,(void *)tmpbar,(rightend+1)*sizeof(bar_t));
		if (kbhit() && (getch()==ESC)) return ESC;
	}
	while (rpos<=rightend) {
		tmp[tmppos++]=bar[rpos++];
		memcpy((void *)tmpbar,(void *)bar,(rightend+1)*sizeof(bar_t));
		memcpy((void *)bar,(void *)tmp,(rightend+1)*sizeof(bar_t));
		renderframe(scrbuf,nbar);
		memcpy((void *)bar,(void *)tmpbar,(rightend+1)*sizeof(bar_t));
		if (kbhit() && (getch()==ESC)) return ESC;
	}
	memcpy((void *)bar,(void *)tmp,(rightend+1)*sizeof(bar_t));

	return 0;
}

char    msort(bar_t * bar,bar_t * tmp,__u8 left,__u8 right,__u8 nbar)
{
	int     center;

	renderframe(scrbuf,nbar);
	if (left<right) {
		center=(left+right)/2;
		if (msort(bar,tmp,left,center,nbar)==ESC) return ESC;
		if (msort(bar,tmp,center+1,right,nbar)==ESC) return ESC;
		if (merge(bar,tmp,left,center+1,right,nbar)==ESC) return ESC;
	}

	return 0;
}

char    mergesort(char far * dest,bar_t * bar,__u8 nbar)
{
	bar_t   tmp[NBAR];
	int     n;

	if (msort(bar,tmp,0,nbar-1,nbar)==ESC) return ESC;

	for(;!kbhit();) renderframe(dest,nbar);
	return getch();
}

char    partition(bar_t * bar,__u8 left,__u8 right,int * pivot,__u8 nbar)
{
	bar_t   x=bar[left];
	int     i=left-1;
	int     j=right+1;

	while (1) {
		do      {
			j--;
			renderframe(scrbuf,nbar);
			if (kbhit() && (getch()==ESC)) return ESC;
		} while (j>0 && !(bar[j]<=x));
		if (j<0) j=0;
		do      {
			i++;
			renderframe(scrbuf,nbar);
			if (kbhit() && (getch()==ESC)) return ESC;
		} while (i<nbar-1 && !(bar[i]>=x));
		if (i>=nbar) i=nbar-1;
		if (i<j) {
			swap(&bar[i],&bar[j]);
			renderframe(scrbuf,nbar);
		}
		else    {
			*pivot=j;
			return 0;
		}
	}
}

char    qksort(bar_t * bar,__u8 left,__u8 right,__u8 nbar)
{
	int     pivot;

	renderframe(scrbuf,nbar);
	if (left < right) {
		if (partition(bar,left,right,&pivot,nbar)==ESC) return ESC;
		if (qksort(bar,left,pivot,nbar)==ESC) return ESC;
		if (qksort(bar,pivot+1,right,nbar)==ESC) return ESC;
	}

	return 0;
}

char    quicksort(char far * dest,bar_t * bar,__u8 nbar)
{
	if (qksort(bar,0,nbar-1,nbar)==ESC) return ESC;

	for(;!kbhit();) renderframe(dest,nbar);
	return getch();
}