ofstd/include/ofoset.h

/*
 *
 *  Copyright (C) 2002-2004, OFFIS
 *
 *  This software and supporting documentation were developed by
 *
 *    Kuratorium OFFIS e.V.
 *    Healthcare Information and Communication Systems
 *    Escherweg 2
 *    D-26121 Oldenburg, Germany
 *
 *  THIS SOFTWARE IS MADE AVAILABLE,  AS IS,  AND OFFIS MAKES NO  WARRANTY
 *  REGARDING  THE  SOFTWARE,  ITS  PERFORMANCE,  ITS  MERCHANTABILITY  OR
 *  FITNESS FOR ANY PARTICULAR USE, FREEDOM FROM ANY COMPUTER DISEASES  OR
 *  ITS CONFORMITY TO ANY SPECIFICATION. THE ENTIRE RISK AS TO QUALITY AND
 *  PERFORMANCE OF THE SOFTWARE IS WITH THE USER.
 *
 *  Module:  ofstd
 *
 *  Author:  Thomas Wilkens
 *
 *  Purpose: Template class for administrating an ordered set of elements
 *           of an arbitrary type.
 *
 *  Last Update:      $Author: meichel $
 *  Update Date:      $Date: 2004/04/21 10:00:52 $
 *  Source File:      $Source: /share/dicom/cvs-depot/dcmtk/ofstd/include/ofoset.h,v $
 *  CVS/RCS Revision: $Revision: 1.9 $
 *  Status:           $State: Exp $
 *
 *  CVS/RCS Log at end of file
 *
 */

#ifndef OFOrderedSet_h
#define OFOrderedSet_h

#include "osconfig.h"
#include "oftypes.h"
#include "ofset.h"

template <class T> class OFOrderedSet : public OFSet<T>
{
  protected:

  public:
    OFOrderedSet()
        : OFSet<T>()
      {
      }


    OFOrderedSet( const OFOrderedSet<T> &src )
        : OFSet<T>( src )
      {
      }


    virtual ~OFOrderedSet()
      {
      }


    const OFOrderedSet<T> &operator=( const OFOrderedSet<T> &src )
      {
        return( assign( src ) );
      }


    const OFOrderedSet<T> &assign( const OFOrderedSet<T> &src )
      {
        if( this != &src )
          this->operator=( src );

        return( *this );
      }


    virtual OFBool operator==( const OFOrderedSet<T> &other ) const
      {
        // check if both sets contain the same
        // amount of items; if not, return OFFalse
        if( this->num != other.num )
          return( OFFalse );

        // initialize result with OFTrue
        OFBool result = OFTrue;

        // as long as result is OFTrue go through all items in this
        for( unsigned int i=0 ; i < this->num && result == OFTrue ; i++ )
        {
          // in case the current element does not equal the current
          // element in other, result shall be set to OFFalse
          if( *this->items[i] != *other.items[i] )
            result = OFFalse;
        }

        // return result
        return( result );
      }


    virtual OFBool operator!=( const OFOrderedSet<T> &other ) const
      {
        return( !( *this == other ) );
      }


    virtual void Insert( const T &item )
      {
        // if size equals num, we need more space
        if( this->size == this->num )
          Resize( this->size * 2 );

        // copy item
        T *newItem = new T( item );

        // insert copy into array
        this->items[this->num] = newItem;

        // increase counter
        this->num++;
      }


    virtual void Insert( const OFOrderedSet<T> &other )
      {
        // go through all items in other and insert each item into this
        for( unsigned int i=0 ; i<other.num ; i++ )
          Insert( *other.items[i] );
      }


    virtual void InsertAt( const T &item, unsigned int idx )
      {
        unsigned int i;

        // in case index is greater than the index of the last item,
        // insert the new item right behind the last item of the set
        if( idx > this->num - 1 )
          Insert( item );
        else
        {
          // if size equals num, we need more space
          if( this->size == this->num )
            Resize( this->size * 2 );

          // copy item
          T *newItem = new T( item );

          // create a new temporary array and assign all pointers correspondingly
          T **tmp = new T*[this->size];

          for( i=0 ; i<idx ; i++ )
            tmp[i] = this->items[i];

          tmp[idx] = newItem;

          for( i=idx ; i < this->size - 1 ; i++ )
          {
            if( i < this->num )
              tmp[i+1] = this->items[i];
            else
              tmp[i+1] = NULL;
          }

          // delete old array
          delete this->items;

          // assign new array to member variable
          this->items = tmp;

          // increase counter
          this->num++;
        }
      }


    virtual void Remove( const T &item )
      {
        // so far, nothing was deleted
        OFBool itemDeleted = OFFalse;

        // go through all items
        for( unsigned int i=0 ; i < this->num && !itemDeleted ; i++ )
        {
          // if current item is the one which shall be deleted
          if( *this->items[i] == item )
          {
            // delete item
            delete this->items[i];

            // and - so that there are no holes in the array - move all elements
            // behind the current element up one array field; only do so in case
            // we did _not_ delete the last item
            if( i != this->num - 1 )
            {
              unsigned int j;
              for( j=i+1 ; j < this->num ; j++ )
              {
                this->items[j-1] = this->items[j];
              }

              this->items[j-1] = NULL;
            }
            else
              this->items[i] = NULL;

            // reduce counter
            this->num--;

            // remember that an item was deleted (so that always only one item will be deleted)
            itemDeleted = OFTrue;
          }
        }
      }


    virtual void RemoveByIndex( unsigned int idx )
      {
        // do something only if the given index is not out of range
        if( idx < this->num )
        {
          // delete item with given index
          delete this->items[idx];

          // and - so that there are no holes in the array - move all elements
          // behind the current element up one array field; only do so in case
          // we did _not_ delete the last item
          if( idx != this->num - 1 )
          {
            unsigned int j;
            for( j=idx+1 ; j < this->num ; j++ )
            {
              this->items[j-1] = this->items[j];
            }

            this->items[j-1] = NULL;
          }
          else
            this->items[idx] = NULL;

          // reduce counter
          this->num--;
        }
      }


    virtual T *Find( const T &item ) const
      {
        unsigned int i;
        OFBool itemFound = OFFalse;

        for( i=0 ; i < this->num && !itemFound ; i++ )
        {
          if( *this->items[i] == item )
            itemFound = OFTrue;
        }

        if( itemFound )
          return( this->items[i-1] );
        else
          return( NULL );
      }


    virtual OFBool Contains( const T &item ) const
      {
        OFBool itemFound = OFFalse;

        for( unsigned int i=0 ; i < this->num && !itemFound ; i++ )
        {
          if( *this->items[i] == item )
            itemFound = OFTrue;
        }

        return( itemFound );
      }


    virtual OFBool IsSupersetOf( const OFOrderedSet<T> &other ) const
      {
        // if this contains less or the same amount of items than other, return OFFalse
        if( this->num <= other.num )
          return( OFFalse );

        // initialize result with OFTrue
        OFBool result = OFTrue;

        // make a copy of this
        OFOrderedSet<T> s = *this;

        // as long as result is OFTrue go through all items in other
        for( unsigned int i=0 ; i<other.num && result == OFTrue ; i++ )
        {
          // in case s contains the current item of other
          if( s.Contains( *other.items[i] ) )
          {
            // remove this item from s so that it will not be
            // considered again in a later call to s.Contains()
            s.Remove( *other.items[i] );
          }
          // in case s does not contain the current item of other the result is OFFalse
          else
            result = OFFalse;
        }

        // return result
        return( result );
      }


    virtual OFBool IsSubsetOf( const OFOrderedSet<T> &other ) const
      {
        return( other.IsSupersetOf( *this ) );
      }


    OFOrderedSet<T> Union( const OFOrderedSet<T> &other ) const
      {
        // initialize result set
        OFOrderedSet<T> resultSet = *this;

        // insert other set into result set
        resultSet.Insert( other );

        // return result set
        return( resultSet );
      }


    OFOrderedSet<T> Intersection( const OFOrderedSet<T> &other ) const
      {
        // initialize result set
        OFOrderedSet<T> resultSet;

        // make a copy of other
        OFOrderedSet<T> s = other;

        // go through all items in this
        for( unsigned int i=0 ; i < this->num ; i++ )
        {
          // if s contains the current item
          if( s.Contains( *this->items[i] ) )
          {
            // insert the item into the result set
            resultSet.Insert( *this->items[i] );

            // and remove the item from s so that it will not be
            // considered again in a later call to s.Contains()
            s.Remove( *this->items[i] );
          }
        }

        // return result set
        return( resultSet );
      }


    OFOrderedSet<T> Difference( const OFOrderedSet<T> &other ) const
      {
        // initialize result set
        OFOrderedSet<T> resultSet;

        // make a copy of other
        OFOrderedSet<T> s = other;

        // go through all items in this
        for( unsigned int i=0 ; i < this->num ; i++ )
        {
          // if s does not contain the current item
          if( !s.Contains( *this->items[i] ) )
          {
            // insert the item into the result set
            resultSet.Insert( *this->items[i] );
          }
          else
          {
            // else remove the item from s so that it will not be
            // considered again in a later call to s.Contains()
            s.Remove( *this->items[i] );
          }
        }

        // return result set
        return( resultSet );
      }


    OFOrderedSet<T> SymmetricDifference( const OFOrderedSet<T> &other ) const
      {
        // determine s1 = this - other
        OFOrderedSet<T> s1 = (*this).Difference( other );

        // determine s2 = other - this
        OFOrderedSet<T> s2 = other.Difference( *this );

        // determine the union of s1 and s2
        OFOrderedSet<T> resultSet = s1.Union( s2 );

        // return result set
        return( resultSet );
      }
};


#endif

/*
** CVS/RCS Log:
** $Log: ofoset.h,v $
** Revision 1.9  2004/04/21 10:00:52  meichel
** Minor modifications for compilation with gcc 3.4.0
**
** Revision 1.8  2002/12/17 17:01:33  wilkens
** Modified code again to keep Sun CC 2.0.1 happy on Solaris 2.5.1 (template
** errors).
**
** Revision 1.7  2002/12/16 10:40:24  wilkens
** Removed superfluous implementation files and modified header and make files.
**
** Revision 1.6  2002/12/13 12:26:50  wilkens
** Modified code to keep Sun CC 2.0.1 happy on Solaris 2.5.1 (template errors).
**
** Revision 1.5  2002/12/09 13:03:55  joergr
** Renamed parameter to avoid name clash with global function index().
**
** Revision 1.4  2002/07/09 18:29:45  wilkens
** Added some more functionality.
**
** Revision 1.2  2002/07/02 15:41:33  wilkens
** Made some modifications to keep gcc version egcs-2.91.66 quiet.
**
** Revision 1.1  2002/07/02 15:19:54  wilkens
** Added container classes OFOrderedSet and OFUnorderedSet which
** are based on the new abstract class OFSet.
**
**
*/

---

Generated on 4 Nov 2004 for OFFIS DCMTK Version 3.5.3 by Doxygen 1.3.8