Re: length-specified-strings -- JudySLn()

[john s. <sk...@us...>]

On 03/03/2009, at 5:39 PM, Doug Baskins wrote:

>
> SO, MY QUESTION TO YOU IS:
>
> Is that the correct way to implement JudySLn()?

There is only one "correct" lexicographic ordering:
A string P which is a strict prefix of a string S is lower than it.

Thus XYZ is lower than XYZ\0 which is lower than XYZ\0\0.

The NULL byte \0 is perfectly ordinary and must be treated as such
whether it is embedded or trailing does not matter.

Instead imagine all string are infinite in length, by extending them
after the specified length by an infinite stream of -1s.

It is easy to store a set of such strings .. but you're right
it seems quite hard to order them (uniqueness is trivial,
just pre-pend the length count).

Of course there IS a way: encode the strings, for example
UTF-8 encoding sorts correctly and leaves FF free as a terminator
(for example). The only problem with this is that the length can only
be found by scanning the whole string (same as for NULL terminated!).
But this means it requires two searches to decode it.

--
john skaller
sk...@us...