text: /*
    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_PROPERTY_MERGE_HPP
  #define BOOST_POLYGON_PROPERTY_MERGE_HPP
  namespace boost { namespace polygon{
  
  template <typename coordinate_type>
  class property_merge_point {
  private:
    coordinate_type x_, y_;
  public:
    inline property_merge_point() : x_(), y_() {}
    inline property_merge_point(coordinate_type x, coordinate_type y) : x_(x), y_(y) {}
    //use builtin assign and copy
    inline bool operator==(const property_merge_point& that) const { return x_ == that.x_ && y_ == that.y_; }
    inline bool operator!=(const property_merge_point& that) const { return !((*this) == that); }
    inline bool operator<(const property_merge_point& that) const {
      if(x_ < that.x_) return true;
      if(x_ > that.x_) return false;
      return y_ < that.y_;
    }
    inline coordinate_type x() const { return x_; }
    inline coordinate_type y() const { return y_; }
    inline void x(coordinate_type value) { x_ = value; }
    inline void y(coordinate_type value) { y_ = value; }
  };
  
  template <typename coordinate_type>
  class property_merge_interval {
  private:
    coordinate_type low_, high_;
  public:
    inline property_merge_interval() : low_(), high_() {}
    inline property_merge_interval(coordinate_type low, coordinate_type high) : low_(low), high_(high) {}
    //use builtin assign and copy
    inline bool operator==(const property_merge_interval& that) const { return low_ == that.low_ && high_ == that.high_; }
    inline bool operator!=(const property_merge_interval& that) const { return !((*this) == that); }
    inline bool operator<(const property_merge_interval& that) const {
      if(low_ < that.low_) return true;
      if(low_ > that.low_) return false;
      return high_ < that.high_;
    }
    inline coordinate_type low() const { return low_; }
    inline coordinate_type high() const { return high_; }
    inline void low(coordinate_type value) { low_ = value; }
    inline void high(coordinate_type value) { high_ = value; }
  };
  
  template <typename coordinate_type, typename property_type, typename polygon_set_type, typename keytype = std::set<property_type> >
  class merge_scanline {
  public:
    //definitions
  
    typedef keytype property_set;
    typedef std::vector<std::pair<property_type, int> > property_map;
    typedef std::pair<property_merge_point<coordinate_type>, std::pair<property_type, int> > vertex_property;
    typedef std::pair<property_merge_point<coordinate_type>, property_map> vertex_data;
    typedef std::vector<vertex_property> property_merge_data;
    //typedef std::map<property_set, polygon_set_type> Result;
    typedef std::map<coordinate_type, property_map> scanline_type;
    typedef typename scanline_type::iterator scanline_iterator;
    typedef std::pair<property_merge_interval<coordinate_type>, std::pair<property_set, property_set> > edge_property;
    typedef std::vector<edge_property> edge_property_vector;
  
    //static public member functions
  
    template <typename iT, typename orientation_2d_type>
    static inline void 
    populate_property_merge_data(property_merge_data& pmd, iT input_begin, iT input_end, 
                                 const property_type& property, orientation_2d_type orient) {
      for( ; input_begin != input_end; ++input_begin) {
        std::pair<property_merge_point<coordinate_type>, std::pair<property_type, int> > element;
        if(orient == HORIZONTAL)
          element.first = property_merge_point<coordinate_type>((*input_begin).second.first, (*input_begin).first);
        else
          element.first = property_merge_point<coordinate_type>((*input_begin).first, (*input_begin).second.first);
        element.second.first = property;
        element.second.second = (*input_begin).second.second;
        pmd.push_back(element);
      }
    }
  
    //public member functions
  
    merge_scanline() : output(), scanline(), currentVertex(), tmpVector(), previousY(), countFromBelow(), scanlinePosition() {}
    merge_scanline(const merge_scanline& that) :
      output(that.output),
      scanline(that.scanline),
      currentVertex(that.currentVertex),
      tmpVector(that.tmpVector),
      previousY(that.previousY),
      countFromBelow(that.countFromBelow),
      scanlinePosition(that.scanlinePosition)
    {}
    merge_scanline& operator=(const merge_scanline& that) {
      output = that.output;
      scanline = that.scanline;
      currentVertex = that.currentVertex;
      tmpVector = that.tmpVector;
      previousY = that.previousY;
      countFromBelow = that.countFromBelow;
      scanlinePosition = that.scanlinePosition;
      return *this;
    }
  
    template <typename result_type>
    inline void perform_merge(result_type& result, property_merge_data& data) {
      if(data.empty()) return;
      //sort
      gtlsort(data.begin(), data.end(), less_vertex_data<vertex_property>());
      //scanline
      bool firstIteration = true;
      scanlinePosition = scanline.end();
      for(std::size_t i = 0; i < data.size(); ++i) {
        if(firstIteration) {
          mergeProperty(currentVertex.second, data[i].second);
          currentVertex.first = data[i].first;
          firstIteration = false;
        } else {
          if(data[i].first != currentVertex.first) {
            if(data[i].first.x() != currentVertex.first.x()) {
              processVertex(output);
              //std::cout << scanline.size() << " ";
              countFromBelow.clear(); //should already be clear
              writeOutput(currentVertex.first.x(), result, output);
              currentVertex.second.clear();
              mergeProperty(currentVertex.second, data[i].second);
              currentVertex.first = data[i].first;
              //std::cout << assertRedundant(scanline) << "/" << scanline.size() << " ";
            } else {
              processVertex(output);
              currentVertex.second.clear();
              mergeProperty(currentVertex.second, data[i].second);
              currentVertex.first = data[i].first;
            }
          } else {
            mergeProperty(currentVertex.second, data[i].second);
          }
        }
      }
      processVertex(output);
      writeOutput(currentVertex.first.x(), result, output);
      //std::cout << assertRedundant(scanline) << "/" << scanline.size() << "\n";
      //std::cout << scanline.size() << "\n";
    }
  
  private:
    //private supporting types
  
    template <class T>
    class less_vertex_data {
    public:
      less_vertex_data() {}
      bool operator()(const T& lvalue, const T& rvalue) const {
        if(lvalue.first.x() < rvalue.first.x()) return true;
        if(lvalue.first.x() > rvalue.first.x()) return false;
        if(lvalue.first.y() < rvalue.first.y()) return true;
        return false;
      }
    };
  
    template <typename T>
    struct lessPropertyCount {
      lessPropertyCount() {}
      bool operator()(const T& a, const T& b) {
        return a.first < b.first;
      }
    };
  
    //private static member functions
  
    static inline void mergeProperty(property_map& lvalue, std::pair<property_type, int>& rvalue) {
      typename property_map::iterator itr = std::lower_bound(lvalue.begin(), lvalue.end(), rvalue, 
                                                            lessPropertyCount<std::pair<property_type, int> >());
      if(itr == lvalue.end() ||
         (*itr).first != rvalue.first) {
        lvalue.insert(itr, rvalue);
      } else {
        (*itr).second += rvalue.second;
        if((*itr).second == 0)
          lvalue.erase(itr);
      }
  //     if(assertSorted(lvalue)) {
  //       std::cout << "in mergeProperty\n";
  //       exit(0);
  //     }
    }
  
  //   static inline bool assertSorted(property_map& pset) {
  //     bool result = false;
  //     for(std::size_t i = 1; i < pset.size(); ++i) {
  //       if(pset[i] < pset[i-1]) {
  //         std::cout << "Out of Order Error ";
  //         result = true;
  //       }
  //       if(pset[i].first == pset[i-1].first) {
  //         std::cout << "Duplicate Property Error ";
  //         result = true;
  //       }
  //       if(pset[0].second == 0 || pset[1].second == 0) {
  //         std::cout << "Empty Property Error ";
  //         result = true;
  //       }
  //     }
  //     return result;
  //   }
  
    static inline void setProperty(property_set& pset, property_map& pmap) {
      for(typename property_map::iterator itr = pmap.begin(); itr != pmap.end(); ++itr) {
        if((*itr).second > 0) {
          pset.insert(pset.end(), (*itr).first);
        }
      }
    }
  
    //private data members
  
    edge_property_vector output;
    scanline_type scanline;
    vertex_data currentVertex;
    property_map tmpVector;
    coordinate_type previousY;
    property_map countFromBelow;
    scanline_iterator scanlinePosition;
  
    //private member functions
  
    inline void mergeCount(property_map& lvalue, property_map& rvalue) {
      typename property_map::iterator litr = lvalue.begin();
      typename property_map::iterator ritr = rvalue.begin();
      tmpVector.clear();
      while(litr != lvalue.end() && ritr != rvalue.end()) {
        if((*litr).first <= (*ritr).first) {
          if(!tmpVector.empty() &&
             (*litr).first == tmpVector.back().first) {
            tmpVector.back().second += (*litr).second;
          } else {
            tmpVector.push_back(*litr);
          }
          ++litr;
        } else if((*ritr).first <= (*litr).first) {
          if(!tmpVector.empty() &&
             (*ritr).first == tmpVector.back().first) {
            tmpVector.back().second += (*ritr).second;
          } else {
            tmpVector.push_back(*ritr);
          }
          ++ritr;
        }
      }
      while(litr != lvalue.end()) {
        if(!tmpVector.empty() &&
           (*litr).first == tmpVector.back().first) {
          tmpVector.back().second += (*litr).second;
        } else {
          tmpVector.push_back(*litr);
        }
        ++litr;
      }
      while(ritr != rvalue.end()) {
        if(!tmpVector.empty() &&
           (*ritr).first == tmpVector.back().first) {
          tmpVector.back().second += (*ritr).second;
        } else {
          tmpVector.push_back(*ritr);
        }
        ++ritr;
      }
      lvalue.clear();
      for(std::size_t i = 0; i < tmpVector.size(); ++i) {
        if(tmpVector[i].second != 0) {
          lvalue.push_back(tmpVector[i]);
        }
      }
  //     if(assertSorted(lvalue)) {
  //       std::cout << "in mergeCount\n";
  //       exit(0);
  //     }
    }
  
    inline void processVertex(edge_property_vector& output) {
      if(!countFromBelow.empty()) {
        //we are processing an interval of change in scanline state between
        //previous vertex position and current vertex position where 
        //count from below represents the change on the interval
        //foreach scanline element from previous to current we
        //write the interval on the scanline that is changing
        //the old value and the new value to output
        property_merge_interval<coordinate_type> currentInterval(previousY, currentVertex.first.y());
        coordinate_type currentY = currentInterval.low();
        if(scanlinePosition == scanline.end() ||
           (*scanlinePosition).first != previousY) {
          scanlinePosition = scanline.lower_bound(previousY);
        }
        scanline_iterator previousScanlinePosition = scanlinePosition;
        ++scanlinePosition;
        while(scanlinePosition != scanline.end()) {
          coordinate_type elementY = (*scanlinePosition).first;
          if(elementY <= currentInterval.high()) {
            property_map& countOnLeft = (*previousScanlinePosition).second;
            edge_property element;
            output.push_back(element);
            output.back().first = property_merge_interval<coordinate_type>((*previousScanlinePosition).first, elementY);
            setProperty(output.back().second.first, countOnLeft);
            mergeCount(countOnLeft, countFromBelow);
            setProperty(output.back().second.second, countOnLeft);
            if(output.back().second.first == output.back().second.second) {
              output.pop_back(); //it was an internal vertical edge, not to be output
            }
            else if(output.size() > 1) {
              edge_property& secondToLast = output[output.size()-2];
              if(secondToLast.first.high() == output.back().first.low() &&
                 secondToLast.second.first == output.back().second.first &&
                 secondToLast.second.second == output.back().second.second) {
                //merge output onto previous output because properties are
                //identical on both sides implying an internal horizontal edge
                secondToLast.first.high(output.back().first.high());
                output.pop_back();
              }
            }
            if(previousScanlinePosition == scanline.begin()) {
              if(countOnLeft.empty()) {
                scanline.erase(previousScanlinePosition);
              }
            } else {
              scanline_iterator tmpitr = previousScanlinePosition;
              --tmpitr;
              if((*tmpitr).second == (*previousScanlinePosition).second)
                scanline.erase(previousScanlinePosition);
            }
               
          } else if(currentY < currentInterval.high()){
            //elementY > currentInterval.high()
            //split the interval between previous and current scanline elements
            std::pair<coordinate_type, property_map> elementScan;
            elementScan.first = currentInterval.high();
            elementScan.second = (*previousScanlinePosition).second;
            scanlinePosition = scanline.insert(scanlinePosition, elementScan);
            continue;
          } else {
            break;
          }
          previousScanlinePosition = scanlinePosition;
          currentY = previousY = elementY;
          ++scanlinePosition;
          if(scanlinePosition == scanline.end() &&
             currentY < currentInterval.high()) {
            //insert a new element for top of range
            std::pair<coordinate_type, property_map> elementScan;
            elementScan.first = currentInterval.high();
            scanlinePosition = scanline.insert(scanline.end(), elementScan);
          } 
        }
        if(scanlinePosition == scanline.end() &&
           currentY < currentInterval.high()) {
          //handle case where we iterated to end of the scanline
          //we need to insert an element into the scanline at currentY
          //with property value coming from below
          //and another one at currentInterval.high() with empty property value
          mergeCount(scanline[currentY], countFromBelow);
          std::pair<coordinate_type, property_map> elementScan;
          elementScan.first = currentInterval.high();
          scanline.insert(scanline.end(), elementScan);
  
          edge_property element;
          output.push_back(element);
          output.back().first = property_merge_interval<coordinate_type>(currentY, currentInterval.high());
          setProperty(output.back().second.second, countFromBelow);
          mergeCount(countFromBelow, currentVertex.second);
        } else {
          mergeCount(countFromBelow, currentVertex.second);
          if(countFromBelow.empty()) {
            if(previousScanlinePosition == scanline.begin()) {
              if((*previousScanlinePosition).second.empty()) {
                scanline.erase(previousScanlinePosition);
                //previousScanlinePosition = scanline.end();
                //std::cout << "ERASE_A ";
              }
            } else {
              scanline_iterator tmpitr = previousScanlinePosition;
              --tmpitr;
              if((*tmpitr).second == (*previousScanlinePosition).second) {
                scanline.erase(previousScanlinePosition);
                //previousScanlinePosition = scanline.end();
                //std::cout << "ERASE_B ";
              }
            }
          }
        }
      } else {
        //count from below is empty, we are starting a new interval of change
        countFromBelow = currentVertex.second;
        scanlinePosition = scanline.lower_bound(currentVertex.first.y());
        if(scanlinePosition != scanline.end()) {
          if((*scanlinePosition).first != currentVertex.first.y()) {
            if(scanlinePosition != scanline.begin()) {
              //decrement to get the lower position of the first interval this vertex intersects
              --scanlinePosition;
              //insert a new element into the scanline for the incoming vertex
              property_map& countOnLeft = (*scanlinePosition).second;
              std::pair<coordinate_type, property_map> element(currentVertex.first.y(), countOnLeft);
              scanlinePosition = scanline.insert(scanlinePosition, element);
            } else {
              property_map countOnLeft;
              std::pair<coordinate_type, property_map> element(currentVertex.first.y(), countOnLeft);
              scanlinePosition = scanline.insert(scanlinePosition, element);
            }
          }
        } else {
          property_map countOnLeft;
          std::pair<coordinate_type, property_map> element(currentVertex.first.y(), countOnLeft);
          scanlinePosition = scanline.insert(scanlinePosition, element);
        }
      }
      previousY = currentVertex.first.y();
    }
  
    template <typename T>
    inline int assertRedundant(T& t) {
      if(t.empty()) return 0;
      int count = 0; 
      typename T::iterator itr = t.begin();
      if((*itr).second.empty())
        ++count;
      typename T::iterator itr2 = itr;
      ++itr2;
      while(itr2 != t.end()) {
        if((*itr).second == (*itr2).second)
          ++count;
        itr = itr2;
        ++itr2;
      }
      return count;
    }
  
    template <typename T>
    inline void performExtract(T& result, property_merge_data& data) {
      if(data.empty()) return;
      //sort
      gtlsort(data.begin(), data.end(), less_vertex_data<vertex_property>());
      
      //scanline
      bool firstIteration = true;
      scanlinePosition = scanline.end();
      for(std::size_t i = 0; i < data.size(); ++i) {
        if(firstIteration) {
          mergeProperty(currentVertex.second, data[i].second);
          currentVertex.first = data[i].first;
          firstIteration = false;
        } else {
          if(data[i].first != currentVertex.first) {
            if(data[i].first.x() != currentVertex.first.x()) {
              processVertex(output);
              //std::cout << scanline.size() << " ";
              countFromBelow.clear(); //should already be clear
              writeGraph(currentVertex.first.x(), result, output, scanline);
              currentVertex.second.clear();
              mergeProperty(currentVertex.second, data[i].second);
              currentVertex.first = data[i].first;
            } else {
              processVertex(output);
              currentVertex.second.clear();
              mergeProperty(currentVertex.second, data[i].second);
              currentVertex.first = data[i].first;
            }
          } else {
            mergeProperty(currentVertex.second, data[i].second);
          }
        }
      }
      processVertex(output);
      writeGraph(currentVertex.first.x(), result, output, scanline);
      //std::cout << scanline.size() << "\n";
    }
  
    template <typename T>
    inline void insertEdges(T& graph, property_set& p1, property_set& p2) {
      for(typename property_set::iterator itr = p1.begin(); itr != p1.end(); ++itr) {
        for(typename property_set::iterator itr2 = p2.begin(); itr2 != p2.end(); ++itr2) {
          if(*itr != *itr2) {
            graph[*itr].insert(*itr2);
            graph[*itr2].insert(*itr);
          }
        }
      }
    }
  
    template <typename T>
    inline void propertySetAbove(coordinate_type y, property_set& ps, T& scanline) {
      ps.clear();
      typename T::iterator itr = scanline.find(y);
      if(itr != scanline.end())
        setProperty(ps, (*itr).second);
    }
  
    template <typename T>
    inline void propertySetBelow(coordinate_type y, property_set& ps, T& scanline) {
      ps.clear();
      typename T::iterator itr = scanline.find(y);
      if(itr != scanline.begin()) {
        --itr;
        setProperty(ps, (*itr).second);
      }
    }
  
    template <typename T, typename T2>
    inline void writeGraph(coordinate_type x, T& graph, edge_property_vector& output, T2& scanline) {
      if(output.empty()) return;
      edge_property* previousEdgeP = &(output[0]);
      bool firstIteration = true;
      property_set ps;
      for(std::size_t i = 0; i < output.size(); ++i) {
        edge_property& previousEdge = *previousEdgeP;
        edge_property& edge = output[i];
        if(previousEdge.first.high() == edge.first.low()) {
          //horizontal edge
          insertEdges(graph, edge.second.first, previousEdge.second.first);
          //corner 1
          insertEdges(graph, edge.second.first, previousEdge.second.second);
          //other horizontal edge
          insertEdges(graph, edge.second.second, previousEdge.second.second);
          //corner 2
          insertEdges(graph, edge.second.second, previousEdge.second.first);
        } else {
          if(!firstIteration){
            //look up regions above previous edge 
            propertySetAbove(previousEdge.first.high(), ps, scanline);
            insertEdges(graph, ps, previousEdge.second.first);
            insertEdges(graph, ps, previousEdge.second.second);
          }
          //look up regions below current edge in the scanline
          propertySetBelow(edge.first.high(), ps, scanline);
          insertEdges(graph, ps, edge.second.first);
          insertEdges(graph, ps, edge.second.second);
        }
        firstIteration = false;
        //vertical edge
        insertEdges(graph, edge.second.second, edge.second.first);
        //shared region to left
        insertEdges(graph, edge.second.second, edge.second.second);
        //shared region to right
        insertEdges(graph, edge.second.first, edge.second.first);
        previousEdgeP = &(output[i]);
      }
      edge_property& previousEdge = *previousEdgeP;
      propertySetAbove(previousEdge.first.high(), ps, scanline);
      insertEdges(graph, ps, previousEdge.second.first);
      insertEdges(graph, ps, previousEdge.second.second);
      output.clear();
    }
  
    template <typename Result>
    inline void writeOutput(coordinate_type x, Result& result, edge_property_vector& output) {
      for(std::size_t i = 0; i < output.size(); ++i) {
        edge_property& edge = output[i];
        //edge.second.first is the property set on the left of the edge
        if(!edge.second.first.empty()) {
          typename Result::iterator itr = result.find(edge.second.first);
          if(itr == result.end()) {
            std::pair<property_set, polygon_set_type> element(edge.second.first, polygon_set_type(VERTICAL));
            itr = result.insert(result.end(), element);
          }
          std::pair<interval_data<coordinate_type>, int> element2(interval_data<coordinate_type>(edge.first.low(), edge.first.high()), -1); //right edge of figure
          (*itr).second.insert(x, element2);
        }
        if(!edge.second.second.empty()) {
          //edge.second.second is the property set on the right of the edge
          typename Result::iterator itr = result.find(edge.second.second);
          if(itr == result.end()) {
            std::pair<property_set, polygon_set_type> element(edge.second.second, polygon_set_type(VERTICAL));
            itr = result.insert(result.end(), element);
          }
          std::pair<interval_data<coordinate_type>, int> element3(interval_data<coordinate_type>(edge.first.low(), edge.first.high()), 1); //left edge of figure
          (*itr).second.insert(x, element3);
        }
      }
      output.clear();
    }
  };
  
  }
  }
  #endif
  