Gnash  0.8.10
snappingrange.h
Go to the documentation of this file.
00001 // 
00002 //   Copyright (C) 2007, 2008, 2009, 2010, 2011, 2012
00003 //   Free Software Foundation, Inc.
00004 // 
00005 // This program is free software; you can redistribute it and/or modify
00006 // it under the terms of the GNU General Public License as published by
00007 // the Free Software Foundation; either version 3 of the License, or
00008 // (at your option) any later version.
00009 // 
00010 // This program is distributed in the hope that it will be useful,
00011 // but WITHOUT ANY WARRANTY; without even the implied warranty of
00012 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.    See the
00013 // GNU General Public License for more details.
00014 // 
00015 // You should have received a copy of the GNU General Public License
00016 // along with this program; if not, write to the Free Software
00017 // Foundation, Inc., 51 Franklin St, Fifth Floor, Boston, MA  02110-1301  USA
00018 // 
00019 
00020 #ifndef GNASH_SNAPPINGRANGE_H
00021 #define GNASH_SNAPPINGRANGE_H
00022 
00023 #include "Range2d.h"
00024 
00025 #include <vector>
00026 #include <iterator>
00027 #include <algorithm>
00028 #include <ostream>
00029 #include <boost/cstdint.hpp>
00030 
00031 namespace gnash {
00032 
00033 namespace geometry {
00034 
00039 //
00069 
00070 // Forward declarations.
00071 namespace {
00072 
00074     template<typename T> inline bool snaptest(
00075             const geometry::Range2d<T>& range1,
00076             const geometry::Range2d<T>& range2, const float snapFactor);
00077 }
00078 
00079 template <typename T>
00080 class SnappingRanges2d
00081 {
00082 public:
00083     typedef geometry::Range2d<T> RangeType;
00084     typedef std::vector<RangeType> RangeList; 
00085     typedef typename RangeList::size_type size_type;    
00086 
00087     template<typename U> friend std::ostream& operator<<(std::ostream& os,
00088                     const SnappingRanges2d<U>& r);
00089     
00090     SnappingRanges2d() 
00091         :
00092         _snapFactor(1.3f),
00093         _singleMode(false),
00094         _rangesLimit(50),
00095         _combineCounter(0)
00096     {
00097     }
00098 
00100     template <typename U>
00101     SnappingRanges2d(const SnappingRanges2d<U>& from)
00102         :
00103         _snapFactor(from.getSnapFactor()), 
00104         _singleMode(from.getSingleMode()),
00105         _rangesLimit(from.getRangeCountLimit()),
00106         _combineCounter(0)
00107     {
00108         if (from.isWorld()) setWorld();
00109         else if (from.isNull()) setNull();
00110         else {
00111             // TODO: can we safely assume that the 'from' parameter was
00112             //             finalized ?
00113 
00114             // TODO: use visitor pattern !
00115             for (size_type i = 0, e = from.size(); i != e; ++i) {
00116                 const Range2d<U>& r = from.getRange(i);
00117                 RangeType rc(r);
00118                 add(rc);
00119             }
00120         }
00121     }
00122     
00125     void setSnapFactor(const float factor) {
00126         assert(factor > 1.0f);
00127         _snapFactor = factor;
00128     }
00129     
00130     float getSnapFactor() const {
00131         return _snapFactor;
00132     }
00133     
00135     void setSingleMode(const bool mode) {
00136         _singleMode = mode;
00137     }
00138     
00139     bool getSingleMode() const {
00140         return _singleMode;
00141     }    
00142     
00145     void setRangeCountLimit(const size_type limit) {
00146         _rangesLimit = limit;
00147     }
00148     
00149     size_type getRangeCountLimit() const {
00150         return _rangesLimit;
00151     }
00152     
00155     void inheritConfig(const SnappingRanges2d<T>& from) {
00156         _snapFactor = from._snapFactor;
00157         _singleMode = from._singleMode;
00158     }
00159     
00161     struct ExpandToIfSnap
00162     {
00163     public:
00164         ExpandToIfSnap(const RangeType& rt, const float snapFactor)
00165             :
00166             _rt(rt),
00167             _snapFactor(snapFactor)
00168         {}
00169         
00170         bool operator()(RangeType& r) {
00171             if (snaptest(r, _rt, _snapFactor)) {
00172                 r.expandTo(_rt);
00173                 return false;
00174             }
00175             return true;
00176         }
00177     private:
00178         const RangeType& _rt;
00179         const float _snapFactor;
00180     };
00181 
00182     class Scale
00183     {
00184     public:
00185         Scale(const float scale) : _scale(scale) {}
00186         void operator()(RangeType& r) {
00187             r.scale(_scale);
00188         }
00189     private:
00190         const float _scale;
00191     };
00192 
00193     class GrowBy
00194     {
00195     public:
00196         GrowBy(const float factor) : _factor(factor) {}
00197         void operator()(RangeType& r) {
00198             r.growBy(_factor);
00199         }
00200     private:
00201         const float _factor;
00202     };
00203 
00204     class AddTo
00205     {
00206     public:
00207         AddTo(SnappingRanges2d<T>& us) : _this(us) {}
00208         void operator()(const RangeType& r) {
00209             _this.add(r);
00210         }
00211     private:
00212         SnappingRanges2d<T>& _this;
00213     };
00214     
00215     class IntersectsRange
00216     {
00217     public:
00218         IntersectsRange(const RangeType& range) : _range(range) {}
00219         bool operator()(const RangeType& us) {
00220             return us.intersects(_range);
00221         }
00222     private:
00223         const RangeType& _range;
00224     };
00225     
00226     class ContainsPoint
00227     {
00228     public:
00229         ContainsPoint(const T x, const T y) : _x(x), _y(y) {}
00230         bool operator()(const RangeType& us) {
00231             return us.contains(_x, _y);
00232         }
00233     private:
00234         const T _x, _y;
00235     };
00236     
00237     class ContainsRange
00238     {
00239     public:
00240         ContainsRange(const RangeType& range) : _range(range) {}
00241         bool operator()(const RangeType& us) {
00242             return us.contains(_range);
00243         }
00244     private:
00245         const RangeType& _range;
00246     };
00247 
00248 
00250     void add(const RangeType& range) {
00251         if (range.isWorld()) {
00252             setWorld();
00253             return;
00254         }
00255         
00256         if (range.isNull()) return;
00257         
00258         if (_singleMode) {
00259             if (_ranges.empty()) _ranges.resize(1);
00260             _ranges[0].expandTo(range);
00261             return;
00262         }
00263         
00264         ExpandToIfSnap exp(range, _snapFactor);
00265         if (visit(exp)) return;
00266 
00267         // reached this point we need a new range 
00268         _ranges.push_back(range);
00269         
00270         combineRangesLazy();
00271     }
00272     
00274     void add(const SnappingRanges2d<T>& other) {
00275         const RangeList& rl = other._ranges;
00276         std::for_each(rl.begin(), rl.end(), AddTo(*this));
00277     }
00278 
00280     void growBy(const T amount) {
00281     
00282         if (isWorld() || isNull()) return;
00283         
00284         std::for_each(_ranges.begin(), _ranges.end(), GrowBy(amount));
00285         combineRangesLazy();
00286     }
00287 
00289     void scale(const float factor) {
00290     
00291         if (isWorld() || isNull()) return;
00292         
00293         std::for_each(_ranges.begin(), _ranges.end(), Scale(factor));
00294         combineRangesLazy();
00295     }
00296     
00298     void setNull() {
00299         _ranges.clear();
00300     }
00301     
00303     void setWorld() {
00304         if (isWorld()) return;
00305         _ranges.resize(1);
00306         _ranges[0].setWorld();
00307     }
00308     
00310     bool isWorld() const {
00311         return ((size()==1) && (_ranges.front().isWorld()));
00312     }
00313     
00315     bool isNull() const {
00316         return _ranges.empty();
00317     }
00318     
00320     size_type size() const {
00321         finalize();
00322         return _ranges.size();
00323     }
00324     
00326     const RangeType& getRange(size_type index) const {
00327         finalize();
00328         assert(index<size());
00329         return _ranges[index];
00330     }
00331     
00334     RangeType getFullArea() const {
00335         RangeType range;
00336         
00337         range.setNull();
00338         
00339         int rcount = _ranges.size();
00340         
00341         for (int rno=0; rno<rcount; rno++) 
00342             range.expandTo(_ranges[rno]);
00343         
00344         return range;     
00345     }
00346     
00347 
00349     //
00353     bool intersects(const RangeType& r) const {
00354     
00355         finalize();
00356         return std::find_if(_ranges.begin(), _ranges.end(), IntersectsRange(r))
00357             != _ranges.end();
00358     }
00359     
00361     bool contains(T x, T y) const {
00362     
00363         finalize();
00364         return std::find_if(_ranges.begin(), _ranges.end(), ContainsPoint(x, y))
00365             != _ranges.end();
00366     }
00367 
00369     //
00373     bool contains(const RangeType& r) const {
00374     
00375         finalize();
00376         return std::find_if(_ranges.begin(), _ranges.end(), ContainsRange(r))
00377             != _ranges.end();
00378     }
00379 
00388     bool contains(const SnappingRanges2d<T>& o) const
00389     {
00390     
00391         finalize();
00392         // o.finalize(); // should I finalize the other range too ?
00393 
00394         // Null range set doesn't contain and isn't contained by anything
00395         if ( isNull() ) return false;
00396         if ( o.isNull() ) return false;
00397 
00398         // World range contains everything (except null ranges)
00399         if ( isWorld() ) return true;
00400 
00401         // This snappingrange is neither NULL nor WORLD
00402         // The other can still be WORLD, but in that case the
00403         // first iteration would return false
00404         //
00406         for (unsigned rno=0, rcount=o.size(); rno<rcount; rno++) 
00407         {
00408             RangeType r = o.getRange(rno);
00409             if ( ! contains(r) )
00410             {
00411                 return false;
00412             }
00413         }
00414             
00415         return true;
00416     
00417     }
00418     
00419     
00425     void intersect(const SnappingRanges2d<T>& o) 
00426     {
00427         if (o.isNull()) {
00428             setNull();
00429             return;
00430         }
00431         
00432         if (o.isWorld()) return;
00433         
00434         // We create a new ranges set for each range in "o" and
00435         // then update ourselves with the *union* of these ranges.
00436         // Anybody knows a better method (in terms of efficieny) ?    
00437      
00438         std::vector<SnappingRanges2d<T> > list;
00439         list.reserve(o.size());
00440     
00441         //TODO: use a visitor !
00442         for (unsigned rno=0, rcount=o.size(); rno<rcount; rno++) {
00443             
00444             // add a copy of ourselves to the list
00445             list.push_back(*this);
00446             
00447             // intersect that copy with the single range
00448             list.back().intersect(o.getRange(rno));
00449             
00450         } 
00451         
00452         // update ourselves with the union of the "list"
00453         setNull();
00454         for (size_type lno=0, lcount=list.size(); lno<lcount; lno++) {
00455             add(list[lno]);
00456         }
00457                             
00458     }
00459     
00460     
00463     void intersect(const RangeType& r) 
00464     {
00465     
00466         finalize();
00467 
00468         if (isWorld()) {            // world intersection with X = X
00469             setNull();    
00470             add(r);
00471             return;
00472         }
00473         
00474         if (isNull()) return; // NULL will always remain NULL
00475         
00476         if (r.isNull()) {         // X intersection with NULL = NULL
00477             setNull();
00478             return;
00479         }
00480         
00481         if (r.isWorld()) return;    // X intersection with WORLD = X
00482         
00483         // TODO: use a vector (remember to walk in reverse dir.)
00484         for (int rno=_ranges.size()-1; rno>=0; rno--) {     
00485         
00486             RangeType newrange = Intersection(_ranges[rno], r);
00487             
00488             if (newrange.isNull())
00489                 _ranges.erase(_ranges.begin() + rno);
00490             else             
00491                 _ranges[rno] = newrange;
00492         }
00493     }
00494     
00497     void combineRanges() const {
00498     
00499         // makes no sense in single mode
00500         if (_singleMode) return;
00501     
00502         bool restart = true;
00503         
00504         _combineCounter = 0;
00505         
00506         while (restart) {
00507         
00508             int rcount = _ranges.size();
00509 
00510             restart=false;
00511         
00512             for (int i=0; i<rcount; i++) {
00513             
00514                 for (int j=i+1; j<rcount; j++) {
00515                 
00516                     if (snaptest(_ranges[i], _ranges[j], _snapFactor)) {
00517                         // merge i + j
00518                         _ranges[i].expandTo(_ranges[j]);
00519                         
00520                         _ranges.erase(_ranges.begin() + j);
00521                         
00522                         restart=true; // restart from beginning
00523                         break;
00524                         
00525                     } 
00526                 } 
00527                 
00528                 if (restart) break;
00529             } 
00530         } 
00531         
00532         // limit number of ranges
00533         if (_ranges.size() > _rangesLimit) {
00534         
00535             // We found way too much ranges, so reduce to just one single range.
00536             // We could also double the factor and try again, but that probably
00537             // won't make much difference, so we avoid the trouble...
00538             
00539             RangeType single = getFullArea();            
00540             _ranges.resize(1);
00541             _ranges[0] = single;
00542         
00543         }
00544     
00545     }
00546     
00548     //
00557     template<class V> inline bool visit(V& visitor) const
00558     {
00559         typename RangeList::iterator it, e;
00560         for (it = _ranges.begin(), e = _ranges.end(); it != e; ++it) {
00561             if (!visitor(*it)) break;
00562         }
00563         return it != _ranges.end();
00564     }
00565 
00567     //
00573     template<class V> inline void visitAll(V& visitor) const
00574     {
00575         for_each(_ranges.begin(), _ranges.end(), visitor);
00576     }
00577     
00578 private:
00579 
00580     
00583     void combineRangesLazy() const {
00584         const size_type max = 5;
00585         ++_combineCounter;
00586         if (_combineCounter > max) combineRanges();
00587     }
00588             
00589     void finalize() const {
00590         if (_combineCounter > 0) combineRanges();
00591     } 
00592         
00594     //
00597     mutable RangeList _ranges;
00598 
00600     float _snapFactor;
00601     
00603     bool _singleMode;
00604     
00606     size_type _rangesLimit;     
00607     
00609     mutable size_type _combineCounter;
00610         
00611 };
00612 
00613 template <class T>
00614 std::ostream&
00615 operator<< (std::ostream& os, const SnappingRanges2d<T>& r)
00616 {
00617     if ( r.isNull() ) return os << "NULL";
00618     if ( r.isWorld() ) return os << "WORLD";
00619 
00620     typedef typename SnappingRanges2d<T>::RangeList R;
00621 
00622     const R& ranges = r._ranges;
00623 
00624     std::copy(ranges.begin(), ranges.end(),
00625             std::ostream_iterator<typename R::value_type>(os, ","));
00626 
00627     return os;
00628 }
00629     
00630 namespace {
00631 
00632 template<typename T>
00633 inline bool snaptest(const geometry::Range2d<T>& range1,
00634         const geometry::Range2d<T>& range2, const float snapFactor)
00635 {
00636 
00637     // when they intersect anyway, they should of course be merged! 
00638     // TODO: not really, a "+" style ranges list might be worth to 
00639     // remain unmerged (but needs special handling, i.e. create three
00640     // ranges out of two)...
00641     if (range1.intersects(range2)) return true;
00642         
00643     geometry::Range2d<T> temp = range1;
00644     temp.expandTo(range2);
00645     
00646     return (range1.getArea() + range2.getArea()) * snapFactor >
00647         temp.getArea();
00648 
00649 } 
00650     
00651 } // anonymous namespace
00652 } // namespace geometry
00653 
00655 typedef geometry::SnappingRanges2d<boost::int32_t> InvalidatedRanges;
00656 
00657 } //namespace gnash
00658 
00659 #endif