/*********************************************************************************************************************************************************************/
int get(offset)                                                                      /*  The procedure get() is in charge of the use of external memory.  It's use   */
int offset; {                                                                        /*  is completely transparent. It is given a number and returns a number.       */
  int block,emptyblock,lastused=0, update=1, index;                                  /*  Count is a global counter that counts the calls to get().                   */
                                                                                     /*  Block is calculated to know which block offset is in, for all memory        */
  count++;                                                                           /*  transactions are dealt with in blocks of addresses, and not by single       */
  block=offset/nodesperblock;                                                        /*  integer offsets, such as the one passed to get().  Virtmem holds the        */
  if(virtmem[block]<0) {                                                             /*  location of each block--virtmem[block] is -2 if the block has never been    */
    external++;                                                                      /*  used, -1 if the block has been used but is in external memory, and 0 to     */
    emptyblock=lru(lastused);                                                        /*  blocksinmem if the block is in main memory, telling which block it is in by */
    write_block(emptyblock,offset);                                                  /*  the value it is.  So the first if statement checks to see if the block      */
    if(virtmem[block]==(-1))                                                         /*  offset is asking for is in main memory or not.  If it is not, the external  */
      read_block(block,emptyblock);                                                  /*  calls counter is incremented;  the Least Recently Used block is obtained    */
    else                                                                             /*  and put into emptyblock, which is then copied to memory.  If the block that */
      init_block(emptyblock);                                                        /*  contains offset exists, it is read into emptyblock (whose data is now in    */
    virtmem[physmem[emptyblock]]=(-1);                                               /*  external memory).  If it does not exist, emptyblock is cleared and          */
    virtmem[block]=emptyblock;                                                       /*  initialized by init_block.  Physmem holds values telling which block of     */
    physmem[emptyblock]=block;                                                       /*  numbers which block of memory is holding; physmem and virtmem are inverses: */
    lru(update);                                                                     /*  virtmem[physmem[block]]=block.  But not the other way around, for some      */
  }                                                                                  /*  virtmem entries are negative since the blocks they represent are not in     */
                                                                                     /*  main memory.  Once emptyblock has it's values read in/ initialized, the     */
  index=(virtmem[block]*nodesperblock)+(offset%nodesperblock);                       /*  assignments must occur to reflect these changes. Lru and used are updated,  */
  return(index);                                                                     /*  and the new index for offset is calculated.  The subscripts for physmem are */
}                                                                                    /*  numbers of blocks of physical locations in the computer.  The subscripts for*/
/*********************************************************************************************************************************************************************/
int lru(status)                                                                      /*  virtmem are blocks of data(nodes).                                          */
int status; {                                                                        /*                                                                              */
  int lastused=0,slot;                                                               /*  The procedure lru() is in charge of knowing which blocks of physical memory */
  static i=0, counter=1;                                                             /*  have been accessed least recently.  It does this by maintaining the used    */
                                                                                     /*  array.  To find which block has not been used recently, the procedure loops */
  i=(i+1)%blocksinmem;                                                               /*  through the used array to find a zero--indicating no use for quite a while. */
  if(status==lastused) {                                                             /*  Once it finds such a block, since it is getting ready to be used, it sets   */
    slot=(i+blocksinmem-1)%blocksinmem;                                              /*  that element to TRUE.  In the other mode, that of update, the counter       */
    while((used[i]!=FALSE)&&(i!=slot))                                               /*  simply cycles through every so often and sets the element to FALSE,         */
      i=(++i)%blocksinmem;                                                           /*  indicating it has not been used.  This is obviously not going to be         */
    used[i]=TRUE;                                                                    /*  completely accurate, but if there is a correct ratio of completed cycles to */
    return(i);                                                                       /*  calls of get, only those used often should remain marked TRUE.  I have not  */
  }                                                                                  /*  the privilidge of determining what that ratio is, but that is why lrutimer  */
  else {                         /*           update            */                   /*  is a user input.                                                            */
    counter=(++counter)%lrutimer;
    if(!counter)
      used[i]=FALSE;
    return(i);
  }
}
/*********************************************************************************************************************************************************************/
void read_block(newblock,oldblock)                                                   /*  This procedure calls set_file_ptr to determine what datafile to open, then  */
int newblock,oldblock; {                                                             /*  opens it.  Then it reads into this file the data for the incoming block--   */
  int i;                                                                             /*  newblock, and writes it into the correct space, oldblock.  Upon completion, */
                                                                                     /*  it unlinks the file because the data the file contained is now in memory.   */
  set_file_ptr(newblock);
  fin=fopen(datafile,"r");
  for(i=(oldblock*nodesperblock);i<((oldblock+1)*nodesperblock);i++) {
    read_struct(node[i],fin);
  }
  fclose(fin);
  unlink(datafile);
}
/*********************************************************************************************************************************************************************/
void write_block(blockno,offset)                                                     /*  Write_block() writes a block of data to external memory.  The variable,     */
int blockno, offset; {                                                               /*  is passed to be written as a header for each node (it has no real           */
  int i;                                                                             /*  usefulnesss).  It calls set_file_ptr to know which file to write to, and    */
                                                                                     /*  closes this file when done, so it may be read from.                         */
  set_file_ptr(physmem[blockno]);
  fout=fopen(datafile,"w");
  for(i=(blockno*nodesperblock);i<((blockno+1)*nodesperblock);i++) {
    write_struct(node[i],offset++);
  }
  fclose(fout);
}
/*********************************************************************************************************************************************************************/
void set_mem_loc() {                                                                 /*  Procedere set_mem_loc() initializes used and sets all the virtmem and       */
  int i;                                                                             /*  elements to values such that get() does not have to be used until the       */
                                                                                     /*  possibility of needing external data files becomes real.                    */
  for(i=0;i<blocksinmem;i++) {                                                       /*  All the elements of virtmem that are greater than the number of blocks in   */
    virtmem[i]=i;                                                                    /*  main memory are set to -2 to show that they have not been used until get()  */
    physmem[i]=i;                                                                    /*  changes them to something else.                                             */
    used[i]=FALSE; 
  } 
  for(i=blocksinmem;i<MAXFILES;i++)
    virtmem[i]=(-2);
}
/*********************************************************************************************************************************************************************/
void init_block(block)                                                               /*  Initialize block clears and initializes all the structures in that block of */
int block; {                                                                         /*  memory, with the aid of init_node (in the main program).                    */
  int j,k;

  for(k=(block*nodesperblock);k<((block+1)*nodesperblock);k++) {
    init_node(node[k]);
    node[k]->cube=0.0;
    for(j=0;j<8;j++)
       node[k]->value[j]=0.0;
  }
}
/*********************************************************************************************************************************************************************/
void write_struct(side,offset)                                                       /*  This procedure wirtes a structure to fout.                                  */
list side; 
int offset; {
  int i,j,l;
  
  fprintf(fout,"\n\n%d\n",offset);
  fprintf(fout,"%g ",side->Jmin);
  for(i=0;i<3;i++)
    for(j=0;j<2;j++) {
      for(l=0;l<8;l++) 
        fprintf(fout,"%g ",side->denom[i][j][l]);
  }
  fprintf(fout,"\n%g ",side->prob);
  for(i=0;i<8;i++)
    fprintf(fout,"%g ",side->value[i]);
  fprintf(fout,"%d ",side->Opti);
  fprintf(fout,"%d ",side->Optj);
  fprintf(fout,"%d ",side->optflag);
  fprintf(fout,"%f\n",side->cube);
  for(i=0;i<3;i++) 
    for(j=0;j<2;j++) 
      for(l=0;l<8;l++)
        fprintf(fout,"%d ",side->child[i][j][l]);
  fprintf(fout,"\n%d ",side->left);
  fprintf(fout,"%d ",side->right);
  fprintf(fout,"%d\n",side->parent);
}
/*********************************************************************************************************************************************************************/
void read_struct(side,fin)                                                           /*  This procedure reads a structure from fin.                                  */
list side; 
FILE *fin; {
  int i,j,l;

  fscanf(fin,"\n\n%d\n",&i);
  fscanf(fin,"%f ",&side->Jmin);
  for(i=0;i<3;i++)
    for(j=0;j<2;j++) {
      for(l=0;l<8;l++) 
        fscanf(fin,"%f ",&side->denom[i][j][l]);
  }
  fscanf(fin,"\n%f ",&side->prob);
  for(i=0;i<8;i++)
    fscanf(fin,"%f ",&side->value[i]);
  fscanf(fin,"%d ",&side->Opti);
  fscanf(fin,"%d ",&side->Optj);
  fscanf(fin,"%d ",&side->optflag);
  fscanf(fin,"%f\n",&side->cube);
  for(i=0;i<3;i++) 
    for(j=0;j<2;j++) 
      for(l=0;l<8;l++)
        fscanf(fin,"%d ",&side->child[i][j][l]);
  fscanf(fin,"\n%d",&side->left);
  fscanf(fin,"%d ",&side->right);
  fscanf(fin,"%d\n",&side->parent);
}
/*********************************************************************************************************************************************************************/
void set_file_ptr(blockno)                                                           /*  This procedure takes a block number between 0 and 99 and appends it to the  */
int blockno; {                                                                       /*  end of the datafile string.                                                 */

  strcpy(datafile,"/usr/tmp/data");
  if(blockno<10) 
    datafile[13]='0';
  else 
    datafile[13]='0'+(blockno/10);
  datafile[14]='0'+(blockno%10);
  datafile[15]='\0';
}
/*********************************************************************************************************************************************************************/