[Gambas-user] problems in trie class

[Tobias Boege]

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