Does someone has some need for Ternary Search Trees into Phobos (for D1. And eventually later for D2 too)?
TSTs allow to find keys, key prefixes, or even keys with holes. Keys are arrays of T, where T is the template type.
They can be designed to store the keys alone, or as an associative data structure.

With some benchmarks I have seen that a simple TST implementation is about as fast as the built-in AAs of D (but much slower than Python dicts).

Bye,
bearophile

bearophile wrote:
> Does someone has some need for Ternary Search Trees into Phobos (for D1. And eventually later for D2 too)?
> TSTs allow to find keys, key prefixes, or even keys with holes. Keys are arrays of T, where T is the template type.
> They can be designed to store the keys alone, or as an associative data structure.
> 
> With some benchmarks I have seen that a simple TST implementation is about as fast as the built-in AAs of D (but much slower than Python dicts).
> 
> Bye,
> bearophile

I'd love to see them! Got a Tango version? ;-P

Also, D's AAs aren't a great benchmark, since they are outperformed by even a basic hashtable implementation (compare them to tango.util.collection.HashMap). But TSTs support many more operations, so the fact that they're slower than BSTs/Hashtables is to be expected.

bearophile wrote:
> Does someone has some need for Ternary Search Trees into Phobos (for D1. And eventually later for D2 too)?
> TSTs allow to find keys, key prefixes, or even keys with holes. Keys are arrays of T, where T is the template type.
> They can be designed to store the keys alone, or as an associative data structure.
> 
> With some benchmarks I have seen that a simple TST implementation is about as fast as the built-in AAs of D (but much slower than Python dicts).
> 
> Bye,
> bearophile

Hey, could you please post your implementation (assuming it's open-source?) I'd love to use them, but can't be bothered to implement it. Thanks!

Robert Fraser wrote:
> bearophile wrote:
>> Does someone has some need for Ternary Search Trees into Phobos (for D1. And eventually later for D2 too)?
>> TSTs allow to find keys, key prefixes, or even keys with holes. Keys are arrays of T, where T is the template type.
>> They can be designed to store the keys alone, or as an associative data structure.
>>
>> With some benchmarks I have seen that a simple TST implementation is about as fast as the built-in AAs of D (but much slower than Python dicts).
>>
>> Bye,
>> bearophile
> 
> Hey, could you please post your implementation (assuming it's open-source?) I'd love to use them, but can't be bothered to implement it. Thanks!

BTW, anyone got a KD-tree implementation? I could use one.

Andrei

Andrei Alexandrescu:
> BTW, anyone got a KD-tree implementation? I could use one.

I think at the moment I have none, but a 2D/3D one deserves to be in the std lib, because it allows you to reduce the complexity of lot of geometric-based code.

Bye,
bearophile

Andrei Alexandrescu wrote:
> Robert Fraser wrote:
>> bearophile wrote:
>>> Does someone has some need for Ternary Search Trees into Phobos (for
>>> D1. And eventually later for D2 too)?
>>> TSTs allow to find keys, key prefixes, or even keys with holes. Keys
>>> are arrays of T, where T is the template type.
>>> They can be designed to store the keys alone, or as an associative
>>> data structure.
>>>
>>> With some benchmarks I have seen that a simple TST implementation is about as fast as the built-in AAs of D (but much slower than Python dicts).
>>>
>>> Bye,
>>> bearophile
>>
>> Hey, could you please post your implementation (assuming it's open-source?) I'd love to use them, but can't be bothered to implement it. Thanks!
> 
> BTW, anyone got a KD-tree implementation? I could use one.
> 
> Andrei

A random idea occurs: it might be interesting to put up a page somewhere of "things we'd like in the standard library."  Provide details on a rough API, functionality and license.  Might get some people bored on a weekend dropping in code for the standard library.  :)

  -- Daniel

Robert Fraser:
> Hey, could you please post your implementation (assuming it's open-source?) I'd love to use them, but can't be bothered to implement it. Thanks!

It's just a translation to D of this Py code:
Info:
http://jeethurao.com/blog/?p=146
Code:
http://bitbucket.org/woadwarrior/trie/

Where necessary you can also follow the ideas from the original article here (but using an enum is MUCH better and it's also safer in C, to avoid aliasing):
http://www.ddj.com/windows/184410528

My implementation is about 57 times faster than the Python version and much faster than the Psyco version too.

You can also take a look here: http://sourceforge.net/projects/ternary/

You can implement it with a _single_ template struct, filled with all the methods you want:

struct TST(T) {
    TST* left, right;
    union {
      TST* mid;
      int index;
    }
    T item;

    // methods here
}

Note that inside there you don't need TST!(T)*, TST* is probably enough, but I don't know why yet.

You can start with only the few basic methods, test them, and later when/if you want you can add more methods, taking ideas from here:
http://abc.se/~re/code/tst/tst_docs/index.html

I'd like to not show my code because it's not nice, it has no comments, tests, etc. But it's quite close to that Py code.

A problem with that template struct is that even if you add a opIn_r() method as I have done, then you have to do (note the star):
if (!(k in *ds))

I don't know if in D2 for structs you can use the syntax you use with classes:
if (!(k in ds))

Even better syntax is:
if (k !in ds)

In Python you write something better still:
if k not in ds:

Bye,
bearophile

On 2009-04-16 18:19:36 +0200, bearophile <bearophileHUGS@lycos.com> said:

> [...]
> struct TST(T) {
>     TST* left, right;
>     union {
>       TST* mid;
>       int index;
>     }
>     T item;
> 
>     // methods here
> }
> 
> Note that inside there you don't need TST!(T)*, TST* is probably enough, but I don't know why yet.

struct TST(T){ ... }

is syntactic sugar for

template TST(T){
 struct TST{ ...}
}

so TST in the structure refers by default to the struct itself.

Fawzi

bearophile Wrote:

> Robert Fraser:
> > Hey, could you please post your implementation (assuming it's open-source?) I'd love to use them, but can't be bothered to implement it. Thanks!
> 
> It's just a translation to D of this Py code:
> Info:
> http://jeethurao.com/blog/?p=146
> Code:
> http://bitbucket.org/woadwarrior/trie/
> 
> Where necessary you can also follow the ideas from the original article here (but using an enum is MUCH better and it's also safer in C, to avoid aliasing):
> http://www.ddj.com/windows/184410528
> 
> My implementation is about 57 times faster than the Python version and much faster than the Psyco version too.
> 
> You can also take a look here: http://sourceforge.net/projects/ternary/
> 
> You can implement it with a _single_ template struct, filled with all the methods you want:
> 
> struct TST(T) {
>     TST* left, right;
>     union {
>       TST* mid;
>       int index;
>     }
>     T item;
> 
>     // methods here
> }
> 
> Note that inside there you don't need TST!(T)*, TST* is probably enough, but I don't know why yet.
> 
> You can start with only the few basic methods, test them, and later when/if you want you can add more methods, taking ideas from here:
> http://abc.se/~re/code/tst/tst_docs/index.html
> 
> I'd like to not show my code because it's not nice, it has no comments, tests, etc. But it's quite close to that Py code.
> 
> A problem with that template struct is that even if you add a opIn_r() method as I have done, then you have to do (note the star):
> if (!(k in *ds))
> 
> I don't know if in D2 for structs you can use the syntax you use with classes:
> if (!(k in ds))
> 
> Even better syntax is:
> if (k !in ds)
> 
> In Python you write something better still:
> if k not in ds:
> 
> Bye,
> bearophile

Why use a struct for TST? it requires you to use pointers everywhere and passing by value hardly makes any sense. A class (optionally with final methods for speed) would work a lot better. It even fixes your issue with opIn

Jason House wrote:
> bearophile Wrote:
> 
>> Robert Fraser:
>>> Hey, could you please post your implementation (assuming it's open-source?) I'd love to use them, but can't be bothered to implement it. Thanks!
>> It's just a translation to D of this Py code:
>> Info:
>> http://jeethurao.com/blog/?p=146
>> Code:
>> http://bitbucket.org/woadwarrior/trie/
>>
>> Where necessary you can also follow the ideas from the original article here (but using an enum is MUCH better and it's also safer in C, to avoid aliasing):
>> http://www.ddj.com/windows/184410528
>>
>> My implementation is about 57 times faster than the Python version and much faster than the Psyco version too.
>>
>> You can also take a look here:
>> http://sourceforge.net/projects/ternary/
>>
>> You can implement it with a _single_ template struct, filled with all the methods you want:
>>
>> struct TST(T) {
>>     TST* left, right;     union {
>>       TST* mid;
>>       int index;
>>     }
>>     T item;
>>
>>     // methods here
>> }
>>
>> Note that inside there you don't need TST!(T)*, TST* is probably enough, but I don't know why yet.
>>
>> You can start with only the few basic methods, test them, and later when/if you want you can add more methods, taking ideas from here:
>> http://abc.se/~re/code/tst/tst_docs/index.html
>>
>> I'd like to not show my code because it's not nice, it has no comments, tests, etc. But it's quite close to that Py code.
>>
>> A problem with that template struct is that even if you add a opIn_r() method as I have done, then you have to do (note the star):
>> if (!(k in *ds))
>>
>> I don't know if in D2 for structs you can use the syntax you use with classes:
>> if (!(k in ds))
>>
>> Even better syntax is:
>> if (k !in ds)
>>
>> In Python you write something better still:
>> if k not in ds:
>>
>> Bye,
>> bearophile
> 
> Why use a struct for TST? it requires you to use pointers everywhere and passing by value hardly makes any sense. A class (optionally with final methods for speed) would work a lot better. It even fixes your issue with opIn

I assume it saves some space (classes have a monitor and vtbl pointer which are un-needed here). For maximum efficiency, rather than mallocing individual nodes, you'd want to be using some sort of array.