ceph/src/boost/boost/polygon/detail/polygon_90_touch.hpp

   1 /*
   2   Copyright 2008 Intel Corporation
   3
   4   Use, modification and distribution are subject to the Boost Software License,
   5   Version 1.0. (See accompanying file LICENSE_1_0.txt or copy at
   6   http://www.boost.org/LICENSE_1_0.txt).
   7 */
   8 #ifndef BOOST_POLYGON_POLYGON_90_TOUCH_HPP
   9 #define BOOST_POLYGON_POLYGON_90_TOUCH_HPP
  10 namespace boost { namespace polygon{
  11
  12   template <typename Unit>
  13   struct touch_90_operation {
  14     typedef interval_data<Unit> Interval;
  15
  16     class TouchScanEvent {
  17     private:
  18       typedef std::map<Unit, std::set<int> > EventData;
  19       EventData eventData_;
  20     public:
  21
  22       // The TouchScanEvent::iterator is a lazy algorithm that accumulates
  23       // polygon ids in a set as it is incremented through the
  24       // scan event data structure.
  25       // The iterator provides a forward iterator semantic only.
  26       class iterator {
  27       private:
  28         typename EventData::const_iterator itr_;
  29         std::pair<Interval, std::set<int> > ivlIds_;
  30         bool incremented_;
  31       public:
  32         inline iterator() : itr_(), ivlIds_(), incremented_(false) {}
  33         inline iterator(typename EventData::const_iterator itr,
  34                         Unit prevPos, Unit curPos, const std::set<int>& ivlIds) : itr_(itr), ivlIds_(), incremented_(false) {
  35           ivlIds_.second = ivlIds;
  36           ivlIds_.first = Interval(prevPos, curPos);
  37         }
  38         inline iterator(const iterator& that) : itr_(), ivlIds_(), incremented_(false) { (*this) = that; }
  39         inline iterator& operator=(const iterator& that) {
  40           itr_ = that.itr_;
  41           ivlIds_.first = that.ivlIds_.first;
  42           ivlIds_.second = that.ivlIds_.second;
  43           incremented_ = that.incremented_;
  44           return *this;
  45         }
  46         inline bool operator==(const iterator& that) { return itr_ == that.itr_; }
  47         inline bool operator!=(const iterator& that) { return itr_ != that.itr_; }
  48         inline iterator& operator++() {
  49           //std::cout << "increment\n";
  50           //std::cout << "state\n";
  51           //for(std::set<int>::iterator itr = ivlIds_.second.begin(); itr != ivlIds_.second.end(); ++itr) {
  52           //   std::cout << (*itr) << " ";
  53           //} std::cout << std::endl;
  54           //std::cout << "update\n";
  55           for(std::set<int>::const_iterator itr = (*itr_).second.begin();
  56               itr != (*itr_).second.end(); ++itr) {
  57             //std::cout << (*itr) <<  " ";
  58             std::set<int>::iterator lb = ivlIds_.second.find(*itr);
  59             if(lb != ivlIds_.second.end()) {
  60               ivlIds_.second.erase(lb);
  61             } else {
  62               ivlIds_.second.insert(*itr);
  63             }
  64           }
  65           //std::cout << std::endl;
  66           //std::cout << "new state\n";
  67           //for(std::set<int>::iterator itr = ivlIds_.second.begin(); itr != ivlIds_.second.end(); ++itr) {
  68           //   std::cout << (*itr) << " ";
  69           //} std::cout << std::endl;
  70           ++itr_;
  71           //ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
  72           incremented_ = true;
  73           return *this;
  74         }
  75         inline const iterator operator++(int){
  76           iterator tmpItr(*this);
  77           ++(*this);
  78           return tmpItr;
  79         }
  80         inline std::pair<Interval, std::set<int> >& operator*() {
  81           if(incremented_) ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
  82           incremented_ = false;
  83           if(ivlIds_.second.empty())(++(*this));
  84           if(incremented_) ivlIds_.first = Interval(ivlIds_.first.get(HIGH), itr_->first);
  85           incremented_ = false;
  86           return ivlIds_; }
  87       };
  88
  89       inline TouchScanEvent() : eventData_() {}
  90       template<class iT>
  91       inline TouchScanEvent(iT begin, iT end) : eventData_() {
  92         for( ; begin != end; ++begin){
  93           insert(*begin);
  94         }
  95       }
  96       inline TouchScanEvent(const TouchScanEvent& that) : eventData_(that.eventData_) {}
  97       inline TouchScanEvent& operator=(const TouchScanEvent& that){
  98         eventData_ = that.eventData_;
  99         return *this;
 100       }
 101
 102       //Insert an interval polygon id into the EventData
 103       inline void insert(const std::pair<Interval, int>& intervalId){
 104         insert(intervalId.first.low(), intervalId.second);
 105         insert(intervalId.first.high(), intervalId.second);
 106       }
 107
 108       //Insert an position and polygon id into EventData
 109       inline void insert(Unit pos, int id) {
 110         typename EventData::iterator lb = eventData_.lower_bound(pos);
 111         if(lb != eventData_.end() && lb->first == pos) {
 112           std::set<int>& mr (lb->second);
 113           std::set<int>::iterator mri = mr.find(id);
 114           if(mri == mr.end()) {
 115             mr.insert(id);
 116           } else {
 117             mr.erase(id);
 118           }
 119         } else {
 120           lb = eventData_.insert(lb, std::pair<Unit, std::set<int> >(pos, std::set<int>()));
 121           (*lb).second.insert(id);
 122         }
 123       }
 124
 125       //merge this scan event with that by inserting its data
 126       inline void insert(const TouchScanEvent& that){
 127         typename EventData::const_iterator itr;
 128         for(itr = that.eventData_.begin(); itr != that.eventData_.end(); ++itr) {
 129           eventData_[(*itr).first].insert(itr->second.begin(), itr->second.end());
 130         }
 131       }
 132
 133       //Get the begin iterator over event data
 134       inline iterator begin() const {
 135         //std::cout << "begin\n";
 136         if(eventData_.empty()) return end();
 137         typename EventData::const_iterator itr = eventData_.begin();
 138         Unit pos = itr->first;
 139         const std::set<int>& idr = itr->second;
 140         ++itr;
 141         return iterator(itr, pos, itr->first, idr);
 142       }
 143
 144       //Get the end iterator over event data
 145       inline iterator end() const { return iterator(eventData_.end(), 0, 0, std::set<int>()); }
 146
 147       inline void clear() { eventData_.clear(); }
 148
 149       inline Interval extents() const {
 150         if(eventData_.empty()) return Interval();
 151         return Interval((*(eventData_.begin())).first, (*(eventData_.rbegin())).first);
 152       }
 153     };
 154
 155     //declaration of a map of scan events by coordinate value used to store all the
 156     //polygon data for a single layer input into the scanline algorithm
 157     typedef std::pair<std::map<Unit, TouchScanEvent>, std::map<Unit, TouchScanEvent> > TouchSetData;
 158
 159     class TouchOp {
 160     public:
 161       typedef std::map<Unit, std::set<int> > ScanData;
 162       typedef std::pair<Unit, std::set<int> > ElementType;
 163     protected:
 164       ScanData scanData_;
 165       typename ScanData::iterator nextItr_;
 166     public:
 167       inline TouchOp () : scanData_(), nextItr_() { nextItr_ = scanData_.end(); }
 168       inline TouchOp (const TouchOp& that) : scanData_(that.scanData_), nextItr_() { nextItr_ = scanData_.begin(); }
 169       inline TouchOp& operator=(const TouchOp& that);
 170
 171       //moves scanline forward
 172       inline void advanceScan() { nextItr_ = scanData_.begin(); }
 173
 174       //proceses the given interval and std::set<int> data
 175       //the output data structre is a graph, the indicies in the vector correspond to graph nodes,
 176       //the integers in the set are vector indicies and are the nodes with which that node shares an edge
 177       template <typename graphT>
 178       inline void processInterval(graphT& outputContainer, Interval ivl, const std::set<int>& ids, bool leadingEdge) {
 179         //print();
 180         typename ScanData::iterator lowItr = lookup_(ivl.low());
 181         typename ScanData::iterator highItr = lookup_(ivl.high());
 182         //std::cout << "Interval: " << ivl << std::endl;
 183         //for(std::set<int>::const_iterator itr = ids.begin(); itr != ids.end(); ++itr)
 184         //   std::cout << (*itr) << " ";
 185         //std::cout << std::endl;
 186         //add interval to scan data if it is past the end
 187         if(lowItr == scanData_.end()) {
 188           //std::cout << "case0" << std::endl;
 189           lowItr = insert_(ivl.low(), ids);
 190           evaluateBorder_(outputContainer, ids, ids);
 191           highItr = insert_(ivl.high(), std::set<int>());
 192           return;
 193         }
 194         //ensure that highItr points to the end of the ivl
 195         if(highItr == scanData_.end() || (*highItr).first > ivl.high()) {
 196           //std::cout << "case1" << std::endl;
 197           //std::cout << highItr->first << std::endl;
 198           std::set<int> value = std::set<int>();
 199           if(highItr != scanData_.begin()) {
 200             --highItr;
 201             //std::cout << highItr->first << std::endl;
 202             //std::cout << "high set size " << highItr->second.size() << std::endl;
 203             value = highItr->second;
 204           }
 205           nextItr_ = highItr;
 206           highItr = insert_(ivl.high(), value);
 207         } else {
 208           //evaluate border with next higher interval
 209           //std::cout << "case1a" << std::endl;
 210           if(leadingEdge)evaluateBorder_(outputContainer, highItr->second, ids);
 211         }
 212         //split the low interval if needed
 213         if(lowItr->first > ivl.low()) {
 214           //std::cout << "case2" << std::endl;
 215           if(lowItr != scanData_.begin()) {
 216             //std::cout << "case3" << std::endl;
 217             --lowItr;
 218             nextItr_ = lowItr;
 219             //std::cout << lowItr->first << " " << lowItr->second.size() << std::endl;
 220             lowItr = insert_(ivl.low(), lowItr->second);
 221           } else {
 222             //std::cout << "case4" << std::endl;
 223             nextItr_ = lowItr;
 224             lowItr = insert_(ivl.low(), std::set<int>());
 225           }
 226         } else {
 227           //evaluate border with next higher interval
 228           //std::cout << "case2a" << std::endl;
 229           typename ScanData::iterator nextLowerItr = lowItr;
 230           if(leadingEdge && nextLowerItr != scanData_.begin()){
 231             --nextLowerItr;
 232             evaluateBorder_(outputContainer, nextLowerItr->second, ids);
 233           }
 234         }
 235         //std::cout << "low: " << lowItr->first << " high: " << highItr->first << std::endl;
 236         //print();
 237         //process scan data intersecting interval
 238         for(typename ScanData::iterator itr = lowItr; itr != highItr; ){
 239           //std::cout << "case5" << std::endl;
 240           //std::cout << itr->first << std::endl;
 241           std::set<int>& beforeIds = itr->second;
 242           ++itr;
 243           evaluateInterval_(outputContainer, beforeIds, ids, leadingEdge);
 244         }
 245         //print();
 246         //merge the bottom interval with the one below if they have the same count
 247         if(lowItr != scanData_.begin()){
 248           //std::cout << "case6" << std::endl;
 249           typename ScanData::iterator belowLowItr = lowItr;
 250           --belowLowItr;
 251           if(belowLowItr->second == lowItr->second) {
 252             //std::cout << "case7" << std::endl;
 253             scanData_.erase(lowItr);
 254           }
 255         }
 256         //merge the top interval with the one above if they have the same count
 257         if(highItr != scanData_.begin()) {
 258           //std::cout << "case8" << std::endl;
 259           typename ScanData::iterator beforeHighItr = highItr;
 260           --beforeHighItr;
 261           if(beforeHighItr->second == highItr->second) {
 262             //std::cout << "case9" << std::endl;
 263             scanData_.erase(highItr);
 264             highItr = beforeHighItr;
 265             ++highItr;
 266           }
 267         }
 268         //print();
 269         nextItr_ = highItr;
 270       }
 271
 272 //       inline void print() const {
 273 //         for(typename ScanData::const_iterator itr = scanData_.begin(); itr != scanData_.end(); ++itr) {
 274 //           std::cout << itr->first << ": ";
 275 //           for(std::set<int>::const_iterator sitr = itr->second.begin();
 276 //               sitr != itr->second.end(); ++sitr){
 277 //             std::cout << *sitr << " ";
 278 //           }
 279 //           std::cout << std::endl;
 280 //         }
 281 //       }
 282
 283     private:
 284       inline typename ScanData::iterator lookup_(Unit pos){
 285         if(nextItr_ != scanData_.end() && nextItr_->first >= pos) {
 286           return nextItr_;
 287         }
 288         return nextItr_ = scanData_.lower_bound(pos);
 289       }
 290
 291       inline typename ScanData::iterator insert_(Unit pos, const std::set<int>& ids){
 292         //std::cout << "inserting " << ids.size() << " ids at: " << pos << std::endl;
 293         return nextItr_ = scanData_.insert(nextItr_, std::pair<Unit, std::set<int> >(pos, ids));
 294       }
 295
 296       template <typename graphT>
 297       inline void evaluateInterval_(graphT& outputContainer, std::set<int>& ids,
 298                                     const std::set<int>& changingIds, bool leadingEdge) {
 299         for(std::set<int>::const_iterator ciditr = changingIds.begin(); ciditr != changingIds.end(); ++ciditr){
 300           //std::cout << "evaluateInterval " << (*ciditr) << std::endl;
 301           evaluateId_(outputContainer, ids, *ciditr, leadingEdge);
 302         }
 303       }
 304       template <typename graphT>
 305       inline void evaluateBorder_(graphT& outputContainer, const std::set<int>& ids, const std::set<int>& changingIds) {
 306         for(std::set<int>::const_iterator ciditr = changingIds.begin(); ciditr != changingIds.end(); ++ciditr){
 307           //std::cout << "evaluateBorder " << (*ciditr) << std::endl;
 308           evaluateBorderId_(outputContainer, ids, *ciditr);
 309         }
 310       }
 311       template <typename graphT>
 312       inline void evaluateBorderId_(graphT& outputContainer, const std::set<int>& ids, int changingId) {
 313         for(std::set<int>::const_iterator scanItr = ids.begin(); scanItr != ids.end(); ++scanItr) {
 314           //std::cout << "create edge: " << changingId << " " << *scanItr << std::endl;
 315           if(changingId != *scanItr){
 316             outputContainer[changingId].insert(*scanItr);
 317             outputContainer[*scanItr].insert(changingId);
 318           }
 319         }
 320       }
 321       template <typename graphT>
 322       inline void evaluateId_(graphT& outputContainer, std::set<int>& ids, int changingId, bool leadingEdge) {
 323         //std::cout << "changingId: " << changingId << std::endl;
 324         //for( std::set<int>::iterator itr = ids.begin(); itr != ids.end(); ++itr){
 325         //   std::cout << *itr << " ";
 326         //}std::cout << std::endl;
 327         std::set<int>::iterator lb = ids.lower_bound(changingId);
 328         if(lb == ids.end() || (*lb) != changingId) {
 329           if(leadingEdge) {
 330             //std::cout << "insert\n";
 331             //insert and add to output
 332             for(std::set<int>::iterator scanItr = ids.begin(); scanItr != ids.end(); ++scanItr) {
 333               //std::cout << "create edge: " << changingId << " " << *scanItr << std::endl;
 334               if(changingId != *scanItr){
 335                 outputContainer[changingId].insert(*scanItr);
 336                 outputContainer[*scanItr].insert(changingId);
 337               }
 338             }
 339             ids.insert(changingId);
 340           }
 341         } else {
 342           if(!leadingEdge){
 343             //std::cout << "erase\n";
 344             ids.erase(lb);
 345           }
 346         }
 347       }
 348     };
 349
 350     template <typename graphT>
 351     static inline void processEvent(graphT& outputContainer, TouchOp& op, const TouchScanEvent& data, bool leadingEdge) {
 352       for(typename TouchScanEvent::iterator itr = data.begin(); itr != data.end(); ++itr) {
 353         //std::cout << "processInterval" << std::endl;
 354         op.processInterval(outputContainer, (*itr).first, (*itr).second, leadingEdge);
 355       }
 356     }
 357
 358     template <typename graphT>
 359     static inline void performTouch(graphT& outputContainer, const TouchSetData& data) {
 360       typename std::map<Unit, TouchScanEvent>::const_iterator leftItr = data.first.begin();
 361       typename std::map<Unit, TouchScanEvent>::const_iterator rightItr = data.second.begin();
 362       typename std::map<Unit, TouchScanEvent>::const_iterator leftEnd = data.first.end();
 363       typename std::map<Unit, TouchScanEvent>::const_iterator rightEnd = data.second.end();
 364       TouchOp op;
 365       while(leftItr != leftEnd || rightItr != rightEnd) {
 366         //std::cout << "loop" << std::endl;
 367         op.advanceScan();
 368         //rightItr cannont be at end if leftItr is not at end
 369         if(leftItr != leftEnd && rightItr != rightEnd &&
 370            leftItr->first <= rightItr->first) {
 371           //std::cout << "case1" << std::endl;
 372           //std::cout << leftItr ->first << std::endl;
 373           processEvent(outputContainer, op, leftItr->second, true);
 374           ++leftItr;
 375         } else {
 376           //std::cout << "case2" << std::endl;
 377           //std::cout << rightItr ->first << std::endl;
 378           processEvent(outputContainer, op, rightItr->second, false);
 379           ++rightItr;
 380         }
 381       }
 382     }
 383
 384     template <class iT>
 385     static inline void populateTouchSetData(TouchSetData& data, iT beginData, iT endData, int id) {
 386       Unit prevPos = ((std::numeric_limits<Unit>::max)());
 387       Unit prevY = prevPos;
 388       int count = 0;
 389       for(iT itr = beginData; itr != endData; ++itr) {
 390         Unit pos = (*itr).first;
 391         if(pos != prevPos) {
 392           prevPos = pos;
 393           prevY = (*itr).second.first;
 394           count = (*itr).second.second;
 395           continue;
 396         }
 397         Unit y = (*itr).second.first;
 398         if(count != 0 && y != prevY) {
 399           std::pair<Interval, int> element(Interval(prevY, y), id);
 400           if(count > 0) {
 401             data.first[pos].insert(element);
 402           } else {
 403             data.second[pos].insert(element);
 404           }
 405         }
 406         prevY = y;
 407         count += (*itr).second.second;
 408       }
 409     }
 410
 411     static inline void populateTouchSetData(TouchSetData& data, const std::vector<std::pair<Unit, std::pair<Unit, int> > >& inputData, int id) {
 412       populateTouchSetData(data, inputData.begin(), inputData.end(), id);
 413     }
 414
 415   };
 416 }
 417 }
 418 #endif