Range2d.h

Go to the documentation of this file.

// 
//   Copyright (C) 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012
//   Free Software Foundation, Inc
// 
// This program is free software; you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation; either version 3 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.
// 
// You should have received a copy of the GNU General Public License
// along with this program; if not, write to the Free Software
// Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA

//
// Original author: Sandro Santilli <strk@keybit.net>
//

#ifndef GNASH_RANGE2D_H
#define GNASH_RANGE2D_H

#include <ostream>
#include <limits>
#include <algorithm>
#include <cassert> // for inlines
#include <cmath> // for floor / ceil
#include <cstdint>

namespace gnash {

namespace geometry {

enum RangeKind {
        finiteRange,

        nullRange,

        // 
        worldRange
};

namespace detail {
    template <typename U> struct Promote { typedef U type; };
    template <> struct Promote<float> { typedef double type; };
    template <> struct Promote<int> { typedef std::int64_t type; };
    template <> struct Promote<unsigned int> { typedef std::uint64_t type; };
}

//
template <typename T>
class Range2d
{
public:

        template <typename U>
        friend std::ostream& operator<< (std::ostream& os, const Range2d<U>& rect);

        //
        template <typename U>
        friend bool operator== (const Range2d<U>& r1, const Range2d<U>& r2);

        //
        template <typename U>
        friend bool operator!= (const Range2d<U>& r1, const Range2d<U>& r2);

        //
        template <typename U> friend Range2d<U>
        Intersection(const Range2d<U>& r1, const Range2d<U>& r2);

        template <typename U> friend Range2d<U>
        Union(const Range2d<U>& r1, const Range2d<U>& r2);

        //
        Range2d(RangeKind kind=nullRange)
                :
                _xmin(T()),
                _xmax(T()),
                _ymin(T()),
                _ymax(T())
        {
                switch ( kind )
                {
                        case worldRange:
                                setWorld();
                                break;
                        case nullRange:
                                setNull();
                                break;
                        default:
                        case finiteRange:
                                break;
                }
        }

        //
        Range2d(T xmin, T ymin, T xmax, T ymax)
                :
                _xmin(xmin),
                _xmax(xmax),
                _ymin(ymin),
                _ymax(ymax)
        {
                // use the default ctor to make a NULL Range2d
                assert(_xmin <= _xmax);
                assert(_ymin <= _ymax);
                // .. or should we raise an exception .. ?
        }

        template <typename U>
        Range2d(const Range2d<U>& from)
        {
                if ( from.isWorld() ) {
                        setWorld();
                } else if ( from.isNull() ) {
                        setNull();
                } else {
                        _xmin = roundMin(from.getMinX());
                        _ymin = roundMin(from.getMinY());
                        _xmax = roundMax(from.getMaxX());
                        _ymax = roundMax(from.getMaxY());
                }
        }

        bool isNull() const
        {
                return _xmax < _xmin;
        }

        //
        Range2d<T>& setNull()
        {
                _xmin = std::numeric_limits<T>::max();
                _xmax = std::numeric_limits<T>::min();
                _ymin = 0;
                _ymax = 0;
                return *this;
        }

        bool isWorld() const
        {
                return _xmax == std::numeric_limits<T>::max()
                        && _xmin == std::numeric_limits<T>::min();
        }

        //
        bool isFinite() const
        {
                return ( ! isNull() && ! isWorld() );
        }

        //
        Range2d<T>& setWorld()
        {
                _xmin = std::numeric_limits<T>::min();
                _xmax = std::numeric_limits<T>::max();
                _ymin = 0;
                _ymax = 0;
                return *this;
        }

        //
        template <typename U>
        bool contains(U x, U y) const
        {
                if ( isNull() ) return false;
                if ( isWorld() ) return true;
                if (x < _xmin || x > _xmax || y < _ymin || y > _ymax)
                {
                        return false;
                }
                return true;
        }

        //
        bool contains(const Range2d<T>& other) const
        {
                if ( isNull() || other.isNull() ) return false;
                if ( isWorld() ) return true;
                if ( other.isWorld() ) return false;

                return _xmin <= other._xmin &&
                        _xmax >= other._xmax &&
                        _ymin <= other._ymin &&
                        _ymax >= other._ymax;
        }

        //
        bool intersects(const Range2d<T>& other) const
        {
                if ( isNull() || other.isNull() ) return false;
                if ( isWorld() || other.isWorld() ) return true;

                if ( _xmin > other._xmax ) return false;
                if ( _xmax < other._xmin ) return false;
                if ( _ymin > other._ymax ) return false;
                if ( _ymax < other._ymin ) return false;
                return true;
        }

        //
        Range2d<T>& expandTo(T x, T y)
        {
                // A WORLD range already enclose every point
                if ( isWorld() ) return *this;

                if ( isNull() ) 
                {
                        setTo(x,y);
                }
                else
                {
                        _xmin = std::min(_xmin, x);
                        _ymin = std::min(_ymin, y);
                        _xmax = std::max(_xmax, x);
                        _ymax = std::max(_ymax, y);
                }

                return *this;
        }

        //
        Range2d<T>& expandToCircle(T x, T y, T radius)
        {
                // A WORLD range already enclose every point
                if ( isWorld() ) return *this;

        expandTo(x-radius, y);
        expandTo(x+radius, y);

        expandTo(x, y-radius);
        expandTo(x, y+radius);

                return *this;
        }

        //
        Range2d<T>& setTo(T x, T y)
        {
                _xmin = _xmax = x;
                _ymin = _ymax = y;
                return *this;
        }

        //
        //
        Range2d<T>& setTo(T xmin, T ymin, T xmax, T ymax)
        {
                _xmin = xmin;
                _xmax = xmax;
                _ymin = ymin;
                _ymax = ymax;

                // use the default ctor to make a NULL Range2d
                assert(_xmin <= _xmax);
                assert(_ymin <= _ymax);

                return *this;
        }

        //
        T width() const
        {
                assert ( ! isWorld() );
                if ( isNull() ) return 0;
                return _xmax-_xmin;
        }

        //
        T height() const
        {
                assert ( ! isWorld() );
                if ( isNull() ) return 0;
                return _ymax-_ymin;
        }

        //
        Range2d<T>& shiftX(T offset)
        {
                if ( isNull() || isWorld() ) return *this;
                _xmin += offset;
                _xmax += offset;
                return *this;
        }

        //
        Range2d<T>& shiftY(T offset)
        {
                if ( isNull() || isWorld() ) return *this;
                _ymin += offset;
                _ymax += offset;
                return *this;
        }

        Range2d<T>& scaleX(float factor)
        {
                return scale(factor, 1);
        }

        Range2d<T>& scaleY(float factor)
        {
                return scale(1, factor);
        }

        //
        Range2d<T>& scale(float xfactor, float yfactor)
        {
                assert(xfactor >= 0 && yfactor >= 0);

                if ( ! isFinite() ) return *this;

                if ( xfactor == 0 || yfactor == 0 )
                {
                        return setNull();
                }

                if ( xfactor != 1 )
                {
                        _xmin = scaleMin(_xmin, xfactor);
                        _xmax = scaleMax(_xmax, xfactor);
                        assert(_xmin <= _xmax); // in case of overflow...
                }

                if ( yfactor != 1 )
                {
                        _ymin = scaleMin(_ymin, yfactor);
                        _ymax = scaleMax(_ymax, yfactor);
                        assert(_ymin <= _ymax); // in case of overflow...
                }

                return *this;
        }

        Range2d<T>& scale(float factor)
        {
                return scale(factor, factor);
        }

        //
        Range2d<T>& growBy(T amount)
        {
                if ( isNull() || isWorld() || amount==0 ) return *this;

                // NOTE: this trigger a compiler warning when T is an
                //       unsigned type (Coverity CID 1154656 -
                //       logically dead code)
                if ( amount < 0 ) return shrinkBy(-amount);

                T newxmin = _xmin - amount;
                if (newxmin > _xmin ) return setWorld();
                else _xmin = newxmin;

                T newxmax = _xmax + amount;
                if (newxmax < _xmax ) return setWorld();
                else _xmax = newxmax;

                T newymin = _ymin - amount;
                if (newymin > _ymin ) return setWorld();
                else _ymin = newymin;

                T newymax = _ymax + amount;
                if (newymax < _ymax ) return setWorld();
                else _ymax = newymax;

                return *this;

        }

        //
        Range2d<T>& shrinkBy(T amount)
        {
                if ( isNull() || isWorld() || amount==0 ) return *this;

                // NOTE: this trigger a compiler warning when T is an
                //       unsigned type (Coverity CID 1154655 -
                //       logically dead code)
                if ( amount < 0 ) return growBy(-amount);

                // Turn this range into the NULL range
                // if any dimension collapses.
                // Don't use width() and height() to 
                // avoid superflous checks.

                if ( _xmax - _xmin <= amount ) return setNull();
                if ( _ymax - _ymin <= amount ) return setNull();

                _xmin += amount;
                _ymin += amount;
                _xmax -= amount;
                _ymax -= amount;

                return *this;

        }

        //
        T getMinX() const
        {
                assert ( isFinite() );
                return _xmin;
        }

        //
        T getMaxX() const
        {
                assert ( isFinite() );
                return _xmax;
        }

        //
        T getMinY() const
        {
                assert ( isFinite() );
                return _ymin;
        }

        //
        T getMaxY() const
        {
                assert ( isFinite() );
                return _ymax;
        }


        //
        typename detail::Promote<T>::type
        getArea() const {
            assert ( !isWorld() );
            if ( isNull() ) return 0;
            return static_cast<typename detail::Promote<T>::type>(_xmax - _xmin)
                   * (_ymax - _ymin);
            // this implementation is for float types, see specialization below
            // for ints...
        }

        //
        void expandTo(const Range2d<T>& r)
        {
                if ( r.isNull() )
                {
                        // the given range will add nothing
                        return; 
                }

                if ( isNull() ) 
                {
                        // being null ourself, we'll equal the given range
                        *this = r;
                        return;
                }

                if ( isWorld() || r.isWorld() )
                {
                        // union with world is always world...
                        setWorld();
                        return;
                }

                _xmin = std::min(_xmin, r._xmin);
                _xmax = std::max(_xmax, r._xmax);
                _ymin = std::min(_ymin, r._ymin);
                _ymax = std::max(_ymax, r._ymax);

        }

private:

        T _xmin, _xmax, _ymin, _ymax;

        T scaleMin(T min, float scale) const {
                return roundMin(static_cast<float>(min) * scale);
        }

        T scaleMax(T max, float scale) const {
                return roundMax(static_cast<float>(max) * scale);
        }

        T roundMin(float v) const {
                return static_cast<T>(v);
        }

        T roundMax(float v) const {
                return static_cast<T>(v);
        }


};

template <typename T> inline std::ostream&
operator<< (std::ostream& os, const Range2d<T>& rect)
{
        if ( rect.isNull() ) return os << "Null range";
        if ( rect.isWorld() ) return os << "World range";

        return os << "Finite range (" << rect._xmin << "," << rect._ymin
                << " " << rect._xmax << "," << rect._ymax << ")";
}

template <typename T> inline bool
operator== (const Range2d<T>& r1, const Range2d<T>& r2)
{
        // These checks are needed becase
        // we don't initialize *all* memebers
        // when setting to Null or World

        if ( r1.isNull() ) return r2.isNull();
        if ( r2.isNull() ) return r1.isNull();
        if ( r1.isWorld() ) return r2.isWorld();
        if ( r2.isWorld() ) return r1.isWorld();

        return r1._xmin == r2._xmin && r1._ymin == r2._ymin &&
                r1._xmax == r2._xmax && r1._ymax == r2._ymax;
}

template <typename T> inline bool
operator!= (const Range2d<T>& r1, const Range2d<T>& r2)
{
        return ! ( r1 == r2 );
}

template <typename T> inline bool
Intersect(const Range2d<T>& r1, const Range2d<T>& r2)
{
        return r1.intersects(r2);
}

template <typename T> inline Range2d<T>
Union(const Range2d<T>& r1, const Range2d<T>& r2)
{
        Range2d<T> ret = r1;
        ret.expandTo(r2);
        return ret;
}

//
template <typename T> inline Range2d<T>
Intersection(const Range2d<T>& r1, const Range2d<T>& r2)
{
        if ( r1.isNull() || r2.isNull() ) {
                // NULL ranges intersect nothing
                return Range2d<T>(nullRange); 
        }

        if ( r1.isWorld() ) {
                // WORLD range intersect everything
                return r2;
        }

        if ( r2.isWorld() ) {
                // WORLD range intersect everything
                return r1;
        }

        if ( ! r1.intersects(r2) ) {
                // No intersection results in a NULL range
                return Range2d<T>(nullRange); 
        }

        return Range2d<T> (
                std::max(r1._xmin, r2._xmin), // xmin
                std::max(r1._ymin, r2._ymin), // ymin
                std::min(r1._xmax, r2._xmax), // xmax
                std::min(r1._ymax, r2._ymax)  // ymax
        );

}

//
template<> inline int
Range2d<int>::roundMin(float min) const
{
        return static_cast<int>(std::floor(min));
}

//
template<> inline unsigned int
Range2d<unsigned int>::roundMin(float min) const
{
        return static_cast<unsigned int>(std::floor(min));
}

//
template<> inline int
Range2d<int>::roundMax(float max) const
{
        return static_cast<int>(std::ceil(max));
}

//
template<> inline unsigned int
Range2d<unsigned int>::roundMax(float max) const
{
        return static_cast<unsigned int>(std::ceil(max));
}

//
template<> inline
detail::Promote<int>::type
Range2d<int>::getArea() const
{
    assert ( !isWorld() );
    if ( isNull() ) return 0;
    return static_cast<detail::Promote<int>::type>(_xmax - _xmin + 1) *
               (_ymax - _ymin + 1);
}

//
template<> inline
detail::Promote<unsigned int>::type
Range2d<unsigned int>::getArea() const
{
    assert ( isFinite() );
    return static_cast<detail::Promote<unsigned int>::type>(_xmax - _xmin + 1) *
              (_ymax - _ymin + 1);
}


} // namespace gnash::geometry
} // namespace gnash

#endif // GNASH_RANGE2D_H


// Local Variables:
// mode: C++
// indent-tabs-mode: t
// End: