home *** CD-ROM | disk | FTP | other *** search
/ The Datafile PD-CD 4 / DATAFILE_PDCD4.iso / unix / unixtools / util / c / set < prev    next >
Encoding:
Text File  |  1992-07-21  |  11.0 KB  |  464 lines
  1. /*      > C.Set - Set data type */
  2.  
  3. #include <stddef.h>
  4. #include <stdlib.h>
  5. #include <string.h>
  6. #include "set.h"
  7.  
  8. #ifdef test
  9. #include <stdio.h>
  10. #endif
  11.  
  12. struct link
  13. {
  14.         struct link *next;
  15.         char data[1];
  16. };
  17.  
  18. typedef struct link *link;
  19.  
  20. /* Return values from functions */
  21.  
  22. #define OK      1
  23. #define ERR     0
  24.  
  25. /* Utility function - find an element in a set */
  26.  
  27. static link find (const set s, const void *element, link *prev)
  28. {
  29.         link this;
  30.         link p = NULL;
  31.         const int size = s->obj_size;
  32.  
  33.         for ( this = s->first; this != NULL; this = this->next )
  34.         {
  35.                 if ( memcmp(element,this->data,size) == 0 )
  36.                 {
  37.                         if ( prev != NULL )
  38.                                 *prev = p;
  39.                                 
  40.                         return this;
  41.                 }
  42.  
  43.                 p = this;
  44.         }
  45.  
  46.         return NULL;
  47. }
  48.  
  49. /* General component routines */
  50.  
  51. set set_new (int obj_len)
  52. {
  53.         register set s;
  54.  
  55.         s = malloc(sizeof(struct set));
  56.  
  57.         if ( s == NULL )
  58.                 return NULL;
  59.  
  60.         s->first    = NULL;
  61.         s->obj_size = obj_len;
  62.  
  63.         return s;
  64. }
  65.  
  66. void set_free (set s)
  67. {
  68.         set_clear(s);
  69.         free(s);
  70. }
  71.  
  72. void set_clear (set s)
  73. {
  74.         link this_entry = s->first;
  75.         link next_entry;
  76.         
  77.         while ( this_entry != NULL )
  78.         {
  79.                 next_entry = this_entry->next;
  80.                 free(this_entry);
  81.                 this_entry = next_entry;
  82.         }
  83.  
  84.         s->first = NULL;
  85. }
  86.  
  87. int set_copy (set s1, const set s2)
  88. {
  89.         link p;
  90.         link new;
  91.         link last;
  92.         int size;
  93.  
  94.         if ( s1->obj_size != s2->obj_size )
  95.                 return ERR;
  96.  
  97.         set_clear(s1);
  98.  
  99.         last = (link)s1;
  100.         size = s2->obj_size;
  101.  
  102.         for ( p = s2->first; p != NULL; p = p->next )
  103.         {
  104.                 new = malloc(sizeof(struct link) - 1 + size);
  105.                 if ( new == NULL )
  106.                 {
  107.                         set_clear(s1);
  108.                         return ERR;
  109.                 }
  110.                 last->next = new;
  111.                 memcpy(new->data,p->data,size);
  112.                 last = new;
  113.         }
  114.  
  115.         last->next = NULL;
  116.         return OK;
  117. }
  118.  
  119. int set_equal (const set s1, const set s2)
  120. {
  121.         link p;
  122.         int n1 = 0;
  123.         int n2 = 0;
  124.  
  125.         if ( s1->obj_size != s2->obj_size )
  126.                 return 0;
  127.  
  128.         /* For every element of s1, look for it in s2 */
  129.  
  130.         for ( p = s1->first; p != NULL; p = p->next )
  131.         {
  132.                 /* If it's not in s2, the sets are different */
  133.                 if ( find(s2,p->data,NULL) == NULL )
  134.                         return 0;
  135.  
  136.                 /* Count the elements of s1 */
  137.                 ++n1;
  138.         }
  139.  
  140.         /* Count the elements of s2 */
  141.         n2 = set_size(s2);
  142.  
  143.         /* The sets differ if there are elements in s1 not in s2 */
  144.         return ( n1 == n2 );
  145. }
  146.  
  147. int set_empty (const set s)
  148. {
  149.         return ( s->first == NULL );
  150. }
  151.  
  152. int set_size (const set s)
  153. {
  154.         int i = 0;
  155.         link p;
  156.  
  157.         for ( p = s->first; p != NULL; p = p->next )
  158.                 ++i;
  159.  
  160.         return i;
  161. }
  162.  
  163. int set_iterate (const set s, int (*process)(void *))
  164. {
  165.         int ret = 0;
  166.         link p;
  167.  
  168.         for ( p = s->first; p != NULL; p = p->next )
  169.         {
  170.                 ret = (*process)(p->data);
  171.  
  172.                 /* Non-zero => stop processing here */
  173.  
  174.                 if ( ret != 0 )
  175.                         break;
  176.         }
  177.  
  178.         /* Negative => Abnormal (error) termination */
  179.  
  180.         return ( ret >= 0 );
  181. }
  182.  
  183. /* set-specific routines */
  184.  
  185. int set_add (set s, const void *object)
  186. {
  187.         link new;
  188.  
  189.         if ( find(s,object,NULL) != NULL )
  190.                 return ERR;
  191.  
  192.         new = malloc(sizeof(struct link) - 1 + s->obj_size);
  193.  
  194.         if ( new == NULL )
  195.                 return ERR;
  196.  
  197.         memcpy(new->data,object,s->obj_size);
  198.  
  199.         new->next = s->first;
  200.         s->first = new;
  201.  
  202.         return OK;
  203. }
  204.  
  205. int set_remove (set s, const void *object)
  206. {
  207.         link p;
  208.         link prev;
  209.  
  210.         p = find(s,object,&prev);
  211.  
  212.         if ( p == NULL )
  213.                 return ERR;
  214.  
  215.         if ( prev == NULL )
  216.                 s->first = p->next;
  217.         else
  218.                 prev->next = p->next;
  219.  
  220.         free(p);
  221.  
  222.         return OK;
  223. }
  224.  
  225. int set_member (const set s, const void *object)
  226. {
  227.         return ( find(s,object,NULL) != NULL );
  228. }
  229.  
  230. int set_union (set s, const set t, const set u)
  231. {
  232.         link p;
  233.         link new;
  234.  
  235.         /* Check with t's length occurs in set_copy */
  236.         if ( s->obj_size != u->obj_size )
  237.                 return ERR;
  238.  
  239.         if ( !set_copy(s,t) )
  240.                 return ERR;
  241.  
  242.         for ( p = u->first; p != NULL; p = p->next )
  243.         {
  244.                 if ( find(s,p->data,NULL) != NULL )
  245.                         continue;
  246.  
  247.                 new = malloc(sizeof(struct link) - 1 + s->obj_size);
  248.  
  249.                 if ( new == NULL )
  250.                         return ERR;
  251.  
  252.                 memcpy(new->data,p->data,s->obj_size);
  253.  
  254.                 new->next = s->first;
  255.                 s->first = new;
  256.         }
  257.  
  258.         return OK;
  259. }
  260.  
  261. int set_intersection (set s, const set t, const set u)
  262. {
  263.         link p;
  264.         link new;
  265.  
  266.         if ( s->obj_size != t->obj_size || s->obj_size != u->obj_size )
  267.                 return ERR;
  268.  
  269.         set_clear(s);
  270.  
  271.         for ( p = t->first; p != NULL; p = p->next )
  272.         {
  273.                 if ( find(u,p->data,NULL) == NULL )
  274.                         continue;
  275.  
  276.                 new = malloc(sizeof(struct link) - 1 + s->obj_size);
  277.  
  278.                 if ( new == NULL )
  279.                         return ERR;
  280.  
  281.                 memcpy(new->data,p->data,s->obj_size);
  282.  
  283.                 new->next = s->first;
  284.                 s->first = new;
  285.         }
  286.  
  287.         return OK;
  288. }
  289.  
  290. int set_difference (set s, const set t, const set u)
  291. {
  292.         link p;
  293.         link new;
  294.  
  295.         if ( s->obj_size != t->obj_size || s->obj_size != u->obj_size )
  296.                 return ERR;
  297.  
  298.         set_clear(s);
  299.  
  300.         for ( p = t->first; p != NULL; p = p->next )
  301.         {
  302.                 if ( find(u,p->data,NULL) != NULL )
  303.                         continue;
  304.  
  305.                 new = malloc(sizeof(struct link) - 1 + s->obj_size);
  306.  
  307.                 if ( new == NULL )
  308.                         return ERR;
  309.  
  310.                 memcpy(new->data,p->data,s->obj_size);
  311.  
  312.                 new->next = s->first;
  313.                 s->first = new;
  314.         }
  315.  
  316.         return OK;
  317. }
  318.  
  319. int set_subset (const set s1, const set s2)
  320. {
  321.         link p;
  322.  
  323.         if ( s1->obj_size != s2->obj_size )
  324.                 return 0;
  325.  
  326.         /* For every element of s1, look for it in s2 */
  327.  
  328.         for ( p = s1->first; p != NULL; p = p->next )
  329.         {
  330.                 /* If it's not in s2, s1 is not a subset */
  331.                 if ( find(s2,p->data,NULL) == NULL )
  332.                         return 0;
  333.         }
  334.  
  335.         return 1;
  336. }
  337.  
  338. int set_proper_subset (const set s1, const set s2)
  339. {
  340.         link p;
  341.         int n1 = 0;
  342.         int n2 = 0;
  343.  
  344.         if ( s1->obj_size != s2->obj_size )
  345.                 return 0;
  346.  
  347.         /* For every element of s1, look for it in s2 */
  348.  
  349.         for ( p = s1->first; p != NULL; p = p->next )
  350.         {
  351.                 /* If it's not in s2, s1 is not a subset */
  352.                 if ( find(s2,p->data,NULL) == NULL )
  353.                         return 0;
  354.  
  355.                 /* Count the elements of s1 */
  356.                 ++n1;
  357.         }
  358.  
  359.         /* Count the elements of s2 */
  360.         n2 = set_size(s2);
  361.  
  362.         /* It is only a proper subset if there are elements of s2 not in s1 */
  363.         return ( n1 < n2 );
  364. }
  365.  
  366. /*---------------------------------------------------------------------------*/
  367.  
  368. #ifdef test
  369. int print (void *ptr)
  370. {
  371.         printf("%d ",*(int *)ptr);
  372.         return STATUS_CONTINUE;
  373. }
  374.  
  375. void set_dump (set s)
  376. {
  377.         printf("set: ");
  378.         set_iterate(s,print);
  379.         putchar('\n');
  380. }
  381. #endif
  382.  
  383. /*---------------------------------------------------------------------------*/
  384.  
  385. #ifdef test
  386.  
  387. #define BUFLEN 255
  388.  
  389. int main (void)
  390. {
  391.         char buf[BUFLEN];
  392.         int i, j, k, num;
  393.         set s[10];
  394.  
  395.         for ( i = 0; i < 10; ++i )
  396.                 s[i] = set_new(sizeof(int));
  397.  
  398.         for ( ; ; )
  399.         {
  400.                 printf(">");
  401.                 fgets(buf,BUFLEN,stdin);
  402.  
  403.                 if ( buf[0] == '\n' || buf[0] == '\0' )
  404.                         continue;
  405.                 else if ( sscanf(buf,"clear %1d",&i) == 1 )
  406.                         set_clear(s[i]);
  407.                 else if ( sscanf(buf,"copy %1d %1d",&i,&j) == 2 )
  408.                         set_copy(s[i],s[j]);
  409.                 else if ( sscanf(buf,"equal %1d %1d",&i,&j) == 2 )
  410.                         printf("%s\n",(set_equal(s[i],s[j]) ? "yes" : "no"));
  411.                 else if ( sscanf(buf,"empty %1d",&i) == 1 )
  412.                         printf("%s\n",(set_empty(s[i]) ? "yes" : "no"));
  413.                 else if ( sscanf(buf,"size %1d",&i) == 1 )
  414.                         printf("%d\n",set_size(s[i]));
  415.                 else if ( sscanf(buf,"dump %1d",&i) == 1 )
  416.                         set_dump(s[i]);
  417.                 else if ( sscanf(buf,"add %1d %d",&i,&num) == 2 )
  418.                         set_add(s[i],&num);
  419.                 else if ( sscanf(buf,"remove %1d %d",&i,&num) == 2 )
  420.                         set_remove(s[i],&num);
  421.                 else if ( sscanf(buf,"member %1d %d",&i,&num) == 2 )
  422.                         printf("%s\n", set_member(s[i],&num) ? "yes" : "no");
  423.                 else if ( sscanf(buf,"union %1d %1d %1d",&i,&j,&k) == 3 )
  424.                         set_union(s[i],s[j],s[k]);
  425.                 else if ( sscanf(buf,"intersection %1d %1d %1d",&i,&j,&k) == 3 )
  426.                         set_intersection(s[i],s[j],s[k]);
  427.                 else if ( sscanf(buf,"difference %1d %1d %1d",&i,&j,&k) == 3 )
  428.                         set_difference(s[i],s[j],s[k]);
  429.                 else if ( sscanf(buf,"subset %1d %1d",&i,&j) == 2 )
  430.                         printf("%s\n", set_subset(s[i],s[j]) ? "yes" : "no");
  431.                 else if ( sscanf(buf,"proper subset %1d %1d",&i,&j) == 2 )
  432.                         printf("%s\n", set_proper_subset(s[i],s[j]) ? "yes" : "no");
  433.                 else if ( strncmp(buf,"help",4) == 0 )
  434.                         printf(
  435.                                 "clear i\n"
  436.                                 "copy i j\n"
  437.                                 "equal i j\n"
  438.                                 "empty i\n"
  439.                                 "size i\n"
  440.                                 "dump i\n"
  441.                                 "add i n\n"
  442.                                 "remove i n\n"
  443.                                 "member i n\n"
  444.                                 "union i j k\n"
  445.                                 "intersection i j k\n"
  446.                                 "difference i j k\n"
  447.                                 "subset i j\n"
  448.                                 "proper subset i j\n"
  449.                               );
  450.                 else if ( strncmp(buf,"quit",4) == 0 )
  451.                         break;
  452.                 else
  453.                         printf("Mistake\n");
  454.         }
  455.  
  456.         printf("Deleting s[0-9]\n");
  457.         for ( i = 0; i < 10; ++i )
  458.                 set_free(s[i]);
  459.  
  460.         return 0;
  461. }
  462.  
  463. #endif
  464.