ceph/src/boost/libs/polygon/include/boost/polygon/detail/max_cover.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_MAX_COVER_HPP
   9 #define BOOST_POLYGON_MAX_COVER_HPP
  10 namespace boost { namespace polygon{
  11
  12   template <typename Unit>
  13   struct MaxCover {
  14     typedef interval_data<Unit> Interval;
  15     typedef rectangle_data<Unit> Rectangle;
  16
  17     class Node {
  18     private:
  19       std::vector<Node*> children_;
  20       std::set<Interval> tracedPaths_;
  21     public:
  22       Rectangle rect;
  23       Node() : children_(), tracedPaths_(), rect() {}
  24       Node(const Rectangle rectIn) : children_(), tracedPaths_(), rect(rectIn) {}
  25       typedef typename std::vector<Node*>::iterator iterator;
  26       inline iterator begin() { return children_.begin(); }
  27       inline iterator end() { return children_.end(); }
  28       inline void add(Node* child) { children_.push_back(child); }
  29       inline bool tracedPath(const Interval& ivl) const {
  30         return tracedPaths_.find(ivl) != tracedPaths_.end();
  31       }
  32       inline void addPath(const Interval& ivl) {
  33         tracedPaths_.insert(tracedPaths_.end(), ivl);
  34       }
  35     };
  36
  37     typedef std::pair<std::pair<Unit, Interval>, Node* > EdgeAssociation;
  38
  39     class lessEdgeAssociation : public std::binary_function<const EdgeAssociation&, const EdgeAssociation&, bool> {
  40     public:
  41       inline lessEdgeAssociation() {}
  42       inline bool operator () (const EdgeAssociation& elem1, const EdgeAssociation& elem2) const {
  43         if(elem1.first.first < elem2.first.first) return true;
  44         if(elem1.first.first > elem2.first.first) return false;
  45         return elem1.first.second < elem2.first.second;
  46       }
  47     };
  48
  49     template <class cT>
  50     static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient) {
  51       Interval rectIvl = node->rect.get(orient);
  52       if(node->tracedPath(rectIvl)) {
  53         return;
  54       }
  55       node->addPath(rectIvl);
  56       if(node->begin() == node->end()) {
  57         //std::cout << "WRITE OUT 3: " << node->rect << std::endl;
  58         outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(node->rect));
  59         return;
  60       }
  61       bool writeOut = true;
  62       for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
  63         getMaxCover(outputContainer, *itr, orient, node->rect); //get rectangles down path
  64         Interval nodeIvl = (*itr)->rect.get(orient);
  65         if(contains(nodeIvl, rectIvl, true)) writeOut = false;
  66       }
  67       if(writeOut) {
  68         //std::cout << "WRITE OUT 2: " << node->rect << std::endl;
  69         outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(node->rect));
  70       }
  71     }
  72
  73     struct stack_element {
  74       inline stack_element() :
  75         node(), rect(), itr() {}
  76       inline stack_element(Node* n,
  77                            const Rectangle& r,
  78                            typename Node::iterator i) :
  79         node(n), rect(r), itr(i) {}
  80       Node* node;
  81       Rectangle rect;
  82       typename Node::iterator itr;
  83     };
  84
  85     template <class cT>
  86     static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient,
  87                                    Rectangle rect) {
  88       //std::cout << "New Root\n";
  89       std::vector<stack_element> stack;
  90       typename Node::iterator itr = node->begin();
  91       do {
  92         //std::cout << "LOOP\n";
  93         //std::cout << node->rect << std::endl;
  94         Interval rectIvl = rect.get(orient);
  95         Interval nodeIvl = node->rect.get(orient);
  96         bool iresult = intersect(rectIvl, nodeIvl, false);
  97         bool tresult = !node->tracedPath(rectIvl);
  98         //std::cout << (itr != node->end()) << " " << iresult << " " << tresult << std::endl;
  99         Rectangle nextRect1 = Rectangle(rectIvl, rectIvl);
 100         Unit low = rect.get(orient.get_perpendicular()).low();
 101         Unit high = node->rect.get(orient.get_perpendicular()).high();
 102         nextRect1.set(orient.get_perpendicular(), Interval(low, high));
 103         if(iresult && tresult) {
 104           node->addPath(rectIvl);
 105           bool writeOut = true;
 106           //check further visibility beyond this node
 107           for(typename Node::iterator itr2 = node->begin(); itr2 != node->end(); ++itr2) {
 108             Interval nodeIvl3 = (*itr2)->rect.get(orient);
 109             //if a child of this node can contain the interval then we can extend through
 110             if(contains(nodeIvl3, rectIvl, true)) writeOut = false;
 111             //std::cout << "child " << (*itr2)->rect << std::endl;
 112           }
 113           Rectangle nextRect2 = Rectangle(rectIvl, rectIvl);
 114           Unit low2 = rect.get(orient.get_perpendicular()).low();
 115           Unit high2 = node->rect.get(orient.get_perpendicular()).high();
 116           nextRect2.set(orient.get_perpendicular(), Interval(low2, high2));
 117           if(writeOut) {
 118             //std::cout << "write out " << nextRect << std::endl;
 119             outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect2));
 120           } else {
 121             //std::cout << "suppress " << nextRect << std::endl;
 122           }
 123         }
 124         if(itr != node->end() && iresult && tresult) {
 125           //std::cout << "recurse into child\n";
 126           stack.push_back(stack_element(node, rect, itr));
 127           rect = nextRect1;
 128           node = *itr;
 129           itr = node->begin();
 130         } else {
 131           if(!stack.empty()) {
 132             //std::cout << "recurse out of child\n";
 133             node = stack.back().node;
 134             rect = stack.back().rect;
 135             itr = stack.back().itr;
 136             stack.pop_back();
 137           } else {
 138             //std::cout << "empty stack\n";
 139             //if there were no children of the root node
 140 //             Rectangle nextRect = Rectangle(rectIvl, rectIvl);
 141 //             Unit low = rect.get(orient.get_perpendicular()).low();
 142 //             Unit high = node->rect.get(orient.get_perpendicular()).high();
 143 //             nextRect.set(orient.get_perpendicular(), Interval(low, high));
 144 //             outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect));
 145           }
 146           //std::cout << "increment " << (itr != node->end()) << std::endl;
 147           if(itr != node->end()) {
 148             ++itr;
 149             if(itr != node->end()) {
 150               //std::cout << "recurse into next child.\n";
 151               stack.push_back(stack_element(node, rect, itr));
 152               Interval rectIvl2 = rect.get(orient);
 153               Interval nodeIvl2 = node->rect.get(orient);
 154               /*bool iresult =*/ intersect(rectIvl2, nodeIvl2, false);
 155               Rectangle nextRect2 = Rectangle(rectIvl2, rectIvl2);
 156               Unit low2 = rect.get(orient.get_perpendicular()).low();
 157               Unit high2 = node->rect.get(orient.get_perpendicular()).high();
 158               nextRect2.set(orient.get_perpendicular(), Interval(low2, high2));
 159               rect = nextRect2;
 160               //std::cout << "rect for next child" << rect << std::endl;
 161               node = *itr;
 162               itr = node->begin();
 163             }
 164           }
 165         }
 166       } while(!stack.empty() || itr != node->end());
 167     }
 168
 169     /*  Function recursive version of getMaxCover
 170         Because the code is so much simpler than the loop algorithm I retain it for clarity
 171
 172     template <class cT>
 173     static inline void getMaxCover(cT& outputContainer, Node* node, orientation_2d orient,
 174                                    const Rectangle& rect) {
 175       Interval rectIvl = rect.get(orient);
 176       Interval nodeIvl = node->rect.get(orient);
 177       if(!intersect(rectIvl, nodeIvl, false)) {
 178         return;
 179       }
 180       if(node->tracedPath(rectIvl)) {
 181         return;
 182       }
 183       node->addPath(rectIvl);
 184       Rectangle nextRect(rectIvl, rectIvl);
 185       Unit low = rect.get(orient.get_perpendicular()).low();
 186       Unit high = node->rect.get(orient.get_perpendicular()).high();
 187       nextRect.set(orient.get_perpendicular(), Interval(low, high));
 188       bool writeOut = true;
 189       rectIvl = nextRect.get(orient);
 190       for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
 191         nodeIvl = (*itr)->rect.get(orient);
 192         if(contains(nodeIvl, rectIvl, true)) writeOut = false;
 193       }
 194       if(writeOut) {
 195         outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(nextRect));
 196       }
 197       for(typename Node::iterator itr = node->begin(); itr != node->end(); ++itr) {
 198         getMaxCover(outputContainer, *itr, orient, nextRect);
 199       }
 200     }
 201     */
 202
 203     //iterator range is assummed to be in topological order meaning all node's trailing
 204     //edges are in sorted order
 205     template <class iT>
 206     static inline void computeDag(iT beginNode, iT endNode, orientation_2d orient,
 207                                   std::size_t size) {
 208       std::vector<EdgeAssociation> leadingEdges;
 209       leadingEdges.reserve(size);
 210       for(iT iter = beginNode; iter != endNode; ++iter) {
 211         Node* nodep = &(*iter);
 212         Unit leading = nodep->rect.get(orient.get_perpendicular()).low();
 213         Interval rectIvl = nodep->rect.get(orient);
 214         leadingEdges.push_back(EdgeAssociation(std::pair<Unit, Interval>(leading, rectIvl), nodep));
 215       }
 216       polygon_sort(leadingEdges.begin(), leadingEdges.end(), lessEdgeAssociation());
 217       typename std::vector<EdgeAssociation>::iterator leadingBegin = leadingEdges.begin();
 218       iT trailingBegin = beginNode;
 219       while(leadingBegin != leadingEdges.end()) {
 220         EdgeAssociation& leadingSegment = (*leadingBegin);
 221         Unit trailing = (*trailingBegin).rect.get(orient.get_perpendicular()).high();
 222         Interval ivl = (*trailingBegin).rect.get(orient);
 223         std::pair<Unit, Interval> trailingSegment(trailing, ivl);
 224         if(leadingSegment.first.first < trailingSegment.first) {
 225           ++leadingBegin;
 226           continue;
 227         }
 228         if(leadingSegment.first.first > trailingSegment.first) {
 229           ++trailingBegin;
 230           continue;
 231         }
 232         if(leadingSegment.first.second.high() <= trailingSegment.second.low()) {
 233           ++leadingBegin;
 234           continue;
 235         }
 236         if(trailingSegment.second.high() <= leadingSegment.first.second.low()) {
 237           ++trailingBegin;
 238           continue;
 239         }
 240         //leading segment intersects trailing segment
 241         (*trailingBegin).add((*leadingBegin).second);
 242         if(leadingSegment.first.second.high() > trailingSegment.second.high()) {
 243           ++trailingBegin;
 244           continue;
 245         }
 246         if(trailingSegment.second.high() > leadingSegment.first.second.high()) {
 247           ++leadingBegin;
 248           continue;
 249         }
 250         ++leadingBegin;
 251         ++trailingBegin;
 252       }
 253     }
 254
 255     template <class cT>
 256     static inline void getMaxCover(cT& outputContainer,
 257                                    const std::vector<Rectangle>& rects, orientation_2d orient) {
 258       if(rects.empty()) return;
 259       std::vector<Node> nodes;
 260       {
 261         if(rects.size() == 1) {
 262           outputContainer.push_back(copy_construct<typename cT::value_type, Rectangle>(rects[0]));
 263           return;
 264         }
 265         nodes.reserve(rects.size());
 266         for(std::size_t i = 0; i < rects.size(); ++i) { nodes.push_back(Node(rects[i])); }
 267       }
 268       computeDag(nodes.begin(), nodes.end(), orient, nodes.size());
 269       for(std::size_t i = 0; i < nodes.size(); ++i) {
 270         getMaxCover(outputContainer, &(nodes[i]), orient);
 271       }
 272     }
 273
 274   };
 275 }
 276 }
 277
 278 #endif