www.digitalmars.com         C & C++   DMDScript  

D - DTL Update [was Re: Some food for thought]

reply "Matthew" <matthew stlsoft.org> writes:
 What is the equivalent of Java's Vector in D?


The DTL's Vector!! :)

I've sent Walter the first pieces of the DTL, and am waiting for his
thoughts.

The current state is that we have several containers - Vector, Queue, Stack,
List (double) and Map - which are able to contain things, and do "normal"
operations for their kind:

    - subscripting and foreach for Vector
    - push, pop, top and foreach for Stack
    - push, pop, top and foreach for Queue
    - "subscript" operator, keys(), values(), containsKey(),
containsValue(), erase(), clear() and foreach for Map
    - push_front/back(), pop_front/back(), front(), back() and foreach for
List

[
    Note that the Map's foreach returns key&value pairs, which the built-in
assoc arrays do not, so we get to do this:

    Map!(int, int).Map    m;
    . . .
    foreach(map_t.pair_type p; m)
    {
        printf("[%d]: %d ", p.key, p.value);
    }

    I don't know about anyone else, but this is much more convenient for
most times I want to use a map. You can still enumerate just the values or
just the keys, by

    foreach(map_t.key_type k; m.keys)
    {
        printf("[%d] ", k);
    }

    foreach(map_t.value_type v; m.values)
    {
        printf("[]: %d ", v);
    }

]


There's also an IntRange, which I mentioned in a recent post will support a
relativelt succint syntax

    foreach(int i; new IntRange(-20, +20, 2))
    {
        . . .
    }

This'll be turned into a template soon so that it will work with any
integral type.

There are a couple more containers to do - SList and Set, and we'll also
take requests.

The next big thing is to work out how the Range concept - which I've been
working on in C++ with John Torjo - can be integrated over into the DTL, and
to work seamlessly with the built-in slicing. This is what I want to get
through with Walter before releasing. I've been fannying on about this for
some time, but I'll get it all done with big-W's foot up my arse pretty
soon, I'm sure. [Ranges is going to be a big feature in my next book -
"Extended STL" (mainly C++, but also D & .NET) - and I need to start on that
soonish.]

I'm interested to hear know whether people would like an early release as it
is now, since they're moderately well tested and usable within the available
interfaces described above, or wait for the full Monty is a couple of weeks'
time?

Cheers

Matthew
Mar 19 2004
next sibling parent "Phill" <phill pacific.net.au> writes:
"Matthew" <matthew stlsoft.org> wrote in message
news:c3gplm$1v69$1 digitaldaemon.com...

 What is the equivalent of Java's Vector in D?


 The DTL's Vector!! :)


Thats great!


 The next big thing is to work out how the Range concept - which I've been
 working on in C++ with John Torjo - can be integrated over into the DTL,


and

 to work seamlessly with the built-in slicing. This is what I want to get
 through with Walter before releasing. I've been fannying on about this for
 some time, but I'll get it all done with big-W's foot up my arse pretty
 soon, I'm sure.


LOL


 I'm interested to hear know whether people would like an early release as


it

 is now, since they're moderately well tested and usable within the


available

 interfaces described above, or wait for the full Monty is a couple of


weeks'

 time?


I'd be interested to get access to an early release.

Everything sounds great!

Phill.





 Cheers

 Matthew
Mar 19 2004
prev sibling next sibling parent reply Ant <duitoolkit yahoo.ca> writes:
On Sat, 20 Mar 2004 06:51:24 +0000, Matthew wrote:


 What is the equivalent of Java's Vector in D?


 
     Note that the Map's foreach returns key&value pairs, which the built-in
 assoc arrays do not, so we get to do this:
 

    Map!(int, int).Map    m;
    . . .
    foreach(map_t.pair_type p; m)
    {
        printf("[%d]: %d ", p.key, p.value);
    }


they do, no need for that.

	int[int] m;
	. . .	
	foreach(int key, int value ; m)
	{
		printf("[%d] %d\n", key, value);
	}


I fail to see the necessity of Map at all...

I'll wait to see.


    foreach(int i; new IntRange(-20, +20, 2))


    foreach(int i; Range!(int)(-20, +20, 2))

why is this better then:

     for(int i=-20; i<20 ; i+=2)



Ant
Mar 19 2004
next sibling parent reply "Matthew" <matthew stlsoft.org> writes:
"Ant" <duitoolkit yahoo.ca> wrote in message
news:pan.2004.03.20.07.35.36.332897 yahoo.ca...

 On Sat, 20 Mar 2004 06:51:24 +0000, Matthew wrote:


 What is the equivalent of Java's Vector in D?


     Note that the Map's foreach returns key&value pairs, which the




built-in

 assoc arrays do not, so we get to do this:


    Map!(int, int).Map    m;
    . . .
    foreach(map_t.pair_type p; m)
    {
        printf("[%d]: %d ", p.key, p.value);
    }


 they do, no need for that.

 int[int] m;
 . . .
 foreach(int key, int value ; m)
 {
 printf("[%d] %d\n", key, value);
 }


Since when? I remember have multiple debates with Walter to have this
feature, and they were rejected. Are you sure?


 I fail to see the necessity of Map at all...


If you're correct, then there is no need for Map.


 I'll wait to see.


    foreach(int i; new IntRange(-20, +20, 2))


     foreach(int i; Range!(int)(-20, +20, 2))

 why is this better then:

      for(int i=-20; i<20 ; i+=2)


Pure syntactic sugar in the case of int, but it's a unifying thing that
people want. It serves a genuine need, however, since it facilitates generic
programming for freachable entities and integral ranges.

I'm off to test your key/val assertion ...
Mar 19 2004
parent reply "Matthew" <matthew stlsoft.org> writes:
Well, you could knock me down with a feather!

You're quite right, and I can ditch Map. Shame I spend several hours on it.
:(

Walter and I had several exchanges on this during the time we were writing
the Dr Dobb's article. I must have missed the update.

Ho hum. Anyone got any more wild geese that need chasing?


"Matthew" <matthew stlsoft.org> wrote in message
news:c3gth8$25fs$1 digitaldaemon.com...

 "Ant" <duitoolkit yahoo.ca> wrote in message
 news:pan.2004.03.20.07.35.36.332897 yahoo.ca...

 On Sat, 20 Mar 2004 06:51:24 +0000, Matthew wrote:


 What is the equivalent of Java's Vector in D?


     Note that the Map's foreach returns key&value pairs, which the




 built-in

 assoc arrays do not, so we get to do this:


    Map!(int, int).Map    m;
    . . .
    foreach(map_t.pair_type p; m)
    {
        printf("[%d]: %d ", p.key, p.value);
    }


 they do, no need for that.

 int[int] m;
 . . .
 foreach(int key, int value ; m)
 {
 printf("[%d] %d\n", key, value);
 }


 Since when? I remember have multiple debates with Walter to have this
 feature, and they were rejected. Are you sure?


 I fail to see the necessity of Map at all...


 If you're correct, then there is no need for Map.


 I'll wait to see.


    foreach(int i; new IntRange(-20, +20, 2))


     foreach(int i; Range!(int)(-20, +20, 2))

 why is this better then:

      for(int i=-20; i<20 ; i+=2)


 Pure syntactic sugar in the case of int, but it's a unifying thing that
 people want. It serves a genuine need, however, since it facilitates


generic

 programming for freachable entities and integral ranges.

 I'm off to test your key/val assertion ...
Mar 20 2004
parent reply "Matthew" <matthew stlsoft.org> writes:
Nope. I've just checked, and I must be even more dense that was previously
suspected. Dr, heal thyself! :(

Apologies all round, not least of which to my finger joints for all that
unnecessary typing.


"Matthew" <matthew stlsoft.org> wrote in message
news:c3gtmi$2632$1 digitaldaemon.com...

 Well, you could knock me down with a feather!

 You're quite right, and I can ditch Map. Shame I spend several hours on


it.

 :(

 Walter and I had several exchanges on this during the time we were writing
 the Dr Dobb's article. I must have missed the update.

 Ho hum. Anyone got any more wild geese that need chasing?


 "Matthew" <matthew stlsoft.org> wrote in message
 news:c3gth8$25fs$1 digitaldaemon.com...

 "Ant" <duitoolkit yahoo.ca> wrote in message
 news:pan.2004.03.20.07.35.36.332897 yahoo.ca...

 On Sat, 20 Mar 2004 06:51:24 +0000, Matthew wrote:


 What is the equivalent of Java's Vector in D?


     Note that the Map's foreach returns key&value pairs, which the




 built-in

 assoc arrays do not, so we get to do this:


    Map!(int, int).Map    m;
    . . .
    foreach(map_t.pair_type p; m)
    {
        printf("[%d]: %d ", p.key, p.value);
    }


 they do, no need for that.

 int[int] m;
 . . .
 foreach(int key, int value ; m)
 {
 printf("[%d] %d\n", key, value);
 }


 Since when? I remember have multiple debates with Walter to have this
 feature, and they were rejected. Are you sure?


 I fail to see the necessity of Map at all...


 If you're correct, then there is no need for Map.


 I'll wait to see.


    foreach(int i; new IntRange(-20, +20, 2))


     foreach(int i; Range!(int)(-20, +20, 2))

 why is this better then:

      for(int i=-20; i<20 ; i+=2)


 Pure syntactic sugar in the case of int, but it's a unifying thing that
 people want. It serves a genuine need, however, since it facilitates


 generic

 programming for freachable entities and integral ranges.

 I'm off to test your key/val assertion ...
Mar 20 2004
parent reply "C. Sauls" <ibisbasenji yahoo.com> writes:
Hey don't worry about it, isn't that why we have this NG?  :)  Besides, 
you at least proved it can be done... good news to anybody who actually 
comes up with a need for a map-like object down the road.  Keep your 
code laying around somewhere.

Oh, and I wanna add my begging for the preview release.  :)

-C. Sauls
-Invironz
Mar 20 2004
parent "Matthew" <matthew stlsoft.org> writes:
"C. Sauls" <ibisbasenji yahoo.com> wrote in message
news:c3hk8r$boj$1 digitaldaemon.com...

 Hey don't worry about it, isn't that why we have this NG?  :)  Besides,
 you at least proved it can be done... good news to anybody who actually
 comes up with a need for a map-like object down the road.  Keep your
 code laying around somewhere.


Of course. It's in version control


 Oh, and I wanna add my begging for the preview release.  :)


As soon as I hear from big-W
Mar 20 2004
prev sibling parent reply "Pablo Aguilar" <paguilarg hotmail.com> writes:
I haven't done much D yet, but...
Aren't the typedefs like map_t.key_type and map_t.value_type good for
generic programming, instead of hardcoding types using the built in arrays?
Or can you figure them out in a template which takes the assoc array's type
as a parameter?


 What is the equivalent of Java's Vector in D?


     Note that the Map's foreach returns key&value pairs, which the




built-in

 assoc arrays do not, so we get to do this:


    Map!(int, int).Map    m;
    . . .
    foreach(map_t.pair_type p; m)
    {
        printf("[%d]: %d ", p.key, p.value);
    }


 they do, no need for that.

 int[int] m;
 . . .
 foreach(int key, int value ; m)
 {
 printf("[%d] %d\n", key, value);
 }


 I fail to see the necessity of Map at all...



 I'll wait to see.


    foreach(int i; new IntRange(-20, +20, 2))


     foreach(int i; Range!(int)(-20, +20, 2))

 why is this better then:

      for(int i=-20; i<20 ; i+=2)



 Ant
Mar 20 2004
parent reply "Matthew" <matthew stlsoft.org> writes:
 I haven't done much D yet, but...
 Aren't the typedefs like map_t.key_type and map_t.value_type good for
 generic programming, instead of hardcoding types using the built in


arrays?

Yes. All DTL containers will have an appropriate and complete set of member
types.


 Or can you figure them out in a template which takes the assoc array's


type

 as a parameter?


 What is the equivalent of Java's Vector in D?


     Note that the Map's foreach returns key&value pairs, which the




 built-in

 assoc arrays do not, so we get to do this:


    Map!(int, int).Map    m;
    . . .
    foreach(map_t.pair_type p; m)
    {
        printf("[%d]: %d ", p.key, p.value);
    }


 they do, no need for that.

 int[int] m;
 . . .
 foreach(int key, int value ; m)
 {
 printf("[%d] %d\n", key, value);
 }


 I fail to see the necessity of Map at all...



 I'll wait to see.


    foreach(int i; new IntRange(-20, +20, 2))


     foreach(int i; Range!(int)(-20, +20, 2))

 why is this better then:

      for(int i=-20; i<20 ; i+=2)



 Ant
Mar 21 2004
parent reply "Pablo Aguilar" <paguilarg hotmail.com> writes:
"Matthew" <matthew stlsoft.org> wrote in message
news:c3jqev$tbl$1 digitaldaemon.com...

 I haven't done much D yet, but...
 Aren't the typedefs like map_t.key_type and map_t.value_type good for
 generic programming, instead of hardcoding types using the built in


 arrays?

 Yes. All DTL containers will have an appropriate and complete set of


member

 types.


That's exactly my point, can the benefits of having those simple typedefs be
achieved with the built in assoc arrays?

My last post was very short-sighted, there's a whole lot more to C++'s STL
than just things doing what they're supposed to... I'll explain: you don't
rely on a map, just to use it's associative storing capabilities, you might
use it knowing that forward traversals give you the collection's items in
ascending order, or reverse iterating give's 'em to you in descending
order...

Also, there are complexity (time and space) guarantee's which you might want
to trade (making the storing policy a template, and have the map work with a
tree or hash map) which you can't do with the language's built in types, or
have it use a different sorting function, the list can go on!. How about
something like C++ map's insert(iterator, value) which guarantee's a certain
insertion time?

How would you do a vector's insert at a given point? Using slicing? If so,
wouldn't the sintactic commodity be worth writing the wrapper around built
in arrays?

And finally, if your so easily coninced that map was a blunder, why do Set
then? (that's if you're doing it) I saw a few weeks ago, someone using an
assoc array of elements to themselves (sorry for not remembering which post
it was, but it stored functions keyed by functions) which as far as I can
tell is pretty much a set...

My point is, don't be so easily discouraged just because something can
already be half-done.
Mar 22 2004
parent J Anderson <REMOVEanderson badmama.com.au> writes:
Pablo Aguilar wrote:


And finally, if your so easily coninced that map was a blunder, why do Set
then? (that's if you're doing it)


I don't think a set should be done in DTL.  It's basicly supported by 
assoative arrays.  What should be done (as stated before) is have 
supporting functions that can easily be improved (added to) as time goes on.

-- 
-Anderson: http://badmama.com.au/~anderson/
Mar 22 2004
prev sibling next sibling parent reply =?ISO-8859-1?Q?Sigbj=F8rn_Lund_Olsen?= <sigbjorn lundolsen.net> writes:
Matthew wrote:


 I'm interested to hear know whether people would like an early release as it
 is now, since they're moderately well tested and usable within the available
 interfaces described above, or wait for the full Monty is a couple of weeks'
 time?


Early release would be wonderful.

Cheers,
Sigbjørn Lund Olsen
Mar 20 2004
parent "Matthew" <matthew stlsoft.org> writes:
Ok. I just want to hear back from Walter on the current implementations, and
delete the Map one (LOL!), and then I'll do that.

The Range stuff that's in there so far is to be ignored, as it's likely to
change significantly. I shouldn't really affect anyone, as long as you don't
try to use it.

Cheers

Matthew

"Sigbjørn Lund Olsen" <sigbjorn lundolsen.net> wrote in message
news:c3h9k9$2tf9$1 digitaldaemon.com...

 Matthew wrote:


 I'm interested to hear know whether people would like an early release




as it

 is now, since they're moderately well tested and usable within the




available

 interfaces described above, or wait for the full Monty is a couple of




weeks'

 time?


 Early release would be wonderful.

 Cheers,
 Sigbjørn Lund Olsen
Mar 20 2004
prev sibling next sibling parent reply Ben Hinkle <bhinkle4 juno.com> writes:
On Sat, 20 Mar 2004 06:51:24 -0000, "Matthew" <matthew stlsoft.org>
wrote:


 What is the equivalent of Java's Vector in D?


The DTL's Vector!! :)


I should probably wait until DTL is more baked, but...
why have a Vector class when we have dynamic arrays
in D already? Unless there are really good reasons
to have one we should avoid making a Vector class.

I can imagine a couple of possible reasons for Vector:
1) Vector subclasses some abstract list class or
   interface
2) Vector would use iterator classes to be consistent
   with other classes in DTL

Without seeing DTL it's kindof hard to imagine
satisfying 1 and 2 with "pure" dynamic arrays but 
I really hope we don't just add a Vector class
because Java/C++ have one in their collections API.

-Ben
Mar 20 2004
next sibling parent reply "C. Sauls" <ibisbasenji yahoo.com> writes:
I think the idea is that Vector will somehow allow values of variable 
type, whereas arrays use fixed types.  Its also the one remaining reason 
I could see for a Map class, if Map could be a subsclass of Vector that 
uses variable typed keys.

-C. Sauls
-Invironz
Mar 20 2004
parent "Matthew" <matthew stlsoft.org> writes:
I'm not sure what you mean. Arrays can only contain monomorphic types by
value, but can contain polymorphic types by reference. Vector!() is the
same, partly because it's implemented in terms of the built-in arrays.

"C. Sauls" <ibisbasenji yahoo.com> wrote in message
news:c3hsn1$r04$1 digitaldaemon.com...

 I think the idea is that Vector will somehow allow values of variable
 type, whereas arrays use fixed types.  Its also the one remaining reason
 I could see for a Map class, if Map could be a subsclass of Vector that
 uses variable typed keys.

 -C. Sauls
 -Invironz
Mar 20 2004
prev sibling next sibling parent C <dont respond.com> writes:
Automatic resizing ?

C

On Sat, 20 Mar 2004 11:30:40 -0500, Ben Hinkle <bhinkle4 juno.com> wrote=
:


 On Sat, 20 Mar 2004 06:51:24 -0000, "Matthew" <matthew stlsoft.org>
 wrote:


 What is the equivalent of Java's Vector in D?


 The DTL's Vector!! :)


 I should probably wait until DTL is more baked, but...
 why have a Vector class when we have dynamic arrays
 in D already? Unless there are really good reasons
 to have one we should avoid making a Vector class.

 I can imagine a couple of possible reasons for Vector:
 1) Vector subclasses some abstract list class or
    interface
 2) Vector would use iterator classes to be consistent
    with other classes in DTL

 Without seeing DTL it's kindof hard to imagine
 satisfying 1 and 2 with "pure" dynamic arrays but
 I really hope we don't just add a Vector class
 because Java/C++ have one in their collections API.

 -Ben




-- =

D Newsgroup.
Mar 20 2004
prev sibling parent reply "Matthew" <matthew stlsoft.org> writes:
"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:ggro5099etn7cu5i6c3skaairgvi7u25ib 4ax.com...

 On Sat, 20 Mar 2004 06:51:24 -0000, "Matthew" <matthew stlsoft.org>
 wrote:


 What is the equivalent of Java's Vector in D?


The DTL's Vector!! :)


 I should probably wait until DTL is more baked, but...
 why have a Vector class when we have dynamic arrays
 in D already?


1. The length and capacity are clearly distinguished.
2. The containers will be bolt-ins (see
the other thread in which I talk about this "popular" technique), to allow
them to subclass abstract container interfaces, or abstract classes, or
whatever you want/think appropriate, so that they can work with more
flexible
inheritance-based/runtime-polymorphic code just as well as with more
efficient/type-safe generic code.
3. They will all work with Ranges. Alas this is all still well up in the
blue-skies as far as D goes. I've pretty much got it all worked out for C++,
along with John Torjo - I've been doing the concepts and the abstractions,
and John's been doing some mind bending things with filters. I *know* it
will
work for D because I worked it out on a bike ride a couple of weeks ago,
but I forgot it again before I could get to some paper, so it's a case of
arsing
around in code, or doing something else, until the code pixie comes by and
whispers it in my ear again. <G>

(Please don't be concerned if this sounds like the ravings of a madman: I
get the
majority of my ideas in this way, and they often tantalise me from afar for
days/weeks
before I can crystalise them onto paper.)


 Unless there are really good reasons
 to have one we should avoid making a Vector class.

 I can imagine a couple of possible reasons for Vector:
 1) Vector subclasses some abstract list class or
    interface


That will be possible, via the bolt-in mechanism


 2) Vector would use iterator classes to be consistent
    with other classes in DTL


DTL classes will all work with algorithms and built-in language features in
the form
of ranges/slices, rather than STL-like iterators.

FYI, I'm going to try and complete the C++ Ranges stuff (for STLSoft; JT's
doing a Boost version) before, so the concept's are clear, and then the D
Range
stuff should seem a lot clearer (if only because there'll be something
concrete and
proven to which people (including me) can refer).

But we should have no issue using the DTL stuff thus far without any concern
of Ranges, so I'll try and do the bolt-in stuff and post it shortly.


 Without seeing DTL it's kindof hard to imagine
 satisfying 1 and 2 with "pure" dynamic arrays but
 I really hope we don't just add a Vector class
 because Java/C++ have one in their collections API.


Not in the least.
Mar 20 2004
parent reply Ben Hinkle <bhinkle4 juno.com> writes:
On Sat, 20 Mar 2004 17:52:48 -0000, "Matthew" <matthew stlsoft.org>
wrote:


"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:ggro5099etn7cu5i6c3skaairgvi7u25ib 4ax.com...

 On Sat, 20 Mar 2004 06:51:24 -0000, "Matthew" <matthew stlsoft.org>
 wrote:


 What is the equivalent of Java's Vector in D?


The DTL's Vector!! :)


 I should probably wait until DTL is more baked, but...
 why have a Vector class when we have dynamic arrays
 in D already?


1. The length and capacity are clearly distinguished.


The capacity of dynamic arrays is a pretty hot topic and there
are several possible ways to support capacity without making
a Vector class.


2. The containers will be bolt-ins (see
the other thread in which I talk about this "popular" technique), to allow
them to subclass abstract container interfaces, or abstract classes, or
whatever you want/think appropriate, so that they can work with more
flexible
inheritance-based/runtime-polymorphic code just as well as with more
efficient/type-safe generic code.


I'm trying to dig up those posts but I'm having trouble 
finding them... oh well. I'll wait for DTL.


3. They will all work with Ranges. Alas this is all still well up in the
blue-skies as far as D goes. I've pretty much got it all worked out for C++,
along with John Torjo - I've been doing the concepts and the abstractions,
and John's been doing some mind bending things with filters. I *know* it
will
work for D because I worked it out on a bike ride a couple of weeks ago,
but I forgot it again before I could get to some paper, so it's a case of
arsing
around in code, or doing something else, until the code pixie comes by and
whispers it in my ear again. <G>

(Please don't be concerned if this sounds like the ravings of a madman: I
get the
majority of my ideas in this way, and they often tantalise me from afar for
days/weeks
before I can crystalise them onto paper.)


no problem. I know what you mean. I'll wait for more details.


 Unless there are really good reasons
 to have one we should avoid making a Vector class.

 I can imagine a couple of possible reasons for Vector:
 1) Vector subclasses some abstract list class or
    interface


That will be possible, via the bolt-in mechanism


 2) Vector would use iterator classes to be consistent
    with other classes in DTL


DTL classes will all work with algorithms and built-in language features in
the form of ranges/slices, rather than STL-like iterators.


cool!


FYI, I'm going to try and complete the C++ Ranges stuff (for STLSoft; JT's
doing a Boost version) before, so the concept's are clear, and then the D
Range stuff should seem a lot clearer (if only because there'll be something
concrete and proven to which people (including me) can refer).

But we should have no issue using the DTL stuff thus far without any concern
of Ranges, so I'll try and do the bolt-in stuff and post it shortly.


ok.


 Without seeing DTL it's kindof hard to imagine
 satisfying 1 and 2 with "pure" dynamic arrays but
 I really hope we don't just add a Vector class
 because Java/C++ have one in their collections API.


Not in the least.


yeah, I shouldn't have said "just because Java/C++ have
one"... It's natural to want to add one, just as it is
natural to want to add a String class of some sort. I really
hope we can keep 90% of D code using dynamic arrays - no 
offense to Vector but multiple ways to do very similar 
things is a pain in the butt when writing APIs.

-Ben
Mar 20 2004
next sibling parent reply "Walter" <walter digitalmars.com> writes:
"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:sknp50lk1tbov9fhefoiflqin8ihr6bpkd 4ax.com...

 yeah, I shouldn't have said "just because Java/C++ have
 one"... It's natural to want to add one, just as it is
 natural to want to add a String class of some sort. I really
 hope we can keep 90% of D code using dynamic arrays - no
 offense to Vector but multiple ways to do very similar
 things is a pain in the butt when writing APIs.


One point I tried to make in my sdwest talk was I just did not like having
arrays, Vectors, and Strings as separate types. They really should be the
same thing, and it was a significant design goal of D to make them the same
(i.e., add sufficient power to arrays).

You're right, though, that people coming from Java/C++ will look for a
String or Vector and initially wonder why it isn't there. I'd like the
collection classes in DTL to be more advanced things than what really ought
to be in the core language. I think we can show, using DTL, that D is more
expressive with far less code than C++ STL.

Anyone want to throw out ideas on collection types that would be cool in
DTL?
Mar 21 2004
next sibling parent reply "Matthew" <matthew stlsoft.org> writes:
"Walter" <walter digitalmars.com> wrote in message
news:c3jo7a$q25$1 digitaldaemon.com...

 "Ben Hinkle" <bhinkle4 juno.com> wrote in message
 news:sknp50lk1tbov9fhefoiflqin8ihr6bpkd 4ax.com...

 yeah, I shouldn't have said "just because Java/C++ have
 one"... It's natural to want to add one, just as it is
 natural to want to add a String class of some sort. I really
 hope we can keep 90% of D code using dynamic arrays - no
 offense to Vector but multiple ways to do very similar
 things is a pain in the butt when writing APIs.


 One point I tried to make in my sdwest talk was I just did not like having
 arrays, Vectors, and Strings as separate types. They really should be the
 same thing, and it was a significant design goal of D to make them the


same

 (i.e., add sufficient power to arrays).


It's nice if it can be done. I'm skeptical that it can be done and, even if
it can, whether that covers all the cases that will arise.

I've plenty of ideas for how to have these things built in. For example, a
queue could be denoted by

    int [<<] q_of_ints;

Some possibilities for the operations:

    //
    q_of_ints.is_empty; // is empty?
    q_of_ints.length;     // number of items in queue
    q_of_ints.capacity; // current capacity

    // PUSH
    q_of_ints << 10; // pushes one on
    q_of_ints ~= 10;
    q_of_ints.push(10);

    //TOP
    int top_value = q_of_ints[0]; // other indexes are banned.
    int top_value = q_of_ints; // uses implicit conversion
    int top_value = q_of_ints.top;

    // POP
    <<= q_of_ints; // I don't really like this, and imagine it'll cause
ambiguous parsing anyway
    q_of_ints.pop();

There are other ideas I've had for other types, stacks, lists etc.

But I think we make a serious mistake to throw the baby out with the C++
bathwater. There is enormous flexibility in the fact that things are in
libraries and not in language in C++. As I've said many times before, I'm
highly skeptical that all such flexibility is achievable in D in the
language. If that's true, then the last thing we want is to breed conflict
between the language and one or more libraries. It makes much more sense to
have things in libs to begin with if that's going to happen.

One example of this is the current Queue implementation. It uses a built-in
array, and does smart shuffling/resizing to prevent the array growing
indefinitely. Naturally, such a thing can become a policy to the template.
If this was a built-in, how would the user specify such policies, without us
having guts-out whitebox approach to the language constructs. We've achieved
this with foreach in a nice way, but opApply() is still a little bit
uncomfortably whitebox, especially given the use of ints for the loop
control return values.

What I think is a sensible approach is to go for the libraries-focused
approach first in DTL - though not doing things like my stupid Map blunder
where they're completely unneeded - and then consider what we want built
into the language. It's easier to change libraries than language, after all.


 You're right, though, that people coming from Java/C++ will look for a
 String or Vector and initially wonder why it isn't there. I'd like the
 collection classes in DTL to be more advanced things than what really


ought

 to be in the core language.


Agreed. There's also the fact that I believe we can support
Java-like/runtime flexibility and STL-like/compile-time flexibility in one
code base. I'm pretty confident that that is not achievable in language.


 I think we can show, using DTL, that D is more
 expressive with far less code than C++ STL.


That's the intention (and one of the main motivations).


 Anyone want to throw out ideas on collection types that would be cool in
 DTL?


Please do.
Mar 21 2004
next sibling parent reply "Matthew" <matthew stlsoft.org> writes:
More:

int [] array_of_ints;
int [<<] queue_of_ints;    // The chevron denotes that things go in one
direction
int[<>] stack_of_ints;       //  the <> denotes in one way, out the other. I
also thought of [|<], and [|<>]
int<-> slist_of_ints;        // Singly-linked list
int<<->> dlist_of_ints;    // Doubly-linked list

I confess that I'm only really enamoured of the queue one. Better
suggestions would be good for the other types, if they did indeed get into
the language, rather than stay in libraries (as I think they should).

"Matthew" <matthew stlsoft.org> wrote in message
news:c3jpr6$sg2$1 digitaldaemon.com...

 "Walter" <walter digitalmars.com> wrote in message
 news:c3jo7a$q25$1 digitaldaemon.com...

 "Ben Hinkle" <bhinkle4 juno.com> wrote in message
 news:sknp50lk1tbov9fhefoiflqin8ihr6bpkd 4ax.com...

 yeah, I shouldn't have said "just because Java/C++ have
 one"... It's natural to want to add one, just as it is
 natural to want to add a String class of some sort. I really
 hope we can keep 90% of D code using dynamic arrays - no
 offense to Vector but multiple ways to do very similar
 things is a pain in the butt when writing APIs.


 One point I tried to make in my sdwest talk was I just did not like




having

 arrays, Vectors, and Strings as separate types. They really should be




the

 same thing, and it was a significant design goal of D to make them the


 same

 (i.e., add sufficient power to arrays).


 It's nice if it can be done. I'm skeptical that it can be done and, even


if

 it can, whether that covers all the cases that will arise.

 I've plenty of ideas for how to have these things built in. For example, a
 queue could be denoted by

     int [<<] q_of_ints;

 Some possibilities for the operations:

     //
     q_of_ints.is_empty; // is empty?
     q_of_ints.length;     // number of items in queue
     q_of_ints.capacity; // current capacity

     // PUSH
     q_of_ints << 10; // pushes one on
     q_of_ints ~= 10;
     q_of_ints.push(10);

     //TOP
     int top_value = q_of_ints[0]; // other indexes are banned.
     int top_value = q_of_ints; // uses implicit conversion
     int top_value = q_of_ints.top;

     // POP
     <<= q_of_ints; // I don't really like this, and imagine it'll cause
 ambiguous parsing anyway
     q_of_ints.pop();

 There are other ideas I've had for other types, stacks, lists etc.

 But I think we make a serious mistake to throw the baby out with the C++
 bathwater. There is enormous flexibility in the fact that things are in
 libraries and not in language in C++. As I've said many times before, I'm
 highly skeptical that all such flexibility is achievable in D in the
 language. If that's true, then the last thing we want is to breed conflict
 between the language and one or more libraries. It makes much more sense


to

 have things in libs to begin with if that's going to happen.

 One example of this is the current Queue implementation. It uses a


built-in

 array, and does smart shuffling/resizing to prevent the array growing
 indefinitely. Naturally, such a thing can become a policy to the template.
 If this was a built-in, how would the user specify such policies, without


us

 having guts-out whitebox approach to the language constructs. We've


achieved

 this with foreach in a nice way, but opApply() is still a little bit
 uncomfortably whitebox, especially given the use of ints for the loop
 control return values.

 What I think is a sensible approach is to go for the libraries-focused
 approach first in DTL - though not doing things like my stupid Map blunder
 where they're completely unneeded - and then consider what we want built
 into the language. It's easier to change libraries than language, after


all.

 You're right, though, that people coming from Java/C++ will look for a
 String or Vector and initially wonder why it isn't there. I'd like the
 collection classes in DTL to be more advanced things than what really


 ought

 to be in the core language.


 Agreed. There's also the fact that I believe we can support
 Java-like/runtime flexibility and STL-like/compile-time flexibility in one
 code base. I'm pretty confident that that is not achievable in language.


 I think we can show, using DTL, that D is more
 expressive with far less code than C++ STL.


 That's the intention (and one of the main motivations).


 Anyone want to throw out ideas on collection types that would be cool in
 DTL?


 Please do.
Mar 21 2004
next sibling parent reply "Walter" <walter digitalmars.com> writes:
"Matthew" <matthew stlsoft.org> wrote in message
news:c3jq8m$t2q$2 digitaldaemon.com...

 More:

 int [] array_of_ints;
 int [<<] queue_of_ints;    // The chevron denotes that things go in one
 direction
 int[<>] stack_of_ints;       //  the <> denotes in one way, out the other.


I

 also thought of [|<], and [|<>]
 int<-> slist_of_ints;        // Singly-linked list
 int<<->> dlist_of_ints;    // Doubly-linked list

 I confess that I'm only really enamoured of the queue one. Better
 suggestions would be good for the other types, if they did indeed get into
 the language, rather than stay in libraries (as I think they should).


Should we invent new tokens for these unless there are generally accepted
symbols for them?
Mar 21 2004
parent "Matthew" <matthew stlsoft.org> writes:
"Walter" <walter digitalmars.com> wrote in message
news:c3kmnl$2afo$2 digitaldaemon.com...

 "Matthew" <matthew stlsoft.org> wrote in message
 news:c3jq8m$t2q$2 digitaldaemon.com...

 More:

 int [] array_of_ints;
 int [<<] queue_of_ints;    // The chevron denotes that things go in one
 direction
 int[<>] stack_of_ints;       //  the <> denotes in one way, out the




other.

 I

 also thought of [|<], and [|<>]
 int<-> slist_of_ints;        // Singly-linked list
 int<<->> dlist_of_ints;    // Doubly-linked list

 I confess that I'm only really enamoured of the queue one. Better
 suggestions would be good for the other types, if they did indeed get




into

 the language, rather than stay in libraries (as I think they should).


 Should we invent new tokens for these unless there are generally accepted
 symbols for them?


Sorry, mate. I think I'm suffering NG overload (and I'm sure the rest of you
are, of me!). I don't understand the question
Mar 21 2004
prev sibling parent John Reimer <jjreimer telus.net> writes:
Matthew wrote:


 More:
 
 int [] array_of_ints;
 int [<<] queue_of_ints;    // The chevron denotes that things go in one
 direction
 int[<>] stack_of_ints;       //  the <> denotes in one way, out the other.
 I also thought of [|<], and [|<>]
 int<-> slist_of_ints;        // Singly-linked list
 int<<->> dlist_of_ints;    // Doubly-linked list
 
 I confess that I'm only really enamoured of the queue one. Better
 suggestions would be good for the other types, if they did indeed get into
 the language, rather than stay in libraries (as I think they should).


These are pretty nifty looking ideas.  I hope they can be implemented is
some form in the future.
Mar 21 2004
prev sibling parent J Anderson <REMOVEanderson badmama.com.au> writes:
Matthew wrote:


"Walter" <walter digitalmars.com> wrote in message
news:c3jo7a$q25$1 digitaldaemon.com...
  


"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:sknp50lk1tbov9fhefoiflqin8ihr6bpkd 4ax.com...
    


yeah, I shouldn't have said "just because Java/C++ have
one"... It's natural to want to add one, just as it is
natural to want to add a String class of some sort. I really
hope we can keep 90% of D code using dynamic arrays - no
offense to Vector but multiple ways to do very similar
things is a pain in the butt when writing APIs.
      


One point I tried to make in my sdwest talk was I just did not like having
arrays, Vectors, and Strings as separate types. They really should be the
same thing, and it was a significant design goal of D to make them the
    


same
  


(i.e., add sufficient power to arrays).
    


It's nice if it can be done. I'm skeptical that it can be done and, even if
it can, whether that covers all the cases that will arise.

I've plenty of ideas for how to have these things built in. For example, a
queue could be denoted by

    int [<<] q_of_ints;

Some possibilities for the operations:

    //
    q_of_ints.is_empty; // is empty?
    q_of_ints.length;     // number of items in queue
    q_of_ints.capacity; // current capacity

    // PUSH
    q_of_ints << 10; // pushes one on
    q_of_ints ~= 10;
  


I think the ~= is nice for push because its the same as for arrays.  It 
would be nice if arrays had a append to front as well but then I guess 
that would be very inefficient.  Parhaps if the memory before is free (I 
guess would be rare) then D could simply slide the pointer back one.  
What the symbol should be?   I can't think of anything that looks good.

:: //is used in some functional languages such as scheme

so parhaps
:=
or
::=

-- 
-Anderson: http://badmama.com.au/~anderson/
Mar 24 2004
prev sibling next sibling parent reply =?ISO-8859-1?Q?Sigbj=F8rn_Lund_Olsen?= <sigbjorn lundolsen.net> writes:
Walter wrote:


 "Ben Hinkle" <bhinkle4 juno.com> wrote in message
 news:sknp50lk1tbov9fhefoiflqin8ihr6bpkd 4ax.com...
 

yeah, I shouldn't have said "just because Java/C++ have
one"... It's natural to want to add one, just as it is
natural to want to add a String class of some sort. I really
hope we can keep 90% of D code using dynamic arrays - no
offense to Vector but multiple ways to do very similar
things is a pain in the butt when writing APIs.


 
 
 One point I tried to make in my sdwest talk was I just did not like having
 arrays, Vectors, and Strings as separate types. They really should be the
 same thing, and it was a significant design goal of D to make them the same
 (i.e., add sufficient power to arrays).
 
 You're right, though, that people coming from Java/C++ will look for a
 String or Vector and initially wonder why it isn't there. I'd like the
 collection classes in DTL to be more advanced things than what really ought
 to be in the core language. I think we can show, using DTL, that D is more
 expressive with far less code than C++ STL.
 
 Anyone want to throw out ideas on collection types that would be cool in
 DTL?


Deque.

Cheers,
Sigbjørn Lund Olsen
Mar 21 2004
parent reply "Matthew" <matthew stlsoft.org> writes:
"Sigbjørn Lund Olsen" <sigbjorn lundolsen.net> wrote in message
news:c3jqq0$ts7$1 digitaldaemon.com...

 Walter wrote:


 "Ben Hinkle" <bhinkle4 juno.com> wrote in message
 news:sknp50lk1tbov9fhefoiflqin8ihr6bpkd 4ax.com...


yeah, I shouldn't have said "just because Java/C++ have
one"... It's natural to want to add one, just as it is
natural to want to add a String class of some sort. I really
hope we can keep 90% of D code using dynamic arrays - no
offense to Vector but multiple ways to do very similar
things is a pain in the butt when writing APIs.



 One point I tried to make in my sdwest talk was I just did not like




having

 arrays, Vectors, and Strings as separate types. They really should be




the

 same thing, and it was a significant design goal of D to make them the




same

 (i.e., add sufficient power to arrays).

 You're right, though, that people coming from Java/C++ will look for a
 String or Vector and initially wonder why it isn't there. I'd like the
 collection classes in DTL to be more advanced things than what really




ought

 to be in the core language. I think we can show, using DTL, that D is




more

 expressive with far less code than C++ STL.

 Anyone want to throw out ideas on collection types that would be cool in
 DTL?


 Deque.


Already covered in List, since it has push_front/back, front/back,
pop_front/back
Mar 21 2004
next sibling parent reply =?ISO-8859-1?Q?Sigbj=F8rn_Lund_Olsen?= <sigbjorn lundolsen.net> writes:
Matthew wrote:

 "Sigbjørn Lund Olsen" <sigbjorn lundolsen.net> wrote in message
 news:c3jqq0$ts7$1 digitaldaemon.com...
 

Walter wrote:



"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:sknp50lk1tbov9fhefoiflqin8ihr6bpkd 4ax.com...



yeah, I shouldn't have said "just because Java/C++ have
one"... It's natural to want to add one, just as it is
natural to want to add a String class of some sort. I really
hope we can keep 90% of D code using dynamic arrays - no
offense to Vector but multiple ways to do very similar
things is a pain in the butt when writing APIs.



One point I tried to make in my sdwest talk was I just did not like




 
 having
 

arrays, Vectors, and Strings as separate types. They really should be




 
 the
 

same thing, and it was a significant design goal of D to make them the




 
 same
 

(i.e., add sufficient power to arrays).

You're right, though, that people coming from Java/C++ will look for a
String or Vector and initially wonder why it isn't there. I'd like the
collection classes in DTL to be more advanced things than what really




 
 ought
 

to be in the core language. I think we can show, using DTL, that D is




 
 more
 

expressive with far less code than C++ STL.

Anyone want to throw out ideas on collection types that would be cool in
DTL?


Deque.


 
 
 Already covered in List, since it has push_front/back, front/back,
 pop_front/back


Wonderful :-)

(Now you go release this)

Cheers,
Sigbjørn Lund Olsen
Mar 21 2004
parent "Matthew" <matthew stlsoft.org> writes:
"Sigbjørn Lund Olsen" <sigbjorn lundolsen.net> wrote in message
news:c3jvmd$14je$1 digitaldaemon.com...

 Matthew wrote:

 "Sigbjørn Lund Olsen" <sigbjorn lundolsen.net> wrote in message
 news:c3jqq0$ts7$1 digitaldaemon.com...


Walter wrote:



"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:sknp50lk1tbov9fhefoiflqin8ihr6bpkd 4ax.com...



yeah, I shouldn't have said "just because Java/C++ have
one"... It's natural to want to add one, just as it is
natural to want to add a String class of some sort. I really
hope we can keep 90% of D code using dynamic arrays - no
offense to Vector but multiple ways to do very similar
things is a pain in the butt when writing APIs.



One point I tried to make in my sdwest talk was I just did not like




 having


arrays, Vectors, and Strings as separate types. They really should be




 the


same thing, and it was a significant design goal of D to make them the




 same


(i.e., add sufficient power to arrays).

You're right, though, that people coming from Java/C++ will look for a
String or Vector and initially wonder why it isn't there. I'd like the
collection classes in DTL to be more advanced things than what really




 ought


to be in the core language. I think we can show, using DTL, that D is




 more


expressive with far less code than C++ STL.

Anyone want to throw out ideas on collection types that would be cool








in

DTL?


Deque.



 Already covered in List, since it has push_front/back, front/back,
 pop_front/back


 Wonderful :-)

 (Now you go release this)


It is a matter of a couple of days or so. No more. Walter's got the latest
batch, but he's also got several new libs from me that've been waiting to go
in for ages to contend with first.  I didn't want to release it before I'd
done all the Range stuff, but now I think it's better to just get it out
there, so it will be done in the next few days, I promise.

FYI: I've to deliver the final modifications on "Imperfect C++" tomorrow (US
time), and have been faffing around on the evil Chapter 13 for days. When I
was a student, I'd do almost anything before doing an assignment, even
ironing clothes, so now I call this process "doing the ironing". These days,
when I'm doing the ironing, it's usually on one of my more enjoyable
projects, such as working on a CUJ column, or STLSoft, or DTL, or learning
Ruby, or whatever.

The last few days' ironing have been the DTL, but now I've got about 32 hrs
to go, it's panic stations, and so I am doing nothing but Ch 13 from now
until it's done. But fear not, once Monday's gone, I'll be back to spreading
myself around several things, and DTL is high on the list.

Matthew
Mar 21 2004
prev sibling parent Chris Paulson-Ellis <chris edesix.com> writes:
Matthew wrote:

Anyone want to throw out ideas on collection types that would be cool in
DTL?


Deque.


 
 Already covered in List, since it has push_front/back, front/back,
 pop_front/back


I'd like deque implemented with linked arrays, like C++ std::dequeue<>. 
It has significantly faster performance than a list for random access 
and than an array for insertion/removal. Less importantly, they are more 
compact than lists.

Chris.
Mar 22 2004
prev sibling next sibling parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
Walter wrote:


"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:sknp50lk1tbov9fhefoiflqin8ihr6bpkd 4ax.com...
  


yeah, I shouldn't have said "just because Java/C++ have
one"... It's natural to want to add one, just as it is
natural to want to add a String class of some sort. I really
hope we can keep 90% of D code using dynamic arrays - no
offense to Vector but multiple ways to do very similar
things is a pain in the butt when writing APIs.
    


One point I tried to make in my sdwest talk was I just did not like having
arrays, Vectors, and Strings as separate types. They really should be the
same thing, and it was a significant design goal of D to make them the same
(i.e., add sufficient power to arrays).

You're right, though, that people coming from Java/C++ will look for a
String or Vector and initially wonder why it isn't there. I'd like the
collection classes in DTL to be more advanced things than what really ought
to be in the core language. I think we can show, using DTL, that D is more
expressive with far less code than C++ STL.

Anyone want to throw out ideas on collection types that would be cool in
DTL?


  


Although D has many of the basic types in STL I think that not all 
possible uses will be though of in the language.  I think each type of 
collection needs a group of supporting functions in the STL under some 
standardised namespaces (so they are easy to find).  That is probably 
obvious.

As far as collections go, what about different types of algorithms for 
different applications?  Surely the one-shoe-fits-all approach does not 
work for things like maps/associative arrays.  Users often wish to have 
a choice about what type of sort they use.  Of course you don't want to 
go overboard here either.  Parhaps a way of hinting what type of 
algorithm you want to use and if it is not there STL would use the next 
best thing.


-- 
-Anderson: http://badmama.com.au/~anderson/
Mar 21 2004
parent reply Ben Hinkle <bhinkle4 juno.com> writes:
Anyone want to throw out ideas on collection types that would be cool in
DTL?


Although D has many of the basic types in STL I think that not all 
possible uses will be though of in the language.  I think each type of 
collection needs a group of supporting functions in the STL under some 
standardised namespaces (so they are easy to find).  That is probably 
obvious.


I agree if you mean DTL should contain supporting functions for
dynamic arrays and associative arrays instead of writing Vector
and Map classes. Plus it should contain more "esoteric" containers
like deque and linked lists (double and possibly single linked)
and sets, multiset and multimaps.
Ranges would be nice to throw in because they help with array
manipulation.



As far as collections go, what about different types of algorithms for 
different applications?  Surely the one-shoe-fits-all approach does not 
work for things like maps/associative arrays.  Users often wish to have 
a choice about what type of sort they use.  Of course you don't want to 
go overboard here either.  Parhaps a way of hinting what type of 
algorithm you want to use and if it is not there STL would use the next 
best thing.


seems reasonable. I remember custom sort algorithms for associative
arrays coming up before.
Mar 21 2004
parent J Anderson <REMOVEanderson badmama.com.au> writes:
Ben Hinkle wrote:


Anyone want to throw out ideas on collection types that would be cool in
DTL?
      


Although D has many of the basic types in STL I think that not all 
possible uses will be though of in the language.  I think each type of 
collection needs a group of supporting functions in the STL under some 
standardised namespaces (so they are easy to find).  That is probably 
obvious.
    


I agree if you mean DTL should contain supporting functions for
dynamic arrays and associative arrays instead of writing Vector
and Map classes. 


Exactly but with a name convention that everyone can follow.


Plus it should contain more "esoteric" containers
like deque and linked lists (double and possibly single linked)
and sets, multiset and multimaps.
Ranges would be nice to throw in because they help with array
manipulation.
  


Single linked lists are one thing I miss in C++ and end up creating 
myself.  Please have single linked lists.


As far as collections go, what about different types of algorithms for 
different applications?  Surely the one-shoe-fits-all approach does not 
work for things like maps/associative arrays.  Users often wish to have 
a choice about what type of sort they use.  Of course you don't want to 
go overboard here either.  Parhaps a way of hinting what type of 
algorithm you want to use and if it is not there STL would use the next 
best thing.
    


seems reasonable. I remember custom sort algorithms for associative
arrays coming up before.


Personally with collections I would like a form with as little overhead 
as possible.   For example, in C++ to access a vector's element there 
are always two or three checks just to do that.  I found that it was 
much faster to extract the array first before access many elements (of 
course that assumes knowledge that the size does not change).  Also, 
IMHO exceptions should be used sparingly, only on algorithms that are 
more then a few lines (of processing).  Contracts should be used in the 
main as these can be removed from the release.

-- 
-Anderson: http://badmama.com.au/~anderson/
Mar 22 2004
prev sibling next sibling parent Patrick Down <pat codemoon.com> writes:
"Walter" <walter digitalmars.com> wrote in
news:c3jo7a$q25$1 digitaldaemon.com: 


 Anyone want to throw out ideas on collection types that would be cool
 in DTL?


Priority Queue
Mar 21 2004
prev sibling next sibling parent reply resistor mac.com writes:
In article <c3jo7a$q25$1 digitaldaemon.com>, Walter says...

Anyone want to throw out ideas on collection types that would be cool in
DTL?


I did some work on one point on a templated set of Tree classes.  The classes
themselves provided most of the common trees, but it was also meant to be
extensible with new tree types.  It went something like this:

Node(T) - holds an array of other Node(T)'s.  Used to implement webs where all
objects are peers

HierNode(T):Node(T) - holds two arrays of Node(T)'s, one parents array and one
children array.

TreeNode(T):HierNode(T) - a HierNode(T) with the parent array enforced to hold
only one Node(T).

BinaryTreeNode(T):TreeNode(T) - a TreeNode(T) with only two elements in the
children array.  Could be subclassed to make self-balancing trees, etc.

By polymorphism it would be possible to create some very complicated and yet
potentially very useful structures out of them, and the layers of abstraction
would make it pretty easy to add more specific functionalities (self-balancing,
ternary trees, etc.)

Just my idea thought.

Owen Anderson
Mar 21 2004
parent reply "Matthew" <matthew stlsoft.org> writes:
I'm not sure I'm at a point where I can digest all that <g>, but please do
keep it all in mind, and in a few days take a look at DTL and let us know if
there's some congruence. Hopefully we can slide in all these good ideas.

<resistor mac.com> wrote in message news:c3kmue$2aqg$1 digitaldaemon.com...

 In article <c3jo7a$q25$1 digitaldaemon.com>, Walter says...

Anyone want to throw out ideas on collection types that would be cool in
DTL?


 I did some work on one point on a templated set of Tree classes.  The


classes

 themselves provided most of the common trees, but it was also meant to be
 extensible with new tree types.  It went something like this:

 Node(T) - holds an array of other Node(T)'s.  Used to implement webs where


all

 objects are peers

 HierNode(T):Node(T) - holds two arrays of Node(T)'s, one parents array and


one

 children array.

 TreeNode(T):HierNode(T) - a HierNode(T) with the parent array enforced to


hold

 only one Node(T).

 BinaryTreeNode(T):TreeNode(T) - a TreeNode(T) with only two elements in


the

 children array.  Could be subclassed to make self-balancing trees, etc.

 By polymorphism it would be possible to create some very complicated and


yet

 potentially very useful structures out of them, and the layers of


abstraction

 would make it pretty easy to add more specific functionalities


(self-balancing,

 ternary trees, etc.)

 Just my idea thought.

 Owen Anderson
Mar 21 2004
parent resistor mac.com writes:
It's basically just a way of having templated tree classes, but leaving the
hierarchy open enough that it would be feasible to add new tree variants with
the absolute minimum of effort.  I'm a big supporter of class hierarchies so the
functionality can be divided into clear levels.  In my imaginary tree hierarchy,
it might go something like this:

Container -> Node -> HierNode -> TreeNode -> BinaryTreeNode -> RedBlackTreeNode

Each class implements as little as possible, but by the time you reach something
as far down the chain as RedBlackTreeNode you've got significantly useful stuff.
Also, like I said, having lots of layers makes it easier for someone writing a
custom class to find exactly the right thing to inherit from without having to
inherit unwanted functionality.

Owen

In article <c3kn3d$2b2u$1 digitaldaemon.com>, Matthew says...

I'm not sure I'm at a point where I can digest all that <g>, but please do
keep it all in mind, and in a few days take a look at DTL and let us know if
there's some congruence. Hopefully we can slide in all these good ideas.

<resistor mac.com> wrote in message news:c3kmue$2aqg$1 digitaldaemon.com...

 In article <c3jo7a$q25$1 digitaldaemon.com>, Walter says...

Anyone want to throw out ideas on collection types that would be cool in
DTL?


 I did some work on one point on a templated set of Tree classes.  The


classes

 themselves provided most of the common trees, but it was also meant to be
 extensible with new tree types.  It went something like this:

 Node(T) - holds an array of other Node(T)'s.  Used to implement webs where


all

 objects are peers

 HierNode(T):Node(T) - holds two arrays of Node(T)'s, one parents array and


one

 children array.

 TreeNode(T):HierNode(T) - a HierNode(T) with the parent array enforced to


hold

 only one Node(T).

 BinaryTreeNode(T):TreeNode(T) - a TreeNode(T) with only two elements in


the

 children array.  Could be subclassed to make self-balancing trees, etc.

 By polymorphism it would be possible to create some very complicated and


yet

 potentially very useful structures out of them, and the layers of


abstraction

 would make it pretty easy to add more specific functionalities


(self-balancing,

 ternary trees, etc.)

 Just my idea thought.

 Owen Anderson
Mar 21 2004
prev sibling parent reply Chris Paulson-Ellis <chris edesix.com> writes:
Walter wrote:

 Anyone want to throw out ideas on collection types that would be cool in
 DTL?


I just measured my usage of the C++ containers in some recent projects...

35% vector
27% list
15% map
14% set
  6% multimap

Interestingly, the more recent projects use vector<> & list<> less and 
set<> & multimap<> more. I guess this comes from realising that more 
things are associative then a crusty old C programmer is at first 
prepared to admit.

I'd like tree *and* hash implementations of the associative containers. 
It is annoying that C++ doesn't yet provide any hash containers (outside 
boost) and that other languages use them for everything. Choice please!

Call a spade a spade, please. multimap<> should be treemap<> (though 
redblacktreemap<> is going too far). The worst is multiset<>, which 
should be called bag<> (or treebag<> & hashbag<>). My pet gripe is that 
D "associative arrays" are called arrays at all. They are hashmaps, not 
arrays, right?

Chris.
Mar 22 2004
parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
Chris Paulson-Ellis wrote:


 I'd like tree *and* hash implementations of the associative 
 containers. It is annoying that C++ doesn't yet provide any hash 
 containers (outside boost) and that other languages use them for 
 everything. Choice please!


Hu? I assume your talking about stl. What about hash_map?


 Chris.



-- 
-Anderson: http://badmama.com.au/~anderson/
Mar 22 2004
next sibling parent C <dont respond.com> writes:
 Hu? I assume your talking about stl. What about hash_map?


I think thats 'unofficial' , depends on the implementation.  I don't thi=
nk =

that ever actually made into the standard ( though it seems most STL's =

still include it ).

( from other post )


 Personally with collections I would like a form with as little overhea=


d =


 as possible.


I agree , and yes (single and double )link list too please!  Sorry did I=
 =

miss a release date on DTL ?

Thanks,
Charles


On Mon, 22 Mar 2004 23:01:39 +0800, J Anderson =

<REMOVEanderson badmama.com.au> wrote:


 Chris Paulson-Ellis wrote:


 I'd like tree *and* hash implementations of the associative container=




s. =


 It is annoying that C++ doesn't yet provide any hash containers =





 (outside boost) and that other languages use them for everything. =





 Choice please!


 Hu? I assume your talking about stl. What about hash_map?


 Chris.






-- =

D Newsgroup.
Mar 22 2004
prev sibling parent reply Chris Paulson-Ellis <chris edesix.com> writes:
J Anderson wrote:

 Hu? I assume your talking about stl. What about hash_map?


It never made it into the C++ standard library - apparently the 
proposals for inclusion came too late.
Mar 22 2004
parent J Anderson <REMOVEanderson badmama.com.au> writes:
Chris Paulson-Ellis wrote:


 J Anderson wrote:


 Hu? I assume your talking about stl. What about hash_map?



 It never made it into the C++ standard library - apparently the 
 proposals for inclusion came too late.


Oh, as C said many stl versions come with it.

-- 
-Anderson: http://badmama.com.au/~anderson/
Mar 22 2004
prev sibling parent "Matthew" <matthew stlsoft.org> writes:
"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:sknp50lk1tbov9fhefoiflqin8ihr6bpkd 4ax.com...

 On Sat, 20 Mar 2004 17:52:48 -0000, "Matthew" <matthew stlsoft.org>
 wrote:


"Ben Hinkle" <bhinkle4 juno.com> wrote in message
news:ggro5099etn7cu5i6c3skaairgvi7u25ib 4ax.com...

 On Sat, 20 Mar 2004 06:51:24 -0000, "Matthew" <matthew stlsoft.org>
 wrote:


 What is the equivalent of Java's Vector in D?


The DTL's Vector!! :)


 I should probably wait until DTL is more baked, but...
 why have a Vector class when we have dynamic arrays
 in D already?


1. The length and capacity are clearly distinguished.


 The capacity of dynamic arrays is a pretty hot topic and there
 are several possible ways to support capacity without making
 a Vector class.


I'm a pragmatist, so took this opportunity to address it here, rather than
wait - potentially for ever - for a resolution in the built-ins.


2. The containers will be bolt-ins (see
the other thread in which I talk about this "popular" technique), to




allow

them to subclass abstract container interfaces, or abstract classes, or
whatever you want/think appropriate, so that they can work with more
flexible
inheritance-based/runtime-polymorphic code just as well as with more
efficient/type-safe generic code.


 I'm trying to dig up those posts but I'm having trouble
 finding them... oh well. I'll wait for DTL.


Just search for "bolt-in"


3. They will all work with Ranges. Alas this is all still well up in the
blue-skies as far as D goes. I've pretty much got it all worked out for




C++,

along with John Torjo - I've been doing the concepts and the




abstractions,

and John's been doing some mind bending things with filters. I *know* it
will
work for D because I worked it out on a bike ride a couple of weeks ago,
but I forgot it again before I could get to some paper, so it's a case of
arsing
around in code, or doing something else, until the code pixie comes by




and

whispers it in my ear again. <G>

(Please don't be concerned if this sounds like the ravings of a madman: I
get the
majority of my ideas in this way, and they often tantalise me from afar




for

days/weeks
before I can crystalise them onto paper.)


 no problem. I know what you mean. I'll wait for more details.


I'm not the only nutter, then


 Unless there are really good reasons
 to have one we should avoid making a Vector class.

 I can imagine a couple of possible reasons for Vector:
 1) Vector subclasses some abstract list class or
    interface


That will be possible, via the bolt-in mechanism


 2) Vector would use iterator classes to be consistent
    with other classes in DTL


DTL classes will all work with algorithms and built-in language features




in

the form of ranges/slices, rather than STL-like iterators.


 cool!


I hope so.


FYI, I'm going to try and complete the C++ Ranges stuff (for STLSoft;




JT's

doing a Boost version) before, so the concept's are clear, and then the D
Range stuff should seem a lot clearer (if only because there'll be




something

concrete and proven to which people (including me) can refer).

But we should have no issue using the DTL stuff thus far without any




concern

of Ranges, so I'll try and do the bolt-in stuff and post it shortly.


 ok.


 Without seeing DTL it's kindof hard to imagine
 satisfying 1 and 2 with "pure" dynamic arrays but
 I really hope we don't just add a Vector class
 because Java/C++ have one in their collections API.


Not in the least.


 yeah, I shouldn't have said "just because Java/C++ have
 one"... It's natural to want to add one, just as it is
 natural to want to add a String class of some sort. I really
 hope we can keep 90% of D code using dynamic arrays - no
 offense to Vector but multiple ways to do very similar
 things is a pain in the butt when writing APIs.


Very true. But a language that needlessly restricts the expressiveness of
its users will have fewer sooner.
Mar 21 2004
prev sibling next sibling parent reply J Anderson <REMOVEanderson badmama.com.au> writes:
Matthew wrote:


There's also an IntRange, which I mentioned in a recent post will support a
relativelt succint syntax

    foreach(int i; new IntRange(-20, +20, 2))
    {
        . . .
    }

This'll be turned into a template soon so that it will work with any
integral type.


Wouldn't this be neater in a free function ie:

    foreach(int i; range(-20, +20, 2))
    {
        . . .
    }

or do you plan to do that?

-- 
-Anderson: http://badmama.com.au/~anderson/
Mar 20 2004
parent "Matthew" <matthew stlsoft.org> writes:
"J Anderson" <REMOVEanderson badmama.com.au> wrote in message
news:c3i172$12o2$2 digitaldaemon.com...

 Matthew wrote:


There's also an IntRange, which I mentioned in a recent post will support




a

relativelt succint syntax

    foreach(int i; new IntRange(-20, +20, 2))
    {
        . . .
    }

This'll be turned into a template soon so that it will work with any
integral type.


 Wouldn't this be neater in a free function ie:

     foreach(int i; range(-20, +20, 2))
     {
         . . .
     }

 or do you plan to do that?


Indeed. That's one option, and I've now done it. But because D does not
support implicit template instantiation, we'd either have to be satisfied
with just one (int), or one of a small set (one integral, one floating
point, etc.), as in:

    IntegralRange!(int).Range range(int from, int to, int inc)
    {
        return new IntegralRange!(int).Range(from, to, inc);
    }

    FloatingRange!(double) range(double from, ...)
    {
        return new FloatingRange!(double)(from, to, inc);
    }

and rely on the user to specify integers or floating points to help the
compiler disambiguate, as in:

 foreach(int i; range(0, 10, +1))
 {
  printf("%d ", i);
 }

 foreach(int i; range(0.0, 10.0, +1.0))
 {
  printf("%d ", i);
 }

This is not really a bad solution, since one would always be free to use
explicit ranges for other types, as in

 foreach(int i; IntegralRange!(long).range(0, 10, +1))
 {
  printf("%d ", i);
 }


I've also got several half finished thoughts about how we might somehow get
these things integrated into the language, but as I say, they're only
half-finished (probably half-baked). And since the int and double forms
would serve the vast majority of cases, it's probably best left
unemcumbered.
Mar 20 2004
prev sibling parent reply John Reimer <jjreimer telus.net> writes:
Matthew,

It's really nice to see work being done on a comprehensive DTL.  And 
what's better is having the right person doing it.

Just wanted to say thanks.  There's plenty of work in that task, and I, 
and I'm sure many others, appreciate the time you are putting into it. 
And for free? Wow! (Or do we have to promise to buy all your books?!)

The thing about working on a library with such important implications 
is that it takes nerve to put your work out for public critism (or 
critique as we North Americans like to say ;-D ).  It's great you've got 
the nerve.  I'm looking forward to seeing it's completion and inclusion 
in D.

Thanks again,

John
Mar 22 2004
next sibling parent reply "Phill" <phill pacific.net.au> writes:
"John Reimer" <jjreimer telus.net> wrote in message
news:c3ns62$1fjp$1 digitaldaemon.com...

 Matthew,

 It's really nice to see work being done on a comprehensive DTL.  And
 what's better is having the right person doing it.

 Just wanted to say thanks.  There's plenty of work in that task, and I,
 and I'm sure many others, appreciate the time you are putting into it.
 And for free? Wow! (Or do we have to promise to buy all your books?!)

 The thing about working on a library with such important implications
 is that it takes nerve to put your work out for public critism (or
 critique as we North Americans like to say ;-D ).  It's great you've got
 the nerve.  I'm looking forward to seeing it's completion and inclusion
 in D.

 Thanks again,

 John


Yes, even though he's British he is very talented. :o))

Seriously, I dont know where this would be without him, this DTL will
definately make D more attractive.

Phill.
Mar 22 2004
next sibling parent "Matthew" <matthew stlsoft.org> writes:
"Phill" <phill pacific.net.au> wrote in message
news:c3ok1g$2phm$1 digitaldaemon.com...

 "John Reimer" <jjreimer telus.net> wrote in message
 news:c3ns62$1fjp$1 digitaldaemon.com...

 Matthew,

 It's really nice to see work being done on a comprehensive DTL.  And
 what's better is having the right person doing it.

 Just wanted to say thanks.  There's plenty of work in that task, and I,
 and I'm sure many others, appreciate the time you are putting into it.
 And for free? Wow! (Or do we have to promise to buy all your books?!)

 The thing about working on a library with such important implications
 is that it takes nerve to put your work out for public critism (or
 critique as we North Americans like to say ;-D ).  It's great you've got
 the nerve.  I'm looking forward to seeing it's completion and inclusion
 in D.

 Thanks again,

 John


 Yes, even though he's British he is very talented. :o))


I'm sure I don't get the contradiction.

Anyway, I'm not British, just a child of the world ... think of me as a
well-travelled Yorkshireman, which is an oxymoron all its own.


 Seriously, I dont know where this would be without him, this DTL will
 definately make D more attractive.


Well, let's just hope we get there. :)

It's not entirely philanthropy, of course. I want to get Ranges accepted in
both C++ and D (and maybe .NET) communities, so a bit of cross-correlation
is going to go down nicely. It's also good stuff for books. The penultimate
chapter of "Imperfect C++" - Chapter 34 "Functors and Ranges" - contains a
good description of the Simple (like IntegralRange, i.e. the range is
"purely" notional) and Iterable (based on a pair of iterators demarking a
"real" range). The next C++ book (on "advanced" STL, if I may be so bold)
will take this to the next level, with the introduction of a new range
concept that I'm working on, which will encompass most other types of ranges
that I can think of, which the STL Iterator concept cannot support (see my
Feb 2004 CUJ article for a description of some of the limitations of
Iterators.). If/when the D book gets going, I hope that Ranges will be in
DTL, and therefore the cross-correlation will be complete! (I had a scary
Emporer/Skywalker moment then. <G>)

Once I've got them in D and C++, I want to explore it with .NET, but it's
very early days yet, and those guys'll be a lot harder to persuade. (I
recently wrote a beautiful little range adapter template, to adapt the .NET
mapping of recls to a range, in Managed C++, only to be informed by the
compiler that templates may not hold pointers to managed objects. Grrrr.
There's a lot of work to be done there, methinks. :(
Mar 23 2004
prev sibling parent reply =?ISO-8859-1?Q?Sigbj=F8rn_Lund_Olsen?= <sigbjorn lundolsen.net> writes:
Phill wrote:


 "John Reimer" <jjreimer telus.net> wrote in message
 news:c3ns62$1fjp$1 digitaldaemon.com...
 

Matthew,

It's really nice to see work being done on a comprehensive DTL.  And
what's better is having the right person doing it.

Just wanted to say thanks.  There's plenty of work in that task, and I,
and I'm sure many others, appreciate the time you are putting into it.
And for free? Wow! (Or do we have to promise to buy all your books?!)

The thing about working on a library with such important implications
is that it takes nerve to put your work out for public critism (or
critique as we North Americans like to say ;-D ).  It's great you've got
the nerve.  I'm looking forward to seeing it's completion and inclusion
in D.

Thanks again,

John


 
 
 Yes, even though he's British he is very talented. :o))


Oh. I thought a Brit accent gave you 20 free IQ points. My mistake :-p

Cheers,
Sigbjørn Lund Olsen
Mar 23 2004
next sibling parent reply John Reimer <jjreimer telus.net> writes:
 Yes, even though he's British he is very talented. :o))
 
 Oh. I thought a Brit accent gave you 20 free IQ points. My mistake :-p
 
 Cheers,
 Sigbjørn Lund Olsen


True, there appears to be a pattern to it.  It seems that in the movies,
they have to get these annoying British accented actors to play the
intellectuals. I guess a drawling redneck American just doesn't cut it! :-D
Mar 23 2004
parent reply Chris Paulson-Ellis <chris edesix.com> writes:
John Reimer wrote:

 True, there appears to be a pattern to it.  It seems that in the movies,
 they have to get these annoying British accented actors to play the
 intellectuals. I guess a drawling redneck American just doesn't cut it! :-D


Interestingly, British made TV science documentaries rely almost 
exclusively on American scientists for soundbites and convincing 
sounding explanations of ideas.

The footage is usually accompanied with shots of the scientists driving 
around California in flashy open top cars. I suspect the producers 
rather enjoy their trips to the sun :-)

Chris (in very sunny Edinburgh, Scotland).
Mar 24 2004
parent Alix Pexton <Alix thedjournal.com> writes:
I am of the opinion that, Americans are used for sound bites because 
they are better at putting concepts into laymans terms than the English 
generally are, after all they get more practice...

Additionally it is difficult to get an Englishman to comment on some 
scientific research if it was undertaken in the US, the UK does not 
(perhaps cannot) expend the same level of resources on research for 
research's sake...

Alix (In mildly drizzly York, England)...

Chris Paulson-Ellis wrote:


 John Reimer wrote:


 True, there appears to be a pattern to it.  It seems that in the movies,
 they have to get these annoying British accented actors to play the
 intellectuals. I guess a drawling redneck American just doesn't cut 
 it! :-D



 Interestingly, British made TV science documentaries rely almost 
 exclusively on American scientists for soundbites and convincing 
 sounding explanations of ideas.

 The footage is usually accompanied with shots of the scientists 
 driving around California in flashy open top cars. I suspect the 
 producers rather enjoy their trips to the sun :-)

 Chris (in very sunny Edinburgh, Scotland).




-- 
            Alix Pexton
Webmaster - http://www.theDjournal.com

            Alix theDjournal.com
Mar 24 2004
prev sibling parent "Kris" <someidiot earthlink.net> writes:
 Oh. I thought a Brit accent gave you 20 free IQ points. My mistake :-p

 Cheers,
 Sigbjørn Lund Olsen


Hey! I spent 20 years in Scottish education, and we were always told it was
worth FAR more than that ...

- Kris
Mar 24 2004
prev sibling parent "Matthew" <matthew stlsoft.org> writes:
"John Reimer" <jjreimer telus.net> wrote in message
news:c3ns62$1fjp$1 digitaldaemon.com...

 Matthew,

 It's really nice to see work being done on a comprehensive DTL.  And
 what's better is having the right person doing it.


You may have cause to eat those words ... ;)


 Just wanted to say thanks.  There's plenty of work in that task, and I,
 and I'm sure many others, appreciate the time you are putting into it.


Good to hear. I'm looking forward to getting lots of feedback.

FYI: My next step is relying on default template params, which is not yet
supported. Big W is working on (or at least thinking about) that at the
moment, so it may be a week or so before we get anything coming down the
pipe.

That works out well anyway, since I have to research and write an article
for a paying client this week. :)


sitting in the Addison-Wesley mail-system until they work out how to let me
down gently. <G>

I feel 10 years younger this morning. :-)


 And for free? Wow! (Or do we have to promise to buy all your books?!)


Free? Yes. Book purchase? Most assuredly!


 The thing about working on a library with such important implications
 is that it takes nerve to put your work out for public critism (or
 critique as we North Americans like to say ;-D ).  It's great you've got
 the nerve.


Nerve's not something I'm lacking in. Brains? Maybe. Tact? Definitely.
Charm? Alas yes. (At least my wife would say so)

As for the ramifications, there are two main features of DTL that will be
"different" (can't really say radical) from what's gone before.

First, is focus on/use of Ranges, rather than Iterators, since Iterators is
just one of (currently) three types of ranges. (This is, as I've said
before, falling out of work in C++ with John Torjo, and will feature in the
next C++ book.) I'm still working out the details, but I hope to integrate
ranges/filters into D's slice syntax. Things are still blue sky a bit on
that, and I'm content for that to wait awhile.

The second aspect is the ability to support Java style runtime polymorphic
implementation of container interfaces, and compile-time STL style generic
behaviour. I've mentioned some of this to Walter, and must now wait until
Walter makes some changes to the compiler. I've done some proof of concept
work in C++, and it looks good so far, but there may be D aspects I've not
yet thought of, or additions to the language that Walter is unwilling to
make.


  I'm looking forward to seeing it's completion and inclusion
 in D.

 Thanks again,


You're most welcome.
Mar 23 2004