I need to make a table that returns an entry for a value in a given
range. And I'm wondering if a more experienced programmer can comment
on whether this is a common data structure with a common name.
For example say you have weight x = 50.0
and your *table* looks something like this ...
0.0 <= x <= 10.0 this stuff
10.0 < x <= 40.0 this other stuff
40.0 < x <= 100.0 yet some other stuff
... and so on
and you would call (get-val 50.0 *table*) to get the data for that
range.
Is there a common name for this?
Is this something that should just be thrown into a list?
--Jason Kantz
--
Jason Kantz
http://kantz.com/jason
Jason Kantz <·····@kantz.com> writes:
> I need to make a table that returns an entry for a value in a given
> range. And I'm wondering if a more experienced programmer can comment
> on whether this is a common data structure with a common name.
>
> For example say you have weight x = 50.0
>
> and your *table* looks something like this ...
>
> 0.0 <= x <= 10.0 this stuff
> 10.0 < x <= 40.0 this other stuff
> 40.0 < x <= 100.0 yet some other stuff
> ... and so on
>
> and you would call (get-val 50.0 *table*) to get the data for that
> range.
In the simplest situation you can just make a tree where the fringe is
ordered (it usually is for most implementations) and search for your
element. In the case where the element is not found just return the
value to the left and you are set as this will mark the lower bound of
one of your intervals. There may be better approaches than that but
that is a reasonable first guess.
The interesting situation is where you have arbitrary intervals which
can overlap. In that case you need to use an interval tree, you can
find an exact specification in _Introduction to Algorithms_ by Cormen,
Leiserson and Rivest. In their implementation a red black tree is
used and will do O(log n) insertions, deletions, and searches. These
things are useful for scheduling and like tasks.
The final decision depends on when you know your intervals, are there
gaps, and how many of them are there. If you only have a few values
your best choice may be just making an ordered alist and searching it.
Hope that helps,
-Eric
In article <·················@kantz.com>, ·····@kantz.com wrote:
> I need to make a table that returns an entry for a value in a given
> range. And I'm wondering if a more experienced programmer can comment
> on whether this is a common data structure with a common name.
"Rtree" for example.
Rainer Joswig, ISION Internet AG, Harburger Schlossstrasse 1,
21079 Hamburg, Germany, Tel: +49 40 77175 226
Email: ·············@ision.de , WWW: http://www.ision.de/