home *** CD-ROM | disk | FTP | other *** search
/ World of Shareware - Software Farm 2 / wosw_2.zip / wosw_2 / CPROG / SETCLASS.ZIP / OOSET.CPP next >
Text File  |  1991-11-01  |  7KB  |  391 lines
  1. // File ooset.cpp
  2. // Source file for class set
  3.  
  4. #    if !defined( __OOSET_H )
  5. #        include "ooset.h"
  6. #    endif
  7.  
  8. // Empty set constructor
  9. set::set()
  10. {
  11.     min = MINIMUM;
  12.     max = MAXIMUM;
  13.     len = max - min + 1;
  14.  
  15.     if( len <= 0 )
  16.         ptr = NULL;
  17.  
  18.     else
  19.     {
  20.         if( ! ( ptr = new char[ len ] ) )
  21.         {
  22.             cerr << "\nMemory allocation failure. Program terminated";
  23.             exit(1);
  24.         }
  25.         memset( ptr, FALSE, len );
  26.     }
  27. }
  28.  
  29. // Singleton set constructor
  30. set::set( int num )
  31. {
  32.     min = MINIMUM;
  33.     max = MAXIMUM;
  34.     len = max - min + 1;
  35.  
  36.     if( ( num < min ) || ( num > max ) )                //Check range
  37.         ptr = NULL;
  38.  
  39.     else
  40.     {
  41.         if( ! ( ptr = new char[ len ] ) )
  42.         {
  43.             cerr << "\nMemory allocation failure. Program terminated";
  44.             exit(1);
  45.         }
  46.  
  47.         memset( ptr, FALSE, len );
  48.         ptr[ num - min ] = TRUE ;                        //Set "bit"
  49.     }
  50. }
  51.  
  52.  
  53. // Assignment
  54. set& set::operator= ( const set& set_two )
  55. {
  56.     if ( this == &set_two )
  57.         return ( *this );
  58.  
  59.     else
  60.     {
  61.         len = set_two.len;
  62.         min = set_two.min;
  63.         max = set_two.max;
  64.         delete ptr;
  65.  
  66.         if( ! ( ptr = new char[ len ] ) )
  67.         {
  68.             cerr << "\nMemory allocation failure. Program terminated";
  69.             exit(1);
  70.         }
  71.  
  72.         memcpy( ptr, set_two.ptr, len );
  73.         return ( *this );
  74.     }
  75. }
  76.  
  77. // Copy Constructor
  78. set::set( const set& s )
  79. {
  80.     if( s.ptr == NULL)
  81.         ptr = NULL;
  82.  
  83.     else
  84.     {
  85.         len = s.len;
  86.         min = s.min;
  87.         max = s.max;
  88.  
  89.         if( ! ( ptr = new char[ s.len ] ) )
  90.         {
  91.             cerr << "\nMemory allocation failure. Program terminated";
  92.             exit(1);
  93.         }
  94.  
  95.         memcpy( ptr, s.ptr, s.len );
  96.     }
  97. }
  98.  
  99. // Union of two sets ( BINARY + )
  100. // The union of set A and set B is the set of elements I that belong
  101. // to either A or B or both A and B
  102. set operator+ ( const set& set_one, const set& set_two )
  103. {
  104.     if( set_one.len == 0 )
  105.         return set_two;
  106.  
  107.     else if( set_two.len == 0 )
  108.         return set_one;
  109.  
  110.     else
  111.     {
  112.         set set_three = set_one;
  113.  
  114.         for( int i = 0; i < set_three.len; i++ )
  115.         {
  116.             if( set_two.ptr[i] )
  117.                 set_three.ptr[i] = TRUE;
  118.         }
  119.     return set_three;
  120.     }
  121. }
  122.  
  123. // Union of two sets ( BINARY += )
  124. // The union of set A and set B is the set of elements I that belong
  125. // to either A or B or both A and B
  126. set& set::operator+= ( const set& set_two )
  127. {
  128.     set temp;
  129.     temp = *this + set_two;
  130.     *this = temp;
  131.     return ( *this );
  132. }
  133.  
  134. // Complement of a set ( UNARY - )
  135. // The complement of set A  is the set of elements in the range of the set
  136. // A that do not belong to set A
  137. set operator- ( const set& s )
  138. {
  139.     set complement = s;
  140.  
  141.     for( int i = 0; i < complement.max - complement.min + 1; i++ )
  142.         complement.ptr[ i ] = ! s.ptr[ i ];
  143.  
  144.     return ( complement );
  145. }
  146.  
  147. // Difference of two sets ( BINARY - )
  148. // The difference of set A and set B is the set of elements I that belong
  149. // to set A but not set B
  150. set operator- ( const set& set_one, const set& set_two )
  151. {
  152.     if( set_one.len == 0 )
  153.         return set_one;
  154.  
  155.     else if( set_two.len == 0 )
  156.         return set_one;
  157.  
  158.     else
  159.     {
  160.         set set_three;
  161.         set_three.len = set_one.len;
  162.  
  163.         int jmin = 0;
  164.  
  165.         for( int i = 0; i < set_one.len; i++ )
  166.         {
  167.             int match = FALSE;
  168.  
  169.             if( set_one.ptr[i] )
  170.             {
  171.                 for( int j = jmin; j < set_two.len; j++ )
  172.                 {
  173.                     if( set_two.ptr[j] )
  174.                     {
  175.                         if( set_one.min + i == set_two.min + j )
  176.                         {
  177.                             jmin = j + 1;
  178.                             match = TRUE;
  179.                             break;
  180.                         }
  181.                     }
  182.  
  183.                     if( set_two.min + j >= set_one.min + i )
  184.                     {
  185.                         jmin = j + 1;
  186.                         break;
  187.                     }
  188.  
  189.                 }
  190.  
  191.                 if( ! match )
  192.                     set_three.ptr[i] = TRUE;
  193.             }
  194.         }
  195.     return set_three;
  196.     }
  197. }
  198.  
  199. // Difference of two sets ( BINARY -= )
  200. // The difference of set A and set B is the set of elements I that belong
  201. // to set A but not set B
  202. set& set::operator-= ( const set& set_two )
  203. {
  204.     set temp;
  205.     temp = *this - set_two;
  206.     *this = temp;
  207.     return ( *this );
  208. }
  209.  
  210. // Intersection of two sets ( BINARY * )
  211. // The intersection of set A and set B is the set of elements I that
  212. // belong to both set A and set B
  213. set operator* ( const set& set_one, const set& set_two )
  214. {
  215.     if( set_one.len == 0 )
  216.         return NULL;
  217.  
  218.     else if( set_two.len == 0 )
  219.         return NULL;
  220.  
  221.     else
  222.     {
  223.         set set_three;
  224.         set_three.len = set_one.len;
  225.  
  226.         int jmin = 0;
  227.  
  228.         for( int i = 0; i < set_one.len; i++ )
  229.         {
  230.             if( set_one.ptr[i] )
  231.             {
  232.                 for( int j = jmin; j < set_two.len; j++ )
  233.                 {
  234.                     if( set_two.ptr[j] )
  235.                     {
  236.                         if( set_one.min + i == set_two.min + j )
  237.                         {
  238.                             jmin = j + 1;
  239.                             set_three.ptr[i] = TRUE;
  240.                             break;
  241.                         }
  242.                     }
  243.  
  244.                     if( set_two.min + j >= set_one.min + i )
  245.                     {
  246.                         jmin = j + 1;
  247.                         break;
  248.                     }
  249.                 }
  250.             }
  251.         }
  252.  
  253.     return set_three;
  254.     }
  255. }
  256.  
  257. // Intersection of two sets ( BINARY *= )
  258. // The intersection of set A and set B is the set of elements I that
  259. // belong to both set A and set B
  260. set& set::operator*= ( const set& set_two )
  261. {
  262.     set temp;
  263.     temp = *this * set_two;
  264.     *this = temp;
  265.     return ( *this );
  266. }
  267.  
  268. // Equality of two sets ( == )
  269. // Set A and set B are equal if they have the same elements over the
  270. // same range
  271. BOOLEAN operator== ( const set& set_one, const set& set_two )
  272. {
  273.     int jmin = 0;
  274.  
  275.     for( int i = 0; i < set_one.len; i++ )
  276.     {
  277.         if( set_one.ptr[ i ] )
  278.         {
  279.             for( int j = jmin; j < set_two.len; j++ )
  280.             {
  281.                 if( set_two.ptr[ j ] )
  282.                 {
  283.                     if( set_one.min + i != set_two.min + j )
  284.                         return FALSE;
  285.  
  286.                     else
  287.                     {
  288.                         jmin = j + 1;
  289.                         break;
  290.                     }
  291.                 }
  292.             }
  293.         }
  294.  
  295.     }
  296.     return TRUE;
  297. }
  298.  
  299. // Inequality of two sets ( != )
  300. // Set A and set B are not equal if they don't have the same elements
  301. // over the same range
  302. BOOLEAN operator!= ( const set& set_one, const set& set_two )
  303. {
  304.     if( set_one == set_two )
  305.         return FALSE;
  306.     else
  307.         return TRUE;
  308. }
  309.  
  310. // Compare set A less than B ( < )
  311. // Set A is a subset of set B if every element of set A is also an element
  312. // of set B.
  313. BOOLEAN operator< ( const set& set_one, const set& set_two )
  314. {
  315.     int jmin = 0;
  316.  
  317.     for( int i = 0; i < set_one.len; i++ )
  318.     {
  319.         if( set_one.ptr[ i ] )
  320.         {
  321.             for( int j = jmin; j < set_two.len; j++ )
  322.             {
  323.                 if( set_two.ptr[ j ] )
  324.                 {
  325.                     if( set_one.min + i == set_two.min + j )
  326.                     {
  327.                         jmin = j + 1;
  328.                         break;
  329.                     }
  330.  
  331.                     else if( set_two.min + j  > set_one.min + i )
  332.                         return FALSE;
  333.                 }
  334.             }
  335.         }
  336.  
  337.     }
  338.     return TRUE;
  339. }
  340.  
  341.  
  342. // Compare set A greater than B ( > )
  343. // Set B is a subset of set A if every element of set B is also an element
  344. // of set A.
  345. BOOLEAN operator> ( const set& set_one, const set& set_two )
  346. {
  347.     return ( set_two < set_one );
  348. }
  349.  
  350. // Compare set A greater than or equal to set B ( >= )
  351. BOOLEAN operator>= ( const set& set_one, const set& set_two )
  352. {
  353.     return ( set_two < set_one );
  354. }
  355.  
  356. // Compare set A less than or equal to set B ( <= )
  357. BOOLEAN operator<= ( const set& set_one, const set& set_two )
  358. {
  359.     return ( set_one < set_two );
  360. }
  361.  
  362. //  String output
  363. ostream& operator<< ( ostream& stream, const set& data )
  364. {
  365.     BOOLEAN first = TRUE;
  366.     BOOLEAN empty = TRUE;
  367.  
  368.     stream << "{ ";
  369.  
  370.     for( int i = 0; i < data.len; i++ )
  371.     {
  372.  
  373.         if( data.ptr[i] )
  374.         {
  375.             if( ! first )
  376.                 stream << ", ";
  377.  
  378.             stream << ( data.min + i );
  379.  
  380.             first = FALSE;
  381.             empty = FALSE;
  382.         }
  383.  
  384.     }
  385.  
  386.     if ( empty )
  387.         stream << "NULL";
  388.  
  389.     stream << " }\n";
  390.     return stream;
  391. }