//=============================================================================
// Copyright (c) Kitware, Inc.
// All rights reserved.
// See LICENSE.txt for details.
//
// This software is distributed WITHOUT ANY WARRANTY; without even
// the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR
// PURPOSE.  See the above copyright notice for more information.
//=============================================================================
#include "smtk/bridge/polygon/operators/CreateFaces.h"

#include "smtk/bridge/polygon/Session.h"
#include "smtk/bridge/polygon/internal/Config.h"
#include "smtk/bridge/polygon/internal/Model.h"
#include "smtk/bridge/polygon/internal/Edge.h"

#include "smtk/common/UnionFind.h"

#include "smtk/io/Logger.h"

#include "smtk/attribute/Attribute.h"
#include "smtk/attribute/DoubleItem.h"
#include "smtk/attribute/IntItem.h"
#include "smtk/attribute/ModelEntityItem.h"
#include "smtk/attribute/StringItem.h"

#include "smtk/bridge/polygon/CreateFaces_xml.h"

#include <deque>
#include <map>
#include <set>
#include <vector>

namespace smtk {
  namespace bridge {
    namespace polygon {

/// An internal structure used when discovering edge loops.
struct ModelEdgeInfo
{
  ModelEdgeInfo()
    : m_allowedOrientations(0)
    {
    this->m_visited[0] = this->m_visited[1] = false;
    }
  ModelEdgeInfo(int allowedOrientations)
    {
    this->m_allowedOrientations = allowedOrientations > 0 ? +1 : allowedOrientations < 0 ? -1 : 0;
    this->m_visited[0] = this->m_visited[1] = false;
    }
  ModelEdgeInfo(const ModelEdgeInfo& other)
    : m_allowedOrientations(other.m_allowedOrientations)
    {
    for (int i = 0; i < 2; ++i)
      m_visited[i] = other.m_visited[i];
    }

  int m_allowedOrientations; // 0: all, -1: only negative, +1: only positive
  bool m_visited[2]; // has the [0]: negative, [1]: positive orientation of the edge been visited already?
};

/// An internal structure used to map model edges to information about the space between them.
typedef std::map<smtk::model::Edge, ModelEdgeInfo> ModelEdgeMap;

/// An internal structure used to hold a sequence of model edges which form a loop.
struct LoopInfo
{
  internal::Id m_id;
  internal::Rect m_bounds;
  smtk::model::Edges m_edges;
  std::set<internal::Id> m_children; // first-level holes
  bool operator < (const LoopInfo& other)
    {
    return ll(this->m_bounds) < ur(other.m_bounds);
    }
};

/// An internal structure that holds all the loops discovered, sorted by their lower-left bounding box coordinates.
typedef std::map<internal::Id,LoopInfo> LoopsById;

/// Sweep events ordered by their left-, lower-most point coordinates.
typedef std::set<SweepEvent> SweepEventSet;

/// Structure to hold a sweepline event data (segment start, segment end, segment crossing).
struct SweepEvent
{
  enum SweepEventType {
    SEGMENT_START,
    SEGMENT_CROSS, // NB: CROSS must come before END so that RemoveCrossing can terminate early; want to handle crossings while edge is still active.
    SEGMENT_END
  };
  SweepEventType m_type;
  internal::Point m_posn;
  smtk::model::Edge m_edge; // only used by SEGMENT_START
  int m_indx; // only used by SEGMENT_START
  RegionIdSet::value_type m_frag[2]; // used by SEGMENT_END and SEGMENT_CROSS as frag ID, SEGMENT_START as sense (-1/+1)

  SweepEventType type() const { return this->m_type; }
  const internal::Point& point() const { return this->m_posn; }

  bool operator < (const SweepEvent& other) const
    {
    return
      (this->m_posn.x() < other.point().x() ||
       (this->m_posn.x() == other.point().x() &&
        (this->m_posn.y() < other.point().y() ||
         (this->m_posn.y() == other.point().y() &&
          (this->m_type < other.type() ||
           (this->m_type == other.type() &&
            ( // Types match, perform type-specific comparisons:
             (this->m_type == SEGMENT_START &&
              (this->m_edge < other.m_edge ||
               (this->m_edge == other.m_edge && this->m_indx < other.m_indx))) ||
             (this->m_type == SEGMENT_END &&
              (this->m_frag[0] < other.m_frag[0])) ||
             (this->m_type == SEGMENT_CROSS &&
              (this->m_frag[0] < other.m_frag[0] ||
               (this->m_frag[0] == other.m_frag[0] &&
                (this->m_frag[1] < other.m_frag[1]))))
            ))))))) ?
      true : false;
    }

  static SweepEvent SegmentStart(
    const internal::Point& p0,
    const internal::Point& p1,
    const smtk::model::Edge& edge,
    int segId)
    {
    SweepEvent event;
    event.m_type = SEGMENT_START;
    if (p0.x() < p1.x() || (p0.x() == p1.x() && p0.y() < p1.y()))
      {
      event.m_posn = p0;
      event.m_frag[0] = +1;
      }
    else
      {
      event.m_posn = p1;
      event.m_frag[0] = -1;
      }
    event.m_edge = edge;
    event.m_indx = segId;
    return event;
    }
  static SweepEvent SegmentEnd(
    const internal::Point& posn,
    RegionIdSet::value_type fragId)
    {
    SweepEvent event;
    event.m_type = SEGMENT_END;
    event.m_posn = posn;
    event.m_frag[0] = fragId;
    return event;
    }
  static SweepEvent SegmentCross(
    const internal::Point& crossPos,
    RegionIdSet::value_type fragId0,
    RegionIdSet::value_type fragId1)
    {
    SweepEvent event;
    event.m_type = SEGMENT_CROSS;
    event.m_posn = crossPos;
    event.m_frag[0] = fragId0;
    event.m_frag[1] = fragId1;
    return event;
    }

  static bool RemoveCrossing(
    SweepEventSet& queue,
    FragmentId fragId0,
    FragmentId fragId1)
    {
    for (SweepEventSet::iterator it = queue.begin(); it != queue.end(); ++it)
      {
      switch (it->m_type)
        {
      case SEGMENT_START:
        break;
      case SEGMENT_CROSS:
        if (
          it->m_frag[0] == fragId0 &&
          it->m_frag[1] == fragId1)
          {
          queue.erase(it);
          return true;
          }
        break;
      case SEGMENT_END:
        if (it->m_frag[0] == fragId0 || it->m_frag[0] == fragId1)
          { // Terminate early... crossing event must come before either edge ends.
          return false;
          }
        break;
        }
      }
    return false;
    }
};

/// Structure to hold information about a portion of an edge-segment forming part of an output loop.
struct EdgeFragment
{
  internal::Point m_lo; // Low is relative to the sweep direction (left to right, bottom to top).
  internal::Point m_hi; // High is relative to the sweep direction.
  smtk::model::Edge m_edge; // SMTK model information
  internal::EdgePtr m_edgeData; // Private edge data (sequence of points defining segments)
  int m_segment; // Offset into edge's point sequence defining the segment containing this fragment.
  bool m_sense; // True when fragment and model edge are codirectional; false when they are antidirectional.
  RegionIdSet::value_type m_regionId[2]; // Union-Find region to each side of edge; 0: region CCW of edge, 1: region CW of edge.
  FragmentId m_next[2]; // Next co-fragment in region; 0: opposite of fragment dir, 1: along fragment dir.

  internal::Point& lo() { return this->m_lo; }
  const internal::Point& lo() const { return this->m_lo; }

  internal::Point& hi() { return this->m_hi; }
  const internal::Point& hi() const { return this->m_hi; }

  /// Return the ID of the region above the fragment.
  RegionIdSet::value_type& upperRegion() { return this->m_regionId[1]; }
  /// Return the ID of the region below the fragment.
  RegionIdSet::value_type& lowerRegion() { return this->m_regionId[0]; }

  /**\brief Return the ID of the region just counter-clockwise (CCW) of the fragment...
    *
    * ... when winding around the lower (\a fromLowerEnd is true) or
    * upper (\a fromLowerEnd is false) endpoint of the fragment.
    */
  RegionIdSet::value_type& ccwRegion(bool fromLowerEnd) { return this->m_regionId[fromLowerEnd ? 1 : 0]; }
  /**\brief Return the ID of the region just clockwise (CW) of the fragment...
    *
    * ... when winding around the lower (\a fromLowerEnd is true) or
    * upper (\a fromLowerEnd is false) endpoint of the fragment.
    */
  RegionIdSet::value_type& cwRegion(bool fromLowerEnd) { return this->m_regionId[fromLowerEnd ? 0 : 1]; }

  /**\brief Return the next fragment bounding the region to the left of the fragment.
    *
    */
  FragmentId& nextFragment(bool forwardDir) { return this->m_next[forwardDir ? 1 : 0]; }

  /// Debug dump of fragment
  void dump(RegionIdSet& ufind) const
    {
    std::cout
      << "  " << this->lo().x()/1182720.0 << " " << this->lo().y()/1182720.0
      << " -- " << this->hi().x()/1182720.0 << " " << this->hi().y()/1182720.0
      << "  " << this->m_edge.name() << ", seg " << this->m_segment
      << " regIds " << ufind.find(this->m_regionId[0]) << " " << ufind.find(this->m_regionId[1])
      << " next " << this->m_next[0] << " " << this->m_next[1]
      << "\n";
    }
};

typedef std::vector<EdgeFragment> FragmentArray; // List of all output fragments forming loops.

struct SweeplinePosition
{
  internal::Point m_position;
  SweeplinePosition(const internal::Point& posn)
    : m_position(posn)
    {
    }
  SweeplinePosition(const SweeplinePosition& other)
    : m_position(other.m_position)
    {
    }

  /// Return the current sweepline position
  internal::Point& position() { return this->m_position; }

  /// Return the current sweepline position
  const internal::Point& position() const { return this->m_position; }

  /// Advance the sweepline to another position, ignoring invalid points to the left of the current position.
  void advance(const internal::Point& pt)
    {
    if (
      pt.x() > this->m_position.x() ||
      (pt.x() == this->m_position.x() && pt.y() > this->m_position.y()))
      {
      this->m_position = pt;
      }
    /*
    else
      {
      throw std::string("Can not sweep backwards!");
      }
      */
    }
  bool operator < (const internal::Point& other)
    {
    return this->m_position < other;
    }
  bool operator > (const internal::Point& other)
    {
    return this->m_position > other;
    }
  bool operator == (const internal::Point& other)
    {
    return this->m_position == other;
    }
  bool operator != (const internal::Point& other)
    {
    return this->m_position != other;
    }
};

/// Functor to compare indices into a vector of EdgeFragments based on which fragment is above the other.
struct EdgeFragmentComparator
{
  FragmentArray* m_sweptFragments;

  EdgeFragmentComparator(FragmentArray& frag, SweeplinePosition& startPoint)
    : m_sweptFragments(&frag)
    {
    }

  EdgeFragmentComparator(const EdgeFragmentComparator& other)
    : m_sweptFragments(other.m_sweptFragments)
    {
    }

  /// Return the array of fragments the comparator indexes into.
  FragmentArray* fragments() const
    {
    return this->m_sweptFragments;
    }
  /**\brief Return true when line a lies to the left of and/or below line b for the current sweepLocation.
    *
    * When the sweep position is at an intersection point of 2 or more lines, we order
    * the lines according to their behavior just to the left (or below, in the case of
    * vertical lines) of the sweep position.
    *
    * As noted by Boissonat and Preparata, predicates for testing relationships between
    * lines require increased-precision operations according to the degree of the
    * equations in the predicate.
    */
  bool operator() (FragmentId a, FragmentId b) const
    {
    FragmentId fsize = this->fragments()->size();
    // If a is invalid, it is "above" any valid segments:
    if (a >= fsize)
      return false;
    // Now we know a is valid (or we would have returned false).

    // A segment is never less than itself.
    if (b == a)
      return false;

    // Valid segments are always below invalid ones:
    if (b >= fsize)
      return true;

    // Both a and b are valid:
    EdgeFragment& lineA((*this->fragments())[a]);
    EdgeFragment& lineB((*this->fragments())[b]);

    // I. Compare y coordinates of fragment lo() points.
    //    Since active fragments do not cross (or have their hi() coordinates
    //    altered to an intersection point) comparing low coordinates is
    //    valid as long as fragments are removed once their hi() neighborhood
    //    has been processed.
    if (lineA.lo().y() < lineB.lo().y())
      return true;
    else if (lineA.lo().y() > lineB.lo().y())
      return false;

    // II. Compare slopes of fragments when they have identical lo().y() coords.
    //     Multiple fragments can start at the same point but shouldn't have the
    //     same slope. Note that because fragments always go from low to high
    //     x coordinates, we do not have to worry about the direction of the
    //     inequality changing because of negative delta_x values in the slope.
    //     (delta_x >= 0 for all fragments).
    internal::HighPrecisionCoord dxA = lineA.hi().x() - lineA.lo().x();
    internal::HighPrecisionCoord dxB = lineB.hi().x() - lineB.lo().x();
    internal::HighPrecisionCoord slopeDiff =
      dxB * (lineA.hi().y() - lineA.lo().y()) -
      dxA * (lineB.hi().y() - lineB.lo().y());

    if (slopeDiff < 0)
      return true;
    else if (slopeDiff > 0)
      return false;

    // We are here because of a problem. No two line segments should be
    // collinear. If they are, one corresponding fragment should be discarded
    // before being added to m_fragments. So, we should complain but not die.
    std::cerr
      << "Error: trying to insert coincident, collinear fragments " << a << " and " << b << " into active fragment tree.";
    return a < b;
    }
};

/// The sweepline Interval Tree (IT), of active edge segments, is a set of offsets into the array of fragments.
typedef std::set<FragmentId, EdgeFragmentComparator> ActiveFragmentTree;

/// The set of all regions is a UnionFind (UF) data structure.
typedef smtk::common::UnionFind<int> RegionIdSet;

/// A structure to hold chains of coedges bounding regions of space.
struct Region
{
  FragmentId m_seedFragment;
  bool m_seedSense;
  //std::deque<std::pair<FragmentId,bool> > m_boundary; // size_t = fragment id, bool = sense rel to fragment
  std::set<int> m_innerLoops;

  Region()
    : m_seedFragment(-1), m_seedSense(true)
    { }
  Region(FragmentId seedFrag, bool seedSense)
    : m_seedFragment(seedFrag), m_seedSense(seedSense)
    { }

  void merge(const Region* other)
    {
    if (!other)
      {
      return;
      }
    if (this->m_seedFragment == -1)
      {
      this->m_seedFragment = other->m_seedFragment;
      this->m_seedSense = other->m_seedSense;
      for (std::set<int>::const_iterator it = other->m_innerLoops.begin(); it != other->m_innerLoops.end(); ++it)
        {
        this->m_innerLoops.insert(*it);
        }
      }
    }
};

/// A map to hold each region's definition indexed by its UF region ID.
typedef std::map<RegionIdSet::value_type,smtk::shared_ptr<Region> > RegionDefinitions;

internal::HighPrecisionCoord dot2d(const internal::Coord oa[2], const internal::Coord oo[2])
{
  internal::HighPrecisionCoord result;
  result =
    static_cast<internal::HighPrecisionCoord>(oa[0]) * oo[0] +
    static_cast<internal::HighPrecisionCoord>(oa[1]) * oo[1];
  return result;
}

internal::HighPrecisionCoord cross2d(const internal::Coord oa[2], const internal::Coord oo[2])
{
  internal::HighPrecisionCoord result;
  result =
    static_cast<internal::HighPrecisionCoord>(oa[0]) * oo[1] -
    static_cast<internal::HighPrecisionCoord>(oa[1]) * oo[0];
  return result;
}

/**\brief Represent the neighborhood of a sweepline point, x.
  *
  * This holds a CCW-ordered list of edges incident to x, plus an
  * array of fragments
  */
struct Neighborhood
{
  Neighborhood(SweeplinePosition& x, FragmentArray& fragments, SweepEventSet& eventQueue, ActiveFragmentTree& active)
    : m_point(&x), m_fragments(&fragments), m_eventQueue(&eventQueue), m_activeEdges(&active)
    {
    }

  SweeplinePosition* m_point;
  FragmentArray* m_fragments;
  SweepEventSet* m_eventQueue;
  ActiveFragmentTree* m_activeEdges;
  RegionIdSet m_regionIds;
  RegionDefinitions m_regions;
  std::vector<FragmentId> m_fragmentsToQueue;
  std::set<FragmentId> m_fragmentsToDeactivate;
  std::list<FragmentId> m_ring; // offsets into m_fragments that order a neighborhood CCW

  /**\brief Return the orientation of a fragment relative to the neighborhood.
    *
    * Returns true when the neighborhood is placed at the left/lower end of the fragment
    * and true otherwise.
    * This is used to obtain the proper region ID when winding around
    * the edges incident to the neighborhood.
    */
  bool isFragmentOutgoing(const EdgeFragment& frag)
    {
    return frag.lo() == this->m_point->position();
    }

  /// The space between \a ringA and \a ringB is not interrupted; mark coedges of A/B as same region.
  void assignAndMergeRegions(
    const std::list<FragmentId>::iterator& ringA,
    const std::list<FragmentId>::iterator& ringB)
    {
    std::cout << "  A-B: " << *ringA << " " << *ringB << "\n";
    EdgeFragment& fragA((*this->m_fragments)[*ringA]);
    EdgeFragment& fragB((*this->m_fragments)[*ringB]);
    // Determine sense wrt neighborhood (isOutX == true => fragment's other vertex hasn't been processed yet).
    bool isOutA = this->isFragmentOutgoing(fragA); // true when m_point is coincident with fragA.lower
    bool isOutB = this->isFragmentOutgoing(fragB);

    RegionIdSet::value_type idA = this->m_regionIds.find(fragA.ccwRegion(isOutA));
    RegionIdSet::value_type idB = this->m_regionIds.find(fragB.cwRegion(isOutB));
    RegionIdSet::value_type winner;
    if (idA != idB)
      { // Merge regions on inside of A--B. Add coedges (of exiting edges on inside of A--B) to region.
      winner = this->m_regionIds.mergeSets(idA, idB);
      RegionIdSet::value_type loser = (winner == idA ? idB : idA);
      // If this is a new region, create a record for it.
      if (!this->m_regions[winner])
        {
        this->m_regions[winner] = smtk::shared_ptr<Region>(new Region(*ringB, !isOutB));
        }
      this->m_regions[winner]->merge(this->m_regions[loser].get());
      }
    else
      { // Add coedges (of exiting edges on inside of A--B) to region.
      winner = idA;
      }
    // Link one coedge of B to A.
    fragB.nextFragment(!isOutB) = *ringA;
    /*
    if (this->m_point.position() > fragA.lo())
      {
      this->m_regions[winner].insert(fragA.xxx)
    this->m_regionIds.mergeSets(fragA.regionIds[0], fragB.regionIds[1]);
      // TODO. Pop m_regions[whichever fragX.regionId[z] is not returned by mergeSets] and append/prepend
      //       to m_regions[whichever fragX.regionId[z] *is* returned by mergeSets] depending on
      //       whether survivor X == A (prepend m_regions[m_regionIds->find(B)]) or X == b (append ...find(A)).
      }
      */

    /*
    if (!isOutA && !isOutB && edgeA.below(edgeB))
      {
      // Both edges are ending here... we should mark the A-B region
      // as an inner loop contained by the edges immediately above
      // and below neighborhood.
      xxx
      }
      */

    // TODO. Could also check whether fragments are both segment-end events;
    //       if so, see whether chain is complete and output a "create face
    //       from chain" event.
    }

  /// Insert \a fragId into \a m_ring if it is between \a ringA and \a ringB
  bool insertFragmentBetween(
    const std::list<FragmentId>::iterator& ringA,
    const std::list<FragmentId>::iterator& ringB,
    FragmentId fragId,
    EdgeFragment& frag,
    const internal::Point& other)
    {
    EdgeFragment& fragA((*this->m_fragments)[*ringA]);
    EdgeFragment& fragB((*this->m_fragments)[*ringB]);
    internal::Point otherA(fragA.lo() == this->m_point->position() ? fragA.hi() : fragA.lo());
    internal::Point otherB(fragB.lo() == this->m_point->position() ? fragB.hi() : fragB.lo());

    internal::Coord oa[2] = {
      otherA.x() - this->m_point->position().x(),
      otherA.y() - this->m_point->position().y()};
    internal::Coord ob[2] = {
      otherB.x() - this->m_point->position().x(),
      otherB.y() - this->m_point->position().y()};
    internal::Coord oo[2] = {
      other.x() - this->m_point->position().x(),
      other.y() - this->m_point->position().y()};
    internal::HighPrecisionCoord oaXoo = cross2d(oa, oo);
    internal::HighPrecisionCoord ooXob = cross2d(oo, ob);
    if (oaXoo > 0 && ooXob > 0)
      { // other is between ringA and ringB. Insert it just before ringB:
      this->m_ring.insert(ringB, fragId);
      return true;
      }
    else if (oaXoo == 0)
      { // Urk. other is collinear with ringA...
      if (dot2d(oa,oo) < 0 && ooXob > 0)
        {
        // ... but antidirectional with ringA; and properly oriented with ringB.
        this->m_ring.insert(ringB, fragId);
        return true;
        }
      else
        {
        // TODO. FIXME.
        // Replace ringA with fragId if frag is shorter (or barf if lengths identical? surgery to fix problems could be nasty);
        // queue new SegmentStart for remaining long fragment.
        }
      }
    else if (ooXob == 0)
      { // Urk. other is collinear with ringB...
      if (dot2d(oo,ob) < 0 && oaXoo > 0)
        {
        // ... but antidirectional with ringB; and properly oriented with ringA.
        this->m_ring.insert(ringB, fragId);
        return true;
        }
      else
        {
        // TODO. FIXME.
        // Replace ringB with fragId if frag is shorter (or barf if lengths identical? surgery to fix problems could be nasty);
        // queue new SegmentStart for remaining long fragment.
        }
      }
    return false; // other is not between ringA and ringB.
    }
  /**\brief Insert \a frag where it belongs in the ring of fragments incident to \a m_point.
    *
    * The \a other point is the end of \a frag which is not \a m_point.
    * This algorithm works by traversing pre-existing neighborhood fragments to identify when
    * dot(cross(fragIt-m_point x other-m_point),(0,0,1)) changes sign from - to +.
    * Or, identically, it inserts frag between a neighboring pair of points on the ring (a,b)
    * when dot(cross(a-m_point x other-m_point),(0,0,1)) > 0 && dot(cross(other-m_point x b-m_point),(0,0,1)) > 0.
    *
    * If either cross product has zero magnitude, the fragment is collinear with an existing segment.
    * In that case, (1) the shorter fragment is kept in the ring; (2) a new SegmentStart event is queued
    * for the uncovered portion of the longer fragment; (3) the longer fragment is discarded; and
    * (4?) a warning is logged.
    */
  void insertFragment(FragmentId fragId, EdgeFragment& frag, const internal::Point& other)
    {
    for (int i = 0; i < 2; ++i)
      if (frag.m_regionId[i] < 0)
        frag.m_regionId[i] = this->m_regionIds.newSet();

    if (this->m_ring.size() < 2)
      { // No matter where we insert, the order will be CCW. So insert at beginning:
      this->m_ring.insert(this->m_ring.begin(), fragId);
      return;
      }
    std::list<FragmentId>::iterator ringA = this->m_ring.end();
    --ringA; // "unadvance" before end() to the last ring entry.
    std::list<FragmentId>::iterator ringB = this->m_ring.begin();
    // Start by processing the implicit fragment-pair between m_ring.end() and m_ring.begin():
    if (this->insertFragmentBetween(ringA, ringB, fragId, frag, other))
      return;
    // Now proceed through the list until we find the right spot.
    ringA = ringB;
    for (++ringB; ringB != this->m_ring.end(); ++ringA, ++ringB /*, sao = -sbo??? */)
      {
      if (this->insertFragmentBetween(ringA, ringB, fragId, frag, other))
        return;
      }
    std::cerr << "Error. Unable to insert fragment into neighborhood!\n"; // FIXME. Add to log, not cerr/cout.
    }

  void queueActiveEdge(FragmentId fragId, EdgeFragment& frag)
    {
    this->m_fragmentsToQueue.push_back(fragId);
    }

  void removeActiveEdge(FragmentId fragId)
    {
    this->m_fragmentsToDeactivate.insert(fragId);
    }

  /**\brief Process the neighborhood of one or more event endpoints.
    *
    * When this method is called, m_ring contains a CCW-ordered list
    * of fragments incident to the sweepline position.
    */
  void processQueue()
    {
    std::cout << "Neighborhood::processQueue()\n";

    // I. Merge regions associated with neighboring fragments.
    //    This also marks one co-edge of the pair with the "next"
    //    fragment in the loop bounding a region.

    if (!this->m_ring.empty())
      { // Note that ringA == ringB is valid (both sides of fragment are the same regionId).
      std::list<FragmentId>::iterator ringA = this->m_ring.end();
      --ringA; // "unadvance" before end() to the last ring entry.
      std::list<FragmentId>::iterator ringB = this->m_ring.begin();
      // Start by processing the implicit fragment-pair between m_ring.end() and m_ring.begin():
      this->assignAndMergeRegions(ringA, ringB);
      // Now proceed through the list until we have visited them all.
      ringA = ringB;
      for (++ringB; ringB != this->m_ring.end(); ++ringA, ++ringB /*, sao = -sbo??? */)
        {
        this->assignAndMergeRegions(ringA, ringB);
        }
      }

#if 0
    // Debug printout
    std::list<FragmentId>::iterator rit;
    for (rit = this->m_ring.begin(); rit != this->m_ring.end(); ++rit)
      {
      EdgeFragment& frag((*this->m_fragments)[*rit]);
      std::cout
        << "  " << frag.lo().x()/1182720.0 << " " << frag.lo().y()/1182720.0
        << " -- " << frag.hi().x()/1182720.0 << " " << frag.hi().y()/1182720.0
        << "  " << frag.m_edge.name() << ", seg " << frag.m_segment
        << "\n";
      }
#endif // 0

    // II. We are done processing the ring; if any incident edges are outgoing,
    //     add their SEGMENT_END events to the event queue.
    std::vector<FragmentId>::iterator it;
    for (it = this->m_fragmentsToQueue.begin(); it != this->m_fragmentsToQueue.end(); ++it)
      {
      this->m_activeEdges->insert(*it);
      EdgeFragment& frag((*this->m_fragments)[*it]);
      this->m_eventQueue->insert(SweepEvent::SegmentEnd(frag.m_hi, *it));
      // TODO: Check for neighbor intersections; remove them then check for neighbor intersections with *it and add them.
      }
    this->m_fragmentsToQueue.clear();
    this->m_ring.clear();

    // III. Remove active edges going out of scope after the neighborhood
    //      has been visited.
    while (!this->m_fragmentsToDeactivate.empty())
      {
      std::set<FragmentId>::iterator fragIt = this->m_fragmentsToDeactivate.begin();
      this->m_activeEdges->erase(*fragIt);
      this->m_fragmentsToDeactivate.erase(fragIt);
      }
    }

  /**\brief Advance the sweepline to the next event's point.
    *
    * This may do nothing if the next event is coincident with the current point.
    * This may advance to some position other than \a pt if any queued edge fragments
    * end or cross before \a pt.
    */
  void advanceSweeplineTo(const internal::Point& pt)
    {
    if (this->m_point->m_position != pt)
      {
      // Now it is safe to add edges which crossed at the previous sweepline point.
      this->processQueue();

      internal::Point tmp = this->m_eventQueue->begin()->point();
      if (tmp.x() < pt.x() || (tmp.x() == pt.x() && tmp.y() < pt.y()))
        {
        this->m_point->advance(tmp);
        return;
        }

      // FIXME!!! Do not do this. Consider newly inserted end/crossing events created by processQueue!
      this->m_point->advance(pt);
      }
    }

  void dumpRegions()
    {
    FragmentArray::const_iterator fit;
    std::cout << "\nFragments\n";
    std::size_t i = 0;
    for (fit = this->m_fragments->begin(); fit != this->m_fragments->end(); ++fit, ++i)
      {
      std::cout << "  " << i << " ";
      fit->dump(this->m_regionIds);
      }
    std::cout << "\nRegions\n";
    std::set<RegionId> found = this->m_regionIds.roots();
    for (std::set<RegionId>::const_iterator rit = found.begin(); rit != found.end(); ++rit)
      {
      std::cout << "  Region " << *rit;
      smtk::shared_ptr<Region> regRec = this->m_regions[*rit];
      if (regRec)
        {
        std::cout << " seed frag " << regRec->m_seedFragment << " sense " << regRec->m_seedSense << " has " << regRec->m_innerLoops.size() << " holes.\n";
        }
      else
        {
        std::cout << " has no record!\n";
        }
      }
    }
};

#if 0
static void AddLoopsForEdge(
  CreateFaces* op,
  ModelEdgeMap& modelEdgeMap,
  ModelEdgeMap::iterator edgeInfo,
  LoopsById& loops,
  smtk::model::VertexSet& visitedVerts,
  std::map<internal::Point, int>& visitedPoints // number of times a point has been encountered (not counting periodic repeat at end of a single-edge loop); used to identify points that must be promoted to model vertices.
)
{
  if (!edgeInfo->first.isValid() || !op)
    {
    return; // garbage-in? garbage-out.
    }
  internal::EdgePtr edgeRec = op->findStorage<internal::edge>(edgeInfo->first.entity());

  smtk::model::Vertices endpts = edgeInfo->first.vertices();
  if (endpts.empty())
    { // Tessellation had better be a periodic loop. Traverse for bbox.
    //AddEdgePointsToBox(tess, box);
    }
  else
    { // Choose an endpoint and walk around the edge.
    }
}
#endif // 0

void DumpEventQueue(const char* msg, SweepEventSet& eventQueue)
{
  std::cout << ">>>>>   " << msg << "\n";
  std::cout << ">>>>>   Event Queue:\n";
  SweepEventSet::iterator it;
  for (it = eventQueue.begin(); it != eventQueue.end(); ++it)
    {
    std::cout << "  " << it->type() << ": " << it->point().x() << ", " << it->point().y() << "\n";
    }
  std::cout << "<<<<<   Event Queue\n";
}

smtk::model::OperatorResult CreateFaces::operateInternal()
{
  // Discover how the user wants to specify scaling.
  smtk::attribute::IntItem::Ptr constructionMethodItem = this->findInt("construction method");
  int method = constructionMethodItem->discreteIndex(0);

  smtk::attribute::DoubleItem::Ptr pointsItem = this->findDouble("points");
  smtk::attribute::IntItem::Ptr coordinatesItem = this->findInt("coordinates");
  smtk::attribute::IntItem::Ptr offsetsItem = this->findInt("offsets");

  smtk::attribute::ModelEntityItem::Ptr edgesItem = this->findModelEntity("edges");

  smtk::attribute::ModelEntityItem::Ptr modelItem = this->specification()->associations();
  smtk::model::Model model;

  internal::pmodel::Ptr storage; // Look up from session = internal::pmodel::create();
  bool ok = true;

  Session* sess = this->polygonSession();
  smtk::model::ManagerPtr mgr;
  if (!sess || !(mgr = sess->manager()))
    {
    // error logging requires mgr...
    return this->createResult(smtk::model::OPERATION_FAILED);
    }
  // Keep a set of model edges marked by the directions in which they
  // should be used to form faces. This will constrain what faces
  // may be created without requiring users to pick a point interior
  // to the face.
  //
  // This way, when users specify oriented (CCW) point sequences or
  // a preferred set of edges as outer loop + inner loops, we don't
  // create faces that fill the holes.
  // But when users specify that all possible faces should be created,
  // they don't have to pick interior points.
  //
  // -1 = use only negative orientation
  //  0 = no preferred direction: use in either or both directions
  // +1 = use only positive orientation
  ModelEdgeMap modelEdgeMap;

  // First, collect or create edges to process:
  // These case values match CreateFaces.sbt indices (and enum values):
  switch (method)
    {
  case 0: // points, coordinates, offsets
      {
      // identify pre-existing model vertices from points
      // verify that existing edges/faces incident to model vertices
      //        do not impinge on proposed edge/face
      // run edge-creation pre-processing on each point-sequence?
      // determine sub-sequences of points that will
      //   (a) form new edges
      //   (b) make use of existing edges (with orientation)
      // determine loop nesting and edge splits required by intersecting loops
      // report point sequences, model vertices (existing, imposed by intersections, non-manifold), loops w/ nesting
      // ---
      // create new vertices as required
      // create edges on point sequences
      // modify/create vertex uses
      // create chains
      // create edge uses
      // create loops
      // create faces
      }
    break;
  case 1: // edges, points, coordinates
      {
      // for each edge
      //   for each model vertex
      //     walk loops where vertices have no face, aborting walk if an unselected edge is found.
      //     mark traversed regions and do not re-traverse
      //   OR IF NO MODEL VERTICES
      //     edge must be periodic and oriented properly... treat it as a loop to bound a hole+/^face-filling-the-hole.
      //     mark traversed regions and do not re-traverse
      //   determine loop nesting and edge splits required by intersecting loops
      //   report model vertices (imposed by intersections, non-manifold), loops w/ nesting
      // ---
      // create new vertices as required
      // modify vertex uses
      // create edge uses
      // create loops
      // create faces
      }
    break;
  case 2: // all non-overlapping
      {
      model = modelItem->value(0);
      smtk::model::Edges allEdges =
        model.cellsAs<smtk::model::Edges>();
      for (smtk::model::Edges::const_iterator it = allEdges.begin(); it != allEdges.end(); ++it)
        {
        modelEdgeMap[*it] = 0;
        }
      // Same as case 1 but with the set of all edges in model.
      //
      // Create a union-find struct
      // for each "model" vertex
      //   for each edge attached to each vertex
      //     add 2 union-find entries (UFEs), 1 per co-edge
      //     merge adjacent pairs of UFEs
      //     store UFEs on edges
      // For each loop, discover nestings and merge UFEs
      // For each edge
      //   For each unprocessed (nesting-wise) UFE
      //     Discover nesting via ray test
      //     Merge parent and child UFEs (if applicable)
      //     Add an (edge, coedge sign) tuple to a "face" identified by the given UFE
      // FIXME: Test for self-intersections?
      // FIXME: Deal w/ pre-existing faces?
      }
    break;
  default:
    ok = false;
    smtkInfoMacro(log(), "Unhandled construction method " << method << ".");
    break;
    }

  // Create an event queue and populate it with events
  // for each segment of each edge in modelEdgeMap.
  ModelEdgeMap::iterator modelEdgeIt;
  SweepEventSet eventQueue; // (QE) sorted into a queue by point-x, point-y, event-type, and then event-specific data.
  for (modelEdgeIt = modelEdgeMap.begin(); modelEdgeIt != modelEdgeMap.end(); ++modelEdgeIt)
    {
    std::cout << "Consider " << modelEdgeIt->first.name() << "\n";
    internal::EdgePtr erec =
      this->findStorage<internal::edge>(
        modelEdgeIt->first.entity());

    if (erec->pointsSize() < 2)
      continue; // Do not handle edges with < 2 points.

    internal::PointSeq::const_iterator pit = erec->pointsBegin();
    int seg = 0;
    internal::Point last = *pit;
    for (++pit; pit != erec->pointsEnd(); ++pit, ++seg)
      {
      eventQueue.insert(SweepEvent::SegmentStart(last, *pit, modelEdgeIt->first, seg));
      //eventQueue.insert(SweepEvent::SegmentEnd(*pit, modelEdgeIt->first, seg - 1));
      last = *pit;
      }
    }
  DumpEventQueue( "Initial", eventQueue);

  // The first event in eventQueue had better be a segment-start event.
  // So the first thing this event-loop should do is start processing edges.
  // As other edges are added, they must intersect all active edges
  // and add split events as required.
  std::set<SweepEvent>::iterator event;
  std::vector<SweepEvent> edgesToInsertAfterAdvance; // FIXME. Needed?
  FragmentArray fragments; // (FR)
  fragments.reserve(static_cast<size_t>(eventQueue.size() * 1.125)); // pre-allocate some space for additional segments

  internal::Point startPoint = eventQueue.begin()->point();
  startPoint.x(startPoint.x() - 1);
  SweeplinePosition sweepPosn(startPoint);
  ActiveFragmentTree activeEdges(
    EdgeFragmentComparator(fragments, sweepPosn)); // (IT)
  Neighborhood neighborhood(sweepPosn, fragments, eventQueue, activeEdges); // N(x)

  // Set the initial sweepline to before the beginning of the queue.
  for (
    event = eventQueue.begin();
    (event = eventQueue.begin()) != eventQueue.end();
    )
    {
    neighborhood.advanceSweeplineTo(event->point());
    event = eventQueue.begin(); // Advancing the sweepline may have changed the eventQueue.
    std::cout
      << "Event " << event->type() << " posn " << event->point().x() << " " << event->point().y()
      ;
    /*
    if (event->type() == SweepEvent::SEGMENT_START)
      {
      std::cout << " edge " << event->m_edge.entity().toString() << " seg " << event->m_indx << "\n";
      }
    else
      {
      std::cout
        << " fragment " << event->m_frag[0]
        << " (edge " << fragments[event->m_frag[0]].m_edge.entity().toString() << " seg " << fragments[event->m_frag[0]].m_segment << ")"
        << "\n";
      }
      */
    switch (event->type())
      {
    case SweepEvent::SEGMENT_START:
      this->processSegmentStart(*event, fragments, sweepPosn, activeEdges, edgesToInsertAfterAdvance, neighborhood);
      // Add to active edges:
      //   Test for intersection with existing edges
      //     If any, add SEGMENT_CROSS events.
      //   Add to list in proper place
      // If the edge is neighbors others in the active list, either:
      //   a. Add
      break;
    case SweepEvent::SEGMENT_END:
      this->processSegmentEnd(*event, fragments, neighborhood);
      break;
    case SweepEvent::SEGMENT_CROSS:
      this->processSegmentCross(*event, fragments, sweepPosn, activeEdges, edgesToInsertAfterAdvance, neighborhood);
      break;
      }

    // The event is processed; remove it.
    eventQueue.erase(event);
    // Now if the queue is empty, advance the sweepline just past the current point in order
    // to process the neighborhood (which may add events to the queue).
    if (eventQueue.empty())
      {
      neighborhood.processQueue();
      }
    }

  // Dump report of regions discovered and chains bounding regions.
  neighborhood.dumpRegions();

  // Create vertex-use, chain, edge-use, loop, and face records
  smtk::model::OperatorResult result;
  if (ok)
    {
    result = this->createResult(smtk::model::OPERATION_SUCCEEDED);
    //this->addEntityToResult(result, model, CREATED);
    }

  if (!result)
    {
    result = this->createResult(smtk::model::OPERATION_FAILED);
    }

  return result;
}

void CreateFaces::processNeighborhood(
  Neighborhood& n,
  RegionDefinitions& regions,
  RegionIdSet& regionIds)
{
}

void CreateFaces::processSegmentStart(
  const SweepEvent& event,
  FragmentArray& fragments,
  SweeplinePosition& sweepPosn,
  ActiveFragmentTree& activeEdges,
  SweepEventArray& edgesToInsertAfterAdvance,
  Neighborhood& n)
{
  // Create output fragment for new segment.
  // The m_hi point is altered as segment crossing are processed but the
  // region IDs of this segment will not change. The regions will be
  // unioned with other regions depending on neighborhood adjacency.
  static EdgeFragment blank;
  FragmentArray::size_type fragId = fragments.size();
  FragmentArray::iterator it = fragments.insert(fragments.end(), blank);
  it->m_edge = event.m_edge;
  it->m_segment = event.m_indx;
  it->m_edgeData = this->findStorage<internal::edge>(it->m_edge.entity());
  it->m_edgeData->pointsOfSegment(event.m_indx, it->m_lo, it->m_hi);
  it->m_sense = event.m_frag[0] > 0 ? true : false;
  if (it->m_lo > it->m_hi)
    {
    if (it->m_sense) { std::cout << "\nOoops, reversed frag sense\n\n"; }
    std::swap(it->m_lo, it->m_hi);
    }
  else if (!it->m_sense) { std::cout << "\nOoops, non-reversed frag sense\n\n"; }
  it->m_regionId[0] = it->m_regionId[1] = -1; // Indicate regions are unassigned.

  // Tell neighborhood:
  //   to insert fragment into incident edge ring
  //   to insert SEGMENT_END into activeEdges after neighborhood processed
  //      this will also trigger insertion of SEGMENT_CROSS events
  n.insertFragment(fragId, *it, it->m_hi);
  n.queueActiveEdge(fragId, *it);

  // Locate insertion point in activeEdges
  // Insert end event
  //   eventQueue.insert(SweepEvent::SegmentEnd(*pit, modelEdgeIt->first, seg - 1));
  // Insert fragment into neighborhood (and tell neighborhood to add it to activeEdges at end of processing)
  // Determine if/where fragment intersects neighbors in activeEdges
  // Insert cross events
}

void CreateFaces::processSegmentEnd(
  const SweepEvent& event,
  FragmentArray& fragments,
  Neighborhood& n)
{
  FragmentId fragId = event.m_frag[0];
  EdgeFragment& frag(fragments[fragId]);

  // Add fragment to neighborhood
  n.insertFragment(fragId, frag, frag.m_lo);

  // Find neighbors of fragment in activeEdges
  // Remove fragment from activeEdges
  // If neighbors intersect, add crossing to event queue
  n.removeActiveEdge(fragId);
}

void CreateFaces::processSegmentCross(
  const SweepEvent& event,
  FragmentArray& fragments,
  SweeplinePosition& sweepPosn,
  ActiveFragmentTree& activeEdges,
  SweepEventArray& edgesToInsertAfterAdvance,
  Neighborhood& n)
{
  // Say fragment s and t intersect at x with s < t to the left of x.
  //
  // Be careful not to put activeEdges into an invalid state by either
  // + advancing the sweep position before removing fragments s and t.
  // + inserting new fragments before advancing sweep position.
  //
  // Advance sweepline before queueing new intersections...
  // except we can't guarantee that there aren't more events at
  // this sweep location.
  // So, we have the neighborhood add fragments to the "right" of x to activeEdges
  // during processNeighborhood.
  /*
  // If segment r exists and intersects s, remove r-s cross event
  if (edgeR.isValid())
    {
    SweepEvent::RemoveCrossing(queue, fragR, fragS);
    neighborhood.queueCrossing(edgeR, segR, edgeT, segT);
    }
  // If segment u exists and intersects t, remove t-u cross event
  if (edgeU.isValid())
    {
    SweepEvent::RemoveCrossing(queue, fragT, fragU);
    neighborhood.queueCrossing(edgeS, segS, edgeU, segU);
    }
  // If segment r exists and intersects t, add r-t cross event
  // If segment u exists and intersects s, add s-u cross event
  */
  for (int i = 0; i < 2; ++i)
    {
    }
  //---
  // For each intersecting fragment,
  //   If intersection is not at endpoint,
  //     Create new fragment (cross_pt to fragment_hi)
  //     Modify fragment_hi to be cross_pt
  //     Insert new fragment start event and end event
  //     Insert new fragment into activeEdges
  //     Insert new fragment into neighborhood
  //  Remove existing intersections of segment with existing neighbors
}

    } // namespace polygon
  } //namespace bridge
} // namespace smtk

smtkImplementsModelOperator(
  SMTKPOLYGONSESSION_EXPORT,
  smtk::bridge::polygon::CreateFaces,
  polygon_create_faces,
  "create faces",
  CreateFaces_xml,
  smtk::bridge::polygon::Session);
