epu/neighbours.c

   1
   2 #include <stdio.h>
   3 #include <stdlib.h>
   4 #include <string.h>
   5 #include "epp.h"
   6 #include "eppl_ut.h"
   7 void help()
   8 { printf("Usage: neighbours [-%%][-d] file\n");
   9   exit(0);
  10 }
  11
  12 short int* table;
  13
  14 EPP *file;
  15
  16 int count,limit,delta;
  17 int duplicates=0;
  18
  19 int compare(unsigned short int *r1, unsigned short int *r2)
  20 {int i;
  21  for (i=0;i<2;i++,r1++,r2++)
  22  { if (*r1>*r2) return 1;
  23    else
  24    if (*r1<*r2) return -1;
  25  }
  26  return 0;
  27
  28 }
  29 int search(unsigned short *key,int *index)
  30 {int l=0,h=count-1,i,c;
  31  while(l<=h)
  32  { i=(l+h)>>1;
  33    c=compare(table+2*i,key);
  34    if (c<0) l=i+1;
  35    else
  36    { h=i-1;
  37      if (!c) { *index=i;return 1;}
  38    }
  39   }
  40  *index=l;
  41  return 0;
  42 }
  43 void insert(unsigned short *key,int index)
  44 { int i;
  45   if (count==limit)
  46   {
  47      table=realloc(table,(limit+=delta)*2*sizeof(short int));
  48      if (!table)
  49      { fprintf(stderr,"Couldn't realloc table. Table limit is %d\n",limit);
  50        exit(1);
  51      }
  52    }
  53
  54  for(i=count;i>index;i--)
  55   {table[2*i]=table[2*(i-1)];
  56   table[2*i+1]=table[2*i-1];}
  57   table[2*index]=key[0];
  58   table[2*index+1]=key[1];
  59   count++;
  60 }
  61 void delete(int index)
  62 { int i;
  63   for(i=index+1;i<count;i++)
  64   { table[2*(i-1)]=table[2*i];
  65     table[2*i-1]=table[2*i+1];
  66   }
  67   count--;
  68 }
  69
  70 void add_pair(int v1,int v2)
  71 {int index;unsigned short int key[2];
  72  if (v1==v2||v1==file->offsite||v2==file->offsite) return;
  73  if (v1>v2) {key[0]=v2;key[1]=v1;}
  74       else  {key[0]=v1;key[1]=v2;}
  75  if (!search(key,&index))
  76   insert(key,index);
  77 }
  78
  79 void print_table()
  80 {int i,j;unsigned short int pair[2];
  81  unsigned short *t=table;
  82  i=0;
  83  while (i<count)
  84   { printf("%d\t%d\n",*t,*(t+1));
  85     if (duplicates&&*t<*(t+1))
  86      { pair[1]=*t;
  87        pair[0]=*(t+1);
  88        delete(i);
  89        search(pair,&j);
  90        insert(pair,j);
  91      }
  92     else
  93      { i++;t+=2;}
  94
  95   }
  96 }
  97 int main(int argc,char **argv)
  98 {int i=1,j,k,rows,c,verbose=0;
  99  struct option long_options[]={
 100  {"help",0,0,1},
 101  {"verbose",0,0,'%'},
 102  {"double",0,0,'d'},
 103  {NULL,0,0,0}};
 104  while ((c=getopt_long(argc,argv,"%d",long_options,&j))!=-1)
 105  { switch(c)
 106    {  case '%':verbose=1;break;
 107      case 'd':duplicates=1;break;
 108      case 1:
 109      case '?':
 110      default: help();
 111    }
 112   }
 113  if (argc==optind)
 114   { fprintf(stderr,"No input file\n");
 115     return 2;
 116   }
 117  file=open_epp(argv[optind]);
 118  if (!file) file=open_epp(default_ext(argv[optind],".epp"));
 119  if (!file) {fprintf(stderr,"Cannot open file %s\n",argv[optind]);
 120              return 2;
 121             }
 122  set_epp_cache(file,2);
 123 table=malloc(65536*2*sizeof(short int));
 124  if (!table) { fprintf(stderr,"Not enough memory to allocate %d records\n",65536);
 125  exit(1);
 126  }
 127  limit=65536;
 128  delta=1024;
 129  count=0;
 130  rows=file->lr-file->fr;
 131  install_progress_indicator(verbose?show_percent:check_int);
 132  for(i=file->fr,k=1;i<file->lr;i++,k++)
 133   { if (EndLineProc)
 134      if ((c=(*EndLineProc)(i,k,rows)))
 135       {break;}
 136   for(j=file->fc;j<file->lc;j++)
 137     { add_pair((c=epp_get(file,j,i)),epp_get(file,j+1,i));
 138       add_pair(c,epp_get(file,j,i+1));
 139       add_pair(c,epp_get(file,j+1,i+1));
 140     }
 141  }
 142  if(clear_progress(c)) exit(abs(c));
 143  print_table();
 144  free(table);
 145  close_epp(file);
 146  return 0;
 147 }