FM / detail

/usr/include/boost/geometry/algorithms/detail/

/usr/include/boost/geometry/algorithms/detail

Name	Size	Mode	Actions
buffer/	-	0755	rm
centroid/	-	0755	rm
closest_feature/	-	0755	rm
comparable_distance/	-	0755	rm
covered_by/	-	0755	rm
disjoint/	-	0755	rm
distance/	-	0755	rm
envelope/	-	0755	rm
equals/	-	0755	rm
expand/	-	0755	rm
intersection/	-	0755	rm
intersects/	-	0755	rm
is_simple/	-	0755	rm
is_valid/	-	0755	rm
make/	-	0755	rm
overlaps/	-	0755	rm
overlay/	-	0755	rm
relate/	-	0755	rm
relation/	-	0755	rm
sections/	-	0755	rm
touches/	-	0755	rm
turns/	-	0755	rm
within/	-	0755	rm
assign_box_corners.hpp	3338	0644	edit dl rm
assign_indexed_point.hpp	2656	0644	edit dl rm
assign_values.hpp	8957	0644	edit dl rm
as_range.hpp	2688	0644	edit dl rm
azimuth.hpp	4802	0644	edit dl rm
calculate_null.hpp	1144	0644	edit dl rm
calculate_point_order.hpp	11145	0644	edit dl rm
calculate_sum.hpp	2047	0644	edit dl rm
check_iterator_range.hpp	2012	0644	edit dl rm
convert_indexed_to_indexed.hpp	2296	0644	edit dl rm
convert_point_to_point.hpp	2259	0644	edit dl rm
counting.hpp	2746	0644	edit dl rm
course.hpp	1180	0644	edit dl rm
direction_code.hpp	9205	0644	edit dl rm
expand_by_epsilon.hpp	3880	0644	edit dl rm
extreme_points.hpp	19767	0644	edit dl rm
for_each_range.hpp	4962	0644	edit dl rm
get_max_size.hpp	2054	0644	edit dl rm
has_self_intersections.hpp	5389	0644	edit dl rm
interior_iterator.hpp	1768	0644	edit dl rm
max_interval_gap.hpp	8430	0644	edit dl rm
multi_modify.hpp	1883	0644	edit dl rm
multi_modify_with_predicate.hpp	1442	0644	edit dl rm
multi_sum.hpp	1490	0644	edit dl rm
normalize.hpp	1296	0644	edit dl rm
not.hpp	2032	0644	edit dl rm
num_distinct_consecutive_points.hpp	2449	0644	edit dl rm
partition.hpp	29824	0644	edit dl rm
point_is_spike_or_equal.hpp	5455	0644	edit dl rm
point_on_border.hpp	5254	0644	edit dl rm
recalculate.hpp	6905	0644	edit dl rm
ring_identifier.hpp	2285	0644	edit dl rm
signed_size_type.hpp	770	0644	edit dl rm
single_geometry.hpp	2840	0644	edit dl rm
sub_range.hpp	4097	0644	edit dl rm
sweep.hpp	2086	0644	edit dl rm
throw_on_empty_input.hpp	2073	0644	edit dl rm
tupled_output.hpp	19235	0644	edit dl rm

Edit: /usr/include/boost/geometry/algorithms/detail/max_interval_gap.hpp (8430B)

// Boost.Geometry (aka GGL, Generic Geometry Library)

// Contributed and/or modified by Menelaos Karavelas, on behalf of Oracle

// Licensed under the Boost Software License version 1.0.
// http://www.boost.org/users/license.html

#ifndef BOOST_GEOMETRY_ALGORITHMS_DETAIL_MAX_INTERVAL_GAP_HPP
#define BOOST_GEOMETRY_ALGORITHMS_DETAIL_MAX_INTERVAL_GAP_HPP

#include <cstddef>
#include <queue>
#include <utility>
#include <vector>

#include <boost/core/ref.hpp>
#include <boost/range.hpp>
#include <boost/type_traits/remove_const.hpp>
#include <boost/type_traits/remove_reference.hpp>

#include <boost/geometry/core/assert.hpp>
#include <boost/geometry/util/math.hpp>
#include <boost/geometry/algorithms/detail/sweep.hpp>

namespace boost { namespace geometry
{

#ifndef DOXYGEN_NO_DETAIL
namespace detail { namespace max_interval_gap
{

// the class Interval must provide the following:
// * must define the type value_type
// * must define the type difference_type
// * must have the methods:
//   value_type get<Index>() const
//   difference_type length() const
// where an Index value of 0 (resp., 1) refers to the left (resp.,
// right) endpoint of the interval

template <typename Interval>
class sweep_event
{
public:
    typedef Interval interval_type;
    typedef typename Interval::value_type time_type;

sweep_event(Interval const& interval, bool start_event = true)
        : m_interval(boost::cref(interval))
        , m_start_event(start_event)
    {}

inline bool is_start_event() const
    {
        return m_start_event;
    }

inline interval_type const& interval() const
    {
        return m_interval;
    }

inline time_type time() const
    {
        return (m_start_event)
            ? interval().template get<0>()
            : interval().template get<1>();
    }

inline bool operator<(sweep_event const& other) const
    {
        if (! math::equals(time(), other.time()))
        {
            return time() < other.time();
        }
        // a start-event is before an end-event with the same event time
        return is_start_event() && ! other.is_start_event();
    }

private:
    boost::reference_wrapper<Interval const> m_interval;
    bool m_start_event;
};

template <typename Event>
struct event_greater
{
    inline bool operator()(Event const& event1, Event const& event2) const
    {
        return event2 < event1;
    }
};

struct initialization_visitor
{
    template <typename Range, typename PriorityQueue, typename EventVisitor>
    static inline void apply(Range const& range,
                             PriorityQueue& queue,
                             EventVisitor&)
    {
        BOOST_GEOMETRY_ASSERT(queue.empty());

// it is faster to build the queue directly from the entire
        // range, rather than insert elements one after the other
        PriorityQueue pq(boost::begin(range), boost::end(range));
        std::swap(pq, queue);
    }
};

template <typename Event>
class event_visitor
{
    typedef typename Event::time_type event_time_type;
    typedef typename Event::interval_type::difference_type difference_type;

typedef typename boost::remove_const
        <
            typename boost::remove_reference
                <
                    event_time_type
                >::type
        >::type bare_time_type;

public:
    event_visitor()
        : m_overlap_count(0)
        , m_max_gap_left(0)
        , m_max_gap_right(0)
    {}

template <typename PriorityQueue>
    inline void apply(Event const& event, PriorityQueue& queue)
    {
        if (event.is_start_event())
        {
            ++m_overlap_count;
            queue.push(Event(event.interval(), false));
        }
        else
        {
            --m_overlap_count;
            if (m_overlap_count == 0 && ! queue.empty())
            {
                // we may have a gap
                BOOST_GEOMETRY_ASSERT(queue.top().is_start_event());

event_time_type next_event_time
                    = queue.top().interval().template get<0>();
                difference_type gap = next_event_time - event.time();
                if (gap > max_gap())
                {
                    m_max_gap_left = event.time();
                    m_max_gap_right = next_event_time;
                }
            }
        }
    }

bare_time_type const& max_gap_left() const
    {
        return m_max_gap_left;
    }

bare_time_type const& max_gap_right() const
    {
        return m_max_gap_right;
    }

difference_type max_gap() const
    {
        return m_max_gap_right - m_max_gap_left;
    }

private:
    std::size_t m_overlap_count;
    bare_time_type m_max_gap_left, m_max_gap_right;
};

}} // namespace detail::max_interval_gap
#endif // DOXYGEN_NO_DETAIL

// Given a range of intervals I1, I2, ..., In, maximum_gap() returns
// the maximum length of an interval M that satisfies the following
// properties:
//
// 1. M.left >= min(I1, I2, ..., In)
// 2. M.right <= max(I1, I2, ..., In)
// 3. intersection(interior(M), Ik) is the empty set for all k=1, ..., n
// 4. length(M) is maximal
//
// where M.left and M.right denote the left and right extreme values
// for the interval M, and length(M) is equal to M.right - M.left.
//
// If M does not exist (or, alternatively, M is identified as the
// empty set), 0 is returned.
//
// The algorithm proceeds for performing a sweep: the left endpoints
// are inserted into a min-priority queue with the priority being the
// value of the endpoint. The sweep algorithm maintains an "overlap
// counter" that counts the number of overlaping intervals at any
// specific sweep-time value.
// There are two types of events encountered during the sweep:
// (a) a start event: the left endpoint of an interval is found.
//     In this case the overlap count is increased by one and the
//     right endpoint of the interval in inserted into the event queue
// (b) an end event: the right endpoint of an interval is found.
//     In this case the overlap count is decreased by one. If the
//     updated overlap count is 0, then we could expect to have a gap
//     in-between intervals. This gap is measured as the (absolute)
//     distance of the current interval right endpoint (being
//     processed) to the upcoming left endpoint of the next interval
//     to be processed (if such an interval exists). If the measured
//     gap is greater than the current maximum gap, it is recorded.
// The initial maximum gap is initialized to 0. This value is returned
// if no gap is found during the sweeping procedure.

template <typename RangeOfIntervals, typename T>
inline typename boost::range_value<RangeOfIntervals>::type::difference_type
maximum_gap(RangeOfIntervals const& range_of_intervals,
            T& max_gap_left, T& max_gap_right)
{
    typedef typename boost::range_value<RangeOfIntervals>::type interval_type;
    typedef detail::max_interval_gap::sweep_event<interval_type> event_type;

// create a min-priority queue for the events
    std::priority_queue
        <
            event_type,
            std::vector<event_type>, 
            detail::max_interval_gap::event_greater<event_type>
        > queue;

// define initialization and event-process visitors
    detail::max_interval_gap::initialization_visitor init_visitor;
    detail::max_interval_gap::event_visitor<event_type> sweep_visitor;

// perform the sweep
    geometry::sweep(range_of_intervals,
                    queue,
                    init_visitor,
                    sweep_visitor);

max_gap_left = sweep_visitor.max_gap_left();
    max_gap_right = sweep_visitor.max_gap_right();
    return sweep_visitor.max_gap();
}

template <typename RangeOfIntervals>
inline typename boost::range_value<RangeOfIntervals>::type::difference_type
maximum_gap(RangeOfIntervals const& range_of_intervals)
{
    typedef typename boost::remove_const
        <
            typename boost::remove_reference
                <
                    typename boost::range_value
                        <
                            RangeOfIntervals
                        >::type::value_type
                >::type
        >::type value_type;

value_type left, right;

return maximum_gap(range_of_intervals, left, right);
}

}} // namespace boost::geometry

#endif // BOOST_GEOMETRY_ALGORITHMS_DETAIL_MAX_INTERVAL_GAP_HPP

cmd: