find closest item in keyed collection

[Steve Richter]

Does the .NET framework provide a class which will find the item in
the collection with a key which is closest ( greater than or equal,
less than or equal ) to the keys of the collection?

ex: collection keys are 20, 30, 40, 50, 60, 70, 80

find key which is >= 35.

would return the 30 key.

thanks,

[Marc Gravell]

Oops; "Single" should have been "First"...

Marc

[christery]

Still dont understand why >=35 isnt 40... some new math I did miss?

//CY

[Marc Gravell]

If the poster is looking for the nearest property to a particular

address,
then his numbers may indeed be keys.

Yes; I was thrown by the OP *only* mentioning a single series of
numeric data, rather than two.
I followed up with a post acknowledging this. Although lets be fair -
a lot of things could have been a little clearer in the original
question.

Marc

[=?Utf-8?B?RmFtaWx5IFRyZWUgTWlrZQ==?=]

"Marc Gravell" wrote:

If the poster is looking for the nearest property to a particular
address,
then his numbers may indeed be keys.

Yes; I was thrown by the OP *only* mentioning a single series of
numeric data, rather than two.
I followed up with a post acknowledging this. Although lets be fair -
a lot of things could have been a little clearer in the original
question.

Marc

You are right on both counts. Sorry, I responded before seeing the other
posts. You gave a slick solution.

>

[Ben Voigt [C++ MVP]]

"Steve Richter" <St************ @gmail.comwrote in message
news:3a******** *************** ***********@q3g 2000hsg.googleg roups.com...

Does the .NET framework provide a class which will find the item in
the collection with a key which is closest ( greater than or equal,
less than or equal ) to the keys of the collection?

ex: collection keys are 20, 30, 40, 50, 60, 70, 80

find key which is >= 35.

would return the 30 key.

Maintain a SortedList containing these keys, SortedList can find the closest
(or following, or preceding) entry in O(log N) time.

>
thanks,

[Liz]

"Ben Voigt [C++ MVP]" <rb*@nospam.nos pamwrote in message
news:%2******** ********@TK2MSF TNGP06.phx.gbl. ..

>
"Steve Richter" <St************ @gmail.comwrote in message
news:3a******** *************** ***********@q3g 2000hsg.googleg roups.com...

>Does the .NET framework provide a class which will find the item in
the collection with a key which is closest ( greater than or equal,
less than or equal ) to the keys of the collection?

ex: collection keys are 20, 30, 40, 50, 60, 70, 80

find key which is >= 35.

would return the 30 key.

Maintain a SortedList containing these keys, SortedList can find the
closest (or following, or preceding) entry in O(log N) time.

with what method? do you mean by iterating the list ?

I think the OP was looking for a function of the sort you used to see in
xBASE dialects ... think it was called SOFTSEEK(), which would return either
the key sought or the next highest-valued key, if any ... I'm not aware of
such a function in the Framework

[Steve Richter]

On Dec 17, 5:46 pm, "Liz" <l...@tiredofsp am.comwrote:

"Ben Voigt [C++ MVP]" <[e-mail] spamwrote in messagenews:%2* *************** @TK2MSFTNGP06.p hx.gbl...

"Steve Richter" <StephenRich... @gmail.comwrote in message
news:3a******** *************** ***********@q3g 2000hsg.googleg roups.com...

Does the .NET framework provide a class which will find the item in
the collection with a key which is closest ( greater than or equal,
less than or equal ) to the keys of the collection?

ex: collection keys are 20, 30, 40, 50, 60, 70, 80

find key which is >= 35.

would return the 30 key.

Maintain a SortedList containing these keys, SortedList can find the
closest (or following, or preceding) entry in O(log N) time.

with what method? do you mean by iterating the list ?

I think the OP was looking for a function of the sort you used to see in
xBASE dialects ... think it was called SOFTSEEK(), which would return either
the key sought or the next highest-valued key, if any ... I'm not aware of
such a function in the Framework

thanks for the responses ( and sorry for the confusion on what I
intended as <= 35 ).

what I have is a text file concatenated as a single string. As I scan
and parse the string I want to be able to determine the line number
and position in the line of any offset in the string. As I concat the
text lines, the line number and start/end offset in the string of the
line would be stored in a collection. When I find something at offset
2022 in the string, I want to find in the collection of "line numbers/
start offset in the string" the offset which is <= 2022. That would
tell me the text file line number.

-Steve

[Marc Gravell]

One-way searches are fortunately easier than 2-way proximity... you
get to stop sooner ;-p
If this is volume usage, then the LINQ approach I posted earlier would
be a poor choice (it would sort each time); Ben mentioned a SortedList
which may be helpful... I can't only see equality methods myself, but
you could perhaps simply walk the list until you find one that is >
2022 and return the previous (if you see what I mean...).

Of course, if you are adding to the list in sequence, you could just
use a regular list, and do the same walk.
If you are adding to the list while iterating, it is probably just the
last element.

Just for completeness (to contrast to my prior post); in LINQ terms
this is:

IDictionary<int , stringdata = new SortedList<int,
string{
{20, "a"}, {30, "b"}, {40, "c"}, {50, "d"},
{60, "e"}, {70, "f"}, {80, "g"}
};
KeyValuePair<in t, stringresult =
data.TakeWhile( x =x.Key <= 35).Last();

(I'm using TakeWhile here since we know the data is sorted; hence it
will stop reading when it finds something that doesn't meet the <= 35
condition).

Of course, if you are generally accessing recent data you may be
better keeping the list inverted (perhaps even just a List<Tand
Insert at 0; or use a custom comparer to automatically invert the list
in-place [very easy]) and check for the first match:

KeyValuePair<in t, stringresult =
data.SkipWhile( x =x.Key 35).First();

Marc

[Ben Voigt [C++ MVP]]

"Marc Gravell" <ma**********@g mail.comwrote in message
news:%2******** ********@TK2MSF TNGP03.phx.gbl. ..

One-way searches are fortunately easier than 2-way proximity... you get to
stop sooner ;-p
If this is volume usage, then the LINQ approach I posted earlier would be
a poor choice (it would sort each time); Ben mentioned a SortedList which
may be helpful... I can't only see equality methods myself, but you could
perhaps simply walk the list until you find one that is 2022 and return
the previous (if you see what I mean...).

Ack! SortedList.Inde xOfKey doesn't return the index for not found items,
while List.BinarySear ch does. But you can't run BinarySearch on a sorted
list! An extension method would be good...

So either reimplement BinarySearch to work on a SortedList or use List and
List.BinarySear ch and keep the list sorted yourself.

>
Of course, if you are adding to the list in sequence, you could just use a
regular list, and do the same walk.
If you are adding to the list while iterating, it is probably just the
last element.

Just for completeness (to contrast to my prior post); in LINQ terms this
is:

IDictionary<int , stringdata = new SortedList<int, string{
{20, "a"}, {30, "b"}, {40, "c"}, {50, "d"},
{60, "e"}, {70, "f"}, {80, "g"}
};
KeyValuePair<in t, stringresult =
data.TakeWhile( x =x.Key <= 35).Last();

(I'm using TakeWhile here since we know the data is sorted; hence it will
stop reading when it finds something that doesn't meet the <= 35
condition).

Of course, if you are generally accessing recent data you may be better
keeping the list inverted (perhaps even just a List<Tand Insert at 0; or
use a custom comparer to automatically invert the list in-place [very
easy]) and check for the first match:

KeyValuePair<in t, stringresult =
data.SkipWhile( x =x.Key 35).First();

Marc