Main Page | Namespace List | Class Hierarchy | Alphabetical List | Class List | File List | Namespace Members | Class Members | File Members | Related Pages

# Tools/RangeArray.h

Go to the documentation of this file.

    00001 /**
    00002  * @file RangeArray.h
    00003  *
    00004  * The file defines a template class to represent arrays of ranges.
    00005  *
    00006  * @author <a href="mailto:juengel@informatik.hu-berlin.de">Matthias Juengel</a>
    00007  */
    00008
    00009 #ifndef __RangeArray_h__
    00010 #define __RangeArray_h__
    00011
    00012 /**
    00013  * A template class to represent arrays of ranges.
    00014  */
    00015 template <class T> class RangeArray
    00016 {
    00017   public:
    00018     RangeArray() {numberOfClusters = 0;}
    00019     void reset() {numberOfClusters = 0;}
    00020
    00021     int getNumberOfClusters() {return numberOfClusters;}
    00022
    00023     Range<T> getCluster(int index)
    00024     {
    00025       Range<T> defaultRange;
    00026       if(index < numberOfClusters) return clusters[index];
    00027       else return defaultRange;
    00028     };
    00029
    00030     bool isLeftOnBorder(int index) {return leftIsOnBorder[index];}
    00031     bool isRightOnBorder(int index) {return rightIsOnBorder[index];}
    00032
    00033     void add(Range<T> newRange, bool leftOnBorder, bool rightOnBorder)
    00034     {
    00035       bool createNewCluster = true;
    00036       for(int clusterIndex = 0; clusterIndex < numberOfClusters; clusterIndex++)
    00037       {
    00038         // Does the new range overlap with the current range?
    00039         if(!(newRange < clusters[clusterIndex]) && !(newRange > clusters[clusterIndex]))
    00040         {
    00041           createNewCluster = false;
    00042           //enlarge the cluster
    00043           clusters[clusterIndex].add(newRange);
    00044           if(leftOnBorder) leftIsOnBorder[clusterIndex] = true;
    00045           if(rightOnBorder) rightIsOnBorder[clusterIndex] = true;
    00046
    00047           //check if the enlarged cluster overlaps with an existing cluster
    00048           for(int j = 0; j < numberOfClusters; j++)
    00049           {
    00050             if(j != clusterIndex)
    00051             {
    00052               if(!(clusters[j] < clusters[clusterIndex]) && !(clusters[j] > clusters[clusterIndex]))
    00053               {
    00054                 //combine the overlapping clusters
    00055                 clusters[clusterIndex].add(clusters[j]);
    00056                 if(leftIsOnBorder[j]) leftIsOnBorder[clusterIndex] = true;
    00057                 if(rightIsOnBorder[j]) rightIsOnBorder[clusterIndex] = true;
    00058                 clusters[j] = clusters[numberOfClusters-1];
    00059                 leftIsOnBorder[j] = leftIsOnBorder[numberOfClusters-1];
    00060                 rightIsOnBorder[j] = rightIsOnBorder[numberOfClusters-1];
    00061                 j--;
    00062                 numberOfClusters--;
    00063               }
    00064             } //if(j != clusterIndex)
    00065           }// for(int j = 0; j < numberOfClusters; j++)
    00066         }// Does the new range overlap with the current range?
    00067       }// for(int clusterIndex = 0; clusterIndex < numberOfClusters; clusterIndex++)
    00068       if(createNewCluster)
    00069       {
    00070         clusters[numberOfClusters] = newRange;
    00071         leftIsOnBorder[numberOfClusters] = leftOnBorder;
    00072         rightIsOnBorder[numberOfClusters] = rightOnBorder;
    00073         numberOfClusters++;
    00074       }
    00075     }
    00076
    00077   private:
    00078     enum {maxNumberOfRanges = 25};
    00079     Range<T> clusters[maxNumberOfRanges];
    00080     bool leftIsOnBorder[maxNumberOfRanges];
    00081     bool rightIsOnBorder[maxNumberOfRanges];
    00082     int numberOfClusters;
    00083 };
    00084
    00085 #endif // __RangeArray_h__