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

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

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

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

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

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

> 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