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_POLYGON_90_TOUCH_HPP
Chris@16: #define BOOST_POLYGON_POLYGON_90_TOUCH_HPP
Chris@16: namespace boost { namespace polygon{
Chris@16: 
Chris@16:   template <typename Unit>
Chris@16:   struct touch_90_operation {
Chris@16:     typedef interval_data<Unit> Interval;
Chris@16: 
Chris@16:     class TouchScanEvent {
Chris@16:     private:
Chris@16:       typedef std::map<Unit, std::set<int> > EventData;
Chris@16:       EventData eventData_;
Chris@16:     public:
Chris@16: 
Chris@16:       // The TouchScanEvent::iterator is a lazy algorithm that accumulates
Chris@16:       // polygon ids in a set as it is incremented through the
Chris@16:       // scan event data structure.
Chris@16:       // The iterator provides a forward iterator semantic only.
Chris@16:       class iterator {
Chris@16:       private:
Chris@16:         typename EventData::const_iterator itr_;
Chris@16:         std::pair<Interval, std::set<int> > ivlIds_;
Chris@16:         bool incremented_;
Chris@16:       public:
Chris@16:         inline iterator() : itr_(), ivlIds_(), incremented_(false) {}
Chris@16:         inline iterator(typename EventData::const_iterator itr,
Chris@16:                         Unit prevPos, Unit curPos, const std::set<int>& ivlIds) : itr_(itr), ivlIds_(), incremented_(false) {
Chris@16:           ivlIds_.second = ivlIds;
Chris@16:           ivlIds_.first = Interval(prevPos, curPos);
Chris@16:         }
Chris@16:         inline iterator(const iterator& that) : itr_(), ivlIds_(), incremented_(false) { (*this) = that; }
Chris@16:         inline iterator& operator=(const iterator& that) {
Chris@16:           itr_ = that.itr_;
Chris@16:           ivlIds_.first = that.ivlIds_.first;
Chris@16:           ivlIds_.second = that.ivlIds_.second;
Chris@16:           incremented_ = that.incremented_;
Chris@16:           return *this;
Chris@16:         }
Chris@16:         inline bool operator==(const iterator& that) { return itr_ == that.itr_; }
Chris@16:         inline bool operator!=(const iterator& that) { return itr_ != that.itr_; }
Chris@16:         inline iterator& operator++() {
Chris@16:           //std::cout << "increment\n";
Chris@16:           //std::cout << "state\n";
Chris@16:           //for(std::set<int>::iterator itr = ivlIds_.second.begin(); itr != ivlIds_.second.end(); ++itr) {
Chris@16:           //   std::cout << (*itr) << " ";
Chris@16:           //} std::cout << std::endl;
Chris@16:           //std::cout << "update\n";
Chris@16:           for(std::set<int>::const_iterator itr = (*itr_).second.begin();
Chris@16:               itr != (*itr_).second.end(); ++itr) {
Chris@16:             //std::cout << (*itr) <<  " ";
Chris@16:             std::set<int>::iterator lb = ivlIds_.second.find(*itr);
Chris@16:             if(lb != ivlIds_.second.end()) {
Chris@16:               ivlIds_.second.erase(lb);
Chris@16:             } else {
Chris@16:               ivlIds_.second.insert(*itr);
Chris@16:             }
Chris@16:           }
Chris@16:           //std::cout << std::endl;
Chris@16:           //std::cout << "new state\n";
Chris@16:           //for(std::set<int>::iterator itr = ivlIds_.second.begin(); itr != ivlIds_.second.end(); ++itr) {
Chris@16:           //   std::cout << (*itr) << " ";
Chris@16:           //} std::cout << std::endl;
Chris@16:           ++itr_;
Chris@16:           //ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
Chris@16:           incremented_ = true;
Chris@16:           return *this;
Chris@16:         }
Chris@16:         inline const iterator operator++(int){
Chris@16:           iterator tmpItr(*this);
Chris@16:           ++(*this);
Chris@16:           return tmpItr;
Chris@16:         }
Chris@16:         inline std::pair<Interval, std::set<int> >& operator*() {
Chris@16:           if(incremented_) ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
Chris@16:           incremented_ = false;
Chris@16:           if(ivlIds_.second.empty())(++(*this));
Chris@16:           if(incremented_) ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
Chris@16:           incremented_ = false;
Chris@16:           return ivlIds_; }
Chris@16:       };
Chris@16: 
Chris@16:       inline TouchScanEvent() : eventData_() {}
Chris@16:       template<class iT>
Chris@16:       inline TouchScanEvent(iT begin, iT end) : eventData_() {
Chris@16:         for( ; begin != end; ++begin){
Chris@16:           insert(*begin);
Chris@16:         }
Chris@16:       }
Chris@16:       inline TouchScanEvent(const TouchScanEvent& that) : eventData_(that.eventData_) {}
Chris@16:       inline TouchScanEvent& operator=(const TouchScanEvent& that){
Chris@16:         eventData_ = that.eventData_;
Chris@16:         return *this;
Chris@16:       }
Chris@16: 
Chris@16:       //Insert an interval polygon id into the EventData
Chris@16:       inline void insert(const std::pair<Interval, int>& intervalId){
Chris@16:         insert(intervalId.first.low(), intervalId.second);
Chris@16:         insert(intervalId.first.high(), intervalId.second);
Chris@16:       }
Chris@16: 
Chris@16:       //Insert an position and polygon id into EventData
Chris@16:       inline void insert(Unit pos, int id) {
Chris@16:         typename EventData::iterator lb = eventData_.lower_bound(pos);
Chris@16:         if(lb != eventData_.end() && lb->first == pos) {
Chris@16:           std::set<int>& mr (lb->second);
Chris@16:           std::set<int>::iterator mri = mr.find(id);
Chris@16:           if(mri == mr.end()) {
Chris@16:             mr.insert(id);
Chris@16:           } else {
Chris@16:             mr.erase(id);
Chris@16:           }
Chris@16:         } else {
Chris@16:           lb = eventData_.insert(lb, std::pair<Unit, std::set<int> >(pos, std::set<int>()));
Chris@16:           (*lb).second.insert(id);
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       //merge this scan event with that by inserting its data
Chris@16:       inline void insert(const TouchScanEvent& that){
Chris@16:         typename EventData::const_iterator itr;
Chris@16:         for(itr = that.eventData_.begin(); itr != that.eventData_.end(); ++itr) {
Chris@16:           eventData_[(*itr).first].insert(itr->second.begin(), itr->second.end());
Chris@16:         }
Chris@16:       }
Chris@16: 
Chris@16:       //Get the begin iterator over event data
Chris@16:       inline iterator begin() const {
Chris@16:         //std::cout << "begin\n";
Chris@16:         if(eventData_.empty()) return end();
Chris@16:         typename EventData::const_iterator itr = eventData_.begin();
Chris@16:         Unit pos = itr->first;
Chris@16:         const std::set<int>& idr = itr->second;
Chris@16:         ++itr;
Chris@16:         return iterator(itr, pos, itr->first, idr);
Chris@16:       }
Chris@16: 
Chris@16:       //Get the end iterator over event data
Chris@16:       inline iterator end() const { return iterator(eventData_.end(), 0, 0, std::set<int>()); }
Chris@16: 
Chris@16:       inline void clear() { eventData_.clear(); }
Chris@16: 
Chris@16:       inline Interval extents() const {
Chris@16:         if(eventData_.empty()) return Interval();
Chris@16:         return Interval((*(eventData_.begin())).first, (*(eventData_.rbegin())).first);
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     //declaration of a map of scan events by coordinate value used to store all the
Chris@16:     //polygon data for a single layer input into the scanline algorithm
Chris@16:     typedef std::pair<std::map<Unit, TouchScanEvent>, std::map<Unit, TouchScanEvent> > TouchSetData;
Chris@16: 
Chris@16:     class TouchOp {
Chris@16:     public:
Chris@16:       typedef std::map<Unit, std::set<int> > ScanData;
Chris@16:       typedef std::pair<Unit, std::set<int> > ElementType;
Chris@16:     protected:
Chris@16:       ScanData scanData_;
Chris@16:       typename ScanData::iterator nextItr_;
Chris@16:     public:
Chris@16:       inline TouchOp () : scanData_(), nextItr_() { nextItr_ = scanData_.end(); }
Chris@16:       inline TouchOp (const TouchOp& that) : scanData_(that.scanData_), nextItr_() { nextItr_ = scanData_.begin(); }
Chris@16:       inline TouchOp& operator=(const TouchOp& 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 std::set<int> data
Chris@16:       //the output data structre is a graph, the indicies in the vector correspond to graph nodes,
Chris@16:       //the integers in the set are vector indicies and are the nodes with which that node shares an edge
Chris@16:       template <typename graphT>
Chris@16:       inline void processInterval(graphT& outputContainer, Interval ivl, const std::set<int>& ids, bool leadingEdge) {
Chris@16:         //print();
Chris@16:         typename ScanData::iterator lowItr = lookup_(ivl.low());
Chris@16:         typename ScanData::iterator highItr = lookup_(ivl.high());
Chris@16:         //std::cout << "Interval: " << ivl << std::endl;
Chris@16:         //for(std::set<int>::const_iterator itr = ids.begin(); itr != ids.end(); ++itr)
Chris@16:         //   std::cout << (*itr) << " ";
Chris@16:         //std::cout << std::endl;
Chris@16:         //add interval to scan data if it is past the end
Chris@16:         if(lowItr == scanData_.end()) {
Chris@16:           //std::cout << "case0" << std::endl;
Chris@16:           lowItr = insert_(ivl.low(), ids);
Chris@16:           evaluateBorder_(outputContainer, ids, ids);
Chris@16:           highItr = insert_(ivl.high(), std::set<int>());
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:           //std::cout << "case1" << std::endl;
Chris@16:           //std::cout << highItr->first << std::endl;
Chris@16:           std::set<int> value = std::set<int>();
Chris@16:           if(highItr != scanData_.begin()) {
Chris@16:             --highItr;
Chris@16:             //std::cout << highItr->first << std::endl;
Chris@16:             //std::cout << "high set size " << highItr->second.size() << std::endl;
Chris@16:             value = highItr->second;
Chris@16:           }
Chris@16:           nextItr_ = highItr;
Chris@16:           highItr = insert_(ivl.high(), value);
Chris@16:         } else {
Chris@16:           //evaluate border with next higher interval
Chris@16:           //std::cout << "case1a" << std::endl;
Chris@16:           if(leadingEdge)evaluateBorder_(outputContainer, highItr->second, ids);
Chris@16:         }
Chris@16:         //split the low interval if needed
Chris@16:         if(lowItr->first > ivl.low()) {
Chris@16:           //std::cout << "case2" << std::endl;
Chris@16:           if(lowItr != scanData_.begin()) {
Chris@16:             //std::cout << "case3" << std::endl;
Chris@16:             --lowItr;
Chris@16:             nextItr_ = lowItr;
Chris@16:             //std::cout << lowItr->first << " " << lowItr->second.size() << std::endl;
Chris@16:             lowItr = insert_(ivl.low(), lowItr->second);
Chris@16:           } else {
Chris@16:             //std::cout << "case4" << std::endl;
Chris@16:             nextItr_ = lowItr;
Chris@16:             lowItr = insert_(ivl.low(), std::set<int>());
Chris@16:           }
Chris@16:         } else {
Chris@16:           //evaluate border with next higher interval
Chris@16:           //std::cout << "case2a" << std::endl;
Chris@16:           typename ScanData::iterator nextLowerItr = lowItr;
Chris@16:           if(leadingEdge && nextLowerItr != scanData_.begin()){
Chris@16:             --nextLowerItr;
Chris@16:             evaluateBorder_(outputContainer, nextLowerItr->second, ids);
Chris@16:           }
Chris@16:         }
Chris@16:         //std::cout << "low: " << lowItr->first << " high: " << highItr->first << std::endl;
Chris@16:         //print();
Chris@16:         //process scan data intersecting interval
Chris@16:         for(typename ScanData::iterator itr = lowItr; itr != highItr; ){
Chris@16:           //std::cout << "case5" << std::endl;
Chris@16:           //std::cout << itr->first << std::endl;
Chris@16:           std::set<int>& beforeIds = itr->second;
Chris@16:           ++itr;
Chris@16:           evaluateInterval_(outputContainer, beforeIds, ids, leadingEdge);
Chris@16:         }
Chris@16:         //print();
Chris@16:         //merge the bottom interval with the one below if they have the same count
Chris@16:         if(lowItr != scanData_.begin()){
Chris@16:           //std::cout << "case6" << std::endl;
Chris@16:           typename ScanData::iterator belowLowItr = lowItr;
Chris@16:           --belowLowItr;
Chris@16:           if(belowLowItr->second == lowItr->second) {
Chris@16:             //std::cout << "case7" << std::endl;
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:           //std::cout << "case8" << std::endl;
Chris@16:           typename ScanData::iterator beforeHighItr = highItr;
Chris@16:           --beforeHighItr;
Chris@16:           if(beforeHighItr->second == highItr->second) {
Chris@16:             //std::cout << "case9" << std::endl;
Chris@16:             scanData_.erase(highItr);
Chris@16:             highItr = beforeHighItr;
Chris@16:             ++highItr;
Chris@16:           }
Chris@16:         }
Chris@16:         //print();
Chris@16:         nextItr_ = highItr;
Chris@16:       }
Chris@16: 
Chris@16: //       inline void print() const {
Chris@16: //         for(typename ScanData::const_iterator itr = scanData_.begin(); itr != scanData_.end(); ++itr) {
Chris@16: //           std::cout << itr->first << ": ";
Chris@16: //           for(std::set<int>::const_iterator sitr = itr->second.begin();
Chris@16: //               sitr != itr->second.end(); ++sitr){
Chris@16: //             std::cout << *sitr << " ";
Chris@16: //           }
Chris@16: //           std::cout << std::endl;
Chris@16: //         }
Chris@16: //       }
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: 
Chris@16:       inline typename ScanData::iterator insert_(Unit pos, const std::set<int>& ids){
Chris@16:         //std::cout << "inserting " << ids.size() << " ids at: " << pos << std::endl;
Chris@16:         return nextItr_ = scanData_.insert(nextItr_, std::pair<Unit, std::set<int> >(pos, ids));
Chris@16:       }
Chris@16: 
Chris@16:       template <typename graphT>
Chris@16:       inline void evaluateInterval_(graphT& outputContainer, std::set<int>& ids,
Chris@16:                                     const std::set<int>& changingIds, bool leadingEdge) {
Chris@16:         for(std::set<int>::const_iterator ciditr = changingIds.begin(); ciditr != changingIds.end(); ++ciditr){
Chris@16:           //std::cout << "evaluateInterval " << (*ciditr) << std::endl;
Chris@16:           evaluateId_(outputContainer, ids, *ciditr, leadingEdge);
Chris@16:         }
Chris@16:       }
Chris@16:       template <typename graphT>
Chris@16:       inline void evaluateBorder_(graphT& outputContainer, const std::set<int>& ids, const std::set<int>& changingIds) {
Chris@16:         for(std::set<int>::const_iterator ciditr = changingIds.begin(); ciditr != changingIds.end(); ++ciditr){
Chris@16:           //std::cout << "evaluateBorder " << (*ciditr) << std::endl;
Chris@16:           evaluateBorderId_(outputContainer, ids, *ciditr);
Chris@16:         }
Chris@16:       }
Chris@16:       template <typename graphT>
Chris@16:       inline void evaluateBorderId_(graphT& outputContainer, const std::set<int>& ids, int changingId) {
Chris@16:         for(std::set<int>::const_iterator scanItr = ids.begin(); scanItr != ids.end(); ++scanItr) {
Chris@16:           //std::cout << "create edge: " << changingId << " " << *scanItr << std::endl;
Chris@16:           if(changingId != *scanItr){
Chris@16:             outputContainer[changingId].insert(*scanItr);
Chris@16:             outputContainer[*scanItr].insert(changingId);
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16:       template <typename graphT>
Chris@16:       inline void evaluateId_(graphT& outputContainer, std::set<int>& ids, int changingId, bool leadingEdge) {
Chris@16:         //std::cout << "changingId: " << changingId << std::endl;
Chris@16:         //for( std::set<int>::iterator itr = ids.begin(); itr != ids.end(); ++itr){
Chris@16:         //   std::cout << *itr << " ";
Chris@16:         //}std::cout << std::endl;
Chris@16:         std::set<int>::iterator lb = ids.lower_bound(changingId);
Chris@16:         if(lb == ids.end() || (*lb) != changingId) {
Chris@16:           if(leadingEdge) {
Chris@16:             //std::cout << "insert\n";
Chris@16:             //insert and add to output
Chris@16:             for(std::set<int>::iterator scanItr = ids.begin(); scanItr != ids.end(); ++scanItr) {
Chris@16:               //std::cout << "create edge: " << changingId << " " << *scanItr << std::endl;
Chris@16:               if(changingId != *scanItr){
Chris@16:                 outputContainer[changingId].insert(*scanItr);
Chris@16:                 outputContainer[*scanItr].insert(changingId);
Chris@16:               }
Chris@16:             }
Chris@16:             ids.insert(changingId);
Chris@16:           }
Chris@16:         } else {
Chris@16:           if(!leadingEdge){
Chris@16:             //std::cout << "erase\n";
Chris@16:             ids.erase(lb);
Chris@16:           }
Chris@16:         }
Chris@16:       }
Chris@16:     };
Chris@16: 
Chris@16:     template <typename graphT>
Chris@16:     static inline void processEvent(graphT& outputContainer, TouchOp& op, const TouchScanEvent& data, bool leadingEdge) {
Chris@16:       for(typename TouchScanEvent::iterator itr = data.begin(); itr != data.end(); ++itr) {
Chris@16:         //std::cout << "processInterval" << std::endl;
Chris@16:         op.processInterval(outputContainer, (*itr).first, (*itr).second, leadingEdge);
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     template <typename graphT>
Chris@16:     static inline void performTouch(graphT& outputContainer, const TouchSetData& data) {
Chris@16:       typename std::map<Unit, TouchScanEvent>::const_iterator leftItr = data.first.begin();
Chris@16:       typename std::map<Unit, TouchScanEvent>::const_iterator rightItr = data.second.begin();
Chris@16:       typename std::map<Unit, TouchScanEvent>::const_iterator leftEnd = data.first.end();
Chris@16:       typename std::map<Unit, TouchScanEvent>::const_iterator rightEnd = data.second.end();
Chris@16:       TouchOp op;
Chris@16:       while(leftItr != leftEnd || rightItr != rightEnd) {
Chris@16:         //std::cout << "loop" << std::endl;
Chris@16:         op.advanceScan();
Chris@16:         //rightItr cannont be at end if leftItr is not at end
Chris@16:         if(leftItr != leftEnd && rightItr != rightEnd &&
Chris@16:            leftItr->first <= rightItr->first) {
Chris@16:           //std::cout << "case1" << std::endl;
Chris@16:           //std::cout << leftItr ->first << std::endl;
Chris@16:           processEvent(outputContainer, op, leftItr->second, true);
Chris@16:           ++leftItr;
Chris@16:         } else {
Chris@16:           //std::cout << "case2" << std::endl;
Chris@16:           //std::cout << rightItr ->first << std::endl;
Chris@16:           processEvent(outputContainer, op, rightItr->second, false);
Chris@16:           ++rightItr;
Chris@16:         }
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     template <class iT>
Chris@16:     static inline void populateTouchSetData(TouchSetData& data, iT beginData, iT endData, int id) {
Chris@16:       Unit prevPos = ((std::numeric_limits<Unit>::max)());
Chris@16:       Unit prevY = prevPos;
Chris@16:       int count = 0;
Chris@16:       for(iT itr = beginData; itr != endData; ++itr) {
Chris@16:         Unit pos = (*itr).first;
Chris@16:         if(pos != prevPos) {
Chris@16:           prevPos = pos;
Chris@16:           prevY = (*itr).second.first;
Chris@16:           count = (*itr).second.second;
Chris@16:           continue;
Chris@16:         }
Chris@16:         Unit y = (*itr).second.first;
Chris@16:         if(count != 0 && y != prevY) {
Chris@16:           std::pair<Interval, int> element(Interval(prevY, y), id);
Chris@16:           if(count > 0) {
Chris@16:             data.first[pos].insert(element);
Chris@16:           } else {
Chris@16:             data.second[pos].insert(element);
Chris@16:           }
Chris@16:         }
Chris@16:         prevY = y;
Chris@16:         count += (*itr).second.second;
Chris@16:       }
Chris@16:     }
Chris@16: 
Chris@16:     static inline void populateTouchSetData(TouchSetData& data, const std::vector<std::pair<Unit, std::pair<Unit, int> > >& inputData, int id) {
Chris@16:       populateTouchSetData(data, inputData.begin(), inputData.end(), id);
Chris@16:     }
Chris@16: 
Chris@16:   };
Chris@16: }
Chris@16: }
Chris@16: #endif