www.digitalmars.com         C & C++   DMDScript  

D - linked lists

reply imr1984 <imr1984_member pathlink.com> writes:
I am very surpised that there isnt a linked list template class in Phobos? Has
someone made one and released it?
Jan 20 2004
next sibling parent "Matthew" <matthew.hat stlsoft.dot.org> writes:
I think there's been a few mentioned in the past.

I'll be working on a whole suite of stuff in Feb/Mar, but I guess that's no
help to you now, eh? ;)

"imr1984" <imr1984_member pathlink.com> wrote in message
news:buioeo$1m0b$1 digitaldaemon.com...
 I am very surpised that there isnt a linked list template class in Phobos?

 someone made one and released it?

Jan 20 2004
prev sibling next sibling parent Vathix <vathix dprogramming.com> writes:
imr1984 wrote:
 I am very surpised that there isnt a linked list template class in Phobos? Has
 someone made one and released it?

I posted mine on www.dprogramming.com/list.php - it's not great but works. You're welcome to improve it or give me suggestions.
Jan 20 2004
prev sibling parent reply Stephan Wienczny <wienczny web.de> writes:
imr1984 wrote:
 I am very surpised that there isnt a linked list template class in Phobos? Has
 someone made one and released it?
 
 

I've written another one. I mentioned it some posts ago... I would have published it, but I don't have webspace... Stephan Wienczny
Jan 20 2004
next sibling parent imr1984 <imr1984_member pathlink.com> writes:
In article <bujk37$316j$1 digitaldaemon.com>, Stephan Wienczny says...
imr1984 wrote:
 I am very surpised that there isnt a linked list template class in Phobos? Has
 someone made one and released it?
 
 

I've written another one. I mentioned it some posts ago... I would have published it, but I don't have webspace... Stephan Wienczny

Jan 20 2004
prev sibling parent reply imr1984 <imr1984_member pathlink.com> writes:
sorry for the double post, i meant to say:

Does it have iterators & double pointer nodes so that you can go back as well as
forwards like the C++ one does?

Im sure you could find a site like www.dprogramming.com that would host it

In article <bujk37$316j$1 digitaldaemon.com>, Stephan Wienczny says...
imr1984 wrote:
 I am very surpised that there isnt a linked list template class in Phobos? Has
 someone made one and released it?
 
 

I've written another one. I mentioned it some posts ago... I would have published it, but I don't have webspace... Stephan Wienczny

Jan 20 2004
parent reply Stephan Wienczny <wienczny web.de> writes:
imr1984 wrote:
 sorry for the double post, i meant to say:
 
 Does it have iterators & double pointer nodes so that you can go back as well
as
 forwards like the C++ one does?
 
 Im sure you could find a site like www.dprogramming.com that would host it
 
 In article <bujk37$316j$1 digitaldaemon.com>, Stephan Wienczny says...
 
imr1984 wrote:

I am very surpised that there isnt a linked list template class in Phobos? Has
someone made one and released it?

I've written another one. I mentioned it some posts ago... I would have published it, but I don't have webspace... Stephan Wienczny


I'll send you a mail as there seems nobody to be responsible for DProgramming (I did not find any email-adress).. Stephan
Jan 20 2004
parent reply imr1984 <imr1984_member pathlink.com> writes:
In article <bujrm3$btt$1 digitaldaemon.com>, Stephan Wienczny says...
imr1984 wrote:
 sorry for the double post, i meant to say:
 
 Does it have iterators & double pointer nodes so that you can go back as well
as
 forwards like the C++ one does?
 
 Im sure you could find a site like www.dprogramming.com that would host it
 
 In article <bujk37$316j$1 digitaldaemon.com>, Stephan Wienczny says...
 
imr1984 wrote:

I am very surpised that there isnt a linked list template class in Phobos? Has
someone made one and released it?

I've written another one. I mentioned it some posts ago... I would have published it, but I don't have webspace... Stephan Wienczny


I'll send you a mail as there seems nobody to be responsible for DProgramming (I did not find any email-adress).. Stephan

The guy who runs dprogramming.com is Vathix, and he uses this forum. his email is vathix dprogramming.com Cant wait to see your class. I would have made my own linked list template, but i didnt want to redo the wheel :)
Jan 20 2004
parent reply Stephan Wienczny <wienczny web.de> writes:
Content-Type: text/plain; charset=us-ascii; format=flowed
Content-Transfer-Encoding: 7bit

imr1984 wrote:

 In article <bujrm3$btt$1 digitaldaemon.com>, Stephan Wienczny says...
 
imr1984 wrote:

sorry for the double post, i meant to say:

Does it have iterators & double pointer nodes so that you can go back as well as
forwards like the C++ one does?

Im sure you could find a site like www.dprogramming.com that would host it

In article <bujk37$316j$1 digitaldaemon.com>, Stephan Wienczny says...


imr1984 wrote:


I am very surpised that there isnt a linked list template class in Phobos? Has
someone made one and released it?

I've written another one. I mentioned it some posts ago... I would have published it, but I don't have webspace... Stephan Wienczny


I'll send you a mail as there seems nobody to be responsible for DProgramming (I did not find any email-adress).. Stephan

The guy who runs dprogramming.com is Vathix, and he uses this forum. his email is vathix dprogramming.com Cant wait to see your class. I would have made my own linked list template, but i didnt want to redo the wheel :)

I'll post it to the newsgroup although I dislike such things...
Jan 20 2004
next sibling parent Georg Wrede <Georg_member pathlink.com> writes:
In article <buk20m$lf9$1 digitaldaemon.com>, Stephan Wienczny says...

Shouldn't line 2 be before line 1?

Check this by InsertingAfter, and then try to backstep,
this should demonstrate the wrong value in iter.next.prev.

void InsertAfter(Node iter, T value)
{
if (!iter) throw new IlleagalIterator("Given iterator does not exists");

Node elem = new Node(value, iter, iter.next);
m_size++;
iter.next = elem;
iter.next.prev = elem;
if (elem.next) elem.next.prev = elem;
}
Jan 20 2004
prev sibling parent reply Georg Wrede <Georg_member pathlink.com> writes:
Sorry for double post, I pressed Send too fast. :-(


In article <buk20m$lf9$1 digitaldaemon.com>, Stephan Wienczny says...

Shouldn't line 2 be before line 1?

Check this by InsertingAfter, and then try to backstep,
this should demonstrate the wrong value in iter.next.prev.

void InsertAfter(Node iter, T value)
{
if (!iter) throw new IlleagalIterator("Given iterator does not exists");

Node elem = new Node(value, iter, iter.next);
m_size++;
iter.next = elem;        // line 1
iter.next.prev = elem;   // line 2 should be before line 1
if (elem.next) elem.next.prev = elem;
}

Oh, and obviously the same for InsertBefore.
Jan 20 2004
parent reply Stephan Wienczny <wienczny web.de> writes:
Georg Wrede wrote:
 Sorry for double post, I pressed Send too fast. :-(
 
 
 In article <buk20m$lf9$1 digitaldaemon.com>, Stephan Wienczny says...
 
 Shouldn't line 2 be before line 1?
 
 Check this by InsertingAfter, and then try to backstep,
 this should demonstrate the wrong value in iter.next.prev.
 
 void InsertAfter(Node iter, T value)
 {
 if (!iter) throw new IlleagalIterator("Given iterator does not exists");
 
 Node elem = new Node(value, iter, iter.next);
 m_size++;
 iter.next = elem;        // line 1
 iter.next.prev = elem;   // line 2 should be before line 1
 if (elem.next) elem.next.prev = elem;
 }
 
 Oh, and obviously the same for InsertBefore.
 
 

Jan 21 2004
parent reply Georg Wrede <Georg_member pathlink.com> writes:
In article <bumat3$17ah$1 digitaldaemon.com>, Stephan Wienczny says...
Georg Wrede wrote:
 Sorry for double post, I pressed Send too fast. :-(
 
 
 In article <buk20m$lf9$1 digitaldaemon.com>, Stephan Wienczny says...
 
 Shouldn't line 2 be before line 1?
 
 Check this by InsertingAfter, and then try to backstep,
 this should demonstrate the wrong value in iter.next.prev.
 
 void InsertAfter(Node iter, T value)
 {
 if (!iter) throw new IlleagalIterator("Given iterator does not exists");
 
 Node elem = new Node(value, iter, iter.next);
 m_size++;
 iter.next = elem;        // line 1
 iter.next.prev = elem;   // line 2 should be before line 1
 if (elem.next) elem.next.prev = elem;
 }
 
 Oh, and obviously the same for InsertBefore.
 
 


On second glance, the code still probably works, even with that mistake! The reason being that the if-line performs actually the same function as line 2, and does it right! Hmm, this uncovers one problem with unit tests. If one sees a unit with lots of unit test code, one tends to intuitively believe that the code is kind of robust and tested. I wonder how M$'s unit tests would look like. :-)
Jan 21 2004
parent reply Stephan Wienczny <wienczny web.de> writes:
Georg Wrede wrote:
Georg Wrede wrote:
 
 On second glance, the code still probably works, even with that
 mistake! The reason being that the if-line performs actually the
 same function as line 2, and does it right!
 
 Hmm, this uncovers one problem with unit tests. If one sees a
 unit with lots of unit test code, one tends to intuitively 
 believe that the code is kind of robust and tested. 
 
 I wonder how M$'s unit tests would look like. :-)
 
 

The code works if there iter has a next element! It there is none it segfaults. The correct version should be: void InsertAfter(Node iter, T value) { if (!iter) throw new IlleagalIterator("Given iterator does not exist"); Node elem = new Node(value, iter, iter.next); // [iter]<-[elem]->[] m_size++; iter.next = elem; // [iter]->[elem] if (elem.next) elem.next.prev = elem; // elem<-[] } You should take a deeper look at the unittest: This unittest does not even compile using a current version dmd! Walter forbid to overload the '++' operator for non basic types... Then look what is tested. I checked only the basics. I think M$ uses this way for unit testing: They write a unit. To test it they write another program using it. Then they sell this program containing the unit. If there are no complains about the program the unit should work ;) Stephan
Jan 21 2004
parent reply imr1984 <imr1984_member pathlink.com> writes:
So is someone going to post a link / post the updated version ?

In article <bumhcm$1i4h$1 digitaldaemon.com>, Stephan Wienczny says...
Georg Wrede wrote:
Georg Wrede wrote:
 
 On second glance, the code still probably works, even with that
 mistake! The reason being that the if-line performs actually the
 same function as line 2, and does it right!
 
 Hmm, this uncovers one problem with unit tests. If one sees a
 unit with lots of unit test code, one tends to intuitively 
 believe that the code is kind of robust and tested. 
 
 I wonder how M$'s unit tests would look like. :-)
 
 

The code works if there iter has a next element! It there is none it segfaults. The correct version should be: void InsertAfter(Node iter, T value) { if (!iter) throw new IlleagalIterator("Given iterator does not exist"); Node elem = new Node(value, iter, iter.next); // [iter]<-[elem]->[] m_size++; iter.next = elem; // [iter]->[elem] if (elem.next) elem.next.prev = elem; // elem<-[] } You should take a deeper look at the unittest: This unittest does not even compile using a current version dmd! Walter forbid to overload the '++' operator for non basic types... Then look what is tested. I checked only the basics. I think M$ uses this way for unit testing: They write a unit. To test it they write another program using it. Then they sell this program containing the unit. If there are no complains about the program the unit should work ;) Stephan

Jan 21 2004
parent reply Stephan Wienczny <wienczny web.de> writes:
imr1984 wrote:
 So is someone going to post a link / post the updated version ?
 

You can get it from: http://d.wienczny.de
Jan 22 2004
next sibling parent reply imr1984 <imr1984_member pathlink.com> writes:
cheers. Are you going to get that site put on the links page ?

In article <bupb1u$1tp$1 digitaldaemon.com>, Stephan Wienczny says...
imr1984 wrote:
 So is someone going to post a link / post the updated version ?
 

You can get it from: http://d.wienczny.de

Jan 22 2004
parent reply Stephan Wienczny <wienczny web.de> writes:
imr1984 wrote:
 cheers. Are you going to get that site put on the links page ?
 
 In article <bupb1u$1tp$1 digitaldaemon.com>, Stephan Wienczny says...
 
imr1984 wrote:

So is someone going to post a link / post the updated version ?

You can get it from: http://d.wienczny.de


Maybe Walter reads this!?!?
Jan 22 2004
parent J Anderson <REMOVEanderson badmama.com.au> writes:
Stephan Wienczny wrote:

 imr1984 wrote:

 cheers. Are you going to get that site put on the links page ?

 In article <bupb1u$1tp$1 digitaldaemon.com>, Stephan Wienczny says...

 imr1984 wrote:

 So is someone going to post a link / post the updated version ?

You can get it from: http://d.wienczny.de


Maybe Walter reads this!?!?

http://f17.aaacafe.ne.jp/%7Elabamba/ http://www.prowiki.org/wiki4d/wiki.cgi?FrontPage -- -Anderson: http://badmama.com.au/~anderson/
Jan 22 2004
prev sibling parent reply imr1984 <imr1984_member pathlink.com> writes:
In article <bupb1u$1tp$1 digitaldaemon.com>, Stephan Wienczny says...
imr1984 wrote:
 So is someone going to post a link / post the updated version ?
 

You can get it from: http://d.wienczny.de

sorry to bring this old subject up again, but id just though id point out that the class doesnt follow the D naming convections. Sorry if im being fussy, its quite nice otherwise. By the way, is there any chance well see generic linked lists being built into the D language?
Jan 29 2004
next sibling parent Stephan Wienczny <wienczny web.de> writes:
imr1984 wrote:
 In article <bupb1u$1tp$1 digitaldaemon.com>, Stephan Wienczny says...
 
imr1984 wrote:

So is someone going to post a link / post the updated version ?

You can get it from: http://d.wienczny.de

sorry to bring this old subject up again, but id just though id point out that the class doesnt follow the D naming convections. Sorry if im being fussy, its quite nice otherwise. By the way, is there any chance well see generic linked lists being built into the D language?

better idea when writing! To the other point: Maybe. When I started my try own d-compiler projekt and thought about the basic types it should support, I came to the conclusion list became something like a basic type. One could have the backend to generate the list code. Stephan
Jan 29 2004
prev sibling parent reply "Matthew" <matthew.hat stlsoft.dot.org> writes:
"imr1984" <imr1984_member pathlink.com> wrote in message
news:bvbth9$27n$1 digitaldaemon.com...
 In article <bupb1u$1tp$1 digitaldaemon.com>, Stephan Wienczny says...
imr1984 wrote:
 So is someone going to post a link / post the updated version ?

You can get it from: http://d.wienczny.de

sorry to bring this old subject up again, but id just though id point out

 the class doesnt follow the D naming convections. Sorry if im being fussy,

 quite nice otherwise.

 By the way, is there any chance well see generic linked lists being built

 the D language?

We're going to be working on the DTL in Feb/Mar.
Jan 29 2004
parent reply imr1984 <imr1984_member pathlink.com> writes:
so that means generic lists will be in the DTL, and not part of the language
itself? shame. Well im happy that at least something official is being made :)

In article <bvc1cg$8if$4 digitaldaemon.com>, Matthew says...
"imr1984" <imr1984_member pathlink.com> wrote in message
news:bvbth9$27n$1 digitaldaemon.com...
 In article <bupb1u$1tp$1 digitaldaemon.com>, Stephan Wienczny says...
imr1984 wrote:
 So is someone going to post a link / post the updated version ?

You can get it from: http://d.wienczny.de

sorry to bring this old subject up again, but id just though id point out

 the class doesnt follow the D naming convections. Sorry if im being fussy,

 quite nice otherwise.

 By the way, is there any chance well see generic linked lists being built

 the D language?

We're going to be working on the DTL in Feb/Mar.

Jan 29 2004
parent reply "Matthew" <matthew.hat stlsoft.dot.org> writes:
 so that means generic lists will be in the DTL, and not part of the

 itself? shame.

Is it a shame? I'm a big fan of the C++/Stroustrup vision where everything that does not _have_ to be in the language goes in the libraries. The difference between C++ and D is that D is new, and we have the ability to put those things that _should_ be in the language in there, rather than having to perform ridiculous mental acrobatics to get the simplest after-the-fact concepts supported. This is well exemplified in the likes of Boost and STLSoft. For my part, I find most of the Boost code utterly impenetrable, and I know several *very* cluey people who feel the same. But I have used similarly complex techniques in the STLSoft libraries, which those same *very* cluey people find equally impenetrable. The point, I think is that C++ is on the verge of being unmanageably complex, and only the authors or diligent students of modern leading-edge libraries can understand them. This is not a good position for a language to be in. It is our intention, with the DTL specifically, that all the wonderful - and they are wonderful, to be sure - things that can be currently be achieved in C++ are also achieveable in D, but in a more inclusive fashion. In other words, there'll be no need for TMP (template meta programming) super-gurus (and the egos they bring along with them), and the code will be accessible to any *reasonably* cluey individual.
 Well im happy that at least something official is being made :)

You should hang fire on that happiness. It might be a load of old crap ... ;)
 In article <bvc1cg$8if$4 digitaldaemon.com>, Matthew says...
"imr1984" <imr1984_member pathlink.com> wrote in message
news:bvbth9$27n$1 digitaldaemon.com...
 In article <bupb1u$1tp$1 digitaldaemon.com>, Stephan Wienczny says...
imr1984 wrote:
 So is someone going to post a link / post the updated version ?

You can get it from: http://d.wienczny.de

sorry to bring this old subject up again, but id just though id point



that
 the class doesnt follow the D naming convections. Sorry if im being



its
 quite nice otherwise.

 By the way, is there any chance well see generic linked lists being



into
 the D language?

We're going to be working on the DTL in Feb/Mar.


Jan 29 2004
parent reply Andy Friesen <andy ikagames.com> writes:
Matthew wrote:

so that means generic lists will be in the DTL, and not part of the

language
itself? shame.

Is it a shame? I'm a big fan of the C++/Stroustrup vision where everything that does not _have_ to be in the language goes in the libraries.

That brings something to mind. Does D still need to have associative arrays built into the language? -- andy
Jan 29 2004
parent "Matthew" <matthew.hat stlsoft.dot.org> writes:
"Andy Friesen" <andy ikagames.com> wrote in message
news:bvcg4d$vhh$2 digitaldaemon.com...
 Matthew wrote:

so that means generic lists will be in the DTL, and not part of the

language
itself? shame.

Is it a shame? I'm a big fan of the C++/Stroustrup vision where


 that does not _have_ to be in the language goes in the libraries.

That brings something to mind. Does D still need to have associative arrays built into the language?

Aha! I was wondering when someone was going to ask that. It does seem arbitrary, to be sure. From a small perspective, the question will be resolved if we manage to write a smaller, faster, easier-to-use ass-arr library. On a larger perspective, it's probably going to seem a little arbitrary to have them in, but I think they're overwhelmingly likely to stay. We'll look back on it all fondly, and recognise the hand of Walter in there. :)
Jan 29 2004