Numerically largest entry in a trie of digits

[H. S. Teoh]

On Tue, Apr 19, 2022 at 05:12:30PM -0700, H. S. Teoh via Digitalmars-d wrote:
> On Tue, Apr 19, 2022 at 02:37:07PM -0700, Ali Çehreli via Digitalmars-d wrote:
[...]
> !!! Ali, you're a genius!  Pad the numbers with 0's up to some maximum
> number of digits (for this particular trie I'm not expecting more than
> a handful of digits anyway), and that would ensure numerical order ==
> lexicographic order, so the problem becomes trivial. It also
> simultaneously solves a bunch of other issues I have, all stemming
> from the fact that with digit strings of non-equal lengths, numerical
> order != lexicographic order.
[...]

Hmm, actually, it turns out that padding with 0's breaks the very reason
I'm using a trie in the first place (it's for detecting potential
matches of a set of numbers based on an incomplete input prefix). So
it's a no-go, even though it was a genius idea. :-(

Looks like the best solution is just to separately index the set with a
sorted linear array... Steven's idea of storing max lengths in each node
does work for this specific problem, but it makes other operations
needlessly hard.  So also no-go. :-/


T

-- 
Be in denial for long enough, and one day you'll deny yourself of things you wish you hadn't.