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
From: Erik Naggum
Subject: Re: looking up entries in a table of ranges
Date:
Message-ID: <3158948495513418@naggum.no>
* Jason Kantz
| 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.
looks like a sorted association list to me.
(assoc 50.0 '((10.0 . "this stuff")
(40.0 . "this other stuff")
(100.0 . "yet some other stuff"))
:test #'<=)
=> (100.0 . "yet some other stuff")
FIND would allow you to use a sequence of more complex objects and use
:KEY to extract the slot you want to look at.
in any case, I would expect such a function to be called FIND-foo, foo
being the object you're looking for. whether you implement it as a
general function traversing a list or a function with a fast TYPECASE
dispatch on ranges is largely immaterial, though.
#:Erik
······@je1.jsc.nasa.gov 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.
>
> Is there a common name for this?
> Is this something that should just be thrown into a list?
The name is an "Interval Tree" data structure. Check out Cormen,
Leiserson and Rivest's "Intro to Algorithms". I know of no
implementation in CL, although the Red/Black tree implementation that
you can find in the AI.Repository may be a good place to start (note:
this is a shameless plug :) ).
Cheers
--
Marco Antoniotti ===========================================
PARADES, Via San Pantaleo 66, I-00186 Rome, ITALY
tel. +39 - 06 68 10 03 17, fax. +39 - 06 68 80 79 26
http://www.parades.rm.cnr.it/~marcoxa