ofstd/include/dcmtk/ofstd/ofuoset.h

00001 /*
00002  *
00003  *  Copyright (C) 1997-2010, OFFIS e.V.
00004  *  All rights reserved.  See COPYRIGHT file for details.
00005  *
00006  *  This software and supporting documentation were developed by
00007  *
00008  *    OFFIS e.V.
00009  *    R&D Division Health
00010  *    Escherweg 2
00011  *    D-26121 Oldenburg, Germany
00012  *
00013  *
00014  *  Module:  ofstd
00015  *
00016  *  Author:  Thomas Wilkens
00017  *
00018  *  Purpose: Template class for administrating an unordered set of elements
00019  *           of an arbitrary type.
00020  *
00021  *  Last Update:      $Author: joergr $
00022  *  Update Date:      $Date: 2010-10-14 13:15:51 $
00023  *  CVS/RCS Revision: $Revision: 1.7 $
00024  *  Status:           $State: Exp $
00025  *
00026  *  CVS/RCS Log at end of file
00027  *
00028  */
00029 
00030 #ifndef OFUnorderedSet_h
00031 #define OFUnorderedSet_h
00032 
00033 #include "dcmtk/config/osconfig.h"
00034 #include "dcmtk/ofstd/oftypes.h"
00035 #include "dcmtk/ofstd/ofset.h"
00036 
00052 template <class T> class OFUnorderedSet : public OFSet<T>
00053 {
00054   protected:
00055 
00056   public:
00059     OFUnorderedSet()
00060         : OFSet<T>()
00061       {
00062       }
00063 
00064 
00068     OFUnorderedSet( const OFUnorderedSet<T> &src )
00069         : OFSet<T>( src )
00070       {
00071       }
00072 
00073 
00076     virtual ~OFUnorderedSet()
00077       {
00078       }
00079 
00080 
00085     const OFUnorderedSet<T> &operator=( const OFUnorderedSet<T> &src )
00086       {
00087         if( this == &src )
00088           return( *this );
00089 
00090         OFSet<T>::operator=( src );
00091 
00092         return( *this );
00093       }
00094 
00095 
00100     virtual OFBool operator==( const OFUnorderedSet<T> &other ) const
00101       {
00102         // check if both sets contain the same
00103         // amount of items; if not, return OFFalse
00104         if( OFSet<T>::num != other.num )
00105           return( OFFalse );
00106 
00107         // initialize result with OFTrue
00108         OFBool result = OFTrue;
00109 
00110         // make a copy of this
00111         OFUnorderedSet<T> s = *this;
00112 
00113         // as long as result is OFTrue go through all items in other
00114         for( unsigned int i=0 ; i<other.num && result == OFTrue ; i++ )
00115         {
00116           // in case s contains the current item of other
00117           if( s.Contains( *other.items[i] ) )
00118           {
00119             // remove this item from s so that it will not be
00120             // considered again in a later call to s.Contains()
00121             s.Remove( *other.items[i] );
00122           }
00123           // in case s doesn't contain the current item of other the result is OFFalse
00124           else
00125             result = OFFalse;
00126         }
00127 
00128         // return result
00129         return( result );
00130       }
00131 
00132 
00137     virtual OFBool operator!=( const OFUnorderedSet<T> &other ) const
00138       {
00139         return( !( *this == other ) );
00140       }
00141 
00142 
00146     virtual void Insert( const T &item )
00147       {
00148         // if size equals num, we need more space
00149         if( OFSet<T>::size == OFSet<T>::num )
00150           Resize( OFSet<T>::size * 2 );
00151 
00152         // copy item
00153         T *newItem = new T( item );
00154 
00155         // insert copy into array
00156         OFSet<T>::items[OFSet<T>::num] = newItem;
00157 
00158         // increase counter
00159         OFSet<T>::num++;
00160       }
00161 
00162 
00166     virtual void Insert( const OFUnorderedSet<T> &other )
00167       {
00168         // go through all items in other and insert each item into this
00169         for( unsigned int i=0 ; i<other.num ; i++ )
00170           Insert( *other.items[i] );
00171       }
00172 
00173 
00177     virtual void Remove( const T &item )
00178       {
00179         // so far, nothing was deleted
00180         OFBool itemDeleted = OFFalse;
00181 
00182         // go through all items
00183         for( unsigned int i=0 ; i<OFSet<T>::num && !itemDeleted ; i++ )
00184         {
00185           // if current item is the one which shall be deleted
00186           if( *OFSet<T>::items[i] == item )
00187           {
00188             // delete item
00189             delete OFSet<T>::items[i];
00190 
00191             // and - so that there are no holes in the array - move the last
00192             // item to the array field from which the item was deleted;
00193             // only do so in case we did _not_ delete the last item
00194             if( i != OFSet<T>::num - 1 )
00195             {
00196               OFSet<T>::items[i] = OFSet<T>::items[OFSet<T>::num-1];
00197               OFSet<T>::items[OFSet<T>::num-1] = NULL;
00198             }
00199             else
00200               OFSet<T>::items[i] = NULL;
00201 
00202             // reduce counter
00203             OFSet<T>::num--;
00204 
00205             // remember that an item was deleted (so that always only one item will be deleted)
00206             itemDeleted = OFTrue;
00207           }
00208         }
00209       }
00210 
00211 
00215     virtual void RemoveByIndex( unsigned int index )
00216       {
00217         // do something only if the given index is not out of range
00218         if( index < OFSet<T>::num )
00219         {
00220           // delete item with given index
00221           delete OFSet<T>::items[index];
00222 
00223           // and - so that there are no holes in the array - move the last
00224           // item to the array field from which the item was deleted;
00225           // only do so in case we did _not_ delete the last item
00226           if( index != OFSet<T>::num - 1 )
00227           {
00228             OFSet<T>::items[index] = OFSet<T>::items[OFSet<T>::num-1];
00229             OFSet<T>::items[OFSet<T>::num-1] = NULL;
00230           }
00231           else
00232             OFSet<T>::items[index] = NULL;
00233 
00234           // reduce counter
00235           OFSet<T>::num--;
00236         }
00237       }
00238 
00239 
00246     virtual T *Find( const T &item ) const
00247       {
00248         unsigned int i;
00249         OFBool itemFound = OFFalse;
00250 
00251         for( i=0 ; i<OFSet<T>::num && !itemFound ; i++ )
00252         {
00253           if( *OFSet<T>::items[i] == item )
00254             itemFound = OFTrue;
00255         }
00256 
00257         if( itemFound )
00258           return( OFSet<T>::items[i-1] );
00259         else
00260           return( NULL );
00261       }
00262 
00263 
00268     virtual OFBool Contains( const T &item ) const
00269       {
00270         OFBool itemFound = OFFalse;
00271 
00272         for( unsigned int i=0 ; i<OFSet<T>::num && !itemFound ; i++ )
00273         {
00274           if( *OFSet<T>::items[i] == item )
00275             itemFound = OFTrue;
00276         }
00277 
00278         return( itemFound );
00279       }
00280 
00281 
00288     virtual OFBool IsSupersetOf( const OFUnorderedSet<T> &other ) const
00289       {
00290         // if this contains less or the same amount of items than other, return OFFalse
00291         if( OFSet<T>::num <= other.num )
00292           return( OFFalse );
00293 
00294         // initialize result with OFTrue
00295         OFBool result = OFTrue;
00296 
00297         // make a copy of this
00298         OFUnorderedSet<T> s = *this;
00299 
00300         // as long as result is OFTrue go through all items in other
00301         for( unsigned int i=0 ; i<other.num && result == OFTrue ; i++ )
00302         {
00303           // in case s contains the current item of other
00304           if( s.Contains( *other.items[i] ) )
00305           {
00306             // remove this item from s so that it will not be
00307             // considered again in a later call to s.Contains()
00308             s.Remove( *other.items[i] );
00309           }
00310           // in case s does not contain the current item of other the result is OFFalse
00311           else
00312             result = OFFalse;
00313         }
00314 
00315         // return result
00316         return( result );
00317       }
00318 
00319 
00326     virtual OFBool IsSubsetOf( const OFUnorderedSet<T> &other ) const
00327       {
00328         return( other.IsSupersetOf( *this ) );
00329       }
00330 
00331 
00338     OFUnorderedSet<T> Union( const OFUnorderedSet<T> &other ) const
00339       {
00340         // initialize result set
00341         OFUnorderedSet<T> resultSet = *this;
00342 
00343         // insert other set into result set
00344         resultSet.Insert( other );
00345 
00346         // return result set
00347         return( resultSet );
00348       }
00349 
00350 
00357     OFUnorderedSet<T> Intersection( const OFUnorderedSet<T> &other ) const
00358       {
00359         // initialize result set
00360         OFUnorderedSet<T> resultSet;
00361 
00362         // make a copy of other
00363         OFUnorderedSet<T> s = other;
00364 
00365         // go through all items in this
00366         for( unsigned int i=0 ; i< OFSet<T>::num ; i++ )
00367         {
00368           // if s contains the current item
00369           if( s.Contains( *OFSet<T>::items[i] ) )
00370           {
00371             // insert the item into the result set
00372             resultSet.Insert( *OFSet<T>::items[i] );
00373 
00374             // and remove the item from s so that it will not be
00375             // considered again in a later call to s.Contains()
00376             s.Remove( *OFSet<T>::items[i] );
00377           }
00378         }
00379 
00380         // return result set
00381         return( resultSet );
00382       }
00383 
00384 
00391     OFUnorderedSet<T> Difference( const OFUnorderedSet<T> &other ) const
00392       {
00393         // initialize result set
00394         OFUnorderedSet<T> resultSet;
00395 
00396         // make a copy of other
00397         OFUnorderedSet<T> s = other;
00398 
00399         // go through all items in this
00400         for( unsigned int i=0 ; i< OFSet<T>::num ; i++ )
00401         {
00402           // if s does not contain the current item
00403           if( !s.Contains( *OFSet<T>::items[i] ) )
00404           {
00405             // insert the item into the result set
00406             resultSet.Insert( *OFSet<T>::items[i] );
00407           }
00408           else
00409           {
00410             // else remove the item from s so that it will not be
00411             // considered again in a later call to s.Contains()
00412             s.Remove( *OFSet<T>::items[i] );
00413           }
00414         }
00415 
00416         // return result set
00417         return( resultSet );
00418       }
00419 
00420 
00428     OFUnorderedSet<T> SymmetricDifference( const OFUnorderedSet<T> &other ) const
00429       {
00430         // determine s1 = this - other
00431         OFUnorderedSet<T> s1 = (*this).Difference( other );
00432 
00433         // determine s2 = other - this
00434         OFUnorderedSet<T> s2 = other.Difference( *this );
00435 
00436         // determine the union of s1 and s2
00437         OFUnorderedSet<T> resultSet = s1.Union( s2 );
00438 
00439         // return result set
00440         return( resultSet );
00441       }
00442 };
00443 
00444 #endif
00445 
00446 /*
00447 ** CVS/RCS Log:
00448 ** $Log: ofuoset.h,v $
00449 ** Revision 1.7  2010-10-14 13:15:51  joergr
00450 ** Updated copyright header. Added reference to COPYRIGHT file.
00451 **
00452 ** Revision 1.6  2005/12/12 09:24:27  meichel
00453 ** Added explicit references to parent template class, needed for
00454 **   gcc 3.4.2 (MinGW port)
00455 **
00456 ** Revision 1.5  2005/12/08 16:06:12  meichel
00457 ** Changed include path schema for all DCMTK header files
00458 **
00459 ** Revision 1.4  2002/12/16 10:40:25  wilkens
00460 ** Removed superfluous implementation files and modified header and make files.
00461 **
00462 ** Revision 1.3  2002/07/09 18:29:47  wilkens
00463 ** Added some more functionality.
00464 **
00465 **
00466 */


Generated on 6 Jan 2011 for OFFIS DCMTK Version 3.6.0 by Doxygen 1.5.1