>>>>> "B" == Bad <mr.bad at pigdog.org> writes:
B> OK, well, I think I might know why this would happen, maybe. If
B> you've got a search key located exactly equidistant between two
B> other keys, like this:
| | |
Key A Search Key Key B
B> Then it *might* go Key A, Key B, Key A, Key B, Key A, Key B,
B> etc. I'll change that and check it in -- should probably fix it
B> anyways, even if it's not your problem.
So, let me clarify again: the previous semantics of
StandardDataStore.findClosestKey(searchKey, maskKey) was to find the
closest key in the store to searchKey that was not closer to the
searchKey than maskKey. This allowed returning a key that was
equidistant from searchKey with maskKey.
The code that calls findClosestKey() is in a loop. It calls the
method, sees if there's a reference associated with the key returned,
and if not, it loops again, calling findClosestKey() with the previous
return value as a "mask." Usually this means that you do broader and
broader searches for keys "around" the search key. However, if there
are two equidistant keys, you go into a cycle.
Q: What's the key closest to searchKey?
A: Key B
Q: What's the key closest to searchKey that's not closer than Key B?
A: Key A
Q: What's the key closest to searchKey that's not closer than Key A?
A: Key B
Q: What's the key closest to searchKey that's not closer than Key B?
A: Key A
Q: What's the key closest to searchKey that's not closer than Key A?
A: Key B
etc.
The change I made last night means that findClosestKey(searchKey,
maskKey) will find the closest key to searchKey that is STRICTLY
FARTHER from searchKey than maskKey. That means that, in the situation
described above with two equidistant keys, you'll get this kind of
behavior:
Q: What's the key closest to searchKey?
A: Key B
Q: What's the key closest to searchKey that's farther than Key B?
A: Key C
Q: What's the key closest to searchKey that's farther than Key C?
A: Key D
Note that key A is _skipped_ (it is not farther than Key B). This kind
of sucks, since it's actually a better candidate than Key C in terms
of closeness. However, given only the context of a single mask key,
there's not much to do to avoid cycling.
I think I'm going to change the findClosestKey() method so that
instead of taking a single mask key, it takes a vector of previously
tried keys. So that the semantic changes to this:
Q: What's the key closest to searchKey?
A: Key B
Q: What's the key closest to searchKey that's not in this list: (Key B)?
A: Key A
