View mode: basic / threaded / horizontal-split · Log in · Help
July 26, 2007
C++/ D C struct2 D inner classes, C++ templates/D templates
Hi :
it is about translating a C++ B+Tree algoritm into D.
Question No1 <g>
#include <algorithm>
#include <functional>
etc. and so on

*The C++* source looks like :
template <typename _Key, typename _Data,
          typename _Value = std::pair<_Key, _Data>,
          typename _Compare = std::less<_Key>,
          typename _Traits = btree_default_map_traits<_Key, _Data>,
          bool _Duplicates = false>

class bptree
{
public:
    typedef _Key                        key_type;

  //etc, and so on

private :
  struct node
  {
    //contains somethink like
    inline void initialize(const unsigned short l)
    {
      level = l;
      slotuse = 0;
    }
  struct inner_node : public node
  {
  }


}


*IN D*, I would like to use adaptor classes instead of structs -> struct 
inheritance

class BplusTtree(_Key, _Data, and so on, bool _Duplicates=false)
{
  class node(){}
  // and
  class inner_node : node{}

}

Is this legal ?

No2 :
The code contains std::pairs, (for key, value pairs)
What is the fasted (execution-speed) way to implement this in D ?

No3 :
C++ *prepare_cast, static_cast* just cast(whatever) in D ?

Sorry for beeing so ignorant but I just have basic C++ knowhow, and I am 
 still learning about D templates. Many thanks in advance
Bjoern
July 26, 2007
Re: C++/ D C struct2 D inner classes, C++ templates/D templates
BLS wrote:
> Hi :
> it is about translating a C++ B+Tree algoritm into D.
> Question No1 <g>
> #include <algorithm>
> #include <functional>
> etc. and so on
> 
> *The C++* source looks like :
> template <typename _Key, typename _Data,
>           typename _Value = std::pair<_Key, _Data>,
>           typename _Compare = std::less<_Key>,
>           typename _Traits = btree_default_map_traits<_Key, _Data>,
>           bool _Duplicates = false>
> 
> class bptree
> {
> public:
>     typedef _Key                        key_type;
> 
>   //etc, and so on
> 
> private :
>   struct node
>   {
>     //contains somethink like
>     inline void initialize(const unsigned short l)
>     {
>       level = l;
>       slotuse = 0;
>     }
>   struct inner_node : public node
>   {
>   }
> 
> 
> }
> 
> 
> *IN D*, I would like to use adaptor classes instead of structs -> struct 
> inheritance
> 
> class BplusTtree(_Key, _Data, and so on, bool _Duplicates=false)
> {
>   class node(){}
>   // and
>   class inner_node : node{}
> 
> }
> 
> Is this legal ?

If you mean just "are inner classes" legal, then yes.  In the way you 
show above, the class will belong to a given class instance/object.  If 
you prefix them with 'static' they will belong to the class (aka 
template instance, in this case).

If you meant something else in particular... then I'm not sure what you 
meant.  :)

> No2 :
> The code contains std::pairs, (for key, value pairs)
> What is the fasted (execution-speed) way to implement this in D ?

Associative array.  I'm not sure if there's any difference between AA's 
in D/1.x versus D/2.x, so I'll link to both.
http://digitalmars.com/d/1.0/arrays.html#associative
http://digitalmars.com/d/arrays.html#associative

> No3 :
> C++ *prepare_cast, static_cast* just cast(whatever) in D ?

Yes, just cast(whatever).

> Sorry for beeing so ignorant but I just have basic C++ knowhow, and I am 
>  still learning about D templates. Many thanks in advance
> Bjoern
> 
> 
> 

No apologies necessary.

-- Chris Nicholson-Sauls
July 26, 2007
Re: C++/ D C struct2 D inner classes, C++ templates/D templates
Hi Chris,
MANY THANKS.
Your help is kicking me into the right direction.

I am pretty sure that you (as nice guy and brainiac) will translate the 
the C++ implementation  within 15 minutes into D, but for me (as 
Modula/Oberon fragment) this is a challenge.
I guess that I will have a lot of more questions, (so be prepared <g>) 
For the moment I prefer to find out as much as I can by myself because 
this is my way to learn. However:
you wrote :
> If you mean just "are inner classes" legal, then yes.  In the way you
> show above, the class will belong to a given class instance/object.

Yes, I mean private inner classes - instead of the shown structs, but 
why should I declare them *static* ? I mean the inner classes should 
belong to the class-instance. Am I wrong ?

In case that you have time enough:  Here the /templated/ B+Tree Cpp 
implementation. 
http://idlebox.net/2007/stx-btree/stx-btree-0.8/include/stx/btree.h.html

Read it ? Do you see something not doable in D ?
again, thanks for beeing so gentle and patient
Bjoern

http://idlebox.net/2007/stx-btree/stx-btree-0.8/include/stx/btree.h.html


Chris Nicholson-Sauls schrieb:
> BLS wrote:
>> Hi :
>> it is about translating a C++ B+Tree algoritm into D.
>> Question No1 <g>
>> #include <algorithm>
>> #include <functional>
>> etc. and so on
>>
>> *The C++* source looks like :
>> template <typename _Key, typename _Data,
>>           typename _Value = std::pair<_Key, _Data>,
>>           typename _Compare = std::less<_Key>,
>>           typename _Traits = btree_default_map_traits<_Key, _Data>,
>>           bool _Duplicates = false>
>>
>> class bptree
>> {
>> public:
>>     typedef _Key                        key_type;
>>
>>   //etc, and so on
>>
>> private :
>>   struct node
>>   {
>>     //contains somethink like
>>     inline void initialize(const unsigned short l)
>>     {
>>       level = l;
>>       slotuse = 0;
>>     }
>>   struct inner_node : public node
>>   {
>>   }
>>
>>
>> }
>>
>>
>> *IN D*, I would like to use adaptor classes instead of structs -> 
>> struct inheritance
>>
>> class BplusTtree(_Key, _Data, and so on, bool _Duplicates=false)
>> {
>>   class node(){}
>>   // and
>>   class inner_node : node{}
>>
>> }
>>
>> Is this legal ?
> 
> If you mean just "are inner classes" legal, then yes.  In the way you 
> show above, the class will belong to a given class instance/object.  If 
> you prefix them with 'static' they will belong to the class (aka 
> template instance, in this case).
> 
> If you meant something else in particular... then I'm not sure what you 
> meant.  :)
> 
>> No2 :
>> The code contains std::pairs, (for key, value pairs)
>> What is the fasted (execution-speed) way to implement this in D ?
> 
> Associative array.  I'm not sure if there's any difference between AA's 
> in D/1.x versus D/2.x, so I'll link to both.
> http://digitalmars.com/d/1.0/arrays.html#associative
> http://digitalmars.com/d/arrays.html#associative
> 
>> No3 :
>> C++ *prepare_cast, static_cast* just cast(whatever) in D ?
> 
> Yes, just cast(whatever).
> 
>> Sorry for beeing so ignorant but I just have basic C++ knowhow, and I 
>> am  still learning about D templates. Many thanks in advance
>> Bjoern
>>
>>
>>
> 
> No apologies necessary.
> 
> -- Chris Nicholson-Sauls
July 26, 2007
Re: C++/ D C struct2 D inner classes, C++ templates/D templates
BLS wrote:
> Hi Chris,
> MANY THANKS.
> Your help is kicking me into the right direction.
> 

> In case that you have time enough:  Here the /templated/ B+Tree Cpp 
> implementation. 
> http://idlebox.net/2007/stx-btree/stx-btree-0.8/include/stx/btree.h.html
> 
> Read it ? Do you see something not doable in D ?
> again, thanks for beeing so gentle and patient
> Bjoern


The tricky thing, as with all STL-type C++, is translating the 
iterators.  The STL standard technique for iterators is to overload 
operator* and operator->, which you can't do in D.  So you need to use 
methods or something for those instead.  Something like iter.value or 
iter.deref or iter.data, etc.  Also there's a lot of passing of 
references here and there in STL code like that.  That's always kinda 
tricky to figure out what to do with.  Are you doing this with D2 or D 
classic?

One issue I ran into trying to translate std::map was the use of the 
idiom   T(val) or T x(val)  to construct objects.  In C++ that works 
fine whether T is an 'int', a class, or a struct.  But in D (AFAIK) 
there's no single expression that can be used to construct either a 
plain value type or a class type with the given initializer.  I didn't 
really think about it too hard though.  I decided it was easier to grab 
ArcLib's RedBlackTree implementation and use that.

--bb
July 27, 2007
Re: C++/ D C struct2 D inner classes, C++ templates/D templates
Bill Baxter schrieb:
> BLS wrote:
>> Hi Chris,
>> MANY THANKS.
>> Your help is kicking me into the right direction.
>>
> 
>> In case that you have time enough:  Here the /templated/ B+Tree Cpp 
>> implementation. 
>> http://idlebox.net/2007/stx-btree/stx-btree-0.8/include/stx/btree.h.html
>>
>> Read it ? Do you see something not doable in D ?
>> again, thanks for beeing so gentle and patient
>> Bjoern
> 
> 
> The tricky thing, as with all STL-type C++, is translating the 
> iterators.  The STL standard technique for iterators is to overload 
> operator* and operator->, which you can't do in D.  So you need to use 
> methods or something for those instead.  Something like iter.value or 
> iter.deref or iter.data, etc.  Also there's a lot of passing of 
> references here and there in STL code like that.  That's always kinda 
> tricky to figure out what to do with.  Are you doing this with D2 or D 
> classic?


D classic because TANGO.


> 
> One issue I ran into trying to translate std::map was the use of the 
> idiom   T(val) or T x(val)  to construct objects.  In C++ that works 
> fine whether T is an 'int', a class, or a struct.  But in D (AFAIK) 
> there's no single expression that can be used to construct either a 
> plain value type or a class type with the given initializer.  I didn't 
> really think about it too hard though.  I decided it was easier to grab 
> ArcLib's RedBlackTree implementation and use that.
> 
> --bb

Hi Bill, thanks for taking the time to answere.
first - OFF Topic
interesting that you name ArcLibs RB Tree. My Interest in B+Trees are, 
beside learning,  piece tables ... a (unknown?) data-structure which 
uses trees to hold text information often used in 
Text-processors/Management-Tools. /The workhorse in ABIWORD/. The funny 
part is that people behind ABI WORD  are switching from RB Trees to 
guess what : B+Trees, because of speed.  Further ArcLib has builtin 
support for FreeType .... So I wonder why not build something better 
than Scintilla using ArcLib ? [my never ending IDE proj.]

Some piece table info :

Both *NOT that good* :
http://www.cs.unm.edu/~crowley/papers/sds/node15.html#SECTION00064000000000000000
http://e98cuenc.free.fr/wordprocessor/piecetable.html


next :
perheps it is not nessesary to use std::map; 2 weeks ago I read in 
Dr.Dobs about Lisp like lists in C.
Hmmm difficult to say "Okay thats it" : because it is more a feeling but 
LISP Lists (implemented in C)  do not use _classic_ nodes just void* 
probabely this is a workaround. As said, more a feeling;

And prob. using D AAs as key/value pairs (thanks to Chris) like :
class X(_Key, _Val)
{
bla, bla

	_Key[_Val[]] key_val_pair;

is a workaround??? It is late now, I am afraid I produce too much 
bullshi* Next try tommorow

Bjoern
July 27, 2007
Re: C++/ D C struct2 D inner classes, C++ templates/D templates
BLS wrote:
> Bill Baxter schrieb:
>> BLS wrote:
>>> Hi Chris,
>>> MANY THANKS.
>>> Your help is kicking me into the right direction.
>>>
>>
>>> In case that you have time enough:  Here the /templated/ B+Tree Cpp 
>>> implementation. 
>>> http://idlebox.net/2007/stx-btree/stx-btree-0.8/include/stx/btree.h.html
>>>
>>> Read it ? Do you see something not doable in D ?
>>> again, thanks for beeing so gentle and patient
>>> Bjoern
>>
>>
>> The tricky thing, as with all STL-type C++, is translating the 
>> iterators.  The STL standard technique for iterators is to overload 
>> operator* and operator->, which you can't do in D.  So you need to use 
>> methods or something for those instead.  Something like iter.value or 
>> iter.deref or iter.data, etc.  Also there's a lot of passing of 
>> references here and there in STL code like that.  That's always kinda 
>> tricky to figure out what to do with.  Are you doing this with D2 or D 
>> classic?
> 
> 
> D classic because TANGO.
> 
> 
>>
>> One issue I ran into trying to translate std::map was the use of the 
>> idiom   T(val) or T x(val)  to construct objects.  In C++ that works 
>> fine whether T is an 'int', a class, or a struct.  But in D (AFAIK) 
>> there's no single expression that can be used to construct either a 
>> plain value type or a class type with the given initializer.  I didn't 
>> really think about it too hard though.  I decided it was easier to 
>> grab ArcLib's RedBlackTree implementation and use that.
>>
>> --bb
> 
> Hi Bill, thanks for taking the time to answere.
> first - OFF Topic
> interesting that you name ArcLibs RB Tree. My Interest in B+Trees are, 
> beside learning,  piece tables ... a (unknown?) data-structure which 
> uses trees to hold text information often used in 
> Text-processors/Management-Tools. /The workhorse in ABIWORD/. The funny 
> part is that people behind ABI WORD  are switching from RB Trees to 
> guess what : B+Trees, because of speed.  Further ArcLib has builtin 
> support for FreeType .... So I wonder why not build something better 
> than Scintilla using ArcLib ? [my never ending IDE proj.]
> 
> Some piece table info :
> 
> Both *NOT that good* :
> http://www.cs.unm.edu/~crowley/papers/sds/node15.html#SECTION00064000000000000000 
> 
> http://e98cuenc.free.fr/wordprocessor/piecetable.html

Well that's interesting, but if I were really worried about performance 
that much I'd probably be using Intel's C++ compiler and not D.  I don't 
expect I'll really be pushing up against any asymptotic ceilings with my 
current work.

> next :
> perheps it is not nessesary to use std::map; 2 weeks ago I read in 
> Dr.Dobs about Lisp like lists in C.
> Hmmm difficult to say "Okay thats it" : because it is more a feeling but 
> LISP Lists (implemented in C)  do not use _classic_ nodes just void* 
> probabely this is a workaround. As said, more a feeling;
> 
> And prob. using D AAs as key/value pairs (thanks to Chris) like :
> class X(_Key, _Val)
> {
> bla, bla
> 
>     _Key[_Val[]] key_val_pair;
> 
> is a workaround??? It is late now, I am afraid I produce too much 
> bullshi* Next try tommorow

If I follow you, yes, using AA's is a workaround if you want a Set type 
and you don't frequently need to access the elements in sorted order. 
But what I was actually after was a multiset, which isn't as trivial to 
implement with AA's, and is pretty easy to implement with an RBtree -- 
just make insert() unconditional pretty much.

But in the end actually I realized that the code I was porting was using 
a multiset for a very silly reason rather than the really slick reason I 
thought.  And it turned out just replacing the multiset with AA's was 
better.

(Incidentally, this is the code I was porting -- a triangle mesh 
datastructure in this library: 
http://www.multires.caltech.edu/software/CircleParam/html/index.html#download)

Sadly, in the end I've decided just to give up and use an existing C++ 
library instead.  Just can't justify spending all my time re-inventing 
wheels.  Sad but true fact of life in research. :-(

--bb
July 27, 2007
Re: C++/ D C struct2 D inner classes, C++ templates/D templates
> So I wonder why not build something better
> than Scintilla using ArcLib ? [my never ending IDE proj.]

Well, ArcLib isn't really aimed at building applications. The GUI subsystem,
while usable, is still rather rough around the edges and will, out of the
box, only support the widgets games usually require. Since it's based on
SDL + OpenGL, you won't get the native look and feel some other windowing
toolkits give you.

By the way, if one of you finds a bug in our RB-tree, please drop Clay or me
a line. Only recently (several months ago), we found a bug in our remove
function that occured only in very specific situations. Although I think
that the physics system serves as a relatively good testsuite, you can
never be certain there are no holes left.

Regards,
Christian
Top | Discussion index | About this forum | D home