comparison DEPENDENCIES/generic/include/boost/polygon/detail/boolean_op.hpp @ 16:2665513ce2d3

Add boost headers

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