Disclaimer: I am very new to templated containers as this is the second time I've implemented a doubly linked list thingy (the first time being in C++), but of course the D one is much better : )

Goal: implement a fast and easy to use templated doubly linked list in D

How it works: it keeps track of itself and lets you go forward/backward and remove any items you want to.

Simple example: print out 1 through 3

------------------------------------------
DLlist!(int) list = new DLlist!(int);

list.add(1); list.add(2); list.add(3);

while (!list.last)
    writefln(list.data);
------------------------------------------

Other features:
  * list.first : go from last to first
  * list.size/length : size as int
  * list.remove : remove current item (must be in the loop)
  * list.clear() : clear all data in the list
  * list.reset() : not really needed, but ensures the first/last feature
works correctly

My only question I have about it is that I know in C++ you can return references which is faster for large chunks of data. So, can you do the same type of thing in D? right now I just use a simple

T data() {
   return curr.data;
}

like structure.

So, what do you think? Is it good, or not really?

Thanks,
  - Clay

Clay put listtest.d into unittest of your Dlist code.

-- 
...........
Dejan Lekic
  http://dejan.lekic.org

On Mon, 09 May 2005 23:23:22 +0000, clayasaurus wrote:

> So, what do you think? Is it good, or not really?

I'll have a closer look during the next couple of days but should

-------------------
   bit empty()
   {
      if (listSize == 0)
         return true;
      else
         return false;
   }
---------------------

be written as either ...

--------------------
   bool empty()
   {
      if (listSize == 0)
         return true;
      else
         return false;
   }

----------------------

or ...
----------------------
   bit empty()
   {
      if (listSize == 0)
         return 1;
      else
         return 0;
   }
-------------------------

Conceptually, a boolean is not one eighth of a byte, so just for some consistency you probably need to select one or the other.

-- 
Derek
Melbourne, Australia
10/05/2005 9:37:59 AM

Dejan Lekic wrote:
> Clay put listtest.d into unittest of your Dlist code.
> 

I tried it but I'm not quite sure how to implement it. For example, would I use a unit test after add like this?


add(T) { ... }

unittest
{
   writefln("unittest...");
   add(2);
   assert(size() == 1);
}

also, is unittest supposed to happen at compile time or runtime?

On Mon, 09 May 2005 20:51:23 -0400, clayasaurus wrote:

> Dejan Lekic wrote:
>> Clay put listtest.d into unittest of your Dlist code.
>> 
> 
> I tried it but I'm not quite sure how to implement it. For example, would I use a unit test after add like this?
> 
> add(T) { ... }
> 
> unittest
> {
>     writefln("unittest...");
>     add(2);
>     assert(size() == 1);
> }

More like this ...

 unittest
 {
     // Create a list to play with.
     DLlist!(int) list = new DLlist!(int);
     // Display only if compiled with debug=1
     debug(1) writefln("unittest...");

     // add first item.
     list.add(2);
     assert(list.size() == 1);
     // add second item.
     list.add(3);
     assert(list.size() == 2);

 }
> also, is unittest supposed to happen at compile time or runtime?

Runtime, but only if compiled with -unittest *and* if main() gets invoked.
Then it runs after all module constructors are run and before main() gets
control.

-- 
Derek
Melbourne, Australia
10/05/2005 11:11:07 AM

Derek Parnell wrote:
> On Mon, 09 May 2005 20:51:23 -0400, clayasaurus wrote:
> 
> 
>>Dejan Lekic wrote:
>>
>>>Clay put listtest.d into unittest of your Dlist code.
>>>
>>
>>I tried it but I'm not quite sure how to implement it. For example, would I use a unit test after add like this?
>>
>>add(T) { ... }
>>
>>unittest
>>{
>>    writefln("unittest...");
>>    add(2);
>>    assert(size() == 1);
>>}
> 
> 
> More like this ...
> 
>  unittest
>  {
>      // Create a list to play with.
>      DLlist!(int) list = new DLlist!(int);       // Display only if compiled with debug=1
>      debug(1) writefln("unittest..."); 
> 
>      // add first item.
>      list.add(2);
>      assert(list.size() == 1);
>      // add second item.
>      list.add(3);
>      assert(list.size() == 2);
> 
>  }
> 
>>also, is unittest supposed to happen at compile time or runtime?
> 
> 
> Runtime, but only if compiled with -unittest *and* if main() gets invoked.
> Then it runs after all module constructors are run and before main() gets
> control.
> 

Okay, because the D documentation says ...

"The best way to make sure that unit tests do get run, and that they are maintained along with the class code is to put the test code right in with the class implementation code."

and then gives this example...

class Sum
{
    int add(int x, int y) { return x + y; }

    unittest
    {
	assert(add(3,4) == 7);
	assert(add(-2,0) == -2);
    }
}

so... is it true that unittests have a better chance of being run if they are put right after the function inside the class? does that mean that sometimes unittests are not run?

It seems like unittest is trying to be a member function, but it I guess it is not if you can implement it outside the class.

http://www.digitalmars.com/d/class.html#unittest

Just a little confusion...

On Mon, 09 May 2005 23:49:36 -0400, clayasaurus wrote:

> Derek Parnell wrote:
>> On Mon, 09 May 2005 20:51:23 -0400, clayasaurus wrote:
>> 
>>>Dejan Lekic wrote:
>>>
>>>>Clay put listtest.d into unittest of your Dlist code.
>>>>
>>>
>>>I tried it but I'm not quite sure how to implement it. For example, would I use a unit test after add like this?
>>>
>>>add(T) { ... }
>>>
>>>unittest
>>>{
>>>    writefln("unittest...");
>>>    add(2);
>>>    assert(size() == 1);
>>>}
>> 
>> More like this ...
>> 
>>  unittest
>>  {
>>      // Create a list to play with.
>>      DLlist!(int) list = new DLlist!(int);
>>      // Display only if compiled with debug=1
>>      debug(1) writefln("unittest...");
>> 
>>      // add first item.
>>      list.add(2);
>>      assert(list.size() == 1);
>>      // add second item.
>>      list.add(3);
>>      assert(list.size() == 2);
>> 
>>  }
>> 
>>>also, is unittest supposed to happen at compile time or runtime?
>> 
>> Runtime, but only if compiled with -unittest *and* if main() gets invoked.
>> Then it runs after all module constructors are run and before main() gets
>> control.
>> 
> 
> Okay, because the D documentation says ...
> 
> "The best way to make sure that unit tests do get run, and that they are maintained along with the class code is to put the test code right in with the class implementation code."
> 
> and then gives this example...
> 
> class Sum
> {
>      int add(int x, int y) { return x + y; }
> 
>      unittest
>      {
> 	assert(add(3,4) == 7);
> 	assert(add(-2,0) == -2);
>      }
> }
> 
> so... is it true that unittests have a better chance of being run if they are put right after the function inside the class? does that mean that sometimes unittests are not run?
> 
> It seems like unittest is trying to be a member function, but it I guess it is not if you can implement it outside the class.
> 
> http://www.digitalmars.com/d/class.html#unittest
> 
> Just a little confusion...

My fault. You can write them as member functions or module functions. I always write them as module functions 'cos I know how they work. I haven't experimented with unittests as class member functions yet.


-- 
Derek
Melbourne, Australia
10/05/2005 1:58:35 PM

General two cents about list implementations:

There are two types of list implementations: opaque and intrusive.
You've implemented opaque - means that you create
and envelope around data (struct Node).

Problem with this approach is simple - you need to allocate additional object for each data item. Which is not so good for couple of reasons.

Different approach:  intrusive lists. There data item by itself contains next and prev fields. So you are allocating item once.

Consider this template

class ListItem(NODE)
{
    NODE next;
    NODE prev;
    this() { next = prev = this; }

    // link this after NODE 'after'
    void linkAfter(NODE after)
         {  (next = after.next).prev = this; (prev = after).next = this;  }
    // link this before NODE 'before'
    void linkBefore(NODE before)
         { (prev = before.prev).next = this; (next = before).prev = this; }
    // unlink this from the list
    void unlink() {  prev.next = next; next.prev = prev; next = prev =
this; }
}

Then if you will declare you class as

class MyClass: ListItem!(MyClass) // see [1] for the explanation of this
trick
{
   members....
   ......
}

then you can work with instances of your class without
any additional list structures and allocations as your MyClass is a list
itself
generally speaking.

MyClass list = new MyClass(); // first member of the list, its head
(new MyClass()).linkAfter(list); // second
(new MyClass()).linkAfter(list); // third

// enumeration of list members.
MyClass m = list;
do {
     m.dosomething();
} while ( m !==  list);

-------------------------
Andrew.


[1] Curiously Recurring Template Pattern.
 http://everything2.com/index.pl?node_id=1701684

"Andrew Fedoniouk" <news@terrainformatica.com> wrote in message news:d5plb2$gsu$1@digitaldaemon.com...
> General two cents about list implementations:
>
> There are two types of list implementations: opaque and intrusive.
> You've implemented opaque - means that you create
> and envelope around data (struct Node).
>
> Problem with this approach is simple - you need to allocate additional object for each data item. Which is not so good for couple of reasons.
>
> Different approach:  intrusive lists. There data item by itself contains next and prev fields. So you are allocating item once.

The downside of intrusive lists is that an item can be in only one list. This is fine for some situations like widgets in a GUI but it is a pretty strong restriction in general. With reusing nodes and allocating nodes in chunks the node overhead isn't that bad IMHO. I was going to add some mixins to MinTL to support intrusive lists but I never got it fully baked.

>> General two cents about list implementations:
>>
>> There are two types of list implementations: opaque and intrusive.
>> You've implemented opaque - means that you create
>> and envelope around data (struct Node).
>>
>> Problem with this approach is simple - you need to allocate additional object for each data item. Which is not so good for couple of reasons.
>>
>> Different approach:  intrusive lists. There data item by itself contains next and prev fields. So you are allocating item once.
>
> The downside of intrusive lists is that an item can be in only one list. This is fine for some situations like widgets in a GUI but it is a pretty strong restriction in general. With reusing nodes and allocating nodes in chunks the node overhead isn't that bad IMHO. I was going to add some mixins to MinTL to support intrusive lists but I never got it fully baked.

Agreed.
But, in general and in most cases lists as containers are not so effective
as arrays (memory, cache misses, etc.).
Only if you have situations when you frequently
need to do insertions in the collections... In this cases lists are working
better.
In other cases like append-and-read array are better. So I think
in almost 99% of cases you can use intrusive lists.
(IMHO)