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