Tools/RangeArray.h

Go to the documentation of this file.

/**
 * @file RangeArray.h
 *
 * The file defines a template class to represent arrays of ranges.
 * 
 * @author <a href="mailto:juengel@informatik.hu-berlin.de">Matthias Juengel</a>
 */

#ifndef __RangeArray_h__
#define __RangeArray_h__

/**
 * A template class to represent arrays of ranges.
 */
template <class T> class RangeArray
{
  public:
    RangeArray() {numberOfClusters = 0;}
    void reset() {numberOfClusters = 0;}
    
    int getNumberOfClusters() {return numberOfClusters;}
    
    Range<T> getCluster(int index)
    {
      Range<T> defaultRange;
      if(index < numberOfClusters) return clusters[index];
      else return defaultRange;
    };

    bool isLeftOnBorder(int index) {return leftIsOnBorder[index];}
    bool isRightOnBorder(int index) {return rightIsOnBorder[index];}

    void add(Range<T> newRange, bool leftOnBorder, bool rightOnBorder)
    {
      bool createNewCluster = true;
      for(int clusterIndex = 0; clusterIndex < numberOfClusters; clusterIndex++)
      {
        // Does the new range overlap with the current range?
        if(!(newRange < clusters[clusterIndex]) && !(newRange > clusters[clusterIndex]))
        {
          createNewCluster = false;
          //enlarge the cluster
          clusters[clusterIndex].add(newRange);
          if(leftOnBorder) leftIsOnBorder[clusterIndex] = true;
          if(rightOnBorder) rightIsOnBorder[clusterIndex] = true;

          //check if the enlarged cluster overlaps with an existing cluster
          for(int j = 0; j < numberOfClusters; j++)
          {
            if(j != clusterIndex)
            {
              if(!(clusters[j] < clusters[clusterIndex]) && !(clusters[j] > clusters[clusterIndex]))
              {
                //combine the overlapping clusters
                clusters[clusterIndex].add(clusters[j]);
                if(leftIsOnBorder[j]) leftIsOnBorder[clusterIndex] = true;
                if(rightIsOnBorder[j]) rightIsOnBorder[clusterIndex] = true;
                clusters[j] = clusters[numberOfClusters-1];
                leftIsOnBorder[j] = leftIsOnBorder[numberOfClusters-1];
                rightIsOnBorder[j] = rightIsOnBorder[numberOfClusters-1];
                j--;
                numberOfClusters--;
              }
            } //if(j != clusterIndex)
          }// for(int j = 0; j < numberOfClusters; j++)
        }// Does the new range overlap with the current range?
      }// for(int clusterIndex = 0; clusterIndex < numberOfClusters; clusterIndex++)
      if(createNewCluster)
      {
        clusters[numberOfClusters] = newRange;
        leftIsOnBorder[numberOfClusters] = leftOnBorder;
        rightIsOnBorder[numberOfClusters] = rightOnBorder;
        numberOfClusters++;
      }
    }

  private:
    enum {maxNumberOfRanges = 25};
    Range<T> clusters[maxNumberOfRanges];
    bool leftIsOnBorder[maxNumberOfRanges];
    bool rightIsOnBorder[maxNumberOfRanges];
    int numberOfClusters;
};

#endif // __RangeArray_h__

/*
 * Change log:
 * 
 * $Log: RangeArray.h,v $
 * Revision 1.1.1.1  2004/05/22 17:35:55  cvsadm
 * created new repository GT2004_WM
 *
 * Revision 1.1  2003/10/07 10:13:21  cvsadm
 * Created GT2004 (M.J.)
 *
 * Revision 1.3  2003/09/28 09:28:48  juengel
 * Comments corrected.
 *
 * Revision 1.2  2003/09/26 15:28:10  juengel
 * Renamed DataTypes to representations.
 *
 * Revision 1.1  2003/09/26 11:40:40  juengel
 * - sorted tools
 * - clean-up in DataTypes
 *
 * Revision 1.1.1.1  2003/07/02 09:40:22  cvsadm
 * created new repository for the competitions in Padova from the 
 * tamara CVS (Tuesday 2:00 pm)
 *
 * removed unused solutions
 *
 * Revision 1.1  2003/06/12 16:55:13  juengel
 * Moved RangeArray to its own file.
 *
 *
 */

---