polygon/detail/polygon_90_touch.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_POLYGON_90_TOUCH_HPP
#define BOOST_POLYGON_POLYGON_90_TOUCH_HPP
namespace boost { namespace polygon{

  template <typename Unit>
  struct touch_90_operation {
    typedef interval_data<Unit> Interval;

    class TouchScanEvent {
    private:
      typedef std::map<Unit, std::set<int> > EventData;
      EventData eventData_;
    public:

      // The TouchScanEvent::iterator is a lazy algorithm that accumulates
      // polygon ids in a set as it is incremented through the
      // scan event data structure.
      // The iterator provides a forward iterator semantic only.
      class iterator {
      private:
        typename EventData::const_iterator itr_;
        std::pair<Interval, std::set<int> > ivlIds_;
        bool incremented_;
      public:
        inline iterator() : itr_(), ivlIds_(), incremented_(false) {}
        inline iterator(typename EventData::const_iterator itr,
                        Unit prevPos, Unit curPos, const std::set<int>& ivlIds) : itr_(itr), ivlIds_(), incremented_(false) {
          ivlIds_.second = ivlIds;
          ivlIds_.first = Interval(prevPos, curPos);
        }
        inline iterator(const iterator& that) : itr_(), ivlIds_(), incremented_(false) { (*this) = that; }
        inline iterator& operator=(const iterator& that) {
          itr_ = that.itr_;
          ivlIds_.first = that.ivlIds_.first;
          ivlIds_.second = that.ivlIds_.second;
          incremented_ = that.incremented_;
          return *this;
        }
        inline bool operator==(const iterator& that) { return itr_ == that.itr_; }
        inline bool operator!=(const iterator& that) { return itr_ != that.itr_; }
        inline iterator& operator++() {
          //std::cout << "increment\n";
          //std::cout << "state\n";
          //for(std::set<int>::iterator itr = ivlIds_.second.begin(); itr != ivlIds_.second.end(); ++itr) {
          //   std::cout << (*itr) << " ";
          //} std::cout << std::endl;
          //std::cout << "update\n";
          for(std::set<int>::const_iterator itr = (*itr_).second.begin();
              itr != (*itr_).second.end(); ++itr) {
            //std::cout << (*itr) <<  " ";
            std::set<int>::iterator lb = ivlIds_.second.find(*itr);
            if(lb != ivlIds_.second.end()) {
              ivlIds_.second.erase(lb);
            } else {
              ivlIds_.second.insert(*itr);
            }
          }
          //std::cout << std::endl;
          //std::cout << "new state\n";
          //for(std::set<int>::iterator itr = ivlIds_.second.begin(); itr != ivlIds_.second.end(); ++itr) {
          //   std::cout << (*itr) << " ";
          //} std::cout << std::endl;
          ++itr_;
          //ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
          incremented_ = true;
          return *this;
        }
        inline const iterator operator++(int){
          iterator tmpItr(*this);
          ++(*this);
          return tmpItr;
        }
        inline std::pair<Interval, std::set<int> >& operator*() {
          if(incremented_) ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
          incremented_ = false;
          if(ivlIds_.second.empty())(++(*this));
          if(incremented_) ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
          incremented_ = false;
          return ivlIds_; }
      };

      inline TouchScanEvent() : eventData_() {}
      template<class iT>
      inline TouchScanEvent(iT begin, iT end) : eventData_() {
        for( ; begin != end; ++begin){
          insert(*begin);
        }
      }
      inline TouchScanEvent(const TouchScanEvent& that) : eventData_(that.eventData_) {}
      inline TouchScanEvent& operator=(const TouchScanEvent& that){
        eventData_ = that.eventData_;
        return *this;
      }

      //Insert an interval polygon id into the EventData
      inline void insert(const std::pair<Interval, int>& intervalId){
        insert(intervalId.first.low(), intervalId.second);
        insert(intervalId.first.high(), intervalId.second);
      }

      //Insert an position and polygon id into EventData
      inline void insert(Unit pos, int id) {
        typename EventData::iterator lb = eventData_.lower_bound(pos);
        if(lb != eventData_.end() && lb->first == pos) {
          std::set<int>& mr (lb->second);
          std::set<int>::iterator mri = mr.find(id);
          if(mri == mr.end()) {
            mr.insert(id);
          } else {
            mr.erase(id);
          }
        } else {
          lb = eventData_.insert(lb, std::pair<Unit, std::set<int> >(pos, std::set<int>()));
          (*lb).second.insert(id);
        }
      }

      //merge this scan event with that by inserting its data
      inline void insert(const TouchScanEvent& that){
        typename EventData::const_iterator itr;
        for(itr = that.eventData_.begin(); itr != that.eventData_.end(); ++itr) {
          eventData_[(*itr).first].insert(itr->second.begin(), itr->second.end());
        }
      }

      //Get the begin iterator over event data
      inline iterator begin() const {
        //std::cout << "begin\n";
        if(eventData_.empty()) return end();
        typename EventData::const_iterator itr = eventData_.begin();
        Unit pos = itr->first;
        const std::set<int>& idr = itr->second;
        ++itr;
        return iterator(itr, pos, itr->first, idr);
      }

      //Get the end iterator over event data
      inline iterator end() const { return iterator(eventData_.end(), 0, 0, std::set<int>()); }

      inline void clear() { eventData_.clear(); }

      inline Interval extents() const {
        if(eventData_.empty()) return Interval();
        return Interval((*(eventData_.begin())).first, (*(eventData_.rbegin())).first);
      }
    };

    //declaration of a map of scan events by coordinate value used to store all the
    //polygon data for a single layer input into the scanline algorithm
    typedef std::pair<std::map<Unit, TouchScanEvent>, std::map<Unit, TouchScanEvent> > TouchSetData;

    class TouchOp {
    public:
      typedef std::map<Unit, std::set<int> > ScanData;
      typedef std::pair<Unit, std::set<int> > ElementType;
    protected:
      ScanData scanData_;
      typename ScanData::iterator nextItr_;
    public:
      inline TouchOp () : scanData_(), nextItr_() { nextItr_ = scanData_.end(); }
      inline TouchOp (const TouchOp& that) : scanData_(that.scanData_), nextItr_() { nextItr_ = scanData_.begin(); }
      inline TouchOp& operator=(const TouchOp& that);

      //moves scanline forward
      inline void advanceScan() { nextItr_ = scanData_.begin(); }

      //proceses the given interval and std::set<int> data
      //the output data structre is a graph, the indicies in the vector correspond to graph nodes,
      //the integers in the set are vector indicies and are the nodes with which that node shares an edge
      template <typename graphT>
      inline void processInterval(graphT& outputContainer, Interval ivl, const std::set<int>& ids, bool leadingEdge) {
        //print();
        typename ScanData::iterator lowItr = lookup_(ivl.low());
        typename ScanData::iterator highItr = lookup_(ivl.high());
        //std::cout << "Interval: " << ivl << std::endl;
        //for(std::set<int>::const_iterator itr = ids.begin(); itr != ids.end(); ++itr)
        //   std::cout << (*itr) << " ";
        //std::cout << std::endl;
        //add interval to scan data if it is past the end
        if(lowItr == scanData_.end()) {
          //std::cout << "case0" << std::endl;
          lowItr = insert_(ivl.low(), ids);
          evaluateBorder_(outputContainer, ids, ids);
          highItr = insert_(ivl.high(), std::set<int>());
          return;
        }
        //ensure that highItr points to the end of the ivl
        if(highItr == scanData_.end() || (*highItr).first > ivl.high()) {
          //std::cout << "case1" << std::endl;
          //std::cout << highItr->first << std::endl;
          std::set<int> value = std::set<int>();
          if(highItr != scanData_.begin()) {
            --highItr;
            //std::cout << highItr->first << std::endl;
            //std::cout << "high set size " << highItr->second.size() << std::endl;
            value = highItr->second;
          }
          nextItr_ = highItr;
          highItr = insert_(ivl.high(), value);
        } else {
          //evaluate border with next higher interval
          //std::cout << "case1a" << std::endl;
          if(leadingEdge)evaluateBorder_(outputContainer, highItr->second, ids);
        }
        //split the low interval if needed
        if(lowItr->first > ivl.low()) {
          //std::cout << "case2" << std::endl;
          if(lowItr != scanData_.begin()) {
            //std::cout << "case3" << std::endl;
            --lowItr;
            nextItr_ = lowItr;
            //std::cout << lowItr->first << " " << lowItr->second.size() << std::endl;
            lowItr = insert_(ivl.low(), lowItr->second);
          } else {
            //std::cout << "case4" << std::endl;
            nextItr_ = lowItr;
            lowItr = insert_(ivl.low(), std::set<int>());
          }
        } else {
          //evaluate border with next higher interval
          //std::cout << "case2a" << std::endl;
          typename ScanData::iterator nextLowerItr = lowItr;
          if(leadingEdge && nextLowerItr != scanData_.begin()){
            --nextLowerItr;
            evaluateBorder_(outputContainer, nextLowerItr->second, ids);
          }
        }
        //std::cout << "low: " << lowItr->first << " high: " << highItr->first << std::endl;
        //print();
        //process scan data intersecting interval
        for(typename ScanData::iterator itr = lowItr; itr != highItr; ){
          //std::cout << "case5" << std::endl;
          //std::cout << itr->first << std::endl;
          std::set<int>& beforeIds = itr->second;
          ++itr;
          evaluateInterval_(outputContainer, beforeIds, ids, leadingEdge);
        }
        //print();
        //merge the bottom interval with the one below if they have the same count
        if(lowItr != scanData_.begin()){
          //std::cout << "case6" << std::endl;
          typename ScanData::iterator belowLowItr = lowItr;
          --belowLowItr;
          if(belowLowItr->second == lowItr->second) {
            //std::cout << "case7" << std::endl;
            scanData_.erase(lowItr);
          }
        }
        //merge the top interval with the one above if they have the same count
        if(highItr != scanData_.begin()) {
          //std::cout << "case8" << std::endl;
          typename ScanData::iterator beforeHighItr = highItr;
          --beforeHighItr;
          if(beforeHighItr->second == highItr->second) {
            //std::cout << "case9" << std::endl;
            scanData_.erase(highItr);
            highItr = beforeHighItr;
            ++highItr;
          }
        }
        //print();
        nextItr_ = highItr;
      }

//       inline void print() const {
//         for(typename ScanData::const_iterator itr = scanData_.begin(); itr != scanData_.end(); ++itr) {
//           std::cout << itr->first << ": ";
//           for(std::set<int>::const_iterator sitr = itr->second.begin();
//               sitr != itr->second.end(); ++sitr){
//             std::cout << *sitr << " ";
//           }
//           std::cout << std::endl;
//         }
//       }

    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, const std::set<int>& ids){
        //std::cout << "inserting " << ids.size() << " ids at: " << pos << std::endl;
        return nextItr_ = scanData_.insert(nextItr_, std::pair<Unit, std::set<int> >(pos, ids));
      }

      template <typename graphT>
      inline void evaluateInterval_(graphT& outputContainer, std::set<int>& ids,
                                    const std::set<int>& changingIds, bool leadingEdge) {
        for(std::set<int>::const_iterator ciditr = changingIds.begin(); ciditr != changingIds.end(); ++ciditr){
          //std::cout << "evaluateInterval " << (*ciditr) << std::endl;
          evaluateId_(outputContainer, ids, *ciditr, leadingEdge);
        }
      }
      template <typename graphT>
      inline void evaluateBorder_(graphT& outputContainer, const std::set<int>& ids, const std::set<int>& changingIds) {
        for(std::set<int>::const_iterator ciditr = changingIds.begin(); ciditr != changingIds.end(); ++ciditr){
          //std::cout << "evaluateBorder " << (*ciditr) << std::endl;
          evaluateBorderId_(outputContainer, ids, *ciditr);
        }
      }
      template <typename graphT>
      inline void evaluateBorderId_(graphT& outputContainer, const std::set<int>& ids, int changingId) {
        for(std::set<int>::const_iterator scanItr = ids.begin(); scanItr != ids.end(); ++scanItr) {
          //std::cout << "create edge: " << changingId << " " << *scanItr << std::endl;
          if(changingId != *scanItr){
            outputContainer[changingId].insert(*scanItr);
            outputContainer[*scanItr].insert(changingId);
          }
        }
      }
      template <typename graphT>
      inline void evaluateId_(graphT& outputContainer, std::set<int>& ids, int changingId, bool leadingEdge) {
        //std::cout << "changingId: " << changingId << std::endl;
        //for( std::set<int>::iterator itr = ids.begin(); itr != ids.end(); ++itr){
        //   std::cout << *itr << " ";
        //}std::cout << std::endl;
        std::set<int>::iterator lb = ids.lower_bound(changingId);
        if(lb == ids.end() || (*lb) != changingId) {
          if(leadingEdge) {
            //std::cout << "insert\n";
            //insert and add to output
            for(std::set<int>::iterator scanItr = ids.begin(); scanItr != ids.end(); ++scanItr) {
              //std::cout << "create edge: " << changingId << " " << *scanItr << std::endl;
              if(changingId != *scanItr){
                outputContainer[changingId].insert(*scanItr);
                outputContainer[*scanItr].insert(changingId);
              }
            }
            ids.insert(changingId);
          }
        } else {
          if(!leadingEdge){
            //std::cout << "erase\n";
            ids.erase(lb);
          }
        }
      }
    };

    template <typename graphT>
    static inline void processEvent(graphT& outputContainer, TouchOp& op, const TouchScanEvent& data, bool leadingEdge) {
      for(typename TouchScanEvent::iterator itr = data.begin(); itr != data.end(); ++itr) {
        //std::cout << "processInterval" << std::endl;
        op.processInterval(outputContainer, (*itr).first, (*itr).second, leadingEdge);
      }
    }

    template <typename graphT>
    static inline void performTouch(graphT& outputContainer, const TouchSetData& data) {
      typename std::map<Unit, TouchScanEvent>::const_iterator leftItr = data.first.begin();
      typename std::map<Unit, TouchScanEvent>::const_iterator rightItr = data.second.begin();
      typename std::map<Unit, TouchScanEvent>::const_iterator leftEnd = data.first.end();
      typename std::map<Unit, TouchScanEvent>::const_iterator rightEnd = data.second.end();
      TouchOp op;
      while(leftItr != leftEnd || rightItr != rightEnd) {
        //std::cout << "loop" << std::endl;
        op.advanceScan();
        //rightItr cannont be at end if leftItr is not at end
        if(leftItr != leftEnd && rightItr != rightEnd &&
           leftItr->first <= rightItr->first) {
          //std::cout << "case1" << std::endl;
          //std::cout << leftItr ->first << std::endl;
          processEvent(outputContainer, op, leftItr->second, true);
          ++leftItr;
        } else {
          //std::cout << "case2" << std::endl;
          //std::cout << rightItr ->first << std::endl;
          processEvent(outputContainer, op, rightItr->second, false);
          ++rightItr;
        }
      }
    }

    template <class iT>
    static inline void populateTouchSetData(TouchSetData& data, iT beginData, iT endData, int id) {
      Unit prevPos = ((std::numeric_limits<Unit>::max)());
      Unit prevY = prevPos;
      int count = 0;
      for(iT itr = beginData; itr != endData; ++itr) {
        Unit pos = (*itr).first;
        if(pos != prevPos) {
          prevPos = pos;
          prevY = (*itr).second.first;
          count = (*itr).second.second;
          continue;
        }
        Unit y = (*itr).second.first;
        if(count != 0 && y != prevY) {
          std::pair<Interval, int> element(Interval(prevY, y), id);
          if(count > 0) {
            data.first[pos].insert(element);
          } else {
            data.second[pos].insert(element);
          }
        }
        prevY = y;
        count += (*itr).second.second;
      }
    }

    static inline void populateTouchSetData(TouchSetData& data, const std::vector<std::pair<Unit, std::pair<Unit, int> > >& inputData, int id) {
      populateTouchSetData(data, inputData.begin(), inputData.end(), id);
    }

  };
}
}
#endif