class for a Segment

[Peter]

Mother of tickets #640 and #641

I need a class that can compare intervals. I'm thinking a template<T> that is defined as

template<T>
struct {
T first
T last
}

which should be interpreted as [first,last). I wanna be able to compare two Intervals, e.g. create the intersection of them or just tell whether the overlapping of which one is entirely less than the other one.

Unique Associate Container The simple case for a interval container is when two intervals never overlap. Then one can implement it as a wrapper of std::set/std::map or simply provide functions that work on a std::set<Interval<T>>. One function, e.g., would be to find the interval that overlap with an element T; The first interval entirely less than element T (or greater); etc. Adding an interval could mean different things: 1) Add interval only if it does not overlap with any interval in container and inserted intervals are kept intact. 2) Add interval and merge it with overlapping intervals, which means in principle that inserted [b,c) into container with [a,b) and [c,d) would create one interval [a,d). And similar with similar cases. (#640)

Associate MultiContainer When intervals may overlap the container is a bit more tricky. A tree structure seems the best approach also here but a slightly different tree than the red/black tree. Here are some references ​http://www.dgp.toronto.edu/people/JamesStewart/378notes/22intervals/ and ​http://en.wikipedia.org/wiki/Interval_tree This is a much bigger task than the ones above. (#641)

[Peter]

There is a class in boost for intervals ​http://www.boost.org/doc/libs/1_43_0/libs/numeric/interval/doc/interval.htm but it is aimed at numerical types (with arithmetic). The class proposed here is more generic and is supposed to work on any type as long as they are less than comparable. I change to class name Segment to avoid confusion.

[Peter]

(In [2291]) refs #635. New classes Segment and SegmentSet?.

[Peter]

(In [2293]) adding a function that takes intersection of two Sections. refs #635

[Peter]

(In [2294]) refs #635. fix return type (int) in compare_3way and add some more test for Segment.

[Peter]

(In [2296]) class SegmentSet?: added function clear and fixed bug in insert. Divided test into subtests. refs #635

[Peter]

Split this ticket into #640 and #641

[Peter]

Ticket #640 was implemented in milestone:"yat 0.7", and #641 was markes as wontfix so I place this in milestone:"yat 0.7".