QIntervalSet.cc

Go to the documentation of this file.

#include "QIntervalSet.hh"
#include <algorithm>
#include "TString.h"
using std::list;
 
QObjectImp(Diana::QIntervalSet);
 
Q_BEGIN_NAMESPACE
 
QIntervalSet::QIntervalSet()
    : fIsLowerBoundSet(false), fIsUpperBoundSet(false)
{
}
 
QIntervalSet::QIntervalSet(const double min, const double max)
    : fIsLowerBoundSet(false), fIsUpperBoundSet(false)
{
    QInterval interval(min, max);
    fIntervals.push_back(interval);
}
 
void QIntervalSet::Clear()
{
    fIntervals.clear();
    fIsLowerBoundSet = false;
    fIsUpperBoundSet = false;
    fLowerBound = Q_DOUBLE_DEFAULT;
    fUpperBound = Q_DOUBLE_DEFAULT;
}
 
void QIntervalSet::CloseGapsSmallerThan(const double smallestAllowedGap)
{
    if (Size() >= 2) {
        list<QInterval>::iterator currentInterval = fIntervals.begin();
        list<QInterval>::iterator nextInterval = currentInterval;
        ++nextInterval;
        while (nextInterval != fIntervals.end()) {
            const double gap
                = nextInterval->GetMin() - currentInterval->GetMax();
            if (gap <= smallestAllowedGap) {
                // combine current and next intervals, eliminating gap
                currentInterval->SetMax(nextInterval->GetMax());
                fIntervals.erase(nextInterval);
            }
            else {
                ++currentInterval;
            }
            nextInterval = currentInterval;
            ++nextInterval;
        }
    }
    
    if (fIsLowerBoundSet && !fIntervals.empty()) {
        const double gap = fIntervals.front().GetMin() - fLowerBound;
        if (gap <= smallestAllowedGap) {
            // eliminate gap between lower bound and first interval
            fIntervals.front().SetMin(fLowerBound);
        }
    }
    if (fIsUpperBoundSet && !fIntervals.empty()) {
        const double gap = fUpperBound - fIntervals.back().GetMax();
        if (gap <= smallestAllowedGap) {
            // eliminate gap between last interval and upper bound
            fIntervals.back().SetMax(fUpperBound);
        }
    }
}
 
bool QIntervalSet::Consolidate()
{
    bool foundOverlappedIntervals = false;
    
    list<QInterval>::iterator currentInterval = fIntervals.begin();
    while (foundOverlappedIntervals == false
           && currentInterval != fIntervals.end()) {
        list<QInterval>::iterator nextInterval = currentInterval;
        ++nextInterval;
        if (nextInterval != fIntervals.end()) {
            if (currentInterval->GetMax() >= nextInterval->GetMin()) {
                foundOverlappedIntervals = true;
                currentInterval->SetMax(
                    std::max(currentInterval->GetMax(), nextInterval->GetMax())
                );
                fIntervals.erase(nextInterval);
            }
        }
        
        ++currentInterval;
    }
    
    if (foundOverlappedIntervals) {
        Consolidate();
    }
    
    return foundOverlappedIntervals;
}
 
bool QIntervalSet::Contains(const double value) const
{
    bool contains = false;
    
    list<QInterval>::const_iterator currentInterval = fIntervals.begin();
    while (currentInterval != fIntervals.end()
           && value >= currentInterval->GetMin()) {
        contains = currentInterval->Contains(value);
        ++currentInterval;
    }
    
    return contains;
}
 
QMatrix QIntervalSet::GetMatrix()
{
    QMatrix matrix(Size(), 2);
    int row = 0;
    std::list<QInterval>::const_iterator interval;
    for (interval  = fIntervals.begin();
         interval != fIntervals.end();
         ++interval, ++row) {
        matrix(row, 0) = interval->GetMin();
        matrix(row, 1) = interval->GetMax();
    }
    return matrix;
}
 
void QIntervalSet::Insert(QInterval interval)
{
    if (fIsLowerBoundSet && interval.GetMin() < fLowerBound) {
        if (interval.GetMax() <= fLowerBound) {
            return;
        }
        interval.SetMin(fLowerBound);
    }
    if (fIsUpperBoundSet && interval.GetMax() > fUpperBound) {
        if (interval.GetMin() >= fUpperBound) {
            return;
        }
        interval.SetMax(fUpperBound);
    }
 
    if (fIntervals.empty()) {
        fIntervals.push_back(interval);
    }
    else if (interval.GetMin() > GetMax()) {
        fIntervals.push_back(interval);
    }
    else if (interval.GetMax() < GetMin()) {
        fIntervals.insert(fIntervals.begin(), interval);
    }
    else {
        list<QInterval>::iterator insertionPoint
            = lower_bound(fIntervals.begin(), fIntervals.end(), interval);
        // insertionPoint refers to the first position in which interval can be
        // inserted while preserving the ordering 
        // (the ordering is like std::pair)
        if (insertionPoint == fIntervals.end()) {
            bool intersectsPreceeding
                = interval.GetMin() <= fIntervals.back().GetMax();
            if (intersectsPreceeding) {
                // expand preceeding interval
                fIntervals.back().SetMax(
                    std::max(interval.GetMax(), fIntervals.back().GetMax()));
            }
            else {
                // interval is past last interval in fIntervals
                fIntervals.push_back(interval);
            }
        }
        else if (insertionPoint == fIntervals.begin()) {
            bool intersectsFollowing
                = interval.GetMax() >= fIntervals.front().GetMin();
            if (intersectsFollowing) {
                // extend following interval
                fIntervals.front().SetMin(
                    std::min(interval.GetMin(), fIntervals.front().GetMin())
                );
                fIntervals.front().SetMax(
                    std::max(interval.GetMax(), fIntervals.front().GetMax())
                );
            }
            else {
                // interval is before first interval in fIntervals
                fIntervals.insert(insertionPoint, interval);
            }
        }
        else {
            list<QInterval>::iterator preceedingInterval = insertionPoint;
            --preceedingInterval;
            bool intersectsPreceeding
                = interval.GetMin() <= preceedingInterval->GetMax();
            bool intersectsFollowing
                = interval.GetMax() >= insertionPoint->GetMin();
            if (!intersectsPreceeding && !intersectsFollowing) {
                // interval is disjoint from existing intervals in fIntervals
                // insert interval
                fIntervals.insert(insertionPoint, interval);
            }
            else if (intersectsPreceeding && !intersectsFollowing) {
                // extend preceeding interval
                preceedingInterval->SetMax(
                    std::max(
                        interval.GetMax(),
                        preceedingInterval->GetMax()
                    )
                );
            }
            else if (intersectsFollowing && !intersectsPreceeding) {
                // extend following interval
                insertionPoint->SetMin(
                    std::min(
                        interval.GetMin(),
                        insertionPoint->GetMin()
                    )
                );
                insertionPoint->SetMax(
                    std::max(
                        interval.GetMax(),
                        insertionPoint->GetMax()
                    )
                );
            }
            else if (intersectsPreceeding && intersectsFollowing) {
                // combine preceeding and following intervals
                preceedingInterval->SetMax(
                    std::max(
                        interval.GetMax(),
                        insertionPoint->GetMax()
                    )
                );
                fIntervals.erase(insertionPoint);
            }
        }
    }
    
    Consolidate();
}
 
double QIntervalSet::Length() const
{
    double length = 0;
    for (list<QInterval>::const_iterator interval = fIntervals.begin();
         interval != fIntervals.end();
         ++interval) {
        length += interval->Length();
    }
    return length;
}
 
void QIntervalSet::RemoveIntervalsShorterThan(const double minimumLength)
{
    list<QInterval>::iterator currentInterval = fIntervals.begin();
    while (currentInterval != fIntervals.end()) {
        if (currentInterval->Length() <= minimumLength) {
            currentInterval = fIntervals.erase(currentInterval);
        }
        else {
            ++currentInterval;
        }
    }
}
 
void QIntervalSet::SetLowerBound(const double lowerBound)
{
    fLowerBound = lowerBound;
    fIsLowerBoundSet = true;
        
    while (!fIntervals.empty() && GetMin() < fLowerBound) {
        if (fIntervals.front().GetMax() <= fLowerBound) {
            fIntervals.pop_front();
        }
        else {
            fIntervals.front().SetMin(fLowerBound);
            break;
        }
    }
}
 
void QIntervalSet::SetUpperBound(const double upperBound)
{
    fUpperBound = upperBound;
    fIsUpperBoundSet = true;
    
    while (!fIntervals.empty() && GetMax() > fUpperBound) {
        if (fIntervals.back().GetMin() >= fUpperBound) {
            fIntervals.pop_back();
        }
        else {
            fIntervals.back().SetMax(fUpperBound);
            break;
        }
    }
}
 
void QIntervalSet::Dump(std::ostream &o) const {
  o << "Lower Bound : " << (fIsLowerBoundSet ? Form("%f",fLowerBound) : "None") << std::endl;
  o << "Upper Bound : " << (fIsUpperBoundSet ? Form("%f",fUpperBound) : "None") << std::endl;
 
  std::list<QInterval>::const_iterator it;
  for(it=fIntervals.begin();it!=fIntervals.end();it++) {
    o << "\t" << it->GetMin() << " - " << it->GetMax() << std::endl;
  }
}
 
Q_END_NAMESPACE