Chris@16: /*
Chris@16:   Copyright 2008 Intel Corporation
Chris@16: 
Chris@16:   Use, modification and distribution are subject to the Boost Software License,
Chris@16:   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
Chris@16:   http://www.boost.org/LICENSE_1_0.txt).
Chris@16: */
Chris@16: #ifndef BOOST_POLYGON_BOOLEAN_OP_HPP
Chris@16: #define BOOST_POLYGON_BOOLEAN_OP_HPP
Chris@16: namespace boost { namespace polygon{
Chris@16: namespace boolean_op {
Chris@16: 
Chris@16:   //BooleanOp is the generic boolean operation scanline algorithm that provides
Chris@16:   //all the simple boolean set operations on manhattan data.  By templatizing
Chris@16:   //the intersection count of the input and algorithm internals it is extensible
Chris@16:   //to multi-layer scans, properties and other advanced scanline operations above
Chris@16:   //and beyond simple booleans.
Chris@16:   //T must cast to int
Chris@16:   template <class T, typename Unit>
Chris@16:   class BooleanOp {
Chris@16:   public:
Chris@16:     typedef std::map<Unit, T> ScanData;
Chris@16:     typedef std::pair<Unit, T> ElementType;
Chris@16:   protected:
Chris@16:     ScanData scanData_;
Chris@16:     typename ScanData::iterator nextItr_;
Chris@16:     T nullT_;
Chris@16:   public:
Chris@16:     inline BooleanOp () : scanData_(), nextItr_(), nullT_() { nextItr_ = scanData_.end(); nullT_ = 0; }
Chris@16:     inline BooleanOp (T nullT) : scanData_(), nextItr_(), nullT_(nullT) { nextItr_ = scanData_.end(); }
Chris@16:     inline BooleanOp (const BooleanOp& that) : scanData_(that.scanData_), nextItr_(),
Chris@16:                                                nullT_(that.nullT_) { nextItr_ = scanData_.begin(); }
Chris@16:     inline BooleanOp& operator=(const BooleanOp& that);
Chris@16: 
Chris@16:     //moves scanline forward
Chris@16:     inline void advanceScan() { nextItr_ = scanData_.begin(); }
Chris@16: 
Chris@16:     //proceses the given interval and T data
Chris@16:     //appends output edges to cT
Chris@16:     template <class cT>
Chris@16:     inline void processInterval(cT& outputContainer, interval_data<Unit> ivl, T deltaCount);
Chris@16: 
Chris@16:   private:
Chris@16:     inline typename ScanData::iterator lookup_(Unit pos){
Chris@16:       if(nextItr_ != scanData_.end() && nextItr_->first >= pos) {
Chris@16:         return nextItr_;
Chris@16:       }
Chris@16:       return nextItr_ = scanData_.lower_bound(pos);
Chris@16:     }
Chris@16:     inline typename ScanData::iterator insert_(Unit pos, T count){
Chris@16:       return nextItr_ = scanData_.insert(nextItr_, ElementType(pos, count));
Chris@16:     }
Chris@16:     template <class cT>
Chris@16:     inline void evaluateInterval_(cT& outputContainer, interval_data<Unit> ivl, T beforeCount, T afterCount);
Chris@16:   };
Chris@16: 
Chris@16:   class BinaryAnd {
Chris@16:   public:
Chris@16:     inline BinaryAnd() {}
Chris@16:     inline bool operator()(int a, int b) { return (a > 0) & (b > 0); }
Chris@16:   };
Chris@16:   class BinaryOr {
Chris@16:   public:
Chris@16:     inline BinaryOr() {}
Chris@16:     inline bool operator()(int a, int b) { return (a > 0) | (b > 0); }
Chris@16:   };
Chris@16:   class BinaryNot {
Chris@16:   public:
Chris@16:     inline BinaryNot() {}
Chris@16:     inline bool operator()(int a, int b) { return (a > 0) & !(b > 0); }
Chris@16:   };
Chris@16:   class BinaryXor {
Chris@16:   public:
Chris@16:     inline BinaryXor() {}
Chris@16:     inline bool operator()(int a, int b) { return (a > 0) ^ (b > 0); }
Chris@16:   };
Chris@16: 
Chris@16:   //BinaryCount is an array of two deltaCounts coming from two different layers
Chris@16:   //of scan event data.  It is the merged count of the two suitable for consumption
Chris@16:   //as the template argument of the BooleanOp algorithm because BinaryCount casts to int.
Chris@16:   //T is a binary functor object that evaluates the array of counts and returns a logical
Chris@16:   //result of some operation on those values.
Chris@16:   //BinaryCount supports many of the operators that work with int, particularly the
Chris@16:   //binary operators, but cannot support less than or increment.
Chris@16:   template <class T>
Chris@16:   class BinaryCount {
Chris@16:   public:
Chris@16:     inline BinaryCount()
Chris@16: #ifndef BOOST_POLYGON_MSVC
Chris@16:       : counts_()
Chris@16: #endif
Chris@16:     { counts_[0] = counts_[1] = 0; }
Chris@16:     // constructs from two integers
Chris@16:     inline BinaryCount(int countL, int countR)
Chris@16: #ifndef BOOST_POLYGON_MSVC
Chris@16:       : counts_()
Chris@16: #endif
Chris@16:     { counts_[0] = countL, counts_[1] = countR; }
Chris@16:     inline BinaryCount& operator=(int count) { counts_[0] = count, counts_[1] = count; return *this; }
Chris@16:     inline BinaryCount& operator=(const BinaryCount& that);
Chris@16:     inline BinaryCount(const BinaryCount& that)
Chris@16: #ifndef BOOST_POLYGON_MSVC
Chris@16:       : counts_()
Chris@16: #endif
Chris@16:     { *this = that; }
Chris@16:     inline bool operator==(const BinaryCount& that) const;
Chris@16:     inline bool operator!=(const BinaryCount& that) const { return !((*this) == that);}
Chris@16:     inline BinaryCount& operator+=(const BinaryCount& that);
Chris@16:     inline BinaryCount& operator-=(const BinaryCount& that);
Chris@16:     inline BinaryCount operator+(const BinaryCount& that) const;
Chris@16:     inline BinaryCount operator-(const BinaryCount& that) const;
Chris@16:     inline BinaryCount operator-() const;
Chris@16:     inline int& operator[](bool index) { return counts_[index]; }
Chris@16: 
Chris@16:     //cast to int operator evaluates data using T binary functor
Chris@16:     inline operator int() const { return T()(counts_[0], counts_[1]); }
Chris@16:   private:
Chris@16:     int counts_[2];
Chris@16:   };
Chris@16: 
Chris@16:   class UnaryCount {
Chris@16:   public:
Chris@16:     inline UnaryCount() : count_(0) {}
Chris@16:     // constructs from two integers
Chris@16:     inline explicit UnaryCount(int count) : count_(count) {}
Chris@16:     inline UnaryCount& operator=(int count) { count_ = count; return *this; }
Chris@16:     inline UnaryCount& operator=(const UnaryCount& that) { count_ = that.count_; return *this; }
Chris@16:     inline UnaryCount(const UnaryCount& that) : count_(that.count_) {}
Chris@16:     inline bool operator==(const UnaryCount& that) const { return count_ == that.count_; }
Chris@16:     inline bool operator!=(const UnaryCount& that) const { return !((*this) == that);}
Chris@16:     inline UnaryCount& operator+=(const UnaryCount& that) { count_ += that.count_; return *this; }
Chris@16:     inline UnaryCount& operator-=(const UnaryCount& that) { count_ -= that.count_; return *this; }
Chris@16:     inline UnaryCount operator+(const UnaryCount& that) const { UnaryCount tmp(*this); tmp += that; return tmp; }
Chris@16:     inline UnaryCount operator-(const UnaryCount& that) const { UnaryCount tmp(*this); tmp -= that; return tmp; }
Chris@16:     inline UnaryCount operator-() const { UnaryCount tmp; return tmp - *this; }
Chris@16: 
Chris@16:     //cast to int operator evaluates data using T binary functor
Chris@16:     inline operator int() const { return count_ % 2; }
Chris@16:   private:
Chris@16:     int count_;
Chris@16:   };
Chris@16: 
Chris@16:   template <class T, typename Unit>
Chris@16:   inline BooleanOp<T, Unit>& BooleanOp<T, Unit>::operator=(const BooleanOp& that) {
Chris@16:     scanData_ = that.scanData_;
Chris@16:     nextItr_ = scanData_.begin();
Chris@16:     nullT_ = that.nullT_;
Chris@16:     return *this;
Chris@16:   }
Chris@16: 
Chris@16:   //appends output edges to cT
Chris@16:   template <class T, typename Unit>
Chris@16:   template <class cT>
Chris@16:   inline void BooleanOp<T, Unit>::processInterval(cT& outputContainer, interval_data<Unit> ivl, T deltaCount) {
Chris@16:     typename ScanData::iterator lowItr = lookup_(ivl.low());
Chris@16:     typename ScanData::iterator highItr = lookup_(ivl.high());
Chris@16:     //add interval to scan data if it is past the end
Chris@16:     if(lowItr == scanData_.end()) {
Chris@16:       lowItr = insert_(ivl.low(), deltaCount);
Chris@16:       highItr = insert_(ivl.high(), nullT_);
Chris@16:       evaluateInterval_(outputContainer, ivl, nullT_, deltaCount);
Chris@16:       return;
Chris@16:     }
Chris@16:     //ensure that highItr points to the end of the ivl
Chris@16:     if(highItr == scanData_.end() || (*highItr).first > ivl.high()) {
Chris@16:       T value = nullT_;
Chris@16:       if(highItr != scanData_.begin()) {
Chris@16:         --highItr;
Chris@16:         value = highItr->second;
Chris@16:       }
Chris@16:       nextItr_ = highItr;
Chris@16:       highItr = insert_(ivl.high(), value);
Chris@16:     }
Chris@16:     //split the low interval if needed
Chris@16:     if(lowItr->first > ivl.low()) {
Chris@16:       if(lowItr != scanData_.begin()) {
Chris@16:         --lowItr;
Chris@16:         nextItr_ = lowItr;
Chris@16:         lowItr = insert_(ivl.low(), lowItr->second);
Chris@16:       } else {
Chris@16:         nextItr_ = lowItr;
Chris@16:         lowItr = insert_(ivl.low(), nullT_);
Chris@16:       }
Chris@16:     }
Chris@16:     //process scan data intersecting interval
Chris@16:     for(typename ScanData::iterator itr = lowItr; itr != highItr; ){
Chris@16:       T beforeCount = itr->second;
Chris@16:       T afterCount = itr->second += deltaCount;
Chris@16:       Unit low = itr->first;
Chris@16:       ++itr;
Chris@16:       Unit high = itr->first;
Chris@16:       evaluateInterval_(outputContainer, interval_data<Unit>(low, high), beforeCount, afterCount);
Chris@16:     }
Chris@16:     //merge the bottom interval with the one below if they have the same count
Chris@16:     if(lowItr != scanData_.begin()){
Chris@16:       typename ScanData::iterator belowLowItr = lowItr;
Chris@16:       --belowLowItr;
Chris@16:       if(belowLowItr->second == lowItr->second) {
Chris@16:         scanData_.erase(lowItr);
Chris@16:       }
Chris@16:     }
Chris@16:     //merge the top interval with the one above if they have the same count
Chris@16:     if(highItr != scanData_.begin()) {
Chris@16:       typename ScanData::iterator beforeHighItr = highItr;
Chris@16:       --beforeHighItr;
Chris@16:       if(beforeHighItr->second == highItr->second) {
Chris@16:         scanData_.erase(highItr);
Chris@16:         highItr = beforeHighItr;
Chris@16:         ++highItr;
Chris@16:       }
Chris@16:     }
Chris@16:     nextItr_ = highItr;
Chris@16:   }
Chris@16: 
Chris@16:   template <class T, typename Unit>
Chris@16:   template <class cT>
Chris@16:   inline void BooleanOp<T, Unit>::evaluateInterval_(cT& outputContainer, interval_data<Unit> ivl,
Chris@16:                                               T beforeCount, T afterCount) {
Chris@16:     bool before = (int)beforeCount > 0;
Chris@16:     bool after = (int)afterCount > 0;
Chris@16:     int value =  (!before & after) - (before & !after);
Chris@16:     if(value) {
Chris@16:       outputContainer.insert(outputContainer.end(), std::pair<interval_data<Unit>, int>(ivl, value));
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <class T>
Chris@16:   inline BinaryCount<T>& BinaryCount<T>::operator=(const BinaryCount<T>& that) {
Chris@16:     counts_[0] = that.counts_[0];
Chris@16:     counts_[1] = that.counts_[1];
Chris@16:     return *this;
Chris@16:   }
Chris@16:   template <class T>
Chris@16:   inline bool BinaryCount<T>::operator==(const BinaryCount<T>& that) const {
Chris@16:     return counts_[0] == that.counts_[0] &&
Chris@16:       counts_[1] == that.counts_[1];
Chris@16:   }
Chris@16:   template <class T>
Chris@16:   inline BinaryCount<T>& BinaryCount<T>::operator+=(const BinaryCount<T>& that) {
Chris@16:     counts_[0] += that.counts_[0];
Chris@16:     counts_[1] += that.counts_[1];
Chris@16:     return *this;
Chris@16:   }
Chris@16:   template <class T>
Chris@16:   inline BinaryCount<T>& BinaryCount<T>::operator-=(const BinaryCount<T>& that) {
Chris@16:     counts_[0] += that.counts_[0];
Chris@16:     counts_[1] += that.counts_[1];
Chris@16:     return *this;
Chris@16:   }
Chris@16:   template <class T>
Chris@16:   inline BinaryCount<T> BinaryCount<T>::operator+(const BinaryCount<T>& that) const {
Chris@16:     BinaryCount retVal(*this);
Chris@16:     retVal += that;
Chris@16:     return retVal;
Chris@16:   }
Chris@16:   template <class T>
Chris@16:   inline BinaryCount<T> BinaryCount<T>::operator-(const BinaryCount<T>& that) const {
Chris@16:     BinaryCount retVal(*this);
Chris@16:     retVal -= that;
Chris@16:     return retVal;
Chris@16:   }
Chris@16:   template <class T>
Chris@16:   inline BinaryCount<T> BinaryCount<T>::operator-() const {
Chris@16:     return BinaryCount<T>() - *this;
Chris@16:   }
Chris@16: 
Chris@16: 
Chris@16:   template <class T, typename Unit, typename iterator_type_1, typename iterator_type_2>
Chris@16:   inline void applyBooleanBinaryOp(std::vector<std::pair<Unit, std::pair<Unit, int> > >& output,
Chris@16:                                    //const std::vector<std::pair<Unit, std::pair<Unit, int> > >& input1,
Chris@16:                                    //const std::vector<std::pair<Unit, std::pair<Unit, int> > >& input2,
Chris@16:                                    iterator_type_1 itr1, iterator_type_1 itr1_end,
Chris@16:                                    iterator_type_2 itr2, iterator_type_2 itr2_end,
Chris@16:                                    T defaultCount) {
Chris@16:     BooleanOp<T, Unit> boolean(defaultCount);
Chris@16:     //typename std::vector<std::pair<Unit, std::pair<Unit, int> > >::const_iterator itr1 = input1.begin();
Chris@16:     //typename std::vector<std::pair<Unit, std::pair<Unit, int> > >::const_iterator itr2 = input2.begin();
Chris@16:     std::vector<std::pair<interval_data<Unit>, int> > container;
Chris@16:     //output.reserve((std::max)(input1.size(), input2.size()));
Chris@16: 
Chris@16:     //consider eliminating dependecy on limits with bool flag for initial state
Chris@16:     Unit UnitMax = (std::numeric_limits<Unit>::max)();
Chris@16:     Unit prevCoord = UnitMax;
Chris@16:     Unit prevPosition = UnitMax;
Chris@16:     T count(defaultCount);
Chris@16:     //define the starting point
Chris@16:     if(itr1 != itr1_end) {
Chris@16:       prevCoord = (*itr1).first;
Chris@16:       prevPosition = (*itr1).second.first;
Chris@16:       count[0] += (*itr1).second.second;
Chris@16:     }
Chris@16:     if(itr2 != itr2_end) {
Chris@16:       if((*itr2).first < prevCoord ||
Chris@16:          ((*itr2).first == prevCoord && (*itr2).second.first < prevPosition)) {
Chris@16:         prevCoord = (*itr2).first;
Chris@16:         prevPosition = (*itr2).second.first;
Chris@16:         count = defaultCount;
Chris@16:         count[1] += (*itr2).second.second;
Chris@16:         ++itr2;
Chris@16:       } else if((*itr2).first == prevCoord && (*itr2).second.first == prevPosition) {
Chris@16:         count[1] += (*itr2).second.second;
Chris@16:         ++itr2;
Chris@16:         if(itr1 != itr1_end) ++itr1;
Chris@16:       } else {
Chris@16:         if(itr1 != itr1_end) ++itr1;
Chris@16:       }
Chris@16:     } else {
Chris@16:       if(itr1 != itr1_end) ++itr1;
Chris@16:     }
Chris@16: 
Chris@16:     while(itr1 != itr1_end || itr2 != itr2_end) {
Chris@16:       Unit curCoord = UnitMax;
Chris@16:       Unit curPosition = UnitMax;
Chris@16:       T curCount(defaultCount);
Chris@16:       if(itr1 != itr1_end) {
Chris@16:         curCoord = (*itr1).first;
Chris@16:         curPosition = (*itr1).second.first;
Chris@16:         curCount[0] += (*itr1).second.second;
Chris@16:       }
Chris@16:       if(itr2 != itr2_end) {
Chris@16:         if((*itr2).first < curCoord ||
Chris@16:            ((*itr2).first == curCoord && (*itr2).second.first < curPosition)) {
Chris@16:           curCoord = (*itr2).first;
Chris@16:           curPosition = (*itr2).second.first;
Chris@16:           curCount = defaultCount;
Chris@16:           curCount[1] += (*itr2).second.second;
Chris@16:           ++itr2;
Chris@16:         } else if((*itr2).first == curCoord && (*itr2).second.first == curPosition) {
Chris@16:           curCount[1] += (*itr2).second.second;
Chris@16:           ++itr2;
Chris@16:           if(itr1 != itr1_end) ++itr1;
Chris@16:         } else {
Chris@16:           if(itr1 != itr1_end) ++itr1;
Chris@16:         }
Chris@16:       } else {
Chris@16:         ++itr1;
Chris@16:       }
Chris@16: 
Chris@16:       if(prevCoord != curCoord) {
Chris@16:         boolean.advanceScan();
Chris@16:         prevCoord = curCoord;
Chris@16:         prevPosition = curPosition;
Chris@16:         count = curCount;
Chris@16:         continue;
Chris@16:       }
Chris@16:       if(curPosition != prevPosition && count != defaultCount) {
Chris@16:         interval_data<Unit> ivl(prevPosition, curPosition);
Chris@16:         container.clear();
Chris@16:         boolean.processInterval(container, ivl, count);
Chris@16:         for(std::size_t i = 0; i < container.size(); ++i) {
Chris@16:           std::pair<interval_data<Unit>, int>& element = container[i];
Chris@16:           if(!output.empty() && output.back().first == prevCoord &&
Chris@16:              output.back().second.first == element.first.low() &&
Chris@16:              output.back().second.second == element.second * -1) {
Chris@16:             output.pop_back();
Chris@16:           } else {
Chris@16:             output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevCoord, std::pair<Unit, int>(element.first.low(),
Chris@16:                                                                                                     element.second)));
Chris@16:           }
Chris@16:           output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevCoord, std::pair<Unit, int>(element.first.high(),
Chris@16:                                                                                                   element.second * -1)));
Chris@16:         }
Chris@16:       }
Chris@16:       prevPosition = curPosition;
Chris@16:       count += curCount;
Chris@16:     }
Chris@16:   }
Chris@16: 
Chris@16:   template <class T, typename Unit>
Chris@16:   inline void applyBooleanBinaryOp(std::vector<std::pair<Unit, std::pair<Unit, int> > >& inputOutput,
Chris@16:                                    const std::vector<std::pair<Unit, std::pair<Unit, int> > >& input2,
Chris@16:                                    T defaultCount) {
Chris@16:     std::vector<std::pair<Unit, std::pair<Unit, int> > > output;
Chris@16:     applyBooleanBinaryOp(output, inputOutput, input2, defaultCount);
Chris@16:     if(output.size() < inputOutput.size() / 2) {
Chris@16:       inputOutput = std::vector<std::pair<Unit, std::pair<Unit, int> > >();
Chris@16:     } else {
Chris@16:       inputOutput.clear();
Chris@16:     }
Chris@16:     inputOutput.insert(inputOutput.end(), output.begin(), output.end());
Chris@16:   }
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   inline void applyUnaryXOr(std::vector<std::pair<Unit, std::pair<Unit, int> > >& input) {
Chris@16:     BooleanOp<UnaryCount, Unit> booleanXOr;
Chris@16: 
Chris@16:   }
Chris@16: 
Chris@16:   template <typename count_type = int>
Chris@16:   struct default_arg_workaround {
Chris@16:     template <typename Unit>
Chris@16:     static inline void applyBooleanOr(std::vector<std::pair<Unit, std::pair<Unit, int> > >& input) {
Chris@16:       BooleanOp<count_type, Unit> booleanOr;
Chris@16:       std::vector<std::pair<interval_data<Unit>, int> > container;
Chris@16:       std::vector<std::pair<Unit, std::pair<Unit, int> > > output;
Chris@16:       output.reserve(input.size());
Chris@16:       //consider eliminating dependecy on limits with bool flag for initial state
Chris@16:       Unit UnitMax = (std::numeric_limits<Unit>::max)();
Chris@16:       Unit prevPos = UnitMax;
Chris@16:       Unit prevY = UnitMax;
Chris@16:       int count = 0;
Chris@16:       for(typename std::vector<std::pair<Unit, std::pair<Unit, int> > >::iterator itr = input.begin();
Chris@16:           itr != input.end(); ++itr) {
Chris@16:         Unit pos = (*itr).first;
Chris@16:         Unit y = (*itr).second.first;
Chris@16:         if(pos != prevPos) {
Chris@16:           booleanOr.advanceScan();
Chris@16:           prevPos = pos;
Chris@16:           prevY = y;
Chris@16:           count = (*itr).second.second;
Chris@16:           continue;
Chris@16:         }
Chris@16:         if(y != prevY && count != 0) {
Chris@16:           interval_data<Unit> ivl(prevY, y);
Chris@16:           container.clear();
Chris@16:           booleanOr.processInterval(container, ivl, count_type(count));
Chris@16:           for(std::size_t i = 0; i < container.size(); ++i) {
Chris@16:             std::pair<interval_data<Unit>, int>& element = container[i];
Chris@16:             if(!output.empty() && output.back().first == prevPos &&
Chris@16:                output.back().second.first == element.first.low() &&
Chris@16:                output.back().second.second == element.second * -1) {
Chris@16:               output.pop_back();
Chris@16:             } else {
Chris@16:               output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevPos, std::pair<Unit, int>(element.first.low(),
Chris@16:                                                                                                     element.second)));
Chris@16:             }
Chris@16:             output.push_back(std::pair<Unit, std::pair<Unit, int> >(prevPos, std::pair<Unit, int>(element.first.high(),
Chris@16:                                                                                                   element.second * -1)));
Chris@16:           }
Chris@16:         }
Chris@16:         prevY = y;
Chris@16:         count += (*itr).second.second;
Chris@16:       }
Chris@16:       if(output.size() < input.size() / 2) {
Chris@16:         input = std::vector<std::pair<Unit, std::pair<Unit, int> > >();
Chris@16:       } else {
Chris@16:       input.clear();
Chris@16:       }
Chris@16:       input.insert(input.end(), output.begin(), output.end());
Chris@16:     }
Chris@16:   };
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: }
Chris@16: 
Chris@16: }
Chris@16: #endif