//=============================================================================
// 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/bridge/polygon/internal/Util.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.
  RegionId 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.
  int m_marked[2]; // Has this co-edge been output?

  EdgeFragment()
    {
    for (int i = 0; i < 2; ++i)
      {
      this->m_regionId[i] = -1;
      this->m_marked[i] = 0;
      this->m_next[i] = -1;
      }
    }

  smtk::model::Edge edge() const { return this->m_edge; }
  bool orientation() const { return this->m_sense; }

  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]; }
  RegionIdSet::value_type upperRegion() const { return this->m_regionId[1]; }
  /// Return the ID of the region below the fragment.
  RegionIdSet::value_type& lowerRegion() { return this->m_regionId[0]; }
  RegionIdSet::value_type lowerRegion() const { 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.
    *
    * You can also think of \a fromLowerEnd as representing the
    * orientation of the co-fragment you wish to consider;
    * calling ccwRegion(false) returns ID of the region to the
    * left of the reversed co-fragment (from hi() to lo()) while
    * calling ccwRegion(true) returns ID of the region to the
    * left of the forward co-fragment (from lo() to hi()).
    */
  RegionIdSet::value_type& ccwRegion(bool fromLowerEnd) { return this->m_regionId[fromLowerEnd ? 1 : 0]; }
  RegionIdSet::value_type ccwRegion(bool fromLowerEnd) const { 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]; }
  RegionIdSet::value_type cwRegion(bool fromLowerEnd) const { 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]; }

  /// Mark a co-fragment as visited (or not).
  void mark(bool orientation, int markVal)
    {
    this->m_marked[orientation ? 1 : 0] = markVal;
    }

  /// Return the markings on the forward (orientation true) or backward (false) co-fragment.
  int marked(bool orientation) const
    {
    return this->m_marked[orientation ? 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;

typedef std::vector<std::pair<smtk::model::Edge,bool> > OrientedEdges;

/**\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,
    smtk::model::Manager::Ptr mgr)
    : m_point(&x),
      m_fragments(&fragments),
      m_eventQueue(&eventQueue),
      m_activeEdges(&active),
      m_mgr(mgr)
    {
    }

  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
  std::set<std::pair<RegionId,RegionId> > m_related; // regions that may be disconnected siblings or parent/child.
  smtk::model::Manager::Ptr m_mgr;

  /// Return the region ID neighboring a fragment from above.
  RegionId lowerRegionJustAbove(FragmentId frag)
    {
    ActiveFragmentTree::iterator edgeNeighbor =
      this->m_activeEdges->upper_bound(frag);
    if (edgeNeighbor == this->m_activeEdges->end())
      return -1;
    return (*this->m_fragments)[*edgeNeighbor].lowerRegion();
    }

  /// Return the region ID neighboring a fragment from below.
  RegionId upperRegionJustBelow(FragmentId frag)
    {
    ActiveFragmentTree::iterator edgeNeighbor =
      this->m_activeEdges->lower_bound(frag);
    if (edgeNeighbor != this->m_activeEdges->end())
      { // We found the edge or the edge wasn't active but we have an immediate neighbor above.
      if (edgeNeighbor == this->m_activeEdges->begin())
        { // The edge has no neighbor below:
        return -1;
        }
      --edgeNeighbor;
      return (*this->m_fragments)[*edgeNeighbor].upperRegion();
      }
    // The edge is not active and there's no edge above it.
    // Thus, if any edges are active, the topmost one is
    // just below \a frag.
    if (this->m_activeEdges->empty())
      return -1;
    // Not empty => m_activeEdges->rbegin() is valid:
    return (*this->m_fragments)[*this->m_activeEdges->rbegin()].upperRegion();
    }

  /**\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();
    }

/// Relate a region between 2 fragments A & B which share a vertex x to neighborhoods just before and after x.
  void relateNeighborhoods(
    FragmentId fA, EdgeFragment& fragA, bool isOutA,
    FragmentId fB, EdgeFragment& fragB, bool isOutB,
    RegionId region)
    {
    // NB: Inside this method, the vertex "x" shared by fragments A and B
    //     is referred to as "o" (their common origin).

    // Determine whether this pair of fragments crosses +y or -y,
    // which informs us of which regions border the neighborhood
    // and are identical with disjoint boundary curves.
    static internal::Coord yy[2] = { 0, 1 };
    internal::Coord oa[2];
    internal::Coord ob[2];
    oa[0] = (fragA.hi().x() - fragA.lo().x()) * (isOutA ? +1 : -1);
    oa[1] = (fragA.hi().y() - fragA.lo().y()) * (isOutA ? +1 : -1);
    ob[0] = (fragB.hi().x() - fragB.lo().x()) * (isOutB ? +1 : -1);
    ob[1] = (fragB.hi().y() - fragB.lo().y()) * (isOutB ? +1 : -1);

    internal::HighPrecisionCoord oaXyy = cross2d(oa, yy);
    internal::HighPrecisionCoord yyXob = cross2d(yy, ob);
    internal::HighPrecisionCoord oaXob = cross2d(oa, ob);

    // oaXyy * yyXob is positive when all three edges are in CCW order
    // and oa-ob is acute or obtuse but not reflex (oaXob > 0).
    if (oaXyy * yyXob > 0)
      {
      if (oaXyy > 0)
        { // Fragment B is incoming and bounded above by a fragment whose lower region should be merged with idB
        RegionId other = this->lowerRegionJustAbove(fB);
        this->m_related.insert(std::pair<RegionId,RegionId>(region, other));
        }
      else // (oaXyy < 0)
        { // Fragment A is incoming and bounded below by a fragment whose upper region should be merged with idA
        RegionId other = this->upperRegionJustBelow(fA);
        this->m_related.insert(std::pair<RegionId,RegionId>(region, other));
        }
      }
    else if (oaXyy * yyXob < 0)
      {
      if (oaXob > 0)
        {
        // Acute/obtuse angle between A & B; do nothing.
        }
      else // (oaXob <= 0)
        {
        // Reflex angle between A & B; both neighborhoods (above and below) encompassed.
        // In the case of oaXyy > 0, both edges are outgoing (and thus not in activeSegments yet)
        // but lookup using the origin ("o") and either slope (A or B) is OK because there
        // cannot be any incoming edges. So, we perform the lookups using edge that are correct
        // for the oaXyy < 0 case (where A and B are both incoming and the above/below lookups
        // would be incorrect if we swap A and B).
        if (oaXob == 0 && (fA != fB || this->m_ring.size() > 1))
          {
          smtkWarningMacro(this->m_mgr->log(),
            "Neighborhood of edge fragment is invalid. Expect invalid results.");
          }
        RegionId above = this->lowerRegionJustAbove(fB);
        RegionId below = this->upperRegionJustBelow(fA);
        this->m_related.insert(std::pair<RegionId,RegionId>(region, above));
        this->m_related.insert(std::pair<RegionId,RegionId>(region, below));
        }
      }
    else // (oaXyy * yyXob == 0)
      {
      if (oaXob < 0) // A & B reflex
        {
        // Neighborhood is directly connected by an edge to previous or next
        // neighborhood (hence oaXyy*yyXob == 0), but the A-B region also
        // spans the other neighborhood boundary when A & B are reflex (oaXob < 0)
        // so we must mark the region below or above it.
        RegionId other;
        if (oaXyy > 0 || yyXob > 0)
          {
          // Either:
          //     oaXyy > 0 and thus fragB must be along -y (since oaXob < 0),
          // or  yyXob > 0 and thus fragA must be along -y (since oaXob < 0);
          // thus A-B merges with the region just below: the active segment just above B
          other = this->lowerRegionJustAbove(fB);
          }
        else // (oxXyy < 0 || yyXob < 0)
          {
          // Either:
          //     oaXyy < 0 and thus fragB must be along +y (since oaXob < 0),
          // or  yyXob < 0 and thus fragA must be along +y (since oaXob < 0);
          // thus A-B merges with the region just above: the active segment just below A
          other = this->upperRegionJustBelow(fA); // when oaXyy == 0, fA isn't in m_activeSegments yet, but the lookup is safe).
          }
        this->m_related.insert(std::pair<RegionId,RegionId>(region, other));
        }
      else if (oaXob == 0)
        {
        // A & B are 0 or pi **and** aligned with y axis.
        // We can use outgoing/incoming to decide whether they are up (+y, outgoing)
        // or down (-y, incoming). If both are the same direction, then the opposite
        // region should be linked to this region.
        if (isOutA && isOutB)
          { // Both outgoing, link to region below
          RegionId below = this->lowerRegionJustAbove(fA);
          this->m_related.insert(std::pair<RegionId,RegionId>(region, below));
          }
        else if (!isOutA && !isOutB)
          {
          RegionId above = this->upperRegionJustBelow(fA);
          this->m_related.insert(std::pair<RegionId,RegionId>(region, above));
          }
        }
      }
    }

  void mergeRelated()
    {
    std::set<std::pair<RegionId,RegionId> >::iterator relIt;
    for (relIt = this->m_related.begin(); relIt != this->m_related.end(); ++relIt)
      {
      this->m_regionIds.mergeSets(relIt->first, relIt->second);
      }
    }

  /// 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.find(winner) == this->m_regions.end())
        {
        this->m_regions[winner] = smtk::make_shared<Region>(*ringB, !isOutB);
        }
      if (this->m_regions.find(loser) != this->m_regions.end())
        {
        this->m_regions[winner]->merge(this->m_regions[loser].get());
        this->m_regions.erase(loser);
        }
      }
    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;

    this->relateNeighborhoods(*ringA, fragA, isOutA, *ringB, fragB, isOutB, winner);
    /*
    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);
    internal::HighPrecisionCoord oaXob = cross2d(oa, ob);
    if (
      (oaXoo > 0 && ooXob > 0) || // oaXob < pi and "other" is between them; or...
      (oaXob < 0 && !(ooXob < 0 && oaXoo < 0))) // oaXob > pi and "other" is *not between* the short CCW path between B and A.
      { // 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 " << fragId << " 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

    // 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);
      }

    // 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();
    }

  /**\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";
#if 0
    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";
        }
      }
#else // 0
    std::set<RegionId> found = this->m_regionIds.roots();
    std::cout << "Top-level:";
    for (std::set<RegionId>::const_iterator rit = found.begin(); rit != found.end(); ++rit)
      {
      std::cout << " " << this->m_regionIds.find(*rit);
      }
    std::cout << "\n";
    for (RegionId x = 0; x < static_cast<RegionId>(this->m_fragments->size() * 2); ++x)
      {
      if (this->m_regions.find(x) != this->m_regions.end())
        {
        smtk::shared_ptr<Region> regRec = this->m_regions[x];
        if (regRec)
          {
          std::cout << "  Region " << x;
          std::cout << " seed frag " << regRec->m_seedFragment << " sense " << regRec->m_seedSense << "\n";//" has " << regRec->m_innerLoops.size() << " holes.\n";
          }
        }
      }
#endif // 0
    }

  void traverseLoop(OrientedEdges& result, std::set<RegionId>& neighborRegions, FragmentId fragId, bool orientation)
    {
    result.clear();
    neighborRegions.clear();

    FragmentId fragStart = fragId;
    bool orientStart = orientation;
    EdgeFragment* frag = &((*this->m_fragments)[fragId]);
    RegionId lr = this->m_regionIds.find(frag->ccwRegion(orientStart));
    std::cout << "   ";
    do
      {
      frag->mark(orientation, 1);
      result.push_back(std::make_pair(frag->edge(), orientation ^ frag->orientation()));
      neighborRegions.insert(this->m_regionIds.find(frag->ccwRegion(!orientation)));
      fragId = frag->nextFragment(orientation);
      std::cout << " " << fragId;
      if (fragId == -1)
        break;
      frag = &((*this->m_fragments)[fragId]);
      RegionId nextRegion = this->m_regionIds.find(frag->ccwRegion(false));
      orientation = nextRegion == lr ? false : true;
      std::cout << (orientation ? "+" : "-");
      }
    while ((fragId != fragStart || orientation != orientStart) && !frag->marked(orientation)); // stop infinity on buggy edges
    std::cout << "\n";
    }

  void dumpLoop(OrientedEdges& loopEdges, std::set<RegionId>& neighborRegions)
    {
    std::cout << "Loop with neighbors ";
    std::ostream_iterator<RegionId> out_reg(std::cout, "  ");
    std::copy (neighborRegions.begin(), neighborRegions.end(), out_reg);
    std::cout << "\n";

    for (OrientedEdges::const_iterator oe = loopEdges.begin(); oe != loopEdges.end(); ++oe)
      {
      if (oe->first.vertices().empty())
        {
        std::cout << "  " << "periodic  " << oe->first.name() << "\n";
        }
      else
        {
        model::Vertices endpts = oe->first.vertices();
        double* a = endpts[endpts.size() == 1 ? 0 : (oe->second ? 0 : 1)].coordinates();
        double* b = endpts[endpts.size() == 1 ? 0 : (oe->second ? 1 : 0)].coordinates();
        std::cout << "  " << a[0] << " " << a[1] << " -- " << b[0] << " " << b[1] << "  " << oe->first.name() << "\n";
        }
      }
    }

  // Try generating output faces.
  void dumpRegions2()
    {
    FragmentArray::const_iterator fit;
    std::cout << "\nCreepy crawler\n";
    fit = this->m_fragments->begin();
    // The left/lower region of the first fragment to be inserted is always exterior
    // to all faces. It corresponds to a "hole" cut in the infinite plane of all fragments.
    RegionId outside = this->m_regionIds.find(fit->lowerRegion());

    // Traverse every fragment. For each unprocessed coedge, if the region is equivalent
    // to outside, queue the other coedge (if unprocessed) as an output face.
    OrientedEdges loopEdges;
    std::set<RegionId> neighborRegions;
    FragmentId fid = 0;
    for (fit = this->m_fragments->begin(); fit != this->m_fragments->end(); ++fit, ++fid)
      {
      std::cout << "Fragment " << fid << "-\n";
      if (!fit->marked(false) && this->m_regionIds.find(fit->ccwRegion(false)) != outside)
        {
        this->traverseLoop(loopEdges, neighborRegions, fid, false);
        this->dumpLoop(loopEdges, neighborRegions);
        }
      std::cout << "Fragment " << fid << "+\n";
      if (!fit->marked(true) && this->m_regionIds.find(fit->ccwRegion(true)) != outside)
        {
        this->traverseLoop(loopEdges, neighborRegions, fid, true);
        this->dumpLoop(loopEdges, neighborRegions);
        }
      std::cout << "\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, mgr); // 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 type " <<
      (event->type() == SweepEvent::SEGMENT_START ? "START" :
        (event->type() == SweepEvent::SEGMENT_END ? "END" : "CROSS"))
      << " posn " << event->point().x()/2.31e13 << " " << event->point().y()/2.31e13 << "\n"
      ;
    /*
    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();
      }
    }

  // Now we have a single loop for each region, obtainable by
  // starting with a Region's m_seedFragment and traversing
  // the m_next entry of that and each successive fragment.
  // Disjoint regions that should be joined are in m_related
  // and these may indicate that the loops are siblings to each
  // other or parent and child.

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

  // 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);
