www.digitalmars.com         C & C++   DMDScript  

digitalmars.D.learn - feedback wanted: DLlist.d - doubly linked list implementation in

reply clayasaurus <clayasaurus gmail.com> writes:
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit

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
May 09 2005
next sibling parent reply Dejan Lekic <leka entropy.tmok.com> writes:
Clay put listtest.d into unittest of your Dlist code.

-- 
...........
Dejan Lekic
  http://dejan.lekic.org
  
May 09 2005
parent reply clayasaurus <clayasaurus gmail.com> writes:
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?
May 09 2005
parent reply Derek Parnell <derek psych.ward> writes:
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
May 09 2005
parent reply clayasaurus <clayasaurus gmail.com> writes:
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...
May 09 2005
parent Derek Parnell <derek psych.ward> writes:
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
May 09 2005
prev sibling next sibling parent Derek Parnell <derek psych.ward> writes:
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
May 09 2005
prev sibling parent reply "Andrew Fedoniouk" <news terrainformatica.com> writes:
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 
May 09 2005
parent reply "Ben Hinkle" <ben.hinkle gmail.com> writes:
"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.
May 10 2005
next sibling parent "Andrew Fedoniouk" <news terrainformatica.com> writes:
 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)
May 10 2005
prev sibling parent Klaus Oberhofer <oberhofer ixxat.de> writes:
"Ben Hinkle" <ben.hinkle gmail.com> wrote in
news:d5q8fi$1090$1 digitaldaemon.com: 

 The downside of intrusive lists is that an item can be in only one
 list. 
 

There is an interesting article about intrusive data structures in C++ on http://www.codefarms.com/publications/intrusiv/intr.htm They use a third template parameter which is only used to be able to inherit multiple times from the intrusive base. The purpose is to maintain the node in multiple data structures. Example: template<class Node,class Edge,int i=0> class Node { // ... }; class Town : public Node<Town,Flight,0> , public Node<Town,Flight,1> { // ... }; IMHO this is one of the rare contexts were multiple inheritance has an advantage. I was wondering if the same behaviour could be achieved with mixins.
May 10 2005