home *** CD-ROM | disk | FTP | other *** search
/ gdead.berkeley.edu / gdead.berkeley.edu.tar / gdead.berkeley.edu / pub / cad-tools / pgsort.c < prev    next >
C/C++ Source or Header  |  1996-07-05  |  9KB  |  429 lines
  1. /*
  2.  * Sort a mann formatted file in preparation for saving the GCA pattern
  3.  * generator some work.
  4.  * Mann format is:
  5.  *    L <layer-name>;
  6.  *    B <width> <height> <x> <y> <foo> <bar>;
  7.  *    E
  8.  * where foo and bar are optional rotation values.
  9.  * Sort layer by layer.
  10.  * Within a layer, sort by width, then height, with the special
  11.  * consideration that the heights for a given width may be output
  12.  * in reverse order to prevent a sawtooth movement.
  13.  * For a given size of box, try to minimize positional movement.
  14.  * Subsorts are done at output time.
  15.  */
  16.  
  17. #include <stdio.h>
  18. #include <ctype.h>
  19. #include <math.h>
  20.  
  21. FILE    *Input, *I2;
  22. FILE    *Output;
  23. char    LayerName[32];
  24. int    LayerCount;
  25. int    LastXPos, LastYPos;
  26. long    LayerStartTell;
  27. char    *nil = "0";
  28. char    *malloc(), *NextNum();
  29. #define RFUNK    32828392
  30. double    StatCnt, StatSum1, StatSum2, StatSqr1, StatSqr2;
  31. double    Var1, Var2;
  32. int    Which;
  33.  
  34. struct datum {
  35.     long    d;        /* file position */
  36.     int    d_w;
  37.     int    d_h;
  38.     int    d_x;
  39.     int    d_y;
  40.     int    d_r1;
  41.     int    d_r2;
  42. };
  43.  
  44. main(argc, argv)
  45.     int        argc;
  46.     char    **argv;
  47. {
  48.     if (argc != 3) {
  49.     fputs("pgsort: improper argument count\n", stderr);
  50.     exit(1);
  51.     }
  52.  
  53.     Input = fopen(argv[1], "r");        /* seek file */
  54.     I2 = fopen(argv[1], "r");            /* toplevel read file */
  55.     if (! Input || ! I2) {
  56.     perror(argv[1]);
  57.     exit(1);
  58.     }
  59.     Output = fopen(argv[2], "w");        /* the result */
  60.     if (! Output) {
  61.     perror(argv[1]);
  62.     exit(1);
  63.     }
  64.  
  65.     TopLevel();                    /* do it */
  66.  
  67.     exit(0);
  68. }
  69.  
  70. TopLevel()
  71. {
  72.     char    nextLayer[128];            /* storage for next layer */
  73.     char    buf[BUFSIZ];
  74.     int        onceThrough = 0;        /* iteration control */
  75.     int        globalLine = 0;
  76.     int        layerLine;
  77.  
  78.     for (;;) {                /* loop once per layer */
  79.     if (! onceThrough) {
  80.         if (! fgets(buf, BUFSIZ, I2) ) {
  81.         fputs("pgsort: premature EOF\n", stderr);
  82.         exit(1);
  83.         }
  84.         globalLine++;
  85.     }
  86.     fputs(buf, Output);            /* dump line */
  87.  
  88.     if (buf[0] == 'L') {        /* start layer */
  89.         LayerStartTell = ftell(I2);        /* start of boxes */
  90.         strcpy(LayerName, buf + 2);        /* save name too */
  91.  
  92.         LayerCount = 0;
  93.         for (;;) {                /* loop once per box in layer */
  94.         if (! fgets(buf, BUFSIZ, I2) ) {
  95.             fputs("pgsort: premature EOF\n", stderr);
  96.             exit(1);
  97.         }
  98.         globalLine++;
  99.         LayerCount++;
  100.  
  101.         if (buf[0] == 'L' || buf[0] == 'E') {
  102.             onceThrough = 1;
  103.             LayerCount--;
  104.             LastXPos = 0;
  105.             LastYPos = 0;
  106.             DoLayerInput();
  107.             break;
  108.         } else if (buf[0] != 'B') {
  109.             fprintf(stderr,
  110.                 "pgsort: unknown command at line %d\n", globalLine);
  111.             fputs(buf, Output);
  112.         }
  113.         }                /* end of layer loop */
  114.  
  115.     } else if (buf[0] == 'E') {        /* end of file */
  116.         break;
  117.     } else {
  118.         fprintf(stderr, "pgsort: unknown command at line %d\n", globalLine);
  119.     }
  120.     }        /* end of file loop */
  121. }
  122.  
  123. /*
  124.  * Given the name of the layer already output, and the start of the
  125.  * boxes in the given layer, and the number of lines (useful or no)
  126.  * in the current layer, sort and output the layer.
  127.  */
  128. DoLayerInput()
  129. {
  130.     int        count, lcount;
  131.     register char    *cp;
  132.     register struct datum    *dp, **dpp;
  133.     struct datum    *dBase, **dpBase;
  134.     char    buf[BUFSIZ];
  135.  
  136.     dBase = (struct datum *) malloc((LayerCount + 1) * sizeof (struct datum));
  137.     dpBase = (struct datum**) malloc((LayerCount + 1) * sizeof (int *));
  138.     if (! dBase || ! dpBase) {
  139.     fputs("pgsort: out of memory\n", stderr);
  140.     exit(1);
  141.     }
  142.  
  143.     fseek(Input, LayerStartTell, 0);        /* goto point of interest */
  144.     count = 0;
  145.     lcount = 0;
  146.     dp = dBase;
  147.     dpp = dpBase;
  148.     StatReset();
  149.     while (lcount < LayerCount) {
  150.     if (! fgets(buf, BUFSIZ, Input) ) {
  151.         fputs("pgsort: unexpected EOF\n", stderr);
  152.         exit(1);
  153.     }
  154.     lcount++;
  155.     if (buf[0] == 'B') {
  156.         count++;
  157.         cp = NextNum(buf);        /* stash the line */
  158.         dp->d_w = atoi(cp);
  159.         cp = NextNum(cp);
  160.         dp->d_h = atoi(cp);
  161.         cp = NextNum(cp);
  162.         dp->d_x = atoi(cp);
  163.         cp = NextNum(cp);
  164.         dp->d_y = atoi(cp);
  165.         cp = NextNum(cp);
  166.         if (cp != nil) {
  167.         dp->d_r1 = atoi(cp);
  168.         cp = NextNum(cp);
  169.         dp->d_r2 = atoi(cp);
  170.         } else {
  171.         dp->d_r1 = RFUNK;
  172.         }
  173.         Sigma(dp->d_w, dp->d_h);
  174.         *dpp++ = dp;
  175.         dp++;
  176.     }
  177.     }        /* end of layer read loop */
  178.  
  179.     if (count) {
  180.     Variance();
  181.     Which = (Var2 > Var1);
  182.     DumpLayerStats(dpBase, count, 0);
  183.     SortBySize(dpBase, count);
  184.     OutputSort(dpBase, count);
  185.     DumpLayerStats(dpBase, count, 1);
  186.     DumpOutput(dpBase, count);
  187.     }
  188.  
  189.     free((char*)dBase);
  190.     free((char*)dpBase);
  191. }
  192.  
  193. /*
  194.  * Comparison function for box sizes.
  195.  */
  196. SizeSort(a1, a2)
  197.     struct datum    **a1, **a2;
  198. {
  199.     register struct datum    *d1, *d2;
  200.  
  201.     d1 = *a1;
  202.     d2 = *a2;
  203.     if (Which)                /* variance of h > variance of w */
  204.     if (d1->d_h != d2->d_h)
  205.         if (d1->d_h < d2->d_h)
  206.         return (-1);
  207.         else
  208.         return (1);
  209.     else if (d1->d_w != d2->d_w)
  210.         if (d1->d_w < d2->d_w)
  211.         return (-1);
  212.         else
  213.         return (1);
  214.     else
  215.         return (0);
  216.     else
  217.     if (d1->d_w != d2->d_w)
  218.         if (d1->d_w < d2->d_w)
  219.         return (-1);
  220.         else
  221.         return (1);
  222.     else if (d1->d_h != d2->d_h)
  223.         if (d1->d_h < d2->d_h)
  224.         return (-1);
  225.         else
  226.         return (1);
  227.     else
  228.         return (0);
  229. }
  230.  
  231. /*
  232.  * Do the sort.  Not too difficult.
  233.  */
  234. SortBySize(dpp, n)
  235.     struct datum    **dpp;
  236.     int        n;
  237. {
  238.     qsort((char*)dpp, n, sizeof (struct datum *), SizeSort);
  239. }
  240.  
  241. /*
  242.  * Reverse order of given chunk.
  243.  * d2 is just past end of area of interest.
  244.  */
  245. SortOutput(d1, d2)
  246.     register struct datum    **d1, **d2;
  247. {
  248.     struct datum    *d;
  249.  
  250.     while (d1 < --d2) {
  251.     d = *d1;
  252.     *d1++ = *d2;
  253.     *d2 = d;
  254.     }
  255. }
  256.  
  257. /*
  258.  * Perform secondary optimizations.
  259.  */
  260. OutputSort(dpBase, n)
  261.     struct datum    **dpBase;
  262.     int        n;
  263. {
  264.     register struct datum    **d1, **d2;
  265.     int        lastH = 0, x1, x2;
  266.  
  267.     d2 = dpBase;
  268.     while (n) {                /* loop once per width value */
  269.     d1 = d2;
  270.     do {
  271.         d2++, n--;
  272.     } while (n && (*d2)->d_w == (*d1)->d_w);/* stop @ end or change */
  273.     if (d2 > d1 + 1) {
  274.         if ( (x1 = (*d1)->d_h - lastH) < 0)
  275.         x1 = -x1;
  276.         if ( (x2 = (*d2[-1]).d_h - lastH) < 0)
  277.         x2 = -x2;
  278.         if (x1 > x2)
  279.         SortOutput(d1, d2);
  280.     }
  281.     lastH = (*d2[-1]).d_h;
  282.     SortPositions(d1, d2 - d1);
  283.     }
  284. }
  285.  
  286. /*
  287.  * Do a sort of same sized boxes based on their positions.
  288.  */
  289. PosSort(a1, a2)
  290.     struct datum    **a1, **a2;
  291. {
  292.     register struct datum    *d1, *d2;
  293.  
  294.     d1 = *a1;
  295.     d2 = *a2;
  296.     if (Which)            /* variance of y > variance of x */
  297.     if (d1->d_y != d2->d_y)
  298.         if (d1->d_y < d2->d_y)
  299.         return (-1);
  300.         else
  301.         return (1);
  302.     else if (d1->d_x != d2->d_x)
  303.         if (d1->d_x < d2->d_x)
  304.         return (-1);
  305.         else
  306.         return (1);
  307.     else
  308.         return (0);
  309.     else
  310.     if (d1->d_x != d2->d_x)
  311.         if (d1->d_x < d2->d_x)
  312.         return (-1);
  313.         else
  314.         return (1);
  315.     else if (d1->d_y != d2->d_y)
  316.         if (d1->d_y < d2->d_y)
  317.         return (-1);
  318.         else
  319.         return (1);
  320.     else
  321.         return (0);
  322. }
  323.  
  324. /*
  325.  * Given a chunk in which all widths are the same,
  326.  * find all identical boxes and sort them by position.
  327.  */
  328. SortPositions(dpBase, n)
  329.     struct datum    **dpBase;
  330.     int        n;
  331. {
  332.     register struct datum    **d1, **d2;
  333.  
  334.     d2 = dpBase;
  335.     while (n) {
  336.     d1 = d2;
  337.     StatReset();
  338.     do {
  339.         Sigma((*d2)->d_x, (*d2)->d_y);
  340.         d2++, n--;
  341.     } while (n && (*d2)->d_h == (*d1)->d_h);/* stop @ end or change */
  342.     if (d2 > d1 + 1) {
  343.         Variance();
  344.         Which = (Var2 > Var1);
  345.         qsort((char*)d1, d2 - d1, sizeof (struct datum *), PosSort);
  346.     }
  347.     LastXPos = (*d2[-1]).d_x;
  348.     LastYPos = (*d2[-1]).d_y;
  349.     }
  350. }
  351.  
  352. DumpOutput(dpp, n)
  353.     struct datum    **dpp;
  354.     int        n;
  355. {
  356.     register struct datum    *dp;
  357.  
  358.     while (n--) {
  359.     dp = *dpp;
  360.     fprintf(Output, "B %d %d %d %d", dp->d_w, dp->d_h, dp->d_x, dp->d_y);
  361.     if (dp->d_r1 != RFUNK)
  362.         fprintf(Output, " %d %d", dp->d_r1, dp->d_r2);
  363.     fputs(";\n", Output);
  364.     dpp++;
  365.     }
  366. }
  367.  
  368. DumpLayerStats(dpp, n, final)
  369.     struct datum    **dpp;
  370.     int        n, final;
  371. {
  372. }
  373.  
  374. /*
  375.  * Skip any current number and find the next.
  376.  * Number is defined as a possibly negated integer.
  377.  */
  378. char *
  379. NextNum(s)
  380.     register char    *s;
  381. {
  382.     if (! s || s == nil)
  383.     return (nil);
  384.     while (isdigit(*s) || *s == '-')
  385.     s++;
  386.     while (*s && ! isdigit(*s) && *s != '-')
  387.     s++;
  388.     if (*s)
  389.     return (s);
  390.     return (nil);
  391. }
  392.  
  393. StatReset()
  394. {
  395.     StatCnt = 0.;
  396.     StatSum1 = 0.;
  397.     StatSum2 = 0.;
  398.     StatSqr1 = 0.;
  399.     StatSqr2 = 0.;
  400. }
  401.  
  402. Sigma(v1, v2)
  403.     int        v1, v2;
  404. {
  405.     double d1, d2;
  406.  
  407.     d1 = v1;
  408.     d2 = v2;
  409.     StatSum1 += d1;
  410.     StatSum2 += d2;
  411.     StatSqr1 += d1 * d1;
  412.     StatSqr2 += d2 * d2;
  413.     StatCnt += 1.;
  414. }
  415.  
  416. Variance()
  417. {
  418.     double    nsqr;
  419.  
  420.     if (StatCnt) {
  421.     nsqr = StatCnt * StatCnt;
  422.     Var1 = (StatCnt * StatSqr1 - StatSum1 * StatSum1) / nsqr;
  423.     Var2 = (StatCnt * StatSqr2 - StatSum2 * StatSum2) / nsqr;
  424.     } else {
  425.     Var1 = 0.;
  426.     Var2 = 0.;
  427.     }
  428. }
  429.