gambas-user

[Gambas-user] problems in trie class

[Karl R. <kar...@fe...>]

Salut Tobi,

played with you trie example (trietest) it crash if 
p = h.GetPrefix("texte") find nothing (p=null), even when change
to p = h.GetPrefix("Texte")

My change is h["texte"] to h["Texte"] (source attached)
-- 
Amicalement
Charlie

Re: [Gambas-user] problems in trie class

[Tobias B. <ta...@gm...>]

On Tue, 18 Nov 2014, Karl Reinl wrote:
> Salut Tobi,
> 
> played with you trie example (trietest)
>

I'm glad to hear that :-)

>
> it crash if 
> p = h.GetPrefix("texte") find nothing (p=null), even when change
> to p = h.GetPrefix("Texte")
> 
> My change is h["texte"] to h["Texte"] (source attached)

Not so glad about that...

Did it really crash (i.e. segfault or abort or ...)? When I run the project
it stops at line 25 with the error "Null object" which is to be expected
because the prefix "texte" doesn't exist anymore after your changes. If I
change line 25 to p = h.GetPrefix("Texte"), then it runs through flawlessly
here.

If it really crashes, I need to know your Gambas version / revision and your
system specs, especially your 32- or 64-bitness. It would also help if you
provided a gdb backtrace and a valgrind log of the crash. Do you know how to
do that?

Regards,
Tobi

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk

Re: [Gambas-user] problems in trie class

[Charlie R. <Kar...@Fe...>]

Am Dienstag, den 18.11.2014, 21:48 +0100 schrieb Tobias Boege:
> On Tue, 18 Nov 2014, Karl Reinl wrote:
> > Salut Tobi,
> > 
> > played with you trie example (trietest)
> >
> 
> I'm glad to hear that :-)
> 
> >
> > it crash if 
> > p = h.GetPrefix("texte") find nothing (p=null), even when change
> > to p = h.GetPrefix("Texte")
> > 
> > My change is h["texte"] to h["Texte"] (source attached)
> 
> Not so glad about that...
> 
> Did it really crash (i.e. segfault or abort or ...)? When I run the project
> it stops at line 25 with the error "Null object" which is to be expected
> because the prefix "texte" doesn't exist anymore after your changes. If I
> change line 25 to p = h.GetPrefix("Texte"), then it runs through flawlessly
> here.
> 
It is a #11, CRASH REPORT windows opens

> If it really crashes, I need to know your Gambas version / revision and your
> system specs, especially your 32- or 64-bitness. It would also help if you
> provided a gdb backtrace and a valgrind log of the crash. Do you know how to
> do that?
> 
[System]
Gambas=3.6.90     ----------------->  rev.6647
OperatingSystem=Linux
Kernel=3.2.0-70-generic
Architecture=x86 ------------------>  32 bit
Distribution=Ubuntu 12.04.5 LTS
Desktop=GNOME
Theme=QPlastique
Language=de_DE.UTF-8
Memory=3025M
[Libraries]
Cairo=libcairo.so.2.11000.2
Curl=libcurl.so.4.2.0
DBus=libdbus-1.so.3.5.8
GStreamer=libgstreamer-0.10.so.0.30.0
GTK+3=libgtk-3.so.0.400.2
GTK+=libgtk-x11-2.0.so.0.2400.10
Poppler=libpoppler.so.19.0.0
Qt4=libQtCore.so.4.8.1
SDL=libSDL-1.2.so.0.11.3



> Regards,
> Tobi
> 

(gdb) run
Starting program: /usr/bin/gbx3 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/i386-linux-gnu/libthread_db.so.1".
 -> root
q -> p
Texte -> french
tall -> small
term -> 2+3
test -> tomorrow
text -> words


Program received signal SIGSEGV, Segmentation fault.
0x00337331 in destroy_trie (trie=0x80b53ac, dtor=0x3379f8 <value_dtor>)
    at trie.c:256
256			destroy_trie(trie->children[i], dtor);
(gdb) bt
#0  0x00337331 in destroy_trie (trie=0x80b53ac, dtor=0x3379f8
<value_dtor>)
    at trie.c:256
#1  0x00338368 in Trie_free (_object=0x80aeeec, _param=0xb74a8050)
    at c_trie.c:68
#2  0x08051f54 in EXEC_native () at gbx_exec.c:1366
#3  0x08052657 in EXEC_special (special=1, class=0x80b1884, 
    object=<optimized out>, nparam=0, drop=1 '\001') at gbx_exec.c:1674
#4  0x080527d2 in EXEC_special_inheritance (special=1, class=0x80b1884, 
    object=0x80aeeec, nparam=0, drop=1 '\001') at gbx_exec.c:1730
#5  0x08055895 in CLASS_free (object=0x80aeeec) at gbx_class.c:754
#6  0x08050175 in RELEASE_many (value=<optimized out>, n=0) at
gbx_exec.c:240
#7  0x08050cf0 in EXEC_leave_drop () at gbx_exec.c:795
#8  0x080514fb in EXEC_function_loop () at gbx_exec.c:1053
#9  0x08051826 in EXEC_function_real () at gbx_exec.c:895
#10 0x0804b568 in main (argc=1457883477, argv=0xbffff384) at gbx.c:416
(gdb) 


but I have to say also this. I can NOT run the IDE with gdb 


:~/src/gambas/3/gambas-svn30/app/src/gambas3$ gdb gbx3
GNU gdb (Ubuntu/Linaro 7.4-2012.04-0ubuntu2.1) 7.4-2012.04
Copyright (C) 2012 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later
<http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law.  Type "show
copying"
and "show warranty" for details.
This GDB was configured as "i686-linux-gnu".
For bug reporting instructions, please see:
<http://bugs.launchpad.net/gdb-linaro/>...
Reading symbols from /usr/bin/gbx3...done.
(gdb) run
Starting program: /usr/bin/gbx3 
[Thread debugging using libthread_db enabled]
Using host libthread_db library "/lib/i386-linux-gnu/libthread_db.so.1".
ERROR: #2: Cannot load class 'AngleBox': Unable to load class file
[Inferior 1 (process 7146) exited with code 01]
(gdb) 

-- 
Amicalement
Charlie

Re: [Gambas-user] problems in trie class

[Charlie R. <Kar...@Fe...>]

Am Donnerstag, den 20.11.2014, 15:54 +0100 schrieb Tobias Boege:
> On Tue, 18 Nov 2014, Charlie Reinl wrote:
> > It is a #11, CRASH REPORT windows opens
> > 
> 
> Thanks. I'm sure I can work with this but give me a little time; I have a
> busy week lying ahead...
> 
> As it is a NULL pointer dereference bug (apparently), I can commit a "quick
> fix", that is one which cures the symptom but not the cause, if you need the
> Trie to work ASAP?
> 
> Regards,
> Tobi
> 

Salut Tobi,

no worry, about that, that was just a test to see if and how that works.
The rest of my project keeps me behind the keyboard and the trie can
come later, the  current 'Do While' loop works good and fast.

A wish, something like <trie>.Add(Value,Key) would  simplify filling.


-- 
Amicalement
Charlie

Re: [Gambas-user] problems in trie class

[Tobias B. <ta...@gm...>]

On Tue, 18 Nov 2014, Charlie Reinl wrote:
> It is a #11, CRASH REPORT windows opens
> 

Thanks. I'm sure I can work with this but give me a little time; I have a
busy week lying ahead...

As it is a NULL pointer dereference bug (apparently), I can commit a "quick
fix", that is one which cures the symptom but not the cause, if you need the
Trie to work ASAP?

Regards,
Tobi

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk

Re: [Gambas-user] problems in trie class

[Tobias B. <ta...@gm...>]

On Thu, 20 Nov 2014, Charlie Reinl wrote:
> Am Donnerstag, den 20.11.2014, 15:54 +0100 schrieb Tobias Boege:
> > On Tue, 18 Nov 2014, Charlie Reinl wrote:
> > > It is a #11, CRASH REPORT windows opens
> > > 
> > 
> > Thanks. I'm sure I can work with this but give me a little time; I have a
> > busy week lying ahead...
> > 
> > As it is a NULL pointer dereference bug (apparently), I can commit a "quick
> > fix", that is one which cures the symptom but not the cause, if you need the
> > Trie to work ASAP?
> > 
> > Regards,
> > Tobi
> > 
> 
> Salut Tobi,
> 
> no worry, about that, that was just a test to see if and how that works.
> The rest of my project keeps me behind the keyboard and the trie can
> come later, the  current 'Do While' loop works good and fast.
> 
> A wish, something like <trie>.Add(Value,Key) would  simplify filling.
> 

Will do.

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk

Re: [Gambas-user] problems in trie class

[Charlie R. <Kar...@Fe...>]

Am Donnerstag, den 20.11.2014, 16:24 +0100 schrieb Tobias Boege:
> On Thu, 20 Nov 2014, Charlie Reinl wrote:
> > Am Donnerstag, den 20.11.2014, 15:54 +0100 schrieb Tobias Boege:
> > > On Tue, 18 Nov 2014, Charlie Reinl wrote:
> > > > It is a #11, CRASH REPORT windows opens
> > > > 
> > > 
> > > Thanks. I'm sure I can work with this but give me a little time; I have a
> > > busy week lying ahead...
> > > 
> > > As it is a NULL pointer dereference bug (apparently), I can commit a "quick
> > > fix", that is one which cures the symptom but not the cause, if you need the
> > > Trie to work ASAP?
> > > 
> > > Regards,
> > > Tobi
> > > 
> > 
> > Salut Tobi,
> > 
> > no worry, about that, that was just a test to see if and how that works.
> > The rest of my project keeps me behind the keyboard and the trie can
> > come later, the  current 'Do While' loop works good and fast.
> > 
> > A wish, something like <trie>.Add(Value,Key) would  simplify filling.
> > 
> 
> Will do.
> 
Salut Tobi,

couldn't let the hand off, seems to have a big leak there, or a problem
on my box.
Have for key and value entry. h["OttO"]="OttO" 
-- 
Amicalement
Charlie

Re: [Gambas-user] problems in trie class

[Karl R. <kar...@fe...>]

Am Donnerstag, den 20.11.2014, 16:24 +0100 schrieb Tobias Boege:
> On Thu, 20 Nov 2014, Charlie Reinl wrote:
> > Am Donnerstag, den 20.11.2014, 15:54 +0100 schrieb Tobias Boege:
> > > On Tue, 18 Nov 2014, Charlie Reinl wrote:
> > > > It is a #11, CRASH REPORT windows opens
> > > > 
> > > 
> > > Thanks. I'm sure I can work with this but give me a little time; I have a
> > > busy week lying ahead...
> > > 
> > > As it is a NULL pointer dereference bug (apparently), I can commit a "quick
> > > fix", that is one which cures the symptom but not the cause, if you need the
> > > Trie to work ASAP?
> > > 
> > > Regards,
> > > Tobi
> > > 
> > 
> > Salut Tobi,
> > 
> > no worry, about that, that was just a test to see if and how that works.
> > The rest of my project keeps me behind the keyboard and the trie can
> > come later, the  current 'Do While' loop works good and fast.
> > 
> > A wish, something like <trie>.Add(Value,Key) would  simplify filling.
> > 
> 
> Will do.
> 
Salut Tobi,

send you a test project with 2 screens included. 
The mentioned " different results with arList declaration " is not
proofed.

 
-- 
Amicalement
Charlie

Re: [Gambas-user] problems in trie class

[Tobias B. <ta...@gm...>]

On Tue, 18 Nov 2014, Karl Reinl wrote:
> Salut Tobi,
> 
> played with you trie example (trietest) it crash if 
> p = h.GetPrefix("texte") find nothing (p=null), even when change
> to p = h.GetPrefix("Texte")
> 
> My change is h["texte"] to h["Texte"] (source attached)

Good news: I can reproduce the crash in a fresh VirtualBox'd Ubuntu 12.04
with 32 bits. Let's see if I am mentally able to use that shaky VirtualBox
long enough to fix the error...

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk

Re: [Gambas-user] problems in trie class

[Tobias B. <ta...@gm...>]

On Tue, 18 Nov 2014, Karl Reinl wrote:
> Salut Tobi,
> 
> played with you trie example (trietest) it crash if 
> p = h.GetPrefix("texte") find nothing (p=null), even when change
> to p = h.GetPrefix("Texte")
> 
> My change is h["texte"] to h["Texte"] (source attached)

Can you run your tests with #6688?

Indeed there were bit width errors (I think) but what caused your particular
error here was that a TriePrefix object would erroneously drop reference
counts of its parent Trie object if it couldn't be created. Total nonsense.

Thanks for your report!

As for the leak you showed in a follow-up, I couldn't reproduce that. I'll
try harder if the problem persists with #6688. But I can tell you that this
does not necessarily indicate a severe problem / corruption, as I don't
terminate strings in my trie backend code and it could just be some length
calculations that went wrong. (Most probably that is because the Gambas
string functions automatically use strlen() to determine a string's length
when I give 0 as a length parameter. However, strlen() must not be used on
the strings from my trie.)

Regards,
Tobi

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk

Re: [Gambas-user] problems in trie class

[Charlie R. <Kar...@Fe...>]

Am Samstag, den 29.11.2014, 20:05 +0100 schrieb Tobias Boege:
> On Tue, 18 Nov 2014, Karl Reinl wrote:
> > Salut Tobi,
> > 
> > played with you trie example (trietest) it crash if 
> > p = h.GetPrefix("texte") find nothing (p=null), even when change
> > to p = h.GetPrefix("Texte")
> > 
> > My change is h["texte"] to h["Texte"] (source attached)
> 
> Can you run your tests with #6688?
> 
> Indeed there were bit width errors (I think) but what caused your particular
> error here was that a TriePrefix object would erroneously drop reference
> counts of its parent Trie object if it couldn't be created. Total nonsense.
> 
> Thanks for your report!
> 
> As for the leak you showed in a follow-up, I couldn't reproduce that. I'll
> try harder if the problem persists with #6688. But I can tell you that this
> does not necessarily indicate a severe problem / corruption, as I don't
> terminate strings in my trie backend code and it could just be some length
> calculations that went wrong. (Most probably that is because the Gambas
> string functions automatically use strlen() to determine a string's length
> when I give 0 as a length parameter. However, strlen() must not be used on
> the strings from my trie.)
> 
> Regards,
> Tobi
> 

Salut Tobi,

yes, now no more crash, only an error raises, thats oK.
The leak shown, I can't reproduce any more now..... BUT
Now TriePrefix is case sensitive, in my follow-up the TriePrefix "d"
showed me "D" AND "d"entries, now only the "d", may be thats how trie
work normally, but for my behaves non case sensitive would be better (or
a switch to do like that) 
And we talked about something like <trie>.Add(Value,Key) for simplifing
filling.

Thanks anyway
-- 
Amicalement
Charlie

Re: [Gambas-user] problems in trie class

[Benoît M. <ga...@us...>]

Le 01/12/2014 17:47, Tobias Boege a écrit :
> On Sat, 29 Nov 2014, Charlie Reinl wrote:
>> Am Samstag, den 29.11.2014, 20:05 +0100 schrieb Tobias Boege:
>>> On Tue, 18 Nov 2014, Karl Reinl wrote:
>>>> Salut Tobi,
>>>>
>>>> played with you trie example (trietest) it crash if
>>>> p = h.GetPrefix("texte") find nothing (p=null), even when change
>>>> to p = h.GetPrefix("Texte")
>>>>
>>>> My change is h["texte"] to h["Texte"] (source attached)
>>>
>>> Can you run your tests with #6688?
>>>
>>> Indeed there were bit width errors (I think) but what caused your particular
>>> error here was that a TriePrefix object would erroneously drop reference
>>> counts of its parent Trie object if it couldn't be created. Total nonsense.
>>>
>>> Thanks for your report!
>>>
>>> As for the leak you showed in a follow-up, I couldn't reproduce that. I'll
>>> try harder if the problem persists with #6688. But I can tell you that this
>>> does not necessarily indicate a severe problem / corruption, as I don't
>>> terminate strings in my trie backend code and it could just be some length
>>> calculations that went wrong. (Most probably that is because the Gambas
>>> string functions automatically use strlen() to determine a string's length
>>> when I give 0 as a length parameter. However, strlen() must not be used on
>>> the strings from my trie.)
>>>
>>> Regards,
>>> Tobi
>>>
>>
>> Salut Tobi,
>>
>> yes, now no more crash, only an error raises, thats oK.
>> The leak shown, I can't reproduce any more now..... BUT
>> Now TriePrefix is case sensitive, in my follow-up the TriePrefix "d"
>> showed me "D" AND "d"entries, now only the "d", may be thats how trie
>> work normally,
>>
>
> It should be case-sensitive. If it wasn't before on your system, that was
> a bug (I can't imagine where it came from, though).
>
>> but for my behaves non case sensitive would be better (or
>> a switch to do like that)
>> And we talked about something like <trie>.Add(Value,Key) for simplifing
>> filling.
>>
>
> OK, you get an Add() and Remove() method in #6699, similar to what
> Collection has.
>
> As for the case-insensitivity: I can add an optional constructor argument,
> Mode, which can be gb.Binary or gb.IgnoreCase (just as Collection has).
>
> (After writing about half an hour complaining how hard it would be to get
> case-insensitivity right and efficient) I just had a magnificent idea: I
> will extend the native Trie class in Gambas and do something like that:
>
>    ' Written from scratch, may contain syntax, etc. errors
>
>    Public Struct _Trie_Entry
>      Key As String
>      Value As Variant
>    End Struct
>
>    Public Sub Add(Value As Variant, Key As String)
>      Dim hEntry As New _Trie_Entry
>      Dim sKey As String = Key
>
>      If $iMode = gb.IgnoreCase Then sKey = String.Upper(Key)
>      hEntry.Key = Key
>      hEntry.Value = Value
>      Super.Add(Value, sKey)
>    End
>
> Similarly I can augment _get, _put, etc. so that you won't notice that the
> _Trie_Entry structure exists at all.
>
> If you request a case-insensitive Trie, all keys are upper-case'd internally
> and the real keys are saved as part of the stored object. So you can get
> your original key back later in an enumeration and I don't have to add
> branches in the hot paths of the trie code to support case-insensitivity
> (which would make the whole thing slower -- I don't know if it would be
> noticeable, but...). I will see if I can do that (_next() may impose a
> little problem or maybe not).
>
> @Benoit: I am not familiar with the caveats of UTF-8 strings. If I want to
> implement case-insensitivity by internally converting all characters to
> upper-case, is it sufficient to use String.Upper() or are there hidden
> pitfalls?
>
> Regards,
> Tobi
>

If they are keys, they should be ASCII, not UTF-8, like with the 
Collection class.

If case insensitive is really needed, you should really manage that 
inside the C code of the component.

Regards,

-- 
Benoît Minisini

Re: [Gambas-user] problems in trie class

[Tobias B. <ta...@gm...>]

On Mon, 01 Dec 2014, Beno?t Minisini wrote:
> > (After writing about half an hour complaining how hard it would be to get
> > case-insensitivity right and efficient) I just had a magnificent idea: I
> > will extend the native Trie class in Gambas and do something like that:
> >
> >    ' Written from scratch, may contain syntax, etc. errors
> >
> >    Public Struct _Trie_Entry
> >      Key As String
> >      Value As Variant
> >    End Struct
> >
> >    Public Sub Add(Value As Variant, Key As String)
> >      Dim hEntry As New _Trie_Entry
> >      Dim sKey As String = Key
> >
> >      If $iMode = gb.IgnoreCase Then sKey = String.Upper(Key)
> >      hEntry.Key = Key
> >      hEntry.Value = Value
> >      Super.Add(Value, sKey)
> >    End
> >
> > Similarly I can augment _get, _put, etc. so that you won't notice that the
> > _Trie_Entry structure exists at all.
> >
> > If you request a case-insensitive Trie, all keys are upper-case'd internally
> > and the real keys are saved as part of the stored object. So you can get
> > your original key back later in an enumeration and I don't have to add
> > branches in the hot paths of the trie code to support case-insensitivity
> > (which would make the whole thing slower -- I don't know if it would be
> > noticeable, but...). I will see if I can do that (_next() may impose a
> > little problem or maybe not).
> >
> > @Benoit: I am not familiar with the caveats of UTF-8 strings. If I want to
> > implement case-insensitivity by internally converting all characters to
> > upper-case, is it sufficient to use String.Upper() or are there hidden
> > pitfalls?
> >
> > Regards,
> > Tobi
> >
> 
> If they are keys, they should be ASCII, not UTF-8, like with the 
> Collection class.
> 

Currently the Trie supports arbitrary sequences of bytes as keys. It would
take some time to move the code back in that restricts the key space to
ASCII sequences. Consequently I'd like to leave it as-is.

> If case insensitive is really needed, you should really manage that 
> inside the C code of the component.
> 

Why? With the above method I use some more space but avoid lots of if's in
the more frequently used parts of the C code. Do you see any performance
penalty I'm overlooking?

Regards,
Tobi

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk

Re: [Gambas-user] problems in trie class

[Charlie R. <Kar...@Fe...>]

Am Montag, den 01.12.2014, 17:47 +0100 schrieb Tobias Boege:
> On Sat, 29 Nov 2014, Charlie Reinl wrote:
> > Am Samstag, den 29.11.2014, 20:05 +0100 schrieb Tobias Boege:
> > > On Tue, 18 Nov 2014, Karl Reinl wrote:
> > > > Salut Tobi,
> > > > 
> > > > played with you trie example (trietest) it crash if 
> > > > p = h.GetPrefix("texte") find nothing (p=null), even when change
> > > > to p = h.GetPrefix("Texte")
> > > > 
> > > > My change is h["texte"] to h["Texte"] (source attached)
> > > 
> > > Can you run your tests with #6688?
> > > 
> > > Indeed there were bit width errors (I think) but what caused your particular
> > > error here was that a TriePrefix object would erroneously drop reference
> > > counts of its parent Trie object if it couldn't be created. Total nonsense.
> > > 
> > > Thanks for your report!
> > > 
> > > As for the leak you showed in a follow-up, I couldn't reproduce that. I'll
> > > try harder if the problem persists with #6688. But I can tell you that this
> > > does not necessarily indicate a severe problem / corruption, as I don't
> > > terminate strings in my trie backend code and it could just be some length
> > > calculations that went wrong. (Most probably that is because the Gambas
> > > string functions automatically use strlen() to determine a string's length
> > > when I give 0 as a length parameter. However, strlen() must not be used on
> > > the strings from my trie.)
> > > 
> > > Regards,
> > > Tobi
> > > 
> > 
> > Salut Tobi,
> > 
> > yes, now no more crash, only an error raises, thats oK.
> > The leak shown, I can't reproduce any more now..... BUT
> > Now TriePrefix is case sensitive, in my follow-up the TriePrefix "d"
> > showed me "D" AND "d"entries, now only the "d", may be thats how trie
> > work normally,
> >
> 
> It should be case-sensitive. If it wasn't before on your system, that was
> a bug (I can't imagine where it came from, though).
> 
> > but for my behaves non case sensitive would be better (or
> > a switch to do like that) 
> > And we talked about something like <trie>.Add(Value,Key) for simplifing
> > filling.
> > 
> 
> OK, you get an Add() and Remove() method in #6699, similar to what
> Collection has.
> 
> As for the case-insensitivity: I can add an optional constructor argument,
> Mode, which can be gb.Binary or gb.IgnoreCase (just as Collection has).
> 
> (After writing about half an hour complaining how hard it would be to get
> case-insensitivity right and efficient) I just had a magnificent idea: I
> will extend the native Trie class in Gambas and do something like that:
> 
>   ' Written from scratch, may contain syntax, etc. errors
> 
>   Public Struct _Trie_Entry
>     Key As String
>     Value As Variant
>   End Struct
> 
>   Public Sub Add(Value As Variant, Key As String)
>     Dim hEntry As New _Trie_Entry
>     Dim sKey As String = Key
> 
>     If $iMode = gb.IgnoreCase Then sKey = String.Upper(Key)
>     hEntry.Key = Key
>     hEntry.Value = Value
>     Super.Add(Value, sKey)
>   End
> 
> Similarly I can augment _get, _put, etc. so that you won't notice that the
> _Trie_Entry structure exists at all.
> 
> If you request a case-insensitive Trie, all keys are upper-case'd internally
> and the real keys are saved as part of the stored object. So you can get
> your original key back later in an enumeration and I don't have to add
> branches in the hot paths of the trie code to support case-insensitivity
> (which would make the whole thing slower -- I don't know if it would be
> noticeable, but...). I will see if I can do that (_next() may impose a
> little problem or maybe not).
> 
> @Benoit: I am not familiar with the caveats of UTF-8 strings. If I want to
> implement case-insensitivity by internally converting all characters to
> upper-case, is it sufficient to use String.Upper() or are there hidden
> pitfalls?
> 
> Regards,
> Tobi
> 

Salut Tobi,

I think it would be best, to stay close to the original definition of
trie..."should be case-sensitive".
Every thing else, I can do by myself.
It was just a question because off the first outputs.

-- 
Amicalement
Charlie

Re: [Gambas-user] problems in trie class

[Charlie R. <Kar...@Fe...>]

Am Mittwoch, den 03.12.2014, 11:30 +0100 schrieb Charlie Reinl:
> Am Montag, den 01.12.2014, 23:39 +0100 schrieb Tobias Boege:
> > On Mon, 01 Dec 2014, Charlie Reinl wrote:
> > > Am Montag, den 01.12.2014, 17:47 +0100 schrieb Tobias Boege:
> > > > On Sat, 29 Nov 2014, Charlie Reinl wrote:
> > > > > Am Samstag, den 29.11.2014, 20:05 +0100 schrieb Tobias Boege:
> > > > > > On Tue, 18 Nov 2014, Karl Reinl wrote:
> > > > > > > Salut Tobi,
> > > > > > > 
> > > > > > > played with you trie example (trietest) it crash if 
> > > > > > > p = h.GetPrefix("texte") find nothing (p=null), even when change
> > > > > > > to p = h.GetPrefix("Texte")
> > > > > > > 
> > > > > > > My change is h["texte"] to h["Texte"] (source attached)
> > > > > > 
> > > > > > Can you run your tests with #6688?
> > > > > > 
> > > > > > Indeed there were bit width errors (I think) but what caused your particular
> > > > > > error here was that a TriePrefix object would erroneously drop reference
> > > > > > counts of its parent Trie object if it couldn't be created. Total nonsense.
> > > > > > 
> > > > > > Thanks for your report!
> > > > > > 
> > > > > > As for the leak you showed in a follow-up, I couldn't reproduce that. I'll
> > > > > > try harder if the problem persists with #6688. But I can tell you that this
> > > > > > does not necessarily indicate a severe problem / corruption, as I don't
> > > > > > terminate strings in my trie backend code and it could just be some length
> > > > > > calculations that went wrong. (Most probably that is because the Gambas
> > > > > > string functions automatically use strlen() to determine a string's length
> > > > > > when I give 0 as a length parameter. However, strlen() must not be used on
> > > > > > the strings from my trie.)
> > > > > > 
> > > > > > Regards,
> > > > > > Tobi
> > > > > > 
> > > > > 
> > > > > Salut Tobi,
> > > > > 
> > > > > yes, now no more crash, only an error raises, thats oK.
> > > > > The leak shown, I can't reproduce any more now..... BUT
> > > > > Now TriePrefix is case sensitive, in my follow-up the TriePrefix "d"
> > > > > showed me "D" AND "d"entries, now only the "d", may be thats how trie
> > > > > work normally,
> > > > >
> > > > 
> > > > It should be case-sensitive. If it wasn't before on your system, that was
> > > > a bug (I can't imagine where it came from, though).
> > > > 
> > > > > but for my behaves non case sensitive would be better (or
> > > > > a switch to do like that) 
> > > > > And we talked about something like <trie>.Add(Value,Key) for simplifing
> > > > > filling.
> > > > > 
> > > > 
> > > > OK, you get an Add() and Remove() method in #6699, similar to what
> > > > Collection has.
> > > > 
> > > > As for the case-insensitivity: I can add an optional constructor argument,
> > > > Mode, which can be gb.Binary or gb.IgnoreCase (just as Collection has).
> > > > 
> > > > (After writing about half an hour complaining how hard it would be to get
> > > > case-insensitivity right and efficient) I just had a magnificent idea: I
> > > > will extend the native Trie class in Gambas and do something like that:
> > > > 
> > > >   ' Written from scratch, may contain syntax, etc. errors
> > > > 
> > > >   Public Struct _Trie_Entry
> > > >     Key As String
> > > >     Value As Variant
> > > >   End Struct
> > > > 
> > > >   Public Sub Add(Value As Variant, Key As String)
> > > >     Dim hEntry As New _Trie_Entry
> > > >     Dim sKey As String = Key
> > > > 
> > > >     If $iMode = gb.IgnoreCase Then sKey = String.Upper(Key)
> > > >     hEntry.Key = Key
> > > >     hEntry.Value = Value
> > > >     Super.Add(Value, sKey)
> > > >   End
> > > > 
> > > > Similarly I can augment _get, _put, etc. so that you won't notice that the
> > > > _Trie_Entry structure exists at all.
> > > > 
> > > > If you request a case-insensitive Trie, all keys are upper-case'd internally
> > > > and the real keys are saved as part of the stored object. So you can get
> > > > your original key back later in an enumeration and I don't have to add
> > > > branches in the hot paths of the trie code to support case-insensitivity
> > > > (which would make the whole thing slower -- I don't know if it would be
> > > > noticeable, but...). I will see if I can do that (_next() may impose a
> > > > little problem or maybe not).
> > > > 
> > > > @Benoit: I am not familiar with the caveats of UTF-8 strings. If I want to
> > > > implement case-insensitivity by internally converting all characters to
> > > > upper-case, is it sufficient to use String.Upper() or are there hidden
> > > > pitfalls?
> > > > 
> > > > Regards,
> > > > Tobi
> > > > 
> > > 
> > > Salut Tobi,
> > > 
> > > I think it would be best, to stay close to the original definition of
> > > trie..."should be case-sensitive".
> > > Every thing else, I can do by myself.
> > > It was just a question because off the first outputs.
> > > 
> > 
> > Attached is a project that does this. It should be a complete case-
> > insensitive version of the Trie class. Should work properly with the
> > latest revision (the Trie had a memory leak when objects were replaced
> > until a few minutes ago).
> > 
> > Regards,
> > Tobi
> 
> Thanks Tobi,
> 
> I haven't tested yet, but it looks like a wonderful example, how you can
> extend a gambas class. 
> For my case, KEY and VALUE will have the same entry, I use the key in
> Uppercase.
> 

Salut Tobi,

now I've one last question, about this case-insensitive version of the
Trie class.
Do you plan to release this case-insensitive version to gambas or is it
a case study for you?

-- 
Amicalement
Charlie

Re: [Gambas-user] problems in trie class

[Tobias B. <ta...@gm...>]

On Wed, 03 Dec 2014, Charlie Reinl wrote:
> > > > > It should be case-sensitive. If it wasn't before on your system, that was
> > > > > a bug (I can't imagine where it came from, though).
> > > > > 
> > > > > > but for my behaves non case sensitive would be better (or
> > > > > > a switch to do like that) 
> > > > > > And we talked about something like <trie>.Add(Value,Key) for simplifing
> > > > > > filling.
> > > > > > 
> > > > > 
> > > > > OK, you get an Add() and Remove() method in #6699, similar to what
> > > > > Collection has.
> > > > > 
> > > > > As for the case-insensitivity: I can add an optional constructor argument,
> > > > > Mode, which can be gb.Binary or gb.IgnoreCase (just as Collection has).
> > > > > 
> > > > > (After writing about half an hour complaining how hard it would be to get
> > > > > case-insensitivity right and efficient) I just had a magnificent idea: I
> > > > > will extend the native Trie class in Gambas and do something like that:
> > > > > 
> > > > >   ' Written from scratch, may contain syntax, etc. errors
> > > > > 
> > > > >   Public Struct _Trie_Entry
> > > > >     Key As String
> > > > >     Value As Variant
> > > > >   End Struct
> > > > > 
> > > > >   Public Sub Add(Value As Variant, Key As String)
> > > > >     Dim hEntry As New _Trie_Entry
> > > > >     Dim sKey As String = Key
> > > > > 
> > > > >     If $iMode = gb.IgnoreCase Then sKey = String.Upper(Key)
> > > > >     hEntry.Key = Key
> > > > >     hEntry.Value = Value
> > > > >     Super.Add(Value, sKey)
> > > > >   End
> > > > > 
> > > > > Similarly I can augment _get, _put, etc. so that you won't notice that the
> > > > > _Trie_Entry structure exists at all.
> > > > > 
> > > > > If you request a case-insensitive Trie, all keys are upper-case'd internally
> > > > > and the real keys are saved as part of the stored object. So you can get
> > > > > your original key back later in an enumeration and I don't have to add
> > > > > branches in the hot paths of the trie code to support case-insensitivity
> > > > > (which would make the whole thing slower -- I don't know if it would be
> > > > > noticeable, but...). I will see if I can do that (_next() may impose a
> > > > > little problem or maybe not).
> > > > > 
> > > > > @Benoit: I am not familiar with the caveats of UTF-8 strings. If I want to
> > > > > implement case-insensitivity by internally converting all characters to
> > > > > upper-case, is it sufficient to use String.Upper() or are there hidden
> > > > > pitfalls?
> > > > > 
> > > > > Regards,
> > > > > Tobi
> > > > > 
> > > > 
> > > > Salut Tobi,
> > > > 
> > > > I think it would be best, to stay close to the original definition of
> > > > trie..."should be case-sensitive".
> > > > Every thing else, I can do by myself.
> > > > It was just a question because off the first outputs.
> > > > 
> > > 
> > > Attached is a project that does this. It should be a complete case-
> > > insensitive version of the Trie class. Should work properly with the
> > > latest revision (the Trie had a memory leak when objects were replaced
> > > until a few minutes ago).
> > > 
> > > Regards,
> > > Tobi
> > 
> > Thanks Tobi,
> > 
> > I haven't tested yet, but it looks like a wonderful example, how you can
> > extend a gambas class. 
> > For my case, KEY and VALUE will have the same entry, I use the key in
> > Uppercase.
> > 
> 
> Salut Tobi,
> 
> now I've one last question, about this case-insensitive version of the
> Trie class.
> Do you plan to release this case-insensitive version to gambas or is it
> a case study for you?
> 

You tell me :-) If it behaves well (I haven't tried much), I'll include it.

Regards,
Tobi

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk

Re: [Gambas-user] problems in trie class

[Tobias B. <ta...@gm...>]

On Sat, 29 Nov 2014, Charlie Reinl wrote:
> Am Samstag, den 29.11.2014, 20:05 +0100 schrieb Tobias Boege:
> > On Tue, 18 Nov 2014, Karl Reinl wrote:
> > > Salut Tobi,
> > > 
> > > played with you trie example (trietest) it crash if 
> > > p = h.GetPrefix("texte") find nothing (p=null), even when change
> > > to p = h.GetPrefix("Texte")
> > > 
> > > My change is h["texte"] to h["Texte"] (source attached)
> > 
> > Can you run your tests with #6688?
> > 
> > Indeed there were bit width errors (I think) but what caused your particular
> > error here was that a TriePrefix object would erroneously drop reference
> > counts of its parent Trie object if it couldn't be created. Total nonsense.
> > 
> > Thanks for your report!
> > 
> > As for the leak you showed in a follow-up, I couldn't reproduce that. I'll
> > try harder if the problem persists with #6688. But I can tell you that this
> > does not necessarily indicate a severe problem / corruption, as I don't
> > terminate strings in my trie backend code and it could just be some length
> > calculations that went wrong. (Most probably that is because the Gambas
> > string functions automatically use strlen() to determine a string's length
> > when I give 0 as a length parameter. However, strlen() must not be used on
> > the strings from my trie.)
> > 
> > Regards,
> > Tobi
> > 
> 
> Salut Tobi,
> 
> yes, now no more crash, only an error raises, thats oK.
> The leak shown, I can't reproduce any more now..... BUT
> Now TriePrefix is case sensitive, in my follow-up the TriePrefix "d"
> showed me "D" AND "d"entries, now only the "d", may be thats how trie
> work normally,
>

It should be case-sensitive. If it wasn't before on your system, that was
a bug (I can't imagine where it came from, though).

> but for my behaves non case sensitive would be better (or
> a switch to do like that) 
> And we talked about something like <trie>.Add(Value,Key) for simplifing
> filling.
> 

OK, you get an Add() and Remove() method in #6699, similar to what
Collection has.

As for the case-insensitivity: I can add an optional constructor argument,
Mode, which can be gb.Binary or gb.IgnoreCase (just as Collection has).

(After writing about half an hour complaining how hard it would be to get
case-insensitivity right and efficient) I just had a magnificent idea: I
will extend the native Trie class in Gambas and do something like that:

  ' Written from scratch, may contain syntax, etc. errors

  Public Struct _Trie_Entry
    Key As String
    Value As Variant
  End Struct

  Public Sub Add(Value As Variant, Key As String)
    Dim hEntry As New _Trie_Entry
    Dim sKey As String = Key

    If $iMode = gb.IgnoreCase Then sKey = String.Upper(Key)
    hEntry.Key = Key
    hEntry.Value = Value
    Super.Add(Value, sKey)
  End

Similarly I can augment _get, _put, etc. so that you won't notice that the
_Trie_Entry structure exists at all.

If you request a case-insensitive Trie, all keys are upper-case'd internally
and the real keys are saved as part of the stored object. So you can get
your original key back later in an enumeration and I don't have to add
branches in the hot paths of the trie code to support case-insensitivity
(which would make the whole thing slower -- I don't know if it would be
noticeable, but...). I will see if I can do that (_next() may impose a
little problem or maybe not).

@Benoit: I am not familiar with the caveats of UTF-8 strings. If I want to
implement case-insensitivity by internally converting all characters to
upper-case, is it sufficient to use String.Upper() or are there hidden
pitfalls?

Regards,
Tobi

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk

Re: [Gambas-user] problems in trie class

[Tobias B. <ta...@gm...>]

On Mon, 01 Dec 2014, Tobias Boege wrote:
>   Public Sub Add(Value As Variant, Key As String)
>     Dim hEntry As New _Trie_Entry
>     Dim sKey As String = Key
> 
>     If $iMode = gb.IgnoreCase Then sKey = String.Upper(Key)
>     hEntry.Key = Key
>     hEntry.Value = Value
>     Super.Add(Value, sKey)

-->   Super.Add(hEntry, sKey)

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk

Re: [Gambas-user] problems in trie class

[Tobias B. <ta...@gm...>]

On Mon, 01 Dec 2014, Tobias Boege wrote:
> > If they are keys, they should be ASCII, not UTF-8, like with the 
> > Collection class.
> > 
> 
> Currently the Trie supports arbitrary sequences of bytes as keys. It would
> take some time to move the code back in that restricts the key space to
> ASCII sequences. Consequently I'd like to leave it as-is.
> 

OTOH, I will save 16 bytes per trie node if I restrict the key space to
ASCII. I'll put the restriction back in place sometime later.

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk

Re: [Gambas-user] problems in trie class

[Benoît M. <ga...@us...>]

Le 01/12/2014 19:05, Tobias Boege a écrit :
> On Mon, 01 Dec 2014, Tobias Boege wrote:
>>> If they are keys, they should be ASCII, not UTF-8, like with the
>>> Collection class.
>>>
>>
>> Currently the Trie supports arbitrary sequences of bytes as keys. It would
>> take some time to move the code back in that restricts the key space to
>> ASCII sequences. Consequently I'd like to leave it as-is.
>>
>
> OTOH, I will save 16 bytes per trie node if I restrict the key space to
> ASCII. I'll put the restriction back in place sometime later.
>

You have nothing to change. If you are case-sensitive, then your keys 
are automatically both ASCII and UTF-8. I'm speaking about charset only 
when case matters (because case depends on charset).

So I mean that if you want to be case unsensitive, then you must be case 
unsensitive in the ASCII sense, not UTF-8, to be compatible with the 
Collection class, and because UTF-8 case support is slow as hell.

Regards,

-- 
Benoît Minisini

Re: [Gambas-user] problems in trie class

[Tobias B. <ta...@gm...>]

On Mon, 01 Dec 2014, Charlie Reinl wrote:
> Am Montag, den 01.12.2014, 17:47 +0100 schrieb Tobias Boege:
> > On Sat, 29 Nov 2014, Charlie Reinl wrote:
> > > Am Samstag, den 29.11.2014, 20:05 +0100 schrieb Tobias Boege:
> > > > On Tue, 18 Nov 2014, Karl Reinl wrote:
> > > > > Salut Tobi,
> > > > > 
> > > > > played with you trie example (trietest) it crash if 
> > > > > p = h.GetPrefix("texte") find nothing (p=null), even when change
> > > > > to p = h.GetPrefix("Texte")
> > > > > 
> > > > > My change is h["texte"] to h["Texte"] (source attached)
> > > > 
> > > > Can you run your tests with #6688?
> > > > 
> > > > Indeed there were bit width errors (I think) but what caused your particular
> > > > error here was that a TriePrefix object would erroneously drop reference
> > > > counts of its parent Trie object if it couldn't be created. Total nonsense.
> > > > 
> > > > Thanks for your report!
> > > > 
> > > > As for the leak you showed in a follow-up, I couldn't reproduce that. I'll
> > > > try harder if the problem persists with #6688. But I can tell you that this
> > > > does not necessarily indicate a severe problem / corruption, as I don't
> > > > terminate strings in my trie backend code and it could just be some length
> > > > calculations that went wrong. (Most probably that is because the Gambas
> > > > string functions automatically use strlen() to determine a string's length
> > > > when I give 0 as a length parameter. However, strlen() must not be used on
> > > > the strings from my trie.)
> > > > 
> > > > Regards,
> > > > Tobi
> > > > 
> > > 
> > > Salut Tobi,
> > > 
> > > yes, now no more crash, only an error raises, thats oK.
> > > The leak shown, I can't reproduce any more now..... BUT
> > > Now TriePrefix is case sensitive, in my follow-up the TriePrefix "d"
> > > showed me "D" AND "d"entries, now only the "d", may be thats how trie
> > > work normally,
> > >
> > 
> > It should be case-sensitive. If it wasn't before on your system, that was
> > a bug (I can't imagine where it came from, though).
> > 
> > > but for my behaves non case sensitive would be better (or
> > > a switch to do like that) 
> > > And we talked about something like <trie>.Add(Value,Key) for simplifing
> > > filling.
> > > 
> > 
> > OK, you get an Add() and Remove() method in #6699, similar to what
> > Collection has.
> > 
> > As for the case-insensitivity: I can add an optional constructor argument,
> > Mode, which can be gb.Binary or gb.IgnoreCase (just as Collection has).
> > 
> > (After writing about half an hour complaining how hard it would be to get
> > case-insensitivity right and efficient) I just had a magnificent idea: I
> > will extend the native Trie class in Gambas and do something like that:
> > 
> >   ' Written from scratch, may contain syntax, etc. errors
> > 
> >   Public Struct _Trie_Entry
> >     Key As String
> >     Value As Variant
> >   End Struct
> > 
> >   Public Sub Add(Value As Variant, Key As String)
> >     Dim hEntry As New _Trie_Entry
> >     Dim sKey As String = Key
> > 
> >     If $iMode = gb.IgnoreCase Then sKey = String.Upper(Key)
> >     hEntry.Key = Key
> >     hEntry.Value = Value
> >     Super.Add(Value, sKey)
> >   End
> > 
> > Similarly I can augment _get, _put, etc. so that you won't notice that the
> > _Trie_Entry structure exists at all.
> > 
> > If you request a case-insensitive Trie, all keys are upper-case'd internally
> > and the real keys are saved as part of the stored object. So you can get
> > your original key back later in an enumeration and I don't have to add
> > branches in the hot paths of the trie code to support case-insensitivity
> > (which would make the whole thing slower -- I don't know if it would be
> > noticeable, but...). I will see if I can do that (_next() may impose a
> > little problem or maybe not).
> > 
> > @Benoit: I am not familiar with the caveats of UTF-8 strings. If I want to
> > implement case-insensitivity by internally converting all characters to
> > upper-case, is it sufficient to use String.Upper() or are there hidden
> > pitfalls?
> > 
> > Regards,
> > Tobi
> > 
> 
> Salut Tobi,
> 
> I think it would be best, to stay close to the original definition of
> trie..."should be case-sensitive".
> Every thing else, I can do by myself.
> It was just a question because off the first outputs.
> 

Attached is a project that does this. It should be a complete case-
insensitive version of the Trie class. Should work properly with the
latest revision (the Trie had a memory leak when objects were replaced
until a few minutes ago).

Regards,
Tobi

-- 
"There's an old saying: Don't change anything... ever!" -- Mr. Monk

Re: [Gambas-user] problems in trie class

[Charlie R. <Kar...@Fe...>]

Am Montag, den 01.12.2014, 23:39 +0100 schrieb Tobias Boege:
> On Mon, 01 Dec 2014, Charlie Reinl wrote:
> > Am Montag, den 01.12.2014, 17:47 +0100 schrieb Tobias Boege:
> > > On Sat, 29 Nov 2014, Charlie Reinl wrote:
> > > > Am Samstag, den 29.11.2014, 20:05 +0100 schrieb Tobias Boege:
> > > > > On Tue, 18 Nov 2014, Karl Reinl wrote:
> > > > > > Salut Tobi,
> > > > > > 
> > > > > > played with you trie example (trietest) it crash if 
> > > > > > p = h.GetPrefix("texte") find nothing (p=null), even when change
> > > > > > to p = h.GetPrefix("Texte")
> > > > > > 
> > > > > > My change is h["texte"] to h["Texte"] (source attached)
> > > > > 
> > > > > Can you run your tests with #6688?
> > > > > 
> > > > > Indeed there were bit width errors (I think) but what caused your particular
> > > > > error here was that a TriePrefix object would erroneously drop reference
> > > > > counts of its parent Trie object if it couldn't be created. Total nonsense.
> > > > > 
> > > > > Thanks for your report!
> > > > > 
> > > > > As for the leak you showed in a follow-up, I couldn't reproduce that. I'll
> > > > > try harder if the problem persists with #6688. But I can tell you that this
> > > > > does not necessarily indicate a severe problem / corruption, as I don't
> > > > > terminate strings in my trie backend code and it could just be some length
> > > > > calculations that went wrong. (Most probably that is because the Gambas
> > > > > string functions automatically use strlen() to determine a string's length
> > > > > when I give 0 as a length parameter. However, strlen() must not be used on
> > > > > the strings from my trie.)
> > > > > 
> > > > > Regards,
> > > > > Tobi
> > > > > 
> > > > 
> > > > Salut Tobi,
> > > > 
> > > > yes, now no more crash, only an error raises, thats oK.
> > > > The leak shown, I can't reproduce any more now..... BUT
> > > > Now TriePrefix is case sensitive, in my follow-up the TriePrefix "d"
> > > > showed me "D" AND "d"entries, now only the "d", may be thats how trie
> > > > work normally,
> > > >
> > > 
> > > It should be case-sensitive. If it wasn't before on your system, that was
> > > a bug (I can't imagine where it came from, though).
> > > 
> > > > but for my behaves non case sensitive would be better (or
> > > > a switch to do like that) 
> > > > And we talked about something like <trie>.Add(Value,Key) for simplifing
> > > > filling.
> > > > 
> > > 
> > > OK, you get an Add() and Remove() method in #6699, similar to what
> > > Collection has.
> > > 
> > > As for the case-insensitivity: I can add an optional constructor argument,
> > > Mode, which can be gb.Binary or gb.IgnoreCase (just as Collection has).
> > > 
> > > (After writing about half an hour complaining how hard it would be to get
> > > case-insensitivity right and efficient) I just had a magnificent idea: I
> > > will extend the native Trie class in Gambas and do something like that:
> > > 
> > >   ' Written from scratch, may contain syntax, etc. errors
> > > 
> > >   Public Struct _Trie_Entry
> > >     Key As String
> > >     Value As Variant
> > >   End Struct
> > > 
> > >   Public Sub Add(Value As Variant, Key As String)
> > >     Dim hEntry As New _Trie_Entry
> > >     Dim sKey As String = Key
> > > 
> > >     If $iMode = gb.IgnoreCase Then sKey = String.Upper(Key)
> > >     hEntry.Key = Key
> > >     hEntry.Value = Value
> > >     Super.Add(Value, sKey)
> > >   End
> > > 
> > > Similarly I can augment _get, _put, etc. so that you won't notice that the
> > > _Trie_Entry structure exists at all.
> > > 
> > > If you request a case-insensitive Trie, all keys are upper-case'd internally
> > > and the real keys are saved as part of the stored object. So you can get
> > > your original key back later in an enumeration and I don't have to add
> > > branches in the hot paths of the trie code to support case-insensitivity
> > > (which would make the whole thing slower -- I don't know if it would be
> > > noticeable, but...). I will see if I can do that (_next() may impose a
> > > little problem or maybe not).
> > > 
> > > @Benoit: I am not familiar with the caveats of UTF-8 strings. If I want to
> > > implement case-insensitivity by internally converting all characters to
> > > upper-case, is it sufficient to use String.Upper() or are there hidden
> > > pitfalls?
> > > 
> > > Regards,
> > > Tobi
> > > 
> > 
> > Salut Tobi,
> > 
> > I think it would be best, to stay close to the original definition of
> > trie..."should be case-sensitive".
> > Every thing else, I can do by myself.
> > It was just a question because off the first outputs.
> > 
> 
> Attached is a project that does this. It should be a complete case-
> insensitive version of the Trie class. Should work properly with the
> latest revision (the Trie had a memory leak when objects were replaced
> until a few minutes ago).
> 
> Regards,
> Tobi

Thanks Tobi,

I haven't tested yet, but it looks like a wonderful example, how you can
extend a gambas class. 
For my case, KEY and VALUE will have the same entry, I use the key in
Uppercase.

-- 
Amicalement
Charlie