«

Hi,

I was wondering if someone of you could help me out with an
algorithmic problem I have. This is not a homework exercise but
something I need for a UI framework that I have developed
(www.dlsc.com).

I have a list of time intervals ([long,long]). The list is sorted
based on the start times of the intervals. I now need a fast
algorithm, which takes a time span TS as input and returns the index
of the first time interval A in the list that is contained in the
given time span. The rendering engine of my UI framework will then
iterate over the list starting at the calculated index.

A time interval A is "contained" when A does not end before TS begins
and also does not start after TS ends (!(A.end < TS.start || A.start >
TS.end).

The algorithm gets constantly called as part of a paint() method so it
needs to be extremely fast (linear is not good enough, logarithmic
would be ideal).

To make things complicated. The intervals can overlap each other. An
interval A that starts earlier than B might very well end after B.
A.start < B.start && A.end > B.end.

Note: a standard binary search does not work because it might find a
time interval that ends before the input time span TS and then
interrupts its search even though another time interval is located
before it that ends after it.

Dirk

On Tue, 31 Jul 2007 11:18:55 -0000, lemmi <>
wrote, quoted or indirectly quoted someone who said :

>I have a list of time intervals ([long,long]). The list is sorted
>based on the start times of the intervals. I now need a fast
>algorithm, which takes a time span TS as input and returns the index
>of the first time interval A in the list that is contained in the
>given time span. The rendering engine of my UI framework will then
>iterate over the list starting at the calculated index.

That sounds like a job for a binary search.
See http://mindprod.com/jgloss/binarysearch.html

--
Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

On 31 Jul., 14:07, Roedy Green <see_webs...@mindprod.com.invalid>
wrote:
> On Tue, 31 Jul 2007 11:18:55 -0000, lemmi <dlemmerm...@gmail.com>
> wrote, quoted or indirectly quoted someone who said :
>
> >I have a list of time intervals ([long,long]). The list is sorted
> >based on the start times of the intervals. I now need a fast
> >algorithm, which takes a time span TS as input and returns the index
> >of the first time interval A in the list that is contained in the
> >given time span. The rendering engine of my UI framework will then
> >iterate over the list starting at the calculated index.
>
> That sounds like a job for a binary search.
> Seehttp://mindprod.com/jgloss/binarysearch.html

Binary search fails because of the fact that the time intervals can
overlap each other.

I have created an SSCCE for this problem:
------------------------------------------------------------------


import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/*
* A simple short self-contained compilable example (SSCCE), which
illustrates
* the time span search problem.
*
* @author Dirk Lemmermann
*/
public class TimeSpanProblem {
private List<TimeSpan> list = new ArrayList<TimeSpan>();

private TimeSpanProblem() {
// One huge time span that contains the other three spans.
list.add(new TimeSpan(0, 70));

// Three contained time spans.
list.add(new TimeSpan(10, 20));
list.add(new TimeSpan(30, 40));
list.add(new TimeSpan(50, 60));

// Sort all spans based on their start time.
//
// actually not needed because we added the time spans in their
// correct order.
Collections.sort(list);

/*
* find the first visible time span contained in interval 25, 80.
The
* first one should be the huge time span 0, 70 but the binary
search
* stops looking 'to the left' because interval 10, 20 is
*/
int first = getFirstContainedSpan(new TimeSpan(25, 80));
System.out.println("first contained time span = " + first);

if (first != 0) {
System.err.println("Time span problem not solved!");
System.err.println("The huge time span that overlaps the");
System.err.println("other three spans was not found.");
}
}

public int getFirstContainedSpan(TimeSpan span) {
/*
* These are the javadocs of the binarySearch() method:
*
* Returns: the index of the search key, if it is contained in the
list;
* otherwise, (-(insertion point) - 1). The insertion point is
defined
* as the point at which the key would be inserted into the list:
the
* index of the first element greater than the key, or list.size()
if
* all elements in the list are less than the specified key. Note
that
* this guarantees that the return value will be >= 0 if and only if
the
* key is found.
*/
int result = Collections.binarySearch(list, span);
return -(result + 1);
}

class TimeSpan implements Comparable<TimeSpan> {
long start;

long end;

public TimeSpan(long start, long end) {
this.start = start;
this.end = end;
}

public int compareTo(TimeSpan otherSpan) {
long delta = otherSpan.start - start;
if (delta > 0) {
return -1;
} else if (delta < 0) {
return +1;
}
return 0;
}
}

public static void main(String[] args) {
new TimeSpanProblem();
}
}


--Dirk

lemmi <> writes:

> I have a list of time intervals ([long,long]). The list is sorted
> based on the start times of the intervals. I now need a fast
> algorithm, which takes a time span TS as input and returns the index
> of the first time interval A in the list that is contained in the
> given time span. The rendering engine of my UI framework will then
> iterate over the list starting at the calculated index.

Why iterate? The next element can't be assumed to be hit by TS, so you
might have to iterate over a long list of irrelevant objects anyway.

> A time interval A is "contained" when A does not end before TS begins
> and also does not start after TS ends (!(A.end < TS.start || A.start >
> TS.end).

This is equivalent to (A.end >= TS.start && A.start <= TS.end).
I expect that A.start <= A.end (and likewise for TS) can be assumed.

That sounds like "overlaps", not "contained in". Example;
TS = [2,4]
A = [1,3]
satisfies the requirement.

> The algorithm gets constantly called as part of a paint() method so it
> needs to be extremely fast (linear is not good enough, logarithmic
> would be ideal).

Sounds unlikely, at least in the worst case, since the end-points are
completely unordered. Worst case, assume a (long) list with same start
time, and only one interval has a large enough end time to overlap the
TS.

You should consider whether there is a better data structure than a list
for your purpose, to account for both start and end time.
I can't think of a one, but why think when you can google (for "time interval
data structure"). It seems an Interval Tree is what you need:
<URL:http://en.wikipedia.org/wiki/Interval_tree>.
Found this too:
<URL:http://i11www.iti.uni-karlsruhe.de/~awolff/map-labeling/design/old/interfaces/gen_interval_tree.ps>

Good luck
/L
--
Lasse Reichstein Nielsen -
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

On 31 Jul., 14:31, Lasse Reichstein Nielsen <l...@hotpop.com> wrote:
> lemmi <dlemmerm...@gmail.com> writes:
> > I have a list of time intervals ([long,long]). The list is sorted
> > based on the start times of the intervals. I now need a fast
> > algorithm, which takes a time span TS as input and returns the index
> > of the first time interval A in the list that is contained in the
> > given time span. The rendering engine of my UI framework will then
> > iterate over the list starting at the calculated index.
>
> Why iterate? The next element can't be assumed to be hit by TS, so you
> might have to iterate over a long list of irrelevant objects anyway.

The iteration is smart enough to stop when it reaches a time span with
a start time larger than TS. So if a list contains 100 entries and the
index is (for example 33) then the paint method iterates over 33, 34,
35
and might stop at 36 if its start time is larger than TS.end.

On Tue, 31 Jul 2007 11:18:55 -0000, lemmi <>
wrote, quoted or indirectly quoted someone who said :

>Note: a standard binary search does not work because it might find a
>time interval that ends before the input time span TS and then
>interrupts its search even though another time interval is located
>before it that ends after it.

Predigest your list so that you decide which band number you want for
any point on the line. You can create dummy bands to handle areas not
covered. Then you need do your binary search only on the start points
of each band. You look for a band start point <= to the search point.
Have a look inside com.mindprod.jdisplay.PrettyCanvas. It does this.
http://mindprod.com/products.html#JDISPLAY
--
Roedy Green Canadian Mind Products
The Java Glossary
http://mindprod.com

> That sounds like "overlaps", not "contained in". Example;
> TS = [2,4]
> A = [1,3]
> satisfies the requirement.

Correct, I meant overlap.

Dirk

Lasse Reichstein Nielsen <> writes:

> It seems an Interval Tree is what you need:

Fair warning: Somebody aparently patented that idea.
/L
--
Lasse Reichstein Nielsen -
DHTML Death Colors: <URL:http://www.infimum.dk/HTML/rasterTriangleDOM.html>
'Faith without judgement merely degrades the spirit divine.'

On 31 Jul., 15:01, Lasse Reichstein Nielsen <l...@hotpop.com> wrote:
> Lasse Reichstein Nielsen <l...@hotpop.com> writes:
>
> > It seems an Interval Tree is what you need:
>
> Fair warning: Somebody aparently patented that idea.
> /L

I have found quite a few references to the interval binary
tree algorithm and it seems like a basic computer science
concept. How can this be patented? Can you point me to the
patent?

Dirk