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...!

"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

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

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


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...!

Johannes Pfau <spam example.com> writes:

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

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 :(

Johannes Pfau <spam example.com> writes:

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

"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

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

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
--

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 :).

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

 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
--

 
 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 :).

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.

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.

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?

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. 

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

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 ;)

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 :)

"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

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...!

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

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

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

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

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.

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 

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

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

 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

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

 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.

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

 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?

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

 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.

"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

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.

"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

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

"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

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;
     }

"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

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...!
begin 644 container.d.tar.gz
M'XL(`!T<EDT``]0\_7/;-I;]&7\%DLNT8E:6[33=WL5)YFS':3U-ZHZM-'O3
MZ60H$I)PI  M0=I6N^W??N\]`"1(D?IPY-M=S^RF(H&'A_>%]P5&*LU#F8IL

M9\\.ON`'#X:1]U?H/,PX_T+J:9BN&+?N_;_IW_X^_YC)/!<IERG/IX*_X?-,
M3;)P-I/IA"=A.BG"B1 PMO_T*7LCQB`LFD\$B(R,^*?(R8^&$5>JR"+Q C_I
M_?3]Q<G%U=7E*==YO%^-&L0!>Q]&F=(OV,?S'\[Y*_[35(V4WK_*XU,WB W/


M'N/_9:\9.U7S128GT_P%OQ3QWB )HVN>9T(`A!C_S[[FO=.`/SLX^,\]/EKP



MK\X^'7XZ&.1W.5<9;9V'.3#UX]D)&R'P <HF^XVA00"8'1?Y5&7Z12MA^ 8$
M%UD<IG(`2_?;Z!$P]J1W<G'QP_#XY-T9S&D(0RDE(*=R)I$V>L!/1*)N<84W
M'! T$V&J6>B))\\7<V'>1P&7FH?\)DP*P=6X?53ZI'?UX83=!0$P88Y\28$_

MA%IXRW%<#I

MYI$,=H]4<Z0?9VK&A205"%-%__JCO2VT(!$-XF+>BD548G$I\B)+$0L8F\ (

M%\1V;MC.'-MQ[VAFYT6^  1W &2T2R3O*B0C0+*)95,XE[`D]EI4/2-\GHN,
MUG%[,-PQ7+S$B19#R[8AX(<:&V8+`Y>1V(1:JTB&:,)N06I6LM$`_^77.G42
M-5DA)'8M:;`%.Z=NK)V$S<K,7ZR/1Z"O<7LQ'7<QT"3N$JE?PCX?;8+16Y%'


M+>F\D74:;=<#ER!=H3,E#Q3X
M[\,X!GDI0>(!+%,XI,)$_ 8O4,!83<#F
M J!-%0:1DX#MZ#T
M0:U`T00 KB*R":W(6N>F.F?:[;MA$KYCY?:0$X`7.'LZ=P;,(0$H%A&B(/-E
M%3F.`)9NE1Q0MC3?DG!CF0$"I:ELRL2]+,A !B;I[6;( `,.+E]![ <("9`<
M9!"M>^:=`FU(>D(W(%.L$Y6CJP%'-$Q&%&)C?NH[. *JXK!$C'.& F %N2F>
M"!2&9<`0F,93`6,0-$B1(X&DXX 9LI<(A^;T%..  SHT'O3[9 -6'6LM)^#Y
MX8`;$IHN>JPW+".(`+:4CB1\&.$XV0B5^\O&OZMH((L^2S)6,ZSCP+_;Y+3_
M*5,W,H:S1H)YOX,MAF2(0`3LTDU]I''&DY::+0L)A(F\.IC0>3,ON(9(*PL3
M#X#F
M6I+G8RQX)6UL.VFK':E.W) 3M_9=`=LV%)4KD>O29P>L,0*78^DHU\K"[C6?

M%,!FV-'*<&?O4I7^)C*%JHL2R\>J2,E5L'%&AVQ!E"ZR$QS;N]E$OAI^/"HI


MZ!:!_Y?UVK,4_HF,1D0CB= RB;I 2S"6V;+1*[?*G[:K[#G-*[=>L0(945F\



MH&54T['_RW+I-;:DC0"9/[G/-Q0+FTU16:=D&.Y24+,96KX:W9#RD+=*OG^9
M;-M$2[98LTT]RNF&&"4E*!]BM`$\#C



M,FE^'0P8QICP^ROM NLRZV!KK.O"N#INSIO!H0'C3_<9A&E% LG2>%!%JXS)
M&>;YP8O(Q&`&N&>+OOD!`Y$I<2)']2<999$13IA,%$1]TUF?<?BSH&_,2W$7


MRP&E",8J22C'SF,5%<AZ&PF#FU36'H<J#Y.R.!R )((4YIA>CP%"!FR_$0F&
MT9JK-%D,&&N;)DG"8(_H_.%2(O;R+A1? ;$K %NV%#K%:CL8XZH:;:.PUG3-

MI/S,((*M'&2/(<:`(`-7PNWR<D,8A14C+5S&2PL/]SY#HMK4$JJ2NDVQJ"&-


M?$Z&+JL8):&&.`S$`G^9'!:$JS^J: L&>99!*"TS4198J]*0T%$XIY(/O-8P
MPJNCN"8`TXE BBH83TBPF-X67:7%F22`6FCA;25216K*EADSQ?18 +&=R53J


MVW'*V`N(ZJV IZZK`G4[FT.49-CZN"P/P8^)4C&$FH^I;`<4KI)GF( V.R%B


MF+7>$`TM-G"=CQMR/"65 "/;5J3AJ-PSSN8LG,_I1$)TX9 > E8%++8=8`B%

MS$[NC4)-O5&8_,>R`U&Q;X7?%(+]39CY^;1C-TOJ9)4(+/>T1J6RX<(A&5 Q
MD483J.U'YK1?XFZY8]LAL3\G$X!2"J LT1%`#O'D? 2,+=?8E* ='/X9'ZWF
M<=DQ5:<+XB,CK%ICPQ(`W:/6/.;3BA8R`'2M9> '2A>VO/BYPJ-&6A ]*J<Z
M.E?(>^]_#I8%L!QX5&]HK.T(?,5:IXHSYG``J5 BGJDC`[,14%G)POS?WR[/
MWKZ_>//AW9F9CZUQW^'A1Y7]=L> K..8" Y`M[FW< M6LREO3`^,ZX1_^_O[
MYKG?$U>^_>]YA 80;.E(J813:T O*%]78(A0FI)A!\%1^?B/VCIOP/M3+;"'

MF_ $KL$ND;6P3>VV-S16`H*7AUOJ8FX7,]$85NZJ=0N9[FY5P]_C?->$J^31
M`C8-4MLS_`]C(']RX$P^&HF"MK7L'$,+;.*+MG,G564)IN;5O2 =IL. -'`K
M[%2%<P-?BV55(5OJ"6W4V;U&)S'3(J&4 DU:0$R7:FEKV26 N`/SU#M>/"M0
M<[P0RI9;V-C;:T7*^9]L";$V<= &IY4]8S[?,:2ASC'7H<5Z8<!=;QC(C\N&


M/>U7\0.K5*?:.ADQUV!G=R^VU1U; :4<![$"'1%LEZU5FYMZ9?J:*F^OT=9$
M6E=)APW 7""*  6$P]DW(B62HT498R`W _A=Q;B>=+W&E,A!XJCY%6BGZ-&U

M6K= F1R6Y^%H,W:_5=DMIFILD;ZDB.V'+%WJZ 5UPO6]NRB4/-N$Z%W>X0H<

M3PAW`=63IS(6*IVX,LK?D$)Q2:$6?VTWP-H\LFT =_A9ZQA(F0#JB:I2PV5/

M+"K.:X-5>N6U)/*OJ`/'7 ')P;ZZ>+5N<[R&I0KAG2!(W7M`/MUHX/(Q916F
M?`E3?H'.IU?2\9*K9*3)%6%P:,-DE5&V,"<<<CGSPVNS4Z\_[>%V&F83OU%L
M\[WN>+->+]R]-YN*VT9]Y*L5=Y'RJ=3FB)&Y9D`'JN8,[(%CU.,2KT)2$D_Y
MN[5>T54.SEG`8T4%Z-SFB&H`NER"E/^%S\I<X<RDL;N<;4PQ:EJK)%K#M6]3
M9\*.9U-=4^<_-]#F92O8L1R19WG-Y

MDP*Y%B_=7)7JBO'J>[8=B!OM!/N(-XWFRIM&XO8*SBESWPCWX1Y06U:SP]3>
MM>J\>60> 3 5:8L#NHP$Z65;:[7MK&ZG43C2O10B&$#UG;W\U4KG3^ZJUBMO


M5Y8I5H)U1XEP!5C7$6&S]:RQ6'7KMKRLK)M 9$[U5F$7QIZ1JL+O]7K0.6.S
MWLNW*KVD/V55+)VJ9A!^FIC`FHK`IBY:4%B9LE2E>_6$0$E RX)"^_ 9/H.R

MTJ<.+9B9%B(,?_QJU"Q8.F:6FI(;QXQS5$U7JCGO:F9U0X>Z.DDLQ%JWZSW 
M&JOF=099%.WQ4$:.M77<2S]Z-/W'U&=KU:*L]F)["K:MH"R73;=-TM3ZCG=.
MH'>?"=VD365T;>I$1F?7VA]?74UGE&8R;SGY^LWNX"YS-9?X"0M028.!YYK=
MRT`Q,E"\,E!#T_B!YL.9"7II\R$:!&6I40R18)W& Z\S'G"N9*)QK#QRYW=-

MUD^,\GQ J\Z'C5G.-CXOVEC.ZBQ?9Y6-%1+QABRNF5>35;J_">$KC>SNH7O]
MV0^%-`&W-:_M7/:E/N5UPEN)$]O* K2+$]O$ M"::FY;GN8`=H;]5.3E0NSP
M/DP7U)A#M79MK`&VO8W-PC-L/BN3_M9)YW8B?PWQ0I_5HG[$PMUJ1+N-7U5P
M_9O&,\C4;;K:L&TDUK8`<(]4:2/OUM(\?T](?O?X#I
M]&.`#VDBKTV
MW#R1
MS=>9=HM=NPHXRCSMM/&^.MA'CN*?:2HO'P"RIRX/ >Q]`"]E9$K7($-_'NV5


M.7 ;I77K4E5]H6U=H'U"3'5>E<F/`W-W[UX]X#I^[O;!-_*`RV1BGH31 S+C
M< =++%G'T IADWLZL;9QV1S8^PI&&T>D&UC#E3
M'].D<F)._L;,%A=7)+8QXK=)9?RL%>JH^2(FF4]+G=TGU;)FZX>]O&=_W$-^
MS,S:?<)- 2UES PR ?, D6W8+N<EPLPM]-C/ OVSN9$V25J[%[ ;PKZ[#T  
ML+N49H?5:V>/*)T(;^E:6:U^F=8*'C5UPX^:6)\>Q0V)B[JI,I`U.9.I42:3
ML"S,,'?U):*++J8+R+MMY*6 \0,]WLVCVJTG)')5]YN%UZ)W6N7EAH/!`)M2
M7?'4EOVDK 9AB<4"=A?L-"8'(QHY'%2%F(.J+=2.L,2EC_WU^>/_484Q67-X

M-]54;,=?5?,9%=\7>R#BUR`8B=1Y[7[-U3MX8J[5X*KS3-Y 6Z!]^R-^^[<N

MLEG7Q\+!S90"N`T$B<MVQ%BF\3O8+?[LV6=IA[JE7H=P6&`[Y%00/NF L0$X
MZ("2/7K?U7:,=T-IP%'M<2?,/YJ2E=8JYUMLKU]5$68R[]HL__)+.V"7NT;Q
M?;2W9P#S42;"ZZ-_#ED:)/'>O._*^MU/`/BC5S6PRT3IV+-(Q_ AR-JR]Z4%
M*ORI,]18Z BOS3<KJU C5?BU-IINSSC2PP]![\,OO]I(!.V1-4%H.V0D\V1Q
M6L50CWH?P&H%3?K5OBQ" (*UF-6^P+N,5E?RUR*'4^GP?$0C:O0#P>Y$_\S8
M0XR/S4S<3G/V([<^&M\A?HUWQ7X-;HWMSN9A)K7MYJ7>,O`SNEQ`F?9`0%/\



MYG3V68V?'WDZC [$6Q^+UJMO_D42R^O?2[*:]1LPXX[;--9)A7BK%U0P$-=-
M(90MT-5TPJ#DV


M+9*DAOH;=[^J87W67M/B_C4MMMDUK=8]&*O?=D/+(F^<?-,%N?L[,\P947-/


M]%6-V-0 C5."?YE.;)\E1N&6^Z9MVO7_VOO6[C:.(]'[-?P50YY<&Z!`D-3+


M0R0O2RN7(O4:(/X)94IB5R6`)+.]X1" N6VJKM*COW[YUV?H W"E!%%WU+.J
M7HP!(1SX^`K$)$> I;9]'V=9+C(C9<[4.X3T<5*3'7I>6]1:W8O:.YD93VJZ
M+ [#VR

MTLFI;A`<^ITC9/RTAUCF\8L=[J[XDSE(S_00N 0!`(1:F^B+!P_\>;FD8G-B



M5Q2,8FMJ-\Q`?3?< W:.BAD'14WF-^[ H- J/F)E3T!_OQH=`;/,;FP?HN1!


M> 3,&,`AP>6$O09*KO: IJV;XZ6TJ/F40_;5&JL?S,U':%2]*9>4RQ/X-_Q6

MC6C;WZ*KW)O`5>Y-:$>1`L6&WDX.[<I[UMDS'W*0*[N+(7],=U3B4!ON8];/
MJ'Y3UBCWC&M8(:B$\!VT(^7&_,J7VPT7I%[U<X,1 KMJV5IL_V%T-1J7LTC\
MMN->!/6GKN=68SF`L'_,"[*!`9CL\0+_PUS,D*<6S7.0$PGK`\,!- &9QK<(
MBLR.3<PI'5\PS`3MB<"5D50XAMXM,+F1%X,.3B$*4_:[- Z=8[]EBE \5R;-
MZP;KJXA.32?Y.'^#O1'6:];7?GE44A-L;K/^57E+\<B*$]CSV>Q?[:',G\DC
MM=";K?P `:MA5<#T:9;GP#VX


MFK89"1M9$[5+Y*B(25`<-\H))\%A,W;2ZQ&>E3T?[^L"(_M3;*>=JPFO)79+




MMFW/H?GB$.[;4_ PH>GBD\ MNUG:*+$^XC]](!VCV5'5V"7!V7:S8^R+7<\\
M:4A+W7<F63OV)NDM.1%VTD.$D^G=MXH^40S>G OTIAR_^9:SP!R?=`'HXPS0

M__G/7_SXC?HO99K#A"4S?HG?PZ3*XN=B(&""$?*X8%C%B7A3<>NA,ZO*G16/




M`S+;-S+8NEC5*_[0*_XH[Y-5YZ%5#H
M]JK:'.L6^M!%UV=<S_T54D,%4OA'%_"F:ND(O/P[_,QN20&NB3M9-1.WLM,_

M\'.WVA*H9V=33`="2<Q)%<5%F#C%>37<T.F42H2&-8?.QJ62C+!443V%VF6H
MTJY!IWP`;6=8F Y**E90).H,RBXAC(MR-BA1 !J/*X 1(-<6'&C7ZMROL'>K
M%#J
M+?2H(;W:]1(N#E(W>?%0WQ-CZ,EBK(LZU;D:+2]\='PBPJ4DZ_]2YPG'VE F

M&7M*23]&"00Q!I7MLEMP$6OMQVO6PKJD79;U*R4ESRJR8&YZ$1CP?/.2+TMV

M`X==,44=(+6M?&.]/'5?UI^7F_Q+_ ,>,RK/XL>OM5^=Q1*S?HY7'C<GI%23

M5FG_W=286G;9G-\S[!K.!2NW/S^,-0\_X6'4EY`'>1*\<GU`CT3(+`BSZ Q^
M-2X'4_#GMB0A
M8>[!\,Q83\(."!]RVB2U_M4$TUV[9Q[OXWDYFW]UA6D8"GTR7&!B9)VS$N)M
MM\%?#F\ZAZCUDLL#SU$?T$S=V=LR1VU^?C8J_,5X[/1U[`Q< =`;ESH(^E2G

M?+AMUGZ%V\Y.1"1]5<V^GV+)QUIGVVDZ^]O%%]59"1^S+A#C1DHNEEM,2F1?
M\-VH#A%H&U,PH*L..U\&G%B/K*,0E1+[?GZI<!75W8/%16TK%!.KM L<TR[<
MSX6B,I?5+`ZBG&B,[T<:[`:_V:V8CH=,9N*G"Q[M ZFOQ,/H0=)Z4WL(:0J=
M^I_Z')G.3B*4"`Z!FBQZKV)N>O)WP)Z)NPH^L6-2O)PE3,<1,J2 _]]J-BVF


MEFXC<M']WL]U`(][.3CY(N")GN$C].<[*R%9,YIE]/ZHJ8)KG^J,LJ1`O<_8

M(J$H/*MX>,,37B:G(1O<;+2B*VM?'3+S]7;QJ- UFK+X^F ]M"F_I1TC($(S
MC<L5W>F;1TSHX-Y4^^ILJ!J*Q[%UXQP;[;D^Q"=Q`N`;S^')LF->WVHT^QY"


M+\'GIQIN=I (]L2/+Q15?F6X\OYDVBV^5/?. 0,)?J'[B-5&]Y;$`R^%:]0A



MG%[M ']G7:^9D(.6Y51QT.!3Y;_5>MJR5YP.#CRE(7T*$S*)E8*2A"'^45<0

MQZPA>6!-U;23D5=RW#C

M_L$&QI>L10WTNW9-VY?KOD6);G5A*OK T2P]LE'Q'. 7),Y:=WG4?3Q*CK%M
M`?:6 U3_?7Y8.+0Q>^)'\<-^E_KM]S92,\18=B-[C5%&"4J(T51=-QRMIND"
M"F]DKX"= VMS ']F;6?-Y>>;ELUX-]+="BN$F!-?,%^*=5?N:G0[FG2V_+8 
MAS(Z%EL_3Z]_WM(+N]5$=:.&IH2"&PZE2^D8[&\BY=%FR.O6KT22V9]^\MA"

M_LG?2V8GG^F$#I$9796WHZO%56QF+L)"R")6=$5?%'46`6*G[&I/$S0FH%M"
MK^ ,NH5;.V^N:T0OKJ<3&T2S*MH'-JJ[K9-1RODK]!6:4NJB7IR?*Z$<:P0*
M-;Z2;Z975U,( Z1\,R)..YJ0QFK_0"9MGY F:RA;[12D[C?XU,"]%X.:T4[H
M2T`8:%8PO3DM0\60IYX(3`V>ECHC\I/$#TY;UR3Q[_EV(Q]=XIIN_3?'EO"O



MXT$*-K"/W: !%<MJ[BP`3W1Z_>5T/(:46[G;3JK'VR4--`Z'] 7(UEV(];$5


M))M52$%*5 ZGVG"O-ZW\R*XZ_!&I:]=*,K[#N
M-'NE6Z;DUY"\LD6]J:MLJ#XF
MJJ\/'=7]\R$'?#HWB
M!SQ\,=5NY LJ<\>)(D+N?GH=HO<:B^YZC[+NAZ?13?M!>",\/ G84#SM:68V





M8^V<"HN??G*OP/>0A' UHN<P_8D;^5TFF0TT%DEH<XE)&PNG_WKSDD;I25-=
M\*2LF0[7R20 P<B=Z9)2&5XL7"]SR6KX0FS&A4FZ9[J?HA[3%;K3=`UQP"_/



M%?DJA>KM!S16-9(PVB'9/&PJO)[UY':PJ31E)F,U4OWH*)Q,1(:O46F +R(J
M(^H"X,9F-%0IN`O.W3L[W!HK(UH]YX9QRI=YL0?!-?-2T:USDVV3UA!4!2";


M?KRCN5/AB?DNV*/? I[E20'.-!ZJA:]6U`,[!B$?X6W T_EY7<TQTV7*G9*;
MQ$XR/*Z.)Z-]AF<`^O2C*2TOV H8N E^!/Q"8(EX./S(:QH/L1?KEXHPBK!S
M=\M(GK:TI+8CNA7Z!)AYI S3+?>I]1[=;7_:[TV;Y+Y&T,&S_<M?=:UW[L[;
ME0 6U$E>B4IQEE>?9.4\RG3VZ 9JJG:!ZC=PPETOUVRP?^#LFS_V7MB?J6DH
MJ+%W;I-$.%>%P^9]5>*8$AU`G,`N $F8">1SDL\%\[E??%R1W8_N4]3"1QS 

MA<3DVU]6P:.36-?7Y62B\U=;-,P8(D$*9B. FMH-2*,S3/U,2:]I=9)"[$Y2
MB,T5!G"$V?;YRE=V,A%B`LH"ZL\!RP9QGSF?J.X'K(G?XB&U&,1:J"4>>W'=
MD$.#OG-$VQ\A P0D((&%[*$:L\2T( /UWP$GB3$YJ>OB"GPS%#J

M6\D6<Z9Q C'*Y392M$3M$O]FLJ)J)3VE&_.2+HHOU3S-O[P,J[N[I8YWFAF,
M^[("7\I#C.F 9B93:VESL/$P!B"7AN`9_B`HL1O_S"^OJ^>8!)Y)-YN:JUDW
M:[J/IX]U%AV_-/[+^WM[>VEPP:M(?L^R+SWC)3SM0U[V4RR.K&V!X Y^[M$1
MQR8V,O8P,03TJHGULN:Z'N^?%-O!#N//JJ,_9-*&9\%JG!,-5(M]U60_F 5[

M)'<93Y![M_13;_OO[^6<QM,?E\=(Z_4Y._$&YC-LCQ_&LC1'!_A8=,K-18</

MCTOIAB:ZQZI,'BMO[K&>:-[JUOH&L[NIBY^C!-`, B4E"E 1Q=OUUUN>[O%)

MRQJ\\M5$T W('1+8`I:8ZW3;OTP'(Z^=7'M.5EW-9]/.``R^_G4J[BHO_3M]
MJFAVO_\84LOK" YVL\A7]M\JQ92AR4U[>E%UFK]_]85B2/LWHS>CZVHX*OO3

M-R"$R1K3Q`="!/`_8E0XXD)F&]JQS/%PMI-5B#Z"HEC5.3DVDDU_J+C3)< >
M;,.;20<.$A%^WWE%T8-=[4$"LU:R!LA28AW`PWYQ5LF<SD9&$AU1(&*]P,J-
M2JJAB6IA")-\UB9<KNB8;(<TE"\+#A?13HGD4KIA7?5M]39TZF-[)T4RAN`V
MG-H&W0)*]4R'"'0(-BNN/B>]48I)5U<G(G=0Q3O7M3`+UO4..H/J(`619 4:


M4^<"?.G5`OPP4J=G*1?9B)$H?I?!Q"QZ 6,&>$M>`;,.&#DN_SD"N;V:GUTZ



M0Z:_NBUA+9]M[* '""S_0.N_]0I2W2O"H`OOO1A?3-6->WE5;Q4OIS,%MJB 
MKFQ/R0S[CY^JX<T59UKJXC3[YGY[RF4+U/\?(Q>"J?SQ8 0)&)!Y=+[LE"1(

M%M^N; =WJ:<++P&)/X03]AQ.V`9I`\-+N<-[^]-/1?0U7_38"IW"*7H`I>_7
M%:N,1K-AP0$;ST"#N)PNX!A0N=L%^8-M<:ZF9UMJ`0?5&'5P-SV`4\^'_5+O
M'2?2U#R-HK3+*]6W:J<!:`T":MRT_6LT 5A-[>Y!2,DGK61-LO73$HF_=08I

M^/5BLMFA>P%(C0!BZP[0S3?E%+$:BG6W!T\HG%Y!DPL]I]F6K"7?%0+-]"<$

MP9B'H!W*&$(VFV<3C[F'+*7,GSY7$E6T$9II=`P%N(08M=S^ ?H!-"H'Q<[.
MI,D,0\J6<J8.\:OA+20X!VVOXH)VBX<'86LNV0(HV:&M/S8?*VZ9?YJ<P,V 
M+G5PO$T9:=Z%&[6X\FHR ILI!66/"MBOQ6P0H;2 <68 1`L4QZ1>G$W'&! ^
M IB)FXG]SO".YB?]N8<6`"R&%0;XEPHN41#H4UMU>VY>#Q]OR,)VD"Q$ 45G
MJG,THA;;Q4-T9&)M_2&]>2#SJFJ
M`CWL+.+!T)QPWX['>H/&OC(I/M6DM&\9JN[QVXBWF5TAOI\/B\ D A'_R<P5


MPV7`C43KBY6AB()(&P6U>LBMV/SK-Z+>M(X=U3_SA\%[]%+7KZ6?HGNB:^()
M]GJ%,XD=HTPS0:!VT5A% 6N'6RMOW AM^$>[4$Z`Q%1U9`GL/X`]2Z8J3GZ3
MLM[&^Z;O^IQ[;I3IT>ZC_TWDX.).NNW^X>=<T8./;J5H\8^3Z&YZLP,>G4OA
M0+1=Z<5&LJ8$1%-28J#D



M4 L+"%PH\$<HZ!L0X[/_6HP4?U^[?3L>$E",&LNN5;/Z<L0J1CJ%Q0LN?#U2
M`*[*R>AZ,28?!<81$.BA9-V&V1/,\**DL>D,LC:-EY'H*CVH=2<5XY[S,<`L

MT5>%NB-.HWP/DN>='3*P%H-95;Z)T3PAL[3$`"*/K.(LQU`M1 G\2A:=SBX4

M'F>6VG!B^8FFU>I8U8J":L7XMS^^_/?_=(49CRZP4R56`$QD0&R4,A,HZ"8,
MY0N&G(>U+R7J AIPK..S:L8%-`;R(-AV65_"[2[A+R?RM3 )-PUQ4K3\%#G2
M'BG\L:1?,87:1C>CNDHE8Y1Y-;V%UADU(VFI;.H8D^32,7. _BK0"Z/_F1K7

M:'KI6(7BD_829<:WIW%JD/VQ15Y,F^Q/C,PSPCA#WPCVMS.2M,%C1V)]M`)A

MN.7T]OK:_S/%Z R%*VF$A;.[X'I\\^VP1JJX4R'5YJXG,+0,JWE)9B^9H<3'
MJLCM'4^`DZ?.[Y*I+Y"=-VB+$D74,&:/Q(9.W&=5!0:?>A3^74.>ENKVK+JF
MQ+%R#DXH12=<^6 JN1PR"Z<Q^C8M]Z[,N<`C2H >'KHXW,)GGHM[:=.!,YK$
M^'-ZNC:USW:I&K3.]1LI7L87O;[CPRSG;L>MSC 6K`1U%8A^[ICYU!C.W.7T
M M'!L_52F$-+EBLQ\=*0G`P8&;?B8G=Z9FZ1LWHT>6.5S9IXZ`8)G?U!,4G+
M">WU\TC:FQ7S6G"`X8*'PJ:_ZLB: `X)E2-PY8PF"Q=)A(:I9P?7*R;>ZL$D



M[5W2\ "\6B0?H'Q8H*:J;J\5->?"JY PUT&C\*Y)YZARL"UQSQ^[,I)94XP$
MBB\J+XG-S2ZNXBC.(RP:1LNK4E,$_A;[FT^OO?,:2<KJXJA'-EOBE>T %-%?

MJFIV`!.+RAR#B
M'(;*V6A:<Z`.3A7RKU>LH7W3=5RBR )"`]5?U#T[Q%BC>D/'17%IX6H8*6=F
MDB^5XU<K<5TKLTNN`B[!*GF&=QI1C//1^HZ9>W^OBNBG:9,77;^,*O(`=+WR

M-C.W5,$IO%(XY8,R3E $>`65(F$!3\X'&RK&0W=SA^)5:WF ];4+FD7&E5S1
MS+[%7-(\-/3]T+S7Z'SN.IR1M]D?]1 >D\.9UZO:M GYE+7P5O,4X0?%YJ4.

MXK^\6`UX!&YV\(,N;G7X<V?0,W%4O,8BZB"Q>)<L_G7BU2]ES%D,.Q[1_'";
M'Q8G[,0SZ'8EJ;CG!WP#R1,=;I?[!X^T[91R4*,%DRD4X"R6>E"] FFOA.2P
M\^E%!;>S3N]4Z1HPXV4Q6&Z(>C? W#T8S8$>ZUN5:!J[;%)QH2-=XI5RG&%?


MSQ]]H.<55C"-#P,'\;*I?I`/V]51ANF_6U5*7:\2*IZ(9#E4W
M74[:-KK"`EPVM\]*14)U?'MGL+AX_/C19\UETB.EMFC-Y+]:J)PHFA&$PL,(
M.-&76]/$[>N=LR1?FC!D=QT"HT\X(J_Z*M9-<TJV/O=JLK;I]_W556W3NZ G
M  MP3[5/`]U8>BSW5<Z3=T(K3\KHM1=V_QZ*H*8[^T`%;M,#N*?ZI=Y:#SS-

MPK!;?:5C(HYD(>MD84T<B;U;[U1C4P.93&6%/OYQ[8J;<:[!]PR`/XR`Z7XA
M;G:Q`IA_ EF/7`(*L<9E(!HY&0](7Q1\M5EZHH^_YAF'AN;RGQI(K`IHX50!

M/=Z^9O?%R:0>[(U+).+'I('3!_\,/ ,1-XWU=R),3"*7-[&T\K-]EH1-*H!6
M"[YZ?54-A<NLKEEC54.1I5;;;FMJ7QO+KN9WUKD%_E1 _DP$W'4$WNU`_-+]
M. #N!RML2<_#N*)%))=)*JL2.!3OZ/-#D


M^&NG:JST,=O1E>HX0O[((5E4S\ `N9Q..749UC$ZTZ:$.;)HF`2!35:J=\Z!

M9'N/3\3M\GC-K74OD4$UOZDJ=:'?&!8^4A[LK M+)[1D3>+Z96LC&^*6E_V`
M>[%'68[$CCQ,[LA7_[48J8NW(J^"E0K1:A!>/=H5M\.32M9S+,2$9Y K^J3X
M1#C5X&0=0;"5SJA%QZ`%9SN\[/RG0QG)BM%:SM .BY^15V"EMC?4#X,? 4VI
M-+99LN;Z7VRZGS2L*XYSK3J[N%(8TOA)T=E?%,^?%YV.QT#CQ?:_,Q=;=KMQ
M6'?:[03?9(>N,&#UL=/X)=HT]O-)F#O]YX[$K?VUQ_!AL1&)B03$0:U)7!0?


M',9.2?N%BM5P_G6O&L*9CH=_0XSG_M%N6W0R>", `$&=<J8N(?DBX$EUHP%S

MH\I.((%,.NQ5,O]0C.$),+";D,!5OF;.!'Z.T%OUM 4_OT:=<0V$RXT7IMQX


MO7%B]S`C-_]%S%"K-BC_MH?S\?+H5/2$=/"ZN("G&9+93? '\.5PL/`.1=3O
M"X[%OH9B[/FRZTA>,Q4N`N^*7_`DN&`<`'G"*G(V!P<D>BS*U'E)GY6FX62(
M\UUJU6LH7+*^2)6LYV:9RO7<XFX%[+%NQ:'8OT[W0]Z 7#TSJ] 4.M%P,WZH
MYJVM5DQ9]*?J:B478YW.1/\`.W&!05]XXTY$U"%ELC0W['"HQ!NG0BS]Q`$$
M;OX8W^U90P'HPC,>PR<;%)OEH,;X+E._OMO-8<RIU5C9+QP,\>1YMLX1P^5]

MUL(]1Z7?RG'7A-&T,`-%BKP&AESYTBW$JJ%$ZK$*;$U49FWYL<7R(\X/2_4^


M6P+0+_7G4M--59%FU;B\Y?W4BT/^1+-RQ%F<,85_/S]!:O1JQ6E^ZWSE3_;[
M$7B` U\W%_[VSE2/H_AJ&6$O#H1N
M!MGTF`X'PW64H:YNOK*MXB 3$>F*?Z3_EMRN]5A,B(5I!90L-*2Z=FIEOX`J
MV_=/_C>=PB`-SB1[3YY^J.N!]7_,MZ`&*?3E<J\* XK9TMWIJT)_'ZGE';TJ

MZ[!FI!3UF**$AA3SME97F>K(7X/J"=A<31X7LQG:^>'<.(TI":A3:SF$"`\H
M%8]_3Q'J.0WDRG$$$C#J*ILAM\U-\5U%X `D784DJMB7T\CG6C.RO9,0P=FG

MJ^J9_3"1$`M5-OR.AN1Z`>LM:LE^P0\A5R)S*A K'&;>I!1&LQ15/[($L(G[


M:#UW3[P?_IXAV[D:]NK$]HI_0#S[L()$-^R=)6HBZ&=G)T5RVM+"UQ74[4'X
M.CG1$$J4GE4M.X(G*>0G7NQ(QQ'?R!3G!<6)>VU^2)\X!T$Y'C1S] )NHU_\
M.!F/WE2<`,M /BJ*^"PJB`/5&6J?[!+KZ'NH(41N]("E'.0`\A+(JO`[%].4
M(XV<%76V*  $';4Y-%9V(Z8?>2$B<C!LDHQJK]1&VIKD %F1#EGQO[T4=!?V
MCL>:/>EZ\;;C9]Y%/GT+&A)`/SA;]2_GN)N]";/XN\=.-]3MW,,4:%];'65S

M0*TA^'6H$5^YZ?6L>CN:+FI;&:L:VG+4$4*35/9%I"_]>;.RK^7'[<^V_GI-

M)AL.^$ZC<_:\H&M))QY`9RRH(V<)B,DDH">*A===#C,0/IH*66M8PA`.)M*C
M*?'KSA%">RZ6X>[W9<7I7M J6CTZU/6XO3?RU+CB[ISQIW5T/C+^_58]Z1 0
M9E&:XO9$' ZWABI8.8OUHY!2$!,1 !+DPX;`ILAU)NWW_P-1>_`+H3;EZ)=3
MQE_NK,P,48BVEMWBG[3#S"QJ:G>J)]8Q*IPKQS-S]JTL9K72E*$D/^/PR+3L
M<H1$?D3IXYR7,^/EC;T>>"^MPL)]XU0 GJW* H%F:8ICZ1%O0%OBM/'++Z>U


MG+*<H4L%E-8U"(?*92P""5H5+'M%I5IH`9O"N1T.B8ZT<TSXE/M'&+*[=!RZ
MR[2TYS(:(84-)9E9WY>3I'NI!ZGIO,C!.Z9%^BF67BX\+T&<.*;AVU"2I:DH
M;8/D2E"R%%^,0=TP`0LW_+A`CS'GW=&LJHI.K?Z#A3?5BB)$Q-21"Y;R^-=J
M3PM`3BCI6\[>J#W]SEC0F>FE%+Y&S;$-]&F.S?H%IZ,47ZI_ FI"2S3P&Z$[
M-&+%P60HH'&N28A3)G\!!&\8[O-Y<78Y&NLO9%^*]DV!>P`/J_%-N:P!W) K

MX>#BHH5 4-$.5&+9>%M>B)V;P\ZQ&P+NQU\[8U0P6"^%GE:.THAJA7!0)PE+
M28O,8Z^_ #XZ
M+VA5?#W;-NX'":F7$'`R6-*"`GH[X_J;SH_B`_A*"7 ZDG0(FK4KHFHWY/TQ
MYE(+$]ILA0'?+=1-`/]DGR[:)`T.]ZH8P&ZX2IU*]5, 6 "SL9S[.;O4)EHN


MI^8D3RR-T[" BB(2./J4AL_Z&H;-3?47VNE?P?_.Q^W8EN'?N'% _^7"H/Q:
MV HZ_%NQ"8=(8;IK=N6W?5XJ!>.3J,^]`SF]E`(W?J5K26B974Q=4_4#KZ8I

MMJ</"C3X_IG7&S[?FRE^[_S^D_K_SN?X-^?W(]/^6_G[;O'_^&?U-_'B6_7_


M?9;(GB=`S.!&H<.`2_.:Z2?72Q;.6)RU"T$;C)=L\&`Z7'H?0;T+\-+&K\Q)
MP*)6NHDZ1Z/Z6_7:'C_]4/,^TS-Q'\$3^'9P:WU O>;$L5Y=ZS=]?>N$8XV-
MDK[1L/D !Y\J^/%)\A3F4*7=/_^?!/$:YO37XK!.%`?3XOQC3Q_H^,<(`%.`


MHT)"8'Z,T8$`9W72L!D8UP5V49FL$&GTA]]-YRRJXR<L/I(LK+O6ED"%/^6"
MW4!0$KW$FIX,B2?D%$%C83E$)R]YA=U<)SED$L.XK[8HYO+X?<,T16AKR*<&

M5=?87HF&.U8BA'6FE8,2H%P\5_<]PBIG1NH/R#R
M?4NXIU[).T?+`Y4O,),3*7%"%*`ZYZPM(2Y;]1(Q^E"E>2B!4L_]$4 *(;'"




M&USD_M-JINCQ=H?9OI:6WM3C'3X/37'!\ILF!JS+/0][<-Q9!S45-85RSYT6


M"ZT(\WN[%EI=2K^]:T'4*'8;M'1)\OYI%(Y&DT"W!2V,0N>!%7CC,+(;%W>Y
MWF9O'J$;,:E94.0E^_ZGBG9^:E0G"S#NEU+PU<",Y`OC-S8J,!&[&I4S*AO-
MPM&F)U<[V?6KVWEQJ2[/BJ3F137D<5BYG'4/"'DZJ=!)7`U8 ].:GQL>,D/;
M$=!B:CWRH4F+X%(:GV47L5><CVZUEQ!OY[F:V5E5U^5,E[]U 6*_HK SCTE<
M>B"R&T,7W/-00,FJOAW;FHMZ" Q:YVZC(7LKX>P$" 2/(0W!384^\O\P9:[-
M8GQ:HU_%4OW)Z0F%S[H&I(5]!4)GW;<2]/5T-)FS;]D2 :G>AE,H8\Z%B'UP

MH"-I%Z'\J`^(.M0:HGGYIL*FX/\+_B9>0>3XJA-C>*W8R+'Z_^P \C+877B6
MH+]=QIFGY9C>A6SE<D9O(IH(C()>GN%[]JP(7H_J)>M]E^(B.]AH0"OM.>EN


M4MA"P)8^Y/8X?QKTIHT]1V*],;-P<81&=-FDVD34012.,U_+:\^NX3=(\G_J
MR\P^N-R&7N#E6>/J0NUIUNR[^4PCS>D><,+0Y*6F[TTP:$"Q[ *3>STDDXE:

MFY?868W\MNGB!(E>+5J%?HML6Z"[EU U.43P,!U-1O6ENK>"^45VW!E;*L"%

MPERPM!/._0"AXMK)4)A=^"%3PFU?'F/8D$\^*6ZM^(A>1$D9,GK.;[.25M)*
M8?3_T0;DV K+VTJIKX9Q$YU$4E^3%B$-H&`QTJ+/;2`$NF-H\V4+F:_] L1E
M,5I5X%EN^FE-&+6:8:O\FG=NQI*+OAEG$$DA6E:X[* >):Q9!M:];&E^6^1*

MXRD<XN/TCO":9[UA:6YXK'<B,2T(!:`O):=0AQSV'GX`W4)+3`Y_B>)UDKA;
MK7UKZIZF1_]]B'L6KUNOQT?:+I]?/VUOOXYWH.VSU6G[[!>A[8U*[=;G`)Y?
M%6E')\^[4_8LE;A?RN[^Z[;%X,6"*]RVPE=:/O'%%4P&(Y2*4%A4:`%S7Z^F


M85E)6%1\3\?_G"ZTI8W"H\\ ^%OK.0('2(S;=.(U3= SAFS.6$?.7I`PD$9<

MO>V<.>%$Q80=0V^CAB5W,]Q&,[+&K826JVVEM'/E=_(7VD ;ZA)L)$X,RJK7

M:SFZ0V. ]XTVHH,A`D.DY^K'Z6RVA"1ZPE*']BO,]3?Z9Y4V6H(!2RTS3HH+
MI=FU1.N69R\0.YVC]OBI-'M`N?<.K9T+)$=&$8IKSHC"X9V%YO'=C.(OSQW"
M2RC >_-OWMS?<IDRCKU^;^MR#TN27PU

MQ#AWJ
M7<B1JSI1\ $(B*?$<. 3,5 J*/_G]5=?F^%"4H$!5H;Z> 'G37V/D"&_A)L,
M09.$'OTVI5QW,'6H>"2RIH$IIH-%?;M\VQ,X?(DY>P`PXI>>O?6^0#L.4P%%


M$0;:.D'Y'=CM`M+#F,S[F%D:-AUQ!M(V`%Z.) L*,S')IVVR3^B?6!H[M)Z 

M<`!NRHIJB&(/I"_I'/5TFA7` 4.-ZSTRC7D+J^UCW0VW[!;NW1'6W.D5]&<7
MMYE*.?[T4^&VQ7=T8KHZ<8;)"=W)M=6DA\9LSM`F-SV%/X 6.;>RF"(W(6YJ
MM_CBQV^>T>V)"8D ZJ\X'\UL5A->M.$";\"18G:JXN$?]O=L .D0:)'!(HY=
M( ^?F>2LT<<$BI; &4;;I-XQ(T>0C6W$\6+C654.EXJ0*"2 FDA\Q3N; LG=


M#H\H^.+:+1J%_3JK((;&T4LZWP<\GH[!?86X"[952G5P+B) UP'HSJ9Q:_TG

M\PKWWQP*:];W ^*PI&$3WU5/NA)'*'82D]V59461B28%4NE-B//I=5Y_\>7T
MY65U]B9R+,[ =U^5FRC=T(J&PPP`C\.N/L"(C]2R59M8>;JG6"`8AV*!OD.U
MU=9DJ]OA>YN&DDI9K4>AL]'Y5ZZ^FC'%U7#Z(S=3>PT%0N;5A1)?-H^$QPU=


MKN[W^QDO:>C*X:'QFT05;H/Q;=!`3"!(L+FMTX"3Y'<N7*%T"YE9[ B;6SX7




M4(MU+`TZN6H3PT0$.Z=TQ6T&V/>T?NV&AYDWUQW=P);(20\.9"A0RK<?W_64
M$G%0+F<]...6ZP]/?GHF<MF65]/9'`NW:+7=?C<Z*Z0X-C=T$P;S<OLA+DVS
M00?\#S>9+W)[PZ?.[$V;>1RI0P\!!J<UJ/'=Q+0]]*_EJP$+C]9<0A[I3K??
M $V43! `-Z&3:[]Q^";+P]K;L)O*A8V$> ZJ*+ZX]WN06/]1KWC<*YX$Y?A`





MP+^!$<I8)5"3'2F,'F?]T.14UL;Y`TJ1:`)!J9JR*="8!8S+!5:US.JF%$/^
MI6L\EX,F\SA '"CG;9Y^_AN8`.M+)$8:&)IXV4M"&%WPI5FY%NGZI6`:LR<[



MC]&7>E)44.$P5']`8N 1L/L:,!(\Q=>AI?,U9MDF8ZCZL:L9)JR_HZ05Q8IN
MC29;J:DACZ5:;\8HXWLZY[5W*!_APM2Y)D_5`$6;R.*SCZTLH0+^):+R3(O5
MWG<7&L4O+N7HS59:*W,W"E6* LM![<^X2N)NF/E"YV;7D&R=&;QFN58-5_\>
M+T75FGLA-5P.2M:[RA1-!\^>T=E(C>.E+5FX22U[>,+2Y:O;LO!HN/9K+0E<
M#LK1PI-A
ML?-!%?,4%NBJ8RPPB*)5*R.(-E14!TYAR&A;>,)RY/I!G* \-%LQ;<^JHP'F
MG[KM)XQ>Z3''AI;10$<J*DD48$>B _NY!![V'O4>]R(7 &+R',0SU!Y4+4][
MQ6>]X \]J$&VOT<FJU5 =/?WNPDUC/I&V,^.S0A[3WN?]?[0^V-O?Z^WOY_A



M]SG++V*<NF71[V^"]X^T!E<3*MDX9?*DVKZSV4TP7`C9K;L8O:TFS,E$=L[J
M;32[P^],VI+M4/!%; >+%NK,:TX_=^%=N&9AMH`A[LH`U>6^211?5?3*L022
M_F]`Z4)2K`;`'"1P[=UZ6`>/(\%7,:G]/5'2T":RBD$!(3R4Q- IO)K"[J )


MKYQ4;[=C1UOOXV'C1A)RW=-N]C_H=C:8$;(FA&!7[A<!5MM/M[Q F;Q2*(6;
M4QP8[PN(=E!'MBC/SJ:SH;A>V(\>??8I*`?B;-9D*>C*6%Q?5[,OIHNDI=%5
MJCHT`P([LGK5]:?__`--'T)*5IB^IU,.#UZ5YC367PPEQGV8U
M)ZH+..6QR=MSHTXUM&,_(\RXJFFV^CU*LS%)*A$[BOCA."KQ.+NAX"`PT>L:
MGK\^0!_%URB / $5^(1J(P^GH+`JBW/(T$'!>CUHD`AN\D%1U"FFBKW  D)^


MYTZ*%S^\?/4*9/JKG 2)A`01Q=1G4C>]=FZ"JEQ*3E3X:32IX^IM-985JFKI
MX52\FMLRJ3 P/J*]8CH9+^V(;"I24/V8=( !0-^["T"BRS!%(O6*$9H'AN3Q
MOY=A&R:),-WP[K>=<":!GN[A0?$P$KJ %K6#PT"-K/KC.;=7?W_P(*Z9O%'H

M:ZI;W_EOW_G[QY-0>[ 7]J/A.-0K=8S8]*A1$1SWT): [CU1W0P2.ICH4$CQ

M_":O$?\J.",GDVAOC6ET)G/.;6"/&9M,K\OF"` \:]E(I=`$);_MRS0]>&;!
M=F)^%B'W<>CSR]GT!KW;O[H]JZYAY J_T(-]CA,HMHJ?Z2\_J[]"G.AH`L[0
MHWH.&(9)HQ5ICN&K29F"JN$P&3 \+=B*].+I18`N-C4_I*:O0^1N;71<UN$I

M%++B<I-3A<=DVG$!.ODA78 K+EWZ2$"A"46X2,C`OV)"E-B!B"18`_(QQK _
M(B'Z%M+ OXW!09KC?,0WK_XJ>M6I91^C2V[;?3+WS:`<ZB37SV*0X1$7::+%

M.Z8AH9TR8FZOV,I?XHH( CE)KU31&"9N-T!TX \<1XO[D(QP2WIB0 0,\*%3
M4-A_KQ.(3"AB4#HH8,(!Q8&,WHZ&D$C#BMU3

MM=D"ON+:2+\8M3;J?T:0)1C22W1S <1ISNR*\XK>/(R\62AN<`8O'T5>ZG>/

MZP9UGS=V*9<0^OD,ECWXQ^^*5S6D]5$<[W T*8L?IE=E/9J-Z-T(WLWIU9\O





M[,95J5T<G`FZ.0%_H<DUS<C=^':Q XUC`NTPC2T95GA4^`X;J_7#R$CF9V<=
MXOH">6<F-)PLY+'.SXWYVZ3(/W.];)R-X7[]#T!>13W^M?&[C=_M[N+<';S^
MG285#GTC
M!8L="<EUC18V<G/C!.[G]C[*^S(>"#R[XO)=9-<$&<3P(K!<$/N-0-WK(.P4


M!ZT'"2D*U>\6"/Z3QN6N7]26:8[-ZIB5=88.\49OR6LS/+QXB:?KT;"[T6F\
M=N;G*J&BSIZ_V;G\#NF%XO8%FP]E\<BZ9`5/D>$T(I^0YKZ5 !).32X:`;($


M[$=ML>\!AR9J\LL'1<=;G7514G<Y(C!<;&A&'!5]_8V-%H$H[>.^X(YU.`:X
MK7^G9)__]?'Y^'Q\/CX?GX_/Q^?C\_'Y^'Q\/CX?GX^/>OX_Z+SHO``(` ``
`
end

"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

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.

"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

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

"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

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 :)

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

"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

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

"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

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.)

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

 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

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

 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

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

 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

"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

 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

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

 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

"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

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?

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

 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

Emil Madsen <sovende gmail.com> writes:

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

 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?

-- 
// Yours sincerely
// Emil 'Skeen' Madsen

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

 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

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

 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


 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

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

"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

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.

 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