third_party/boost/include/boost/polygon/detail/polygon_90_touch.hpp - webm/webmlive - Git at Google

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