/** @file
 * @brief Class for implementing sweepline algorithms
 *//*
  * Authors:
  *   Krzysztof Kosiński <tweenk.pl@gmail.com>
  *
  * Copyright 2015 Authors
  *
  * This library is free software; you can redistribute it and/or
  * modify it either under the terms of the GNU Lesser General Public
  * License version 2.1 as published by the Free Software Foundation
  * (the "LGPL") or, at your option, under the terms of the Mozilla
  * Public License Version 1.1 (the "MPL"). If you do not alter this
  * notice, a recipient may use your version of this file under either
  * the MPL or the LGPL.
  *
  * You should have received a copy of the LGPL along with this library
  * in the file COPYING-LGPL-2.1; if not, write to the Free Software
  * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
  * You should have received a copy of the MPL along with this library
  * in the file COPYING-MPL-1.1
  *
  * The contents of this file are subject to the Mozilla Public License
  * Version 1.1 (the "License"); you may not use this file except in
  * compliance with the License. You may obtain a copy of the License at
  * http://www.mozilla.org/MPL/
  *
  * This software is distributed on an "AS IS" basis, WITHOUT WARRANTY
  * OF ANY KIND, either express or implied. See the LGPL or the MPL for
  * the specific language governing rights and limitations.
  */

#ifndef LIB2GEOM_SEEN_SWEEPER_H
#define LIB2GEOM_SEEN_SWEEPER_H

#include <2geom/coord.h>
#include <algorithm>
#include <vector>
#include <boost/intrusive/list.hpp>
#include <boost/range/algorithm/heap_algorithm.hpp>

namespace Geom {

// exposition only
template <typename Item>
class SweepVector {
public:
    typedef typename std::vector<Item>::const_iterator ItemIterator;

    SweepVector(std::vector<Item> const &v)
        : _items(v)
    {}

    std::vector<Item> const &items() { return _items; }
    Interval itemBounds(ItemIterator /*ii*/) { return Interval(); }

    void addActiveItem(ItemIterator /*ii*/) {}
    void removeActiveItem(ItemIterator /*ii*/) {}

private:
    std::vector<Item> const &_items;
};

/** @brief Generic sweepline algorithm.
 *
 * This class encapsulates an algorithm that sorts the objects according
 * to their bounds, then moves an imaginary line (sweepline) over those
 * bounds from left to right. Objects are added to the active list when
 * the line starts intersecting their bounds, and removed when it completely
 * passes over them.
 *
 * To use this, create a class that exposes the following methods:
 * - Range items() - returns a forward iterable range of items that will be swept.
 * - Interval itemBounds(iterator i) - given an iterator from the above range,
 *   compute the bounding interval of the referenced item in the direction of sweep.
 * - void addActiveItem(iterator i) - add an item to the active list.
 * - void removeActiveItem(iterator i) - remove an item from the active list.
 *
 * Create the object, then instantiate this template with the above class
 * as the template parameter, pass it the constructed object of the class,
 * and call the process() method.
 *
 * A good choice for the active list is a Boost intrusive list, which allows
 * you to get an iterator from a value in constant time.
 *
 * Look in path.cpp for example usage.
 *
 * @tparam Item The type of items to sweep
 * @tparam SweepTraits Traits class that defines the items' bounds,
 *   how to interpret them and how to sort the events
 * @ingroup Utilities
 */
template <typename SweepSet>
class Sweeper {
public:
    typedef typename SweepSet::ItemIterator Iter;

    explicit Sweeper(SweepSet &set)
        : _set(set)
    {
        std::size_t sz = std::distance(set.items().begin(), set.items().end());
        _entry_events.reserve(sz);
        _exit_events.reserve(sz);
    }

    /** @brief Process entry and exit events.
     * This will iterate over all inserted items, calling the methods
     * addActiveItem and removeActiveItem on the SweepSet passed at construction
     * according to the order of the boundaries of each item. */
    void process() {
        if (_set.items().empty()) return;

        Iter last = _set.items().end();
        for (Iter i = _set.items().begin(); i != last; ++i) {
            Interval b = _set.itemBounds(i);
            // guard against NANs
            assert(b.min() == b.min() && b.max() == b.max());
            _entry_events.push_back(Event(b.max(), i));
            _exit_events.push_back(Event(b.min(), i));
        }

        boost::make_heap(_entry_events);
        boost::make_heap(_exit_events);

        Event next_entry = _get_next(_entry_events);
        Event next_exit = _get_next(_exit_events);

        while (next_entry || next_exit) {
            assert(next_exit);

            if (!next_entry || next_exit > next_entry) {
                // exit event - remove record from active list
                _set.removeActiveItem(next_exit.item);
                next_exit = _get_next(_exit_events);
            } else {
                // entry event - add record to active list
                _set.addActiveItem(next_entry.item);
                next_entry = _get_next(_entry_events);
            }
        }
    }

private:
    struct Event
        : boost::totally_ordered<Event>
    {
        Coord coord;
        Iter item;

        Event(Coord c, Iter const &i)
            : coord(c), item(i)
        {}
        Event()
            : coord(nan("")), item()
        {}
        bool operator<(Event const &other) const { return coord < other.coord; }
        bool operator==(Event const &other) const { return coord == other.coord; }
        operator bool() const { return !std::isnan(coord); }
    };

    static Event _get_next(std::vector<Event> &heap) {
        if (heap.empty()) {
            Event e;
            return e;
        }
        boost::pop_heap(heap);
        Event ret = heap.back();
        heap.pop_back();
        return ret;
    }

    SweepSet &_set;
    std::vector<Event> _entry_events;
    std::vector<Event> _exit_events;
};

} // namespace Geom

#endif // !LIB2GEOM_SEEN_SWEEPER_H

/*
  Local Variables:
  mode:c++
  c-file-style:"stroustrup"
  c-file-offsets:((innamespace . 0)(inline-open . 0)(case-label . +))
  indent-tabs-mode:nil
  fill-column:99
  End:
*/
// vim: filetype=cpp:expandtab:shiftwidth=4:tabstop=8:softtabstop=4:fileencoding=utf-8:textwidth=99 :