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