polygon/detail/boolean_op.hpp

/*
  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