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 */