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

Subject: [Boost-commit] svn:boost r62672 - in sandbox/SOC/2010/sweepline: boost/sweepline libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-06-09 13:21:23

Author: asydorchuk
Date: 2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
New Revision: 62672
URL: http://svn.boost.org/trac/boost/changeset/62672

Log:
Removed virtual functions from event_types implementations (changed architecture appropriately). 
Added beach_line_node class (with unit tests).
Added node_comparer class (with unit tests).
Added beach_line class (voronoi math implementation).

Text files modified: 
   sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp               |   325 +++++++++++++++++++++++++++++++++++++++ 
   sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp              |    62 ++++---                                 
   sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp              |   130 +++++++++++----                         
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp          |    22 -                                       
   sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2               |     1                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp      |    95 +++++++++++                             
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp     |    75 +++++++-                                
   sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp       |     4                                         
   sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp |    14 +                                       
   9 files changed, 632 insertions(+), 96 deletions(-)

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp	2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -8,6 +8,8 @@
 //  See http://www.boost.org for updates, documentation, and revision history.
 
 #include <map>
+#include <vector>
+#include <cmath>
 
 #ifndef BOOST_SWEEPLINE_BEACH_LINE
 #define BOOST_SWEEPLINE_BEACH_LINE
@@ -15,7 +17,328 @@
 namespace boost {
 namespace sweepline {
 
-    //Not implemented yet.
+    template <typename Point2D>
+    struct beach_line_node {
+    public:
+        typedef typename Point2D Point2D;
+        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;
+
+        beach_line_node() {}
+
+        explicit beach_line_node(const Point2D &new_point) {
+            left_point_ = new_point;
+            right_point_ = new_point;
+        }
+
+        beach_line_node(const Point2D &left_point, const Point2D &right_point) {
+            left_point_ = left_point;
+            right_point_ = right_point;
+        }
+
+        const Point2D &get_left_point() const {
+            return left_point_;
+        }
+
+        const Point2D &get_right_point() const {
+            return right_point_;
+        }
+
+        coordinate_type get_sweepline_coord() const {
+            return std::max(left_point_.x(), right_point_.x());
+        }
+
+        const Point2D& get_new_point() const {
+            if (left_point_.x() > right_point_.x())
+                return left_point_;
+            return right_point_;
+        }
+
+        Point2D get_intersection_point(bool use_right_point, const Point2D &new_point) const {
+            const Point2D &use_point = (use_right_point) ? right_point_ : left_point_;
+            coordinate_type vertex_x = ((new_point.y() - use_point.y()) *
+                                        (new_point.y() - use_point.y()) /
+                                        (use_point.x() - new_point.x()) +
+                                         use_point.x() + new_point.x()) *
+                                         static_cast<coordinate_type>(0.5);
+            return make_point_2d(vertex_x, new_point.y());
+        }
+
+        bool less(const Point2D &new_point) const {
+            coordinate_type sweepline_coord = new_point.x();
+            coordinate_type new_node_coord = new_point.y();
+            coordinate_type a1 = left_point_.x() - sweepline_coord;
+            coordinate_type a2 = right_point_.x() - sweepline_coord;
+            coordinate_type b1 = new_node_coord - left_point_.y();
+            coordinate_type b2 = new_node_coord - right_point_.y();
+            coordinate_type c = left_point_.x() - right_point_.x();
+            return a1 * a2 * c + a2 * b1 * b1 < a1 * b2 * b2;
+        }
+
+    private:
+        Point2D left_point_;
+        Point2D right_point_;
+    };
+
+    template <typename Point2D>
+    struct beach_line_node_data {
+    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;
+
+        beach_line_node_data() {}
+    private:
+    };
+
+    template <typename BeachLineNode>
+    struct node_comparer {
+    public:
+        typedef typename BeachLineNode::coordinate_type coordinate_type;
+
+        bool operator() (const BeachLineNode &node1, const BeachLineNode &node2) const {
+            coordinate_type node1_line = node1.get_sweepline_coord();
+            coordinate_type node2_line = node2.get_sweepline_coord();
+            if (node1_line == node2_line) {
+                if (node1.get_left_point() == node2.get_right_point() &&
+                    node1.get_right_point() == node2.get_left_point())
+                    return node1.get_right_point().x() == node1_line;
+                return node1.get_left_point().y() <= node2.get_left_point().y();
+            }
+            else if (node1_line < node2_line)
+                return node1.less(node2.get_new_point());
+            else
+                return !node2.less(node1.get_new_point());
+        }
+    };
+
+    template <typename Key, typename Value, typename NodeComparer, typename EventQueue>
+    class beach_line {
+    public:
+        typedef typename Key::Point2D Point2D;
+        typedef typename Key::coordinate_type coordinate_type;
+        typedef typename Key::site_event_type site_event_type;
+        typedef typename Key::circle_event_type circle_event_type;
+        typedef typename std::map< Key, Value, node_comparer<Key> >::const_iterator beach_line_iterator;
+        typedef typename std::pair< beach_line_iterator, bool > beach_line_pair;
+
+        struct event_processor {
+            explicit event_processor(beach_line *b_line)
+                : beach_line_(b_line) {}
+
+            void operator()(const site_event_type &site_event) {
+                beach_line_->process_site_event(site_event);
+            }
+
+            void operator()(const circle_event_type &circle_event) {
+                beach_line_->process_circle_event(circle_event);
+            }
+
+            beach_line* beach_line_;
+        };
+
+        beach_line() {
+            event_queue_ = new EventQueue;
+            event_processor_ = new event_processor(this);
+        }
+
+        ~beach_line() {
+            if (event_queue_) {
+                delete event_queue_;
+                event_queue_ = NULL;
+            }
+            if (event_processor_) {
+                delete event_processor_;
+                event_processor_ = NULL;
+            }
+        }
+
+        void init(const std::vector<Point2D> &sites) {
+            std::sort(sites.begin(), sites.end());
+            int skip = 0;
+
+            if (sites.size() == 1) {
+                skip = 1
+            } else {
+                std::vector<Point2D>::const_iterator it = sites.begin();
+                while(it != sites.end() && it->x() == sites.begin()->x()) {
+                    it++;
+                    skip++;
+                }
+
+                if (num == 1) {
+                    init_beach_line(*sites.begin(), *it);
+                } else {
+                    init_beach_line(sites.begin(), it);
+                }
+            }
+            event_queue_->init(sites, skip);
+        }
+
+        void reset() {
+            event_queue_.reset();
+            beach_line_.clear();
+        }
+
+        void run_sweepline() {
+            while (!event_queue_->empty()) {
+                event_queue_->process_top_event(*event_processor_);
+                event_queue_->pop();
+            }
+        }
+
+        void process_site_event(const site_event_type &site_event) {
+            Key new_key(site_event.get_point());
+            beach_line_iterator it = beach_line_.lower_bound(new_key);
+
+            Point2D point_arc;
+            Point2D voronoi_vertex;
+            if (it == beach_line_.end()) {
+                it--;
+                point_arc = it->first.get_right_point();
+                voronoi_vertex = it->first.get_intersection_point(true, site_event.get_point());
+                activate_circle_event(it->first.get_left_point(),
+                                    it->first.get_right_point(),
+                                    site_event.get_point());
+            } else if (it == beach_line_.begin()) {
+                point_arc = it->first.get_left_point();
+                voronoi_vertex = it->first.get_intersection_point(false, site_event.get_point());
+                activate_circle_event(site_event.get_point(),
+                                    it->first.get_left_point(),
+                                    it->first.get_right_point());
+            } else {
+                point_arc = it->first.get_left_point();
+                voronoi_vertex = it->first.get_intersection_point(false, site_event.get_point());
+
+                const Point2D &point2 = it->first.get_left_point();
+                const Point2D &point3 = it->first.get_right_point();
+                it--;
+                const Point2D &point1 = it->first.get_right_point();
+                
+                deactivate_circle_event(point1, point2, point3);
+                activate_circle_event(point1, point2, site_event.get_point());
+                activate_circle_event(site_event.get_point(), point2, point3);
+            }
+
+            Key new_left_node(point_arc, site_event.get_point());
+            Key new_right_node(site_event.get_point(), point_arc);
+            beach_line_.insert(std::pair<Key, Value>(new_left_node, Value()));
+            beach_line_.insert(std::pair<Key, Value>(new_right_node, Value()));
+        }
+
+        void process_circle_event(const circle_event_type &circle_event) {
+            Key new_key(circle_event.get_bisector_left_point(),
+                        circle_event.get_bisector_right_point());
+            beach_line_iterator it_first = beach_line_.find(new_key);
+            beach_line_iterator it_last = it_first;
+
+            if (it_first == beach_line_.end())
+                return;
+
+
+            Point2D point2 = it_first->first.get_left_point();
+            Point2D point3 = it_first->first.get_right_point();
+            it_first--;
+            it_last++;
+            Point2D point1 = it_first->first.get_left_point();
+            beach_line_.erase(it_first, it_last);
+            Key new_node(point1, point3);
+            beach_line_pair it_pair = 
+                beach_line_.insert(std::pair<Key, Value>(new_node, Value()));
+
+            it_first = it_pair.first;
+            it_last = it_first;
+
+            if (it_first != beach_line_.begin()) {
+                it_first--;
+                const Point2D &point_l1 = it_first->first.get_left_point();
+                deactivate_circle_event(point_l1, point1, point2);
+                if (it_first != beach_line_.begin()) {
+                    it_first--;
+                    const Point2D &point_l2 = it_first->first.get_left_point();
+                    activate_circle_event(point_l2, point_l1, point1);
+                }
+            }
+
+            it_last++;
+            if (it_last != beach_line_.end()) {
+                const Point2D &point_r1 = it_last->first.get_right_point();
+                deactivate_circle_event(point2, point3, point_r1);
+                it_last++;
+                if (it_last != beach_line_.end()) {
+                    it_last++;
+                    const Point2D &point_r2 = it_last->first.get_right_point();
+                    activate_circle_event(point3, point_r1, point_r2);
+                }
+            }            
+        }
+
+    protected:
+        void init_beach_line(typename std::vector<Point2D>::const_iterator it_begin,
+                             typename std::vector<Point2D>::const_iterator it_end) {
+             typename std::vector<Point2D>::const_iterator it_first = it_begin;
+             typename std::vector<Point2D>::const_iterator it_second = it_begin;
+             it_second++;
+             while (it_second != it_end) {
+                 beach_line_node new_node(*it_first, *it_second);
+                 beach_line_.insert(std::pair<Key, Value>(new_node, Value()));
+                 it_first++;
+                 it_second++;
+             }
+        }
+
+        void init_beach_line(const Point2D &first_point, const Point2D &second_point) {
+            beach_line_node new_left_node(firs_point, second_point);
+            beach_line_node new_second_node(second_point, first_point);
+            beach_line_.insert(std::pair<Key, Value>(new_left_node, Value()));
+            beach_line_.insert(std::pair<Key, Value>(new_right_node, Value()));
+        }
+
+        bool create_circle_event(const Point2D &point1,
+                                 const Point2D &point2,
+                                 const Point2D &point3,
+                                 circle_event_type &c_event) const {
+            coordinate_type a = (point1.x() - point2.x())*(point2.y() - point3.y()) -
+                                (point1.y() - point2.y())*(point2.x() - point3.x());
+            if (a <= static_cast<coordinate_type>(0))
+                return false;
+            coordinate_type b1 = (point1.x() - point2.x())*(point1.x() + point2.x()) +
+                                 (point1.y() - point2.y())*(point1.y() + point2.y());
+            coordinate_type b2 = (point2.x() - point3.x())*(point2.x() + point3.x()) +
+                                 (point2.y() - point3.y())*(point2.y() + point3.y());
+            coordinate_type c_x = (b1*(point2.y() - point3.y()) - b2*(point1.y() - point2.y())) / a *
+                                  static_cast<coordinate_type>(0.5);
+            coordinate_type c_y = (b2*(point1.x() - point2.x()) - b1*(point2.x() - point3.x())) / a *
+                                  static_cast<coordinate_type>(0.5);
+            coordinate_type sqr_radius = (c_x-point1.x())*(c_x-point1.x()) + (c_y-point1.y())*(c_y-point1.y());
+            coordinate_type radius = static_cast<coordinate_type>(sqr_radius);
+            c_event = make_circle_event(c_x + radius, c_y);
+            c_event.set_bisector(point2, point3);
+            return true;
+        }
+
+        void activate_circle_event(const Point2D &point1,
+                                   const Point2D &point2,
+                                   const Point2D &point3) const {
+            circle_event_type c_event;
+            if (create_circle_event(point1, point2, point3, c_event))
+                event_queue_->push(c_event);
+        }
+
+        void deactivate_circle_event(const Point2D &point1,
+                                     const Point2D &point2,
+                                     const Point2D &point3) const {
+            circle_event_type c_event;
+            if (create_circle_event(point1, point2, point3, c_event))
+                event_queue_->deactivate_event(c_event);
+        }
+
+    private:
+        EventQueue* event_queue_;
+        event_processor* event_processor_;
+        std::map< Key, Value, NodeComparer > beach_line_;
+    };
 
 } // sweepline
 } // boost

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp	2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -21,20 +21,26 @@
     class event_queue {
     public:
         typedef typename Point2D::coordinate_type coordinate_type;
-        typedef typename Point2D::sweepline_event_type sweepline_event_type;
         typedef typename Point2D::site_event_type site_event_type;
         typedef typename Point2D::circle_event_type circle_event_type;
-        typedef typename Point2D::sweepline_event_type::kEventType kEventType;
+
+        enum kEventType {
+            SITE_EVENT = 0,
+            CIRCLE_EVENT = 1,
+            NONE = 2,
+        };
 
         event_queue() {
             site_events_iterator_ = site_events_.begin();
         }
 
-        void init(const std::vector<Point2D> &sites) {
+        void init(const std::vector<Point2D> &sites, int skip) {
             site_events_.clear();
-            site_events_.resize(sites.size());
-            for (int i = 0; i < sites.size(); i++)
-                site_events_[i] = make_site_event(sites[i].x(), sites[i].y());
+            site_events_.resize(sites.size() - skip);
+            std::vector<Point2D>::const_iterator sites_it;
+            int index = 0;
+            for (sites_it = sites.begin() + skip; sites_it != sites.end(); sites_it++)
+                site_events_[index++] = make_site_event(sites_it->x(), sites_it->y());
             init_site_events();
         }
 
@@ -55,53 +61,57 @@
             return true;
         }
 
-        const sweepline_event_type &top() {
+        template <typename event_handler>
+        void process_top_event(event_handler &functor) {
             kEventType top_event_type = get_top_event_type();
-            if (top_event_type == kEventType::SITE_EVENT)
-                return *site_events_iterator_;
+            if (top_event_type == SITE_EVENT)
+                functor(*site_events_iterator_);
             else
-                return circle_events_.top();
+                functor(circle_events_.top());
         }
 
         void pop() {
             kEventType top_event_type = get_top_event_type();
-            if (top_event_type == kEventType::SITE_EVENT)
+            if (top_event_type == SITE_EVENT)
                 site_events_iterator_++;
-            else if (top_event_type == kEventType::CIRCLE_EVENT)
+            else if (top_event_type == CIRCLE_EVENT)
                 circle_events_.pop();
         }
 
-        void push(circle_event_type circle_event) {
+        void push(circle_event_type &circle_event) {
             circle_events_.push(circle_event);
         }
 
+        void deactivate_event(circle_event_type &circle_event) {
+            deactivated_events_.push(circle_event);
+        }
+
     private:
         void init_site_events() {
-            std::sort(site_events_.begin(), site_events_.end());
             site_events_iterator_ = site_events_.begin();
-            last_event_type_ = kEventType::SITE_EVENT;
         }
 
         void remove_not_active_events() {
-            while (!circle_events_.empty() && 
-                   !circle_events_.top().is_active())
+            while (!circle_events_.empty() && !deactivated_events_.empty() &&
+                circle_events_.top() == deactivated_events_.top()) {
                 circle_events_.pop();
+                deactivated_events_.pop();
+            }
         }
 
         kEventType get_top_event_type() {
             remove_not_active_events();
-
             if (site_events_iterator_ == site_events_.end())
-                return kEventType::CIRCLE_EVENT;
+                return CIRCLE_EVENT;
             else if (circle_events_.empty())
-                return kEventType::SITE_EVENT;
+                return SITE_EVENT;
             else {
-                if ((*site_events_iterator_) <= circle_events_.top())
-                    return kEventType::SITE_EVENT;
+                if (site_events_iterator_->get_point() <= circle_events_.top().get_point())
+                    return SITE_EVENT;
                 else
-                    return kEventType::CIRCLE_EVENT;
+                    return CIRCLE_EVENT;
             }
-            return kEventType::NONE;
+            return NONE;
         }
 
         typename std::vector<site_event_type>::const_iterator 
@@ -110,7 +120,9 @@
         std::priority_queue< circle_event_type,
                              std::vector<circle_event_type>,
                              std::greater<circle_event_type> > circle_events_;
-        kEventType last_event_type_;
+        std::priority_queue< circle_event_type,
+                             std::vector<circle_event_type>,
+                             std::greater<circle_event_type> > deactivated_events_;
 
         //Disallow copy constructor and operator=
         event_queue(const event_queue&);

Modified: sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp
==============================================================================
--- sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp	(original)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp	2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -14,19 +14,15 @@
 namespace sweepline {
     
     template <typename T>
-    class sweepline_event;
-
-    template <typename T>
-    class site_event;
+    struct site_event;
     
     template <typename T>
-    class circle_event;
+    struct circle_event;
 
     template <typename T>
-    class point_2d {
+    struct point_2d {
     public:
         typedef T coordinate_type;
-        typedef sweepline_event<T> sweepline_event_type;
         typedef site_event<T> site_event_type;
         typedef circle_event<T> circle_event_type;
 
@@ -90,33 +86,52 @@
     }
 
     template <typename T>
-    class sweepline_event : public point_2d<T> {
+    struct site_event {
     public:
-        enum kEventType {
-            SITE_EVENT = 0,
-            CIRCLE_EVENT = 1,
-            NONE = 2,
-        };
+        typedef T coordinate_type;
 
-        sweepline_event() : point_2d() {}
+        site_event() {}
+        
+        site_event(T x, T y) : point_(x, y) {}
 
-        sweepline_event(T x, T y) : point_2d(x, y) {}
+        bool operator==(const site_event &s_event) const {
+            return point_ == s_event.get_point();
+        }
 
-        virtual kEventType get_event_type() const {
-            return NONE;
+        bool operator!=(const site_event &s_event) const {
+            return point_ != s_event.get_point();
         }
-    };
 
-    template <typename T>
-    class site_event : public sweepline_event<T> {
-    public:
-        site_event() : sweepline_event() {}
-        
-        site_event(T x, T y) : sweepline_event(x, y) {}
+        bool operator<(const site_event &s_event) const {
+            return point_ < s_event.get_point();
+        }
+
+        bool operator<=(const site_event &s_event) const {
+            return point_ <= s_event.get_point();
+        }
 
-        virtual kEventType get_event_type() const {
-            return SITE_EVENT;
+        bool operator>(const site_event &s_event) const {
+            return point_ > s_event.get_point();
         }
+
+        bool operator>=(const site_event &s_event) const {
+            return point_ >= s_event.get_point();
+        }
+
+        coordinate_type x() const {
+            return point_.x();
+        }
+
+        coordinate_type y() const {
+            return point_.y();
+        }
+
+        const point_2d<T> &get_point() const {
+            return point_;
+        }
+
+    private:
+        point_2d<T> point_;
     };
 
     template <typename T>
@@ -124,27 +139,70 @@
         return site_event<T>(x,y);
     }
 
+    struct BeachLineNode;
+
     template <typename T>
-    class circle_event : public site_event<T> {
+    struct circle_event {
     public:
-        circle_event() : site_event() { 
-            active_ = true;
+        typedef T coordinate_type;
+
+        circle_event() {}
+
+        circle_event(T x, T y) : point_(x, y) {}
+
+        bool operator==(const circle_event &c_event) const {
+            return point_ == c_event.get_point();
+        }
+
+        bool operator!=(const circle_event &c_event) const {
+            return point_ != c_event.get_point();
+        }
+
+        bool operator<(const circle_event &c_event) const {
+            return point_ < c_event.get_point();
+        }
+
+        bool operator<=(const circle_event &c_event) const {
+            return point_ <= c_event.get_point();
+        }
+
+        bool operator>(const circle_event &c_event) const {
+            return point_ > c_event.get_point();
+        }
+
+        bool operator>=(const circle_event &c_event) const {
+            return point_ >= c_event.get_point();
+        }
+
+        coordinate_type x() const {
+            return point_.x();
+        }
+
+        coordinate_type y() const {
+            return point_.y();
+        }
+
+        const point_2d<T> &get_point() const {
+            return point_;
         }
 
-        circle_event(T x, T y) : site_event(x, y) {
-            active_ = true;
+        void set_bisector(const point_2d<T> &left_point, const point_2d<T> &right_point) {
+            bisector_left_point_ = left_point;
+            bisector_right_point_ = right_point;
         }
 
-        bool is_active() {
-            return active_;
+        const point_2d<T> &get_bisector_left_point() const {
+            return bisector_left_point_;
         }
 
-        virtual kEventType get_event_type() const {
-            return CIRCLE_EVENT;
+        const point_2d<T> &get_bisector_right_point() const {
+            return bisector_right_point_;
         }
 
     private:
-        bool active_;
+        point_2d<T> point_;
+        point_2d<T> bisector_left_point_;
+        point_2d<T> bisector_right_point_;
     };
 
     template <typename T>

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-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -15,17 +15,14 @@
 namespace boost {
 namespace sweepline {
 
-    template <typename Point2D, typename EventQueue, typename BeachLine>
+template <typename Point2D, typename BeachLine>
     class voronoi_builder {
     public:
-        voronoi_builder() {}
+        voronoi_builder() {
+            beach_line_ = new BeachLine;
+        }
         
         ~voronoi_builder() {
-            if (event_queue_) {
-                delete event_queue_;
-                event_queue_ = NULL;
-            }
-
             if (beach_line_) {
                 delete beach_line_;
                 beach_line_ = NULL;
@@ -33,25 +30,18 @@
         }
 
         void init(const std::vector<Point2D> &sites) {
-            event_queue_->init(sites);
+            beach_line_->init(sites);
         }
 
         void reset() {
-            event_queue_->reset();
             beach_line_->reset();
         }
 
         void build_voronoi_diagram() {
-            while (!event_queue_->empty())
-                make_one_iteration();
+            beach_line_->run_sweepline();
         }
 
     private:
-        void make_one_iteration() {
-            //Not implemented yet
-        }
-
-        EventQueue* event_queue_;
         BeachLine* beach_line_;
     };
 

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-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -13,4 +13,5 @@
 test-suite "sweepline"
     : 
         [ run event_queue_test.cpp :  :  : <link>static ]
+	[ run beach_line_test.cpp :  :  : <link>static ]
     ;
\ No newline at end of file

Modified: sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp
==============================================================================
--- sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp	(original)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp	2010-06-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -5,4 +5,97 @@
 //    (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.
\ No newline at end of file
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+#include "test_type_list.hpp"
+#include <boost/sweepline/beach_line.hpp>
+#include <boost/sweepline/event_types.hpp>
+using namespace boost::sweepline;
+
+#define BOOST_TEST_MODULE beach_line_test
+#include <boost/test/test_case_template.hpp>
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_vertex_computation_test1, T, test_types) {
+    typedef beach_line_node< point_2d<T> > bline_node;
+    bline_node initial_node(make_point_2d<T>(static_cast<T>(0), static_cast<T>(0)),
+                            make_point_2d<T>(static_cast<T>(0), static_cast<T>(2)));
+
+    point_2d<T> point1 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(0));
+    point_2d<T> point2 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(1));
+    point_2d<T> point3 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(2));
+
+    point_2d<T> voronoi_vertex1 = initial_node.get_intersection_point(false, point1);
+    BOOST_CHECK_EQUAL(voronoi_vertex1.x() == static_cast<T>(0.5) &&
+                      voronoi_vertex1.y() == static_cast<T>(0.0), true);
+
+    point_2d<T> voronoi_vertex2_1 = initial_node.get_intersection_point(false, point2);
+    point_2d<T> voronoi_vertex2_2 = initial_node.get_intersection_point(true, point2);
+    BOOST_CHECK_EQUAL(voronoi_vertex2_1.x() == static_cast<T>(0.0) &&
+                      voronoi_vertex2_1.y() == static_cast<T>(1.0) &&
+                      voronoi_vertex2_1.x() == voronoi_vertex2_2.x() &&
+                      voronoi_vertex2_1.y() == voronoi_vertex2_2.y(), true);
+
+    point_2d<T> voronoi_vertex3 = initial_node.get_intersection_point(true, point3);
+    BOOST_CHECK_EQUAL(voronoi_vertex3.x() == static_cast<T>(0.5) &&
+                      voronoi_vertex3.y() == static_cast<T>(2.0), true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test1, T, test_types) {
+    typedef beach_line_node< point_2d<T> > bline_node;
+    typedef 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;
+
+    bline_node initial_node(make_point_2d<T>(static_cast<T>(0), static_cast<T>(0)),
+                            make_point_2d<T>(static_cast<T>(0), static_cast<T>(2)));
+    test_beach_line[initial_node] = 0;
+    BOOST_CHECK_EQUAL(test_beach_line.size(), 1);
+    
+    bline_node new_node1(make_point_2d<T>(static_cast<T>(1), static_cast<T>(0)));
+    bline_node new_node2(make_point_2d<T>(static_cast<T>(1), static_cast<T>(1)));
+    bline_node new_node3(make_point_2d<T>(static_cast<T>(1), static_cast<T>(2)));
+    bline_node new_node4(make_point_2d<T>(static_cast<T>(1), static_cast<T>(1.000001)));
+    bline_node new_node5(make_point_2d<T>(static_cast<T>(1), static_cast<T>(0.999999)));
+    
+    bline_it it = test_beach_line.lower_bound(new_node1);
+    BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
+
+    it = test_beach_line.lower_bound(new_node2);
+    BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
+
+    it = test_beach_line.lower_bound(new_node3);
+    BOOST_CHECK_EQUAL(it == test_beach_line.end(), true);
+
+    it = test_beach_line.lower_bound(new_node4);
+    BOOST_CHECK_EQUAL(it == test_beach_line.end(), true);
+
+    it = test_beach_line.lower_bound(new_node5);
+    BOOST_CHECK_EQUAL(it == test_beach_line.begin(), true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(node_comparer_test2, T, test_types) {
+    typedef beach_line_node< point_2d<T> > bline_node;
+    typedef 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;
+
+    point_2d<T> point1 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(0));
+    point_2d<T> point2 = make_point_2d<T>(static_cast<T>(0), static_cast<T>(2));
+    bline_node initial_node(point1, point2);
+    test_beach_line[initial_node] = 0;
+
+    point_2d<T> point3 = make_point_2d<T>(static_cast<T>(1), static_cast<T>(0));
+    bline_node node1(point1, point3);
+    bline_node node2(point3, point1);
+    test_beach_line.insert(std::pair< bline_node, int>(node1, 1));
+    test_beach_line.insert(std::pair< bline_node, int>(node2, 2));
+    
+    bline_it it = test_beach_line.begin();
+    BOOST_CHECK_EQUAL(it->second == 1, true);
+
+    ++it;
+    BOOST_CHECK_EQUAL(it->second == 2, true);
+
+    ++it;
+    BOOST_CHECK_EQUAL(it->second == 0, true);
+}
\ 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-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -16,11 +16,33 @@
 #include <boost/test/test_case_template.hpp>
 
 #define CHECK_TOP_ELEMENT_EQUALITY(TOP, X, Y) \
-    BOOST_CHECK_EQUAL(TOP.x() == static_cast<T>(X) && \
-                      TOP.y() == static_cast<T>(Y), true)
+    BOOST_CHECK_EQUAL(TOP.x == static_cast<T>(X) && \
+                      TOP.y == static_cast<T>(Y), true)
+
+template <typename Point2D>
+struct event_processor {
+    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;
+
+    event_processor() {}
+
+    void operator()(const site_event_type &site_event) {
+        x = site_event.x();
+        y = site_event.y();
+    }
+
+    void operator()(const circle_event_type &circle_event) {
+        x = circle_event.x();
+        y = circle_event.y();
+    }
+        
+    coordinate_type x;
+    coordinate_type y;
+};
 
 BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test1, T, test_types) {
-    typedef sweepline_event<T>::kEventType kEventType;
+    event_processor< point_2d<T> > test_processor;
 
     event_queue< point_2d<T> > event_q;
     BOOST_CHECK_EQUAL(event_q.empty(), true);
@@ -33,11 +55,15 @@
         T y = static_cast<T>(10-i);
         site_event_vec.push_back(make_point_2d(x, y));
     }
-    event_q.init(site_event_vec);
-    CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 0, 0);
-
+    sort(site_event_vec.begin(), site_event_vec.end());
+    event_q.init(site_event_vec, 0);
+    
+    event_q.process_top_event(test_processor);
+    CHECK_TOP_ELEMENT_EQUALITY(test_processor, 0, 0);
     event_q.pop();
-    CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 1, 1);
+
+    event_q.process_top_event(test_processor);
+    CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1, 1);
 
     for (int i = 5; i < 10; i++) {
         T x = static_cast<T>(10-i);
@@ -52,18 +78,41 @@
     }
     
     for (int i = 0; i < 10; i++) {
-        CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 1 + i/2, 1 + i/2);
-        BOOST_CHECK_EQUAL(event_q.top().get_event_type(),
-            (i&1)?(kEventType::CIRCLE_EVENT):(kEventType::SITE_EVENT));
+        event_q.process_top_event(test_processor);
+        CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1 + i/2, 1 + i/2);
         event_q.pop();
     }
 
     for (int i = 10; i < 20; i++) {
-        CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 1 + i/2, 1 + (i-1)/2);
-        BOOST_CHECK_EQUAL(event_q.top().get_event_type(),
-            (i&1)?(kEventType::SITE_EVENT):(kEventType::CIRCLE_EVENT));
+        event_q.process_top_event(test_processor);
+        CHECK_TOP_ELEMENT_EQUALITY(test_processor, 1 + i/2, 1 + (i-1)/2);
         event_q.pop();
     }
     
     BOOST_CHECK_EQUAL(event_q.empty(), true);
+}
+
+BOOST_AUTO_TEST_CASE_TEMPLATE(event_queue_test2, T, test_types) {
+    event_processor< point_2d<T> > test_processor;
+    event_queue< point_2d<T> > event_q;
+
+    for (int i = 0; i < 10; i++) {
+        T x = static_cast<T>(10-i);
+        T y = static_cast<T>(10-i);
+        event_q.push(make_circle_event(x, y));
+    }
+
+    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);
+        event_q.deactivate_event(make_circle_event(x, y));   
+    }
+
+    for (int i = 0; i < 5; i++) {
+        event_q.process_top_event(test_processor);
+        CHECK_TOP_ELEMENT_EQUALITY(test_processor, 2 + 2*i, 2 + 2*i);
+        event_q.pop();
+    }
+
+    BOOST_CHECK_EQUAL(event_q.empty(), true);
 }
\ 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-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -12,9 +12,7 @@
 
 #include <boost/mpl/list.hpp>
 
-typedef boost::mpl::list<int,
-                         long long,
-                         float,
+typedef boost::mpl::list<float,
                          double,
                          long double> test_types;
 

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-09 13:21:22 EDT (Wed, 09 Jun 2010)
@@ -5,4 +5,16 @@
 //    (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.
\ No newline at end of file
+//  See http://www.boost.org for updates, documentation, and revision history.
+
+//#include "test_type_list.hpp"
+//#include <boost/sweepline/beach_line.hpp>
+//#include <boost/sweepline/event_queue.hpp>
+//#include <boost/sweepline/event_types.hpp>
+//#include <boost/sweepline/voronoi_builder.hpp>
+//
+//#define BOOST_TEST_MODULE voronoi_builder_test
+//#include <boost/test/test_case_template.hpp>
+//
+//BOOST_AUTO_TEST_CASE_TEMPLATE(voronoi_builder_test1, T, test_types) {
+//}
\ No newline at end of file