Opened 12 years ago

Closed 11 years ago

#635 closed discussion (fixed)

class for a Segment

Reported by: Peter Owned by: Peter
Priority: major Milestone: yat 0.7
Component: utility Version: trunk
Keywords: Cc:

Description (last modified by 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)

Change History (9)

comment:1 Changed 12 years ago by Peter

Summary: Intervalclass for a Segment

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.

comment:2 Changed 12 years ago by Peter

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

comment:3 Changed 12 years ago by Peter

Milestone: yat 0.x+yat 0.7
Owner: changed from Jari Häkkinen to Peter
Status: newassigned

comment:4 Changed 12 years ago by Peter

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

comment:5 Changed 12 years ago by Peter

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

comment:6 Changed 12 years ago by Peter

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

comment:7 Changed 12 years ago by Peter

Description: modified (diff)
Milestone: yat 0.7yat 0.x+
Status: assignednew

Split this ticket into #640 and #641

comment:8 Changed 12 years ago by Peter

Milestone: yat 0.x+yat 0.8
Status: newassigned

comment:9 Changed 11 years ago by Peter

Milestone: yat 0.8yat 0.7
Resolution: fixed
Status: assignedclosed

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

Note: See TracTickets for help on using tickets.