snappingrange.h

Go to the documentation of this file.

// 
//   Copyright (C) 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
// 

#ifndef GNASH_SNAPPINGRANGE_H
#define GNASH_SNAPPINGRANGE_H

#include "Range2d.h"

#include <vector>
#include <iterator>
#include <algorithm>
#include <ostream>
#include <boost/cstdint.hpp>

namespace gnash {

namespace geometry {

//

// Forward declarations.
namespace {

    template<typename T> inline bool snaptest(
            const geometry::Range2d<T>& range1,
            const geometry::Range2d<T>& range2, const float snapFactor);
}

template <typename T>
class SnappingRanges2d
{
public:
    typedef geometry::Range2d<T> RangeType;
    typedef std::vector<RangeType> RangeList; 
    typedef typename RangeList::size_type size_type;    

    template<typename U> friend std::ostream& operator<<(std::ostream& os,
                    const SnappingRanges2d<U>& r);
    
    SnappingRanges2d() 
        :
        _snapFactor(1.3f),
        _singleMode(false),
        _rangesLimit(50),
        _combineCounter(0)
    {
    }

    template <typename U>
    SnappingRanges2d(const SnappingRanges2d<U>& from)
        :
        _snapFactor(from.getSnapFactor()), 
        _singleMode(from.getSingleMode()),
        _rangesLimit(from.getRangeCountLimit()),
        _combineCounter(0)
    {
        if (from.isWorld()) setWorld();
        else if (from.isNull()) setNull();
        else {
            // TODO: can we safely assume that the 'from' parameter was
            //             finalized ?

            // TODO: use visitor pattern !
            for (size_type i = 0, e = from.size(); i != e; ++i) {
                const Range2d<U>& r = from.getRange(i);
                RangeType rc(r);
                add(rc);
            }
        }
    }
    
    void setSnapFactor(const float factor) {
        assert(factor > 1.0f);
        _snapFactor = factor;
    }
    
    float getSnapFactor() const {
        return _snapFactor;
    }
    
    void setSingleMode(const bool mode) {
        _singleMode = mode;
    }
    
    bool getSingleMode() const {
        return _singleMode;
    }    
    
    void setRangeCountLimit(const size_type limit) {
        _rangesLimit = limit;
    }
    
    size_type getRangeCountLimit() const {
        return _rangesLimit;
    }
    
    void inheritConfig(const SnappingRanges2d<T>& from) {
        _snapFactor = from._snapFactor;
        _singleMode = from._singleMode;
    }
    
    struct ExpandToIfSnap
    {
    public:
        ExpandToIfSnap(const RangeType& rt, const float snapFactor)
            :
            _rt(rt),
            _snapFactor(snapFactor)
        {}
        
        bool operator()(RangeType& r) {
            if (snaptest(r, _rt, _snapFactor)) {
                r.expandTo(_rt);
                return false;
            }
            return true;
        }
    private:
        const RangeType& _rt;
        const float _snapFactor;
    };

    class Scale
    {
    public:
        Scale(const float scale) : _scale(scale) {}
        void operator()(RangeType& r) {
            r.scale(_scale);
        }
    private:
        const float _scale;
    };

    class GrowBy
    {
    public:
        GrowBy(const float factor) : _factor(factor) {}
        void operator()(RangeType& r) {
            r.growBy(_factor);
        }
    private:
        const float _factor;
    };

    class AddTo
    {
    public:
        AddTo(SnappingRanges2d<T>& us) : _this(us) {}
        void operator()(const RangeType& r) {
            _this.add(r);
        }
    private:
        SnappingRanges2d<T>& _this;
    };
    
    class IntersectsRange
    {
    public:
        IntersectsRange(const RangeType& range) : _range(range) {}
        bool operator()(const RangeType& us) {
            return us.intersects(_range);
        }
    private:
        const RangeType& _range;
    };
    
    class ContainsPoint
    {
    public:
        ContainsPoint(const T x, const T y) : _x(x), _y(y) {}
        bool operator()(const RangeType& us) {
            return us.contains(_x, _y);
        }
    private:
        const T _x, _y;
    };
    
    class ContainsRange
    {
    public:
        ContainsRange(const RangeType& range) : _range(range) {}
        bool operator()(const RangeType& us) {
            return us.contains(_range);
        }
    private:
        const RangeType& _range;
    };


    void add(const RangeType& range) {
        if (range.isWorld()) {
            setWorld();
            return;
        }
        
        if (range.isNull()) return;
        
        if (_singleMode) {
            if (_ranges.empty()) _ranges.resize(1);
            _ranges[0].expandTo(range);
            return;
        }
        
        ExpandToIfSnap exp(range, _snapFactor);
        if (visit(exp)) return;

        // reached this point we need a new range 
        _ranges.push_back(range);
        
        combineRangesLazy();
    }
    
    void add(const SnappingRanges2d<T>& other) {
        const RangeList& rl = other._ranges;
        std::for_each(rl.begin(), rl.end(), AddTo(*this));
    }

    void growBy(const T amount) {
    
        if (isWorld() || isNull()) return;
        
        std::for_each(_ranges.begin(), _ranges.end(), GrowBy(amount));
        combineRangesLazy();
    }

    void scale(const float factor) {
    
        if (isWorld() || isNull()) return;
        
        std::for_each(_ranges.begin(), _ranges.end(), Scale(factor));
        combineRangesLazy();
    }
    
    void setNull() {
        _ranges.clear();
    }
    
    void setWorld() {
        if (isWorld()) return;
        _ranges.resize(1);
        _ranges[0].setWorld();
    }
    
    bool isWorld() const {
        return ((size()==1) && (_ranges.front().isWorld()));
    }
    
    bool isNull() const {
        return _ranges.empty();
    }
    
    size_type size() const {
        finalize();
        return _ranges.size();
    }
    
    const RangeType& getRange(size_type index) const {
        finalize();
        assert(index<size());
        return _ranges[index];
    }
    
    RangeType getFullArea() const {
        RangeType range;
        
        range.setNull();
        
        int rcount = _ranges.size();
        
        for (int rno=0; rno<rcount; rno++) 
            range.expandTo(_ranges[rno]);
        
        return range;     
    }
    

    //
    bool intersects(const RangeType& r) const {
    
        finalize();
        return std::find_if(_ranges.begin(), _ranges.end(), IntersectsRange(r))
            != _ranges.end();
    }
    
    bool contains(T x, T y) const {
    
        finalize();
        return std::find_if(_ranges.begin(), _ranges.end(), ContainsPoint(x, y))
            != _ranges.end();
    }

    //
    bool contains(const RangeType& r) const {
    
        finalize();
        return std::find_if(_ranges.begin(), _ranges.end(), ContainsRange(r))
            != _ranges.end();
    }

    bool contains(const SnappingRanges2d<T>& o) const
    {
    
        finalize();
        // o.finalize(); // should I finalize the other range too ?

        // Null range set doesn't contain and isn't contained by anything
        if ( isNull() ) return false;
        if ( o.isNull() ) return false;

        // World range contains everything (except null ranges)
        if ( isWorld() ) return true;

        // This snappingrange is neither NULL nor WORLD
        // The other can still be WORLD, but in that case the
        // first iteration would return false
        //
        for (unsigned rno=0, rcount=o.size(); rno<rcount; rno++) 
        {
            RangeType r = o.getRange(rno);
            if ( ! contains(r) )
            {
                return false;
            }
        }
            
        return true;
    
    }
    
    
    void intersect(const SnappingRanges2d<T>& o) 
    {
        if (o.isNull()) {
            setNull();
            return;
        }
        
        if (o.isWorld()) return;
        
        // We create a new ranges set for each range in "o" and
        // then update ourselves with the *union* of these ranges.
        // Anybody knows a better method (in terms of efficieny) ?    
     
        std::vector<SnappingRanges2d<T> > list;
        list.reserve(o.size());
    
        //TODO: use a visitor !
        for (unsigned rno=0, rcount=o.size(); rno<rcount; rno++) {
            
            // add a copy of ourselves to the list
            list.push_back(*this);
            
            // intersect that copy with the single range
            list.back().intersect(o.getRange(rno));
            
        } 
        
        // update ourselves with the union of the "list"
        setNull();
        for (size_type lno=0, lcount=list.size(); lno<lcount; lno++) {
            add(list[lno]);
        }
                            
    }
    
    
    void intersect(const RangeType& r) 
    {
    
        finalize();

        if (isWorld()) {            // world intersection with X = X
            setNull();    
            add(r);
            return;
        }
        
        if (isNull()) return; // NULL will always remain NULL
        
        if (r.isNull()) {         // X intersection with NULL = NULL
            setNull();
            return;
        }
        
        if (r.isWorld()) return;    // X intersection with WORLD = X
        
        // TODO: use a vector (remember to walk in reverse dir.)
        for (int rno=_ranges.size()-1; rno>=0; rno--) {     
        
            RangeType newrange = Intersection(_ranges[rno], r);
            
            if (newrange.isNull())
                _ranges.erase(_ranges.begin() + rno);
            else             
                _ranges[rno] = newrange;
        }
    }
    
    void combineRanges() const {
    
        // makes no sense in single mode
        if (_singleMode) return;
    
        bool restart = true;
        
        _combineCounter = 0;
        
        while (restart) {
        
            int rcount = _ranges.size();

            restart=false;
        
            for (int i=0; i<rcount; i++) {
            
                for (int j=i+1; j<rcount; j++) {
                
                    if (snaptest(_ranges[i], _ranges[j], _snapFactor)) {
                        // merge i + j
                        _ranges[i].expandTo(_ranges[j]);
                        
                        _ranges.erase(_ranges.begin() + j);
                        
                        restart=true; // restart from beginning
                        break;
                        
                    } 
                } 
                
                if (restart) break;
            } 
        } 
        
        // limit number of ranges
        if (_ranges.size() > _rangesLimit) {
        
            // We found way too much ranges, so reduce to just one single range.
            // We could also double the factor and try again, but that probably
            // won't make much difference, so we avoid the trouble...
            
            RangeType single = getFullArea();            
            _ranges.resize(1);
            _ranges[0] = single;
        
        }
    
    }
    
    //
    template<class V> inline bool visit(V& visitor) const
    {
        typename RangeList::iterator it, e;
        for (it = _ranges.begin(), e = _ranges.end(); it != e; ++it) {
            if (!visitor(*it)) break;
        }
        return it != _ranges.end();
    }

    //
    template<class V> inline void visitAll(V& visitor) const
    {
        for_each(_ranges.begin(), _ranges.end(), visitor);
    }
    
private:

    
    void combineRangesLazy() const {
        const size_type max = 5;
        ++_combineCounter;
        if (_combineCounter > max) combineRanges();
    }
            
    void finalize() const {
        if (_combineCounter > 0) combineRanges();
    } 
        
    //
    mutable RangeList _ranges;

    float _snapFactor;
    
    bool _singleMode;
    
    size_type _rangesLimit;     
    
    mutable size_type _combineCounter;
        
};

template <class T>
std::ostream&
operator<< (std::ostream& os, const SnappingRanges2d<T>& r)
{
    if ( r.isNull() ) return os << "NULL";
    if ( r.isWorld() ) return os << "WORLD";

    typedef typename SnappingRanges2d<T>::RangeList R;

    const R& ranges = r._ranges;

    std::copy(ranges.begin(), ranges.end(),
            std::ostream_iterator<typename R::value_type>(os, ","));

    return os;
}
    
namespace {

template<typename T>
inline bool snaptest(const geometry::Range2d<T>& range1,
        const geometry::Range2d<T>& range2, const float snapFactor)
{

    // when they intersect anyway, they should of course be merged! 
    // TODO: not really, a "+" style ranges list might be worth to 
    // remain unmerged (but needs special handling, i.e. create three
    // ranges out of two)...
    if (range1.intersects(range2)) return true;
        
    geometry::Range2d<T> temp = range1;
    temp.expandTo(range2);
    
    return (range1.getArea() + range2.getArea()) * snapFactor >
        temp.getArea();

} 
    
} // anonymous namespace
} // namespace geometry

typedef geometry::SnappingRanges2d<boost::int32_t> InvalidatedRanges;

} //namespace gnash

#endif