Massot:
Well you got me thinking about JudySLn() (current name). I looked into
modifying JudySL to be length-specified-strings instead of null
terminated strings. It turns out to be difficult algorithm.
A major problem seems to be a definition of "lexicographic" sorting. My
first thought made strings with different number of trailing zeros
('\0') stored in order of the least number of trailing zeros (otherwise
the same) being stored by just their length differences. I.E. a string
"abc\0\0" would be stored after "abc\0". However, when writing the code
an interesting problem shows up. In a tree hierarchy, they are synonyms
in the tree and require a separate structure to be stored. This
complicates and makes the code very "ugly" as well bloats the memory to
store the strings.
Then I decided to look up the definition of lexicographic sorting. My
interpretation of the definition is the above strings would be
considered the SAME. In "dictionary sorting", all words can be
considered the same length and padded with trailing "spaces" before
sorting. I also believe (but have not thought out carefully) that if
someone wanted to use JudySLn() to do number sorting (by doing byte
reversal of the string), then they would want "\0\0321" to be the same
as "\0321" and considered a synonym (the same number). And, lastly, the
code has a strong preference to work that that way. (I am not sure I
can figure out all of the corner cases nor be sure it is possible.)
SO, MY QUESTION TO YOU IS:
Is that the correct way to implement JudySLn()? My preferred
implementation is to strip all trailing (null or \0 character) from
being stored in the array. Can anybody think of a good case or reason
to NOT do this? I do not consider recovering a null terminating
character a good enough case -- it is just expensive to store in the
array (it could possibly double the memory used in the array).
Strings with imbedded zero characters would not be effected. So a
string "abc\0def\0\0" (length == 9) would be retrieved as "abc\0def"
(length == 7) and no null terminating character.
Thanks for your interest
Doug
Doug Baskins <[email protected]>
________________________________
From: Doug Baskins <[email protected]>
To: Schaeferhaus <[email protected]>
Sent: Thursday, February 26, 2009 5:52:05 PM
Subject: Re: New Judy
Massot:
You caught me without a good answer. JudySL/HS is an "application" using JudyL.
So it is not related to what I am presently working on.
My mind is very deep into Judy1/L right now. I remember that the JudySL (with
string
length and dictionary sorting) is a problem that so far does not have a clean
solution.
If I had a clean solution, I would be able to write it in a week or so.
I feel I have to finish the next version of Judy before playing with JudySLL or
whatever
I call it. So, I will say a year for now. I am sorry I can't be more
accommodating.
Please understand that I believe that JudySL should of had the string length
from the
start. We just did not have time and priority to work on it and JudySL
worked. Some creative thinking is necessary to get it written. Alan wrote a
paper
way back (2001?) on a number of possible ways, and I rejected all of them. If
your are
interested, I will send you a copy.
Thanks for your interest,
Doug
Doug Baskins <[email protected]>
________________________________
From: Schaeferhaus <[email protected]>
To: Doug Baskins <[email protected]>
Sent: Wednesday, February 25, 2009 7:23:23 PM
Subject: New Judy
Hi,
excuse me for asking, but is it possible to know, when i can expect a
test-version of the new judy?
1 week, 1month, 1 year. I'm asking this because of the new feature "non null
terminated strings"
(not the JudyHS).
Thanks
Massot------------------------------------------------------------------------------
Open Source Business Conference (OSBC), March 24-25, 2009, San Francisco, CA
-OSBC tackles the biggest issue in open source: Open Sourcing the Enterprise
-Strategies to boost innovation and cut costs with open source participation
-Receive a $600 discount off the registration fee with the source code: SFAD
http://p.sf.net/sfu/XcvMzF8H
_______________________________________________
Judy-devel mailing list
[email protected]
https://lists.sourceforge.net/lists/listinfo/judy-devel
