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" );

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" );
>

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" );
>>

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

"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" );
> >>
>

> 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.

> 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...

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...
> 
> 

"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"? :-)

> 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. :-)