home *** CD-ROM | disk | FTP | other *** search
/ gdead.berkeley.edu / gdead.berkeley.edu.tar / gdead.berkeley.edu / pub / cad-tools / ciftomann.tar / resort.c < prev    next >
C/C++ Source or Header  |  1988-01-28  |  4KB  |  191 lines
  1. #include "ciftomann.h"
  2. #include "fd.h"
  3. #include <stdio.h>
  4.  
  5. int max_index = 100;
  6.  
  7. #define READ_EDGE(edgeptr) {\
  8.     if ( fread(edgeptr, sizeof(EDGE), 1, stdin) == 0) {\
  9.     eof = TRUE;\
  10.     }\
  11. }
  12.  
  13. typedef struct {
  14.     EDGE *array;
  15.     int index;
  16. } window;
  17.  
  18. window *temp;
  19. #define EXCHANGE(a,b) { temp = a; a = b; b = temp; }
  20.  
  21.  
  22. typedef enum { FALSE = 0,TRUE } boolean;
  23. boolean eof;
  24.  
  25. EDGE start;    /* the first edge loaded by load */
  26. int min;    /* the top of the new low window */
  27. int delta;    /* the grow/shrink factor */
  28. int comparer();
  29.  
  30.     /*
  31.      *    resort is used to resort edges if we have put them out
  32.      *    of order by doing a grow/shrink of delta. The method of
  33.      *    sorting relies on the fact that elements are at most
  34.      *    2*delta units apart. We therefore sort incoming edges
  35.      *  into two different windows: edges falling in the ystart
  36.      *    to ystart + delta going into one window and edges falling
  37.      *    into the ystart + delta to ystart + 2*delta go into the 
  38.      *    second window. Once we see an edge beyond ystart + 2*delta,
  39.      *    we know there are no more edges coming that would lie in the
  40.      *    first window. We can therefore sort the first window, output
  41.      *    it, swap the two windows, set ystart = ystart+delta, and
  42.      *    continue the process.
  43.      */
  44.  
  45. main(argc,argv)
  46. int argc;
  47. char **argv;
  48. {
  49.     window window_1,window_2;
  50.  
  51.     window *low = &window_1,
  52.        *high = &window_2;;
  53.  
  54.     sscanf(argv[1],"%d",&delta);
  55.     delta = Abs(delta);
  56.  
  57.     READ_EDGE(&start);
  58.  
  59.     if ( eof ) {
  60.     exit(0);
  61.     }
  62.  
  63.     if ( delta > 0 ) {
  64.  
  65.     min = start.y;
  66.  
  67.     allocate(low,high);
  68.  
  69.     while ( !eof ) {
  70.         
  71.         load(low,high);    /* read edges into the windows until
  72.                    a 2*delta range has been seen */
  73.         /* sort the first window */
  74.         qsort(low->array,low->index,sizeof(EDGE),comparer);
  75.         output(low);
  76.         EXCHANGE(low,high);    /* swap the low and high windows */
  77.     }
  78.  
  79.         /* sort the final window */
  80.     qsort(low->array,low->index,sizeof(EDGE),comparer);
  81.     output(low);
  82.     } else {
  83.         /* there was no grow/shrink so copy the edges 
  84.            out directly */
  85.     while ( !eof ) {
  86.         fwrite(&start, sizeof(EDGE), 1, stdout);
  87.         READ_EDGE(&start);
  88.     }
  89.     }
  90.  
  91.     exit(0);
  92. }
  93.  
  94.     /* sort the incoming edges into the two windows, see the opening
  95.      * comment */
  96.  
  97. load(low,high)
  98. window *low,*high;
  99. {
  100.     EDGE current;
  101.     int ysplit,ystop;
  102.  
  103.     current = start;
  104.     ysplit = start.y;
  105.     ystop = start.y + 2*delta;
  106.  
  107.     do {
  108.     if (current.y < ysplit) {
  109.  
  110.         if (low->index >= max_index) {
  111.         reallocate(low, high);
  112.         }
  113.  
  114.         low->array[low->index++] = current;
  115.     } else {
  116.  
  117.         if (high->index >= max_index) {
  118.         reallocate(low, high);
  119.         }
  120.  
  121.         high->array[high->index++] = current;
  122.     }
  123.  
  124.     if ( current.y < min ) {
  125.         min = current.y;
  126.     }
  127.  
  128.     READ_EDGE(¤t);
  129.  
  130.     } while (current.y < ystop && !eof);
  131.  
  132.     start = current;
  133. }
  134.  
  135. output(hi)
  136. window *hi;
  137. {
  138.     register int i,max;
  139.     register EDGE *array;
  140.  
  141.     max = hi->index;
  142.     array = hi->array;
  143.  
  144.     for (i = 0; i < max; i++) {
  145.     fwrite((char *) (array+i), sizeof(EDGE), 1, stdout);
  146.     }
  147.  
  148.     hi->index = 0;
  149. }
  150.  
  151. allocate(a,b)
  152. window *a,*b;
  153. {
  154.     a->array = (EDGE *) malloc(max_index*sizeof(EDGE));
  155.     b->array = (EDGE *) malloc(max_index*sizeof(EDGE));
  156.  
  157.     if (a->array == (EDGE *) 0 || b->array == (EDGE *) 0) {
  158.     panic("can't obtain any memory");
  159.     }
  160.  
  161.     a->index = 0;
  162.     b->index = 0;
  163. }
  164.  
  165. char *realloc();
  166.  
  167. reallocate(a,b)
  168. window *a, *b;
  169. {
  170.     max_index *= 2;
  171.  
  172.     free(a->array);
  173.     a->array = (EDGE *) realloc((char *) a->array,
  174.                 max_index*sizeof(EDGE));
  175.  
  176.     free(b->array);
  177.     b->array = (EDGE *) realloc((char *) b->array,
  178.                 max_index*sizeof(EDGE));
  179.  
  180.     if (a->array == (EDGE *) 0 || b->array == (EDGE *) 0) {
  181.     panic("can't obtain any memory");
  182.     }
  183. }
  184.  
  185. panic(str)
  186. char *str;
  187. {
  188.     fprintf(stderr,"Panic in resort: %s\n",str);
  189.     exit(1);
  190. }
  191.