home *** CD-ROM | disk | FTP | other *** search
/ Usenet 1994 January / usenetsourcesnewsgroupsinfomagicjanuary1994.iso / sources / unix / volume13 / measures < prev    next >
Encoding:
Internet Message Format  |  1988-01-31  |  19.5 KB
  1. Subject:  v13i042:  Brute force measurement selection
  2. Newsgroups: comp.sources.unix
  3. Sender: sources
  4. Approved: rsalz@uunet.UU.NET
  5.  
  6. Submitted-by: elsie!ado (Arthur David Olson)
  7. Posting-number: Volume 13, Issue 42
  8. Archive-name: measures
  9.  
  10. [  Truly how to save work by using a computer.  --r$ ]
  11.  
  12. Measures reads one or more files containing the values of measurable
  13. traits for a set of items, and lists which traits may be measured to learn
  14. which one of the items an unknown item is.
  15.  
  16. : To unbundle, sh this file
  17. echo 'measures.1' 1>&2
  18. cat >'measures.1' <<'End of measures.1'
  19. .LC @(#)measures.1    1.13
  20. .TH MEASURES 1E \*(eH
  21. .SH NAME
  22. measures \- list measurements to take
  23. .SH SYNOPSIS
  24. .B measures
  25. [ file ... ]
  26. .= measures
  27. .SH DESCRIPTION
  28. .I Measures
  29. reads one or more files containing the values of measurable traits
  30. for a set of items, and lists which traits may be measured to learn which one of
  31. the items an unknown item is.
  32. .PP
  33. The file(s) to read may be named on the command line;
  34. the standard input is read if there are no
  35. .IR file (s)
  36. on the command line or if 
  37. .B `-'
  38. is used.
  39. Sharp signs ('#'s) and characters that follow them on lines are ignored.
  40. Lines with only spaces, tabs, and colons in them are ignored.
  41. Each remaining line gives the values for the item
  42. whose name is given first on the line;
  43. values are separated by any number of spaces, tabs, or colons.
  44. A non-numeric string of characters
  45. (for example,
  46. .B `--'
  47. or
  48. .BR `unknown' )
  49. may be used for any trait whose value is unknown for a given item.
  50. Two values separated by a `-' may be used to give a range in which
  51. the value for the item is known to fall.
  52. .PP
  53. If a line starts with one of the words listed below,
  54. it gets the special treatment indicated.
  55. .TP
  56. .B Filed
  57. Other entries on the line are used as names of the traits when the traits are
  58. listed.  In the absence of a
  59. .B `Filed'
  60. line, the first trait is called `1', the second is called `2', and so forth.
  61. .TP
  62. .B Errors
  63. Other entries on the line give the `experimental error' involved in measuring
  64. each trait.  The number may end with a percent sign (`%') to signify a
  65. percentage error figure.
  66. The range of values that might be measured for a trait
  67. (given experimental error)
  68. for two items must not overlap
  69. for the two items to be told apart by measuring that trait.
  70. In the absence of a
  71. .B `Errors'
  72. line, each trait's experimental error is taken to be zero.
  73. .TP
  74. .B Costs
  75. Other entries on the line give the cost of measuring each trait.
  76. In the absence of a
  77. .B `Costs'
  78. line, each trait's cost is taken to be one.
  79. .PP
  80. The listed set or sets of traits to be measured are those whose totaled costs
  81. are lowest and provide as much information as you could get by measuring
  82. all the traits.
  83. .SH EXAMPLE
  84. Given the input
  85. .in +.5i
  86. .nf
  87. .ft B
  88. .ta \w'Errors\0\0'u +\w'10%\0\0'u +\w'10%\0\0'u
  89. Filed    A    B    C
  90. Errors    10%    10%    10%
  91. p    1    6    5
  92. q    1    3    5
  93. r    4    6    2
  94. .br
  95. .in -.5i
  96. .fi
  97. .ft P
  98. the
  99. .I measures
  100. program produces the two lines of output
  101. .in +.5i
  102. .nf
  103. .ft B
  104. A B
  105. B C
  106. .br
  107. .in -.5i
  108. .fi
  109. .ft P
  110. to indicate that either A and B or B and C may be measured to identify an
  111. unknown sample as being one of p, q, or r.
  112. .SH LIMITATION
  113. There's a limit (usually thirty-two) 
  114. on the number of traits that may be worked with.
  115. Lines may be at most one thousand characters long.
  116. .SH SEE ALSO
  117. .IR "Journal of Theoretical Biology" ,
  118. (1987)
  119. .BR 128 ,
  120. 1-9.
  121. End of measures.1
  122. echo 'Makefile' 1>&2
  123. cat >'Makefile' <<'End of Makefile'
  124. # @(#)Makefile    1.1
  125.  
  126. SRCS=        ealloc.c ialloc.c measures.c substrings.c wild.c wildexit.c
  127. OBJS=        ealloc.o ialloc.o measures.o substrings.o wild.o wildexit.o
  128. CFLAGS=        -s -O
  129. LINT=        lint
  130. LINTFLAGS=    -phbaaxc
  131.  
  132. all:        measures
  133.  
  134. sure:
  135.         $(LINT) $(LINTFLAGS) $(SRCS)
  136.  
  137. clean:
  138.         rm -f *.o *.out core ,*
  139.  
  140. measures:    $(OBJS)
  141.         $(CC) $(CFLAGS) $(OBJS) -o $@
  142. End of Makefile
  143. echo 'ealloc.c' 1>&2
  144. cat >'ealloc.c' <<'End of ealloc.c'
  145. #
  146.  
  147. /*LINTLIBRARY*/
  148.  
  149. #include "stdio.h"
  150.  
  151. #if !defined lint && !defined NOID
  152. static char    elsieid[] = "@(#)ealloc.c    8.2";
  153. #endif /* !defined lint && !defined NOID */
  154.  
  155. extern char *    icalloc();
  156. extern char *    icatalloc();
  157. extern char *    icpyalloc();
  158. extern char *    imalloc();
  159. extern char *    irealloc();
  160.  
  161. static char *
  162. check(pointer)
  163. char *    pointer;
  164. {
  165.     if (pointer == NULL)
  166.         wildrexit("allocating memory");
  167.     return pointer;
  168. }
  169.  
  170. char *
  171. emalloc(size)
  172. {
  173.     return check(imalloc(size));
  174. }
  175.  
  176. char *
  177. ecalloc(nelem, elsize)
  178. {
  179.     return check(icalloc(nelem, elsize));
  180. }
  181.  
  182. char *
  183. erealloc(ptr, size)
  184. char *    ptr;
  185. {
  186.     return check(irealloc(ptr, size));
  187. }
  188.  
  189. char *
  190. ecatalloc(old, new)
  191. char *    old;
  192. char *    new;
  193. {
  194.     return check(icatalloc(old, new));
  195. }
  196.  
  197. char *
  198. ecpyalloc(string)
  199. char *    string;
  200. {
  201.     return check(icpyalloc(string));
  202. }
  203.  
  204. efree(p)
  205. char *    p;
  206. {
  207.     ifree(p);
  208. }
  209.  
  210. ecfree(p)
  211. char *    p;
  212. {
  213.     icfree(p);
  214. }
  215. End of ealloc.c
  216. echo 'ialloc.c' 1>&2
  217. cat >'ialloc.c' <<'End of ialloc.c'
  218. #
  219.  
  220. /*LINTLIBRARY*/
  221.  
  222. #include "stdio.h"
  223.  
  224. #if !defined lint && !defined NOID
  225. static char    elsieid[] = "@(#)ialloc.c    8.3";
  226. #endif /* !defined lint && !defined NOID */
  227.  
  228. #if !defined alloc_t
  229. #define alloc_t    unsigned
  230. #endif /* !defined alloc_t */
  231.  
  232. #if defined MAL
  233. #define NULLMAL(x)    ((x) == NULL || (x) == MAL)
  234. #else /* !defined MAL */
  235. #define NULLMAL(x)    ((x) == NULL)
  236. #endif /* !defined MAL */
  237.  
  238. extern char *    calloc();
  239. extern char *    malloc();
  240. extern char *    realloc();
  241. extern char *    strcpy();
  242.  
  243. char *
  244. imalloc(n)
  245. {
  246. #if defined MAL
  247.     register char *    result;
  248.  
  249.     if (n == 0)
  250.         n = 1;
  251.     result = malloc((alloc_t) n);
  252.     return (result == MAL) ? NULL : result;
  253. #else /* !defined MAL */
  254.     if (n == 0)
  255.         n = 1;
  256. #if defined __TURBOC__
  257.     /*
  258.     ** Beat a TURBOC bug.
  259.     */
  260.     if ((n & 1) != 0)
  261.         ++n;
  262. #endif /* defined __TURBOC__ */
  263.     return malloc((alloc_t) n);
  264. #endif /* !defined MAL */
  265. }
  266.  
  267. char *
  268. icalloc(nelem, elsize)
  269. {
  270.     if (nelem == 0 || elsize == 0)
  271.         nelem = elsize = 1;
  272. #if defined __TURBOC__
  273.     if ((nelem & 1) != 0 && (elsize & 1) != 0)
  274.         ++nelem;
  275. #endif /* defined __TURBOC__ */
  276.     return calloc((alloc_t) nelem, (alloc_t) elsize);
  277. }
  278.  
  279. char *
  280. irealloc(pointer, size)
  281. char *    pointer;
  282. {
  283.     if (NULLMAL(pointer))
  284.         return imalloc(size);
  285.     if (size == 0)
  286.         size = 1;
  287. #if defined __TURBOC__
  288.     if ((size & 1) != 0)
  289.         ++size;
  290. #endif /* defined __TURBOC__ */
  291.     return realloc(pointer, (alloc_t) size);
  292. }
  293.  
  294. char *
  295. icatalloc(old, new)
  296. char *    old;
  297. char *    new;
  298. {
  299.     register char *    result;
  300.     register    oldsize, newsize;
  301.  
  302.     oldsize = NULLMAL(old) ? 0 : strlen(old);
  303.     newsize = NULLMAL(new) ? 0 : strlen(new);
  304.     if ((result = irealloc(old, oldsize + newsize + 1)) != NULL)
  305.         if (!NULLMAL(new))
  306.             (void) strcpy(result + oldsize, new);
  307.     return result;
  308. }
  309.  
  310. char *
  311. icpyalloc(string)
  312. char *    string;
  313. {
  314.     return icatalloc((char *) NULL, string);
  315. }
  316.  
  317. ifree(p)
  318. char *    p;
  319. {
  320.     if (!NULLMAL(p))
  321.         free(p);
  322. }
  323.  
  324. icfree(p)
  325. char *    p;
  326. {
  327.     if (!NULLMAL(p))
  328.         free(p);
  329. }
  330. End of ialloc.c
  331. echo 'measures.c' 1>&2
  332. cat >'measures.c' <<'End of measures.c'
  333. #
  334.  
  335. #include "stdio.h"
  336.  
  337. #if !defined lint && !defined NOID
  338. static char elsieid[] = "@(#)measures.c    1.23";
  339. #endif /* !defined lint && !defined NOID */
  340.  
  341. #include "math.h"
  342.  
  343. #if !defined NBPI
  344. #define NBPI    (8 * sizeof (int))    /* Number of Bits Per Int */
  345. #endif /* !defined NBPI */
  346.  
  347. #if !defined MAXLINE
  348. #define MAXLINE    1000            /* MAXimum LINE length */
  349. #endif /* !defined MAXLINE */
  350.  
  351. #define SKIPPED    '\0'
  352.  
  353. #if defined __TURBOC__
  354. #define HUGE    HUGE_VAL
  355. #define float    double
  356. #undef SKIPPED
  357. #define SKIPPED    (-1)
  358. #endif /* defined __TURBOC__ */
  359.  
  360. extern char *    ecpyalloc();
  361. extern char *    erealloc();
  362. extern char *    strchr();
  363. extern char **    substrings();
  364. extern char *    wildname();
  365.  
  366. struct range {
  367.     float    lo;
  368.     float    hi;
  369. };
  370.  
  371. struct range **    ranges;        /* measured ranges of traits, -/+ errors */
  372.  
  373. int        itemcount;    /* number of items  with traits */
  374. int        traitcount;    /* number of traits of each item */
  375.  
  376. struct trait {
  377.     char *    name;
  378.     float    error;
  379.     char    errtype;
  380.     float    cost;
  381. };
  382.  
  383. struct trait    traits[NBPI];
  384.  
  385. apartbits(i, j)
  386. {
  387.     register struct range *    rp1;
  388.     register struct range *    rp2;
  389.     register int        n, result;
  390.  
  391.     result = 0;
  392.     n = traitcount;
  393.     rp1 = ranges[i + 1];
  394.     rp2 = ranges[j + 1];
  395.     while (--n >= 0) {
  396.         --rp1;
  397.         --rp2;
  398.         if (rp1->lo > rp2->hi || rp1->hi < rp2->lo)
  399.             result |= 1 << n;
  400.     }
  401.     return result;
  402. }
  403.  
  404. char *    oopsname;
  405. long    oopsline;
  406.  
  407. oops(message)
  408. char *    message;
  409. {
  410.     (void) fprintf(stderr, "\"%s\", line %ld: wild %s\n",
  411.         oopsname, oopsline, message);
  412.     for ( ; ; )
  413.         wildexit(message);
  414. }
  415.  
  416. dofiled(innames)
  417. char **    innames;
  418. {
  419.     register int    i;
  420.  
  421.     for (i = 0; i < traitcount; ++i)
  422.         if (traits[i].name != NULL)
  423.             if (strcmp(innames[i], traits[i].name) == 0)
  424.                 continue;
  425.             else    oops("mismatched `Filed' lines");
  426.         else traits[i].name = ecpyalloc(innames[i]);
  427. }
  428.  
  429. doerrors(inerrors)
  430. char **    inerrors;
  431. {
  432.     register int    i;
  433.     float        f;
  434.     char        c;
  435.  
  436.     for (i = 0; i < traitcount; ++i) {
  437.         c = '\0';
  438.         if ((sscanf(inerrors[i], "%f%c", &f, &c) == 1 &&
  439.             c != SKIPPED) || (c != SKIPPED && c != '%'))
  440.                 oops("`Errors' line");
  441.         if (f < 0)
  442.             oops("negative `Errors' value");
  443.         if (c == '%' && f > 100)
  444.             oops("Error percentage > 100");
  445.         if (traits[i].error != 0 &&
  446.             (f != traits[i].error || c != traits[i].errtype))
  447.                 oops("mismatched `Errors' lines");
  448.         traits[i].error = f;
  449.         traits[i].errtype = c;
  450.     }
  451. }
  452.  
  453. docosts(incosts)
  454. char **    incosts;
  455. {
  456.     register int    i;
  457.     float        f;
  458.     char        c;
  459.  
  460.     for (i = 0; i < traitcount; ++i) {
  461.         c = '\0';
  462.         if (sscanf(incosts[i], "%f%c", &f, &c) != 1 || c != SKIPPED)
  463.             oops("`Costs' line");
  464.         if (f <= 0)
  465.             oops("non-positive `Costs' value");
  466.         if (traits[i].cost != 0 && f != traits[i].cost)
  467.             oops("mismatched `Costs' lines");
  468.         traits[i].cost = f;
  469.     }
  470. }
  471.  
  472. getanum(string, address)
  473. char *    string;
  474. float *    address;
  475. {
  476.     double    d;
  477.     char    c;
  478.  
  479.     /*
  480.     ** Some buggy sscanfs think that "-" is a number.
  481.     */
  482.     if (strcmp(string, "-") == 0)
  483.         return 0;
  484.     c = '\0';
  485.     if (sscanf(string, "%f%c", &d, &c) == 1 && c == SKIPPED) {
  486.         *address = d;
  487.         return 1;
  488.     }
  489.     if (*string == '-') {
  490.         *address = -HUGE;
  491.         ++string;
  492.     } else    *address = HUGE;
  493.     return strcmp(string, "HUGE") == 0 || strcmp(string, "huge") == 0 ||
  494.         strcmp(string, "Huge") == 0;
  495. }
  496.  
  497. #define ATATIME    500
  498.  
  499. doranges(inranges)
  500. register char **    inranges;
  501. {
  502.     register char *    cp;
  503.     register int    i;
  504.     register int    ok;
  505.  
  506.     if ((itemcount % ATATIME) == 0) {
  507.         ranges = (struct range **) erealloc((char *) ranges,
  508.             (itemcount + ATATIME) * sizeof *ranges);
  509.         ranges[0] = (struct range *) erealloc((char *) ranges[0],
  510.             (itemcount + ATATIME) * traitcount * sizeof *ranges[0]);
  511.         for (i = 1; i < itemcount + ATATIME; ++i)
  512.             ranges[i] = ranges[i - 1] + traitcount;
  513.     }
  514.     for (i = 0; i < traitcount; ++i) {
  515.         if (getanum(inranges[i], &ranges[itemcount][i].lo)) {
  516.             ranges[itemcount][i].hi = ranges[itemcount][i].lo;
  517.             continue;
  518.         }
  519.         cp = inranges[i];
  520.         for ( ; ; ) {
  521.             cp = strchr(cp + 1, '-');
  522.             if (cp == 0) {
  523.                 ranges[itemcount][i].lo = -HUGE;
  524.                 ranges[itemcount][i].hi = HUGE;
  525.                 break;
  526.             }
  527.             *cp = '\0';
  528.             ok = getanum(inranges[i], &ranges[itemcount][i].lo) &&
  529.                 getanum(cp + 1, &ranges[itemcount][i].hi);
  530.             *cp++ = '-';
  531.             if (!ok)
  532.                 continue;
  533.             if (ranges[itemcount][i].lo > ranges[itemcount][i].hi)
  534.                 oops("range");
  535.             break;
  536.         }
  537.     }
  538.     ++itemcount;
  539. }
  540.  
  541. infile(filename)
  542. char *    filename;
  543. {
  544.     register FILE *        fp;
  545.     register char *        cp;
  546.     register char **    cpp;
  547.     register int        i;
  548.     char            buf[MAXLINE + 2];    /* +2 for "\n\0" */
  549.  
  550.     if (strcmp(filename, "-") == 0) {
  551.         fp = stdin;
  552.         filename = "standard input";
  553.     }
  554.     else if ((fp = fopen(filename, "r")) == NULL)
  555.         for ( ; ; )
  556.             wild2exit("result opening", filename);
  557.     oopsname = filename;
  558.     for (oopsline = 1; fgets(buf, sizeof buf, fp) == buf; ++oopsline) {
  559.         cp = strchr(buf, '\n');
  560.         if (cp == 0)
  561.             oops("long line");
  562.         *cp = '\0';        /* Zap the trailing newline */
  563.         if (strchr(buf, '#') != 0)
  564.             *strchr(buf, '#') = '\0';    /* Zap comments */
  565.         cpp = substrings(buf, ": \t");
  566.         if (cpp == NULL)
  567.             for ( ; ; )
  568.                 wildrexit("substrings");
  569.         for (i = 0; cpp[i] != NULL; ++i)
  570.             ;
  571.         if (i == 0) {
  572.             free((char *) cpp);
  573.             continue;
  574.         }
  575.         if (traitcount == 0) {
  576.             traitcount = i - 1;
  577.             if (traitcount <= 0)
  578.                 oops("lack of traits");
  579.             if (traitcount > NBPI)
  580.                 oops("large number of traits");
  581.         } else if (traitcount != i - 1)
  582.             oops("number of traits");
  583.         cp = cpp[0];
  584.         if (strcmp(cp, "Filed") == 0)
  585.             dofiled(&cpp[1]);
  586.         else if (strcmp(cp, "Errors") == 0)
  587.             doerrors(&cpp[1]);
  588.         else if (strcmp(cp, "Costs") == 0)
  589.             docosts(&cpp[1]);
  590.         else    doranges(&cpp[1]);
  591.         (void) free((char *) cpp);
  592.     }
  593.     if (ferror(fp) || !feof(fp))
  594.         for ( ; ; )
  595.             wild2exit("result reading", filename);
  596.     if (fp != stdin)
  597.         (void) fclose(fp);
  598. }
  599.  
  600. int *    aparts;        /* traits to measure to tell two items apart */
  601. int    apartcount;    /* number of elements in above table */
  602. int    mustbits;    /* tells which traits MUST be measured */
  603. int    mustcount;    /* tells how many traits MUST be measured */
  604.  
  605. main(argc, argv)
  606. int    argc;
  607. char *    argv[];
  608. {
  609.     register int    argind;
  610.     register int    i, j;
  611.     float        lo, hi;
  612.     char        buf[NBPI];    /* Wildly generous! */
  613.  
  614.     argv[0] = wildname(argv[0]);
  615.     argind = 1;
  616.     if (strcmp(argv[argind], "--") == 0)
  617.         ++argind;
  618.     if (argind == (argc - 1) && strcmp(argv[argind], "=") == 0) {
  619.         (void) fprintf(stderr, "%s: usage is %s [file...]\n",
  620.             argv[0], argv[0]);
  621.         for ( ; ; )
  622.             tameexit();
  623.     }
  624.     if (argind == argc)
  625.         infile("-");
  626.     else for (i = argind; i < argc; ++i)
  627.         infile(argv[i]);
  628.     if (itemcount == 0)
  629.         for ( ; ; )
  630.             wildrexit("lack of items");
  631. /*
  632. ** Set all costs to one if no costs were given.
  633. */
  634.     for (i = 0; i < traitcount; ++i)
  635.         if (traits[i].cost != 0)
  636.             break;
  637.     if (i >= traitcount)
  638.         for (i = 0; i < traitcount; ++i)
  639.             traits[i].cost = 1;
  640. /*
  641. ** Set all labels if no labels were given.
  642. */
  643.     if (traits[0].name == NULL)
  644.         for (i = 0; i < traitcount; ++i) {
  645.             (void) sprintf(buf, "%d", i + 1);
  646.             traits[i].name = ecpyalloc(buf);
  647.         }
  648. /*
  649. ** Adjust the ranges to reflect the errors.
  650. */
  651.     for (i = 0; i < itemcount; ++i)
  652.         for (j = 0; j < traitcount; ++j) {
  653.             if (traits[j].error == 0)
  654.                 continue;
  655.             lo = ranges[i][j].lo;
  656.             if (lo > -HUGE && lo < HUGE) {
  657.                 if (traits[j].errtype == '\0')
  658.                     lo -= traits[j].error;
  659.                 else    lo -= lo * (traits[j].error / 100.);
  660.                 ranges[i][j].lo = lo;
  661.             }
  662.             hi = ranges[i][j].hi;
  663.             if (hi > -HUGE && hi < HUGE) {
  664.                 if (traits[j].errtype == '\0')
  665.                     hi += traits[j].error;
  666.                 else    hi += hi * (traits[j].error / 100.);
  667.                 ranges[i][j].hi = hi;
  668.             }
  669.         }
  670. /*
  671. ** Build the "tell apart" table.
  672. */
  673.     for (i = 0; i < itemcount - 1; ++i) {
  674.         aparts = (int *) erealloc((char *) aparts,
  675.             (apartcount + itemcount + 1 - i) * sizeof *aparts);
  676.         for (j = i + 1; j < itemcount; ++j)
  677.             newbits(apartbits(i, j));
  678.     }
  679.     if (mustcount + apartcount == 0)
  680.         for ( ; ; )
  681.             wildexit("indistinguishable items (given errors)");
  682.     finish();
  683.     for ( ; ; )
  684.         tameexit();
  685. }
  686.  
  687. newbits(new)
  688. register int    new;
  689. {
  690.     register int *    ip;
  691.     register int    i;
  692.  
  693.     if ((mustbits & new) != 0)
  694.         return;    /* A test we must do can tell these two apart */
  695.     if (new == 0)
  696.         return;    /* We can't tell these two apart! */
  697.     /*
  698.     ** Is the new case (or a harder one) already in the table?
  699.     */
  700.     ip = aparts;
  701.     ip[apartcount] = new;
  702.     while ((*ip++ & ~new) != 0)
  703.         ;
  704.     if (ip <= &aparts[apartcount])
  705.         return;
  706.     /*
  707.     ** Get rid of any old entries that this new one is harder than.
  708.     */
  709.     ip = aparts;
  710.     for ( ; ; )
  711.         if ((new & ~*ip++) == 0) {
  712.             if (*--ip == new)
  713.                 break;
  714.             *ip = aparts[--apartcount];
  715.             aparts[apartcount] = new;
  716.         }
  717.     /*
  718.     ** Is more than one test involved?
  719.     */
  720.     i = 1;
  721.     while ((new & i) == 0)
  722.         i <<= 1;
  723.     if (new != i) {
  724.         ++apartcount;
  725.         return;
  726.     }
  727.     /*
  728.     ** A single test is involved.
  729.     */
  730.     mustbits |= i;
  731.     if (++mustcount < traitcount)
  732.         return;
  733.     /*
  734.     ** Oh well. . .
  735.     */
  736.     finish();
  737.     for ( ; ; )
  738.         tameexit();
  739. }
  740.  
  741. float    lowcost;
  742. int *    lowbits;
  743. int    lowcount;
  744.  
  745. finish()
  746. {
  747.     register int    i, j;
  748.  
  749.     lowcost = HUGE;
  750.     aparts[apartcount] = 0;
  751.     dobits(mustbits, 0, 0., aparts);
  752.     for (i = 0; i < lowcount; ++i) {
  753.         for (j = 0; j < traitcount; ++j)
  754.             if ((lowbits[i] & (1 << j)) != 0)
  755.                 (void) printf("%s ", traits[j].name);
  756.         printf("\n");
  757.     }
  758. }
  759.  
  760. dobits(todo, done, cost, ip)
  761. register int    todo, done;
  762. register float    cost;
  763. register int *    ip;
  764. {
  765.     register int    i, nextbit;
  766.  
  767.     while((todo & *ip++) != 0)
  768.         ;
  769.     if (*--ip == 0) {
  770.         if (cost < lowcost) {
  771.             lowcost = cost;
  772.             lowcount = 0;
  773.         }
  774.         lowbits = (int *) erealloc((char *) lowbits,
  775.             (lowcount + 1) * sizeof *lowbits);
  776.         lowbits[lowcount++] = todo;
  777.         return;
  778.     }
  779.     if (cost >= lowcost)
  780.         return;        /* cost can't get smaller! */
  781.     i = *ip++ & ~(todo | done);
  782.     for (nextbit = 0; nextbit < traitcount; ++nextbit) {
  783.         if ((i & (1 << nextbit)) == 0 ||
  784.             cost + traits[nextbit].cost > lowcost)
  785.                 continue;
  786.         dobits(todo | ( 1 << nextbit), done,
  787.             cost + traits[nextbit].cost, ip);
  788.         done |= 1 << nextbit;
  789.     }
  790. }
  791. End of measures.c
  792. echo 'substrings.c' 1>&2
  793. cat >'substrings.c' <<'End of substrings.c'
  794. #
  795.  
  796. /*LINTLIBRARY*/
  797.  
  798. #include "stdio.h"
  799.  
  800. #if !defined lint && !defined NOID
  801. static char    elsieid[] = "@(#)substrings.c    8.2";
  802. #endif /* !defined lint && !defined NOID */
  803.  
  804. #include "ctype.h"
  805.  
  806. #if !defined TRUE
  807. #define TRUE    1
  808. #define FALSE    0
  809. #endif /* !defined TRUE */
  810.  
  811. extern char *    imalloc();
  812. extern char *    strchr();
  813.  
  814. char **
  815. substrings(string, separators)
  816. char *    string;
  817. char *    separators;
  818. {
  819.     register char **    array;
  820.     register char *        cp;
  821.     register int        nsubs;
  822.     register int        lastsepprint;
  823.  
  824.     if (string == NULL || separators == NULL || *separators == '\0')
  825.         return NULL;
  826.     array = (char **) imalloc((strlen(string) + 2) * sizeof *array);
  827.     if (array == NULL)
  828.         return NULL;
  829.     if (*string == '\0') {
  830.         array[0] = NULL;
  831.         return array;
  832.     }
  833.     nsubs = 0;
  834.     lastsepprint = TRUE;
  835.     for (cp = string; *cp != '\0'; ++cp)
  836.         if (strchr(separators, *cp) != 0) {
  837.             if (isascii(*cp) && isprint(*cp) && *cp != ' ' &&
  838.                 lastsepprint)
  839.                     array[nsubs++] = cp;
  840.             lastsepprint = isascii(*cp) && isprint(*cp) &&
  841.                 *cp != ' ';
  842.             *cp = '\0';
  843.         } else {
  844.             lastsepprint = FALSE;
  845.             if (cp == string || *(cp - 1) == '\0')
  846.                 array[nsubs++] = cp;
  847.         }
  848.     if (lastsepprint && *(cp - 1) == '\0')
  849.         array[nsubs++] = cp;
  850.     array[nsubs] = NULL;
  851.     return array;
  852. }
  853. End of substrings.c
  854. echo 'wild.c' 1>&2
  855. cat >'wild.c' <<'End of wild.c'
  856. #
  857.  
  858. /*LINTLIBRARY*/
  859.  
  860. #include "stdio.h"
  861.  
  862. #if !defined lint && !defined NOID
  863. static char    elsieid[] = "@(#)wild.c    8.3";
  864. #endif /* !defined lint && !defined NOID */
  865.  
  866. char *
  867. wildname(name)
  868. char *    name;
  869. {
  870.     register int    i;
  871.     static char    saved[15];
  872.  
  873.     if (name != NULL && *name != '\0')
  874.         for (i = 0; (saved[i] = *name) != '\0'; ++name)
  875.             if ((*name == '/' || *name == '\\') &&
  876.                 *(name + 1) != '/' && *(name + 1) != '\\' &&
  877.                 *(name + 1) != '\0')
  878.                     i = 0;
  879.             else if (i < sizeof saved - 1)
  880.                 ++i;
  881.     return (saved[0] == '\0') ? "?" : saved;
  882. }
  883.  
  884. wild2(part1, part2)
  885. char *    part1;
  886. char *    part2;
  887. {
  888.     (void) fputs(wildname(""), stderr);
  889.     /*
  890.     ** One space after the colon matches what perror does
  891.     ** (although your typing teacher may want a second space).
  892.     */
  893.     (void) fputs(": wild ", stderr);
  894.     if (part1 == NULL)
  895.         part1 = "";
  896.     if (part2 == NULL)
  897.         part2 = "";
  898.     (void) fputs(part1, stderr);
  899.     if (*part1 != '\0' && *part2 != '\0')
  900.         (void) fputs(" ", stderr);
  901.     (void) fputs(part2, stderr);
  902.     (void) fputs("\n", stderr);
  903. }
  904.  
  905. wild(string)
  906. char *    string;
  907. {
  908.     wild2("", string);
  909. }
  910.  
  911. wildcall(string)
  912. char *    string;
  913. {
  914.     wild2("call of", string);
  915. }
  916.  
  917. wildret(string)
  918. char *    string;
  919. {
  920.     wild2("result from", string);
  921. }
  922. End of wild.c
  923. echo 'wildexit.c' 1>&2
  924. cat >'wildexit.c' <<'End of wildexit.c'
  925. #
  926.  
  927. /*LINTLIBRARY*/
  928.  
  929. #include "stdio.h"
  930.  
  931. #if !defined lint && !defined NOID
  932. static char    elsieid[] = "@(#)wildexit.c    8.2";
  933. #endif /* !defined lint && !defined NOID */
  934.  
  935. #if !defined TAMEEXITVAL
  936. #define TAMEEXITVAL    0
  937. #endif /* !defined TAMEEXITVAL */
  938.  
  939. #if !defined WILDEXITVAL
  940. #define WILDEXITVAL    1
  941. #endif /* !defined WILDEXITVAL */
  942.  
  943. wildexit(string)
  944. char *    string;
  945. {
  946.     wild(string);
  947.     for ( ; ; )
  948.         exit(WILDEXITVAL);
  949. }
  950.  
  951. wildcexit(string)
  952. char *    string;
  953. {
  954.     wildcall(string);
  955.     for ( ; ; )
  956.         exit(WILDEXITVAL);
  957. }
  958.  
  959. wildrexit(string)
  960. char *    string;
  961. {
  962.     wildret(string);
  963.     for ( ; ; )
  964.         exit(WILDEXITVAL);
  965. }
  966.  
  967. wild2exit(part1, part2)
  968. char *    part1;
  969. char *    part2;
  970. {
  971.     wild2(part1, part2);
  972.     for ( ; ; )
  973.         exit(WILDEXITVAL);
  974. }
  975.  
  976. tameexit()
  977. {
  978.     for ( ; ; )
  979.         exit(TAMEEXITVAL);
  980. }
  981. End of wildexit.c
  982. exit
  983.  
  984.