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

Subject: [Boost-commit] svn:boost r62357 - in sandbox/SOC/2010/sweepline: . boost/sweepline libs/sweepline/test
From: sydorchuk.andriy_at_[hidden]
Date: 2010-05-31 16:43:41

Author: asydorchuk
Date: 2010-05-31 16:43:40 EDT (Mon, 31 May 2010)
New Revision: 62357
URL: http://svn.boost.org/trac/boost/changeset/62357

Log:
Added event_queue class with define event types.
Added basic project architecture classes.
Added build rules.
Added unit test for the event_queue class.
Added:
   sandbox/SOC/2010/sweepline/Jamfile.v2   (contents, props changed)
   sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp   (contents, props changed)
   sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp   (contents, props changed)
   sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp   (contents, props changed)
   sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp   (contents, props changed)
   sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp   (contents, props changed)
   sandbox/SOC/2010/sweepline/project-root.jam   (contents, props changed)

Added: sandbox/SOC/2010/sweepline/Jamfile.v2
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/Jamfile.v2	2010-05-31 16:43:40 EDT (Mon, 31 May 2010)
@@ -0,0 +1,12 @@
+#          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)
+
+project sweepline
+    : requirements
+        <include>.
+        <include>$(BOOST_ROOT)
+    :
+        build-dir bin.v2
+    ;

Added: sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/beach_line.hpp	2010-05-31 16:43:40 EDT (Mon, 31 May 2010)
@@ -0,0 +1,23 @@
+// Boost sweepline/beach_line.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.
+
+#include <map>
+
+#ifndef BOOST_SWEEPLINE_BEACH_LINE
+#define BOOST_SWEEPLINE_BEACH_LINE
+
+namespace boost {
+namespace sweepline {
+
+    //Not implemented yet.
+
+} // sweepline
+} // boost
+
+#endif
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/event_queue.hpp	2010-05-31 16:43:40 EDT (Mon, 31 May 2010)
@@ -0,0 +1,123 @@
+// Boost sweepline/event_queue.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.
+
+#ifndef BOOST_SWEEPLINE_EVENT_QUEUE
+#define BOOST_SWEPPLINE_EVENT_QUEUE
+
+#include <queue>
+
+namespace boost {
+namespace sweepline {
+
+    // Event queue data structure, contains two types of events:
+    // site events and circle events.
+    template <typename Point2D>
+    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;
+
+        event_queue() {
+            site_events_iterator_ = site_events_.begin();
+        }
+
+        void init(const std::vector<Point2D> &sites) {
+            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());
+            init_site_events();
+        }
+
+        void reset() {
+            site_events_iterator_ = site_events_.begin();
+            while (!circle_events_.empty())
+                circle_events_.pop();
+        }
+
+        bool empty() {
+            if (site_events_iterator_ != site_events_.end())
+                return false;
+
+            remove_not_active_events();
+            if (!circle_events_.empty())
+                return false;
+
+            return true;
+        }
+
+        const sweepline_event_type &top() {
+            kEventType top_event_type = get_top_event_type();
+            if (top_event_type == kEventType::SITE_EVENT)
+                return *site_events_iterator_;
+            else
+                return circle_events_.top();
+        }
+
+        void pop() {
+            kEventType top_event_type = get_top_event_type();
+            if (top_event_type == kEventType::SITE_EVENT)
+                site_events_iterator_++;
+            else if (top_event_type == kEventType::CIRCLE_EVENT)
+                circle_events_.pop();
+        }
+
+        void push(circle_event_type circle_event) {
+            circle_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())
+                circle_events_.pop();
+        }
+
+        kEventType get_top_event_type() {
+            remove_not_active_events();
+
+            if (site_events_iterator_ == site_events_.end())
+                return kEventType::CIRCLE_EVENT;
+            else if (circle_events_.empty())
+                return kEventType::SITE_EVENT;
+            else {
+                if ((*site_events_iterator_) <= circle_events_.top())
+                    return kEventType::SITE_EVENT;
+                else
+                    return kEventType::CIRCLE_EVENT;
+            }
+            return kEventType::NONE;
+        }
+
+        typename std::vector<site_event_type>::const_iterator 
+            site_events_iterator_;
+        std::vector<site_event_type> site_events_;
+        std::priority_queue< circle_event_type,
+                             std::vector<circle_event_type>,
+                             std::greater<circle_event_type> > circle_events_;
+        kEventType last_event_type_;
+
+        //Disallow copy constructor and operator=
+        event_queue(const event_queue&);
+        void operator=(const event_queue&);
+    };
+
+} // sweepline
+} // boost
+
+#endif
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/event_types.hpp	2010-05-31 16:43:40 EDT (Mon, 31 May 2010)
@@ -0,0 +1,158 @@
+// Boost sweepline/event_types.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.
+
+#ifndef BOOST_SWEEPLINE_EVENT_TYPES
+#define BOOST_SWEEPLINE_EVENT_TYPES
+
+namespace boost {
+namespace sweepline {
+    
+    template <typename T>
+    class sweepline_event;
+
+    template <typename T>
+    class site_event;
+    
+    template <typename T>
+    class circle_event;
+
+    template <typename T>
+    class 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;
+
+        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());
+        }
+
+        bool operator<(const point_2d &point) const {
+            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);
+    }
+
+    template <typename T>
+    class sweepline_event : public point_2d<T> {
+    public:
+        enum kEventType {
+            SITE_EVENT = 0,
+            CIRCLE_EVENT = 1,
+            NONE = 2,
+        };
+
+        sweepline_event() : point_2d() {}
+
+        sweepline_event(T x, T y) : point_2d(x, y) {}
+
+        virtual kEventType get_event_type() const {
+            return NONE;
+        }
+    };
+
+    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) {}
+
+        virtual kEventType get_event_type() const {
+            return SITE_EVENT;
+        }
+    };
+
+    template <typename T>
+    site_event<T> make_site_event(T x, T y) {
+        return site_event<T>(x,y);
+    }
+
+    template <typename T>
+    class circle_event : public site_event<T> {
+    public:
+        circle_event() : site_event() { 
+            active_ = true;
+        }
+
+        circle_event(T x, T y) : site_event(x, y) {
+            active_ = true;
+        }
+
+        bool is_active() {
+            return active_;
+        }
+
+        virtual kEventType get_event_type() const {
+            return CIRCLE_EVENT;
+        }
+
+    private:
+        bool active_;
+    };
+
+    template <typename T>
+    circle_event<T> make_circle_event(T x, T y) {
+        return circle_event<T>(x,y);
+    }
+  
+} // sweepline
+} // boost
+
+#endif
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/boost/sweepline/voronoi_builder.hpp	2010-05-31 16:43:40 EDT (Mon, 31 May 2010)
@@ -0,0 +1,61 @@
+// Boost sweepline/voronoi_builder.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.
+
+#ifndef BOOST_SWEEPLINE_VORONOI_BUILDER
+#define BOOST_SWEEPLINE_VORONOI_BUILDER
+
+#include <vector>
+
+namespace boost {
+namespace sweepline {
+
+    template <typename Point2D, typename EventQueue, typename BeachLine>
+    class voronoi_builder {
+    public:
+        voronoi_builder() {}
+        
+        ~voronoi_builder() {
+            if (event_queue_) {
+                delete event_queue_;
+                event_queue_ = NULL;
+            }
+
+            if (beach_line_) {
+                delete beach_line_;
+                beach_line_ = NULL;
+            }
+        }
+
+        void init(const std::vector<Point2D> &sites) {
+            event_queue_->init(sites);
+        }
+
+        void reset() {
+            event_queue_->reset();
+            beach_line_->reset();
+        }
+
+        void build_voronoi_diagram() {
+            while (!event_queue_->empty())
+                make_one_iteration();
+        }
+
+    private:
+        void make_one_iteration() {
+            //Not implemented yet
+        }
+
+        EventQueue* event_queue_;
+        BeachLine* beach_line_;
+    };
+
+} // sweepline
+} // boost
+
+#endif
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/Jamfile.v2	2010-05-31 16:43:40 EDT (Mon, 31 May 2010)
@@ -0,0 +1,16 @@
+#          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)
+
+import testing ;
+
+project 
+    : requirements
+      <library>$(BOOST_ROOT)/libs/test/build//boost_unit_test_framework
+    ;
+
+test-suite "sweepline"
+    : 
+        [ run event_queue_test.cpp :  :  : <link>static ]
+    ;
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/beach_line_test.cpp	2010-05-31 16:43:40 EDT (Mon, 31 May 2010)
@@ -0,0 +1,8 @@
+// Boost sweepline library beach_line_test.cpp 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.
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/event_queue_test.cpp	2010-05-31 16:43:40 EDT (Mon, 31 May 2010)
@@ -0,0 +1,69 @@
+// Boost sweepline library event_queue_test.cpp 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.
+
+#include "test_type_list.hpp"
+#include <boost/sweepline/event_queue.hpp>
+#include <boost/sweepline/event_types.hpp>
+using namespace boost::sweepline;
+
+#define BOOST_TEST_MODULE event_queue_test
+#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_AUTO_TEST_CASE_TEMPLATE(event_queue_test1, T, test_types) {
+    typedef sweepline_event<T>::kEventType kEventType;
+
+    event_queue< point_2d<T> > event_q;
+    BOOST_CHECK_EQUAL(event_q.empty(), true);
+    
+    event_q.reset();
+
+    std::vector< point_2d<T> > site_event_vec;
+    for (int i = 0; i <= 10; i++) {
+        T x = static_cast<T>(10-i);
+        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);
+
+    event_q.pop();
+    CHECK_TOP_ELEMENT_EQUALITY(event_q.top(), 1, 1);
+
+    for (int i = 5; 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-i);
+        T y = static_cast<T>(10-i-1);
+        event_q.push(make_circle_event(x, y));
+    }
+    
+    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.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.pop();
+    }
+    
+    BOOST_CHECK_EQUAL(event_q.empty(), true);
+}
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/test_type_list.hpp	2010-05-31 16:43:40 EDT (Mon, 31 May 2010)
@@ -0,0 +1,21 @@
+// Boost sweepline library test_type_list.hpp 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.
+
+#ifndef BOOST_SWEEPLINE_TEST_TYPE_LIST
+#define BOOST_SWEEPLINE_TEST_TYPE_LIST
+
+#include <boost/mpl/list.hpp>
+
+typedef boost::mpl::list<int,
+                         long long,
+                         float,
+                         double,
+                         long double> test_types;
+
+#endif
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/libs/sweepline/test/voronoi_builder_test.cpp	2010-05-31 16:43:40 EDT (Mon, 31 May 2010)
@@ -0,0 +1,8 @@
+// Boost sweepline library voronoi_builder_test.cpp 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.
\ No newline at end of file

Added: sandbox/SOC/2010/sweepline/project-root.jam
==============================================================================
--- (empty file)
+++ sandbox/SOC/2010/sweepline/project-root.jam	2010-05-31 16:43:40 EDT (Mon, 31 May 2010)
@@ -0,0 +1,9 @@
+#          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)
+
+
+import os ;
+
+path-constant BOOST_ROOT : [ os.environ BOOST_ROOT ] ;