home *** CD-ROM | disk | FTP | other *** search
/ The Education Master 1994 (4th Edition) / EDUCATIONS_MASTER_4TH_EDITION.bin / files / progmisc / qparser2 / lib / sets.c < prev    next >
Encoding:
C/C++ Source or Header  |  1992-05-17  |  10.7 KB  |  413 lines
  1. /* sets.c
  2.  
  3. Author: QCAD Systems, Inc., 1990.
  4.  
  5.    Provides set operations.
  6.    A "set" is an array of char made large enough to carry all the
  7. elements of a power set as bits in the array.  The organization of
  8. the bits can be inferred from the function "set_member" given below.
  9.    We recommend using the define SETSIZE in sets.h when allocating
  10. a set array.
  11.    A set array can be expanded in size as needed without impacting
  12. any of these functions -- but note that certain functions need the
  13. dimension of the array as a parameter.  "size" will refer to the
  14. number of chars in the array, not the number of elements.
  15.  
  16.    */
  17.  
  18. #include <stdio.h>
  19. #include "sets.h"
  20.  
  21. static char mask[]= {0x80, 0x40, 0x20, 0x10, 8, 4, 2, 1};
  22. static char nmask[]= {0x7F, 0xBF, 0xDF, 0xEF, 0xF7, 0xFB, 0xFD, 0xFE}; 
  23.  
  24. /* clip_mask n has leftmost n+1 bits set; n= 0..7 */ 
  25. static char clip_mask[]= {0, 0x80, 0xC0, 0xE0, 0xF0, 0xF8, 0xFC, 0xFE};
  26.  
  27. /* set_count is the number of bits in the number 0..15 */ 
  28. static char set_count[]= {0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4};
  29.  
  30. /* .................... */
  31. void clearset(set, size)
  32.   char *set;
  33.   int size;  /* chars in set */
  34. { /* 'set' is emptied of elements */
  35.   memset(set, '\0', size);
  36.   }
  37.  
  38. /* .................... */
  39. void fillset(set, size)
  40.   char *set;
  41.   int size;  /* chars in set */
  42. { /* 'set' is filled with elements.
  43.      NOTE: should be followed by a 'trimset' call */
  44.   memset(set, (char) 0xFF, size);
  45.   }
  46.  
  47. /* ................... */
  48. int set_member(element, set)
  49.   const int element;
  50.   char *set;
  51. { /* is the 'element' (0..elements-1) in the 'set'? */
  52.   return (set[element >> 3] & mask[element & 7]);
  53.   }
  54.  
  55. /* ................... */
  56. int set_size(set, size)
  57.   char *set;
  58.   int size;
  59.   /* how many elements are in the set?
  60.      NOTE: is valid only if the set has been trimmed */
  61. { int count= 0;
  62.  
  63.   while (size--) {
  64.     count += set_count[(*set >> 4) & 0xF];
  65.     count += set_count[*set & 0xF];
  66.     set++;
  67.     }
  68.   return count;
  69.   }
  70.  
  71. /* ................... */
  72. int empty_set(set, size)
  73.   char *set;
  74.   int size;
  75. {  /* is the 'set' empty?
  76.       NOTE: is valid only if the set has been trimmed */
  77.   while (size--)
  78.     if (*(set++)) return 0;  /* not empty */
  79.   return 1;  /* is empty */
  80.   }
  81.  
  82. /* ................... */
  83. void set_union(set1, set2, set3, size)
  84.   char *set1, *set2, *set3;
  85.   int size;
  86. { /* set1 = set_union(set2, set3) */
  87.   while (size--) *(set1++) = *(set2++) | *(set3++);
  88.   }
  89.  
  90. /* ................... */
  91. void set_merge(set1, set2, size)
  92.   char *set1, *set2;
  93.   int size;
  94. { /* set1 = set_union(set1, set2) */
  95.   while (size--) *(set1++) |= *(set2++);
  96.   }
  97.  
  98. /* ................... */
  99. void intersection(set1, set2, set3, size)
  100.   char *set1, *set2, *set3;
  101.   int size;
  102. { /* set1 = set_intersection(set2, set3) */
  103.   while (size--) *(set1++) = *(set2++) & *(set3++);
  104.   }
  105.  
  106. /* ................... */
  107. int is_intersection(set1, set2, size)
  108.   char *set1, *set2;
  109.   int size;
  110. { /* are there any elements in set_intersection(set1, set2)? */
  111.   while (size--)
  112.     if (*(set1++) & *(set2++)) return 1;
  113.   return 0;
  114.   }
  115.  
  116. /* ................... */
  117. int set_equal(set1, set2, size)
  118.   char *set1, *set2;
  119.   int size;
  120. { /* are the two sets equivalent?
  121.      NOTE: both sets should be trimmed BEFORE calling this */
  122.   while (size--)
  123.     if (*(set1++) != *(set2++)) return 0;
  124.   return 1;
  125.   }
  126.  
  127. /* ................... */
  128. void set_include(element, set)
  129.   /* add element to set */
  130.   int element;
  131.   char *set;
  132. {
  133.   set[element >> 3] |= mask[element & 7];
  134.   }
  135.  
  136. /* ................... */
  137. void set_exclude(element, set)
  138.   /* remove element from set */
  139.   int element;
  140.   char *set;
  141. {
  142.   set[element >> 3] &= nmask[element & 7];
  143.   }
  144.  
  145. /* ..................... */
  146. int set_greater(set1, set2, size)
  147.   char *set1, *set2;
  148.   int size;
  149. { /* is there an element in set1 that isn't in set2? */
  150.   while (size--)
  151.     if (*(set1++) & ~*(set2++)) return 1;
  152.   return 0;
  153.   }
  154.  
  155. /* .................... */
  156. void set_difference(set1, set2, set3, size)
  157.   char *set1, *set2, *set3;
  158.   int size;
  159. {  /* set1 will contain all elements in set2 that are NOT in set3 */
  160.   while (size--)
  161.     *(set1++) = *(set2++) & ~*(set3++);
  162.   }
  163.  
  164. /* .................... */
  165. void set_inverse(set, size)
  166.   char *set;
  167.   int size;
  168. {  /* 'set' is replaced by its inverse.  This call should
  169.       be followed by a TRIMSET call */
  170.   while (size--) {
  171.     *set= ~*set;
  172.     set++;
  173.     }
  174.   }
  175.  
  176. /* .................... */
  177. void trimset(set, setbits)
  178.   /* this removes any spurious 'members' in the last byte of the
  179.       set array, in case they happen to get in by some accident.
  180.      For example, 'fillset' will mark the last byte 0xFF, whether
  181.       or not all the bits correspond to set members */
  182.   char *set;
  183.   int setbits;  /* number of set members, not number of bytes */
  184. { 
  185.   if (setbits & 7)
  186.     set[setbits >> 3] &= clip_mask[setbits & 7];
  187.   }
  188.  
  189. /* ................ */
  190. void set_incl(char *set, ...)
  191.   /* This is designed to accept a set, a count, and a list of any
  192.      number of element numbers to be included in the set.
  193.      see definition in sets.h */
  194. { int  element, count;
  195.   va_list args;
  196.  
  197.   va_start(args, set);
  198.   count= va_arg(args, int);
  199.   while (count--) {
  200.     element= va_arg(args, int);
  201.     set[element >> 3] |= mask[element & 7];
  202.     }
  203.   }
  204.  
  205. /* ................ */
  206. void set_excl(char *set, ...)
  207.   /* This is designed to accept a set, a count, and a list of any
  208.      number of element numbers to be excluded from the set.
  209.      see definition in sets.h */
  210. { int  count, element;
  211.   va_list args;
  212.  
  213.   va_start(args, set);
  214.   count= va_arg(args, int);
  215.   while (count--) {
  216.     element= va_arg(args, int);
  217.     set[element >> 3] &= nmask[element & 7];
  218.     }
  219.   }
  220.  
  221.     
  222. #ifdef TEST
  223. static int errors= 0;
  224.  
  225. /* ....... */
  226. static void complain(testno)
  227.   int testno;
  228. {                           
  229.   printf("Test %d failure\n", testno);
  230.   errors++;
  231.   }
  232.  
  233. /* ....... */
  234. void main()
  235. {   /* standalone test program for the set utilities */
  236.   char set1[SETSIZE(32)], set2[SETSIZE(32)], set3[SETSIZE(32)]; 
  237.   int index;
  238.   
  239.   set1[0]= set1[1]= set1[2]= set1[3]= 0x18;
  240.   clearset(set1, 4);
  241.   if (set1[0] != 0 ||
  242.       set1[1] != 0 ||
  243.       set1[2] != 0 ||
  244.       set1[3] != 0) complain(1); 
  245.   fillset(set1, 4);
  246.   if (set1[0] != (char)0xFF ||
  247.       set1[1] != (char)0xFF ||
  248.       set1[2] != (char)0xFF ||
  249.       set1[3] != (char)0xFF) complain(2);
  250.   trimset(set1, 32);
  251.   if (set1[3] != (char)255) complain(502);
  252.   trimset(set1, 31);
  253.   if (set1[3] != (char)0xFE) complain(3); 
  254.   trimset(set1, 30);
  255.   if (set1[3] != (char)0xFC) complain(4); 
  256.   trimset(set1, 29);
  257.   if (set1[3] != (char)0xF8) complain(5); 
  258.   trimset(set1, 28);
  259.   if (set1[3] != (char)0xF0) complain(6); 
  260.   trimset(set1, 27);
  261.   if (set1[3] != (char)0xE0) complain(7); 
  262.   trimset(set1, 26);
  263.   if (set1[3] != (char)0xC0) complain(8); 
  264.   trimset(set1, 25);
  265.   if (set1[3] != (char)0x80) complain(9);
  266.   
  267.   set1[0]= (char) 0x14;
  268.   if (set_member(0, set1) ||
  269.       set_member(1, set1) ||
  270.       set_member(2, set1) ||
  271.       !set_member(3, set1) ||
  272.       set_member(4, set1) ||
  273.       !set_member(5, set1) ||
  274.       set_member(6, set1) ||
  275.       set_member(7, set1)) complain(10);
  276.  
  277.   set1[1]= (char) 0x81;
  278.   if (!set_member(8, set1) ||
  279.       set_member(9, set1) ||
  280.       set_member(10, set1) ||
  281.       set_member(11, set1) ||
  282.       set_member(12, set1) ||
  283.       set_member(13, set1) ||
  284.       set_member(14, set1) ||
  285.       !set_member(15, set1)) complain(11);
  286.  
  287.   if (set_size(set1, 2) != 4) complain(12); 
  288.  
  289.   for (index= 0; index< 32; index++) {
  290.     clearset(set1, 4);
  291.     set_include(index, set1);
  292.     if (set_size(set1, 4) != 1) complain(100+index);
  293.     fillset(set1, 4);
  294.     set_exclude(index, set1);
  295.     if (set_size(set1, 4) != 31) complain(132+index);
  296.     }
  297.     
  298.   set1[0]= (char) 0x14;
  299.   set1[1]= (char) 0x81;
  300.  
  301.   set1[0]= ~set1[0]; 
  302.   set1[1]= ~set1[1];
  303.   if (set_size(set1, 2) != 12) complain(13);
  304.  
  305.   if (!set_member(0, set1) ||
  306.       !set_member(1, set1) ||
  307.       !set_member(2, set1) ||
  308.       set_member(3, set1) ||
  309.       !set_member(4, set1) ||
  310.       set_member(5, set1) ||
  311.       !set_member(6, set1) ||
  312.       !set_member(7, set1)) complain(14);
  313.  
  314.   set1[1]= (char) 0x81;
  315.   if (!set_member(8, set1) ||
  316.       set_member(9, set1) ||
  317.       set_member(10, set1) ||
  318.       set_member(11, set1) ||
  319.       set_member(12, set1) ||
  320.       set_member(13, set1) ||
  321.       set_member(14, set1) ||
  322.       !set_member(15, set1)) complain(15);
  323.  
  324.   
  325.   if (empty_set(set1, 2)) complain(16);
  326.  
  327.   clearset(set1, 4);
  328.   if (!empty_set(set1, 4)) complain(17);
  329.  
  330.   set1[0]= (char) 0x77;
  331.   set1[1]= (char) 0x88;
  332.   set2[0]= (char) 0x88;
  333.   set2[1]= (char) 0x77;
  334.   set_union(set3, set1, set2, 2);
  335.   if (set3[0] != (char) 0xFF ||
  336.       set3[1] != (char) 0xFF) complain(18);
  337.  
  338.   intersection(set3, set1, set2, 2);
  339.   if (set3[0] != 0 ||
  340.       set3[1] != 0) complain(19);
  341.  
  342.   if (set_equal(set1, set2, 2)) complain(20);
  343.   set_merge(set1, set2, 2);
  344.   if (set1[0] != (char) 0xFF ||
  345.       set1[1] != (char) 0xFF) complain(21);
  346.  
  347.   set1[0]= (char) 0x77;
  348.   set1[1]= (char) 0x88;
  349.   set2[0]= (char) 0x88;
  350.   set2[1]= (char) 0x77;
  351.   set_merge(set2, set1, 2);
  352.   if (set2[0] != (char) 0xFF ||
  353.       set2[1] != (char) 0xFF) complain(22);          
  354.    
  355.   set_merge(set1, set2, 2);
  356.   if (!set_equal(set1, set2, 2)) complain(23);
  357.   
  358.   clearset(set1, 2);
  359.   set_include(2, set1);
  360.   set_include(3, set1);
  361.   set_include(4, set1);
  362.   if (set1[0] != (char) 0x38) complain(24);
  363.  
  364.   set_exclude(2, set1);
  365.   set_exclude(4, set1);
  366.   if (set1[0] != (char) 0x10) complain(25);
  367.  
  368.   clearset(set1, 2); 
  369.   set_incl(set1, 3, 2, 3, 4);
  370.   if (set1[0] != (char) 0x38) complain(24);
  371.  
  372.   set_excl(set1, 2, 2, 4);
  373.   if (set1[0] != (char) 0x10) complain(25);
  374.  
  375.   clearset(set1, 2);
  376.   clearset(set2, 2);
  377.   set_incl(set1, 3, 2, 3, 4);
  378.   set_incl(set2, 2, 3, 4);
  379.   if (!set_greater(set1, set2, 2)) complain(26);
  380.   if (set_greater(set2, set1, 2)) complain(27);
  381.  
  382.   set_difference(set3, set1, set2, 2);
  383.   if (set3[0] != (char) 0x20 ||
  384.       set3[1] != 0) complain(28);
  385.  
  386.   set_inverse(set1, 2);
  387.   if (set1[0] != (char) 0xC7 ||
  388.       set1[1] != (char) 0xFF) complain(29);
  389.  
  390.   set_inverse(set1, 2);
  391.   if (set1[0] != (char) 0x38 ||
  392.       set1[1] != 0) complain(30);
  393.  
  394.   clearset(set1, 2);
  395.   clearset(set2, 2);
  396.   set_incl(set1, 3, 2, 3, 4);
  397.   set_incl(set2, 2, 3, 4);
  398.   if (!is_intersection(set1, set2, 2)) complain(31);
  399.   clearset(set2, 2);
  400.   set_incl(set2, 3, 5, 6, 7);
  401.   if (is_intersection(set1, set2, 2)) complain(32);
  402.   set2[0]= !set1[0];
  403.   set2[1]= !set1[1];
  404.   if (is_intersection(set1, set2, 2)) complain(33); 
  405.  
  406.   if (errors > 0) printf("%d errors!\n", errors);
  407.   else printf("NO errors\n");
  408.   exit(errors);
  409.   }
  410.  
  411. #endif
  412.  
  413.