home *** CD-ROM | disk | FTP | other *** search
/ Simtel MSDOS 1992 December / simtel1292_SIMTEL_1292_Walnut_Creek.iso / msdos / c / cnews016.arc / SETS.ARC / SETSOURC.ARC / SETDIFF.C < prev    next >
C/C++ Source or Header  |  1989-03-09  |  2KB  |  75 lines
  1. #include <stdio.h>
  2. #include <stdarg.h>
  3. #include "sets.h"
  4. /***************************************************************************/
  5.       int set_difference(set *difference, set *minuend, set *subtrahend)
  6. /***************************************************************************/
  7. /* This procedure computes the difference of two sets.  The sets must
  8.    have the same base_type in order for this to work.  The input parameters
  9.    are left unchanged.
  10. */
  11. {
  12. int i;
  13. defset(temp,UNIVERSAL,MAX_MEMBERS,0);
  14.  
  15.     /* first check for the same base_types */
  16.     if(!cmp_base_types(minuend,subtrahend) || 
  17.        !cmp_base_types(minuend,difference) ||
  18.        !cmp_set_tags(minuend,subtrahend)   ||
  19.        !cmp_set_tags(minuend,difference))
  20.         return NULL;
  21.  
  22.     /* zero out the result */
  23.     set_clear(&temp);
  24.  
  25.     /* The difference of two sets is a set whose members are members of the
  26.        minuend and not also of the subtrahend.  The set_difference is found
  27.        by first taking the XOR of the minuend and subtrahend and then ANDing
  28.        that result with the minuend.  This is expressed in C as
  29.        ((minuend ^ subtrahend) & minuend).  To prove it, consider the
  30.        following (all operations are bitwise):
  31.  
  32.                                minuend = 100111
  33.                             subtrahend = 101011
  34.                            ---------------------
  35.                                   XOR => 001100
  36.                                minuend = 100111
  37.                            ---------------------
  38.                                     & => 000100
  39.  
  40.       which is the member in the minuend that is not in the subtrahend.
  41.     */
  42.  
  43.     /* The set, 'difference' must be at least the size of the minuend.
  44.        Check this.
  45.     */
  46.     if(temp.set_size < minuend->set_size)
  47.         return FAILURE;
  48.     else
  49.         {
  50.         temp.set_size = minuend->set_size;
  51.         temp.member_recs = minuend->member_recs;
  52.         }
  53.  
  54.     /* Now the calculation for the difference...Note that the smaller set
  55.        will have ALL bits at member locations higher than nmembers reset
  56.        to zero.
  57.     */
  58.     for(i=0;i<minuend->member_recs;i++)
  59.         temp.word[i] =
  60.             (minuend->word[i] ^ subtrahend->word[i]) & minuend->word[i];
  61.  
  62.     /* correct the member count in the set record */
  63.     temp.nmembers = set_member_count(&temp);
  64.  
  65.     /* now clear the destination and assign temp */
  66.     set_clear(difference);
  67.     if(set_assign(difference,&temp) == FAILURE)
  68.         return FAILURE;
  69.  
  70.     /* done. */
  71.     return SUCCESS;
  72.  
  73. }  /* end set_difference */
  74.  
  75.