home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / set.h < prev    next >
C/C++ Source or Header  |  1995-04-09  |  16KB  |  419 lines
  1.  
  2.  
  3. #ifndef _set_h_
  4. #define _set_h_
  5.  
  6.  
  7.  
  8.  
  9.  
  10. /*
  11.  *
  12.  *          Copyright (C) 1994, M. A. Sridhar
  13.  *  
  14.  *
  15.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  16.  *     to copy, modify or distribute this software  as you see fit,
  17.  *     and to use  it  for  any  purpose, provided   this copyright
  18.  *     notice and the following   disclaimer are included  with all
  19.  *     copies.
  20.  *
  21.  *                        DISCLAIMER
  22.  *
  23.  *     The author makes no warranties, either expressed or implied,
  24.  *     with respect  to  this  software, its  quality, performance,
  25.  *     merchantability, or fitness for any particular purpose. This
  26.  *     software is distributed  AS IS.  The  user of this  software
  27.  *     assumes all risks  as to its quality  and performance. In no
  28.  *     event shall the author be liable for any direct, indirect or
  29.  *     consequential damages, even if the  author has been  advised
  30.  *     as to the possibility of such damages.
  31.  *
  32.  */
  33.  
  34.  
  35.  
  36. // This   is   a  template-based   Set   class, that  maintains   a  set of
  37. // objects. Duplicate objects  are, of course,  not allowed.  The Set class
  38. // allows addition and removal of objects and membership tests.
  39. // 
  40. // It  is also assumed that  (a) the  default  constructor for the BaseType
  41. // class produces a value that can  be treated as  the "null value" of that
  42. // class, (b)   the BaseType  class  supports a  copy  constructor   and an
  43. // assignment operator, and (c)  the BaseType class supports the    Compare
  44. // method. (This is because the set uses  a sorted array representation for
  45. // maximum efficiency.)   Primitive  objects    that do not     support the
  46. // Compare    method,  such as  long and int,  are provided  with "template
  47. // override" methods in basicops.h.
  48. // 
  49. // A SetIterator object is also provided; this object allows inspecting the
  50. // objects contained in  a set, in   ascending order.  It provides  methods
  51. // Reset(), More() and Next(), so  that iteration in  the following form is
  52. // possible:
  53. // \par\begin{verbatim}
  54. //           CL_StringSetIterator iter (my_set);
  55. //           CL_String s;
  56. //           for (iter.Reset(); iter.More(); ) {
  57. //               s = iter.Next();
  58. //               // Process the string s here....
  59. //           }
  60. // \end{verbatim}
  61. // 
  62. // Objects returned  by  the  Next()  method of  the  iterator  may NOT  be
  63. // modified. It is not advisable to add or remove elements from a set while  an
  64. // iterator on the set is active.
  65. // 
  66. // When the Set is instantiated as a container for pointers (as are
  67. // {\tt CL_Set<CL_ObjectPtr>} or CL_ObjectSet), the set
  68. // does {\it not\/} own the objects that the pointers point to, and
  69. // therefore does not delete them when it is destroyed. The {\tt
  70. // DestroyContents} method is provided on {\tt CL_ObjectSet} to
  71. // provide explicit control over destruction of contents.
  72. //
  73. // The implementation uses a sorted {\small\tt CL_Sequence}, so that it is
  74. // possible to create sets with size up to $2^{26}$, or approximately 64
  75. // million, even under MS-Windows, thus alleviating the 64K  limitation
  76. // under MS-Windows (provided, of course, there is enough main memory
  77. // available).
  78.  
  79.  
  80.  
  81.  
  82. #ifdef __GNUC__
  83. #pragma interface
  84. #endif
  85.  
  86.  
  87. #include "base/object.h"
  88. #include "base/sequence.h"
  89. #include "base/iterator.h"
  90.  
  91.  
  92.  
  93. template <class BaseType> class CL_SetIterator;
  94.  
  95. template <class BaseType>
  96. class CL_EXPORT  CL_Set: public CL_Object {
  97.  
  98. public:
  99.  
  100.     // ------------------------ Creation and destruction --------------
  101.  
  102.     CL_Set (CL_ObjectIOFilter* filter = 0);
  103.     // Construct an empty set. Remember the given filter as the means of
  104.     // reading and writing contained objects to streams. If specified, the
  105.     // filter object must exist whenever the set needs to save or restore
  106.     // itself from a stream; the set does not take responsibility for the
  107.     // (memory used by the) filter object.
  108.  
  109.     // CL_Set (const CL_Sequence<BaseType>& s); Borland doesn't like this!
  110.     // Create a set from the given Sequence, using the assignment operator.
  111.     
  112.     CL_Set (const CL_Set<BaseType>&);
  113.     // Copy constructor. If the template parameter {\small\tt BaseType>}
  114.     // is a first-class object, the copy constructor of the {\small\tt
  115.     // BaseType} is used to copy each entry in the set; if it's a
  116.     // pointer, just the pointer is copied.
  117.  
  118.     ~CL_Set ();
  119.     // Destructor.
  120.  
  121.     //
  122.     // ------------------------ Element access ---------------------------
  123.  
  124.     long Size() const;
  125.     // Return the number of objects in the set.
  126.  
  127.     virtual bool Add (const BaseType& o);
  128.     // Add an object to the set. Return true on success.
  129.  
  130.     void operator+= (const BaseType& value);
  131.     // Add the given value into the set.
  132.  
  133.     virtual BaseType Remove (const BaseType& o);
  134.     // Remove the object equal to o from the set (if it's there). Return
  135.     // the removed object if successful, and the null value of the base
  136.     // type if failed. If this set is a pointer-based set, the return
  137.     // value must be destroyed by the caller of this method.
  138.  
  139.     virtual bool Includes (const BaseType& o) const;
  140.     // Determine if object o is in the set.
  141.  
  142.     virtual void MakeEmpty ();
  143.     // Empty the set (i.e., remove all its elements). If this is a
  144.     // pointer-based set, the contained objects are {\it not\/} deleted.
  145.  
  146.     // ------------------- Miscellaneous methods -------------------------
  147.  
  148.     virtual long RankOf (const BaseType& v) const;
  149.     // Return the number of elements in this set that are less than v.
  150.     // The parameter v need not be in the set. The ordering
  151.     // relationship used is that defined by the base
  152.     // type; if the latter does not define a Compare method or an {\tt
  153.     // operator<} method, this method does not return anything useful.
  154.     
  155.     virtual const BaseType& ItemWithRank (long i) const;
  156.     // Given an index $i$ between 0 and Size()-1, return the element of rank
  157.     // $i$, i.e., the element that has $i$ elements less than it in the set.
  158.     // If $i \le 0$, this returns the 
  159.     // smallest element, and if $i \ge {\tt Size()}$, this returns the
  160.     // largest element.
  161.     //
  162.     // This is a const method; even if this
  163.     // is a set of pointers, it is not safe to modify the object pointed
  164.     // to by the return value because the set's internal representation
  165.     // may be affected and its algorithms may perform incorrectly.
  166.     //   Note that it is possible to iterate through the elements of the set
  167.     // via calls to this method, varying the index from 0 to Size()-1;
  168.     // however, depending on the implementation, this may lead to very
  169.     // inefficient iteration. Use of the SetIterator is the recommended way
  170.     // to inspect all elements of the set.
  171.  
  172.     const BaseType& Smallest () const {return ItemWithRank(0);};
  173.     // Return the smallest element in the set; return the null value of
  174.     // the base type if the set is empty.
  175.     
  176.     const BaseType& Largest () const;
  177.     // Return the largest element in the set; return the null value of
  178.     // the base type if the set is empty.
  179.     
  180.     // ------------------- Manipulation of sets ------------------------
  181.  
  182.     CL_Sequence<BaseType> AsSequence() const;
  183.     // Return a sequence containing our data in ascending order.
  184.     
  185.     operator CL_Sequence<BaseType>  () const;
  186.     // Return a sequence containing our data in ascending order. The
  187.     // implementation simply invokes AsSequence() and returns its value.
  188.     
  189.     virtual bool operator== (const CL_Set<BaseType>& o) const;
  190.     // Check if object o is the same as this set.
  191.  
  192.     virtual bool operator== (const CL_Object& o) const;
  193.     // Check if object o is the same as this set.
  194.  
  195.     
  196.     // ----- Assignments
  197.  
  198.     virtual CL_Set<BaseType>& operator= (const CL_Set<BaseType>& s);
  199.     // Assign the  given set to this one. If the template
  200.     // parameter {\small\tt BaseType>} 
  201.     // is a first-class object, the copy constructor of the {\small\tt
  202.     // BaseType} is used to copy each entry in the set s; if it's a
  203.     // pointer, just the pointer is copied.
  204.  
  205.  
  206.     virtual void operator= (const CL_Sequence<BaseType>&);
  207.     // Assign  the given sequence to  this set, with  duplicates removed.  If
  208.     // the {\small\tt  BaseType} of this sequence is  a pointer, the pointers
  209.     // are copied  into the returned  set; if the  {\small\tt  BaseType} is a
  210.     // first-class object,  the copy  constructor of the {\small\tt BaseType}
  211.     // is used   to  copy the  objects   into the returned  set.   Removal of
  212.     // duplicates is done using BaseType's == operator.
  213.  
  214.     void operator= (const CL_Object& o);
  215.     // Override method inherited from CL_Object.
  216.  
  217.  
  218.     virtual CL_Set<BaseType> operator+   (const CL_Set<BaseType>& o) const;
  219.     // Return the set containing all elements in either this set or o. The
  220.     // implementation uses an algorithm that performs $m + n$ pointer
  221.     // moves and as many comparisons, where $m$ and $n$ are the sizes of
  222.     // this set and {\small\tt o}.
  223.     
  224.     virtual void operator+= (const CL_Set<BaseType>& o);
  225.     // Add all elements in o to this set; return a reference to this set.
  226.     
  227.     virtual CL_Set<BaseType> operator* (const CL_Set<BaseType>& o) const; 
  228.     // Intersection: Return the set containing the elements common between
  229.     // this set and o. The
  230.     // implementation uses an algorithm that performs $m + n$ pointer
  231.     // moves and as many comparisons, where $m$ and $n$ are the sizes of
  232.     // this set and {\small\tt o}.
  233.         
  234.     virtual void operator*= (const CL_Set<BaseType>& o);
  235.     // Replace this set by its intersection with o.
  236.     
  237.     virtual CL_Set<BaseType> operator-   (const CL_Set<BaseType>& o) const;
  238.     // Difference: return the set obtained by removing from this set those
  239.     // elements that are common with o. The
  240.     // implementation uses an algorithm that performs $m + n$ pointer
  241.     // moves and as many comparisons, where $m$ and $n$ are the sizes of
  242.     // this set and {\small\tt o}.
  243.     
  244.     virtual void operator-= (const CL_Set<BaseType>& o);
  245.     // Remove from this set the elements in common with o.
  246.  
  247.     virtual CL_Set<BaseType> operator^   (const CL_Set<BaseType>& o) const;
  248.     // Symmetric difference (exclusive-or): return the set containing those
  249.     // elements that are either in this set or in {\tt o}, but nor both. The
  250.     // implementation uses an algorithm that performs $m + n$ pointer
  251.     // moves and as many comparisons, where $m$ and $n$ are the sizes of
  252.     // this set and {\small\tt o}.
  253.     
  254.     virtual void operator^= (const CL_Set<BaseType>& o);
  255.  
  256.     virtual bool IncludesAll (const CL_Set<BaseType>& s) const;
  257.     // Return true if this set contains all elements of the given set. The
  258.     // algorithm performs as many comparisons as the sum of the sizes of
  259.     // this set and the given set.
  260.     
  261.     //
  262.     // ---------------------- Storage and retrieval ----------------------
  263.     //
  264.  
  265.     long StorableFormWidth() const;
  266.     // Override the method inherited from {\small\tt CL_Object}.
  267.  
  268.     bool ReadFrom (const CL_Stream&);
  269.     // Override the method inherited from {\small\tt CL_Object}.
  270.  
  271.     bool WriteTo  (CL_Stream&) const;
  272.     // Override the method inherited from {\small\tt CL_Object}.
  273.  
  274.     
  275.  
  276.     //
  277.     // ------------------------- Basic methods --------------------
  278.     //
  279.     CL_Object* Clone () const
  280.         {return new CL_Set<BaseType> (*this);};
  281.     // Override the method inherited from {\small\tt CL_Object}.
  282.     
  283.     const char* ClassName() const {return "CL_Set";};
  284.     // Override the method inherited from {\small\tt CL_Object}.
  285.     
  286.     CL_ClassId ClassId() const
  287.         { return _CL_Set_CLASSID;};
  288.     // Override the method inherited from {\small\tt CL_Object}.
  289.  
  290.  
  291.  
  292.     // -------------------- End public protocol ---------------------------
  293.  
  294.     
  295. protected:
  296.  
  297.     // ---------------------- Friend declarations -----------------------
  298.     
  299.     friend CL_SetIterator<BaseType>;
  300.  
  301.     
  302.     // ----------------------- Instance variables -----------------------
  303.     
  304.     void*              _idata;   // Representation of the Set
  305.     CL_ObjectIOFilter* _filter;
  306.     BaseType           _null;    // I wish this could be a static instance
  307.                                  // var, but GCC doesn't implement static
  308.                                  // template inst vars :-(
  309.  
  310.     
  311.     // ------------------------ Protected methods ----------------------
  312.     
  313.     CL_Set (void* p);
  314.     // Protected constructor, for use by derived classes. This constructor
  315.     // assumes that its parameter p is the data representation, and sets
  316.     // _idata to p.
  317.  
  318.     virtual bool       _ReadElement (const CL_Stream& s, BaseType& e);
  319.     // Read an element e of the set from the stream. This method
  320.     // is used by {\tt ReadFrom}. The return value is TRUE if the
  321.     // operation succeeds, and FALSE otherwise. The default implementation
  322.     // simply calls {\tt CL_RestoreFrom} in {\tt basicops.h}.
  323.     
  324.     virtual bool       _WriteElement (CL_Stream& s, const BaseType& e) const;
  325.     // Write an element e of the set to the stream. This method
  326.     // is used by {\tt WriteTo}. The return value is TRUE if the
  327.     // operation succeeds, and FALSE otherwise. The default implementation
  328.     // simply calls {\tt CL_SaveTo} in {\tt basicops.h}.
  329.     
  330.     
  331. };
  332.  
  333.  
  334.  
  335.  
  336. template <class BaseType>
  337. class CL_EXPORT  CL_SetIterator: public CL_Iterator <BaseType> {
  338.  
  339. public:
  340.  
  341.     CL_SetIterator (const CL_Set<BaseType>& s);
  342.     // Constructor. The parameter specifies the set to be inspected.
  343.  
  344.     CL_SetIterator (const CL_SetIterator<BaseType>& itr);
  345.     // Copy constructor. The copy inspects the same set as {\tt itr}, and
  346.     // (unless reset) begins  its iteration at the same object that itr is
  347.     // currently positioned.
  348.     
  349.     virtual void Reset();
  350.  
  351.     virtual void BeginFromRank (long i);
  352.     // Start the iteration so that the first call to {\tt Next} returns the
  353.     // element of rank i. Thus {\tt BeginFromRank(0)} is equivalent to {\tt
  354.     // Reset()}.
  355.     
  356.     virtual bool More();
  357.  
  358.     virtual const BaseType& Next();
  359.  
  360.     virtual const char* ClassName () const {return "CL_SetIterator";};
  361.     
  362.  
  363. protected:
  364.     const CL_Set<BaseType>& _set;
  365.     long                    _index;
  366.  
  367. };
  368.  
  369.  
  370.  
  371.  
  372.  
  373. // template <class BaseType>
  374. // inline CL_Set<BaseType>::CL_Set  (const CL_Sequence<BaseType>& seq)
  375. // {
  376. //     *this = seq;
  377. // }
  378.  
  379.  
  380.  
  381.  
  382. template <class BaseType>
  383. inline long CL_Set<BaseType>::StorableFormWidth () const
  384. {
  385.     return sizeof (CL_ClassId) +
  386.         (*(CL_Sequence<BaseType> *)_idata).StorableFormWidth ();
  387. }
  388.  
  389. template <class BaseType>
  390. inline const BaseType& CL_Set<BaseType>::Largest () const
  391. {
  392.     return ItemWithRank(Size()-1);
  393. }
  394.  
  395.  
  396.  
  397. template <class BaseType>
  398. inline bool CL_Set<BaseType>::operator== (const CL_Object& o) const
  399. {
  400.     return ClassId() == o.ClassId() && *this == ((const CL_Set<BaseType>&) o);
  401. }
  402.  
  403.  
  404. template <class BaseType>
  405. inline CL_Sequence<BaseType> CL_Set<BaseType>::AsSequence () const
  406. {
  407.     return *(CL_Sequence<BaseType>*)_idata;
  408. }
  409.  
  410. template <class BaseType>
  411. inline CL_Set<BaseType>::operator CL_Sequence<BaseType>  () const
  412. {
  413.     return AsSequence ();
  414. }
  415.  
  416. #endif /* _set_h_ */
  417.  
  418.  
  419.