View mode: basic / threaded / horizontal-split · Log in · Help
July 18, 2004
initial cut at "minimal template lib"
Well yesterday I was poking around with Java's Collections Framework and
that didn't go so well since it ran into various dmd bugs and it also
wasn't meshing well with existing D concepts like dynamic and assoc arrays.
So this morning I switched tactics and have started a "minimal template
library". The only thing I have so far is list.d (attached). I've pasted
below the unittest for list.d to give a flavor of usage (hint: List is a
parametrized struct). Basically List behaves alot like dynamic arrays
except the obvious O(n)/O(1) differences. Feedback welcome.

 List!(int) x;
 x.add(3);
 x.add(4);
 assert( x[0] == 3 );
 assert( x[1] == 4 );
 assert( x.length == 2 );

 // test addFront
 List!(int) y;
 y.addFront(4);
 y.addFront(3);

 // test ==
 assert( x == y );
 List!(int) w = x.dup;
 w.add(5);
 assert( x != w);

 // test remove
 assert( w.remove == 5 );
 w.trim();
 w.add(5);

 // test reverse lists
 List!(int) z = y.reverse.apply;
 assert( z[0] == 4 );
 assert( z[1] == 3 );

 // test foreach iteration
 foreach(int n, inout int val; z) {
   val = n*10;
 }
 assert( z[0] == 0 );
 assert( z[1] == 10 );
 foreach(int n, int val; y.reverse()) {
   assert(x[1-n] == val);
 }

 // test slicing
 List!(int) v = w[1..3];
 assert( v.length == 2 );
 assert( v[0] == 4 );
 assert( v[1] == 5 );

 // test another node type
 List!(char[]) str;
 str.add("hello");
 str.add("world");
 assert( str[str.length-1] == "world" );
July 19, 2004
Re: initial cut at "minimal template lib"
Ben

Pending some compiler fixes, I'm only days away from releasing 0.1 of DTL. Do you
want to perhaps dovetail our efforts? I've currently got List, Vector, Queue and
Map, so maybe if you're feeling creative you could look at some different types,
so as to avoid wasting effort?

Of course, if you're pioneering a solo course, that's fine. I'll meet you at the
colosseum. ;)

Matthew


"Ben Hinkle" <bhinkle4@juno.com> wrote in message
news:cdeeab$2haf$1@digitaldaemon.com...
> Well yesterday I was poking around with Java's Collections Framework and
> that didn't go so well since it ran into various dmd bugs and it also
> wasn't meshing well with existing D concepts like dynamic and assoc arrays.
> So this morning I switched tactics and have started a "minimal template
> library". The only thing I have so far is list.d (attached). I've pasted
> below the unittest for list.d to give a flavor of usage (hint: List is a
> parametrized struct). Basically List behaves alot like dynamic arrays
> except the obvious O(n)/O(1) differences. Feedback welcome.
>
>   List!(int) x;
>   x.add(3);
>   x.add(4);
>   assert( x[0] == 3 );
>   assert( x[1] == 4 );
>   assert( x.length == 2 );
>
>   // test addFront
>   List!(int) y;
>   y.addFront(4);
>   y.addFront(3);
>
>   // test ==
>   assert( x == y );
>   List!(int) w = x.dup;
>   w.add(5);
>   assert( x != w);
>
>   // test remove
>   assert( w.remove == 5 );
>   w.trim();
>   w.add(5);
>
>   // test reverse lists
>   List!(int) z = y.reverse.apply;
>   assert( z[0] == 4 );
>   assert( z[1] == 3 );
>
>   // test foreach iteration
>   foreach(int n, inout int val; z) {
>     val = n*10;
>   }
>   assert( z[0] == 0 );
>   assert( z[1] == 10 );
>   foreach(int n, int val; y.reverse()) {
>     assert(x[1-n] == val);
>   }
>
>   // test slicing
>   List!(int) v = w[1..3];
>   assert( v.length == 2 );
>   assert( v[0] == 4 );
>   assert( v[1] == 5 );
>
>   // test another node type
>   List!(char[]) str;
>   str.add("hello");
>   str.add("world");
>   assert( str[str.length-1] == "world" );
>
July 19, 2004
Re: initial cut at "minimal template lib"
My next target is a red-black tree for sorted maps. I've also written a
little set of array helpers: 
- reserve space for a dynamic array
- reserve space for an assoc array
- clear out an assoc array without losing capacity
- foreach backwards over a dyn array without reversing the elements in place

So in total mintl will have 3 files (maybe plus a doc file if I'm feeling
ambitious). If the red-black tree can be reused in DTL that would be cool
but I'd like to let these things evolve independently for a while. I don't
mean to be a pain in the tush by putting out a "competing" List/Map/etc but
I just wanted to test out some ideas. For instance, do we need iterators?
maybe not. Can the types be structs? I think so. Stuff like that. All of
your recent DTL posting got me thinking about these things. It would be
nice to keep the concepts as simple as the ones for dynamic arrays and
assoc arrays. Anyhow, I'm gonna finish up the rbtree in the next few days
or so.

-Ben

Matthew wrote:

> Ben
> 
> Pending some compiler fixes, I'm only days away from releasing 0.1 of DTL.
> Do you want to perhaps dovetail our efforts? I've currently got List,
> Vector, Queue and Map, so maybe if you're feeling creative you could look
> at some different types, so as to avoid wasting effort?
> 
> Of course, if you're pioneering a solo course, that's fine. I'll meet you
> at the colosseum. ;)
> 
> Matthew
> 
> 
> "Ben Hinkle" <bhinkle4@juno.com> wrote in message
> news:cdeeab$2haf$1@digitaldaemon.com...
>> Well yesterday I was poking around with Java's Collections Framework and
>> that didn't go so well since it ran into various dmd bugs and it also
>> wasn't meshing well with existing D concepts like dynamic and assoc
>> arrays. So this morning I switched tactics and have started a "minimal
>> template library". The only thing I have so far is list.d (attached).
>> I've pasted below the unittest for list.d to give a flavor of usage
>> (hint: List is a parametrized struct). Basically List behaves alot like
>> dynamic arrays except the obvious O(n)/O(1) differences. Feedback
>> welcome.
>>
>>   List!(int) x;
>>   x.add(3);
>>   x.add(4);
>>   assert( x[0] == 3 );
>>   assert( x[1] == 4 );
>>   assert( x.length == 2 );
>>
>>   // test addFront
>>   List!(int) y;
>>   y.addFront(4);
>>   y.addFront(3);
>>
>>   // test ==
>>   assert( x == y );
>>   List!(int) w = x.dup;
>>   w.add(5);
>>   assert( x != w);
>>
>>   // test remove
>>   assert( w.remove == 5 );
>>   w.trim();
>>   w.add(5);
>>
>>   // test reverse lists
>>   List!(int) z = y.reverse.apply;
>>   assert( z[0] == 4 );
>>   assert( z[1] == 3 );
>>
>>   // test foreach iteration
>>   foreach(int n, inout int val; z) {
>>     val = n*10;
>>   }
>>   assert( z[0] == 0 );
>>   assert( z[1] == 10 );
>>   foreach(int n, int val; y.reverse()) {
>>     assert(x[1-n] == val);
>>   }
>>
>>   // test slicing
>>   List!(int) v = w[1..3];
>>   assert( v.length == 2 );
>>   assert( v[0] == 4 );
>>   assert( v[1] == 5 );
>>
>>   // test another node type
>>   List!(char[]) str;
>>   str.add("hello");
>>   str.add("world");
>>   assert( str[str.length-1] == "world" );
>>
July 19, 2004
Re: initial cut at
In article <cdeeab$2haf$1@digitaldaemon.com>, Ben Hinkle says...
> Feedback welcome.

for yourself and everybody that you want to use the
lib add proper documentation into the source.
Use doxygen to generate (or just test) the documentation.
Use the javadoc sintax and tags.

Ant
July 19, 2004
Re: initial cut at "minimal template lib"
"Ben Hinkle" <bhinkle4@juno.com> wrote in message
news:cdgfi3$c61$1@digitaldaemon.com...
> My next target is a red-black tree for sorted maps. I've also written a
> little set of array helpers:
> - reserve space for a dynamic array
> - reserve space for an assoc array
> - clear out an assoc array without losing capacity
> - foreach backwards over a dyn array without reversing the elements in
place
>
> So in total mintl will have 3 files (maybe plus a doc file if I'm feeling
> ambitious). If the red-black tree can be reused in DTL that would be cool
> but I'd like to let these things evolve independently for a while. I don't
> mean to be a pain in the tush by putting out a "competing" List/Map/etc
but
> I just wanted to test out some ideas. For instance, do we need iterators?
> maybe not. Can the types be structs? I think so. Stuff like that. All of
> your recent DTL posting got me thinking about these things. It would be
> nice to keep the concepts as simple as the ones for dynamic arrays and
> assoc arrays. Anyhow, I'm gonna finish up the rbtree in the next few days
> or so.

You're not being a pain in the slightest. The approach you've described
sounds perfectly attuned with my own. I'm not really focusing on particular
containers at the moment, I'm trying to get the overall "paradigm" sorted,
if you'll pardon my grandiloquence.

My current focus is trying to get Walter to change some parts of the
language, so we can compose filters. I'm going to do a workaround, but the
real thing'd be much easier.

In the long run, I hope my vision of DTL is accepted/acceptable, and that
all contributions of specific container classes all fall into a consistent
library.

Regarding iterators, I'm currently doubtful about them. I'm quite certain
that they'll have far less important in D than they do in C++.

I've been thinking about the struct/class issue, and I'm pleased that you're
also thinking about it. I look forward to hearing more of your thoughts.


> -Ben
>
> Matthew wrote:
>
> > Ben
> >
> > Pending some compiler fixes, I'm only days away from releasing 0.1 of
DTL.
> > Do you want to perhaps dovetail our efforts? I've currently got List,
> > Vector, Queue and Map, so maybe if you're feeling creative you could
look
> > at some different types, so as to avoid wasting effort?
> >
> > Of course, if you're pioneering a solo course, that's fine. I'll meet
you
> > at the colosseum. ;)
> >
> > Matthew
> >
> >
> > "Ben Hinkle" <bhinkle4@juno.com> wrote in message
> > news:cdeeab$2haf$1@digitaldaemon.com...
> >> Well yesterday I was poking around with Java's Collections Framework
and
> >> that didn't go so well since it ran into various dmd bugs and it also
> >> wasn't meshing well with existing D concepts like dynamic and assoc
> >> arrays. So this morning I switched tactics and have started a "minimal
> >> template library". The only thing I have so far is list.d (attached).
> >> I've pasted below the unittest for list.d to give a flavor of usage
> >> (hint: List is a parametrized struct). Basically List behaves alot like
> >> dynamic arrays except the obvious O(n)/O(1) differences. Feedback
> >> welcome.
> >>
> >>   List!(int) x;
> >>   x.add(3);
> >>   x.add(4);
> >>   assert( x[0] == 3 );
> >>   assert( x[1] == 4 );
> >>   assert( x.length == 2 );
> >>
> >>   // test addFront
> >>   List!(int) y;
> >>   y.addFront(4);
> >>   y.addFront(3);
> >>
> >>   // test ==
> >>   assert( x == y );
> >>   List!(int) w = x.dup;
> >>   w.add(5);
> >>   assert( x != w);
> >>
> >>   // test remove
> >>   assert( w.remove == 5 );
> >>   w.trim();
> >>   w.add(5);
> >>
> >>   // test reverse lists
> >>   List!(int) z = y.reverse.apply;
> >>   assert( z[0] == 4 );
> >>   assert( z[1] == 3 );
> >>
> >>   // test foreach iteration
> >>   foreach(int n, inout int val; z) {
> >>     val = n*10;
> >>   }
> >>   assert( z[0] == 0 );
> >>   assert( z[1] == 10 );
> >>   foreach(int n, int val; y.reverse()) {
> >>     assert(x[1-n] == val);
> >>   }
> >>
> >>   // test slicing
> >>   List!(int) v = w[1..3];
> >>   assert( v.length == 2 );
> >>   assert( v[0] == 4 );
> >>   assert( v[1] == 5 );
> >>
> >>   // test another node type
> >>   List!(char[]) str;
> >>   str.add("hello");
> >>   str.add("world");
> >>   assert( str[str.length-1] == "world" );
> >>
>
July 19, 2004
Re: initial cut at "minimal template lib"
> Regarding iterators, I'm currently doubtful about them. I'm quite certain
> that they'll have far less important in D than they do in C++.

Cool. I agree. I've been playing around with using a one-item sub-list (or
sub-map or whatever) as a replacement for an iterator. From what I
understand of ranges you might be thinking something similar. For example,
I've added an opApply that instead of passing the integer index like
foreach( int n, T val; x) {} // x[n] is val
passes a one-item sub-list holding the current item:
foreach( List!(T) n, T val; x){} // n[0] is val
Also I've added more functions to handle sub-lists - things like removing
them, growing them, inserting before and after them, spanning them... etc.

Maps can be treated similarly (a slice of a map is a sub-map) but it has a
downside of increasing the size of the struct to have pointers to the first
and last nodes in addition to the tree root.
July 19, 2004
Re: initial cut at "minimal template lib"
> I've been thinking about the struct/class issue, and I'm pleased that
you're
> also thinking about it. I look forward to hearing more of your thoughts.

I'd guess that you need both struct based and class based variants of
collections like list, e.g. I've made Sequence and SequenceRef, the first is
a struct template while the second is a class template. Both mix-in their
implementation and both are quite useful. I guess for types like arrayed
lists there's even four variants: struct/class dynamic/static; not to speak
of higher-dimensional structures.

It'll be interesting to see how much "D-think" there'll be in the first
version of DTL...
July 19, 2004
Re: initial cut at "minimal template lib"
definitely do both struct and class of everything

you never know when one might come in handy...

on the other hand it definitely muddles pass-by-ref and pass-by-val

you get cases where you pass a vector<> into a function and it gets 
copied sometimes:
i.e. the inner function does a push_back on a value...
that may or may not increase memory allocation
then that inner function sets the value--that may or may not set the 
caller's copy of the struct
but one thing is certain: the caller's vector struct will be precisely 
the size it was when it was passed it, because it's a local struct var...
how do we deal with difficult to identify bugs like this (they only 
occur on power of two borders)


Bent Rasmussen wrote:
>>I've been thinking about the struct/class issue, and I'm pleased that
> 
> you're
> 
>>also thinking about it. I look forward to hearing more of your thoughts.
> 
> 
> I'd guess that you need both struct based and class based variants of
> collections like list, e.g. I've made Sequence and SequenceRef, the first is
> a struct template while the second is a class template. Both mix-in their
> implementation and both are quite useful. I guess for types like arrayed
> lists there's even four variants: struct/class dynamic/static; not to speak
> of higher-dimensional structures.
> 
> It'll be interesting to see how much "D-think" there'll be in the first
> version of DTL...
> 
>
July 20, 2004
Re: initial cut at "minimal template lib"
"Bent Rasmussen" <exo@bent-rasmussen.info> wrote in message
news:cdhjsb$roi$1@digitaldaemon.com...
> > I've been thinking about the struct/class issue, and I'm pleased that
> you're
> > also thinking about it. I look forward to hearing more of your thoughts.
>
> I'd guess that you need both struct based and class based variants of
> collections like list, e.g. I've made Sequence and SequenceRef, the first is
> a struct template while the second is a class template. Both mix-in their
> implementation and both are quite useful. I guess for types like arrayed
> lists there's even four variants: struct/class dynamic/static; not to speak
> of higher-dimensional structures.
>
> It'll be interesting to see how much "D-think" there'll be in the first
> version of DTL...

What's "D-think"? Is that a bit like "double-speak"? :-)
July 20, 2004
Re: initial cut at "minimal template lib"
> What's "D-think"? Is that a bit like "double-speak"? :-)

I mean using the language constructs that make D special.I've heard the term
"D style" before, its probably the same thing. :-)
« First   ‹ Prev
1 2 3
Top | Discussion index | About this forum | D home