www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - C++/ D C struct2 D inner classes, C++ templates/D templates

reply BLS <nanali nospam-wanadoo.fr> writes:
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
Jul 26 2007
parent reply Chris Nicholson-Sauls <ibisbasenji gmail.com> writes:
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
Jul 26 2007
parent reply BLS <nanali nospam-wanadoo.fr> writes:
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
Jul 26 2007
parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
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
Jul 26 2007
parent reply BLS <nanali nospam-wanadoo.fr> writes:
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
Jul 26 2007
next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
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#SECTION
0064000000000000000 
 
 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
Jul 26 2007
prev sibling parent Christian Kamm <kamm.incasoftware shift-at-left-and-remove-this.de> writes:
 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
Jul 27 2007