Range.h

Go to the documentation of this file.

// SPDX-FileCopyrightText: The Bio++ Development Group
//
// SPDX-License-Identifier: CECILL-2.1

#ifndef BPP_NUMERIC_RANGE_H
#define BPP_NUMERIC_RANGE_H


#include "../Clonable.h"
#include "../Text/TextTools.h"

// From the STL:
#include <string>
#include <set>
#include <algorithm>
#include <iostream>
#include <cstddef>

namespace bpp
{
template<class T> class Range :
  public virtual Clonable
{
private:
  T begin_;
  T end_;

public:
  Range(const T& a = 0, const T& b = 0) :
    begin_(std::min(a, b)),
    end_(std::max(a, b))
  {}

  Range(const Range<T>& range) : begin_(range.begin_), end_(range.end_) {}

  Range<T>& operator=(const Range<T>& range)
  {
    begin_ = range.begin_;
    end_   = range.end_;
    return *this;
  }

  Range<T>* clone() const { return new Range<T>(*this); }

  virtual ~Range() {}

public:
  bool operator==(const Range<T>& r) const
  {
    return begin_ == r.begin_ && end_ == r.end_;
  }
  bool operator!=(const Range<T>& r) const
  {
    return begin_ != r.begin_ || end_ != r.end_;
  }
  bool operator<(const Range<T>& r) const
  {
    return begin_ < r.begin_ || end_ < r.end_;
  }
  virtual Range& operator+=(const T& val)
  {
    begin_ += val;
    end_ += val;
    return *this;
  }
  virtual Range operator+(const T& val)
  {
    return Range<T>(*this) += val;
  }
  virtual Range& operator-=(const T& val)
  {
    begin_ -= val;
    end_ -= val;
    return *this;
  }
  virtual Range operator-(const T& val)
  {
    return Range<T>(*this) -= val;
  }

  T begin() const { return begin_; }

  T end() const { return end_; }

  T length() const { return end_ - begin_; }

  bool overlap(const Range& r) const
  {
    return r.begin_ < end_ && r.end_ > begin_;
  }

  bool isContiguous(const Range& r) const
  {
    return r.begin_ == end_ || r.end_ == begin_;
  }

  bool contains(const Range& r) const
  {
    return r.begin_ >= begin_ && r.end_ <= end_;
  }

  void expandWith(const Range& r)
  {
    if (r.begin_ < begin_ && r.end_ >= begin_)
      begin_ = r.begin_;
    if (r.end_ > end_ && r.begin_ <= end_)
      end_ = r.end_;
  }

  void sliceWith(const Range& r)
  {
    if (!overlap(r))
    {
      begin_ = 0;
      end_   = 0;
    }
    else
    {
      if (r.begin_ > begin_ && r.begin_ <= end_)
        begin_ = r.begin_;
      if (r.end_ < end_ && r.end_ >= begin_)
        end_ = r.end_;
    }
  }

  bool isEmpty() const { return begin_ == end_; }

  std::string toString() const
  {
    return "[" + TextTools::toString(begin_) + "," + TextTools::toString(end_) + "[";
  }
};

template<class T> class RangeCollection
{
public:
  virtual ~RangeCollection() {}
  virtual void addRange(const Range<T>& r) = 0;

  virtual void restrictTo(const Range<T>& r) = 0;

  virtual void filterWithin(const Range<T>& r) = 0;

  virtual std::string toString() const = 0;

  virtual bool isEmpty() const = 0;

  virtual size_t size() const = 0;

  virtual size_t totalLength() const = 0;

  virtual const Range<T>& getRange(size_t i) const = 0;

  virtual void clear() = 0;
};

template<class T> class rangeComp_
{
public:
  bool operator()(const Range<T>* a, const Range<T>* b) const
  {
    return (*a) < (*b);
  }
};

template<class T> class RangeSet :
  public virtual RangeCollection<T>
{
public:

private:
  std::vector< Range<T>* > ranges_;

public:
  RangeSet() : ranges_() {}

  RangeSet(const RangeSet<T>& set) : ranges_()
  {
    for (const auto& it : set.ranges_)
    {
      ranges_.push_back(it->clone());
    }
  }

  RangeSet& operator=(const RangeSet<T>& set)
  {
    clear_();
    for (const auto& it : set.ranges_)
    {
      ranges_.push_back(it->clone());
    }
    return *this;
  }

  virtual ~RangeSet()
  {
    clear_();
  }

public:
  void addRange(const Range<T>& r)
  {
    if (!r.isEmpty())
      ranges_.push_back(r.clone());
  }

  void restrictTo(const Range<T>& r)
  {
    auto it = ranges_.begin();
    while (it != ranges_.end())
    {
      (**it).sliceWith(r);
      if ((**it).isEmpty())
      {
        delete *it;
        it = ranges_.erase(it);
      }
      else
      {
        ++it;
      }
    }
  }

  void filterWithin(const Range<T>& r)
  {
    auto it = ranges_.begin();
    while (it != ranges_.end())
    {
      if (r.contains(**it))
      {
        ++it;
      }
      else
      {
        delete *it;
        it = ranges_.erase(it);
      }
    }
  }

  std::string toString() const
  {
    std::string s = "{ ";
    for (const auto& it : ranges_)
    {
      s += it->toString() + " ";
    }
    s += "}";
    return s;
  }

  bool isEmpty() const { return ranges_.size() == 0; }

  size_t size() const { return ranges_.size(); }

  size_t totalLength() const
  {
    size_t tot = 0;
    for (const auto& it : ranges_)
    {
      tot += it->length();
    }
    return tot;
  }

  const Range<T>& getRange(size_t i) const
  {
    return *ranges_[i];
  }

  const std::vector< Range<T>* >& getSet() const { return ranges_; }

  std::vector< Range<T>* >& getSet() { return ranges_; }

  void clear()
  {
    clear_();
  }

private:
  void clear_()
  {
    for (auto it = ranges_.begin(); it != ranges_.end(); ++it)
    {
      delete *it;
    }
    ranges_.clear();
  }
};

template<class T> class MultiRange :
  public virtual RangeCollection<T>
{
private:
  std::vector<Range<T>*> ranges_;

public:
  MultiRange() : ranges_() {}

  MultiRange(const MultiRange<T>& mr) : ranges_()
  {
    for (size_t i = 0; i < mr.ranges_.size(); ++i)
    {
      ranges_.push_back(mr.ranges_[i]->clone());
    }
  }

  MultiRange& operator=(const MultiRange<T>& mr)
  {
    clear_();
    for (size_t i = 0; i < mr.ranges_.size(); ++i)
    {
      ranges_.push_back(mr.ranges_[i]->clone());
    }
    return *this;
  }

  virtual ~MultiRange()
  {
    clear_();
  }

public:
  void addRange(const Range<T>& r)
  {
    // this is a bit tricky, as many cases can happen. we have to check how many ranges overlap with the new one:
    std::vector<size_t> overlappingPositions;
    for (size_t i = 0; i < ranges_.size(); ++i)
    {
      if (ranges_[i]->overlap(r))
        overlappingPositions.push_back(i);
    }
    // check if not overlap:
    if (overlappingPositions.size() == 0)
    {
      // We simply add the new range to the list:
      ranges_.push_back(r.clone());
    }
    else
    {
      // We extend the first overlapping element:
      ranges_[overlappingPositions[0]]->expandWith(r);
      // Now we merge all other overlapping ranges, if any:
      for (size_t i = overlappingPositions.size() - 1; i > 0; --i)
      {
        // Expand first range:
        ranges_[overlappingPositions[0]]->expandWith(*ranges_[overlappingPositions[i]]);
        // Then removes this range:
        delete ranges_[overlappingPositions[i]];
        ranges_.erase(ranges_.begin() + static_cast<ptrdiff_t>(overlappingPositions[i]));
      }
    }
    clean_();
  }

  void restrictTo(const Range<T>& r)
  {
    for (auto& it : ranges_)
    {
      it->sliceWith(r);
    }
    clean_();
  }

  void filterWithin(const Range<T>& r)
  {
    auto it = ranges_.begin();
    while (it != ranges_.end())
    {
      if (r.contains(**it))
      {
        ++it;
      }
      else
      {
        delete *it;
        it = ranges_.erase(it);
      }
    }
  }

  std::string toString() const
  {
    std::string s = "{ ";
    for (const auto& it : ranges_)
    {
      s += it->toString() + " ";
    }
    s += "}";
    return s;
  }

  std::vector<T> getBounds() const
  {
    std::vector<T> bounds;
    for (const auto& it : ranges_)
    {
      bounds.push_back(it->begin());
      bounds.push_back(it->end());
    }
    return bounds;
  }

  bool isEmpty() const { return ranges_.size() == 0; }

  size_t size() const { return ranges_.size(); }

  size_t totalLength() const
  {
    size_t tot = 0;
    for (const auto& it : ranges_)
    {
      tot += it->length();
    }
    return tot;
  }

  const Range<T>& getRange(size_t i) const { return *ranges_[i]; }

  void clear()
  {
    clear_();
  }

private:
  void clean_()
  {
    // Reorder
    rangeComp_<T> comp;
    std::sort(ranges_.begin(), ranges_.end(), comp);
    // Remove empty intervals:
    auto it = ranges_.begin();
    while (it != ranges_.end())
    {
      if ((**it).isEmpty())
      {
        delete *it;
        it = ranges_.erase(it);
      }
      else
      {
        ++it;
      }
    }
  }

private:
  void clear_()
  {
    for (size_t i = 0; i < ranges_.size(); ++i)
    {
      delete ranges_[i];
    }
    ranges_.clear();
  }
};
} // end of namespace bpp
#endif // BPP_NUMERIC_RANGE_H