AMRange.h

Go to the documentation of this file.

 
#ifndef AMCORE_AMRANGE_H
#define AMCORE_AMRANGE_H
 
#include <set>
#include <algorithm>
 
namespace AMCore {
 
    template<typename T>
    class AMRange
    {
    public:
        T from;
        T to;
 
        AMRange();
 
        AMRange(T _from, T _to);
 
        inline bool operator<(const AMRange &right) const;
 
        inline AMRange &operator-=(const AMRange &right);
 
        inline AMRange &operator+=(const AMRange &right);
 
        inline bool operator==(const AMRange &right) const;
 
        inline bool operator!=(const AMRange &right) const;
 
        inline AMRange &intersect(const AMRange &right);
 
        inline bool valid() const;
 
        inline bool nonEmpty() const;
 
        inline bool in(T num) const;
 
        inline bool in(const AMRange &rng) const;
 
        inline bool empty() const;
    };
 
    template<typename T>
    inline AMRange<T> intersect(const AMRange<T> &left, const AMRange<T> &right);
    template<typename T>
    inline AMRange<T> operator+(const AMRange<T> &left, const AMRange<T> &right);
    template<typename T>
    inline AMRange<T> operator-(const AMRange<T> &left, const AMRange<T> &right);
 
    template<typename T>
    bool isPacked(const std::set<AMRange<T> > &s);
    template<typename T>
    bool valid(const std::set<AMRange<T> > &s);
    template<typename T>
    std::set<AMRange<T> > pack(const std::set<AMRange<T> > &s);
    template<typename T>
    std::set<AMRange<T> > operator+(const std::set<AMRange<T> > &left, const std::set<AMRange<T> > &right);
    template<typename T>
    std::set<AMRange<T> > operator-(const std::set<AMRange<T> > &left, const std::set<AMRange<T> > &right);
    template<typename T>
    std::set<AMRange<T> > operator+(const AMRange<T> &left, const std::set<AMRange<T> > &right);
    template<typename T>
    std::set<AMRange<T> > operator-(const AMRange<T> &left, const std::set<AMRange<T> > &right);
    template<typename T>
    std::set<AMRange<T> > operator+(const std::set<AMRange<T> > &left, const AMRange<T> &right);
    template<typename T>
    std::set<AMRange<T> > operator-(const std::set<AMRange<T> > &left, const AMRange<T> &right);
 
 
    template<typename T>
    AMRange<T>::AMRange()
        : from(),
          to()
    {
    };
 
    template<typename T>
    AMRange<T>::AMRange(T _from, T _to)
        : from(_from),
          to(_to)
    {
    };
 
    template<typename T>
    inline bool AMRange<T>::operator<(const AMRange<T> &right) const
    {
        if (from < right.from)  {
            return true;
        } else if (from == right.from) {
            return to < right.to;
        }
        return false;
    }
 
    template<typename T>
    inline AMRange<T> &AMRange<T>::operator-=(const AMRange<T> &right)
    {
        if (!valid()) {
            return *this;
        }
        if (!right.valid()) {
            from = right.from;
            to = right.to;
            return *this;
        }
        if (from < right.from) {
            if (to > right.to) {
                T t = to;
                to = from;
                from = t;
            }else if (to > right.from) {
                to = right.from;
            }
        } else {
            if (to < right.to) {
                to = from;
            } else if (from < right.to) {
                from = right.to;
            }
        }
        return *this;
    }
 
    template<typename T>
    inline AMRange<T> &AMRange<T>::intersect(const AMRange<T> &right)
    {
        if (from < right.from) {
            from = right.from;
        }
        if (to > right.to) {
            to = right.to;
        }
        if (to < from) {
            to = from;
        }
        return *this;
    }
 
    template<typename T>
    inline AMRange<T> &AMRange<T>::operator+=(const AMRange<T> &right)
    {
        if (!valid()) {
            return *this;
        }
        if (!right.valid()) {
            from = right.from;
            to = right.to;
            return *this;
        }
        if (to < right.from || from > right.to) {
            if (from == to) {
                from = right.from;
                to = right.to;
            } else {
                T t = to;
                to = from;
                from = t;
            }
        } else {
            if (to < right.to) {
                to = right.to;
            }
            if (from > right.from) {
                from = right.from;
            }
        }
        return *this;
    }
 
    template<typename T>
    inline bool AMRange<T>::operator==(const AMRange<T> &right) const
    {
        return (from == right.from && to == right.to);
    }
 
    template<typename T>
    inline bool AMRange<T>::operator!=(const AMRange<T> &right) const
    {
        return (from != right.from || to != right.to);
    }
 
 
    template<typename T>
    inline bool AMRange<T>::valid() const
    {
        return (to >= from);
    }
 
    template<typename T>
    inline bool AMRange<T>::in(T num) const
    {
        return ((num >= from) && (num < to));
    }
 
    template<typename T>
    inline bool AMRange<T>::empty() const
    {
        return to == from;
    }
 
    template<typename T>
    inline bool AMRange<T>::nonEmpty() const
    {
        return to > from;
    }
 
    template<typename T>
    inline bool AMRange<T>::in(const AMRange<T> &_rng) const
    {
        return ((_rng.from >= from) && (_rng.to <= to) && (_rng.from < _rng.to));
    }
 
    template<typename T>
    inline AMRange<T> operator+(const AMRange<T> &left, const AMRange<T> &right)
    {
        AMRange<T> r = left;
        r += right;
        return r;
    }
 
    template<typename T>
    inline AMRange<T> operator-(const AMRange<T> &left, const AMRange<T> &right)
    {
        AMRange<T> r = left;
        r -= right;
        return r;
    }
 
    template<typename T>
    inline AMRange<T> intersect(const AMRange<T> &left, const AMRange<T> &right)
    {
        AMRange<T> r = left;
        r.intersect(right);
        return r;
    }
 
    template<typename T>
    bool isPacked(const std::set<AMRange<T> > &s)
    {
        typename std::set<AMRange<T> >::iterator it = s.begin();
        if (it == s.end()) {
            return true;
        }
        typename std::set<AMRange<T> >::iterator itn = it;
        if (!itn->valid()) {
            return false;
        }
        itn++;
        while (itn != s.end()) {
            if (itn->from > it->to) {
                if (!itn->valid()) {
                    return false;
                }
                it = itn;
                itn++;
                continue;
            }
            return false;
        }
        return true;
    }
 
    template<typename T>
    bool valid(const std::set<AMRange<T> > &s)
    {
        for(typename std::set<AMRange<T> >::iterator it = s.begin(); it != s.end(); it++) {
            if (!it->valid()) {
                return false;
            }
        }
        return true;
    }
 
    template<typename T>
    std::set<AMRange<T> > pack(const std::set<AMRange<T> > &s)
    {
        AMRange<T> r;
        std::set<AMRange<T> > result;
        bool start = true;
        typename std::set<AMRange<T> >::iterator it = s.begin();
 
        do {
            do {
                if (it == s.end()) {
                    if (!start) {
                        result.insert(r);
                    }
                    return result;
                }
                if (it->valid()) {
                    break;
                }
                it++;
            } while (1);
 
            if (start) {
                r = *it;
                start = false;
                continue;
            }
            AMRange<T> rx = r + *it;
            if (rx.valid()) {
                r = rx;
            } else {
                result.insert(r);
                r = *it;
            }
            it++;
        } while(1);
    }
 
    template<typename T>
    std::set<AMRange<T> > operator+(const std::set<AMRange<T> > &left, const std::set<AMRange<T> > &right)
    {
        std::set<AMRange<T> > result = left;
        std::merge(left.begin(), left.end(),
            right.begin(), right.end(),
            std::inserter(result, result.begin()));
        result = pack(result);
        return result;
    }
 
    template<typename T>
    std::set<AMRange<T> > operator-(const std::set<AMRange<T> > &left, const std::set<AMRange<T> > &right)
    {
        if (left.size() == 0) {
            return std::set<AMRange<T> >();
        }
        if (right.size() == 0) {
            return left;
        }
        std::set<AMRange<T> > ls = pack(left);
        std::set<AMRange<T> > rs = pack(right);
        std::set<AMRange<T> > result;
        typename std::set<AMRange<T> >::iterator lit = ls.begin();
        typename std::set<AMRange<T> >::iterator rit = rs.begin();
        AMRange<int> r = *lit;
        while (1) {
            if (lit != ls.end()) {
                if (rit != rs.end()) {
                    AMRange<T> tr = r - *rit;
                    if (!tr.valid()) {
                        AMRange ir(r.from, rit->from);
                        if (ir.nonEmpty()) {
                            result.insert(ir);
                        }
                        r.from = rit->to;
                    } else {
                        r = tr;
                    }
                    if (lit->to > rit->to) {
                        rit++;
                    } else {
                        lit++;
                        if (lit != ls.end()) {
                            if (r.nonEmpty()) {
                                result.insert(r);
                            }
                            r = *lit;
                        }
                    }
                } else {
                    lit++;
                    if (lit != ls.end()) {
                        if (r.nonEmpty()) {
                            result.insert(r);
                        }
                        r = *lit;
                    }
                }
            } else {
                if (rit != rs.end()) {
                    rit++;
                } else {
                    break;
                }
            }
        }
        if (r.nonEmpty()) {
            result.insert(r);
        }
        return result;
    }
 
    template<typename T>
    std::set<AMRange<T> > operator+(const AMRange<T> &left, const std::set<AMRange<T> > &right)
    {
        std::set<AMRange<T> > result = right;
        result.insert(left);
        result = pack(result);
        return result;
    }
    template<typename T>
    std::set<AMRange<T> > operator-(const AMRange<T> &left, const std::set<AMRange<T> > &right)
    {
        std::set<AMRange<T> > ls = {left};
        return ls - right;
    }
    template<typename T>
    std::set<AMRange<T> > operator+(const std::set<AMRange<T> > &left, const AMRange<T> &right)
    {
        std::set<AMRange<T> > result = left;
        result.insert(right);
        result = pack(result);
        return result;
    }
    template<typename T>
    std::set<AMRange<T> > operator-(const std::set<AMRange<T> > &left, const AMRange<T> &right)
    {
        std::set<AMRange<T> > rs = {right};
        return left - rs;
    }
}
 
#endif //AMCORE_AMRANGE_H