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__

---