[Boost-commit] svn:boost r63407 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test

Subject: [Boost-commit] svn:boost r63407 - in sandbox/SOC/2010/sweepline: boost/sweepline boost/sweepline/detail libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-28 11:04:39

Author: asydorchuk
Date: 2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
New Revision: 63407
URL: http://svn.boost.org/trac/boost/changeset/63407

Log:
Fixed errors and compile warnings using gcc-3.4.4 and gcc-4.3.4 compilers.
Added output post processing (removing zero length edges).
Updated output structure, moved output from detail namespace.
Updated unit tests for voronoi builder.
Added:
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp   (contents, props changed)
Text files modified: 
   sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp |   384 +++++++-------------------------------- 
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp          |   105 +++++-----                              
   sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2               |     8                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp     |    30 +-                                      
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp     |    86 ++++----                                
   sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp   |   133 +++++++------                           
   sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp       |     6                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp |   232 ++++++++++++++---------                 
   8 files changed, 403 insertions(+), 581 deletions(-)

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/detail/voronoi_formation.hpp	2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -23,12 +23,6 @@
     // VORONOI EVENT TYPES ////////////////////////////////////////////////////
     ///////////////////////////////////////////////////////////////////////////
 
-    template <typename T>
-    struct site_event;
-    
-    template <typename T>
-    struct circle_event;
-
     template <typename Point2D>
     struct beach_line_node;
 
@@ -38,87 +32,21 @@
     template <typename BeachLineNode>
     struct node_comparer;
 
-    // Point in 2D space data structure. Comparators defined in this
-    // data structure actually define sweepline movement direction.
-    template <typename T>
-    struct point_2d {
-    public:
-        typedef T coordinate_type;
-        typedef site_event<T> site_event_type;
-        typedef circle_event<T> circle_event_type;
-
-        point_2d() {}
-
-        point_2d(T x, T y) {
-            x_ = x;
-            y_ = y;
-        }
-
-        bool operator==(const point_2d &point) const {
-            return (this->x_ == point.x()) && (this->y_ == point.y());
-        }
-
-        bool operator!=(const point_2d &point) const {
-            return (this->x_ != point.x()) || (this->y_ != point.y());
-        }
-
-        // This comparator actually defines sweepline movement direction.
-        bool operator<(const point_2d &point) const {
-            // Sweepline sweeps from left to right.
-            if (this->x_ != point.x_)
-                return this->x_ < point.x_;
-            return this->y_ < point.y_;
-        }
-
-        bool operator<=(const point_2d &point) const {
-            return !(point < (*this));
-        }
-
-        bool operator>(const point_2d &point) const {
-            return point < (*this);
-        }
-
-        bool operator>=(const point_2d &point) const {
-            return !((*this) < point);
-        }
-
-        coordinate_type x() const {
-            return this->x_;
-        }
-
-        coordinate_type y() const {
-            return this->y_;
-        }
-
-        void x(coordinate_type x) {
-            x_ = x;
-        }
-
-        void y(coordinate_type y) {
-            y_ = y;
-        }
-
-    private:
-        coordinate_type x_;
-        coordinate_type y_;
-    };
-
-    template <typename T>
-    point_2d<T> make_point_2d(T x, T y) {
-        return point_2d<T>(x,y);
-    }
-
     // Site event type. 
     // Occurs when sweepline sweeps over one of the initial sites.
     // Contains index of a site below the other sorted sites.
-    template <typename T>
+    template <typename Point2D>
     struct site_event {
     public:
-        typedef T coordinate_type;
+        typedef typename Point2D::coordinate_type coordinate_type;
 
         site_event() {}
         
-        site_event(T x, T y, int index) : point_(x, y), site_index_(index) {}
+        site_event(coordinate_type x, coordinate_type y, int index) :
+            point_(x, y), site_index_(index) {}
+
+        site_event(const Point2D &point, int index) :
+            point_(point), site_index_(index) {}
 
         bool operator==(const site_event &s_event) const {
             return point_ == s_event.get_point();
@@ -152,7 +80,7 @@
             return point_.y();
         }
 
-        const point_2d<T> &get_point() const {
+        const Point2D &get_point() const {
             return point_;
         }
 
@@ -161,13 +89,20 @@
         }
 
     private:
-        point_2d<T> point_;
+        Point2D point_;
         int site_index_;
     };
 
-    template <typename T>
-    site_event<T> make_site_event(T x, T y, int index) {
-        return site_event<T>(x, y, index);
+    template <typename Point2D>
+    site_event<Point2D> make_site_event(typename Point2D::coordinate_type x,
+                                        typename Point2D::coordinate_type y,
+                                        int index) {
+        return site_event<Point2D>(x, y, index);
+    }
+
+    template <typename Point2D>
+    site_event<Point2D> make_site_event(const Point2D &point, int index) {
+        return site_event<Point2D>(point, index);
     }
 
     // Circle event type. Occurs when sweepline sweeps over the bottom point of
@@ -180,19 +115,22 @@
     // Bottom point of the voronoi circle will be defined as (x + sqrt(r), y).
     // Contains reference to the second bisector node (ordered from left to
     // right in the beach line) that creates given circle event.
-    template <typename T>
+    template <typename Point2D>
     struct circle_event {
     public:
-        typedef T coordinate_type;
-        typedef typename beach_line_node< point_2d<T> > Key;
-        typedef typename beach_line_node_data< point_2d<T> > Value;
-        typedef typename node_comparer<Key> NodeComparer;
-        typedef typename std::map< Key, Value, NodeComparer >::const_iterator beach_line_iterator;
+        typedef typename Point2D::coordinate_type coordinate_type;
+        typedef beach_line_node<Point2D> Key;
+        typedef beach_line_node_data<typename Point2D::Edge> Value;
+        typedef node_comparer<Key> NodeComparer;
+        typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
 
         circle_event() {}
 
-        circle_event(T c_x, T c_y, T sqr_r) :
-        center_(c_x, c_y), sqr_radius_(sqr_r) {}
+        circle_event(coordinate_type c_x, coordinate_type c_y, coordinate_type sqr_r) :
+            center_(c_x, c_y), sqr_radius_(sqr_r) {}
+
+        circle_event(const Point2D &center, coordinate_type sqr_r) :
+            center_(center), sqr_radius_(sqr_r) {}
 
         circle_event(const circle_event& c_event) {
             center_ = c_event.center_;
@@ -227,11 +165,11 @@
             if (center_.y() != c_event.y())
                 return false;
 
-            T sqr_dif_x = (center_.x() - c_event.x()) *
-                          (center_.x() - c_event.x());
-            T sum_r_sqr = sqr_radius_ + c_event.sqr_radius_;
-            T value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
-            T value_right = static_cast<T>(4) * sqr_radius_ *
+            coordinate_type sqr_dif_x = (center_.x() - c_event.x()) *
+                                        (center_.x() - c_event.x());
+            coordinate_type sum_r_sqr = sqr_radius_ + c_event.sqr_radius_;
+            coordinate_type value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
+            coordinate_type value_right = static_cast<coordinate_type>(4) * sqr_radius_ *
                             c_event.sqr_radius_;
 
             return value_left == value_right;
@@ -242,17 +180,17 @@
         }
 
         bool operator<(const circle_event &c_event) const {
-            T x1 = center_.x();
-            T y1 = center_.y();
-            T sqr_r1 = sqr_radius_;
-            T x2 = c_event.x();
-            T y2 = c_event.y();
-            T sqr_r2 = c_event.get_sqr_radius();
-
-            T sqr_dif_x = (x1 - x2) * (x1 - x2);
-            T sum_r_sqr = sqr_r1 + sqr_r2;
-            T value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
-            T value_right = static_cast<T>(4) * sqr_r1 * sqr_r2;
+            coordinate_type x1 = center_.x();
+            coordinate_type y1 = center_.y();
+            coordinate_type sqr_r1 = sqr_radius_;
+            coordinate_type x2 = c_event.x();
+            coordinate_type y2 = c_event.y();
+            coordinate_type sqr_r2 = c_event.get_sqr_radius();
+
+            coordinate_type sqr_dif_x = (x1 - x2) * (x1 - x2);
+            coordinate_type sum_r_sqr = sqr_r1 + sqr_r2;
+            coordinate_type value_left = (sum_r_sqr - sqr_dif_x) * (sum_r_sqr - sqr_dif_x);
+            coordinate_type value_right = static_cast<coordinate_type>(4) * sqr_r1 * sqr_r2;
             
             if (x1 > x2) {
                 if (sqr_r2 <= sqr_r1)
@@ -329,10 +267,10 @@
         // If circle point is less then site point return -1.
         // If circle point is equal to site point return 0.
         // If circle point is greater then site point return 1.
-        int compare(const site_event<T> &s_event) const {
+        int compare(const site_event<Point2D> &s_event) const {
             if (s_event.x() < center_.x())
                 return 1;
-            T sqr_dif_x = (s_event.x() - center_.x()) * (s_event.x() - center_.x());
+            coordinate_type sqr_dif_x = (s_event.x() - center_.x()) * (s_event.x() - center_.x());
             if (sqr_dif_x == sqr_radius_) {
                 if (center_.y() == s_event.y())
                     return 0;
@@ -349,11 +287,11 @@
             return center_.y();
         }
 
-        const point_2d<T> &get_center() const {
+        const Point2D &get_center() const {
             return center_;
         }
 
-        const T &get_sqr_radius() const {
+        const coordinate_type &get_sqr_radius() const {
             return sqr_radius_;
         }
 
@@ -361,9 +299,9 @@
             bisector_node_ = iterator;
         }
 
-        void set_sites(const site_event<T> site1,
-                       const site_event<T> site2,
-                       const site_event<T> site3) {
+        void set_sites(const site_event<Point2D> site1,
+                       const site_event<Point2D> site2,
+                       const site_event<Point2D> site3) {
             sites_[0] = site1;
             sites_[1] = site2;
             sites_[2] = site3;
@@ -373,209 +311,30 @@
             return bisector_node_;
         }
 
-        const site_event<T>* get_sites() const {
+        const site_event<Point2D>* get_sites() const {
             return sites_;
         }
 
     private:
-        point_2d<T> center_;
-        T sqr_radius_;
+        Point2D center_;
+        coordinate_type sqr_radius_;
         beach_line_iterator bisector_node_;
-        site_event<T> sites_[3];
-    };
-
-    template <typename T>
-    circle_event<T> make_circle_event(T center_x, T center_y, T sqr_radius) {
-        return circle_event<T>(center_x, center_y, sqr_radius);
-    }
-
-    ///////////////////////////////////////////////////////////////////////////
-    // VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
-    ///////////////////////////////////////////////////////////////////////////
-    
-    template <typename Point2D>
-    struct half_edge;
-
-    // Cell record data structure. Represents voronoi cell.
-    // Contains site point and pointer to any incident half-edge.
-    template <typename Point2D>
-    struct cell_record {
-        half_edge<Point2D> *incident_edge;
-        Point2D site_point;
-
-        cell_record(Point2D site, half_edge<Point2D>* edge) : incident_edge(edge), site_point(site) {}
-    };
-
-    // Voronoi vertex data structure. Represents voronoi vertex.
-    // Contains vertex coordinates and pointers to all incident half-edges.
-    template <typename Point2D>
-    struct vertex_record {
-        std::list< half_edge<Point2D>* > incident_edges;
-        Point2D vertex;
-
-        vertex_record(Point2D vertex) : vertex(vertex) {}
+        site_event<Point2D> sites_[3];
     };
 
-    // Half-edge data structure. Represents voronoi edge.
-    // Contains: 1) pointer to cell records;
-    //           2) pointers to start/end vertices of half-edge;
-    //           3) pointers to previous/next half-edges(CCW);
-    //           4) pointer to twin half-edge.
     template <typename Point2D>
-    struct half_edge {
-        typedef typename cell_record<Point2D> cell_record_type;
-        typedef typename vertex_record<Point2D> vertex_record_type;
-        typedef typename half_edge<Point2D> half_edge_type;
-
-        cell_record_type *cell_record;
-        vertex_record_type *start_point;
-        vertex_record_type *end_point;
-        half_edge_type *prev;
-        half_edge_type *next;
-        half_edge_type *twin;
-
-        half_edge(int site_index) :
-            cell_record(NULL),
-            start_point(NULL),
-            end_point(NULL),
-            prev(NULL),
-            next(NULL),
-            twin(NULL) {}
-    };
+    circle_event<Point2D> make_circle_event(
+        typename Point2D::coordinate_type c_x,
+        typename Point2D::coordinate_type c_y,
+        typename Point2D::coordinate_type sqr_radius) {
+        return circle_event<Point2D>(c_x, c_y, sqr_radius);
+    }
 
-    // Voronoi output data structure based on the half-edges.
-    // Contains vector of voronoi cells, doubly linked list of
-    // voronoi vertices and voronoi edges.
     template <typename Point2D>
-    class voronoi_output {
-    public:
-        typedef typename Point2D::site_event_type site_event_type;
-        typedef typename Point2D::circle_event_type circle_event_type;
-        typedef typename cell_record<Point2D> cell_record_type;
-        typedef typename vertex_record<Point2D> vertex_record_type;
-        typedef typename half_edge<Point2D> edge_type;
-        typedef typename std::vector<cell_record_type> cell_records;
-        typedef typename std::list<vertex_record_type> voronoi_vertices;
-        typedef typename std::list<edge_type *>::const_iterator edge_iterator;
-        typedef typename voronoi_vertices::const_iterator voronoi_vertices_iterator;
-
-        voronoi_output() {}
-
-        // This preserves the validity of iterators.
-        void init(int num_sites) {
-            cell_records_.reserve(num_sites);
-        }
-
-        void reset() {
-            cell_records_.clear();
-            vertex_records_.clear();
-            edges_.clear();
-        }
-
-        // Inserts new half-edge into the output data structure during site
-        // event processing. Takes as input left and right sites of the new
-        // beach line node and returns reference to the new half-edge. 
-        // Second argument is new site. During this step we add two new
-        // twin half-edges.
-        edge_type *insert_new_edge(const site_event_type &site1,
-                                   const site_event_type &site2) {
-            // Get indexes of sites.                                           
-            int site_index1 = site1.get_site_index();
-            int site_index2 = site2.get_site_index();
-
-            // Create new half-edge that belongs to the cell with the first site.
-            edges_.push_back(edge_type(site_index1));
-            edge_type &edge1 = edges_.back();
-
-            // Create new half-edge that belongs to the cell with the second site.
-            edges_.push_back(edge_type(site_index2));
-            edge_type &edge2 = edges_.back();
-
-            // Add initial cell during first edge insertion.
-            if (cell_records_.empty())
-                cell_records_.push_back(cell_record_type(site1.get_point(), &edge1));
-
-            // Second site represents new site during site event processing.
-            // Add new cell to the cell records vector.
-            cell_records_.push_back(cell_record_type(site2.get_point(), &edge2));
-
-            // Update pointers to cells.
-            edge1.cell_record = &cell_records_[site_index1];
-            edge2.cell_record = &cell_records_[site_index2];
-
-            // Update twin pointers.
-            edge1.twin = &edge2;
-            edge2.twin = &edge1;
-
-            return &edge1;
-        }
-
-        edge_type *insert_new_edge(const site_event_type &site1,
-                                   const site_event_type &site2,
-                                   const site_event_type &site3,
-                                   const circle_event_type &circle,
-                                   edge_type *edge12,
-                                   edge_type *edge23) {
-            // Add new voronoi vertex as voronoi circle center.
-            vertex_records_.push_back(vertex_record_type(circle.get_center()));
-            vertex_record_type &new_vertex = vertex_records_.back();
-
-            // Update two input bisectors and their twins half-edges with
-            // new voronoi vertex.
-            edge12->start_point = &new_vertex;
-            edge12->twin->end_point = &new_vertex;
-            edge23->start_point = &new_vertex;
-            edge23->twin->end_point = &new_vertex;
-
-            // Add new half-edge.
-            edges_.push_back(edge_type(site1.get_site_index()));
-            edge_type &new_edge1 = edges_.back();
-            new_edge1.cell_record = &cell_records_[site1.get_site_index()];
-            new_edge1.end_point = &new_vertex;
-
-            // Add new half-edge.
-            edges_.push_back(edge_type(site3.get_site_index()));
-            edge_type &new_edge2 = edges_.back();
-            new_edge2.cell_record = &cell_records_[site3.get_site_index()];
-            new_edge2.start_point = &new_vertex;
-
-            // Update twin pointers of the new half-edges.
-            new_edge1.twin = &new_edge2;
-            new_edge2.twin = &new_edge1;
-
-            // Update voronoi prev/next pointers of all half-edges incident
-            // to the new voronoi vertex.
-            edge12->prev = &new_edge1;
-            new_edge1.next = edge12;
-            edge12->twin->next = edge23;
-            edge23->prev = edge12->twin;
-            edge23->twin->next = &new_edge2;
-            new_edge2.prev = edge23->twin;
-
-            // Update voronoi vertex incident edges pointers.
-            new_vertex.incident_edges.push_back(edge12);
-            new_vertex.incident_edges.push_back(edge23);
-            new_vertex.incident_edges.push_back(&new_edge2);
-            return &new_edge1;
-        }
-
-        const cell_records &get_cell_records() const {
-            return cell_records_;
-        }
-
-        const voronoi_vertices &get_voronoi_vertices() const {
-            return vertex_records_;
-        }
-
-    private:
-        std::vector<cell_record_type> cell_records_;
-        std::list<vertex_record_type> vertex_records_;
-        std::list<edge_type> edges_;
-
-        //Disallow copy constructor and operator=
-        voronoi_output(const voronoi_output&);
-        void operator=(const voronoi_output&);
-    };
+    circle_event<Point2D> make_circle_event(Point2D center,
+        typename Point2D::coordinate_type sqr_radius) {
+        return circle_event<Point2D>(center, sqr_radius);
+    }
 
     ///////////////////////////////////////////////////////////////////////////
     // VORONOI CIRCLE EVENTS QUEUE ////////////////////////////////////////////
@@ -586,7 +345,7 @@
     class circle_events_queue {
     public:
         typedef typename Point2D::coordinate_type coordinate_type;
-        typedef typename Point2D::circle_event_type circle_event_type;
+        typedef circle_event<Point2D> circle_event_type;
 
         circle_events_queue() {}
 
@@ -659,8 +418,7 @@
     struct beach_line_node {
     public:
         typedef typename Point2D::coordinate_type coordinate_type;
-        typedef typename Point2D::site_event_type site_event_type;
-        typedef typename Point2D::circle_event_type circle_event_type;
+        typedef site_event<Point2D> site_event_type;
 
         beach_line_node() {}
 
@@ -738,10 +496,8 @@
 
     // Represents edge data sturcture (bisector segment), which is
     // associated with beach line node key in the binary search tree.
-    template <typename Point2D>
+    template <typename Edge>
     struct beach_line_node_data {
-        typedef typename half_edge<Point2D> Edge;
-
         Edge *edge;
 
         beach_line_node_data(Edge *new_edge) : edge(new_edge) {}

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp	2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -7,30 +7,29 @@
 
 //  See http://www.boost.org for updates, documentation, and revision history.
 
-#include "detail/voronoi_formation.hpp"
+#include <algorithm>
+
+#include "voronoi_output.hpp"
 
 #ifndef BOOST_SWEEPLINE_VORONOI_BUILDER
 #define BOOST_SWEEPLINE_VORONOI_BUILDER
 
 namespace boost {
 namespace sweepline {
-    
-    using namespace detail;
 
     // Voronoi diagram builder. Sweepline sweeps from left to right.
     template <typename T>
     class voronoi_builder {
     public:
-        typedef typename point_2d<T> Point2D;
+        typedef point_2d<T> Point2D;
         typedef typename Point2D::coordinate_type coordinate_type;
+        typedef voronoi_output<Point2D> Output;
+        typedef typename Output::edge_type edge_type;
 
-        typedef typename voronoi_output<Point2D>::edge_type edge_type;
-        typedef typename voronoi_output<Point2D>::edge_iterator edge_iterator;
-        typedef typename voronoi_output<Point2D>::cell_records cell_records;
-        typedef typename voronoi_output<Point2D>::voronoi_vertices voronoi_vertices;
-        typedef typename voronoi_vertices::const_iterator voronoi_vertices_iterator;
-
-        voronoi_builder() {}
+        voronoi_builder() {
+            // Set sites iterator.
+            site_events_iterator_ = site_events_.begin();
+        }
 
         // Init beach line before sweepline run.
         // In case of a few first sites situated on the same
@@ -38,24 +37,23 @@
         // In other case just use the first two sites for the initialization.
         void init(std::vector<Point2D> &sites) {
             // Sort all sites.
-            std::sort(sites.begin(), sites.end());
+            sort(sites.begin(), sites.end());
 
             // Add all unique sites to the site events vector.
             int site_event_index = 0;
             int sz = sites.size();
             for (int i = 0; i < sz; i++) {
                 if (!i || sites[i] != sites[i-1]) {
-                    site_events_.push_back(make_site_event(sites[i].x(), sites[i].y(),
-                                                          site_event_index));
+                    site_events_.push_back(detail::make_site_event(sites[i], site_event_index));
                     site_event_index++;
                 }
             }
 
-            // Init output with number of site events.
-            output_.init(site_events_.size());
-
             // Set sites iterator.
             site_events_iterator_ = site_events_.begin();
+
+            // Init output with number of site events.
+            output_.init(site_events_.size());
             
             int skip = 0;
             if (site_events_.size() == 1) {
@@ -93,47 +91,37 @@
             // Algorithm stops when there are no events to process.
             while (!circle_events_.empty() || 
                    !(site_events_iterator_ == site_events_.end())) {
-                if (circle_events_.empty()) {
-                    process_site_event(*site_events_iterator_);
-                    site_events_iterator_++;
-                } else if (site_events_iterator_ == site_events_.end()) {
-                    circle_event<T> c_event = circle_events_.top();
-                    circle_events_.pop();
-                    process_circle_event(c_event);
-                } else {
-                    if (circle_events_.top().compare(*site_events_iterator_) >= 0) {
-                        process_site_event(*site_events_iterator_);
-                        site_events_iterator_++;
-                    } else {
-                        circle_event<T> c_event = circle_events_.top();
-                        circle_events_.pop();
-                        process_circle_event(c_event);
-                    }
+                if (circle_events_.empty())
+                    process_site_event();
+                else if (site_events_iterator_ == site_events_.end())
+                    process_circle_event();
+                else {
+                    if (circle_events_.top().compare(*site_events_iterator_) >= 0)
+                        process_site_event();
+                    else
+                        process_circle_event();
                 }
             }
-        }
 
-        const cell_records &get_cell_records() const {
-            return output_.get_cell_records();
+            // Simplify output.
+            output_.simplify();
         }
 
-        const voronoi_vertices &get_voronoi_vertices() const {
-            return output_.get_voronoi_vertices();
+        const Output &get_output() const {
+            return output_;
         }
 
     protected:
-        typedef typename Point2D::site_event_type site_event_type;
-        typedef typename Point2D::circle_event_type circle_event_type;
+        typedef typename detail::site_event<Point2D> site_event_type;
+        typedef typename detail::circle_event<Point2D> circle_event_type;
         typedef typename std::vector<site_event_type>::const_iterator site_events_iterator;
 
-        typedef typename circle_events_queue<Point2D> CircleEventsQueue;
-        typedef typename beach_line_node<Point2D> Key;
-        typedef typename beach_line_node_data<Point2D> Value;
-        typedef typename node_comparer<Key> NodeComparer;
-        typedef typename std::map< Key, Value, NodeComparer > BeachLine;
-        typedef typename BeachLine::const_iterator beach_line_iterator;
-
-        typedef typename voronoi_output<Point2D> Output;
+        typedef typename detail::circle_events_queue<Point2D> CircleEventsQueue;
+        typedef typename detail::beach_line_node<Point2D> Key;
+        typedef typename detail::beach_line_node_data<edge_type> Value;
+        typedef typename detail::node_comparer<Key> NodeComparer;
+        typedef std::map< Key, Value, NodeComparer > BeachLine;
+        typedef typename std::map< Key, Value, NodeComparer >::iterator beach_line_iterator;
 
         void init_beach_line() {
             site_events_iterator it_first = site_events_.begin();
@@ -176,7 +164,10 @@
 
         // Uses special comparison function for the lower bound and insertion
         // operations.
-        void process_site_event(const site_event_type &site_event) {
+        void process_site_event() {
+            const site_event_type &site_event = *site_events_iterator_;
+            site_events_iterator_++;
+
             // Find the node in the binary search tree with left arc
             // lying above the new site point.
             Key new_key(site_event);
@@ -232,7 +223,9 @@
 
         // Doesn't use special comparison function as it works fine only for
         // the site events processing.
-        void process_circle_event(const circle_event_type &circle_event) {
+        void process_circle_event() { 
+            const circle_event_type &circle_event = circle_events_.top();
+
             // Retrieve the second bisector node that corresponds to the given
             // circle event.
             beach_line_iterator it_first = circle_event.get_bisector();
@@ -262,10 +255,14 @@
             const_cast<Key &>(it_first->first).set_right_site(site3);
             edge_type *edge = output_.insert_new_edge(site1, site2, site3, circle_event,
                                                       bisector1.edge, bisector2.edge);
-            const_cast<Value &>(it_first->second).change_edge(edge);
+            it_first->second.change_edge(edge);
             beach_line_.erase(it_last);
             it_last = it_first;
 
+            // Pop circle event from the event queue, before we might
+            // insert new events in it.
+            circle_events_.pop();
+
             // Check the new triplets formed by the neighboring arcs
             // for potential circle events. Check left.
             if (it_first != beach_line_.begin()) {
@@ -292,8 +289,6 @@
             // Create two new nodes.
             Key new_left_node(site_arc, site_event);
             Key new_right_node(site_event, site_arc);
-            int site_index1 = site_arc.get_site_index();
-            int site_index2 = site_event.get_site_index();
             
             // Insert two new nodes into the binary search tree.
             // Update output.
@@ -323,7 +318,7 @@
             coordinate_type sqr_radius = (c_x-site1.x())*(c_x-site1.x()) +
                                          (c_y-site1.y())*(c_y-site1.y());
             // Create new circle event;
-            c_event = make_circle_event(c_x, c_y, sqr_radius);
+            c_event = detail::make_circle_event<Point2D>(c_x, c_y, sqr_radius);
             c_event.set_sites(site1, site2, site3);
             return true;
         }
@@ -364,4 +359,4 @@
 } // sweepline
 } // boost
 
-#endif
\ No newline at end of file
+#endif

Added: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_output.hpp	2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -0,0 +1,453 @@
+// Boost sweepline/voronoi_output.hpp header file 
+
+//          Copyright Andrii Sydorchuk 2010.
+// Distributed under the Boost Software License, Version 1.0.
+//    (See accompanying file LICENSE_1_0.txt or copy at
+//          http://www.boost.org/LICENSE_1_0.txt)
+
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+// Point in 2D space data structure. Comparators defined in this
+    // data structure actually define sweepline movement direction.
+
+#ifndef BOOST_SWEEPLINE_VORONOI_OUTPUT
+#define BOOST_SWEEPLINE_VORONOI_OUTPUT
+
+#include "detail/voronoi_formation.hpp"
+
+namespace boost {
+namespace sweepline {
+
+    template <typename Point2D>
+    struct half_edge;
+
+    template <typename T>
+    struct point_2d {
+    public:
+        typedef T coordinate_type;
+        typedef half_edge< point_2d<T> > Edge;
+
+        point_2d() {}
+
+        point_2d(T x, T y) {
+            x_ = x;
+            y_ = y;
+        }
+
+        bool operator==(const point_2d &point) const {
+            return (this->x_ == point.x()) && (this->y_ == point.y());
+        }
+
+        bool operator!=(const point_2d &point) const {
+            return (this->x_ != point.x()) || (this->y_ != point.y());
+        }
+
+        // This comparator actually defines sweepline movement direction.
+        bool operator<(const point_2d &point) const {
+            // Sweepline sweeps from left to right.
+            if (this->x_ != point.x_)
+                return this->x_ < point.x_;
+            return this->y_ < point.y_;
+        }
+
+        bool operator<=(const point_2d &point) const {
+            return !(point < (*this));
+        }
+
+        bool operator>(const point_2d &point) const {
+            return point < (*this);
+        }
+
+        bool operator>=(const point_2d &point) const {
+            return !((*this) < point);
+        }
+
+        coordinate_type x() const {
+            return this->x_;
+        }
+
+        coordinate_type y() const {
+            return this->y_;
+        }
+
+        void x(coordinate_type x) {
+            x_ = x;
+        }
+
+        void y(coordinate_type y) {
+            y_ = y;
+        }
+
+    private:
+        coordinate_type x_;
+        coordinate_type y_;
+    };
+
+    template <typename T>
+    point_2d<T> make_point_2d(T x, T y) {
+        return point_2d<T>(x,y);
+    }
+    
+    ///////////////////////////////////////////////////////////////////////////
+    // VORONOI OUTPUT TYPES ///////////////////////////////////////////////////
+    ///////////////////////////////////////////////////////////////////////////
+
+    // Cell record data structure. Represents voronoi cell.
+    // Contains site point pointer to any incident half-edge and number
+    // of incident half-edges.
+    template <typename Point2D>
+    struct cell_record {
+        half_edge<Point2D> *incident_edge;
+        Point2D site_point;
+        int num_incident_edges;
+
+        cell_record(Point2D site, half_edge<Point2D>* edge) :
+            incident_edge(edge),
+            site_point(site),
+            num_incident_edges(0) {}
+    };
+
+    // Voronoi vertex data structure. Represents voronoi vertex.
+    // Contains vertex coordinates, pointers to all incident half-edges and
+    // number of incident half-edges.
+    template <typename Point2D>
+    struct vertex_record {
+        typedef typename std::list< half_edge<Point2D>* >::iterator vertex_incident_edges_it;
+
+        std::list< half_edge<Point2D>* > incident_edges;
+        Point2D vertex;
+        int num_incident_edges;
+        typename std::list< vertex_record<Point2D> >::iterator vertex_it;
+
+        vertex_record(Point2D vertex) : vertex(vertex), num_incident_edges(3) {}
+
+        vertex_incident_edges_it get_prev_incident_edge(vertex_incident_edges_it it) {
+            if (it != incident_edges.begin()) {
+                it--;
+                return it;
+            }
+            it = incident_edges.end();
+            it--;
+            return it;
+        }
+
+        vertex_incident_edges_it get_next_incident_edge(vertex_incident_edges_it it) {
+            it++;
+            if (it != incident_edges.end())
+                return it;            
+            return incident_edges.begin();
+        }
+    };
+
+    // Half-edge data structure. Represents voronoi edge.
+    // Contains: 1) pointer to cell records;
+    //           2) pointers to start/end vertices of half-edge;
+    //           3) pointers to previous/next half-edges(CCW);
+    //           4) pointer to twin half-edge;
+    //           5) iterator in the vertex incident edges list.
+    template <typename Point2D>
+    struct half_edge {
+        typedef cell_record<Point2D> cell_record_type;
+        typedef vertex_record<Point2D> vertex_record_type;
+        typedef half_edge<Point2D> half_edge_type;
+
+        cell_record_type *cell;
+        vertex_record_type *start_point;
+        vertex_record_type *end_point;
+        half_edge_type *prev;
+        half_edge_type *next;
+        half_edge_type *twin;
+        typename std::list< half_edge<Point2D>* >::iterator incident_it;
+
+        half_edge(int site_index) :
+            cell(NULL),
+            start_point(NULL),
+            end_point(NULL),
+            prev(NULL),
+            next(NULL),
+            twin(NULL) {}
+    };
+
+    // Voronoi output data structure based on the half-edges.
+    // Contains vector of voronoi cells, doubly linked list of
+    // voronoi vertices and voronoi edges.
+    template <typename Point2D>
+    class voronoi_output {
+    public:
+        typedef typename detail::site_event<Point2D> site_event_type;
+        typedef typename detail::circle_event<Point2D> circle_event_type;
+        typedef cell_record<Point2D> cell_record_type;
+        typedef vertex_record<Point2D> vertex_record_type;
+        typedef half_edge<Point2D> edge_type;
+        typedef std::vector<cell_record_type> cell_records_type;
+        typedef std::list<vertex_record_type> voronoi_vertices_type;
+        typedef typename std::list<edge_type *>::iterator edge_pointer_iterator_type;
+        typedef typename std::list<edge_type *>::const_iterator edge_pointer_const_iterator_type;
+        typedef typename voronoi_vertices_type::iterator voronoi_vertices_iterator_type;
+        typedef typename voronoi_vertices_type::const_iterator
+            voronoi_vertices_const_iterator_type;
+
+        voronoi_output() {
+            num_cell_records_ = 0;
+            num_edges_ = 0;
+            num_vertex_records_ = 0;
+        }
+
+        // This preserves the validity of iterators.
+        void init(int num_sites) {
+            cell_records_.reserve(num_sites);
+            num_cell_records_ = 0;
+            num_edges_ = 0;
+            num_vertex_records_ = 0;
+        }
+
+        void reset() {
+            cell_records_.clear();
+            vertex_records_.clear();
+            edges_.clear();
+
+            num_cell_records_ = 0;
+            num_edges_ = 0;
+            num_vertex_records_ = 0;
+        }
+
+        // Inserts new half-edge into the output data structure during site
+        // event processing. Takes as input left and right sites of the new
+        // beach line node and returns reference to the new half-edge. 
+        // Second argument is new site. During this step we add two new
+        // twin half-edges.
+        edge_type *insert_new_edge(const site_event_type &site1,
+                                   const site_event_type &site2) {
+            num_cell_records_++;
+            num_edges_++;
+
+            // Get indexes of sites.                                           
+            int site_index1 = site1.get_site_index();
+            int site_index2 = site2.get_site_index();
+
+            // Create new half-edge that belongs to the cell with the first site.
+            edges_.push_back(edge_type(site_index1));
+            edge_type &edge1 = edges_.back();
+
+            // Create new half-edge that belongs to the cell with the second site.
+            edges_.push_back(edge_type(site_index2));
+            edge_type &edge2 = edges_.back();
+
+            // Add initial cell during first edge insertion.
+            if (cell_records_.empty()) {
+                cell_records_.push_back(cell_record_type(site1.get_point(), &edge1));
+                num_cell_records_++;
+            }
+
+            // Second site represents new site during site event processing.
+            // Add new cell to the cell records vector.
+            cell_records_.push_back(cell_record_type(site2.get_point(), &edge2));
+
+            // Update pointers to cells.
+            edge1.cell = &cell_records_[site_index1];
+            edge2.cell = &cell_records_[site_index2];
+
+            // Update incident edges counters.
+            cell_records_[site_index1].num_incident_edges++;
+            cell_records_[site_index2].num_incident_edges++;
+
+            // Update twin pointers.
+            edge1.twin = &edge2;
+            edge2.twin = &edge1;
+
+            return &edge1;
+        }
+
+        edge_type *insert_new_edge(const site_event_type &site1,
+                                   const site_event_type &site2,
+                                   const site_event_type &site3,
+                                   const circle_event_type &circle,
+                                   edge_type *edge12,
+                                   edge_type *edge23) {
+            num_vertex_records_++;
+            num_edges_++;
+
+            // Add new voronoi vertex as voronoi circle center.
+            vertex_records_.push_back(vertex_record_type(circle.get_center()));
+            vertex_record_type &new_vertex = vertex_records_.back();
+            
+            // Update vertex iterator.
+            voronoi_vertices_iterator_type vertices_it = vertex_records_.end();
+            vertices_it--;
+            new_vertex.vertex_it = vertices_it;
+
+            // Update two input bisectors and their twins half-edges with
+            // new voronoi vertex.
+            edge12->start_point = &new_vertex;
+            edge12->twin->end_point = &new_vertex;
+            edge23->start_point = &new_vertex;
+            edge23->twin->end_point = &new_vertex;
+
+            // Add new half-edge.
+            edges_.push_back(edge_type(site1.get_site_index()));
+            edge_type &new_edge1 = edges_.back();
+            new_edge1.cell = &cell_records_[site1.get_site_index()];
+            cell_records_[site1.get_site_index()].num_incident_edges++;
+            new_edge1.end_point = &new_vertex;
+
+            // Add new half-edge.
+            edges_.push_back(edge_type(site3.get_site_index()));
+            edge_type &new_edge2 = edges_.back();
+            new_edge2.cell = &cell_records_[site3.get_site_index()];
+            cell_records_[site3.get_site_index()].num_incident_edges++;
+            new_edge2.start_point = &new_vertex;
+
+            // Update twin pointers of the new half-edges.
+            new_edge1.twin = &new_edge2;
+            new_edge2.twin = &new_edge1;
+
+            // Update voronoi prev/next pointers of all half-edges incident
+            // to the new voronoi vertex.
+            edge12->prev = &new_edge1;
+            new_edge1.next = edge12;
+            edge12->twin->next = edge23;
+            edge23->prev = edge12->twin;
+            edge23->twin->next = &new_edge2;
+            new_edge2.prev = edge23->twin;
+
+            // Update voronoi vertex incident edges pointers.
+            new_vertex.incident_edges.push_back(edge12);
+            typename std::list<edge_type*>::iterator temp_iter =new_vertex.incident_edges.begin();
+            edge12->incident_it = temp_iter;
+            
+            new_vertex.incident_edges.push_back(edge23);
+            temp_iter++;
+            edge23->incident_it = temp_iter;
+            
+            new_vertex.incident_edges.push_back(&new_edge2);
+            temp_iter++;
+            new_edge2.incident_it = temp_iter;
+
+            return &new_edge1;
+        }
+
+        const cell_records_type &get_cell_records() const {
+            return cell_records_;
+        }
+
+        const voronoi_vertices_type &get_voronoi_vertices() const {
+            return vertex_records_;
+        }
+
+        int get_num_voronoi_cells() const {
+            return num_cell_records_;
+        }
+
+        int get_num_voronoi_vertices() const {
+            return num_vertex_records_;
+        }
+
+        int get_num_voronoi_edges() const {
+            return num_edges_;
+        }
+
+        void simplify() {
+            typename std::list<edge_type>::iterator edge_it1;
+            typename std::list<edge_type>::iterator edge_it = edges_.begin();
+
+            // Iterate over all edges and remove degeneracies.
+            while (edge_it != edges_.end()) {
+                edge_it1 = edge_it;
+                edge_it++;
+                edge_it++;
+
+                if (edge_it1->start_point && edge_it1->end_point &&
+                    edge_it1->start_point->vertex == edge_it1->end_point->vertex) {
+                    // Splice incident edges of the second voronoi vertex to the first
+                    // one, if it contains less or equal number of them.
+
+                    // Decrease number of cell incident edges.
+                    edge_it1->cell->num_incident_edges--;
+                    edge_it1->twin->cell->num_incident_edges--;
+
+                    // To guarantee N*lon(N) time we merge vertex with
+                    // less incident edges to the one with more.
+                    if (edge_it1->start_point->num_incident_edges >=
+                        edge_it1->end_point->num_incident_edges)
+                            simplify_edge(*edge_it1);
+                    else
+                        simplify_edge(*edge_it1->twin);
+
+                    // Remove zero length edges.
+                    edges_.erase(edge_it1, edge_it);
+
+                    num_vertex_records_--;
+                    num_edges_--;
+                }
+            }
+        }
+
+        bool check() {
+            return true;
+        }
+
+    private:
+        void simplify_edge(edge_type &edge) {
+            vertex_record_type *vertex1 = edge.start_point;
+            vertex_record_type *vertex2 = edge.end_point;
+
+            // Update number of vertex incident edges.
+            vertex1->num_incident_edges += vertex2->num_incident_edges - 2;
+
+            // Update second vertex incident edges start and end points.
+            for (edge_pointer_iterator_type it = vertex2->incident_edges.begin();
+                 it != vertex2->incident_edges.end(); it++) {
+                (*it)->start_point = vertex1;
+                (*it)->twin->end_point = vertex1;
+            }
+
+            // Update prev and next pointers of incident edges that
+            // belongs to different voronoi vertices.
+            edge_pointer_iterator_type edge1_it = edge.incident_it;
+            edge_pointer_iterator_type edge2_it = edge.twin->incident_it;
+
+            edge_pointer_iterator_type edge1_it_prev = vertex1->get_prev_incident_edge(edge1_it);
+            edge_pointer_iterator_type edge1_it_next = vertex1->get_next_incident_edge(edge1_it);
+
+            edge_pointer_iterator_type edge2_it_prev = vertex2->get_prev_incident_edge(edge2_it);
+            edge_pointer_iterator_type edge2_it_next = vertex2->get_next_incident_edge(edge2_it);
+            
+            (*edge1_it_prev)->twin->next = *edge2_it_next;
+            (*edge2_it_next)->prev = (*edge1_it_prev)->twin;
+
+            (*edge1_it_next)->prev = (*edge2_it_prev)->twin;
+            (*edge2_it_prev)->twin->next = (*edge1_it_next);
+
+            // Splice incident edges of the second voronoi vertex to the first one.
+            edge2_it++;
+            for (; edge2_it != vertex2->incident_edges.end(); edge2_it++)
+                (*edge2_it)->incident_it = vertex1->incident_edges.insert(edge1_it, *edge2_it);
+
+            edge2_it = vertex2->incident_edges.begin();
+            for (; edge2_it != edge.twin->incident_it; edge2_it++)
+                (*edge2_it)->incident_it = vertex1->incident_edges.insert(edge1_it, *edge2_it);
+
+            // Remove zero length edge from list of incident edges.
+            vertex1->incident_edges.erase(edge1_it);
+
+            // Remove second vertex from the vertex records.
+            vertex_records_.erase(vertex2->vertex_it);
+        }
+
+        std::vector<cell_record_type> cell_records_;
+        std::list<vertex_record_type> vertex_records_;
+        std::list<edge_type> edges_;
+
+        int num_cell_records_;
+        int num_vertex_records_;
+        int num_edges_;
+
+        //Disallow copy constructor and operator=
+        voronoi_output(const voronoi_output&);
+        void operator=(const voronoi_output&);
+    };
+
+} // sweepline
+} // boost
+
+#endif

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2	2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -12,8 +12,8 @@
 
 test-suite "sweepline"
     : 
-        [ run event_queue_test.cpp :  :  : <link>static ]
-        [ run event_types_test.cpp :  :  : <link>static ]
-	[ run node_comparer_test.cpp :  :  : <link>static ]
-	[ run voronoi_builder_test.cpp :  :  : <link>static ]
+        [ run event_queue_test.cpp ]
+        [ run event_types_test.cpp ]
+	[ run node_comparer_test.cpp ]
+	[ run voronoi_builder_test.cpp ]
     ;
\ No newline at end of file

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp	2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -7,9 +7,11 @@
 //
 //  See http://www.boost.org for updates, documentation, and revision history.
 
+#include <cmath>
+
 #include "test_type_list.hpp"
-#include "boost/sweepline/detail/voronoi_formation.hpp"
-using namespace boost::sweepline::detail;
+#include "boost/sweepline/voronoi_output.hpp"
+using namespace boost::sweepline;
 
 #define BOOST_TEST_MODULE event_queue_test
 #include <boost/test/test_case_template.hpp>
@@ -20,7 +22,9 @@
                       TOP.y() == static_cast<T>(Y), true)
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test1, T, test_types) {
-    circle_events_queue< point_2d<T> > event_q;
+    typedef point_2d<T> Point2D;
+
+    detail::circle_events_queue< point_2d<T> > event_q;
     BOOST_CHECK_EQUAL(event_q.empty(), true);
     
     event_q.reset();
@@ -28,7 +32,7 @@
     for (int i = 0; i < 10; i++) {
         T x = static_cast<T>(-i);
         T y = static_cast<T>(10-i);
-        event_q.push(make_circle_event(x, y, static_cast<T>(100)));
+        event_q.push(detail::make_circle_event<Point2D>(x, y, static_cast<T>(100)));
     }
 
     for (int i = 0; i < 10; i++) {
@@ -40,15 +44,19 @@
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test2, T, test_types) {
-    circle_events_queue< point_2d<T> > event_q;
-    site_event<T> temp_site = make_site_event(static_cast<T>(0),
-                                              static_cast<T>(0),
-                                              0);
+    typedef point_2d<T> Point2D;
+    typedef detail::circle_event<Point2D> circle_event_type;
+
+    detail::circle_events_queue< point_2d<T> > event_q;
+    detail::site_event<Point2D> temp_site = 
+        detail::make_site_event<Point2D>(static_cast<T>(0),
+                                         static_cast<T>(0),
+                                         0);
 
     for (int i = 0; i < 10; i++) {
         T x = static_cast<T>(10-i);
         T y = static_cast<T>(10-i);
-        circle_event<T> &c = make_circle_event(x, y, static_cast<T>(0));
+        circle_event_type c = detail::make_circle_event<Point2D>(x, y, static_cast<T>(0));
         c.set_sites(temp_site, temp_site, temp_site);
         event_q.push(c);
     }
@@ -56,7 +64,7 @@
     for (int i = 0; i < 5; i++) {
         T x = static_cast<T>(10-2*i-1);
         T y = static_cast<T>(10-2*i-1);
-        circle_event<T> &c = make_circle_event(x, y, static_cast<T>(0));
+        circle_event_type c = detail::make_circle_event<Point2D>(x, y, static_cast<T>(0));
         c.set_sites(temp_site, temp_site, temp_site);
         event_q.deactivate_event(c);   
     }
@@ -67,4 +75,4 @@
     }
 
     BOOST_CHECK_EQUAL(event_q.empty(), true);
-}
\ No newline at end of file
+}

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_types_test.cpp	2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -8,7 +8,8 @@
 //  See http://www.boost.org for updates, documentation, and revision history.
 
 #include "test_type_list.hpp"
-#include "boost/sweepline/detail/voronoi_formation.hpp"
+#include "boost/sweepline/voronoi_output.hpp"
+using namespace boost::sweepline;
 using namespace boost::sweepline::detail;
 
 #define BOOST_TEST_MODULE event_types_test
@@ -43,97 +44,102 @@
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(site_event_test1, T, test_types) {
-    site_event<T> site1 = make_site_event(static_cast<T>(1),
-                                          static_cast<T>(1.05),
-                                          0);
-    site_event<T> site2;
+    typedef point_2d<T> Point2D;
+
+    site_event<Point2D> site1 = make_site_event<Point2D>(static_cast<T>(1),
+                                                         static_cast<T>(1.05),
+                                                         0);
+    site_event<Point2D> site2;
 
     BOOST_CHECK_EQUAL(site1.x(), static_cast<T>(1));
     BOOST_CHECK_EQUAL(site1.y(), static_cast<T>(1.05));
     BOOST_CHECK_EQUAL(site1.get_site_index(), 0);
 
-    site2 = make_site_event(static_cast<T>(0.999999), static_cast<T>(1), 1);
+    site2 = make_site_event<Point2D>(static_cast<T>(0.999999), static_cast<T>(1), 1);
     bool arr1[] = { false, true, false, true, false, true };
     EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr1);
 
-    site2 = make_site_event(static_cast<T>(1), static_cast<T>(1.1), 1);
+    site2 = make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1.1), 1);
     bool arr2[] = { true, false, true, false, false, true };
     EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr2);
 
-    site2 = make_site_event(static_cast<T>(1), static_cast<T>(1.05), 1);
+    site2 = make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1.05), 1);
     bool arr3[] = { false, false, true, true, true, false };
     EVENT_TYPES_CHECK_COMPARISON(site1, site2, arr3);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_test1, T, test_types) {
-    circle_event<T> circle1 = make_circle_event<T>(static_cast<T>(1),
-                                                   static_cast<T>(2),
-                                                   static_cast<T>(4));
-    site_event<T> temp_site = make_site_event<T>(static_cast<T>(0),
-                                                 static_cast<T>(0),
-                                                 0);
+    typedef point_2d<T> Point2D;
+
+    circle_event<Point2D> circle1 = make_circle_event<Point2D>(static_cast<T>(1),
+                                                               static_cast<T>(2),
+                                                               static_cast<T>(4));
+    site_event<Point2D> temp_site = make_site_event<Point2D>(static_cast<T>(0),
+                                                             static_cast<T>(0),
+                                                             0);
     circle1.set_sites(temp_site, temp_site, temp_site);
-    circle_event<T> circle2;
+    circle_event<Point2D> circle2;
     
     BOOST_CHECK_EQUAL(circle1.x(), static_cast<T>(1));
     BOOST_CHECK_EQUAL(circle1.y(), static_cast<T>(2));
     BOOST_CHECK_EQUAL(circle1.get_sqr_radius(), static_cast<T>(4));
 
-    circle2 = make_circle_event<T>(static_cast<T>(1),
-                                   static_cast<T>(2),
-                                   static_cast<T>(4));
+    circle2 = make_circle_event<Point2D>(static_cast<T>(1),
+                                         static_cast<T>(2),
+                                         static_cast<T>(4));
     circle2.set_sites(temp_site, temp_site, temp_site);
     bool arr1[] = { false, false, true, true, true, false };
     EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr1);
 
-    circle2 = make_circle_event<T>(static_cast<T>(1),
-                                   static_cast<T>(3),
-                                   static_cast<T>(4));
+    circle2 = make_circle_event<Point2D>(static_cast<T>(1),
+                                         static_cast<T>(3),
+                                         static_cast<T>(4));
     circle2.set_sites(temp_site, temp_site, temp_site);
     bool arr2[] = { true, false, true, false, false, true };
     EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr2);
 
-    circle2 = make_circle_event<T>(static_cast<T>(1),
-                                   static_cast<T>(2),
-                                   static_cast<T>(5));
+    circle2 = make_circle_event<Point2D>(static_cast<T>(1),
+                                         static_cast<T>(2),
+                                         static_cast<T>(5));
     circle2.set_sites(temp_site, temp_site, temp_site);
     bool arr3[] = { true, false, true, false, false, true };
     EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr3);
 
 
-    circle2 = make_circle_event<T>(static_cast<T>(0),
-                                   static_cast<T>(2),
-                                   static_cast<T>(4));
+    circle2 = make_circle_event<Point2D>(static_cast<T>(0),
+                                         static_cast<T>(2),
+                                         static_cast<T>(4));
     circle2.set_sites(temp_site, temp_site, temp_site);
     bool arr4[] = { false, true, false, true, false, true };
     EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr4);
 
-    circle2 = make_circle_event<T>(static_cast<T>(0),
-                                   static_cast<T>(0),
-                                   static_cast<T>(10));
+    circle2 = make_circle_event<Point2D>(static_cast<T>(0),
+                                         static_cast<T>(0),
+                                         static_cast<T>(10));
     circle2.set_sites(temp_site, temp_site, temp_site);
     bool arr5[] = { true, false, true, false, false, true };
     EVENT_TYPES_CHECK_COMPARISON(circle1, circle2, arr5);
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(circle_event_test2, T, test_types) {
-    circle_event<T> circle = make_circle_event<T>(static_cast<T>(1),
-                                                   static_cast<T>(2),
-                                                   static_cast<T>(4));
-    site_event<T> site;
+    typedef point_2d<T> Point2D;
+    circle_event<Point2D> circle = make_circle_event<Point2D>(static_cast<T>(1),
+                                                              static_cast<T>(2),
+                                                              static_cast<T>(4));
+    site_event<Point2D> site;
 
-    site = make_site_event<T>(0, 100, 0);
+    site = make_site_event<Point2D>(0, 100, 0);
     BOOST_CHECK_EQUAL(circle.compare(site), 1);
 
-    site = make_site_event<T>(3, 0, 0);
+    site = make_site_event<Point2D>(3, 0, 0);
     BOOST_CHECK_EQUAL(circle.compare(site), 1);
 
-    site = make_site_event<T>(3, 2, 0);
+    site = make_site_event<Point2D>(3, 2, 0);
     BOOST_CHECK_EQUAL(circle.compare(site), 0);
     
-    site = make_site_event<T>(3, 2, 0);
+    site = make_site_event<Point2D>(3, 2, 0);
     BOOST_CHECK_EQUAL(circle.compare(site), 0);
 
-    site = make_site_event<T>(4, 2, 0);
+    site = make_site_event<Point2D>(4, 2, 0);
     BOOST_CHECK_EQUAL(circle.compare(site), -1);
-}
\ No newline at end of file
+}

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/node_comparer_test.cpp	2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -8,24 +8,28 @@
 //  See http://www.boost.org for updates, documentation, and revision history.
 
 #include "test_type_list.hpp"
-#include "boost/sweepline/detail/voronoi_formation.hpp"
+#include "boost/sweepline/voronoi_output.hpp"
+using namespace boost::sweepline;
 using namespace boost::sweepline::detail;
 
 #define BOOST_TEST_MODULE node_comparer_test
 #include <boost/test/test_case_template.hpp>
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test1, T, test_types) {
+    typedef point_2d<T> Point2D;
+    typedef site_event<Point2D> site_event_type; 
     typedef beach_line_node< point_2d<T> > bline_node;
-    typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
+    typedef typename std::map< bline_node, int, 
+        node_comparer<bline_node> >::const_iterator bline_it;
 
     std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
 
-    site_event<T> site1 = make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0);
-    site_event<T> site2 = make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1);
+    site_event_type site1 = make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0);
+    site_event_type site2 = make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(2), 1);
     bline_node initial_node(site1, site2);
     test_beach_line[initial_node] = 2;
 
-    site_event<T> site3 = make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2);
+    site_event_type site3 = make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 2);
     bline_node node1(site1, site3);
     bline_node node2(site3, site1);
     test_beach_line.insert(std::pair< bline_node, int>(node1, 0));
@@ -39,14 +43,17 @@
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test2, T, test_types) {
+    typedef point_2d<T> Point2D;
+    typedef site_event<Point2D> site_event_type; 
     typedef beach_line_node< point_2d<T> > bline_node;
-    typedef std::map< bline_node, int, node_comparer<bline_node> >::const_iterator bline_it;
+    typedef typename std::map< bline_node, int, 
+        node_comparer<bline_node> >::const_iterator bline_it;
 
     std::map< bline_node, int, node_comparer<bline_node> > test_beach_line;
 
-    site_event<T> site1 = make_site_event<T>(static_cast<T>(0), static_cast<T>(1), 0);
-    site_event<T> site2 = make_site_event<T>(static_cast<T>(2), static_cast<T>(0), 1);
-    site_event<T> site3 = make_site_event<T>(static_cast<T>(2), static_cast<T>(4), 2);
+    site_event_type site1 = make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(1), 0);
+    site_event_type site2 = make_site_event<Point2D>(static_cast<T>(2), static_cast<T>(0), 1);
+    site_event_type site3 = make_site_event<Point2D>(static_cast<T>(2), static_cast<T>(4), 2);
     bline_node initial_node1(site1, site2);
     bline_node initial_node2(site2, site1);
     test_beach_line[initial_node1] = 0;
@@ -65,20 +72,21 @@
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test3, T, test_types) {
+    typedef point_2d<T> Point2D;
     typedef beach_line_node< point_2d<T> > bline_node;
     node_comparer<bline_node> node_comparer_test;
 
     bline_node initial_node(
-        make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 0),
-        make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
+        make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 0),
+        make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(2), 1));
     
-    bline_node new_node1(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-10), 2));
-    bline_node new_node2(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-0.5), 3));
-    bline_node new_node3(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0), 4));
-    bline_node new_node4(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0.5), 4));
-    bline_node new_node5(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(1.0), 4));
-    bline_node new_node6(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(3.0), 4));
-    bline_node new_node7(make_site_event<T>(static_cast<T>(2.0), static_cast<T>(1.0), 4));
+    bline_node new_node1(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-10), 2));
+    bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-0.5), 3));
+    bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0), 4));
+    bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0.5), 4));
+    bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(1.0), 4));
+    bline_node new_node6(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(3.0), 4));
+    bline_node new_node7(make_site_event<Point2D>(static_cast<T>(2.0), static_cast<T>(1.0), 4));
 
 
     BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
@@ -100,20 +108,21 @@
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test4, T, test_types) {
+    typedef point_2d<T> Point2D;
     typedef beach_line_node< point_2d<T> > bline_node;
     node_comparer<bline_node> node_comparer_test;
 
     bline_node initial_node(
-        make_site_event<T>(static_cast<T>(0), static_cast<T>(1), 0),
-        make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 1));
+        make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(1), 0),
+        make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 1));
     
-    bline_node new_node1(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-3), 2));
-    bline_node new_node2(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-1.8), 3));
-    bline_node new_node3(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-1.7), 4));
-    bline_node new_node4(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0.0), 4));
-    bline_node new_node5(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(1.0), 4));
-    bline_node new_node6(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(3.0), 4));
-    bline_node new_node7(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(10.0), 4));
+    bline_node new_node1(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-3), 2));
+    bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-1.8), 3));
+    bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-1.7), 4));
+    bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0.0), 4));
+    bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(1.0), 4));
+    bline_node new_node6(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(3.0), 4));
+    bline_node new_node7(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(10.0), 4));
 
     BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
     BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
@@ -133,20 +142,21 @@
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test5, T, test_types) {
+    typedef point_2d<T> Point2D;
     typedef beach_line_node< point_2d<T> > bline_node;
     node_comparer<bline_node> node_comparer_test;
 
     bline_node initial_node(
-        make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
-        make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 1));
+        make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0),
+        make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(2), 1));
     
-    bline_node new_node1(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-10), 2));
-    bline_node new_node2(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0), 3));
-    bline_node new_node3(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(1.05), 4));
-    bline_node new_node4(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(1.1), 4));
-    bline_node new_node5(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(2), 4));
-    bline_node new_node6(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(5), 4));
-    bline_node new_node7(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(20), 4));
+    bline_node new_node1(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-10), 2));
+    bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0), 3));
+    bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(1.05), 4));
+    bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(1.1), 4));
+    bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(2), 4));
+    bline_node new_node6(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(5), 4));
+    bline_node new_node7(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(20), 4));
 
 
     BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
@@ -168,20 +178,21 @@
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test6, T, test_types) {
+    typedef point_2d<T> Point2D;
     typedef beach_line_node< point_2d<T> > bline_node;
     node_comparer<bline_node> node_comparer_test;
 
     bline_node initial_node(
-        make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 0),
-        make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 1));
+        make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 0),
+        make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 1));
     
-    bline_node new_node1(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-3), 2));
-    bline_node new_node2(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(-1.75), 3));
-    bline_node new_node3(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0.0), 4));
-    bline_node new_node4(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(0.28), 4));
-    bline_node new_node5(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(2.7), 4));
-    bline_node new_node6(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(2.8), 4));
-    bline_node new_node7(make_site_event<T>(static_cast<T>(1.5), static_cast<T>(5.0), 4));
+    bline_node new_node1(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-3), 2));
+    bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(-1.75), 3));
+    bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0.0), 4));
+    bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(0.28), 4));
+    bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(2.7), 4));
+    bline_node new_node6(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(2.8), 4));
+    bline_node new_node7(make_site_event<Point2D>(static_cast<T>(1.5), static_cast<T>(5.0), 4));
 
     BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
     BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
@@ -201,18 +212,19 @@
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test7, T, test_types) {
+    typedef point_2d<T> Point2D;
     typedef beach_line_node< point_2d<T> > bline_node;
     node_comparer<bline_node> node_comparer_test;
 
     bline_node initial_node(
-        make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
-        make_site_event<T>(static_cast<T>(0), static_cast<T>(2), 1));
+        make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0),
+        make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(2), 1));
     
-    bline_node new_node1(make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
-    bline_node new_node2(make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 3));
-    bline_node new_node3(make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 4));
-    bline_node new_node4(make_site_event<T>(static_cast<T>(1), static_cast<T>(1.000001), 5));
-    bline_node new_node5(make_site_event<T>(static_cast<T>(1), static_cast<T>(0.999999), 6));
+    bline_node new_node1(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 2));
+    bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 3));
+    bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(2), 4));
+    bline_node new_node4(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1.000001), 5));
+    bline_node new_node5(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0.999999), 6));
     
     BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
     BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
@@ -228,19 +240,20 @@
 }
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test8, T, test_types) {
+    typedef point_2d<T> Point2D;
     typedef beach_line_node< point_2d<T> > bline_node;
     node_comparer<bline_node> node_comparer_test;
 
     bline_node initial_node(
-        make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0),
-        make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 1));
+        make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0),
+        make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 1));
     
-    bline_node new_node1(make_site_event<T>(static_cast<T>(1), static_cast<T>(0), 2));
-    bline_node new_node2(make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 1));
-    bline_node new_node3(make_site_event<T>(static_cast<T>(1), static_cast<T>(2), 3));
+    bline_node new_node1(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(0), 2));
+    bline_node new_node2(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 1));
+    bline_node new_node3(make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(2), 3));
     bline_node new_node4(
-        make_site_event<T>(static_cast<T>(1), static_cast<T>(1), 1),
-        make_site_event<T>(static_cast<T>(0), static_cast<T>(0), 0));
+        make_site_event<Point2D>(static_cast<T>(1), static_cast<T>(1), 1),
+        make_site_event<Point2D>(static_cast<T>(0), static_cast<T>(0), 0));
     
     BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node1), false);
     BOOST_CHECK_EQUAL(node_comparer_test(initial_node, new_node2), false);
@@ -251,4 +264,4 @@
     BOOST_CHECK_EQUAL(node_comparer_test(new_node2, initial_node), false);
     BOOST_CHECK_EQUAL(node_comparer_test(new_node3, initial_node), false);
     BOOST_CHECK_EQUAL(node_comparer_test(new_node4, initial_node), false);
-}
\ No newline at end of file
+}

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp	2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -12,8 +12,8 @@
 
 #include <boost/mpl/list.hpp>
 
-typedef boost::mpl::list<float,
-                         double,
+typedef boost::mpl::list<//float,
+                         //double,
                          long double> test_types;
 
-#endif
\ No newline at end of file
+#endif

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp	2010-06-28 11:04:37 EDT (Mon, 28 Jun 2010)
@@ -19,10 +19,11 @@
 
 // Sites: (0, 0), (0, 4), (2, 1).
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test1, T, test_types) {
-    typedef typename voronoi_builder<T>::edge_type edge_type;
-    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
+    typedef typename voronoi_output< point_2d<T> >::edge_type edge_type;
+    typedef typename voronoi_output< point_2d<T> >::edge_pointer_const_iterator_type 
+        edge_pointer_iterator_type;
+    typedef typename voronoi_output< point_2d<T> >::voronoi_vertices_const_iterator_type
+        voronoi_vertices_iterator_type;
 
     voronoi_builder<T> test_beach_line;
     point_2d<T> point1 = make_point_2d<T>(0, 0);
@@ -36,31 +37,33 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
-    BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 3);
-    BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 1);
+    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
 
-    voronoi_vertices_iterator it = test_beach_line.get_voronoi_vertices().begin();
-    BOOST_CHECK_EQUAL(it->incident_edges.size(), 3);
+    BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_cell_records().size()), 3);
+    BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 1);
+
+    voronoi_vertices_iterator_type it = test_output.get_voronoi_vertices().begin();
+    BOOST_CHECK_EQUAL(static_cast<int>(it->incident_edges.size()), 3);
     BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<T>(0.25) &&
                       it->vertex.y() == static_cast<T>(2.0), true);
 
-    edge_iterator edge_it = it->incident_edges.begin();
+    edge_pointer_iterator_type edge_it = it->incident_edges.begin();
     edge_type *edge1_1 = *edge_it;
     edge_type *edge1_2 = edge1_1->twin;
-    BOOST_CHECK_EQUAL(edge1_1->cell_record->site_point == point3, true);
-    BOOST_CHECK_EQUAL(edge1_2->cell_record->site_point == point1, true);
+    BOOST_CHECK_EQUAL(edge1_1->cell->site_point == point3, true);
+    BOOST_CHECK_EQUAL(edge1_2->cell->site_point == point1, true);
 
     edge_it++;
     edge_type *edge2_1 = *edge_it;
     edge_type *edge2_2 = edge2_1->twin;
-    BOOST_CHECK_EQUAL(edge2_1->cell_record->site_point == point1, true);
-    BOOST_CHECK_EQUAL(edge2_2->cell_record->site_point == point2, true);
+    BOOST_CHECK_EQUAL(edge2_1->cell->site_point == point1, true);
+    BOOST_CHECK_EQUAL(edge2_2->cell->site_point == point2, true);
 
     edge_it++;
     edge_type *edge3_1 = *edge_it;
     edge_type *edge3_2 = edge3_1->twin;
-    BOOST_CHECK_EQUAL(edge3_1->cell_record->site_point == point2, true);
-    BOOST_CHECK_EQUAL(edge3_2->cell_record->site_point == point3, true);
+    BOOST_CHECK_EQUAL(edge3_1->cell->site_point == point2, true);
+    BOOST_CHECK_EQUAL(edge3_2->cell->site_point == point3, true);
 
     BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
     BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
@@ -82,10 +85,11 @@
 
 // Sites: (0, 1), (2, 0), (2, 4).
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test2, T, test_types) {
-    typedef typename voronoi_builder<T>::edge_type edge_type;
-    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
+    typedef typename voronoi_output< point_2d<T> >::edge_type edge_type;
+    typedef typename voronoi_output< point_2d<T> >::edge_pointer_const_iterator_type 
+        edge_pointer_iterator_type;
+    typedef typename voronoi_output< point_2d<T> >::voronoi_vertices_const_iterator_type
+        voronoi_vertices_iterator_type;
 
     voronoi_builder<T> test_beach_line;
     point_2d<T> point1 = make_point_2d<T>(0, 1);
@@ -99,31 +103,33 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
-    BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 3);
-    BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 1);
+    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+    BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_cell_records().size()), 3);
+    BOOST_CHECK_EQUAL(static_cast<int>(test_output.get_voronoi_vertices().size()), 1);
 
-    voronoi_vertices_iterator it = test_beach_line.get_voronoi_vertices().begin();
-    BOOST_CHECK_EQUAL(it->incident_edges.size(), 3);
+    voronoi_vertices_iterator_type it = test_output.get_voronoi_vertices().begin();
+    BOOST_CHECK_EQUAL(static_cast<int>(it->incident_edges.size()), 3);
     BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<T>(1.75) &&
                       it->vertex.y() == static_cast<T>(2.0), true);
 
-    edge_iterator edge_it = it->incident_edges.begin();
+    edge_pointer_iterator_type edge_it = it->incident_edges.begin();
     edge_type *edge1_1 = *edge_it;
     edge_type *edge1_2 = edge1_1->twin;
-    BOOST_CHECK_EQUAL(edge1_1->cell_record->site_point == point2, true);
-    BOOST_CHECK_EQUAL(edge1_2->cell_record->site_point == point1, true);
+    BOOST_CHECK_EQUAL(edge1_1->cell->site_point == point2, true);
+    BOOST_CHECK_EQUAL(edge1_2->cell->site_point == point1, true);
 
     edge_it++;
     edge_type *edge2_1 = *edge_it;
     edge_type *edge2_2 = edge2_1->twin;    
-    BOOST_CHECK_EQUAL(edge2_1->cell_record->site_point == point1, true);
-    BOOST_CHECK_EQUAL(edge2_2->cell_record->site_point == point3, true);
+    BOOST_CHECK_EQUAL(edge2_1->cell->site_point == point1, true);
+    BOOST_CHECK_EQUAL(edge2_2->cell->site_point == point3, true);
 
     edge_it++;
     edge_type *edge3_1 = *edge_it;
     edge_type *edge3_2 = edge3_1->twin;
-    BOOST_CHECK_EQUAL(edge3_1->cell_record->site_point == point3, true);
-    BOOST_CHECK_EQUAL(edge3_2->cell_record->site_point == point2, true);
+    BOOST_CHECK_EQUAL(edge3_1->cell->site_point == point3, true);
+    BOOST_CHECK_EQUAL(edge3_2->cell->site_point == point2, true);
 
     BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
     BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
@@ -144,10 +150,11 @@
 
 // Sites: (0, 0), (0, 1), (1, 0), (1, 1).
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test3, T, test_types) {
-    typedef typename voronoi_builder<T>::edge_type edge_type;
-    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
+    typedef typename voronoi_output< point_2d<T> >::edge_type edge_type;
+    typedef typename voronoi_output< point_2d<T> >::edge_pointer_const_iterator_type 
+        edge_pointer_iterator_type;
+    typedef typename voronoi_output< point_2d<T> >::voronoi_vertices_const_iterator_type
+        voronoi_vertices_iterator_type;
 
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
@@ -158,17 +165,70 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
-    BOOST_CHECK_EQUAL(test_beach_line.get_cell_records().size(), 4);
-    BOOST_CHECK_EQUAL(test_beach_line.get_voronoi_vertices().size(), 2);
+    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+    BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_cell_records().size()), 4);
+    BOOST_CHECK_EQUAL(static_cast<T>(test_output.get_voronoi_vertices().size()), 1);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 4);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 1);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 4);
+
+    // Check voronoi vertex.
+    voronoi_vertices_iterator_type it = test_output.get_voronoi_vertices().begin();
+    BOOST_CHECK_EQUAL(static_cast<int>(it->incident_edges.size()), 4);
+    BOOST_CHECK_EQUAL(static_cast<int>(it->incident_edges.size()), it->num_incident_edges);
+    BOOST_CHECK_EQUAL(it->vertex.x() == static_cast<T>(0.5) &&
+                      it->vertex.y() == static_cast<T>(0.5), true);
+    BOOST_CHECK_EQUAL(it == it->vertex_it, true);
+
+    // Check voronoi edges.
+    edge_pointer_iterator_type edge_it = it->incident_edges.begin();
+    edge_type *edge1_1 = *edge_it;
+    edge_type *edge1_2 = edge1_1->twin;
+    BOOST_CHECK_EQUAL(edge1_1->cell->site_point == points[2], true);
+    BOOST_CHECK_EQUAL(edge1_2->cell->site_point == points[0], true);
+
+    edge_it++;
+    edge_type *edge2_1 = *edge_it;
+    edge_type *edge2_2 = edge2_1->twin;    
+    BOOST_CHECK_EQUAL(edge2_1->cell->site_point == points[0], true);
+    BOOST_CHECK_EQUAL(edge2_2->cell->site_point == points[1], true);
+
+    edge_it++;
+    edge_type *edge3_1 = *edge_it;
+    edge_type *edge3_2 = edge3_1->twin;
+    BOOST_CHECK_EQUAL(edge3_1->cell->site_point == points[1], true);
+    BOOST_CHECK_EQUAL(edge3_2->cell->site_point == points[3], true);
+
+    edge_it++;
+    edge_type *edge4_1 = *edge_it;
+    edge_type *edge4_2 = edge4_1->twin;
+    BOOST_CHECK_EQUAL(edge4_1->cell->site_point == points[3], true);
+    BOOST_CHECK_EQUAL(edge4_2->cell->site_point == points[2], true);
+
+    BOOST_CHECK_EQUAL(edge1_2->twin == edge1_1, true);
+    BOOST_CHECK_EQUAL(edge2_2->twin == edge2_1, true);
+    BOOST_CHECK_EQUAL(edge3_2->twin == edge3_1, true);
+    BOOST_CHECK_EQUAL(edge4_2->twin == edge4_1, true);
+
+    BOOST_CHECK_EQUAL(edge1_1->next == NULL && edge1_2->prev == NULL, true);
+    BOOST_CHECK_EQUAL(edge2_1->next == NULL && edge2_2->prev == NULL, true);
+    BOOST_CHECK_EQUAL(edge3_1->next == NULL && edge3_2->prev == NULL, true);
+    BOOST_CHECK_EQUAL(edge4_1->next == NULL && edge4_2->prev == NULL, true);
+
+    BOOST_CHECK_EQUAL(edge1_1->prev == edge4_2, true);
+    BOOST_CHECK_EQUAL(edge2_1->prev == edge1_2, true);
+    BOOST_CHECK_EQUAL(edge3_1->prev == edge2_2, true);
+    BOOST_CHECK_EQUAL(edge4_1->prev == edge3_2, true);
+
+    BOOST_CHECK_EQUAL(edge1_2->next == edge2_1, true);
+    BOOST_CHECK_EQUAL(edge2_2->next == edge3_1, true);
+    BOOST_CHECK_EQUAL(edge3_2->next == edge4_1, true);
+    BOOST_CHECK_EQUAL(edge4_2->next == edge1_1, true);
 }
 
 // Sites: {(x, y) | x = 0 .. 3, y = 0 .. 3}.
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test4, T, test_types) {
-    typedef typename voronoi_builder<T>::edge_type edge_type;
-    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
-
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
     for (int i = 0; i < 3; i++)
@@ -178,15 +238,15 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
+    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 9);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 4);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 12);
 }
 
 // Generate 10 random sites 1000 times.
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test4_1, T, test_types) {
-    typedef typename voronoi_builder<T>::edge_type edge_type;
-    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
-
     srand(static_cast<unsigned int>(time(NULL)));
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
@@ -206,11 +266,6 @@
 
 // Sites: {(x, y) | x = 0 .. 9, y = 0 .. 9}.
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test5, T, test_types) {
-    typedef typename voronoi_builder<T>::edge_type edge_type;
-    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
-
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
     for (int i = 0; i < 10; i++)
@@ -220,15 +275,15 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
+    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 100);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 81);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 180);
 }
 
 // Generate 100 random sites 100 times.
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test5_1, T, test_types) {
-    typedef typename voronoi_builder<T>::edge_type edge_type;
-    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
-
     srand(static_cast<unsigned int>(time(NULL)));
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
@@ -248,11 +303,6 @@
 
 // Sites: {(x, y) | x = 0 .. 33, y = 0 .. 33}.
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test6, T, test_types) {
-    typedef typename voronoi_builder<T>::edge_type edge_type;
-    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
-
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
     for (int i = 0; i < 33; i++)
@@ -262,15 +312,15 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
+    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 1089);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 1024);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 2112);
 }
 
 // Generate 1000 random sites 10 times.
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test6_1, T, test_types) {
-    typedef typename voronoi_builder<T>::edge_type edge_type;
-    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
-
     srand(static_cast<unsigned int>(time(NULL)));
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
@@ -290,11 +340,6 @@
 
 // Sites: {(x, y) | x = 0 .. 100, y = 0 .. 100}.
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test7, T, test_types) {
-    typedef typename voronoi_builder<T>::edge_type edge_type;
-    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
-
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
     for (int i = 0; i < 100; i++)
@@ -304,15 +349,15 @@
     
     test_beach_line.init(points);
     test_beach_line.run_sweepline();
+    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 10000);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 9801);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 19800);
 }
 
 // Generate 10000 random sites.
 BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test7_1, T, test_types) {
-    typedef typename voronoi_builder<T>::edge_type edge_type;
-    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-        voronoi_vertices_iterator;
-
     srand(static_cast<unsigned int>(time(NULL)));
     voronoi_builder<T> test_beach_line;
     std::vector< point_2d<T> > points;
@@ -324,21 +369,20 @@
     test_beach_line.run_sweepline();
 }
 
-//// Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
-//BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test8, T, test_types) {
-//    typedef typename voronoi_builder<T>::edge_type edge_type;
-//    typedef typename voronoi_builder<T>::edge_iterator edge_iterator;
-//    typedef typename voronoi_builder<T>::voronoi_vertices_iterator
-//        voronoi_vertices_iterator;
-//
-//    srand(static_cast<unsigned int>(time(NULL)));
-//    voronoi_builder<T> test_beach_line;
-//    std::vector< point_2d<T> > points;
-//    for (int i = 0; i < 270; i++)
-//        for (int j = 0; j < 270; j++)
-//            points.push_back(make_point_2d<T>(static_cast<T>(rand() % 1000),
-//                                              static_cast<T>(rand() % 1000)));
-//    
-//    test_beach_line.init(points);
-//    test_beach_line.run_sweepline();
-//}
\ No newline at end of file
+// Sites: {(x, y) | x = 0 .. 333, y = 0 .. 333}.
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test8, T, test_types) {
+    voronoi_builder<T> test_beach_line;
+    std::vector< point_2d<T> > points;
+    for (int i = 0; i < 333; i++)
+        for (int j = 0; j < 333; j++)
+            points.push_back(make_point_2d<T>(static_cast<T>(i),
+                                              static_cast<T>(j)));
+    
+    test_beach_line.init(points);
+    test_beach_line.run_sweepline();
+    const voronoi_output< point_2d<T> > &test_output = test_beach_line.get_output();
+
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_cells(), 110889);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_vertices(), 110224);
+    BOOST_CHECK_EQUAL(test_output.get_num_voronoi_edges(), 221112);
+}