home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 10 Tools / 10-Tools.zip / yacl-012.zip / base / setimp.cxx < prev    next >
C/C++ Source or Header  |  1995-04-09  |  16KB  |  691 lines
  1.  
  2.  
  3.  
  4.  
  5. /*
  6.  *
  7.  *          Copyright (C) 1994, M. A. Sridhar
  8.  *  
  9.  *
  10.  *     This software is Copyright M. A. Sridhar, 1994. You are free
  11.  *     to copy, modify or distribute this software  as you see fit,
  12.  *     and to use  it  for  any  purpose, provided   this copyright
  13.  *     notice and the following   disclaimer are included  with all
  14.  *     copies.
  15.  *
  16.  *                        DISCLAIMER
  17.  *
  18.  *     The author makes no warranties, either expressed or implied,
  19.  *     with respect  to  this  software, its  quality, performance,
  20.  *     merchantability, or fitness for any particular purpose. This
  21.  *     software is distributed  AS IS.  The  user of this  software
  22.  *     assumes all risks  as to its quality  and performance. In no
  23.  *     event shall the author be liable for any direct, indirect or
  24.  *     consequential damages, even if the  author has been  advised
  25.  *     as to the possibility of such damages.
  26.  *
  27.  */
  28.  
  29.  
  30.  
  31. #ifndef _setimp_cxx_
  32. #define _setimp_cxx_
  33.  
  34.  
  35. #ifdef __GNUC__
  36. #pragma implementation
  37. #endif
  38.  
  39.  
  40.  
  41. #include "base/bytstrng.h"
  42. #include "base/basicops.h"
  43. #include "base/stream.h"
  44.  
  45. #include "base/set.h"
  46.  
  47. #define NEW_OP new
  48.  
  49.  
  50. #ifdef __BORLANDC__
  51. #pragma warn -lvc
  52. #include <stdio.h>
  53. #endif
  54.  
  55.  
  56. template <class BaseType>
  57. CL_Set<BaseType>::CL_Set(CL_ObjectIOFilter* filter)
  58. {
  59.     _idata = new CL_Sequence<BaseType>;
  60.     _filter = filter;
  61.     _null  = CL_Basics<BaseType>::NullValue ();
  62. }
  63.  
  64.  
  65. template <class BaseType>
  66. CL_Set<BaseType>::~CL_Set()
  67. {
  68.     if (_idata)
  69.         delete ((CL_Sequence<BaseType>*)_idata);
  70. }
  71.  
  72.  
  73. /*----------------------------------------------------------------------- */
  74.  
  75. template <class BaseType>
  76. CL_Set<BaseType>::CL_Set(void* p)
  77. {
  78.     _idata = p;
  79.     _filter = NULL;
  80. }
  81.  
  82.  
  83.  
  84. /*----------------------------------------------------------------------- */
  85.  
  86.  
  87.  
  88. template <class BaseType>
  89. CL_Set<BaseType>::CL_Set (const CL_Set<BaseType>& s)
  90. {
  91.     _idata = new CL_Sequence<BaseType>;
  92.     _filter = s._filter;
  93.     *this = s;
  94. }
  95.  
  96.  
  97.  
  98.  
  99.  
  100.  
  101. /*----------------------------------------------------------------------- */
  102.  
  103.  
  104. //
  105. // Add an object to the set. Return true on success.
  106. //
  107. template <class BaseType>
  108. bool CL_Set<BaseType>::Add (const BaseType& o)
  109. {
  110.     if (!_idata || !PrepareToChange())
  111.         return FALSE;
  112.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  113.     long index = 0;
  114.     if (_data.BinarySearch (o, index))
  115.         return FALSE;
  116.     BaseType obj = o;
  117.     if (_data.Insert (obj, index)) {
  118.         Notify ();
  119.         return TRUE;
  120.     }
  121.     return FALSE;
  122. }
  123.  
  124.  
  125.  
  126.  
  127.  
  128. /*----------------------------------------------------------------------- */
  129. // Remove the object equal to o from the set (if it's there). Return
  130. // true on success.
  131. template <class BaseType>
  132. BaseType CL_Set<BaseType>::Remove (const BaseType& o)
  133. {
  134.     if (!_idata || !PrepareToChange())
  135.         return  CL_Basics<BaseType>::NullValue ();
  136.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  137.     long i;
  138.     BaseType p;
  139.     if (!_data.BinarySearch (o, i))
  140.         return  CL_Basics<BaseType>::NullValue ();
  141.     p = _data.Remove (i);
  142.     Notify ();
  143.     return p;
  144. }
  145.  
  146.  
  147.  
  148.  
  149. template <class BaseType>
  150. long CL_Set<BaseType>::Size () const
  151. {
  152.     return ((CL_Sequence<BaseType>*) _idata)->Size();
  153. }
  154.  
  155.  
  156.  
  157.  
  158.  
  159. /*----------------------------------------------------------------------- */
  160. template <class BaseType>
  161. void CL_Set<BaseType>::MakeEmpty ()
  162. {
  163.     if (!_idata || !PrepareToChange())
  164.         return;
  165.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  166.     _data.MakeEmpty ();
  167.     Notify ();
  168. }
  169.  
  170.  
  171.  
  172. /*----------------------------------------------------------------------- */
  173.  
  174.  
  175. // Determine if o is in the set
  176. template <class BaseType>
  177. bool CL_Set<BaseType>::Includes (const BaseType& o) const
  178. {
  179.     if (!_idata)
  180.         return FALSE;
  181.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  182.     long i;
  183.     return _data.BinarySearch (o, i);
  184. }
  185.  
  186.  
  187.  
  188.  
  189. template <class BaseType>
  190. long CL_Set<BaseType>::RankOf (const BaseType& o) const
  191. {
  192.     if (!_idata)
  193.         return 0;
  194.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  195.     long index;
  196.     bool b = _data.BinarySearch (o, index);
  197.     return b ? index : index+1;
  198. }
  199.  
  200.  
  201. template <class BaseType>
  202. const BaseType& CL_Set<BaseType>::ItemWithRank (long i) const
  203. {
  204.     if (!_idata) {
  205.         ((CL_Set<BaseType>*) this)->_null = CL_Basics<BaseType>::NullValue();
  206.         // Just in case someone modified it
  207.         return _null;
  208.     }
  209.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  210.     long n = _data.Size();
  211.     if (n <= 0) {
  212.         ((CL_Set<BaseType>*) this)->_null = CL_Basics<BaseType>::NullValue();
  213.         // Just in case someone modified it
  214.         return _null;
  215.     }
  216.     i = maxl (0, minl (i, n-1));
  217.     return _data[i];
  218. }
  219.  
  220.  
  221.  
  222. /*----------------------------------------------------------------------- */
  223.  
  224. // Check if o is the same as this set
  225. template <class BaseType>
  226. bool CL_Set<BaseType>::operator== (const CL_Set<BaseType>& o) const
  227. {
  228.     if (!IsA (o))
  229.         return FALSE;
  230.     if (!_idata)
  231.         return FALSE;
  232.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  233.     if (Size() != ((const CL_Set<BaseType>&) o).Size())
  234.         return FALSE;
  235.  
  236.     long n = ((const CL_Set<BaseType>&)o).Size();
  237.     for (long i = 0; i < n; i++) {
  238.         if (! ((const CL_Set<BaseType>&)o).Includes (_data[i]))
  239.             return FALSE;
  240.     }
  241.     
  242.     return TRUE;
  243. }
  244.  
  245.  
  246.  
  247.  
  248. /*----------------------------------------------------------------------- */
  249.  
  250.  
  251. // Assignment
  252.  
  253. template <class BaseType>
  254. CL_Set<BaseType>& CL_Set<BaseType>::operator= (const CL_Set<BaseType>& s)
  255. {
  256.     if (this == &s || !_idata || !PrepareToChange())
  257.         return *this;
  258.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  259.     _data = *(CL_Sequence<BaseType>*)(s._idata);
  260.     Notify ();
  261.     return *this;
  262. }
  263.  
  264.  
  265.  
  266. /*----------------------------------------------------------------------- */
  267. template <class BaseType>
  268. void CL_Set<BaseType>::operator= (const CL_Object& o)
  269. {
  270.     if (CheckClassType (o, "CL_Set::op="))
  271.         *this = ((const CL_Set<BaseType>&) o);
  272. }
  273.  
  274.  
  275. /*----------------------------------------------------------------------- */
  276.  
  277. template <class BaseType>
  278. void CL_Set<BaseType>::operator= (const CL_Sequence<BaseType>& s)
  279. {
  280.     if (!_idata || !PrepareToChange())
  281.         return;
  282.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  283.     _data.MakeEmpty ();
  284.     // Don't use this->MakeEmpty, because we don't want double notification
  285.     register long n = s.Size();
  286.     for (register long i = 0; i < n; i++)
  287.         Add (s[i]);
  288.     Notify ();
  289. }
  290.  
  291.  
  292.  
  293. /*----------------------------------------------------------------------- */
  294.  
  295. template <class BaseType>
  296. CL_Set<BaseType> CL_Set<BaseType>::operator* (const CL_Set<BaseType>& s) const
  297. {
  298.     CL_Set<BaseType> aSet;
  299.  
  300.     if (!_idata)
  301.         return aSet;
  302.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  303.     CL_Sequence<BaseType>& sdata = (* (CL_Sequence<BaseType>*) s._idata);
  304.     CL_Sequence<BaseType>& adata = (* (CL_Sequence<BaseType>*) aSet._idata);
  305.     long m = _data.Size();
  306.     long n = s.Size();
  307.     adata.ChangeSize (m+n);
  308.     long i = 0, j = 0, count = 0;
  309.     while (i < m && j < n) {
  310.         short result = CL_Basics<BaseType>::Compare (_data[i], sdata[j]);
  311.         if (result < 0)
  312.             i++;
  313.         else if (result == 0) {
  314.             adata[count++] = _data[i];
  315.             i++; j++;
  316.         }
  317.         else j++;
  318.     }
  319.     adata.ChangeSize (count);
  320.     return aSet;
  321. }
  322.  
  323.  
  324.  
  325.  
  326.  
  327. template <class BaseType>
  328. bool CL_Set<BaseType>::IncludesAll (const CL_Set<BaseType>& s) const
  329. {
  330.     if (!_idata)
  331.         return FALSE;
  332.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  333.     CL_Sequence<BaseType>& sdata = (* (CL_Sequence<BaseType>*) s._idata);
  334.     register long m = _data.Size();
  335.     register long n = sdata.Size();
  336.     if (m < n)
  337.         return FALSE;
  338.     register long i = 0, j = 0, count = 0;
  339.     while (i < m && j < n) {
  340.         register short result = CL_Basics<BaseType>::Compare
  341.             (_data[i], sdata[j]);
  342.         if (result < 0)
  343.             i++;
  344.         else if (result == 0) {
  345.             i++; j++; count++;
  346.         }
  347.         else j++;
  348.     }
  349.     return count == n;
  350. }
  351.  
  352.  
  353.  
  354. template <class BaseType>
  355. CL_Set<BaseType> CL_Set<BaseType>::operator+ (const CL_Set<BaseType>& s) const
  356. {
  357.     CL_Set<BaseType> aSet;
  358.  
  359.     if (!_idata)
  360.         return aSet;
  361.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  362.     CL_Sequence<BaseType>& sdata = (* (CL_Sequence<BaseType>*) s._idata);
  363.     CL_Sequence<BaseType>& adata = (* (CL_Sequence<BaseType>*) aSet._idata);
  364.     long m = _data.Size();
  365.     long n = sdata.Size();
  366.     adata.ChangeSize (m+n);
  367.     long i = 0, j = 0, count = 0;
  368.     while (i < m || j < n) {
  369.         short result = (i >= m) ? 1 :
  370.         ((j >= n) ? -1 : CL_Basics<BaseType>::Compare (_data[i], sdata[j]));
  371.         if (result < 0) {
  372.             adata[count] = _data[i];
  373.             i++;
  374.         }
  375.         else if (result == 0) {
  376.             adata[count] = _data[i];
  377.             i++; j++;
  378.         }
  379.         else {
  380.             adata[count] = sdata[j];
  381.             j++;
  382.         }
  383.         count++;
  384.     }
  385.     adata.ChangeSize (count);
  386.     return aSet;
  387. }
  388.  
  389.  
  390.  
  391. template <class BaseType>
  392. CL_Set<BaseType> CL_Set<BaseType>::operator- (const CL_Set<BaseType>& s) const
  393. {
  394.     CL_Set<BaseType> aSet;
  395.  
  396.     if (!_idata)
  397.         return aSet;
  398.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  399.     CL_Sequence<BaseType>& sdata = (* (CL_Sequence<BaseType>*) s._idata);
  400.     CL_Sequence<BaseType>& adata = (* (CL_Sequence<BaseType>*) aSet._idata);
  401.     long m = _data.Size();
  402.     long n = sdata.Size();
  403.     adata.ChangeSize (m+n);
  404.     long i = 0, j = 0, count = 0;
  405.     while (i < m) {
  406.         short result = (j >= n) ? -1 :
  407.             CL_Basics<BaseType>::Compare (_data[i], sdata[j]);
  408.         if (result < 0) {
  409.             adata[count++] = _data[i];
  410.             i++;
  411.         }
  412.         else if (result == 0) {
  413.             i++; j++;
  414.         }
  415.         else {
  416.             j++;
  417.         }
  418.     }
  419.     adata.ChangeSize (count);
  420.     return aSet;
  421. }
  422.  
  423.  
  424.  
  425.  
  426.  
  427. template <class BaseType>
  428. CL_Set<BaseType> CL_Set<BaseType>::operator^ (const CL_Set<BaseType>& s) const
  429. {
  430.     CL_Set<BaseType> aSet;
  431.  
  432.     if (!_idata)
  433.         return aSet;
  434.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  435.     CL_Sequence<BaseType>& sdata = (* (CL_Sequence<BaseType>*) s._idata);
  436.     CL_Sequence<BaseType>& adata = (* (CL_Sequence<BaseType>*) aSet._idata);
  437.     long m = _data.Size();
  438.     long n = sdata.Size();
  439.     adata.ChangeSize (m+n);
  440.     long i = 0, j = 0, count = 0;
  441.     while (i < m) {
  442.         short result = (j >= n) ? -1 :
  443.             CL_Basics<BaseType>::Compare (_data[i], sdata[j]);
  444.         if (result < 0) {
  445.             adata[count++] = _data[i];
  446.             i++;
  447.         }
  448.         else if (result == 0) {
  449.             i++; j++;
  450.         }
  451.         else {
  452.             adata[count++] = sdata[i];
  453.             j++;
  454.         }
  455.     }
  456.     adata.ChangeSize (count);
  457.     return aSet;
  458. }
  459.  
  460.  
  461.  
  462.  
  463.  
  464.  
  465.  
  466.  
  467. /*----------------------------------------------------------------------- */
  468.     
  469.     
  470.  
  471. template <class BaseType>
  472. void CL_Set<BaseType>::operator += (const CL_Set<BaseType>& s)
  473. {
  474.     // Notification done by operator=
  475.     *this = (*this) + s;
  476. }
  477.  
  478.  
  479.  
  480. /*----------------------------------------------------------------------- */
  481.  
  482.  
  483. // Set intersection
  484.  
  485. template <class BaseType>
  486. void CL_Set<BaseType>::operator *= (const CL_Set<BaseType>& s)
  487. {
  488.     (*this) = (*this) * s;
  489. }
  490.  
  491.  
  492.  
  493. /*----------------------------------------------------------------------- */
  494.  
  495.  
  496. // Set difference
  497.  
  498. template <class BaseType>
  499. void CL_Set<BaseType>::operator -= (const CL_Set<BaseType>& s)
  500. {
  501.     (*this) = (*this) - s;
  502. }
  503.  
  504.  
  505.  
  506. /*----------------------------------------------------------------------- */
  507.  
  508.  
  509.  
  510. // Symmetric difference (xor)
  511.  
  512. template <class BaseType>
  513. void CL_Set<BaseType>::operator ^= (const CL_Set<BaseType>& s)
  514. {
  515.     (*this) = (*this) ^ s;
  516. }
  517.  
  518.  
  519.  
  520. /*----------------------------------------------------------------------- */
  521.  
  522.  
  523.  
  524. template <class BaseType>
  525. bool CL_Set<BaseType>::_ReadElement (const CL_Stream& s,
  526.                                      BaseType& element)
  527. {
  528.     return CL_RestoreFrom (element, s, _filter);
  529. }
  530.  
  531.  
  532.  
  533.  
  534. template <class BaseType>
  535. bool CL_Set<BaseType>::ReadFrom (const CL_Stream& s)
  536. {
  537.     if (!PrepareToChange())
  538.         return FALSE;
  539.     CL_ClassId id;
  540.     if (!s.Read (id) || id != ClassId())
  541.         return FALSE;
  542.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  543.     long n;
  544.     if (!s.Read (n))
  545.         return FALSE;
  546.     if (!_data.ChangeSize (n))
  547.         return FALSE;
  548.     for (register long i = 0; i < n; i++) {
  549.         if (!_ReadElement (s, _data[i]))
  550.             return FALSE;
  551.     }
  552.     _data.Sort ();
  553.     Notify ();
  554.     return TRUE;
  555. }
  556.  
  557.  
  558. template <class BaseType>
  559. bool CL_Set<BaseType>::_WriteElement (CL_Stream& s, const BaseType& e) const
  560. {
  561.     return CL_SaveTo (e, s, _filter);
  562. }
  563.  
  564.  
  565.  
  566.  
  567. template <class BaseType>
  568. bool CL_Set<BaseType>::WriteTo  (CL_Stream& s) const
  569. {
  570.     if (!_idata)
  571.         return FALSE;
  572.     CL_Sequence<BaseType>& _data = (* (CL_Sequence<BaseType>*) _idata);
  573.     register long n = Size();
  574.     if (!s.Write (ClassId()) || !s.Write (n) )
  575.         return FALSE;
  576.     for (register long i = 0; i < n; i++) {
  577.         if (!_WriteElement (s, _data[i]))
  578.             return FALSE;
  579.     }
  580.     return TRUE;
  581. }
  582.  
  583.  
  584.  
  585.  
  586.  
  587.  
  588.  
  589.  
  590.     
  591.  
  592. //
  593. // Protected CL_Set methods
  594. //
  595.  
  596.  
  597.  
  598.  
  599.  
  600.  
  601.  
  602.  
  603.  
  604.  
  605.     
  606. /*----------------------------------------------------------------------- */
  607.  
  608.  
  609. //
  610. //------------------------------------------------------------
  611. //
  612.  
  613. // CL_SetIterator methods
  614.  
  615.  
  616. template <class BaseType>
  617. CL_SetIterator<BaseType>::CL_SetIterator (const CL_Set<BaseType>& o)
  618.     :_set (o) 
  619. {
  620.     _index = 0;
  621. }
  622.  
  623.  
  624.  
  625. /*----------------------------------------------------------------------- */
  626.  
  627. template <class BaseType>
  628. CL_SetIterator<BaseType>::CL_SetIterator (const CL_SetIterator<BaseType>& s)
  629.     :_set (s._set), _index (s._index)
  630. {
  631. }
  632.  
  633.  
  634.  
  635. /*----------------------------------------------------------------------- */
  636.  
  637. template <class BaseType>
  638. void CL_SetIterator<BaseType>::Reset ()
  639. {   
  640.     _index = 0;
  641. }
  642.  
  643.  
  644. /*----------------------------------------------------------------------- */
  645.  
  646. template <class BaseType>
  647. void CL_SetIterator<BaseType>::BeginFromRank (long l)
  648. {   
  649.     _index = maxl (0, l);
  650. }
  651.  
  652.  
  653. /*----------------------------------------------------------------------- */
  654.  
  655. template <class BaseType>
  656. const BaseType& CL_SetIterator<BaseType>::Next ()
  657. {
  658.     register CL_Sequence<BaseType>* data = (CL_Sequence<BaseType>*)
  659.         _set._idata;
  660.     if (data && (_index < data->Size()) )
  661.         return (*data)[_index++];
  662.     ((CL_Set<BaseType>&) _set)._null = CL_Basics<BaseType>::NullValue();
  663.     return _set._null; 
  664. }
  665.  
  666.  
  667.  
  668. /*----------------------------------------------------------------------- */
  669.  
  670. template <class BaseType>
  671. bool CL_SetIterator<BaseType>::More ()
  672. {
  673.     return _index < _set.Size();
  674. }
  675.  
  676.  
  677.  
  678.  
  679.  
  680.  
  681.  
  682. /*----------------------------------------------------------------------- */
  683.  
  684.  
  685.  
  686.  
  687.  
  688.  
  689. #endif /* _setimp_cxx_ */
  690.  
  691.