www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - GSoC-2011 project:: Containers

reply Ishan Thilina <ishanthilina gmail.com> writes:
Hi,

I'm the one who posted "Interested in a GSoC project idea-
http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.com&group=digitalmars.D&artnum=132495
" earlier. Before progressing any further I thought it's better to give a
brief introduction about me first( as most of the other fellow participants
have done). I'm a 2nd year undergraduate from the University of Moratuwa, Sri
Lanka who is specializing in the field of Computer science and Engineering. I
have programming experience in C, C++ and Java. I specifically chose this
organization because I like to take new challenges.

So after looking at all the project ideas posted in the wiki I thought that I
should stick to the "Containers" project because data structures are something
that I know of fairly well.

I have been playing with D for few days now. In that period I learned about D,
learned how to use templates and implemented a simple stack using templates.
But most of
the time was spent trying to understand std.container code. Well to be honest
I'm a bit confused now. I observed that std.container contains implementation
for all the 4 containers that are available in D. But I found another set of
implementations of data structures such as List from here (
http://www.dprogramming.com/list.php ). And the latter List doesn't have the
same methods that are in std.container. Why is this? Can anyone point me to a
proper direction so that I could study exactly what I need to study rather
than looking at all the code in the std.container?

Thank you...!
Mar 25 2011
next sibling parent reply "Vladimir Panteleev" <vladimir thecybershadow.net> writes:
On Fri, 25 Mar 2011 12:12:08 +0200, Ishan Thilina <ishanthilina gmail.com>  
wrote:

 But I found another set of
 implementations of data structures such as List from here (
 http://www.dprogramming.com/list.php ). And the latter List doesn't have  
 the same methods that are in std.container. Why is this?

dprogramming.com is the personal website of Christopher Miller, and it's not affiliated with the D Programming Language. The code you'll find there are Chris's own projects and libraries. Christopher's List class was also written in 2006, way before std.container or even D2 existed. -- Best regards, Vladimir mailto:vladimir thecybershadow.net
Mar 25 2011
next sibling parent reply Ishan Thilina <ishanthilina gmail.com> writes:
   >> But I found another set of
   >> implementations of data structures such as List from here (

   >> http://www.dprogramming.com/list.php ). And the latter List doesn't have
the
same methods that are in std.container. Why is this?

dprogramming.com is the personal website of Christopher Miller, and it's not

own >projects and libraries.
Christopher's List class was also written in 2006, way before std.container or

--
Best regards,
 Vladimir

Ohh, Seems like that I have confused the things :s. Sorry for the mistake. I began to look at ranges, the concept is still new to me. I think I'll understand more about the implementation of std.container after getting used to ranges. Somebody please correct me if I'm taking a wrong turn. Thank you...!
Mar 25 2011
next sibling parent reply Ishan Thilina <ishanthilina gmail.com> writes:
Understanding ranges first is probably a good idea.
This article from Andrei could be helpful:
http://www.informit.com/articles/article.aspx?p=1407357

--
Johannes Pfau

The link is not working :(
Mar 25 2011
next sibling parent reply Ishan Thilina <ishanthilina gmail.com> writes:
  steve & Johannes: Yeah, it works for me now :). I informed the site owners
about
this and he has rectified it :)

 Denis:

You are right, indeed. To say it shortly, ranges are D's version of iterators or

complicated, rather opaque types, various bugs remaining), but globally
extremely

even >more to collections: if you wish to implement new collections for D, it is certainly required that they hold range factories for iteration. Sometimes, more than one (eg >tree traversal breadth-first vs depth-first, leaves only...).
About D collections: aside std.container in Phobos, Steven Schweighoffer has a

http://www.dsource.org/projects>/dcollections. As I understand it, it is a bit of a concurrent for std.container, but there seems to be a possibility for them to converge in the future. In >any case, >you should definitely study it, if only to take inspiration and avoid double work.
Use the D learn mailing list to ask people for help in understanding D's more

Denis
--

Thank you very much for that helpful answer. The biggest challenge now i have is to find good resources to learn about ranges. Any suggestions ? I'll look at the dcollections. I didn't know such a thing existed. It will be a great help for me :).
Mar 25 2011
parent reply Lutger Blijdestijn <lutger.blijdestijn gmail.com> writes:
Ishan Thilina wrote:

   steve & Johannes: Yeah, it works for me now :). I informed the site
 owners about this and he has rectified it :)
 
  Denis:
 
You are right, indeed. To say it shortly, ranges are D's version of
iterators or

(somewhat
complicated, rather opaque types, various bugs remaining), but globally
extremely

applies even >more to collections: if you wish to implement new collections for D, it is certainly required that they hold range factories for iteration. Sometimes, more than one (eg >tree traversal breadth-first vs depth-first, leaves only...).
About D collections: aside std.container in Phobos, Steven Schweighoffer
has a

http://www.dsource.org/projects>/dcollections. As I understand it, it is a bit of a concurrent for std.container, but there seems to be a possibility for them to converge in the future. In >any case, >you should definitely study it, if only to take inspiration and avoid double work.
Use the D learn mailing list to ask people for help in understanding D's
more

Denis
--

Thank you very much for that helpful answer. The biggest challenge now i have is to find good resources to learn about ranges. Any suggestions ?

Boostcon 2009 talk 'iterators must go' also recommended: http://blip.tv/file/2432106 The docs and sourcecode of std.range and std.algorithm is most relevant though, and this newsgroup or .learn for discussion and questions.
 I'll look at the dcollections. I didn't know such a thing existed. It will
 be a great help for me :).

Mar 26 2011
next sibling parent Ishan Thilina <ishanthilina gmail.com> writes:
- "Jonathan M Davis" wrote:

I keep
thinking that I should write one (since no one else has AFAIX), but I haven't
gotten around to it.

If such a guide exists that would be a great help for me :). -"Lutger Blijdestijn" wrote:
The docs and sourcecode of std.range and std.algorithm is most relevant
though, and this newsgroup or .learn for discussion and questions.

To be honest I didn't understand most of the things in the std.container at first. But after half-reading( could read only till the 11th page :s) Andrei's article on ranges and by taking a look at iterators in C++ I think I'll be able to do something :). In these days my main focus is to grasp the concept of Ranges properly.
Mar 26 2011
prev sibling parent reply Ishan Thilina <ishanthilina gmail.com> writes:
As to my understanding algorithms are seperated from the containers so that the
code is maintainable. But in std.container I can see that all the algorithms are
in the container method definitions. Why is this? Have I got the things
incorrectly?
Mar 27 2011
next sibling parent Lutger Blijdestijn <lutger.blijdestijn gmail.com> writes:
Ishan Thilina wrote:

 As to my understanding algorithms are seperated from the containers so
 that the code is maintainable. But in std.container I can see that all the
 algorithms are in the container method definitions. Why is this? Have I
 got the things incorrectly?

Slightly, D ranges use the same basic principles as the STL so any documentation on that can be used to understand the big picture. You'll see that no container implements all of std.algorithm, in fact containers have a very small interface. Normally algorithms work with different kinds of ranges and containers can provide one or more ranges, thus achieving very loose coupling and reuse. If a container provides a certain range then *all* algorithms which operate on that kind of range will work with the container. For example, any container that can be accessed with a random access range can be used by std.sort. However, containers usually have more to offer than what can be expressed by ranges. std.container documents a large set of methods that particular containers can implement as they see fit, as a convention. These methods are usually specific to a particular container implementation and necessary to use a container or take advantage of it's specific properties.
Mar 27 2011
prev sibling parent reply Ishan Thilina <ishanthilina gmail.com> writes:
Lutger Blijdestijn wrote:

Slightly, D ranges use the same basic principles as the STL so any
documentation on that can be used to understand the big picture.

You'll see that no container implements all of std.algorithm, in fact
containers have a very small interface. Normally algorithms work with
different kinds of ranges and containers can  provide one or more ranges,
thus achieving very loose coupling and reuse. If a container provides a
certain range then *all* algorithms which operate on that kind of range will
work with the container. For example, any container that can be accessed
with a random access range can be used by std.sort.

However, containers usually have more to offer than what can be expressed by
ranges. std.container documents a large set of methods that particular
containers can implement as they see fit, as a convention. These methods are
usually specific to a particular container implementation and necessary to
use a container or take advantage of it's specific properties.

Now I get the idea.Algorithms can work on the ranges that are supplied by the container and provide a useful output( if that range is supported by the algorithm of course).Thank you for sorting things out :). Steven Schveighoffe wrote:
If you compare RBNode in std.container and RBNode in dcollections, you'll
find them virtually identical (little cleanup here and there).

Sure they seem to be identical :).
I think Deque would be a good one, even though it's implementation is not

implementation is based on builtin arrays), so the port would be more
involved.  You could also take the Link implementation (dual-linked list),
but that is simple enough to write from scratch ;)

I think I am capable of implementing a Deque and a dual-linked list in D.
If you have any questions, do not hesitate to email me at this address.  I
would be a mentor for this.

Thank you. I do have lot's questions regarding this project.As I'm pretty much new to D I'm am not still 100% comfortable with the language. But I'm truly happy about the improvement that I have had in this little time. I'm glad that you are willing to be a mentor for this project. I'll try my best to come up with a solid project proposal :)
Mar 28 2011
parent reply Ishan Thilina <ishanthilina gmail.com> writes:
I can try to answer your questions, but I have not applied to be an
official mentor.  Just want to make that clear.

My previous message was "I would be a mentor for this, but (reasons why I
will not)"

Sorry if that is not what you read.

-Steve

That's ok, You have given me enough encouragement to carry on this project. :-) --------------------------------- The project idea page gives only a brief introduction to the project. From the ongoing conversation in this mailing list I feel that different people different expectations from this project. But it is hard to make everyone happy. (Me my self being new to will need more time to get familiar with the advanced concepts of D.) So I want to know what are the containers that you hope me to implement in phobos? Thank you...!
Mar 29 2011
next sibling parent bearophile <bearophileHUGS lycos.com> writes:
Fawzi Mohamed:

 Also variations of those presented in Purely Functional Data  
 Structures of Chris Okasaki, would be nice to have.

A finger tree seems useful. Bye, bearophile
Mar 29 2011
prev sibling parent reply Jonathan M Davis <jmdavisProg gmx.com> writes:
On 2011-03-29 12:32, spir wrote:
 On 03/29/2011 08:34 PM, Ishan Thilina wrote:
 I can try to answer your questions, but I have not applied to be an
 official mentor.  Just want to make that clear.
 
 My previous message was "I would be a mentor for this, but (reasons why
 I will not)"
 
 Sorry if that is not what you read.
 
 -Steve

That's ok, You have given me enough encouragement to carry on this project. :-) --------------------------------- The project idea page gives only a brief introduction to the project. From the ongoing conversation in this mailing list I feel that different people different expectations from this project. But it is hard to make everyone happy. (Me my self being new to will need more time to get familiar with the advanced concepts of D.) So I want to know what are the containers that you hope me to implement in phobos?

I have in mind a general Tree & Node, or TreeNode idea; especially implementing all common tree traversal schemes (including leaves only) and the background mechanisms to insert/remove/change given nodes and search/count/replace given values. It may not be used as is --because various tree kinds actually are very different-- but could be highly useful, I guess, either as template or as supertype to be derived from. Comments? (I would probably do it anyway.)

I'm not sure that what you're describing would really be appropriate for std.container. It sounds like what you want isn't really a container but rather the building blocks for a container. What really need at this point is more of the basic container types that your average standard library has. We only really have a vector/ArrayList type (Array), a singly-linked list (SList), and a red-black tree (RedBlackTree). I think that the only thing that we really have in std.container beyond those is BinaryHeap which seems to be more of a container wrapper than a proper container. The fancier stuff would be nice, but we don't even have a doubly-linked list yet. We should get the simpler stuff sorted out before we get particularly fancy, not to mention that it's usually the simple stuff that gets heavily used. - Jonathan M Davis
Mar 29 2011
parent reply dsimcha <dsimcha yahoo.com> writes:
== Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article
 The fancier stuff would be nice, but we don't even have a doubly-linked list
 yet. We should get the simpler stuff sorted out before we get particularly
 fancy, not to mention that it's usually the simple stuff that gets heavily
 used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.
Mar 29 2011
parent reply Daniel Gibson <metalcaedes gmail.com> writes:
Am 30.03.2011 01:55, schrieb Jonathan M Davis:
 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article

 The fancier stuff would be nice, but we don't even have a doubly-linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers that is on the short list of containers that pretty much every standard library has. - Jonathan M Davis

It may be feasible to enhance the single-linked list to support both single- and double linking, via an additional template-parameter "bool doubly" or something like that and some static-ifs in the implementation. I once created a simple single/double-linked queue for D1 like that. Cheers, - Daniel
Mar 30 2011
next sibling parent reply KennyTM~ <kennytm gmail.com> writes:
On Mar 30, 11 16:18, Daniel Gibson wrote:
 Am 30.03.2011 01:55, schrieb Jonathan M Davis:
 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article

 The fancier stuff would be nice, but we don't even have a doubly-linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers that is on the short list of containers that pretty much every standard library has. - Jonathan M Davis

It may be feasible to enhance the single-linked list to support both single- and double linking, via an additional template-parameter "bool doubly" or something like that and some static-ifs in the implementation. I once created a simple single/double-linked queue for D1 like that. Cheers, - Daniel

It is always possible to combine types together with 'static if', but the structure and interface is sufficiently different that doubly-linked list should better be a separate type.
Mar 30 2011
parent reply Daniel Gibson <metalcaedes gmail.com> writes:
Am 30.03.2011 10:27, schrieb KennyTM~:
 On Mar 30, 11 16:18, Daniel Gibson wrote:
 Am 30.03.2011 01:55, schrieb Jonathan M Davis:
 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article

 The fancier stuff would be nice, but we don't even have a
 doubly-linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers that is on the short list of containers that pretty much every standard library has. - Jonathan M Davis

It may be feasible to enhance the single-linked list to support both single- and double linking, via an additional template-parameter "bool doubly" or something like that and some static-ifs in the implementation. I once created a simple single/double-linked queue for D1 like that. Cheers, - Daniel

It is always possible to combine types together with 'static if', but the structure and interface is sufficiently different that doubly-linked list should better be a separate type.

Is it? It's just a few additional functions and the functions do some additional stuff (mostly handling prev-pointers) for double-linked lists. Much of the single-linked list code can (probably) be reused - so why duplicate code?
Mar 30 2011
next sibling parent reply KennyTM~ <kennytm gmail.com> writes:
On Mar 30, 11 16:41, Daniel Gibson wrote:
 Am 30.03.2011 10:27, schrieb KennyTM~:
 On Mar 30, 11 16:18, Daniel Gibson wrote:
 Am 30.03.2011 01:55, schrieb Jonathan M Davis:
 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article

 The fancier stuff would be nice, but we don't even have a
 doubly-linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers that is on the short list of containers that pretty much every standard library has. - Jonathan M Davis

It may be feasible to enhance the single-linked list to support both single- and double linking, via an additional template-parameter "bool doubly" or something like that and some static-ifs in the implementation. I once created a simple single/double-linked queue for D1 like that. Cheers, - Daniel

It is always possible to combine types together with 'static if', but the structure and interface is sufficiently different that doubly-linked list should better be a separate type.

Is it? It's just a few additional functions and the functions do some additional stuff (mostly handling prev-pointers) for double-linked lists. Much of the single-linked list code can (probably) be reused - so why duplicate code?

No, the big difference is you can't move backward in a singly-linked list. So, for instance, SList can only have linearRemove, while (doubly-linked) List can have a constant-time remove. If code duplication is a problem, create a utility function or inherit from a private class. These are implementation details. It should not make them share the same public API.
Mar 30 2011
next sibling parent reply KennyTM~ <kennytm gmail.com> writes:
On Mar 30, 11 21:09, Steven Schveighoffer wrote:
 On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ <kennytm gmail.com> wrote:

 No, the big difference is you can't move backward in a singly-linked
 list. So, for instance, SList can only have linearRemove, while
 (doubly-linked) List can have a constant-time remove.

I hate to point it out, but any linked list implementation, whether it be single or double-linked, which does not support O(1) removal is 100% useless. Might as well use an array. Andrei, you really need to fix that. -Steve

You can't O(1) remove an arbitrary range from an SList. O(1) removal is possible only if you also know an iterator right before the range.
Mar 30 2011
parent reply KennyTM~ <kennytm gmail.com> writes:
On Mar 30, 11 23:01, Steven Schveighoffer wrote:
 And yes, you can, if you have a pointer to the element right before the
 insertion/removal point.

That what I've said in the previous post. The point is linearRemove's interface does not take that pointer. /// Removes a range from the list in linear time. Range linearRemove(Range r); Perhaps SList could provide an O(1) .removeAfter method, like: /// Remove elements in the range [r.front+1 .. $) Range removeAfter(Range r) { // add checking yourself. r._head._next = null; return Range(null); } or an O(1) .removeOneAfter which may be more useful than chopping the whole tail: /// Remove one element in at r.front+1 /// and return the range [r.front+2 .. $) Range removeOneAfter(Range r) { // add checking yourself. r._head._next = r._head._next._next; r.popFront(); return r; }
Mar 30 2011
parent reply Ishan Thilina <ishanthilina gmail.com> writes:
<<I'm posting this mail for the third time. The earlier posted ones are not yet
displayed in the mailing list :s. So I had to take all the burden to re-type the
things>>

Sorry for being idle in the last few days. But I really needed time to get deep
in
to D and learn about advanced concepts( such as template metaprogramming).

As Mr.Steve Schveighoffer has pointed out, there are lots of things that can be
get from DCollecions. Because most of the code and algorithms are implemented in
it my( or anyone who does the project) primary objective should be to port it to
Phobos. Changing from cursors to ranges and discarding those interfaces( As Mr.
Andrei prefers it ) are some of the key points that should be kept in mind while
doing this porting. Then we will be able to think about more advanced Data
structures( If I have the time after porting the data structures from
DCollections
I think I too can try to implement some advanced containers).It's my personal
feeling that implementing advanced containers is no use if the more simpler ones
that are used day-to-day are not there in phobos. These are my personal
perspectives on the project and I'm willing to hear comments on this.

Also I tried to implement a Queue(which is not available in DCollections) using
my
novice D knowledge. But I get two compiler errors when using it. Can some help
me
to sort out the mess?
The std.container file is attached with this ,at the end of the file you'll find
the code that I added.

( I thought of posting this in .learn list. But as this is much more related my
project work i thought its better to post it here).

Thank you...!
Apr 01 2011
parent reply Ishan Thilina <ishanthilina gmail.com> writes:
The file you attached does not work, gzip says the file end prematurely.

I tried to upload that file three times. In the first two times plainly as the container.d file, and it didn't work( the mail isn't shown on the mailing list). Next I tried to upload the tar.gz file and it worked( also that tar file works in my pc very well :s). I'll give a link from a file sharing site. http://www.filejumbo.com/Download/B83F562EEAEAA694
FYI, I did not implement Queue (or Stack) because it is a simple adapter
on List.  I made an executive decision to avoid adapter classes because I
feel they add little value.  This does not mean you shouldn't implement
it, but I think it belongs more in the higher level types (like map, set,
etc) and have it use an implementation container as it's base.  Andrei?

Yes, It's better if an implementation container can be used as a base to the containers that we going to develop. The existing data structures such as the SList and Array will be highly useful because more concrete data structures can be built up on them.
Apr 01 2011
parent reply Ishan Thilina <ishanthilina gmail.com> writes:
-Steve wrote:

There are several problems with your code.

I'd recommend not putting your code in std.container at first.  It will be
easier to deal with, because people will know which code you wrote and
also it will be better when posting code for questions.

Yes, sorry for that :).
I see two problems right off the bat:

1. your Range!T has two definitions for  property void front(T value)
2. Range!T uses Node, which has no definition.

Rectified, but I still face problems.
I'm guessing you meant Range!T to be a part of Queue?  I'm not sure what
you are doing exactly, because there are no usages of Queue in your code
(i.e. it compiles because none of your templates are instantiated).  If
you want Range to be part of Queue, put it inside the definition of
Queue.  It will make things easier, and not pollute the namespace.
Range!T is not a good name to put in the global namespace.

Yes, I want Range!T to be a part of the Queue. It's a forward range that allows to iterate through he contents of the Queue. I still have the original problem I had. I get this error when I try to compile. " /home/ishan/D/1.d(184): Error: no property 'opCall' for type 'test.Queue!(int).Queue' " What is this 'opCall' property? Is it something related to the instantiating a container? Below is the link for the new source code. It is much easier to read than the previously uploaded one ;). http://www.filejumbo.com/Download/0879EB4AAC636C75
Apr 05 2011
parent Ishan Thilina <ishanthilina gmail.com> writes:
Steve wrote:

Thank you very much :)

After fixing these, it still does not compile, but I don't have time right
now to look at the errors, perhaps you can work through them on your own.
I encourage you to isolate problems with the code and write very small
simple programs to test how the syntax works.  Then post questions to
d.learn with small code examples if you still can't figure out why it
doesn't work.

Thanks for the guidance. I'll do like that :)
Apr 05 2011
prev sibling parent KennyTM~ <kennytm gmail.com> writes:
On Mar 31, 11 02:30, spir wrote:
 On 03/30/2011 05:30 PM, Steven Schveighoffer wrote:
 Do you mean removal of an already accessed node/value? If yes, then
 removal
 can effectively be O(1), but to first get the access (here, via a
 pointer)
 one needs O(n) traversing the list in any case.

Of course. With SList, you need O(n) to get to the element, and then O(n) to remove it once you find it ;)

I guess you refer to the fact that, in a slist, as opposed to doubly linked list, one misses the 'previous' slot needed to insert or remove. Thus, one must re-traverse to reach it. Is it the issue you're evoking? There is a trick to avoid that, wrote it once long ago (since then I have, like you, only used doubly-linked ones). I guess the point is, while traversing to search a given element (by index, value, pattern matching or whatever) to constantly keep track of the previously visited node. Thus, when you get there, you have the needed trio (previous/current/next) available for whatever operation. Denis

Using 'previous' pointer to allow O(1) removal will make this program crash, although I don't know if this is allowed or not: auto r = slist.front; r.popFront(); slist.removeFront(); slist.remove(r); (You don't need 'next' because it is already stored in the 'current' node.)
Mar 30 2011
prev sibling parent reply Daniel Gibson <metalcaedes gmail.com> writes:
Am 30.03.2011 16:15, schrieb spir:
 On 03/30/2011 10:41 AM, Daniel Gibson wrote:
 Am 30.03.2011 10:27, schrieb KennyTM~:
 On Mar 30, 11 16:18, Daniel Gibson wrote:
 Am 30.03.2011 01:55, schrieb Jonathan M Davis:
 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article

 The fancier stuff would be nice, but we don't even have a
 doubly-linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple
 stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers that is on the short list of containers that pretty much every standard library has. - Jonathan M Davis

It may be feasible to enhance the single-linked list to support both single- and double linking, via an additional template-parameter "bool doubly" or something like that and some static-ifs in the implementation. I once created a simple single/double-linked queue for D1 like that. Cheers, - Daniel

It is always possible to combine types together with 'static if', but the structure and interface is sufficiently different that doubly-linked list should better be a separate type.

Is it? It's just a few additional functions and the functions do some additional stuff (mostly handling prev-pointers) for double-linked lists. Much of the single-linked list code can (probably) be reused - so why duplicate code?

The internal mechanisms are different when one has 2-side pointers available (actually simpler, that's why I guess singly-linked lists are rare outside the cons-based functional realm). Denis

Deleting within the list is different, yes, at least if you want to support something else than "delete next element" - in that case you only have to care about the additional pointers. Inserting (at least "insert after this element") is pretty similar, apart from some additional prev-pointers. I mostly thought about the other stuff (insert/remove at front/back) because that were my usecases in my single/double linked queue. Cheers, - Daniel
Mar 30 2011
parent reply Daniel Gibson <metalcaedes gmail.com> writes:
Am 30.03.2011 17:31, schrieb Steven Schveighoffer:
 On Wed, 30 Mar 2011 11:27:19 -0400, Daniel Gibson
 <metalcaedes gmail.com> wrote:

 Am 30.03.2011 16:15, schrieb spir:
 On 03/30/2011 10:41 AM, Daniel Gibson wrote:
 Am 30.03.2011 10:27, schrieb KennyTM~:
 On Mar 30, 11 16:18, Daniel Gibson wrote:
 Am 30.03.2011 01:55, schrieb Jonathan M Davis:
 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article

 The fancier stuff would be nice, but we don't even have a
 doubly-linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple
 stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers that is on the short list of containers that pretty much every standard library has. - Jonathan M Davis

It may be feasible to enhance the single-linked list to support both single- and double linking, via an additional template-parameter "bool doubly" or something like that and some static-ifs in the implementation. I once created a simple single/double-linked queue for D1 like that. Cheers, - Daniel

It is always possible to combine types together with 'static if', but the structure and interface is sufficiently different that doubly-linked list should better be a separate type.

Is it? It's just a few additional functions and the functions do some additional stuff (mostly handling prev-pointers) for double-linked lists. Much of the single-linked list code can (probably) be reused - so why duplicate code?

The internal mechanisms are different when one has 2-side pointers available (actually simpler, that's why I guess singly-linked lists are rare outside the cons-based functional realm). Denis

Deleting within the list is different, yes, at least if you want to support something else than "delete next element" - in that case you only have to care about the additional pointers. Inserting (at least "insert after this element") is pretty similar, apart from some additional prev-pointers. I mostly thought about the other stuff (insert/remove at front/back) because that were my usecases in my single/double linked queue

Insert at back for a singly-linked list is O(n). -Steve

Not if you keep a pointer to the last element. Then it's just last.next = newElem; last = newElem; or similar. But deleting the last element is O(n) (So I only supported that for the doubly-linked queue). Cheers, - Daniel
Mar 30 2011
parent Ishan Thilina <ishanthilina gmail.com> writes:
Well, it seems like that different people have lots of different ideas on the
way
that this project should go. It seems like that double linked list is must for
my
project. ( Personally my opinion too is that it is better to construct the most
used structures rather than trying to code data structures that are rarely used
by
few people).

Just an addition to the things you have been discussing about, how about a
Dequeue?
Mar 30 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 03/30/2011 10:41 AM, Daniel Gibson wrote:
 Am 30.03.2011 10:27, schrieb KennyTM~:
 On Mar 30, 11 16:18, Daniel Gibson wrote:
 Am 30.03.2011 01:55, schrieb Jonathan M Davis:
 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article

 The fancier stuff would be nice, but we don't even have a
 doubly-linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers that is on the short list of containers that pretty much every standard library has. - Jonathan M Davis

It may be feasible to enhance the single-linked list to support both single- and double linking, via an additional template-parameter "bool doubly" or something like that and some static-ifs in the implementation. I once created a simple single/double-linked queue for D1 like that. Cheers, - Daniel

It is always possible to combine types together with 'static if', but the structure and interface is sufficiently different that doubly-linked list should better be a separate type.

Is it? It's just a few additional functions and the functions do some additional stuff (mostly handling prev-pointers) for double-linked lists. Much of the single-linked list code can (probably) be reused - so why duplicate code?

The internal mechanisms are different when one has 2-side pointers available (actually simpler, that's why I guess singly-linked lists are rare outside the cons-based functional realm). Denis -- _________________ vita es estrany spir.wikidot.com
Mar 30 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 03/30/2011 10:55 AM, KennyTM~ wrote:
 On Mar 30, 11 16:41, Daniel Gibson wrote:
 Am 30.03.2011 10:27, schrieb KennyTM~:
 On Mar 30, 11 16:18, Daniel Gibson wrote:
 Am 30.03.2011 01:55, schrieb Jonathan M Davis:
 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article

 The fancier stuff would be nice, but we don't even have a
 doubly-linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers that is on the short list of containers that pretty much every standard library has. - Jonathan M Davis

It may be feasible to enhance the single-linked list to support both single- and double linking, via an additional template-parameter "bool doubly" or something like that and some static-ifs in the implementation. I once created a simple single/double-linked queue for D1 like that. Cheers, - Daniel

It is always possible to combine types together with 'static if', but the structure and interface is sufficiently different that doubly-linked list should better be a separate type.

Is it? It's just a few additional functions and the functions do some additional stuff (mostly handling prev-pointers) for double-linked lists. Much of the single-linked list code can (probably) be reused - so why duplicate code?

No, the big difference is you can't move backward in a singly-linked list. So, for instance, SList can only have linearRemove, while (doubly-linked) List can have a constant-time remove. If code duplication is a problem, create a utility function or inherit from a private class. These are implementation details. It should not make them share the same public API.

I agree. (Esp on not letting implementation details leak out to the public interface). Denis -- _________________ vita es estrany spir.wikidot.com
Mar 30 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 03/30/2011 03:09 PM, Steven Schveighoffer wrote:
 On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ <kennytm gmail.com> wrote:

 No, the big difference is you can't move backward in a singly-linked list.
 So, for instance, SList can only have linearRemove, while (doubly-linked)
 List can have a constant-time remove.

I hate to point it out, but any linked list implementation, whether it be single or double-linked, which does not support O(1) removal is 100% useless. Might as well use an array.

Do you mean removal of an already accessed node/value? If yes, then removal can effectively be O(1), but to first get the access (here, via a pointer) one needs O(n) traversing the list in any case. This, even when the lookup is by index, unlike arrays for which access is O(n) only when looking for a given value. So, for me O(1) removal is half of the story (same reasoning applies to change, insert, slice...). Or do I miss something? As I understand it, link lists are only for "sequential collections" which never change, or only on their front. Thus, I like them for simple lists in the common sense, queue-like collections, or... input/forward ranges ;-). Else, they're close to useless, especiallly in a language like D with it's powerful arrays/slices. Denis -- _________________ vita es estrany spir.wikidot.com
Mar 30 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 03/30/2011 05:01 PM, Steven Schveighoffer wrote:
 On Wed, 30 Mar 2011 10:45:19 -0400, KennyTM~ <kennytm gmail.com> wrote:

 On Mar 30, 11 21:09, Steven Schveighoffer wrote:
 On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ <kennytm gmail.com> wrote:

 No, the big difference is you can't move backward in a singly-linked
 list. So, for instance, SList can only have linearRemove, while
 (doubly-linked) List can have a constant-time remove.

I hate to point it out, but any linked list implementation, whether it be single or double-linked, which does not support O(1) removal is 100% useless. Might as well use an array. Andrei, you really need to fix that. -Steve

You can't O(1) remove an arbitrary range from an SList. O(1) removal is possible only if you also know an iterator right before the range.

If you have a linked list of any type, and can't do O(1) insertion or removal of a single element, then you have failed. Linked list's complete advantage is arbitrary O(1) insertion and removal. Arrays have O(n) insertion and removal, with random access. Why would I ever use SList in its current form when it has the same complexity as but less features than a builtin array?

Because it's O(1) insertion/removal at front (not only of elements, also of sublists).
 And yes, you can, if you have a pointer to the element right before the
 insertion/removal point.

Sure, but what kind of programming sorcery provides this pointer without O(n) traversal? (See my other post).
  This is somewhat ugly, but is the cost of having a
 singly linked list. I can guarantee anyone who knows what they are doing is
 never going to use SList, unless they are just interested in a stack type.

Precisely. It's also very well adapted for input/forward ranges, since all operations happen at front. What do you think? (The kind of ranges that may hold their contents). Note that the semantics of range iteration is clearly analogous to list iteration: while (node) { element = node.element; doSomethingWith(element); node = node.next; } while (! r.empty) { element = f.front; doSomethingWith(element); r.popFront(); } (Only that range vocabulary is imo rather weird: while (r.hasNext) { element = r.nextElement; doSomethingWith(element); r.moveNext(); } ) Denis -- _________________ vita es estrany spir.wikidot.com
Mar 30 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 03/30/2011 05:30 PM, Steven Schveighoffer wrote:
 Do you mean removal of an already accessed node/value? If yes, then removal
 can effectively be O(1), but to first get the access (here, via a pointer)
 one needs O(n) traversing the list in any case.

Of course. With SList, you need O(n) to get to the element, and then O(n) to remove it once you find it ;)

I guess you refer to the fact that, in a slist, as opposed to doubly linked list, one misses the 'previous' slot needed to insert or remove. Thus, one must re-traverse to reach it. Is it the issue you're evoking? There is a trick to avoid that, wrote it once long ago (since then I have, like you, only used doubly-linked ones). I guess the point is, while traversing to search a given element (by index, value, pattern matching or whatever) to constantly keep track of the previously visited node. Thus, when you get there, you have the needed trio (previous/current/next) available for whatever operation. Denis -- _________________ vita es estrany spir.wikidot.com
Mar 30 2011
prev sibling next sibling parent spir <denis.spir gmail.com> writes:
On 03/29/2011 08:34 PM, Ishan Thilina wrote:
 I can try to answer your questions, but I have not applied to be an
 official mentor.  Just want to make that clear.

 My previous message was "I would be a mentor for this, but (reasons why I
 will not)"

 Sorry if that is not what you read.

 -Steve

That's ok, You have given me enough encouragement to carry on this project. :-) --------------------------------- The project idea page gives only a brief introduction to the project. From the ongoing conversation in this mailing list I feel that different people different expectations from this project. But it is hard to make everyone happy. (Me my self being new to will need more time to get familiar with the advanced concepts of D.) So I want to know what are the containers that you hope me to implement in phobos?

I have in mind a general Tree & Node, or TreeNode idea; especially implementing all common tree traversal schemes (including leaves only) and the background mechanisms to insert/remove/change given nodes and search/count/replace given values. It may not be used as is --because various tree kinds actually are very different-- but could be highly useful, I guess, either as template or as supertype to be derived from. Comments? (I would probably do it anyway.) Denis -- _________________ vita es estrany spir.wikidot.com
Mar 29 2011
prev sibling parent Fawzi Mohamed <fawzi gmx.ch> writes:
On 29-mar-11, at 21:32, spir wrote:

 On 03/29/2011 08:34 PM, Ishan Thilina wrote:
 I can try to answer your questions, but I have not applied to be an
 official mentor.  Just want to make that clear.

 My previous message was "I would be a mentor for this, but  
 (reasons why I
 will not)"

 Sorry if that is not what you read.

 -Steve

That's ok, You have given me enough encouragement to carry on this project. :-) --------------------------------- The project idea page gives only a brief introduction to the project. From the ongoing conversation in this mailing list I feel that different people different expectations from this project. But it is hard to make everyone happy. (Me my self being new to will need more time to get familiar with the advanced concepts of D.) So I want to know what are the containers that you hope me to implement in phobos?

I have in mind a general Tree & Node, or TreeNode idea; especially implementing all common tree traversal schemes (including leaves only) and the background mechanisms to insert/remove/change given nodes and search/count/replace given values. It may not be used as is --because various tree kinds actually are very different-- but could be highly useful, I guess, either as template or as supertype to be derived from. Comments? (I would probably do it anyway.)

I would very much like to have also persistent containers. I have implemented a Batched array for example in D1, which can grow on one side, and one can have persistent slices, and pointers to elements that remain fixed. For structures that just grow and multithreaded programming without (or with very limited) locking these structures are very useful. Also variations of those presented in Purely Functional Data Structures of Chris Okasaki, would be nice to have. Fawzi
Mar 29 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On 2011-03-25 05:41, spir wrote:
 About D collections: aside std.container in Phobos, Steven Schweighoffer
 has a fairly advanced project called dcollections:
 http://www.dsource.org/projects/dcollections. As I understand it, it is a
 bit of a concurrent for std.container, but there seems to be a possibility
 for them to converge in the future. In any case, you should definitely
 study it, if only to take inspiration and avoid double work.

dcollections is Steven Schweighoffer's project which has existed since D1. std.container is the container module for Phobos. So, they aren't, strictly speaking related. When designing std.container and planning out how containers should be done in Phobos, Andrei took a different approach than Steve did. So, nothing can be taken from dcollections and simply plopped into std.container. However, dcollections 2.0 does use the Boost license, so the code from there can be refactored to work in std.container. Steve already did that with RedBlackTree. He ported std.RedBlackTree from whatever his red-black tree implementation is in dcollections. So, if it makes sense, code can be taken from dcollections and ported to Phobos (and Steve would obviously be a good guy to talk to about that). However, anyone doing that needs to be aware of the differences in how dcollections works vs how std.container works (e.g. dcollections has cursors whereas std.container uses ranges exclusively). Regardless, a solid understanding of ranges is required to create containers for std.container. At the moment, the only good resources that I'm aware of for learning about them are Andrei's original article, the talk he did at BoostCon 2009 ( http://boostcon.blip.tv/ ) - though that's geared towards C++ - and by reading code. std.range and std.algorithm in particular are based heavily on ranges. We probably do need more articles on ranges though. I keep thinking that I should write one (since no one else has AFAIX), but I haven't gotten around to it. - Jonathan M Davis
Mar 25 2011
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 25 Mar 2011 18:37:26 -0400, Jonathan M Davis <jmdavisProg gmx.com>  
wrote:

 On 2011-03-25 05:41, spir wrote:
 About D collections: aside std.container in Phobos, Steven Schweighoffer
 has a fairly advanced project called dcollections:
 http://www.dsource.org/projects/dcollections. As I understand it, it is  
 a
 bit of a concurrent for std.container, but there seems to be a  
 possibility
 for them to converge in the future. In any case, you should definitely
 study it, if only to take inspiration and avoid double work.

dcollections is Steven Schweighoffer's project which has existed since D1. std.container is the container module for Phobos. So, they aren't, strictly speaking related. When designing std.container and planning out how containers should be done in Phobos, Andrei took a different approach than Steve did. So, nothing can be taken from dcollections and simply plopped into std.container. However, dcollections 2.0 does use the Boost license, so the code from there can be refactored to work in std.container. Steve already did that with RedBlackTree. He ported std.RedBlackTree from whatever his red-black tree implementation is in dcollections. So, if it makes sense, code can be taken from dcollections and ported to Phobos (and Steve would obviously be a good guy to talk to about that). However, anyone doing that needs to be aware of the differences in how dcollections works vs how std.container works (e.g. dcollections has cursors whereas std.container uses ranges exclusively).

Any of the private implementations inside dcollections are usable in std.container, because they do not expose any public interface. In fact, dcollections' types can be separated into two categories -- interfaces and implementations. The implementations have a very raw, unsafe, simple API (no range or cursor support there). The interface types (which BTW are implemented via final classes) expose the common public interface that all dcollections classes have, including ranges and cursors. It is this separation which allowed me to port red black tree to std.container by changing nothing in the red black node implementation. If you compare RBNode in std.container and RBNode in dcollections, you'll find them virtually identical (little cleanup here and there). In fact, I plan to have dcollections' RBTree use std.container's RBNode to avoid code duplication. Unfortunately, red black tree is the most complex part of dcollections, so there is not much else to gain by porting to std.container. I think Deque would be a good one, even though it's implementation is not separate (the implementation is based on builtin arrays), so the port would be more involved. You could also take the Link implementation (dual-linked list), but that is simple enough to write from scratch ;) The Hash is extremely naive and basic, so I'm not sure it's worth copying. I'm not an algorithms expert. Aside from porting dcollections/implementing equivalent types, I think there are some things that would be good to have in phobos: * Conceptual types that use the implementations, such as a map type. These *should* be implementation agnostic as long as you use template constraints to identify the appropriate functions required. Doing this should test the completeness of the functions that the containers define. * Custom allocation. This has increased dcollections' performance significantly. If you have any questions, do not hesitate to email me at this address. I would be a mentor for this, but 1) I don't have much time (not sure what is required) and 2) I have a severe difference of opinion from Andrei on what is good in collections, I don't want to guide someone to designs/code that won't be accepted. -Steve
Mar 28 2011
prev sibling parent spir <denis.spir gmail.com> writes:
On 03/25/2011 12:30 PM, Ishan Thilina wrote:
     >>  But I found another set of
     >>  implementations of data structures such as List from here (

     >>  http://www.dprogramming.com/list.php ). And the latter List doesn't
have the
 same methods that are in std.container. Why is this?

 dprogramming.com is the personal website of Christopher Miller, and it's not

own>projects and libraries.
 Christopher's List class was also written in 2006, way before std.container or

 --
 Best regards,
 Vladimir

Ohh, Seems like that I have confused the things :s. Sorry for the mistake. I began to look at ranges, the concept is still new to me. I think I'll understand more about the implementation of std.container after getting used to ranges. Somebody please correct me if I'm taking a wrong turn. Thank you...!

You are right, indeed. To say it shortly, ranges are D's version of iterators or generators, especially powerful and general. With its own set of issues (somewhat complicated, rather opaque types, various bugs remaining), but globally extremely useful and usable. Most of Phobos2 (the std lib) builds on ranges; this applies even more to collections: if you wish to implement new collections for D, it is certainly required that they hold range factories for iteration. Sometimes, more than one (eg tree traversal breadth-first vs depth-first, leaves only...). About D collections: aside std.container in Phobos, Steven Schweighoffer has a fairly advanced project called dcollections: http://www.dsource.org/projects/dcollections. As I understand it, it is a bit of a concurrent for std.container, but there seems to be a possibility for them to converge in the future. In any case, you should definitely study it, if only to take inspiration and avoid double work. Use the D learn mailing list to ask people for help in understanding D's more advanced features and issues. Denis -- _________________ vita es estrany spir.wikidot.com
Mar 25 2011
prev sibling next sibling parent Johannes Pfau <spam example.com> writes:
Content-Type: text/plain; charset=US-ASCII
Content-Transfer-Encoding: quoted-printable

Ishan Thilina wrote:
Ohh, Seems like that I have confused the things :s. Sorry for the
mistake.

I began to look at ranges, the concept is still new to me. I think
I'll understand more about the implementation of std.container after
getting used to ranges. Somebody please correct me if I'm taking a
wrong turn.

Thank you...!

Understanding ranges first is probably a good idea. This article from Andrei could be helpful: http://www.informit.com/articles/article.aspx?p=3D1407357 --=20 Johannes Pfau
Mar 25 2011
prev sibling next sibling parent Johannes Pfau <spam example.com> writes:
Content-Type: text/plain; charset=ISO-8859-1
Content-Transfer-Encoding: quoted-printable

Ishan Thilina wrote:
Understanding ranges first is probably a good idea.
This article from Andrei could be helpful:
http://www.informit.com/articles/article.aspx?p=3D1407357

--
Johannes Pfau

The link is not working :(

Strange, it works for me. You could also go to Andreis homepage http://erdani.com/ and look for 'Read An=ADdrei's ar=ADti=ADcle "On It=ADer=ADa=ADtion"', it's linked from = there. --=20 Johannes Pfau
Mar 25 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 25 Mar 2011 08:07:21 -0400, Ishan Thilina <ishanthilina gmail.com>  
wrote:

 Understanding ranges first is probably a good idea.
 This article from Andrei could be helpful:
 http://www.informit.com/articles/article.aspx?p=1407357

 --
 Johannes Pfau

The link is not working :(

The link works for me. Googling "On Iteration Alexandrescu" gives that link as its first item. -Steve
Mar 25 2011
prev sibling next sibling parent Andrej Mitrovic <andrej.mitrovich gmail.com> writes:
On 3/26/11, Lutger Blijdestijn <lutger.blijdestijn gmail.com> wrote:
 Boostcon 2009 talk 'iterators must go' also recommended:
 http://blip.tv/file/2432106

Which reminds me to open up a video section on wiki4d. I don't believe there is one already. There's a link to that D conference meeting but there's more videos and presentation about D.
Mar 26 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 29 Mar 2011 01:45:02 -0400, Ishan Thilina <ishanthilina gmail.com>  
wrote:

 I'm glad that you are willing to be a mentor for this project. I'll try  
 my best to
 come up with a solid project proposal :)

I can try to answer your questions, but I have not applied to be an official mentor. Just want to make that clear. My previous message was "I would be a mentor for this, but (reasons why I will not)" Sorry if that is not what you read. -Steve
Mar 29 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article
 
 The fancier stuff would be nice, but we don't even have a doubly-linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers that is on the short list of containers that pretty much every standard library has. - Jonathan M Davis
Mar 29 2011
prev sibling next sibling parent Fawzi Mohamed <fawzi gmx.ch> writes:
I think that a doubly linked list is useful, actually it one should  
implement most things so that the can work on any object that has prev  
and next pointers, and give a templated default list wrapper. That is  
what I did for singly linked lists, and it works well.
Often one wants to avoid allocating lot of small wrappers...

About the containers I did propose the persistent ones, because they  
are useful, and currently there aren't any, whereas for more classic  
dcollection is there (even if not part of phobos).

Fawzi
On 30-mar-11, at 01:55, Jonathan M Davis wrote:

 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article

 The fancier stuff would be nice, but we don't even have a doubly- 
 linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple  
 stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly- linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers that is on the short list of containers that pretty much every standard library has. - Jonathan M Davis

Mar 30 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On 2011-03-30 01:18, Daniel Gibson wrote:
 Am 30.03.2011 01:55, schrieb Jonathan M Davis:
 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article
 
 The fancier stuff would be nice, but we don't even have a doubly-linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers that is on the short list of containers that pretty much every standard library has. - Jonathan M Davis

It may be feasible to enhance the single-linked list to support both single- and double linking, via an additional template-parameter "bool doubly" or something like that and some static-ifs in the implementation. I once created a simple single/double-linked queue for D1 like that.

To what end though? I don't think that that would save you much. While some of the implementation would be the same, so much of it would be different, that you'd practically have two complete types defined in one template. At that point, you might as well create a separate class/struct. It's just simpler to have them separate, and I don't see any real gain in combining them. Having both is great, since there are times that you want one and times when you want the other, but having both SList and DList (or whatever it would be called) as separate types makes sense. - Jonathan M Davis
Mar 30 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ <kennytm gmail.com> wrote:

 No, the big difference is you can't move backward in a singly-linked  
 list. So, for instance, SList can only have linearRemove, while  
 (doubly-linked) List can have a constant-time remove.

I hate to point it out, but any linked list implementation, whether it be single or double-linked, which does not support O(1) removal is 100% useless. Might as well use an array. Andrei, you really need to fix that. -Steve
Mar 30 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 30 Mar 2011 10:45:19 -0400, KennyTM~ <kennytm gmail.com> wrote:

 On Mar 30, 11 21:09, Steven Schveighoffer wrote:
 On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ <kennytm gmail.com> wrote:

 No, the big difference is you can't move backward in a singly-linked
 list. So, for instance, SList can only have linearRemove, while
 (doubly-linked) List can have a constant-time remove.

I hate to point it out, but any linked list implementation, whether it be single or double-linked, which does not support O(1) removal is 100% useless. Might as well use an array. Andrei, you really need to fix that. -Steve

You can't O(1) remove an arbitrary range from an SList. O(1) removal is possible only if you also know an iterator right before the range.

If you have a linked list of any type, and can't do O(1) insertion or removal of a single element, then you have failed. Linked list's complete advantage is arbitrary O(1) insertion and removal. Arrays have O(n) insertion and removal, with random access. Why would I ever use SList in its current form when it has the same complexity as but less features than a builtin array? And yes, you can, if you have a pointer to the element right before the insertion/removal point. This is somewhat ugly, but is the cost of having a singly linked list. I can guarantee anyone who knows what they are doing is never going to use SList, unless they are just interested in a stack type. -Steve
Mar 30 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 30 Mar 2011 11:14:20 -0400, spir <denis.spir gmail.com> wrote:

 On 03/30/2011 03:09 PM, Steven Schveighoffer wrote:
 On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ <kennytm gmail.com> wrote:

 No, the big difference is you can't move backward in a singly-linked  
 list.
 So, for instance, SList can only have linearRemove, while  
 (doubly-linked)
 List can have a constant-time remove.

I hate to point it out, but any linked list implementation, whether it be single or double-linked, which does not support O(1) removal is 100% useless. Might as well use an array.

Do you mean removal of an already accessed node/value? If yes, then removal can effectively be O(1), but to first get the access (here, via a pointer) one needs O(n) traversing the list in any case.

Of course. With SList, you need O(n) to get to the element, and then O(n) to remove it once you find it ;)
 This, even when the lookup is by index, unlike arrays for which access  
 is O(n) only when looking for a given value. So, for me O(1) removal is  
 half of the story (same reasoning applies to change, insert, slice...).  
 Or do I miss something?

insert also requires O(n) even with a reference to the insertion point in SList.
 As I understand it, link lists are only for "sequential collections"  
 which never change, or only on their front. Thus, I like them for simple  
 lists in the common sense, queue-like collections, or... input/forward  
 ranges ;-). Else, they're close to useless, especiallly in a language  
 like D with it's powerful arrays/slices.

A deque has (amortized) O(1) removal and insertion at the front and end of it, plus has random access. A list's main bonus is O(1) removal and insertion inside the list. And if you do not keep track of the number of elements, it should also have O(1) splicing (inserting another list in the middle of a list, or removing a section of a list defined by two end points). -Steve
Mar 30 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 30 Mar 2011 11:27:19 -0400, Daniel Gibson <metalcaedes gmail.com>  
wrote:

 Am 30.03.2011 16:15, schrieb spir:
 On 03/30/2011 10:41 AM, Daniel Gibson wrote:
 Am 30.03.2011 10:27, schrieb KennyTM~:
 On Mar 30, 11 16:18, Daniel Gibson wrote:
 Am 30.03.2011 01:55, schrieb Jonathan M Davis:
 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article

 The fancier stuff would be nice, but we don't even have a
 doubly-linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple
 stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior on insertion, etc. rather than wrapping a library solution to get these features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers that is on the short list of containers that pretty much every standard library has. - Jonathan M Davis

It may be feasible to enhance the single-linked list to support both single- and double linking, via an additional template-parameter "bool doubly" or something like that and some static-ifs in the implementation. I once created a simple single/double-linked queue for D1 like that. Cheers, - Daniel

It is always possible to combine types together with 'static if', but the structure and interface is sufficiently different that doubly-linked list should better be a separate type.

Is it? It's just a few additional functions and the functions do some additional stuff (mostly handling prev-pointers) for double-linked lists. Much of the single-linked list code can (probably) be reused - so why duplicate code?

The internal mechanisms are different when one has 2-side pointers available (actually simpler, that's why I guess singly-linked lists are rare outside the cons-based functional realm). Denis

Deleting within the list is different, yes, at least if you want to support something else than "delete next element" - in that case you only have to care about the additional pointers. Inserting (at least "insert after this element") is pretty similar, apart from some additional prev-pointers. I mostly thought about the other stuff (insert/remove at front/back) because that were my usecases in my single/double linked queue

Insert at back for a singly-linked list is O(n). -Steve
Mar 30 2011
prev sibling next sibling parent Emil Madsen <sovende gmail.com> writes:
--e0cb4e70013fb59606049fb58522
Content-Type: text/plain; charset=ISO-8859-1

On 30 March 2011 10:38, Jonathan M Davis <jmdavisProg gmx.com> wrote:

 On 2011-03-30 01:18, Daniel Gibson wrote:
 Am 30.03.2011 01:55, schrieb Jonathan M Davis:
 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article

 The fancier stuff would be nice, but we don't even have a




 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple stuff
 that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior



 insertion, etc. rather than wrapping a library solution to get these
 features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers


 is on the short list of containers that pretty much every standard
 library has.

 - Jonathan M Davis

It may be feasible to enhance the single-linked list to support both single- and double linking, via an additional template-parameter "bool doubly" or something like that and some static-ifs in the implementation. I once created a simple single/double-linked queue for D1 like that.

To what end though? I don't think that that would save you much. While some of the implementation would be the same, so much of it would be different, that you'd practically have two complete types defined in one template. At that point, you might as well create a separate class/struct. It's just simpler to have them separate, and I don't see any real gain in combining them. Having both is great, since there are times that you want one and times when you want the other, but having both SList and DList (or whatever it would be called) as separate types makes sense. - Jonathan M Davis

Just a question that popped into my mind, how does D's std.container handle cyclic lists? using static if? -- // Yours sincerely // Emil 'Skeen' Madsen --e0cb4e70013fb59606049fb58522 Content-Type: text/html; charset=ISO-8859-1 Content-Transfer-Encoding: quoted-printable <div class=3D"gmail_quote">On 30 March 2011 10:38, Jonathan M Davis <span d= ir=3D"ltr">&lt;<a href=3D"mailto:jmdavisProg gmx.com">jmdavisProg gmx.com</= a>&gt;</span> wrote:<br><blockquote class=3D"gmail_quote" style=3D"margin:0= 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;"> <div><div></div><div class=3D"h5">On 2011-03-30 01:18, Daniel Gibson wrote:= <br> &gt; Am 30.03.2011 01:55, schrieb Jonathan M Davis:<br> &gt; &gt; On 2011-03-29 14:50, dsimcha wrote:<br> &gt; &gt;&gt; =3D=3D Quote from Jonathan M Davis (<a href=3D"mailto:jmdavis= Prog gmx.com">jmdavisProg gmx.com</a>)&#39;s article<br> &gt; &gt;&gt;<br> &gt; &gt;&gt;&gt; The fancier stuff would be nice, but we don&#39;t even ha= ve a doubly-linked<br> &gt; &gt;&gt;&gt; list yet. We should get the simpler stuff sorted out befo= re we get<br> &gt; &gt;&gt;&gt; particularly fancy, not to mention that it&#39;s usually = the simple stuff<br> &gt; &gt;&gt;&gt; that gets heavily used.<br> &gt; &gt;&gt;<br> &gt; &gt;&gt; For the most part I agree, but a doubly linked list might be = **too**<br> &gt; &gt;&gt; simple. Linked lists are so trivial to implement that I&#39;d= tend to roll<br> &gt; &gt;&gt; my own that does exactly what I need with regard additional b= ehavior on<br> &gt; &gt;&gt; insertion, etc. rather than wrapping a library solution to ge= t these<br> &gt; &gt;&gt; features.<br> &gt; &gt;<br> &gt; &gt; A doubly-linked list is on the list of containers that every stan= dard<br> &gt; &gt; library should have or it&#39;s likely to be considered lacking. = I can<br> &gt; &gt; understand rolling your own for specific uses, but _I_ sure don&#= 39;t want<br> &gt; &gt; to be doing that if I don&#39;t have to. If I want a doubly-linke= d list, I<br> &gt; &gt; want to be able to just create a standard one and use it. C++, C#= , and<br> &gt; &gt; Java all have doubly-linked lists in their standard libraries.<br=

&gt; &gt; If no one else ever implements a doubly-linked list for Phobos, I= &#39;ll<br> &gt; &gt; probably do it eventually simply because it&#39;s one of the cont= ainers that<br> &gt; &gt; is on the short list of containers that pretty much every standar= d<br> &gt; &gt; library has.<br> &gt; &gt;<br> &gt; &gt; - Jonathan M Davis<br> &gt;<br> &gt; It may be feasible to enhance the single-linked list to support both<b= r> &gt; single- and double linking, via an additional template-parameter &quot= ;bool<br> &gt; doubly&quot; or something like that and some static-ifs in the impleme= ntation.<br> &gt; I once created a simple single/double-linked queue for D1 like that.<b= r> <br> </div></div>To what end though? I don&#39;t think that that would save you = much. While some of<br> the implementation would be the same, so much of it would be different, tha= t<br> you&#39;d practically have two complete types defined in one template. At t= hat<br> point, you might as well create a separate class/struct. It&#39;s just simp= ler to<br> have them separate, and I don&#39;t see any real gain in combining them. Ha= ving<br> both is great, since there are times that you want one and times when you w= ant<br> the other, but having both SList and DList (or whatever it would be called)= as<br> separate types makes sense.<br> <font color=3D"#888888"><br> - Jonathan M Davis<br> </font></blockquote></div><br><br><div>Just a question that popped into my = mind, how does D&#39;s std.container handle cyclic lists?=A0using static if= ?</div><div><br>-- <br>// Yours sincerely<br>// Emil &#39;Skeen&#39; Madsen= <br> </div> --e0cb4e70013fb59606049fb58522--
Mar 30 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 30 Mar 2011 11:52:15 -0400, Daniel Gibson <metalcaedes gmail.com>  
wrote:

 Am 30.03.2011 17:31, schrieb Steven Schveighoffer:
 On Wed, 30 Mar 2011 11:27:19 -0400, Daniel Gibson
 <metalcaedes gmail.com> wrote:


 Deleting within the list is different, yes, at least if you want to
 support something else than "delete next element" - in that case you
 only have to care about the additional pointers.
 Inserting (at least "insert after this element") is pretty similar,
 apart from some additional prev-pointers.
 I mostly thought about the other stuff (insert/remove at front/back)
 because that were my usecases in my single/double linked queue

Insert at back for a singly-linked list is O(n). -Steve

Not if you keep a pointer to the last element. Then it's just last.next = newElem; last = newElem; or similar. But deleting the last element is O(n) (So I only supported that for the doubly-linked queue).

This is equivalent to keeping a separate insertion point for back-insertion (i.e. can be implemented via insertAfter(node)). But I agree, as long as you don't remove from the end, you can maintain that pointer and abstract the insertBack method. -Steve
Mar 30 2011
prev sibling next sibling parent Jonathan M Davis <jmdavisProg gmx.com> writes:
On 2011-03-30 09:18, Emil Madsen wrote:
 On 30 March 2011 10:38, Jonathan M Davis <jmdavisProg gmx.com> wrote:
 On 2011-03-30 01:18, Daniel Gibson wrote:
 Am 30.03.2011 01:55, schrieb Jonathan M Davis:
 On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisProg gmx.com)'s article
 
 The fancier stuff would be nice, but we don't even have a




doubly-linked
 list yet. We should get the simpler stuff sorted out before we get
 particularly fancy, not to mention that it's usually the simple
 stuff that gets heavily used.

For the most part I agree, but a doubly linked list might be **too** simple. Linked lists are so trivial to implement that I'd tend to roll my own that does exactly what I need with regard additional behavior



on
 insertion, etc. rather than wrapping a library solution to get these
 features.

A doubly-linked list is on the list of containers that every standard library should have or it's likely to be considered lacking. I can understand rolling your own for specific uses, but _I_ sure don't want to be doing that if I don't have to. If I want a doubly-linked list, I want to be able to just create a standard one and use it. C++, C#, and Java all have doubly-linked lists in their standard libraries. If no one else ever implements a doubly-linked list for Phobos, I'll probably do it eventually simply because it's one of the containers


that
 is on the short list of containers that pretty much every standard
 library has.
 
 - Jonathan M Davis

It may be feasible to enhance the single-linked list to support both single- and double linking, via an additional template-parameter "bool doubly" or something like that and some static-ifs in the implementation. I once created a simple single/double-linked queue for D1 like that.

To what end though? I don't think that that would save you much. While some of the implementation would be the same, so much of it would be different, that you'd practically have two complete types defined in one template. At that point, you might as well create a separate class/struct. It's just simpler to have them separate, and I don't see any real gain in combining them. Having both is great, since there are times that you want one and times when you want the other, but having both SList and DList (or whatever it would be called) as separate types makes sense. - Jonathan M Davis

Just a question that popped into my mind, how does D's std.container handle cyclic lists? using static if?

And how would it get a cyclic list? The only linked list of any kind at the moment is SList, which is a singly-linked list. It only has elements in it where you inserted them. There's no way to tell it to insert anything cyclically. Sure, a cyclical list container could be implemented, but none such exists at the moment. std.container is one of the newer modules in Phobos and is still pretty sparse. - Jonathan M Davis
Mar 30 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 30 Mar 2011 14:21:35 -0400, spir <denis.spir gmail.com> wrote:

 On 03/30/2011 05:01 PM, Steven Schveighoffer wrote:
 On Wed, 30 Mar 2011 10:45:19 -0400, KennyTM~ <kennytm gmail.com> wrote:

 On Mar 30, 11 21:09, Steven Schveighoffer wrote:
 On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ <kennytm gmail.com>  
 wrote:

 No, the big difference is you can't move backward in a singly-linked
 list. So, for instance, SList can only have linearRemove, while
 (doubly-linked) List can have a constant-time remove.

I hate to point it out, but any linked list implementation, whether it be single or double-linked, which does not support O(1) removal is 100% useless. Might as well use an array. Andrei, you really need to fix that. -Steve

You can't O(1) remove an arbitrary range from an SList. O(1) removal is possible only if you also know an iterator right before the range.

If you have a linked list of any type, and can't do O(1) insertion or removal of a single element, then you have failed. Linked list's complete advantage is arbitrary O(1) insertion and removal. Arrays have O(n) insertion and removal, with random access. Why would I ever use SList in its current form when it has the same complexity as but less features than a builtin array?

Because it's O(1) insertion/removal at front (not only of elements, also of sublists).

I have O(1) insertion/removal at the end of an array. Just call the end the "front" and you have the same thing. BTW, deque supports O(1) insertion and removal at both ends.
 And yes, you can, if you have a pointer to the element right before the
 insertion/removal point.

Sure, but what kind of programming sorcery provides this pointer without O(n) traversal? (See my other post).

You are not getting it. SList's implementation to remove the element containing 5: auto r = find(mySList[], 5); // O(n) operation mySList.linearRemove(take(r, 1)); // O(n) operation, even though I just searched for the element. Expected implementation: auto r = find(mySList[], 5); // O(n) operation mySList.remove(take(r, 1)); // O(1) operation If the second operation is O(n), *EVEN THOUGH YOU JUST GOT A POINTER TO IT*, then the list is a failure. An SList range should retain enough info to be able to remove its front element, it's not that hard. From en.wikipedia.org: "The principal benefit of a linked list over a conventional array is that the list elements can easily be added or removed without reallocation or reorganization of the entire structure because the data items need not be stored contiguously in memory or on disk. Linked lists allow insertion and removal of nodes at any point in the list, and can do so with a constant number of operations if the link previous to the link being added or removed is maintained during list traversal." -Steve
Mar 30 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 30 Mar 2011 14:30:37 -0400, spir <denis.spir gmail.com> wrote:

 On 03/30/2011 05:30 PM, Steven Schveighoffer wrote:
 Do you mean removal of an already accessed node/value? If yes, then  
 removal
 can effectively be O(1), but to first get the access (here, via a  
 pointer)
 one needs O(n) traversing the list in any case.

Of course. With SList, you need O(n) to get to the element, and then O(n) to remove it once you find it ;)

I guess you refer to the fact that, in a slist, as opposed to doubly linked list, one misses the 'previous' slot needed to insert or remove. Thus, one must re-traverse to reach it. Is it the issue you're evoking? There is a trick to avoid that, wrote it once long ago (since then I have, like you, only used doubly-linked ones). I guess the point is, while traversing to search a given element (by index, value, pattern matching or whatever) to constantly keep track of the previously visited node. Thus, when you get there, you have the needed trio (previous/current/next) available for whatever operation.

Yes, the range should do this. -Steve
Mar 30 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Wed, 30 Mar 2011 14:28:49 -0400, KennyTM~ <kennytm gmail.com> wrote:

 On Mar 30, 11 23:01, Steven Schveighoffer wrote:
 And yes, you can, if you have a pointer to the element right before the
 insertion/removal point.

That what I've said in the previous post. The point is linearRemove's interface does not take that pointer. /// Removes a range from the list in linear time. Range linearRemove(Range r); Perhaps SList could provide an O(1) .removeAfter method, like: /// Remove elements in the range [r.front+1 .. $) Range removeAfter(Range r) { // add checking yourself. r._head._next = null; return Range(null); } or an O(1) .removeOneAfter which may be more useful than chopping the whole tail: /// Remove one element in at r.front+1 /// and return the range [r.front+2 .. $) Range removeOneAfter(Range r) { // add checking yourself. r._head._next = r._head._next._next; r.popFront(); return r; }

So I have an SList!int, and I want to remove a certain element in linear time. How can I do this with SList, even with your primitives? Answer: the really convoluted difficult way: void removeSpecificElement(SList!int mylist, int elem) { if(!mylist.empty && mylist.front() == elem) mylist.removeFront(); else { auto r1 = slist[]; auto r2 = r1; r1.popFront(); while(!r1.empty && r1.front != elem) { r2 = r1; r1.popFront(); } if(!r1.empty) mylist.removeOneAfter(r2); } } Whereas, I'd rather have: mylist.remove(take(find(mylist, elem), 1)); BTW, I realized while reading the docs that this only applies to removal, insertion does have an insertAfter function (though with the range properly implemented, insert becomes possible). -Steve
Mar 30 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 01 Apr 2011 14:44:36 -0400, Ishan Thilina <ishanthilina gmail.com>  
wrote:

 Also I tried to implement a Queue(which is not available in  
 DCollections) using my
 novice D knowledge. But I get two compiler errors when using it. Can  
 some help me
 to sort out the mess?
 The std.container file is attached with this ,at the end of the file  
 you'll find
 the code that I added.

The file you attached does not work, gzip says the file end prematurely. FYI, I did not implement Queue (or Stack) because it is a simple adapter on List. I made an executive decision to avoid adapter classes because I feel they add little value. This does not mean you shouldn't implement it, but I think it belongs more in the higher level types (like map, set, etc) and have it use an implementation container as it's base. Andrei? -Steve
Apr 01 2011
prev sibling next sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Fri, 01 Apr 2011 22:56:07 -0400, Ishan Thilina <ishanthilina gmail.com>  
wrote:

 The file you attached does not work, gzip says the file end prematurely.

I tried to upload that file three times. In the first two times plainly as the container.d file, and it didn't work( the mail isn't shown on the mailing list). Next I tried to upload the tar.gz file and it worked( also that tar file works in my pc very well :s). I'll give a link from a file sharing site. http://www.filejumbo.com/Download/B83F562EEAEAA694
 FYI, I did not implement Queue (or Stack) because it is a simple adapter
 on List.  I made an executive decision to avoid adapter classes because  
 I
 feel they add little value.  This does not mean you shouldn't implement
 it, but I think it belongs more in the higher level types (like map,  
 set,
 etc) and have it use an implementation container as it's base.  Andrei?

Yes, It's better if an implementation container can be used as a base to the containers that we going to develop. The existing data structures such as the SList and Array will be highly useful because more concrete data structures can be built up on them.

There are several problems with your code. I'd recommend not putting your code in std.container at first. It will be easier to deal with, because people will know which code you wrote and also it will be better when posting code for questions. I see two problems right off the bat: 1. your Range!T has two definitions for property void front(T value) 2. Range!T uses Node, which has no definition. I'm guessing you meant Range!T to be a part of Queue? I'm not sure what you are doing exactly, because there are no usages of Queue in your code (i.e. it compiles because none of your templates are instantiated). If you want Range to be part of Queue, put it inside the definition of Queue. It will make things easier, and not pollute the namespace. Range!T is not a good name to put in the global namespace. -Steve
Apr 04 2011
prev sibling parent "Steven Schveighoffer" <schveiguy yahoo.com> writes:
On Tue, 05 Apr 2011 10:44:48 -0400, Ishan Thilina <ishanthilina gmail.com>  
wrote:

 -Steve wrote:

 There are several problems with your code.

 I'd recommend not putting your code in std.container at first.  It will  
 be
 easier to deal with, because people will know which code you wrote and
 also it will be better when posting code for questions.

Yes, sorry for that :).
 I see two problems right off the bat:

 1. your Range!T has two definitions for  property void front(T value)
 2. Range!T uses Node, which has no definition.

Rectified, but I still face problems.
 I'm guessing you meant Range!T to be a part of Queue?  I'm not sure what
 you are doing exactly, because there are no usages of Queue in your code
 (i.e. it compiles because none of your templates are instantiated).  If
 you want Range to be part of Queue, put it inside the definition of
 Queue.  It will make things easier, and not pollute the namespace.
 Range!T is not a good name to put in the global namespace.

Yes, I want Range!T to be a part of the Queue. It's a forward range that allows to iterate through he contents of the Queue. I still have the original problem I had. I get this error when I try to compile. " /home/ishan/D/1.d(184): Error: no property 'opCall' for type 'test.Queue!(int).Queue'

classes cannot be instantiated in-place like in C++. They must be instantiated on the heap with a new statement: auto nnn = new Queue!(int)(1); note, however, that templated constructors are not allowed for classes, there is an open bug report on that (435). I'd recommend using just the variadic constructor: this(T[] values...) { ... } After fixing these, it still does not compile, but I don't have time right now to look at the errors, perhaps you can work through them on your own. I encourage you to isolate problems with the code and write very small simple programs to test how the syntax works. Then post questions to d.learn with small code examples if you still can't figure out why it doesn't work. -Steve
Apr 05 2011