/*
    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_FORMATION_HPP
#define BOOST_POLYGON_POLYGON_FORMATION_HPP
namespace boost { namespace polygon{

namespace polygon_formation {

  /*
   * End has two states, HEAD and TAIL as is represented by a bool
   */
  typedef bool End;

  /*
   * HEAD End is represented as false because it is the lesser state
   */
  const End HEAD = false;

  /*
   * TAIL End is represented by true because TAIL comes after head and 1 after 0
   */
  const End TAIL = true;
   
  /*
   * 2D turning direction, left and right sides (is a boolean value since it has two states.)
   */
  typedef bool Side;
   
  /*
   * LEFT Side is 0 because we inuitively think left to right; left < right
   */
  const Side LEFT = false;
   
  /*
   * RIGHT Side is 1 so that right > left
   */
  const Side RIGHT = true;

  /*
   * The PolyLine class is data storage and services for building and representing partial polygons.  
   * As the polyline is added to it extends its storage to accomodate the data.
   * PolyLines can be joined head-to-head/head-to-tail when it is determined that two polylines are
   * part of the same polygon.
   * PolyLines keep state information about what orientation their incomplete head and tail geometry have,
   * which side of the polyline is solid and whether the polyline is joined head-to-head and tail-to-head.
   * PolyLines have nothing whatsoever to do with holes.
   * It may be valuable to collect a histogram of PolyLine lengths used by an algorithm on its typical data
   * sets and tune the allocation of the initial vector of coordinate data to be greater than or equal to
   * the mean, median, mode, or mean plus some number of standard deviation, or just generally large enough
   * to prevent too much unnecesary reallocations, but not too big that it wastes a lot of memory and degrades cache
   * performance.
   */
  template <typename Unit>
  class PolyLine {
  private:
    //data
     
    /*
     * ptdata_ a vector of coordiantes
     * if VERTICAL_HEAD, first coordiante is an X
     * else first coordinate is a Y
     */
    std::vector<Unit> ptdata_;
   
    /*
     * head and tail points to other polylines before and after this in a chain
     */
    PolyLine* headp_;
    PolyLine* tailp_;
   
    /*
     * state bitmask
     * bit zero is orientation, 0 H, 1 V
     * bit 1 is head connectivity, 0 for head, 1 for tail
     * bit 2 is tail connectivity, 0 for head, 1 for tail
     * bit 3 is solid to left of PolyLine when 1, right when 0
     */
    int state_;
   
  public:
    /*
     * default constructor (for preallocation)
     */
    PolyLine();
   
    /*
     * constructor that takes the orientation, coordiante and side to which there is solid
     */
    PolyLine(orientation_2d orient, Unit coord, Side side);
   
    //copy constructor
    PolyLine(const PolyLine& pline);
   
    //destructor
    ~PolyLine();
   
    //assignment operator
    PolyLine& operator=(const PolyLine& that);

    //equivalence operator
    bool operator==(const PolyLine& b) const;

    /*
     * valid PolyLine (only default constructed polylines are invalid.)
     */
    bool isValid() const;

    /*
     * Orientation of Head
     */
    orientation_2d headOrient() const;

    /*
     * returns true if first coordinate is an X value (first segment is vertical)
     */
    bool verticalHead() const; 

    /*
     * returns the orientation_2d fo the tail
     */
    orientation_2d tailOrient() const;
      
    /*
     * returns true if last coordinate is an X value (last segment is vertical)
     */
    bool verticalTail() const;
     
    /*
     * retrun true if PolyLine has odd number of coordiantes
     */
    bool oddLength() const;

    /*
     * retrun the End of the other polyline that the specified end of this polyline is connected to
     */
    End endConnectivity(End end) const;

    /*
     * retrun true if the head of this polyline is connect to the tail of a polyline
     */
    bool headToTail() const;
    /*
     * retrun true if the head of this polyline is connect to the head of a polyline
     */
    bool headToHead() const;

    /*
     * retrun true if the tail of this polyline is connect to the tail of a polyline
     */
    bool tailToTail() const;
    /*
     * retrun true if the tail of this polyline is connect to the head of a polyline
     */
    bool tailToHead() const;
     
    /*
     * retrun the side on which there is solid for this polyline
     */
    Side solidSide() const;

    /*
     * retrun true if there is solid to the right of this polyline
     */
    bool solidToRight() const;

    /*
     * returns true if the polyline tail is not connected
     */
    bool active() const;

    /*
     * adds a coordinate value to the end of the polyline changing the tail orientation
     */
    PolyLine& pushCoordinate(Unit coord);
       
    /*
     * removes a coordinate value at the end of the polyline changing the tail orientation
     */
    PolyLine& popCoordinate();
      
    /*
     * extends the tail of the polyline to include the point, changing orientation if needed
     */
    PolyLine& pushPoint(const point_data<Unit>& point);

    /*
     * changes the last coordinate of the tail of the polyline by the amount of the delta
     */
    PolyLine& extendTail(Unit delta);

    /*
     * join thisEnd of this polyline to that polyline's end
     */
    PolyLine& joinTo(End thisEnd, PolyLine& that, End end);

    /*
     * join an end of this polyline to the tail of that polyline
     */
    PolyLine& joinToTail(PolyLine& that, End end);

    /*
     * join an end of this polyline to the head of that polyline
     */
    PolyLine& joinToHead(PolyLine& that, End end);

    /*
     * join the head of this polyline to the head of that polyline
     */
    //join this to that in the given way
    PolyLine& joinHeadToHead(PolyLine& that);

    /*
     * join the head of this polyline to the tail of that polyline
     */
    PolyLine& joinHeadToTail(PolyLine& that);

    /*
     * join the tail of this polyline to the head of that polyline
     */
    PolyLine& joinTailToHead(PolyLine& that);

    /*
     * join the tail of this polyline to the tail of that polyline
     */
    PolyLine& joinTailToTail(PolyLine& that);

    /*
     * dissconnect the tail at the end of the polygon
     */
    PolyLine& disconnectTails();

    /*
     * get the coordinate at one end of this polyline, by default the tail end
     */
    Unit getEndCoord(End end = TAIL) const;

    /*
     * get the point on the polyline at the given index (polylines have the same number of coordinates as points
     */
    point_data<Unit> getPoint(unsigned int index) const;

    /*
     * get the point on one end of the polyline, by default the tail
     */
    point_data<Unit> getEndPoint(End end = TAIL) const;

    /*
     * get the orientation of a segment by index
     */
    orientation_2d segmentOrient(unsigned int index = 0) const;

    /*
     * get a coordinate by index using the square bracket operator
     */
    Unit operator[] (unsigned int index) const;

    /*
     * get the number of segments/points/coordinates in the polyline
     */
    unsigned int numSegments() const;

    /*
     * get the pointer to the next polyline at one end of this
     */
    PolyLine* next(End end) const;

    /*
     * write out coordinates of this and all attached polylines to a single vector
     */
    PolyLine* writeOut(std::vector<Unit>& outVec, End startEnd = TAIL) const;

  private:
    //methods
    PolyLine& joinTo_(End thisEnd, PolyLine& that, End end);
  };

  //forward declaration
  template<bool orientT, typename Unit>
  class PolyLinePolygonData;

  //forward declaration
  template<bool orientT, typename Unit>
  class PolyLinePolygonWithHolesData;

  /*
   * ActiveTail represents an edge of an incomplete polygon.
   *
   * An ActiveTail object is the active tail end of a polyline object, which may (should) be the attached to
   * a chain of polyline objects through a pointer.  The ActiveTail class provides an abstraction between
   * and algorithm that builds polygons and the PolyLine data representation of incomplete polygons that are
   * being built.  It does this by providing an iterface to access the information about the last edge at the
   * tail of the PolyLine it is associated with.  To a polygon constructing algorithm, an ActiveTail is a floating
   * edge of an incomplete polygon and has an orientation and coordinate value, as well as knowing which side of
   * that edge is supposed to be solid or space.  Any incomplete polygon will have two active tails.  Active tails
   * may be joined together to merge two incomplete polygons into a larger incomplete polygon.  If two active tails
   * that are to be merged are the oppositve ends of the same incomplete polygon that indicates that the polygon
   * has been closed and is complete.  The active tail keeps a pointer to the other active tail of its incomplete 
   * polygon so that it is easy to check this condition.  These pointers are updated when active tails are joined.
   * The active tail also keeps a list of pointers to active tail objects that serve as handles to closed holes.  In
   * this way a hole can be associated to another incomplete polygon, which will eventually be its enclosing shell,
   * or reassociate the hole to another incomplete polygon in the case that it become a hole itself.  Alternately,
   * the active tail may add a filiment to stitch a hole into a shell and "fracture" the hole out of the interior
   * of a polygon.  The active tail maintains a static output buffer to temporarily write polygon data to when
   * it outputs a figure so that outputting a polygon does not require the allocation of a temporary buffer.  This
   * static buffer should be destroyed whenever the program determines that it won't need it anymore and would prefer to
   * release the memory it has allocated back to the system.
   */
  template <typename Unit>
  class ActiveTail {
  private:
    //data
    PolyLine<Unit>* tailp_; 
    ActiveTail *otherTailp_;
    std::list<ActiveTail*> holesList_;
  public:

    /*
     * iterator over coordinates of the figure
     */
    class iterator {
    private:
      const PolyLine<Unit>* pLine_;
      const PolyLine<Unit>* pLineEnd_;
      unsigned int index_;
      unsigned int indexEnd_;
      End startEnd_;
    public:
      inline iterator() : pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() {}
      inline iterator(const ActiveTail* at, bool isHole, orientation_2d orient) : 
        pLine_(), pLineEnd_(), index_(), indexEnd_(), startEnd_() {
        //if it is a hole and orientation is vertical or it is not a hole and orientation is horizontal
        //we want to use this active tail, otherwise we want to use the other active tail
        startEnd_ = TAIL;
        if(!isHole ^ (orient == HORIZONTAL)) {
          //switch winding direction
          at = at->getOtherActiveTail();
        }
        //now we have the right winding direction
        //if it is horizontal we need to skip the first element
        pLine_ = at->getTail();
        index_ = at->getTail()->numSegments() - 1;
        if((at->getOrient() == HORIZONTAL) ^ (orient == HORIZONTAL)) {
          pLineEnd_ = at->getTail();
          indexEnd_ = pLineEnd_->numSegments() - 1;
          if(index_ == 0) {
            pLine_ = at->getTail()->next(HEAD);
            if(at->getTail()->endConnectivity(HEAD) == TAIL) {
              index_ = pLine_->numSegments() -1;
            } else {
              startEnd_ = HEAD;
              index_ = 0;
            }
          } else { --index_; }
        } else {
          pLineEnd_ = at->getOtherActiveTail()->getTail();
          indexEnd_ = pLineEnd_->numSegments() - 1;
        }
        at->getTail()->joinTailToTail(*(at->getOtherActiveTail()->getTail()));
      }
      //use bitwise copy and assign provided by the compiler
      inline iterator& operator++() {
        if(pLine_ == pLineEnd_ && index_ == indexEnd_) {
          pLine_ = 0;
          index_ = 0;
          return *this;
        }
        if(startEnd_ == HEAD) {
          ++index_;
          if(index_ == pLine_->numSegments()) {
            End end = pLine_->endConnectivity(TAIL);
            pLine_ = pLine_->next(TAIL);
            if(end == TAIL) {
              startEnd_ = TAIL;
              index_ = pLine_->numSegments() -1;
            } else {
              index_ = 0;
            }
          }
        } else {
          if(index_ == 0) {
            End end = pLine_->endConnectivity(HEAD);
            pLine_ = pLine_->next(HEAD);
            if(end == TAIL) {
              index_ = pLine_->numSegments() -1;
            } else {
              startEnd_ = HEAD;
              index_ = 0;
            }
          } else {
            --index_;
          }
        }
        return *this;
      }
      inline const iterator operator++(int) {
        iterator tmp(*this);
        ++(*this);
        return tmp;
      }
      inline bool operator==(const iterator& that) const {
        return pLine_ == that.pLine_ && index_ == that.index_;
      }
      inline bool operator!=(const iterator& that) const {
        return pLine_ != that.pLine_ || index_ != that.index_;
      }
      inline Unit operator*() { return (*pLine_)[index_]; }
    };

    /*
     * iterator over holes contained within the figure
     */
    typedef typename std::list<ActiveTail*>::const_iterator iteratorHoles;

    //default constructor
    ActiveTail();

    //constructor
    ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp);

    //constructor
    ActiveTail(PolyLine<Unit>* active, ActiveTail* otherTailp);

    //copy constructor
    ActiveTail(const ActiveTail& that);

    //destructor
    ~ActiveTail();

    //assignment operator
    ActiveTail& operator=(const ActiveTail& that);

    //equivalence operator
    bool operator==(const ActiveTail& b) const;

    /*
     * comparison operators, ActiveTail objects are sortable by geometry
     */
    bool operator<(const ActiveTail& b) const;
    bool operator<=(const ActiveTail& b) const;
    bool operator>(const ActiveTail& b) const;
    bool operator>=(const ActiveTail& b) const;

    /*
     * get the pointer to the polyline that this is an active tail of
     */
    PolyLine<Unit>* getTail() const;

    /*
     * get the pointer to the polyline at the other end of the chain
     */
    PolyLine<Unit>* getOtherTail() const;

    /*
     * get the pointer to the activetail at the other end of the chain
     */
    ActiveTail* getOtherActiveTail() const;

    /*
     * test if another active tail is the other end of the chain
     */
    bool isOtherTail(const ActiveTail& b);

    /*
     * update this end of chain pointer to new polyline
     */
    ActiveTail& updateTail(PolyLine<Unit>* newTail);

    /*
     * associate a hole to this active tail by the specified policy
     */
    ActiveTail* addHole(ActiveTail* hole, bool fractureHoles);

    /*
     * get the list of holes
     */
    const std::list<ActiveTail*>& getHoles() const;

    /*
     * copy holes from that to this
     */
    void copyHoles(ActiveTail& that);

    /*
     * find out if solid to right
     */
    bool solidToRight() const;

    /*
     * get coordinate (getCoord and getCoordinate are aliases for eachother)
     */
    Unit getCoord() const;
    Unit getCoordinate() const;

    /*
     * get the tail orientation
     */
    orientation_2d getOrient() const;

    /*
     * add a coordinate to the polygon at this active tail end, properly handle degenerate edges by removing redundant coordinate
     */
    void pushCoordinate(Unit coord);

    /*
     * write the figure that this active tail points to out to the temp buffer
     */
    void writeOutFigure(std::vector<Unit>& outVec, bool isHole = false) const;

    /*
     * write the figure that this active tail points to out through iterators
     */
    void writeOutFigureItrs(iterator& beginOut, iterator& endOut, bool isHole = false, orientation_2d orient = VERTICAL) const;
    iterator begin(bool isHole, orientation_2d orient) const;
    iterator end() const;

    /*
     * write the holes that this active tail points to out through iterators
     */
    void writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const;
    iteratorHoles beginHoles() const;
    iteratorHoles endHoles() const;

    /*
     * joins the two chains that the two active tail tails are ends of
     * checks for closure of figure and writes out polygons appropriately
     * returns a handle to a hole if one is closed
     */
    static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, std::vector<Unit>& outBufferTmp);
    template <typename PolygonT>
    static ActiveTail* joinChains(ActiveTail* at1, ActiveTail* at2, bool solid, typename std::vector<PolygonT>& outBufferTmp);

    /*
     * deallocate temp buffer
     */
    static void destroyOutBuffer();

    /*
     * deallocate all polygon data this active tail points to (deep delete, call only from one of a pair of active tails)
     */
    void destroyContents();
  };

  /* allocate a polyline object */
  template <typename Unit>
  PolyLine<Unit>* createPolyLine(orientation_2d orient, Unit coord, Side side);

  /* deallocate a polyline object */
  template <typename Unit>
  void destroyPolyLine(PolyLine<Unit>* pLine);

  /* allocate an activetail object */
  template <typename Unit>
  ActiveTail<Unit>* createActiveTail();

  /* deallocate an activetail object */
  template <typename Unit>
  void destroyActiveTail(ActiveTail<Unit>* aTail);
     
  template<bool orientT, typename Unit>
  class PolyLineHoleData {
  private:
    ActiveTail<Unit>* p_;
  public:
    typedef Unit coordinate_type;
    typedef typename ActiveTail<Unit>::iterator compact_iterator_type;
    typedef iterator_compact_to_points<compact_iterator_type, point_data<coordinate_type> > iterator_type;
    inline PolyLineHoleData() : p_(0) {}
    inline PolyLineHoleData(ActiveTail<Unit>* p) : p_(p) {}
    //use default copy and assign
    inline compact_iterator_type begin_compact() const { return p_->begin(true, (orientT ? VERTICAL : HORIZONTAL)); }
    inline compact_iterator_type end_compact() const { return p_->end(); }
    inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); }
    inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); }
    inline std::size_t size() const { return 0; }
    inline ActiveTail<Unit>* yield() { return p_; }
    template<class iT>
    inline PolyLineHoleData& set(iT inputBegin, iT inputEnd) {
      return *this;
    }
    template<class iT>
    inline PolyLineHoleData& set_compact(iT inputBegin, iT inputEnd) {
      return *this;
    }
   
  };

  template<bool orientT, typename Unit>
  class PolyLinePolygonWithHolesData {
  private:
    ActiveTail<Unit>* p_;
  public:
    typedef Unit coordinate_type;
    typedef typename ActiveTail<Unit>::iterator compact_iterator_type;
    typedef iterator_compact_to_points<compact_iterator_type, point_data<coordinate_type> > iterator_type;
    typedef PolyLineHoleData<orientT, Unit> hole_type;
    typedef typename coordinate_traits<Unit>::area_type area_type;
    class iteratorHoles {
    private:
      typename ActiveTail<Unit>::iteratorHoles itr_;
    public:
      inline iteratorHoles() : itr_() {}
      inline iteratorHoles(typename ActiveTail<Unit>::iteratorHoles itr) : itr_(itr) {}
      //use bitwise copy and assign provided by the compiler
      inline iteratorHoles& operator++() {
        ++itr_;
        return *this;
      }
      inline const iteratorHoles operator++(int) {
        iteratorHoles tmp(*this);
        ++(*this);
        return tmp;
      }
      inline bool operator==(const iteratorHoles& that) const {
        return itr_ == that.itr_;
      }
      inline bool operator!=(const iteratorHoles& that) const {
        return itr_ != that.itr_;
      }
      inline PolyLineHoleData<orientT, Unit> operator*() { return PolyLineHoleData<orientT, Unit>(*itr_);}
    };
    typedef iteratorHoles iterator_holes_type;

    inline PolyLinePolygonWithHolesData() : p_(0) {}
    inline PolyLinePolygonWithHolesData(ActiveTail<Unit>* p) : p_(p) {}
    //use default copy and assign
    inline compact_iterator_type begin_compact() const { return p_->begin(false, (orientT ? VERTICAL : HORIZONTAL)); }
    inline compact_iterator_type end_compact() const { return p_->end(); }
    inline iterator_type begin() const { return iterator_type(begin_compact(), end_compact()); }
    inline iterator_type end() const { return iterator_type(end_compact(), end_compact()); }
    inline iteratorHoles begin_holes() const { return iteratorHoles(p_->beginHoles()); }
    inline iteratorHoles end_holes() const { return iteratorHoles(p_->endHoles()); }
    inline ActiveTail<Unit>* yield() { return p_; }
    //stub out these four required functions that will not be used but are needed for the interface
    inline std::size_t size_holes() const { return 0; }
    inline std::size_t size() const { return 0; }
    template<class iT>
    inline PolyLinePolygonWithHolesData& set(iT inputBegin, iT inputEnd) {
      return *this;
    }
    template<class iT>
    inline PolyLinePolygonWithHolesData& set_compact(iT inputBegin, iT inputEnd) {
      return *this;
    }
   
    // initialize a polygon from x,y values, it is assumed that the first is an x
    // and that the input is a well behaved polygon
    template<class iT>
    inline PolyLinePolygonWithHolesData& set_holes(iT inputBegin, iT inputEnd) {
      return *this;
    }
  };


  template <bool orientT, typename Unit, typename polygon_concept_type>
  struct PolyLineType { };
  template <bool orientT, typename Unit>
  struct PolyLineType<orientT, Unit, polygon_90_with_holes_concept> { typedef PolyLinePolygonWithHolesData<orientT, Unit> type; };
  template <bool orientT, typename Unit>
  struct PolyLineType<orientT, Unit, polygon_45_with_holes_concept> { typedef PolyLinePolygonWithHolesData<orientT, Unit> type; };
  template <bool orientT, typename Unit>
  struct PolyLineType<orientT, Unit, polygon_with_holes_concept> { typedef PolyLinePolygonWithHolesData<orientT, Unit> type; };
  template <bool orientT, typename Unit>
  struct PolyLineType<orientT, Unit, polygon_90_concept> { typedef PolyLineHoleData<orientT, Unit> type; };
  template <bool orientT, typename Unit>
  struct PolyLineType<orientT, Unit, polygon_45_concept> { typedef PolyLineHoleData<orientT, Unit> type; };
  template <bool orientT, typename Unit>
  struct PolyLineType<orientT, Unit, polygon_concept> { typedef PolyLineHoleData<orientT, Unit> type; };

  template <bool orientT, typename Unit, typename polygon_concept_type>
  class ScanLineToPolygonItrs {
  private:
    std::map<Unit, ActiveTail<Unit>*> tailMap_;
    typedef typename PolyLineType<orientT, Unit, polygon_concept_type>::type PolyLinePolygonData;
    std::vector<PolyLinePolygonData> outputPolygons_;
    bool fractureHoles_;
  public:
    typedef typename std::vector<PolyLinePolygonData>::iterator iterator; 
    inline ScanLineToPolygonItrs() : tailMap_(), outputPolygons_(), fractureHoles_(false)  {}
    /* construct a scanline with the proper offsets, protocol and options */
    inline ScanLineToPolygonItrs(bool fractureHoles) : tailMap_(), outputPolygons_(), fractureHoles_(fractureHoles) {}
   
    ~ScanLineToPolygonItrs() { clearOutput_(); }
   
    /* process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */
    void processEdges(iterator& beginOutput, iterator& endOutput, 
                      Unit currentX, std::vector<interval_data<Unit> >& leftEdges, 
                      std::vector<interval_data<Unit> >& rightEdges);
   
  private:
    void clearOutput_();
  };

  /*
   * ScanLine does all the work of stitching together polygons from incoming vertical edges
   */
//   template <typename Unit, typename polygon_concept_type>
//   class ScanLineToPolygons {
//   private:
//     ScanLineToPolygonItrs<true, Unit> scanline_;
//   public:
//     inline ScanLineToPolygons() : scanline_() {}
//     /* construct a scanline with the proper offsets, protocol and options */
//     inline ScanLineToPolygons(bool fractureHoles) : scanline_(fractureHoles) {}
   
//     /* process all vertical edges, left and right, at a unique x coordinate, edges must be sorted low to high */
//     inline void processEdges(std::vector<Unit>& outBufferTmp, Unit currentX, std::vector<interval_data<Unit> >& leftEdges, 
//                              std::vector<interval_data<Unit> >& rightEdges) {
//       typename ScanLineToPolygonItrs<true, Unit>::iterator itr, endItr;
//       scanline_.processEdges(itr, endItr, currentX, leftEdges, rightEdges);
//       //copy data into outBufferTmp
//       while(itr != endItr) {
//         typename PolyLinePolygonData<true, Unit>::iterator pditr;
//         outBufferTmp.push_back(0);
//         unsigned int sizeIndex = outBufferTmp.size() - 1;
//         int count = 0;
//         for(pditr = (*itr).begin(); pditr != (*itr).end(); ++pditr) {
//           outBufferTmp.push_back(*pditr);
//           ++count;
//         }
//         outBufferTmp[sizeIndex] = count;
//         typename PolyLinePolygonData<true, Unit>::iteratorHoles pdHoleItr;
//         for(pdHoleItr = (*itr).beginHoles(); pdHoleItr != (*itr).endHoles(); ++pdHoleItr) {
//           outBufferTmp.push_back(0);
//           unsigned int sizeIndex2 = outBufferTmp.size() - 1;
//           int count2 = 0;
//           for(pditr = (*pdHoleItr).begin(); pditr != (*pdHoleItr).end(); ++pditr) {
//             outBufferTmp.push_back(*pditr);
//             ++count2;
//           }
//           outBufferTmp[sizeIndex2] = -count;
//         }
//         ++itr;
//       }
//     }
//   };

  const int VERTICAL_HEAD = 1, HEAD_TO_TAIL = 2, TAIL_TO_TAIL = 4, SOLID_TO_RIGHT = 8;

  //EVERY FUNCTION in this DEF file should be explicitly defined as inline

  //microsoft compiler improperly warns whenever you cast an integer to bool
  //call this function on an integer to convert it to bool without a warning
  template <class T>
  inline bool to_bool(const T& val) { return val != 0; }

  //default constructor (for preallocation)
  template <typename Unit>
  inline PolyLine<Unit>::PolyLine() : ptdata_() ,headp_(0), tailp_(0), state_(-1) {}

  //constructor
  template <typename Unit>
  inline PolyLine<Unit>::PolyLine(orientation_2d orient, Unit coord, Side side) : 
    ptdata_(1, coord),
    headp_(0),
    tailp_(0),
    state_(orient.to_int() +
           (side << 3)) {}

  //copy constructor
  template <typename Unit>
  inline PolyLine<Unit>::PolyLine(const PolyLine<Unit>& pline) : ptdata_(pline.ptdata_),
                                                     headp_(pline.headp_),
                                                     tailp_(pline.tailp_),
                                                     state_(pline.state_) {}

  //destructor
  template <typename Unit>
  inline PolyLine<Unit>::~PolyLine() {
    //clear out data just in case it is read later
    headp_ = tailp_ = 0;
    state_ = 0;
  }

  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::operator=(const PolyLine<Unit>& that) {
    if(!(this == &that)) {
      headp_ = that.headp_;
      tailp_ = that.tailp_;
      ptdata_ = that.ptdata_;
      state_ = that.state_;
    }
    return *this;
  }

  template <typename Unit>
  inline bool PolyLine<Unit>::operator==(const PolyLine<Unit>& b) const {
    return this == &b || (state_ == b.state_ &&
                          headp_ == b.headp_ &&
                          tailp_ == b.tailp_);
  }

  //valid PolyLine
  template <typename Unit>
  inline bool PolyLine<Unit>::isValid() const { 
    return state_ > -1; }

  //first coordinate is an X value
  //first segment is vertical
  template <typename Unit>
  inline bool PolyLine<Unit>::verticalHead() const {
    return state_ & VERTICAL_HEAD;
  }

  //retrun true is PolyLine has odd number of coordiantes
  template <typename Unit>
  inline bool PolyLine<Unit>::oddLength() const {
    return to_bool((ptdata_.size()-1) % 2);
  }

  //last coordiante is an X value
  //last segment is vertical
  template <typename Unit>
  inline bool PolyLine<Unit>::verticalTail() const {
    return to_bool(verticalHead() ^ oddLength());
  }
     
  template <typename Unit>
  inline orientation_2d PolyLine<Unit>::tailOrient() const {
    return (verticalTail() ? VERTICAL : HORIZONTAL);
  }

  template <typename Unit>
  inline orientation_2d PolyLine<Unit>::headOrient() const {
    return (verticalHead() ? VERTICAL : HORIZONTAL);
  }

  template <typename Unit>
  inline End PolyLine<Unit>::endConnectivity(End end) const {
    //Tail should be defined as true
    if(end) { return tailToTail(); }
    return headToTail();
  }

  template <typename Unit>
  inline bool PolyLine<Unit>::headToTail() const {
    return to_bool(state_ & HEAD_TO_TAIL);
  }

  template <typename Unit>
  inline bool PolyLine<Unit>::headToHead() const {
    return to_bool(!headToTail());
  }

  template <typename Unit>
  inline bool PolyLine<Unit>::tailToHead() const {
    return to_bool(!tailToTail());
  }
     
  template <typename Unit>
  inline bool PolyLine<Unit>::tailToTail() const {
    return to_bool(state_ & TAIL_TO_TAIL);
  }

  template <typename Unit>
  inline Side PolyLine<Unit>::solidSide() const { 
    return solidToRight(); }
      
  template <typename Unit>
  inline bool PolyLine<Unit>::solidToRight() const {
    return to_bool(state_ & SOLID_TO_RIGHT) != 0;
  }

  template <typename Unit>
  inline bool PolyLine<Unit>::active() const {
    return !to_bool(tailp_);
  }

  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::pushCoordinate(Unit coord) {
    ptdata_.push_back(coord);
    return *this;
  }

  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::popCoordinate() {
    ptdata_.pop_back();
    return *this;
  }

  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::pushPoint(const point_data<Unit>& point) {
    point_data<Unit> endPt = getEndPoint();
    //vertical is true, horizontal is false
    if((tailOrient().to_int() ? point.get(VERTICAL) == endPt.get(VERTICAL) : point.get(HORIZONTAL) == endPt.get(HORIZONTAL))) {
      //we were pushing a colinear segment
      return popCoordinate();
    }
    return pushCoordinate(tailOrient().to_int() ? point.get(VERTICAL) : point.get(HORIZONTAL));
  }

  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::extendTail(Unit delta) {
    ptdata_.back() += delta;
    return *this;
  }

  //private member function that creates a link from this PolyLine to that
  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::joinTo_(End thisEnd, PolyLine<Unit>& that, End end) {
    if(thisEnd){
      tailp_ = &that;
      state_ &= ~TAIL_TO_TAIL; //clear any previous state_ of bit (for safety)
      state_ |= (end << 2); //place bit into mask
    } else {
      headp_ = &that;
      state_ &= ~HEAD_TO_TAIL; //clear any previous state_ of bit (for safety)
      state_ |= (end << 1); //place bit into mask
    }
    return *this;
  }

  //join two PolyLines (both ways of the association)
  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::joinTo(End thisEnd, PolyLine<Unit>& that, End end) {
    joinTo_(thisEnd, that, end);
    that.joinTo_(end, *this, thisEnd);
    return *this;
  }

  //convenience functions for joining PolyLines
  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::joinToTail(PolyLine<Unit>& that, End end) {
    return joinTo(TAIL, that, end);
  }
  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::joinToHead(PolyLine<Unit>& that, End end) {
    return joinTo(HEAD, that, end);
  }
  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::joinHeadToHead(PolyLine<Unit>& that) {
    return joinToHead(that, HEAD);
  }
  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::joinHeadToTail(PolyLine<Unit>& that) {
    return joinToHead(that, TAIL);
  }
  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::joinTailToHead(PolyLine<Unit>& that) {
    return joinToTail(that, HEAD);
  }
  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::joinTailToTail(PolyLine<Unit>& that) {
    return joinToTail(that, TAIL);
  }

  template <typename Unit>
  inline PolyLine<Unit>& PolyLine<Unit>::disconnectTails() {
    next(TAIL)->state_ &= !TAIL_TO_TAIL;
    next(TAIL)->tailp_ = 0;
    state_ &= !TAIL_TO_TAIL;
    tailp_ = 0;
    return *this;
  }

  template <typename Unit>
  inline Unit PolyLine<Unit>::getEndCoord(End end) const {
    if(end)
      return ptdata_.back();
    return ptdata_.front();
  }

  template <typename Unit>
  inline orientation_2d PolyLine<Unit>::segmentOrient(unsigned int index) const {
    return (to_bool((unsigned int)verticalHead() ^ (index % 2)) ? VERTICAL : HORIZONTAL);
  }

  template <typename Unit>
  inline point_data<Unit> PolyLine<Unit>::getPoint(unsigned int index) const {
    //assert(isValid() && headp_->isValid()) ("PolyLine: headp_ must be valid");
    point_data<Unit> pt;
    pt.set(HORIZONTAL, ptdata_[index]);
    pt.set(VERTICAL, ptdata_[index]);
    Unit prevCoord;
    if(index == 0) {
      prevCoord = headp_->getEndCoord(headToTail());
    } else {
      prevCoord = ptdata_[index-1];
    }
    pt.set(segmentOrient(index), prevCoord);
    return pt;
  }

  template <typename Unit>
  inline point_data<Unit> PolyLine<Unit>::getEndPoint(End end) const {
    return getPoint((end ? numSegments() - 1 : (unsigned int)0));
  }

  template <typename Unit>
  inline Unit PolyLine<Unit>::operator[] (unsigned int index) const {
    //assert(ptdata_.size() > index) ("PolyLine: out of bounds index");
    return ptdata_[index];
  }

  template <typename Unit>
  inline unsigned int PolyLine<Unit>::numSegments() const {
    return ptdata_.size();
  }

  template <typename Unit>
  inline PolyLine<Unit>* PolyLine<Unit>::next(End end) const {
    return (end ? tailp_ : headp_);
  }

  template <typename Unit>
  inline ActiveTail<Unit>::ActiveTail() : tailp_(0), otherTailp_(0), holesList_() {}

  template <typename Unit>
  inline ActiveTail<Unit>::ActiveTail(orientation_2d orient, Unit coord, Side solidToRight, ActiveTail* otherTailp) : 
    tailp_(0), otherTailp_(0), holesList_() {
    tailp_ = createPolyLine(orient, coord, solidToRight);
    otherTailp_ = otherTailp;
  }

  template <typename Unit>
  inline ActiveTail<Unit>::ActiveTail(PolyLine<Unit>* active, ActiveTail<Unit>* otherTailp) : 
    tailp_(active), otherTailp_(otherTailp), holesList_() {}

  //copy constructor
  template <typename Unit>
  inline ActiveTail<Unit>::ActiveTail(const ActiveTail<Unit>& that) : tailp_(that.tailp_), otherTailp_(that.otherTailp_), holesList_() {}

  //destructor
  template <typename Unit>
  inline ActiveTail<Unit>::~ActiveTail() { 
    //clear them in case the memory is read later
    tailp_ = 0; otherTailp_ = 0; 
  }

  template <typename Unit>
  inline ActiveTail<Unit>& ActiveTail<Unit>::operator=(const ActiveTail<Unit>& that) {
    //self assignment is safe in this case
    tailp_ = that.tailp_;
    otherTailp_ = that.otherTailp_;
    return *this;
  }

  template <typename Unit>
  inline bool ActiveTail<Unit>::operator==(const ActiveTail<Unit>& b) const {
    return tailp_ == b.tailp_ && otherTailp_ == b.otherTailp_;
  }

  template <typename Unit>
  inline bool ActiveTail<Unit>::operator<(const ActiveTail<Unit>& b) const {
    return tailp_->getEndPoint().get(VERTICAL) < b.tailp_->getEndPoint().get(VERTICAL);
  }

  template <typename Unit>
  inline bool ActiveTail<Unit>::operator<=(const ActiveTail<Unit>& b) const { 
    return !(*this > b); }
   
  template <typename Unit>
  inline bool ActiveTail<Unit>::operator>(const ActiveTail<Unit>& b) const { 
    return b < (*this); }
   
  template <typename Unit>
  inline bool ActiveTail<Unit>::operator>=(const ActiveTail<Unit>& b) const { 
    return !(*this < b); }

  template <typename Unit>
  inline PolyLine<Unit>* ActiveTail<Unit>::getTail() const { 
    return tailp_; }

  template <typename Unit>
  inline PolyLine<Unit>* ActiveTail<Unit>::getOtherTail() const { 
    return otherTailp_->tailp_; }

  template <typename Unit>
  inline ActiveTail<Unit>* ActiveTail<Unit>::getOtherActiveTail() const { 
    return otherTailp_; }

  template <typename Unit>
  inline bool ActiveTail<Unit>::isOtherTail(const ActiveTail<Unit>& b) {
    //       assert( (tailp_ == b.getOtherTail() && getOtherTail() == b.tailp_) ||
    //                     (tailp_ != b.getOtherTail() && getOtherTail() != b.tailp_)) 
    //         ("ActiveTail: Active tails out of sync");
    return otherTailp_ == &b;
  }

  template <typename Unit>
  inline ActiveTail<Unit>& ActiveTail<Unit>::updateTail(PolyLine<Unit>* newTail) {
    tailp_ = newTail;
    return *this;
  }

  template <typename Unit>
  inline ActiveTail<Unit>* ActiveTail<Unit>::addHole(ActiveTail<Unit>* hole, bool fractureHoles) {
    if(!fractureHoles){
      holesList_.push_back(hole);
      copyHoles(*hole);
      copyHoles(*(hole->getOtherActiveTail()));
      return this;
    }
    ActiveTail<Unit>* h, *v;
    ActiveTail<Unit>* other = hole->getOtherActiveTail();
    if(other->getOrient() == VERTICAL) {
      //assert that hole.getOrient() == HORIZONTAL
      //this case should never happen
      h = hole;  
      v = other;
    } else {
      //assert that hole.getOrient() == VERTICAL
      h = other;
      v = hole;
    }
    h->pushCoordinate(v->getCoordinate());
    //assert that h->getOrient() == VERTICAL
    //v->pushCoordinate(getCoordinate());
    //assert that v->getOrient() == VERTICAL
    //I can't close a figure by adding a hole, so pass zero for xMin and yMin
    std::vector<Unit> tmpVec;
    ActiveTail<Unit>::joinChains(this, h, false, tmpVec);
    return v;
  }

  template <typename Unit>
  inline const std::list<ActiveTail<Unit>*>& ActiveTail<Unit>::getHoles() const {
    return holesList_;
  }

  template <typename Unit>
  inline void ActiveTail<Unit>::copyHoles(ActiveTail<Unit>& that) {
    holesList_.splice(holesList_.end(), that.holesList_); //splice the two lists together
  }

  template <typename Unit>
  inline bool ActiveTail<Unit>::solidToRight() const { 
    return getTail()->solidToRight(); }

  template <typename Unit>
  inline Unit ActiveTail<Unit>::getCoord() const { 
    return getTail()->getEndCoord(); }
 
  template <typename Unit>
  inline Unit ActiveTail<Unit>::getCoordinate() const { 
    return getCoord(); } 

  template <typename Unit>
  inline orientation_2d ActiveTail<Unit>::getOrient() const { 
    return getTail()->tailOrient(); }

  template <typename Unit>
  inline void ActiveTail<Unit>::pushCoordinate(Unit coord) { 
    //appropriately handle any co-linear polyline segments by calling push point internally
    point_data<Unit> p;
    p.set(HORIZONTAL, coord);
    p.set(VERTICAL, coord);
    //if we are vertical assign the last coordinate (an X) to p.x, else to p.y
    p.set(getOrient().get_perpendicular(), getCoordinate());
    tailp_->pushPoint(p);
  }


  //global utility functions
  template <typename Unit>
  inline PolyLine<Unit>* createPolyLine(orientation_2d orient, Unit coord, Side side) {
    return new PolyLine<Unit>(orient, coord, side);
  }

  template <typename Unit>
  inline void destroyPolyLine(PolyLine<Unit>* pLine) {
    delete pLine;
  }

  template <typename Unit>
  inline ActiveTail<Unit>* createActiveTail() {
    //consider replacing system allocator with ActiveTail memory pool
    return new ActiveTail<Unit>();
  }

  template <typename Unit>
  inline void destroyActiveTail(ActiveTail<Unit>* aTail) {
    delete aTail;
  }


  //no recursion, to prevent max recursion depth errors
  template <typename Unit>
  inline void ActiveTail<Unit>::destroyContents() {
    tailp_->disconnectTails();
    PolyLine<Unit>* nextPolyLinep = tailp_->next(HEAD);
    End end = tailp_->endConnectivity(HEAD);
    destroyPolyLine(tailp_);
    while(nextPolyLinep) {
      End nextEnd = nextPolyLinep->endConnectivity(!end); //get the direction of next polyLine
      PolyLine<Unit>* nextNextPolyLinep = nextPolyLinep->next(!end); //get the next polyline
      destroyPolyLine(nextPolyLinep); //destroy the current polyline
      end = nextEnd;
      nextPolyLinep = nextNextPolyLinep;
    }
  }

  template <typename Unit>
  inline typename ActiveTail<Unit>::iterator ActiveTail<Unit>::begin(bool isHole, orientation_2d orient) const {
    return iterator(this, isHole, orient);
  }

  template <typename Unit>
  inline typename ActiveTail<Unit>::iterator ActiveTail<Unit>::end() const {
    return iterator();
  }

  template <typename Unit>
  inline typename ActiveTail<Unit>::iteratorHoles ActiveTail<Unit>::beginHoles() const {
    return holesList_.begin();
  }

  template <typename Unit>
  inline typename ActiveTail<Unit>::iteratorHoles ActiveTail<Unit>::endHoles() const {
    return holesList_.end();
  }

  template <typename Unit>
  inline void ActiveTail<Unit>::writeOutFigureItrs(iterator& beginOut, iterator& endOut, bool isHole, orientation_2d orient) const {
    beginOut = begin(isHole, orient);
    endOut = end();
  }

  template <typename Unit>
  inline void ActiveTail<Unit>::writeOutFigureHoleItrs(iteratorHoles& beginOut, iteratorHoles& endOut) const {
    beginOut = beginHoles();
    endOut = endHoles();
  }

  template <typename Unit>
  inline void ActiveTail<Unit>::writeOutFigure(std::vector<Unit>& outVec, bool isHole) const {
    //we start writing out the polyLine that this active tail points to at its tail
    std::size_t size = outVec.size();
    outVec.push_back(0); //place holder for size
    PolyLine<Unit>* nextPolyLinep = 0;
    if(!isHole){
      nextPolyLinep = otherTailp_->tailp_->writeOut(outVec);
    } else {
      nextPolyLinep = tailp_->writeOut(outVec);
    }
    Unit firsty = outVec[size + 1];
    if((getOrient() == HORIZONTAL) ^ !isHole) {
      //our first coordinate is a y value, so we need to rotate it to the end
      typename std::vector<Unit>::iterator tmpItr = outVec.begin();
      tmpItr += size; 
      outVec.erase(++tmpItr); //erase the 2nd element
    }
    End startEnd = tailp_->endConnectivity(HEAD);
    if(isHole) startEnd = otherTailp_->tailp_->endConnectivity(HEAD);
    while(nextPolyLinep) {
      bool nextStartEnd = nextPolyLinep->endConnectivity(!startEnd);
      nextPolyLinep = nextPolyLinep->writeOut(outVec, startEnd); 
      startEnd = nextStartEnd;
    }      
    if((getOrient() == HORIZONTAL) ^ !isHole) {
      //we want to push the y value onto the end since we ought to have ended with an x
      outVec.push_back(firsty); //should never be executed because we want first value to be an x
    }
    //the vector contains the coordinates of the linked list of PolyLines in the correct order
    //first element is supposed to be the size
    outVec[size] = outVec.size() - 1 - size;  //number of coordinates in vector
    //assert outVec[size] % 2 == 0 //it should be even
    //make the size negative for holes
    outVec[size] *= (isHole ? -1 : 1);
  }

  //no recursion to prevent max recursion depth errors
  template <typename Unit>
  inline PolyLine<Unit>* PolyLine<Unit>::writeOut(std::vector<Unit>& outVec, End startEnd) const {
    if(startEnd == HEAD){
      //forward order
      outVec.insert(outVec.end(), ptdata_.begin(), ptdata_.end());
      return tailp_;
    }else{
      //reverse order
      //do not reserve because we expect outVec to be large enough already
      for(int i = ptdata_.size() - 1; i >= 0; --i){
        outVec.push_back(ptdata_[i]);
      }
      //NT didn't know about this version of the API....
      //outVec.insert(outVec.end(), ptdata_.rbegin(), ptdata_.rend());
      return headp_;
    }
  }

  //solid indicates if it was joined by a solit or a space
  template <typename Unit>
  inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, std::vector<Unit>& outBufferTmp) 
  {
    //checks to see if we closed a figure
    if(at1->isOtherTail(*at2)){
      //value of solid tells us if we closed solid or hole
      //and output the solid or handle the hole appropriately
      //if the hole needs to fracture across horizontal partition boundary we need to notify
      //the calling context to do so
      if(solid) {
        //the chains are being joined because there is solid to the right
        //this means that if the figure is closed at this point it must be a hole
        //because otherwise it would have to have another vertex to the right of this one
        //and would not be closed at this point
        return at1;
      } else {    
        //assert pG != 0
        //the figure that was closed is a shell
        at1->writeOutFigure(outBufferTmp);
        //process holes of the polygon
        at1->copyHoles(*at2); //there should not be holes on at2, but if there are, copy them over
        const std::list<ActiveTail<Unit>*>& holes = at1->getHoles();
        for(typename std::list<ActiveTail<Unit>*>::const_iterator litr = holes.begin(); litr != holes.end(); ++litr) {
          (*litr)->writeOutFigure(outBufferTmp, true);
          //delete the hole
          (*litr)->destroyContents();
          destroyActiveTail((*litr)->getOtherActiveTail());
          destroyActiveTail((*litr));
        }
        //delete the polygon
        at1->destroyContents();
        //at2 contents are the same as at1, so it should not destroy them
        destroyActiveTail(at1);
        destroyActiveTail(at2);
      }
      return 0;
    }
    //join the two partial polygons into one large partial polygon
    at1->getTail()->joinTailToTail(*(at2->getTail()));
    *(at1->getOtherActiveTail()) = ActiveTail(at1->getOtherTail(), at2->getOtherActiveTail());
    *(at2->getOtherActiveTail()) = ActiveTail(at2->getOtherTail(), at1->getOtherActiveTail());
    at1->getOtherActiveTail()->copyHoles(*at1);
    at1->getOtherActiveTail()->copyHoles(*at2);
    destroyActiveTail(at1);
    destroyActiveTail(at2);
    return 0;
  }

  //solid indicates if it was joined by a solit or a space
  template <typename Unit>
  template <typename PolygonT>
  inline ActiveTail<Unit>* ActiveTail<Unit>::joinChains(ActiveTail<Unit>* at1, ActiveTail<Unit>* at2, bool solid, 
                                                        std::vector<PolygonT>& outBufferTmp) {
    //checks to see if we closed a figure
    if(at1->isOtherTail(*at2)){
      //value of solid tells us if we closed solid or hole
      //and output the solid or handle the hole appropriately
      //if the hole needs to fracture across horizontal partition boundary we need to notify
      //the calling context to do so
      if(solid) {
        //the chains are being joined because there is solid to the right
        //this means that if the figure is closed at this point it must be a hole
        //because otherwise it would have to have another vertex to the right of this one
        //and would not be closed at this point
        return at1;
      } else {    
        //assert pG != 0
        //the figure that was closed is a shell
        outBufferTmp.push_back(at1);
        at1->copyHoles(*at2); //there should not be holes on at2, but if there are, copy them over
      }
      return 0;
    }
    //join the two partial polygons into one large partial polygon
    at1->getTail()->joinTailToTail(*(at2->getTail()));
    *(at1->getOtherActiveTail()) = ActiveTail<Unit>(at1->getOtherTail(), at2->getOtherActiveTail());
    *(at2->getOtherActiveTail()) = ActiveTail<Unit>(at2->getOtherTail(), at1->getOtherActiveTail());
    at1->getOtherActiveTail()->copyHoles(*at1);
    at1->getOtherActiveTail()->copyHoles(*at2);
    destroyActiveTail(at1);
    destroyActiveTail(at2);
    return 0;
  }

  template <class TKey, class T> inline typename std::map<TKey, T>::iterator findAtNext(std::map<TKey, T>& theMap, 
                                                                                        typename std::map<TKey, T>::iterator pos, const TKey& key) 
  {
    if(pos == theMap.end()) return theMap.find(key);
    //if they match the mapItr is pointing to the correct position
    if(pos->first < key) {
      return theMap.find(key);
    }
    if(pos->first > key) {
      return theMap.end();
    } 
    //else they are equal and no need to do anything to the iterator
    return pos;
  }

  // createActiveTailsAsPair is called in these two end cases of geometry
  // 1. lower left concave corner
  //         ###| 
  //         ###|
  //         ###|### 
  //         ###|###
  // 2. lower left convex corner
  //            |###          
  //            |###         
  //            |            
  //            |     
  // In case 1 there may be a hole propigated up from the bottom.  If the fracture option is enabled
  // the two active tails that form the filament fracture line edges can become the new active tail pair
  // by pushing x and y onto them.  Otherwise the hole simply needs to be associated to one of the new active tails
  // with add hole
  template <typename Unit>
  inline std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> createActiveTailsAsPair(Unit x, Unit y, bool solid, ActiveTail<Unit>* phole, bool fractureHoles) {
    ActiveTail<Unit>* at1 = 0;
    ActiveTail<Unit>* at2 = 0;
    if(!phole || !fractureHoles){
      at1 = createActiveTail<Unit>();
      at2 = createActiveTail<Unit>();
      (*at1) = ActiveTail<Unit>(VERTICAL, x, solid, at2);
      (*at2) = ActiveTail<Unit>(HORIZONTAL, y, !solid, at1);
      //provide a function through activeTail class to provide this
      at1->getTail()->joinHeadToHead(*(at2->getTail()));
      if(phole) 
        at1->addHole(phole, fractureHoles); //assert fractureHoles == false
      return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2);
    }
    //assert phole is not null
    //assert fractureHoles is true
    if(phole->getOrient() == VERTICAL) {
      at2 = phole;
    } else {
      at2 = phole->getOtherActiveTail(); //should never be executed since orientation is expected to be vertical
    }
    //assert solid == false, we should be creating a corner with solid below and to the left if there was a hole
    at1 = at2->getOtherActiveTail();
    //assert at1 is horizontal
    at1->pushCoordinate(x);
    //assert at2 is vertical
    at2->pushCoordinate(y);
    return std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*>(at1, at2);
  }
 
  //Process edges connects vertical input edges (right or left edges of figures) to horizontal edges stored as member
  //data of the scanline object.  It also creates now horizontal edges as needed to construct figures from edge data.
  //
  //There are only 12 geometric end cases where the scanline intersects a horizontal edge and even fewer unique 
  //actions to take:
  // 1. Solid on both sides of the vertical partition after the current position and space on both sides before
  //         ###|###          
  //         ###|###         
  //            |            
  //            |            
  //    This case does not need to be handled because there is no vertical edge at the current x coordinate.
  //
  // 2. Solid on both sides of the vertical partition before the current position and space on both sides after
  //            |            
  //            |            
  //         ###|###          
  //         ###|###         
  //    This case does not need to be handled because there is no vertical edge at the current x coordinate.
  //
  // 3. Solid on the left of the vertical partition after the current position and space elsewhere
  //         ###|          
  //         ###|         
  //            |            
  //            |     
  //    The horizontal edge from the left is found and turns upward because of the vertical right edge to become
  //    the currently active vertical edge.
  //
  // 4. Solid on the left of the vertical partion before the current position and space elsewhere
  //            |            
  //            |            
  //         ###| 
  //         ###|
  //    The horizontal edge from the left is found and joined to the currently active vertical edge.
  //
  // 5. Solid to the right above and below and solid to the left above current position.
  //         ###|###          
  //         ###|###         
  //            |###            
  //            |###            
  //    The horizontal edge from the left is found and joined to the currently active vertical edge,
  //    potentially closing a hole.
  //
  // 6. Solid on the left of the vertical partion before the current position and solid to the right above and below
  //            |###
  //            |###            
  //         ###|### 
  //         ###|###
  //    The horizontal edge from the left is found and turns upward because of the vertical right edge to become
  //    the currently active vertical edge.
  //
  // 7. Solid on the right of the vertical partition after the current position and space elsewhere
  //            |###          
  //            |###         
  //            |            
  //            |     
  //    Create two new ActiveTails, one is added to the horizontal edges and the other becomes the vertical currentTail
  //
  // 8. Solid on the right of the vertical partion before the current position and space elsewhere
  //            |            
  //            |            
  //            |### 
  //            |###
  //    The currentTail vertical edge turns right and is added to the horizontal edges data
  //
  // 9. Solid to the right above and solid to the left above and below current position.
  //         ###|###          
  //         ###|###         
  //         ###| 
  //         ###|
  //    The currentTail vertical edge turns right and is added to the horizontal edges data
  //
  // 10. Solid on the left of the vertical partion above and below the current position and solid to the right below
  //         ###| 
  //         ###|
  //         ###|### 
  //         ###|###
  //    Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail
  //
  // 11. Solid to the right above and solid to the left below current position.
  //            |### 
  //            |###
  //         ###| 
  //         ###|
  //    The currentTail vertical edge joins the horizontal edge from the left (may close a polygon)
  //    Create two new ActiveTails, one is added to the horizontal edges data and the other becomes the vertical currentTail
  //
  // 12. Solid on the left of the vertical partion above the current position and solid to the right below
  //         ###| 
  //         ###|
  //            |### 
  //            |###
  //    The currentTail vertical edge turns right and is added to the horizontal edges data.
  //    The horizontal edge from the left turns upward and becomes the currentTail vertical edge
  //
  template <bool orientT, typename Unit, typename polygon_concept_type>
  inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::
  processEdges(iterator& beginOutput, iterator& endOutput, 
               Unit currentX, std::vector<interval_data<Unit> >& leftEdges, 
               std::vector<interval_data<Unit> >& rightEdges) {
    clearOutput_();
    typename std::map<Unit, ActiveTail<Unit>*>::iterator nextMapItr = tailMap_.begin();
    //foreach edge
    unsigned int leftIndex = 0;
    unsigned int rightIndex = 0;
    bool bottomAlreadyProcessed = false;
    ActiveTail<Unit>* currentTail = 0;
    const Unit UnitMax = (std::numeric_limits<Unit>::max)();
    while(leftIndex < leftEdges.size() || rightIndex < rightEdges.size()) {
      interval_data<Unit>  edges[2] = {interval_data<Unit> (UnitMax, UnitMax), interval_data<Unit> (UnitMax, UnitMax)};
      bool haveNextEdge = true;
      if(leftIndex < leftEdges.size())
        edges[0] = leftEdges[leftIndex];
      else
        haveNextEdge = false;
      if(rightIndex < rightEdges.size())
        edges[1] = rightEdges[rightIndex];
      else
        haveNextEdge = false;
      bool trailingEdge = edges[1].get(LOW) < edges[0].get(LOW);
      interval_data<Unit> & edge = edges[trailingEdge];
      interval_data<Unit> & nextEdge = edges[!trailingEdge];
      //process this edge
      if(!bottomAlreadyProcessed) {
        //assert currentTail = 0 

        //process the bottom end of this edge
        typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(LOW));
        if(thisMapItr != tailMap_.end()) {
          //there is an edge in the map at the low end of this edge
          //it needs to turn upward and become the current tail
          ActiveTail<Unit>* tail = thisMapItr->second;
          if(currentTail) {
            //stitch currentTail into this tail
            currentTail = tail->addHole(currentTail, fractureHoles_);
            if(!fractureHoles_)
              currentTail->pushCoordinate(currentX);
          } else {
            currentTail = tail;
            currentTail->pushCoordinate(currentX);
          }
          //assert currentTail->getOrient() == VERTICAL
          nextMapItr = thisMapItr; //set nextMapItr to the next position after this one
          ++nextMapItr;
          //remove thisMapItr from the map
          tailMap_.erase(thisMapItr);
        } else {
          //there is no edge in the map at the low end of this edge
          //we need to create one and another one to be the current vertical tail
          //if this is a trailing edge then there is space to the right of the vertical edge
          //so pass the inverse of trailingEdge to indicate solid to the right
          std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = 
            createActiveTailsAsPair(currentX, edge.get(LOW), !trailingEdge, currentTail, fractureHoles_);
          currentTail = tailPair.first;
          tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(LOW), tailPair.second));
          // leave nextMapItr unchanged
        }

      }
      if(haveNextEdge && edge.get(HIGH) == nextEdge.get(LOW)) {
        //the top of this edge is equal to the bottom of the next edge, process them both
        bottomAlreadyProcessed = true;
        typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(HIGH));
        if(thisMapItr == tailMap_.end()) //assert this should never happen
          return;
        if(trailingEdge) {
          //geometry at this position
          //   |##
          //   |##
          // -----
          // ##|
          // ##|
          //current tail should join thisMapItr tail
          ActiveTail<Unit>* tail = thisMapItr->second;
          //pass false because they are being joined because space is to the right and it will close a solid figure
          ActiveTail<Unit>::joinChains(currentTail, tail, false, outputPolygons_);
          //two new tails are created, the vertical becomes current tail, the horizontal becomes thisMapItr tail
          //pass true becuase they are created at the lower left corner of some solid
          //pass null because there is no hole pointer possible
          std::pair<ActiveTail<Unit>*, ActiveTail<Unit>*> tailPair = 
            createActiveTailsAsPair<Unit>(currentX, edge.get(HIGH), true, 0, fractureHoles_);
          currentTail = tailPair.first;
          thisMapItr->second = tailPair.second;
        } else {
          //geometry at this position
          // ##|
          // ##|
          // -----
          //   |##
          //   |##
          //current tail should turn right
          currentTail->pushCoordinate(edge.get(HIGH));
          //thisMapItr tail should turn up
          thisMapItr->second->pushCoordinate(currentX);
          //thisMapItr tail becomes current tail and current tail becomes thisMapItr tail
          std::swap(currentTail, thisMapItr->second);
        }
        nextMapItr = thisMapItr; //set nextMapItr to the next position after this one
        ++nextMapItr;
      } else {
        //there is a gap between the top of this edge and the bottom of the next, process the top of this edge
        bottomAlreadyProcessed = false;
        //process the top of this edge
        typename std::map<Unit, ActiveTail<Unit>*>::iterator thisMapItr = findAtNext(tailMap_, nextMapItr, edge.get(HIGH));
        if(thisMapItr != tailMap_.end()) {
          //thisMapItr is pointing to a horizontal edge in the map at the top of this vertical edge
          //we need to join them and potentially close a figure
          //assert currentTail != 0
          ActiveTail<Unit>* tail = thisMapItr->second;
          //pass the opositve of trailing edge to mean that they are joined because of solid to the right
          currentTail = ActiveTail<Unit>::joinChains(currentTail, tail, !trailingEdge, outputPolygons_);
          nextMapItr = thisMapItr; //set nextMapItr to the next position after this one
          ++nextMapItr;
          if(currentTail) {
            Unit nextItrY = UnitMax;
            if(nextMapItr != tailMap_.end()) {
              nextItrY = nextMapItr->first;
            }
            //for it to be a hole this must have been a left edge
            Unit leftY = UnitMax;
            if(leftIndex + 1 < leftEdges.size())
              leftY = leftEdges[leftIndex+1].get(LOW);
            Unit rightY = nextEdge.get(LOW);
            if(!haveNextEdge || (nextItrY < leftY && nextItrY < rightY)) {
              //we need to add it to the next edge above it in the map
              tail = nextMapItr->second;
              tail = tail->addHole(currentTail, fractureHoles_);
              if(fractureHoles_) {
                //some small additional work stitching in the filament
                tail->pushCoordinate(nextItrY);
                nextMapItr->second = tail;
              }
              //set current tail to null
              currentTail = 0;
            }
          }  
          //delete thisMapItr from the map
          tailMap_.erase(thisMapItr);
        } else {
          //currentTail must turn right and be added into the map
          currentTail->pushCoordinate(edge.get(HIGH));
          //assert currentTail->getOrient() == HORIZONTAL
          tailMap_.insert(nextMapItr, std::pair<Unit, ActiveTail<Unit>*>(edge.get(HIGH), currentTail));
          //set currentTail to null
          currentTail = 0;
          //leave nextMapItr unchanged, it is still next
        }
      }
 
      //increment index
      leftIndex += !trailingEdge;
      rightIndex += trailingEdge;
    } //end while
    beginOutput = outputPolygons_.begin();
    endOutput = outputPolygons_.end();
  } //end function

  template<bool orientT, typename Unit, typename polygon_concept_type>
  inline void ScanLineToPolygonItrs<orientT, Unit, polygon_concept_type>::clearOutput_() {
    for(std::size_t i = 0; i < outputPolygons_.size(); ++i) {
      ActiveTail<Unit>* at1 = outputPolygons_[i].yield();
      const std::list<ActiveTail<Unit>*>& holes = at1->getHoles();
      for(typename std::list<ActiveTail<Unit>*>::const_iterator litr = holes.begin(); litr != holes.end(); ++litr) {
        //delete the hole
        (*litr)->destroyContents();
        destroyActiveTail((*litr)->getOtherActiveTail());
        destroyActiveTail((*litr));
      }
      //delete the polygon
      at1->destroyContents();
      //at2 contents are the same as at1, so it should not destroy them
      destroyActiveTail((at1)->getOtherActiveTail());
      destroyActiveTail(at1);
    }
    outputPolygons_.clear();
  }

} //polygon_formation namespace

  template <bool orientT, typename Unit>
  struct geometry_concept<polygon_formation::PolyLinePolygonWithHolesData<orientT, Unit> > {
    typedef polygon_90_with_holes_concept type;
  };

  template <bool orientT, typename Unit>
  struct geometry_concept<polygon_formation::PolyLineHoleData<orientT, Unit> > {
    typedef polygon_90_concept type;
  };

  //public API to access polygon formation algorithm
  template <typename output_container, typename iterator_type, typename concept_type>
  unsigned int get_polygons(output_container& container, iterator_type begin, iterator_type end,
                    orientation_2d orient, bool fracture_holes, concept_type ) {
    typedef typename output_container::value_type polygon_type;
    typedef typename std::iterator_traits<iterator_type>::value_type::first_type coordinate_type;
    polygon_type poly;
    unsigned int countPolygons = 0;
    typedef typename geometry_concept<polygon_type>::type polygon_concept_type;
    polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type> scanlineToPolygonItrsV(fracture_holes);
    polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type> scanlineToPolygonItrsH(fracture_holes);
    std::vector<interval_data<coordinate_type> > leftEdges;
    std::vector<interval_data<coordinate_type> > rightEdges;
    coordinate_type prevPos = (std::numeric_limits<coordinate_type>::max)();
    coordinate_type prevY = (std::numeric_limits<coordinate_type>::max)();
    int count = 0;
    for(iterator_type itr = begin;
        itr != end; ++ itr) {
      coordinate_type pos = (*itr).first;
      if(pos != prevPos) {
        if(orient == VERTICAL) {
          typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd;
          scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges);
          for( ; itrPoly != itrPolyEnd; ++ itrPoly) {
            ++countPolygons;
            assign(poly, *itrPoly);
            container.insert(container.end(), poly);
          }
        } else {
          typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd;
          scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges);
          for( ; itrPoly != itrPolyEnd; ++ itrPoly) {
            ++countPolygons;
            assign(poly, *itrPoly);
            container.insert(container.end(), poly);
          }
        }
        leftEdges.clear();
        rightEdges.clear();
        prevPos = pos;
        prevY = (*itr).second.first;
        count = (*itr).second.second;
        continue;
      }
      coordinate_type y = (*itr).second.first;
      if(count != 0 && y != prevY) {
        std::pair<interval_data<coordinate_type>, int> element(interval_data<coordinate_type>(prevY, y), count);
        if(element.second == 1) {
          if(leftEdges.size() && leftEdges.back().high() == element.first.low()) {
            encompass(leftEdges.back(), element.first);
          } else {
            leftEdges.push_back(element.first);
          }
        } else {
          if(rightEdges.size() && rightEdges.back().high() == element.first.low()) {
            encompass(rightEdges.back(), element.first);
          } else {
            rightEdges.push_back(element.first);
          }
        }

      }
      prevY = y;
      count += (*itr).second.second;
    }
    if(orient == VERTICAL) {
      typename polygon_formation::ScanLineToPolygonItrs<true, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd;
      scanlineToPolygonItrsV.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges);
      for( ; itrPoly != itrPolyEnd; ++ itrPoly) {
        ++countPolygons;
        assign(poly, *itrPoly);
        container.insert(container.end(), poly);
      }
    } else {
      typename polygon_formation::ScanLineToPolygonItrs<false, coordinate_type, polygon_concept_type>::iterator itrPoly, itrPolyEnd;
      scanlineToPolygonItrsH.processEdges(itrPoly, itrPolyEnd, prevPos, leftEdges, rightEdges);
      for( ; itrPoly != itrPolyEnd; ++ itrPoly) {
        ++countPolygons;
        assign(poly, *itrPoly);
        container.insert(container.end(), poly);
      }
    }
    return countPolygons;
  }

}
}
#endif