ofstd/include/dcmtk/ofstd/ofoset.h

00001 /*
00002  *
00003  *  Copyright (C) 2002-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 ordered set of elements
00019  *           of an arbitrary type.
00020  *
00021  *  Last Update:      $Author: joergr $
00022  *  Update Date:      $Date: 2010-10-14 13:15:50 $
00023  *  CVS/RCS Revision: $Revision: 1.11 $
00024  *  Status:           $State: Exp $
00025  *
00026  *  CVS/RCS Log at end of file
00027  *
00028  */
00029 
00030 #ifndef OFOrderedSet_h
00031 #define OFOrderedSet_h
00032 
00033 #include "dcmtk/config/osconfig.h"
00034 #include "dcmtk/ofstd/oftypes.h"
00035 #include "dcmtk/ofstd/ofset.h"
00036 
00051 template <class T> class OFOrderedSet : public OFSet<T>
00052 {
00053   protected:
00054 
00055   public:
00058     OFOrderedSet()
00059         : OFSet<T>()
00060       {
00061       }
00062 
00063 
00067     OFOrderedSet( const OFOrderedSet<T> &src )
00068         : OFSet<T>( src )
00069       {
00070       }
00071 
00072 
00075     virtual ~OFOrderedSet()
00076       {
00077       }
00078 
00079 
00084     const OFOrderedSet<T> &operator=( const OFOrderedSet<T> &src )
00085       {
00086         return( assign( src ) );
00087       }
00088 
00089 
00093     const OFOrderedSet<T> &assign( const OFOrderedSet<T> &src )
00094       {
00095         if( this != &src )
00096           this->operator=( src );
00097 
00098         return( *this );
00099       }
00100 
00101 
00108     virtual OFBool operator==( const OFOrderedSet<T> &other ) const
00109       {
00110         // check if both sets contain the same
00111         // amount of items; if not, return OFFalse
00112         if( this->num != other.num )
00113           return( OFFalse );
00114 
00115         // initialize result with OFTrue
00116         OFBool result = OFTrue;
00117 
00118         // as long as result is OFTrue go through all items in this
00119         for( unsigned int i=0 ; i < this->num && result == OFTrue ; i++ )
00120         {
00121           // in case the current element does not equal the current
00122           // element in other, result shall be set to OFFalse
00123           if( *this->items[i] != *other.items[i] )
00124             result = OFFalse;
00125         }
00126 
00127         // return result
00128         return( result );
00129       }
00130 
00131 
00136     virtual OFBool operator!=( const OFOrderedSet<T> &other ) const
00137       {
00138         return( !( *this == other ) );
00139       }
00140 
00141 
00145     virtual void Insert( const T &item )
00146       {
00147         // if size equals num, we need more space
00148         if( this->size == this->num )
00149           Resize( this->size * 2 );
00150 
00151         // copy item
00152         T *newItem = new T( item );
00153 
00154         // insert copy into array
00155         this->items[this->num] = newItem;
00156 
00157         // increase counter
00158         this->num++;
00159       }
00160 
00161 
00165     virtual void Insert( const OFOrderedSet<T> &other )
00166       {
00167         // go through all items in other and insert each item into this
00168         for( unsigned int i=0 ; i<other.num ; i++ )
00169           Insert( *other.items[i] );
00170       }
00171 
00172 
00180     virtual void InsertAt( const T &item, unsigned int idx )
00181       {
00182         unsigned int i;
00183 
00184         // in case index is greater than the index of the last item,
00185         // insert the new item right behind the last item of the set
00186         if( idx > this->num - 1 )
00187           Insert( item );
00188         else
00189         {
00190           // if size equals num, we need more space
00191           if( this->size == this->num )
00192             Resize( this->size * 2 );
00193 
00194           // copy item
00195           T *newItem = new T( item );
00196 
00197           // create a new temporary array and assign all pointers correspondingly
00198           T **tmp = new T*[this->size];
00199 
00200           for( i=0 ; i<idx ; i++ )
00201             tmp[i] = this->items[i];
00202 
00203           tmp[idx] = newItem;
00204 
00205           for( i=idx ; i < this->size - 1 ; i++ )
00206           {
00207             if( i < this->num )
00208               tmp[i+1] = this->items[i];
00209             else
00210               tmp[i+1] = NULL;
00211           }
00212 
00213           // delete old array
00214           delete this->items;
00215 
00216           // assign new array to member variable
00217           this->items = tmp;
00218 
00219           // increase counter
00220           this->num++;
00221         }
00222       }
00223 
00224 
00228     virtual void Remove( const T &item )
00229       {
00230         // so far, nothing was deleted
00231         OFBool itemDeleted = OFFalse;
00232 
00233         // go through all items
00234         for( unsigned int i=0 ; i < this->num && !itemDeleted ; i++ )
00235         {
00236           // if current item is the one which shall be deleted
00237           if( *this->items[i] == item )
00238           {
00239             // delete item
00240             delete this->items[i];
00241 
00242             // and - so that there are no holes in the array - move all elements
00243             // behind the current element up one array field; only do so in case
00244             // we did _not_ delete the last item
00245             if( i != this->num - 1 )
00246             {
00247               unsigned int j;
00248               for( j=i+1 ; j < this->num ; j++ )
00249               {
00250                 this->items[j-1] = this->items[j];
00251               }
00252 
00253               this->items[j-1] = NULL;
00254             }
00255             else
00256               this->items[i] = NULL;
00257 
00258             // reduce counter
00259             this->num--;
00260 
00261             // remember that an item was deleted (so that always only one item will be deleted)
00262             itemDeleted = OFTrue;
00263           }
00264         }
00265       }
00266 
00267 
00271     virtual void RemoveByIndex( unsigned int idx )
00272       {
00273         // do something only if the given index is not out of range
00274         if( idx < this->num )
00275         {
00276           // delete item with given index
00277           delete this->items[idx];
00278 
00279           // and - so that there are no holes in the array - move all elements
00280           // behind the current element up one array field; only do so in case
00281           // we did _not_ delete the last item
00282           if( idx != this->num - 1 )
00283           {
00284             unsigned int j;
00285             for( j=idx+1 ; j < this->num ; j++ )
00286             {
00287               this->items[j-1] = this->items[j];
00288             }
00289 
00290             this->items[j-1] = NULL;
00291           }
00292           else
00293             this->items[idx] = NULL;
00294 
00295           // reduce counter
00296           this->num--;
00297         }
00298       }
00299 
00300 
00307     virtual T *Find( const T &item ) const
00308       {
00309         unsigned int i;
00310         OFBool itemFound = OFFalse;
00311 
00312         for( i=0 ; i < this->num && !itemFound ; i++ )
00313         {
00314           if( *this->items[i] == item )
00315             itemFound = OFTrue;
00316         }
00317 
00318         if( itemFound )
00319           return( this->items[i-1] );
00320         else
00321           return( NULL );
00322       }
00323 
00324 
00329     virtual OFBool Contains( const T &item ) const
00330       {
00331         OFBool itemFound = OFFalse;
00332 
00333         for( unsigned int i=0 ; i < this->num && !itemFound ; i++ )
00334         {
00335           if( *this->items[i] == item )
00336             itemFound = OFTrue;
00337         }
00338 
00339         return( itemFound );
00340       }
00341 
00342 
00349     virtual OFBool IsSupersetOf( const OFOrderedSet<T> &other ) const
00350       {
00351         // if this contains less or the same amount of items than other, return OFFalse
00352         if( this->num <= other.num )
00353           return( OFFalse );
00354 
00355         // initialize result with OFTrue
00356         OFBool result = OFTrue;
00357 
00358         // make a copy of this
00359         OFOrderedSet<T> s = *this;
00360 
00361         // as long as result is OFTrue go through all items in other
00362         for( unsigned int i=0 ; i<other.num && result == OFTrue ; i++ )
00363         {
00364           // in case s contains the current item of other
00365           if( s.Contains( *other.items[i] ) )
00366           {
00367             // remove this item from s so that it will not be
00368             // considered again in a later call to s.Contains()
00369             s.Remove( *other.items[i] );
00370           }
00371           // in case s does not contain the current item of other the result is OFFalse
00372           else
00373             result = OFFalse;
00374         }
00375 
00376         // return result
00377         return( result );
00378       }
00379 
00380 
00387     virtual OFBool IsSubsetOf( const OFOrderedSet<T> &other ) const
00388       {
00389         return( other.IsSupersetOf( *this ) );
00390       }
00391 
00392 
00399     OFOrderedSet<T> Union( const OFOrderedSet<T> &other ) const
00400       {
00401         // initialize result set
00402         OFOrderedSet<T> resultSet = *this;
00403 
00404         // insert other set into result set
00405         resultSet.Insert( other );
00406 
00407         // return result set
00408         return( resultSet );
00409       }
00410 
00411 
00418     OFOrderedSet<T> Intersection( const OFOrderedSet<T> &other ) const
00419       {
00420         // initialize result set
00421         OFOrderedSet<T> resultSet;
00422 
00423         // make a copy of other
00424         OFOrderedSet<T> s = other;
00425 
00426         // go through all items in this
00427         for( unsigned int i=0 ; i < this->num ; i++ )
00428         {
00429           // if s contains the current item
00430           if( s.Contains( *this->items[i] ) )
00431           {
00432             // insert the item into the result set
00433             resultSet.Insert( *this->items[i] );
00434 
00435             // and remove the item from s so that it will not be
00436             // considered again in a later call to s.Contains()
00437             s.Remove( *this->items[i] );
00438           }
00439         }
00440 
00441         // return result set
00442         return( resultSet );
00443       }
00444 
00445 
00452     OFOrderedSet<T> Difference( const OFOrderedSet<T> &other ) const
00453       {
00454         // initialize result set
00455         OFOrderedSet<T> resultSet;
00456 
00457         // make a copy of other
00458         OFOrderedSet<T> s = other;
00459 
00460         // go through all items in this
00461         for( unsigned int i=0 ; i < this->num ; i++ )
00462         {
00463           // if s does not contain the current item
00464           if( !s.Contains( *this->items[i] ) )
00465           {
00466             // insert the item into the result set
00467             resultSet.Insert( *this->items[i] );
00468           }
00469           else
00470           {
00471             // else remove the item from s so that it will not be
00472             // considered again in a later call to s.Contains()
00473             s.Remove( *this->items[i] );
00474           }
00475         }
00476 
00477         // return result set
00478         return( resultSet );
00479       }
00480 
00481 
00489     OFOrderedSet<T> SymmetricDifference( const OFOrderedSet<T> &other ) const
00490       {
00491         // determine s1 = this - other
00492         OFOrderedSet<T> s1 = (*this).Difference( other );
00493 
00494         // determine s2 = other - this
00495         OFOrderedSet<T> s2 = other.Difference( *this );
00496 
00497         // determine the union of s1 and s2
00498         OFOrderedSet<T> resultSet = s1.Union( s2 );
00499 
00500         // return result set
00501         return( resultSet );
00502       }
00503 };
00504 
00505 
00506 #endif
00507 
00508 /*
00509 ** CVS/RCS Log:
00510 ** $Log: ofoset.h,v $
00511 ** Revision 1.11  2010-10-14 13:15:50  joergr
00512 ** Updated copyright header. Added reference to COPYRIGHT file.
00513 **
00514 ** Revision 1.10  2005/12/08 16:06:00  meichel
00515 ** Changed include path schema for all DCMTK header files
00516 **
00517 ** Revision 1.9  2004/04/21 10:00:52  meichel
00518 ** Minor modifications for compilation with gcc 3.4.0
00519 **
00520 ** Revision 1.8  2002/12/17 17:01:33  wilkens
00521 ** Modified code again to keep Sun CC 2.0.1 happy on Solaris 2.5.1 (template
00522 ** errors).
00523 **
00524 ** Revision 1.7  2002/12/16 10:40:24  wilkens
00525 ** Removed superfluous implementation files and modified header and make files.
00526 **
00527 ** Revision 1.6  2002/12/13 12:26:50  wilkens
00528 ** Modified code to keep Sun CC 2.0.1 happy on Solaris 2.5.1 (template errors).
00529 **
00530 ** Revision 1.5  2002/12/09 13:03:55  joergr
00531 ** Renamed parameter to avoid name clash with global function index().
00532 **
00533 ** Revision 1.4  2002/07/09 18:29:45  wilkens
00534 ** Added some more functionality.
00535 **
00536 ** Revision 1.2  2002/07/02 15:41:33  wilkens
00537 ** Made some modifications to keep gcc version egcs-2.91.66 quiet.
00538 **
00539 ** Revision 1.1  2002/07/02 15:19:54  wilkens
00540 ** Added container classes OFOrderedSet and OFUnorderedSet which
00541 ** are based on the new abstract class OFSet.
00542 **
00543 **
00544 */


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