home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 21 / IOPROG_21.ISO / SOFT / SET.ZIP / set.cpp
Encoding:
C/C++ Source or Header  |  1997-09-19  |  13.3 KB  |  423 lines
  1.  
  2.      #if !defined(_SourceSet_h)
  3.      #define _SourceSet_h
  4.  
  5.      #pragma hdrstop
  6.  
  7.      #include <_null.h>
  8.  
  9.      template <class T>
  10.      class typeSet;
  11.  
  12.      ///////////////////////////////////////////////////////////////////////////////
  13.      // Class node
  14.      // ======
  15.      // Attributes-----
  16.      // private
  17.      //  data     Field to contain information kept by the node.
  18.      //  link     Field to link node to other nodes of same type.
  19.      //
  20.      // Methods--------
  21.      // private
  22.      //  CONSTRUCTOR: Assign values for data and link.
  23.      //  DESTRUCTOR:  none.
  24.      //
  25.      template<class T>
  26.      class node {
  27.         friend class typeSet<T>;
  28.  
  29.         public:
  30.            node (T item, node* nodePtr = NULL) {
  31.               data = item;
  32.               link = nodePtr;
  33.            } // end node;
  34.            ~node() {}
  35.  
  36.            T data;      // Data to be stored in the node.
  37.            node* link;  // Link to the next node.
  38.  
  39.      }; // end node
  40.  
  41.  
  42.      ///////////////////////////////////////////////////////////////////////////////
  43.      // Class typeSet
  44.      // ===========
  45.      // Attributes-----
  46.      // private
  47.      //  frontPtr     Contains pointer to first node in the list.
  48.      //  count        The number of nodes contained in the list.
  49.      //
  50.      // Methods--------
  51.      // private
  52.      //  pointto      Point to ith item in a list.
  53.      //
  54.      // public
  55.      //  CONSTRUCTOR:    Assign NULL value to new set.
  56.      //                  set count to zero (0).
  57.      //  DESTRUCTOR:     Call function clear (deallocate all nodes
  58.      //                  and set count to zero).
  59.      //  search          Search the list for a node (return -1 if not found).
  60.      //  clear           Delete all the nodes, set count to zero.
  61.      //  isEmpty         Return true or false depending on if the list is empty.
  62.      //  isMember        Return true if node is in the list.
  63.      //  isSubset        Return true if set A is a subset of set B.
  64.      //  isProperSubset  Return true if set A is a subset of set B.
  65.      //  extentOf        Return the number of nodes in the list.
  66.      //  operator -      Return the difference of two sets.
  67.      //  operator ||     Return the union of a two sets.
  68.      //  operator &&     Return the intersection of two sets.
  69.      //  operator =      set one set equal to another set.
  70.      //  operator +=     Add an item to the set.
  71.      //  operator -=     Delete an item from the set.
  72.      //  operator ==     Return true or false depending on sets equality.
  73.      //  operator <<     Display the list.
  74.      //
  75.      template<class T>
  76.      class typeSet {
  77.         private:
  78.            node<T>*  frontPtr;  // Pointer to front of the set.
  79.            unsigned int count;  // Number of nodes in the set.
  80.  
  81.            // Point to the ith node in the set.
  82.            node<T>* pointto(unsigned int);
  83.  
  84.         public:
  85.            typeSet () {
  86.               frontPtr = NULL;
  87.               count = 0;
  88.            } // end list constructor
  89.            ~typeSet() { clear(); }
  90.  
  91.            bool isEmpty();
  92.            bool isMember(T);
  93.            int search(T);
  94.            unsigned extentOf() { return count; }
  95.            void clear();
  96.            typeSet<T>& operator +=(T);
  97.            typeSet<T>& operator -=(T);
  98.            typeSet<T>& operator =(typeSet<T>&);
  99.            friend bool isSubset(typeSet<T>&, typeSet<T>&);
  100.            friend bool isProperSubset(typeSet<T>&, typeSet<T>&);
  101.            friend bool operator ==(typeSet<T>&, typeSet<T>&);
  102.            friend typeSet<T> operator -(typeSet<T>&, typeSet<T>&);
  103.            friend typeSet<T> operator ||(typeSet<T>&, typeSet<T>&);
  104.            friend typeSet<T> operator &&(typeSet<T>&, typeSet<T>&);
  105.            friend ostream& operator <<(ostream& os, typeSet<T>&);
  106.  
  107.      }; // end class typeSet
  108.  
  109.  
  110.      ////////////////////////////////////////////////////////////////////////////
  111.      // typeSet                                                       operator ==
  112.      // =====
  113.      // Test the equality of the set.
  114.      //
  115.      template<class T>
  116.      bool operator ==(typeSet<T>& s1, typeSet<T>& s2) {
  117.         node<T> *chaser = s1.frontPtr;
  118.  
  119.         // Test each member of set A to see if it is in set B
  120.         while (chaser != NULL) {
  121.            // If a member from s1 is not in s2 the sets are not equal.
  122.            if (!s2.isMember(chaser-> data))
  123.               return false;
  124.               chaser = chaser-> link;
  125.         } // end while
  126.  
  127.         // The sets are equal.
  128.         return true;
  129.      } // end operator ==
  130.  
  131.  
  132.      ////////////////////////////////////////////////////////////////////////////
  133.      // typeSet                                                       operator <<
  134.      // =====
  135.      // Display the set.
  136.      //
  137.      template<class T>
  138.      ostream& operator <<(ostream& os, typeSet<T>& s) {
  139.         node<T>* chaser = s.frontPtr;
  140.         // Output the right bracket.
  141.         os << "{";
  142.  
  143.         // If the set is not empty output it's members.
  144.         if (!s.isEmpty()) {
  145.            os << chaser-> data;
  146.            chaser = chaser-> link;
  147.            while (chaser != NULL) {
  148.               os << "," << chaser-> data;
  149.               chaser = chaser-> link;
  150.            } // end while
  151.         } // end if
  152.  
  153.         // Output the left bracket.
  154.         os << "}";
  155.  
  156.         return os;
  157.      } // end operator <<
  158.  
  159.  
  160.      ////////////////////////////////////////////////////////////////////////////
  161.      // typeSet                                                        operator =
  162.      // =====
  163.      // Make this set equal to another set.
  164.      //
  165.      template<class T>
  166.      typeSet<T>& typeSet<T>::operator =(typeSet<T>& s) {
  167.         node<T> *chaser = s.frontPtr;
  168.  
  169.         clear();
  170.         while (chaser!= NULL) {
  171.            // Insert the new member from source.
  172.            *this += chaser-> data;
  173.            // Get the next member.
  174.            chaser = chaser->link;
  175.         } // end while
  176.  
  177.         return *this;
  178.      } // end operator =
  179.  
  180.  
  181.      ////////////////////////////////////////////////////////////////////////////
  182.      // typeSet                                                       operator =-
  183.      // =====
  184.      // Remove a set member.
  185.      //
  186.      template<class T>
  187.      typeSet<T>&  typeSet<T>::operator -=(T item) {
  188.         node<T> *chaser = frontPtr, *prevLink = NULL;
  189.  
  190.         // Search for the item.
  191.         while (chaser!=NULL) {
  192.            // Check equality of item vs node data.
  193.            if (chaser->data == item) {
  194.            // Item found, now delete it.
  195.  
  196.               // Remove the front of the list.
  197.               if (prevLink == NULL)
  198.                  frontPtr = chaser-> link;
  199.  
  200.               // Remove from the back of the list.
  201.               else if (chaser-> link == NULL)
  202.                  prevLink-> link = NULL;
  203.  
  204.               // Remove from middle of the list.
  205.               else
  206.                  prevLink-> link = chaser-> link;
  207.  
  208.               // Delete the node.
  209.               delete chaser;
  210.  
  211.               // Update the elememt counter.
  212.               count--;
  213.  
  214.               return *this;
  215.            } // end if
  216.            prevLink=chaser;       // Remember the previous node.
  217.            chaser = chaser-> link;
  218.         } // end while
  219.  
  220.         return *this;
  221.  
  222.      } // end operator =-
  223.  
  224.  
  225.      ////////////////////////////////////////////////////////////////////////////
  226.      // typeSet                                                             clear
  227.      // =====
  228.      // Delete all members in the set.
  229.      //
  230.      template<class T>
  231.      void typeSet<T>::clear() {
  232.         node<T>* ptr;
  233.  
  234.         // If set is empty set count to zero and exit.
  235.         if (frontPtr == NULL) {
  236.            count = 0;
  237.            return;
  238.         } // end if
  239.  
  240.         // Delete the front pointer.
  241.         ptr = frontPtr;
  242.         frontPtr = ptr-> link;
  243.         delete ptr;
  244.  
  245.         // Recurse until all nodes are deleted.
  246.         clear();
  247.      } // end clear
  248.  
  249.  
  250.      ////////////////////////////////////////////////////////////////////////////
  251.      // typeSet                                                           isEmpty
  252.      // =====
  253.      // Return true or false depending if set is empty.
  254.      //
  255.      template<class T>
  256.      bool typeSet<T>:: isEmpty() {
  257.  
  258.         // If the front pointer is null the set is empty.
  259.         if (frontPtr == NULL) return true;
  260.         return false;
  261.      } // end isEmpty
  262.  
  263.  
  264.      ////////////////////////////////////////////////////////////////////////////
  265.      // typeSet                                                          isMember
  266.      // =====
  267.      // Return true or false depending if set is empty.
  268.      //
  269.      template<class T>
  270.      bool typeSet<T>::isMember(T item) {
  271.         if (search(item)==-1)
  272.            return false;
  273.         else
  274.            return true;
  275.      } // end isMember
  276.  
  277.  
  278.      ////////////////////////////////////////////////////////////////////////////
  279.      // typeSet                                                       operator ||
  280.      // =====
  281.      // Perform the union of two sets.
  282.      //
  283.      template<class T>
  284.      typeSet<T> operator ||(typeSet<T>& s1, typeSet<T>& s2) {
  285.         node<T> *chaser = s2.frontPtr;
  286.         while (chaser != NULL) {
  287.           s1 += chaser-> data;
  288.           chaser = chaser-> link;
  289.         } // end while
  290.  
  291.         return s1;
  292.      } // end operator ||
  293.  
  294.  
  295.      ////////////////////////////////////////////////////////////////////////////
  296.      // typeSet                                                       operator &&
  297.      // =====
  298.      // Perform the intersection of two sets.
  299.      //
  300.      template<class T>
  301.      typeSet<T> operator &&(typeSet<T>& s1, typeSet<T>& s2) {
  302.         typeSet<T> temp = s1;
  303.         s1.clear();
  304.  
  305.         node<T> *chaser = s2.frontPtr;
  306.  
  307.         while (chaser != NULL) {
  308.            if (temp.isMember(chaser-> data))
  309.               s1 += chaser-> data;
  310.            chaser = chaser-> link;
  311.         } // end while
  312.  
  313.         return s1;
  314.      } // end operator &&
  315.  
  316.  
  317.      ////////////////////////////////////////////////////////////////////////////
  318.      // typeSet                                                          isSubset
  319.      // =====
  320.      // Return true if a given set is a subset of this set.
  321.      //
  322.      template<class T>
  323.      bool isSubset(typeSet<T>& s1, typeSet<T>& s2) {
  324.         node<T> *chaser = s2.frontPtr;
  325.  
  326.         if (s2.isEmpty()) return false;
  327.  
  328.         while (chaser != NULL) {
  329.            if(!s1.isMember(chaser-> data))
  330.               return false;
  331.            chaser = chaser-> link;
  332.         } // end while
  333.  
  334.         return true;
  335.      } // end isSubset
  336.  
  337.  
  338.      ////////////////////////////////////////////////////////////////////////////
  339.      // typeSet                                                    isProperSubset
  340.      // =====
  341.      // Return true if a given set is a proper subset of this set.
  342.      //
  343.      template<class T>
  344.      bool isProperSubset(typeSet<T>& s1, typeSet<T>& s2) {
  345.         // Check if the two sets are equal
  346.         if (!(s1 == s2))
  347.            return isSubset(s1, s2);
  348.         else
  349.            return false;
  350.      } // end isSubset
  351.  
  352.  
  353.      ////////////////////////////////////////////////////////////////////////////
  354.      // typeSet                                                        operator -
  355.      // =====
  356.      // Perform the difference of two sets.
  357.      //
  358.      template<class T>
  359.      typeSet<T> operator -(typeSet<T>& s1, typeSet<T>& s2) {
  360.         node<T> *chaser = s2.frontPtr;
  361.  
  362.         while (chaser != NULL) {
  363.            if (s1.isMember(chaser-> data))
  364.               s1 -= chaser-> data;
  365.            chaser = chaser-> link;
  366.         } // end while
  367.  
  368.         return s1;
  369.      } // end operator &&
  370.  
  371.  
  372.      ////////////////////////////////////////////////////////////////////////////
  373.      // typeSet                                                            search
  374.      // =====
  375.      // Search for and return the index of a member. Return -1 if not found.
  376.      //
  377.      template<class T>
  378.      int typeSet<T>::search(T item) {
  379.         node<T> *chaser = frontPtr;
  380.  
  381.         // Search through the set until a item is found.
  382.         for (int p = 0; p < count; p++) {
  383.            // Check equality of item vs node data.
  384.            if (chaser-> data == item) return p;
  385.            chaser = chaser-> link;
  386.         } // end for
  387.  
  388.         // Item not found return -1.
  389.         return -1;
  390.  
  391.      } // end search
  392.  
  393.  
  394.      ////////////////////////////////////////////////////////////////////////////
  395.      // typeSet                                                       operator +=
  396.      // =====
  397.      // Add a member to the set.
  398.      //
  399.      template<class T>
  400.      typeSet<T>& typeSet<T>::operator +=(T item) {
  401.         node<T> *tempPtr;
  402.  
  403.         if (!isMember(item)) {
  404.            // Create a new node with link being assigned frontPtr.
  405.            tempPtr = new node<T>(item, frontPtr);
  406.  
  407.            // Assign front pointer to point to the new node.
  408.            frontPtr = tempPtr;
  409.  
  410.            // Increment the node counter.
  411.            count++;
  412.         } // end if
  413.  
  414.         return *this;
  415.      } // end operator +=
  416.  
  417.      #endif
  418.  
  419.  
  420.  
  421. Copyright 1998,Jeremy Petter. All rights reserved worldwide. The Source shall not be liable in the event of incidental or consequential
  422. damages arising from the use of information supplied herein. 
  423.