digitalmars.D.learn - feedback wanted: DLlist.d - doubly linked list implementation in
- clayasaurus (30/30) May 09 2005 Disclaimer: I am very new to templated containers as this is the second
- Dejan Lekic (6/6) May 09 2005 Clay put listtest.d into unittest of your Dlist code.
- clayasaurus (11/13) May 09 2005 I tried it but I'm not quite sure how to implement it. For example,
- Derek Parnell (22/38) May 09 2005 More like this ...
- clayasaurus (22/68) May 09 2005 Okay, because the D documentation says ...
- Derek Parnell (8/82) May 09 2005 My fault. You can write them as member functions or module functions. I
- Derek Parnell (37/38) May 09 2005 I'll have a closer look during the next couple of days but should
- Andrew Fedoniouk (48/48) May 09 2005 General two cents about list implementations:
- Ben Hinkle (7/16) May 10 2005 The downside of intrusive lists is that an item can be in only one list....
- Andrew Fedoniouk (9/26) May 10 2005 Agreed.
- Klaus Oberhofer (21/24) May 10 2005 There is an interesting article about intrusive data structures in C++ o...
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
Clay put listtest.d into unittest of your Dlist code. -- ........... Dejan Lekic http://dejan.lekic.org
May 09 2005
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
On Mon, 09 May 2005 20:51:23 -0400, clayasaurus wrote:Dejan Lekic wrote: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); }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?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
Derek Parnell wrote:On Mon, 09 May 2005 20:51:23 -0400, clayasaurus wrote: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...Dejan Lekic wrote: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); }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?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.
May 09 2005
Derek Parnell <derek psych.ward> On Mon, 09 May 2005 23:49:36 -0400, clayasaurus wrote:Derek Parnell wrote: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 PMOn Mon, 09 May 2005 20:51:23 -0400, clayasaurus wrote: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...Dejan Lekic wrote: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); }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?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.
May 09 2005
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
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
"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
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)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
"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