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