Thread overview | |||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
|
May 09, 2005 feedback wanted: DLlist.d - doubly linked list implementation in D | ||||
---|---|---|---|---|
| ||||
Attachments: | 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 Re: feedback wanted: DLlist.d - doubly linked list implementation in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to clayasaurus |
Clay put listtest.d into unittest of your Dlist code.
--
...........
Dejan Lekic
http://dejan.lekic.org
|
May 09, 2005 Re: feedback wanted: DLlist.d - doubly linked list implementation in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to clayasaurus | 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 10, 2005 Re: feedback wanted: DLlist.d - doubly linked list implementation in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Dejan Lekic | 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 10, 2005 Re: feedback wanted: DLlist.d - doubly linked list implementation in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to clayasaurus | 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 10, 2005 Re: feedback wanted: DLlist.d - doubly linked list implementation in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Derek Parnell | 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 10, 2005 Re: feedback wanted: DLlist.d - doubly linked list implementation in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to clayasaurus | 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 10, 2005 Re: feedback wanted: DLlist.d - doubly linked list implementation in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to clayasaurus | 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 10, 2005 Re: feedback wanted: DLlist.d - doubly linked list implementation in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Andrew Fedoniouk | "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 Re: feedback wanted: DLlist.d - doubly linked list implementation in D | ||||
---|---|---|---|---|
| ||||
Posted in reply to Ben Hinkle | >> 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)
|
Copyright © 1999-2021 by the D Language Foundation