Opened 13 years ago
Closed 12 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 )
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 13 years ago by
Summary: | Interval → class for a Segment |
---|
comment:3 Changed 13 years ago by
Milestone: | yat 0.x+ → yat 0.7 |
---|---|
Owner: | changed from Jari Häkkinen to Peter |
Status: | new → assigned |
comment:4 Changed 13 years ago by
comment:5 Changed 13 years ago by
comment:6 Changed 13 years ago by
(In [2296]) class SegmentSet?: added function clear and fixed bug in insert. Divided test into subtests. refs #635
comment:7 Changed 13 years ago by
Description: | modified (diff) |
---|---|
Milestone: | yat 0.7 → yat 0.x+ |
Status: | assigned → new |
comment:8 Changed 13 years ago by
Milestone: | yat 0.x+ → yat 0.8 |
---|---|
Status: | new → assigned |
comment:9 Changed 12 years ago by
Milestone: | yat 0.8 → yat 0.7 |
---|---|
Resolution: | → fixed |
Status: | assigned → closed |
Ticket #640 was implemented in milestone:"yat 0.7", and #641 was markes as wontfix so I place this in milestone:"yat 0.7".
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.