// sort-demo.C
// demo of the sorting routines : piksrt, shell, sort, hpsort
// uses a huge vector of floats as for indexing pixels of an image
// if the sorting is complete, they hold always the values 0,1,2,3,....
// to let each routine work independently, a new process is forked
// they communicate with the parent via shared memory segments for 
// the float vectors

#include "window.h"

#define NRANSI
extern "C" {
#include "nr.h"
#include "nrutil.h"
}

#include <sys/types.h>
#include <sys/stat.h>
#include <sys/shm.h>
#include <sys/signal.h>
#include <unistd.h>
#include <errno.h>

long int idum = -1;

// merge a vector by random generator
void merge(long unsigned np, float *f) {  
  for (unsigned i = 0; i < np/4; i++) { // use an arbitrary number of swaps
    int i1 = int (ran1(&idum)*np), i2 = int(ran1(&idum)*np);
    // swap elements i1 and i2
    float tmp = f[i1]; f[i1] = f[i2]; f[i2] = tmp;
  }
}
 
static int image_depth = DefaultDepth(display,screen);
static Visual *visual = DefaultVisual(display,screen);

int boost = 10; // boosting factor : needed because sorting is too fast 
                // only every boost element is used for display !!

class mixwin : public window {
 XImage *xisrc,*xidst;
 float *fsort;
public:
 mixwin(window &parent, XImage *xisrc, float *fsort, 
	 int x, int y) :
 window(parent,xisrc->width,xisrc->height,x,y,0), xisrc(xisrc), fsort(fsort) { 
   // use one image as source
   short *data = new short[width*height]; 
   xidst = XCreateImage(display, visual, depth, ZPixmap, 0,
			(char*) data, xisrc->width, xisrc->height, depth, 0);
 }

 virtual void redraw() {
   short *dst = (short*) xidst->data; // for 16bit color only
   short *src = (short*) xisrc->data;
   for (int i = 0; i < width*height; i++) dst[i] = src[irint(fsort[i*boost])];
   XPutImage(display,Win,gc_copy,xidst,0,0,0,0,width,height);
 }
};

// type for sorting functions
typedef void (*FSORT)(long unsigned, float *);

void piksrx(long unsigned n, float *f) { // wrapper needed for parameter n
  piksrt(n,f);
}

int nsort = 4; // 4 sorting routines to invoke
FSORT fsort[] = { piksrx, shell, sort, hpsort};
char *sname[] = { "piksrt","shell","sort","hpsort"};

// describes structure of shared memory segments
// here : { flag(1 int), vector (np float) } * ns
struct segment { 
  char *addr;
  int np;
  segment(char *addr, int np) : addr(addr), np(np) {}
  int size() { return ((np+1)*sizeof(float)); }
  // return the address of vector i from segment
  float *fptr(int i) {
    float *fx = (float *) addr; 
    return fx+i*(np+1)+1;
  }
  int *flag(int i) { 
    return (int*)(addr+i*size()) ;
  } 
  void set_flag(int i, int v) { *flag(i) = v; }
  int get_flag(int i) { return *flag(i); }
};

int shmid; // shared memory id
char *shmaddr; // its virtual address

char *helps[] = {
  "This demo shows the working of 4 sorting routines of NR :",
  "        'piksrx', 'shell', 'sort', 'hpsort'","",
  "The button 'mix' mixes the window content with a random generator",
  "(it may be pressed some times for better mixing)","",
  "Pressing 'sort' starts all 4 routines simultaneously for 200,000 floats","",
  "The 4 windows show the progression of sorting",
  0};

class mix_main : public main_window {
  mixwin **xi;
  info_window **iw;
  int np,ns;
  segment *gseg;
  float **ff;
  int w;
  int *pchild; // process ids of children
public:
  mix_main(char *Name, XImage *xisrc, int np, int ns, segment *gseg, 
	   int w, int h) 
    : main_window(Name,ns*(w+1),h+40), np(np), ns(ns), gseg(gseg), w(w) {  
      menu_bar *mb = new menu_bar(*this,width,20,0,0,80);
      new instance_button <mix_main>(*mb,"mix",&mixing,this); 
      new instance_button <mix_main>(*mb,"sort",&sort,this); 
      new instance_button <mix_main>(*mb,"stop",&stop,this);
      new help_button(*mb,"help",helps);
      new instance_button <mix_main>(*mb,"quit",&quit,this);
      
      ff = new float*[ns]; // the ith partition of segment
      for (int i=0; i < ns; i++) ff[i] = gseg->fptr(i); 
      float fact = 1.0/boost;
      for (int i=0; i < ns; i++) {
	for (int j=0; j < np; j++) ff[i][j] = fact*j;
      }

      xi = new mixwin*[ns]; iw = new info_window*[ns];
      for (int i=0; i<ns; i++) {
	xi[i] = new mixwin(*this,xisrc,ff[i],(w+1)*i,20);
	iw[i] = new info_window(*this,w+1,20,(w+1)*i,height-20);
      }
      pchild = new int[ns];
      polling_mode = True;
    }

  void sort() {
    // printf("\nparent is forking : shmid = %d addr = %p\n",shmid,addr);
    for (int i = 0; i < ns; i++) {
      int pid = fork(); // up to here all processes have the same data
      pchild[i] = pid;
      if (pid == 0) { // I am a child process !!
	// use shm-address, never real address ff !!!
	char *addr = shmat(shmid, (char *) 0, 0); 
	segment seg(addr,np);
	seg.set_flag(i,-1);
	float *fi = seg.fptr(i); 
	// use the i-th copy as working array 
	// printf("child %d works on %p ",i,fi);
	fsort[i](np,fi-1); // use sorting routine i
	seg.set_flag(i,0); // indicate ready
	exit(0);
      }
    }
  }
  void stop() { // kill all child processes
    for (int i=0; i < ns; i++) kill(pchild[i],9);
  }

  void quit() { stop(); exit_flag = True; }

  void mixing() {
    merge(np,ff[0]);	
    for (int i=0; i < ns; i++) gseg->set_flag(i,-1);
    for (int i=1; i < ns; i++)  
      for (int j=0; j < np; j++) ff[i][j] = ff[0][j];
  }
  virtual void polling_handler() { 
    for (int i=0; i < ns; i++) { 
      xi[i]->redraw(); char *mark = (gseg->get_flag(i) == 0) ? "**" : "--";
      sprintf(iw[i]->info,"%s%s%s",mark,sname[i],mark);
      iw[i]->redraw();
    } 
  }
  virtual void redraw() {
    for (int i=0; i < ns; i++) {
      int xp = (w+1)*i+w;
      line(xp,0,xp,height);
    }
  }
};

void cleanup(int i) {   // only parent should do it
  int ret = shmdt(shmaddr);     
  if (ret < 0) printf("error shmdt %d %d %s ",ret,errno,strerror(errno));

  struct shmid_ds shds;
  ret = shmctl(shmid, IPC_STAT, &shds);
  if (ret < 0) printf(" IPC_STAT %d %d %s ",ret,errno,strerror(errno));

  ret = shmctl(shmid,IPC_RMID,0);
  if (ret < 0) printf(" IPC_RMID %d %d %s ",ret,errno,strerror(errno));
  // printf("parent exiting\n");
  exit(0);
}
 
main() {
  int np = 200000; // size of the arrays to be sorted 
  // shmaddr has room for 4 vectors of size np+1
  shmid = shmget(0, nsort*(np+1)*sizeof(float), 0777 | IPC_CREAT);
  shmaddr = shmat(shmid, (char *) 0, 0);
  segment seg(shmaddr,np);
  Window win = DefaultRootWindow(display); 
  int w = 100, h = np/(w*boost);
  XImage *xisrc = XGetImage(display,win,0,0,w,h, AllPlanes, ZPixmap);

  mix_main *mw = new mix_main("sorting",xisrc,np,nsort,&seg,w,h);

  for (int i=0; i < 17; i++) signal(i,cleanup);

  mw->main_loop();
  
  cleanup(0);
}