subject:"GSoC\-2011 project\:\: Containers"


Am 30.03.2011 01:55, schrieb Jonathan M Davis:

On 2011-03-29 14:50, dsimcha wrote:

== Quote from Jonathan M Davis (jmdavisp...@gmx.com)'s article


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


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


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

If no one else ever implements a doubly-linked list for Phobos, I'll probably
do it eventually simply because it's one of the containers that is on the
short list of containers that pretty much every standard library has.

- Jonathan M Davis


It may be feasible to enhance the single-linked list to support both 
single- and double linking, via an additional template-parameter bool 
doubly or something like that and some static-ifs in the implementation.

I once created a simple single/double-linked queue for D1 like that.

Cheers,
- Daniel

Re: GSoC-2011 project:: Containers


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 (jmdavisp...@gmx.com)'s article


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


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


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

If no one else ever implements a doubly-linked list for Phobos, I'll
probably
do it eventually simply because it's one of the containers that is on the
short list of containers that pretty much every standard library has.

- Jonathan M Davis


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

Cheers,
- Daniel


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

Re: GSoC-2011 project:: Containers

2011-03-30 Thread Jonathan M Davis

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 (jmdavisp...@gmx.com)'s article
  
  The fancier stuff would be nice, but we don't even have a doubly-linked
  list yet. We should get the simpler stuff sorted out before we get
  particularly fancy, not to mention that it's usually the simple stuff
  that gets heavily used.
  
  For the most part I agree, but a doubly linked list might be **too**
  simple. Linked lists are so trivial to implement that I'd tend to roll
  my own that does exactly what I need with regard additional behavior on
  insertion, etc. rather than wrapping a library solution to get these
  features.
  
  A doubly-linked list is on the list of containers that every standard
  library should have or it's likely to be considered lacking. I can
  understand rolling your own for specific uses, but _I_ sure don't want
  to be doing that if I don't have to. If I want a doubly-linked list, I
  want to be able to just create a standard one and use it. C++, C#, and
  Java all have doubly-linked lists in their standard libraries.
  
  If no one else ever implements a doubly-linked list for Phobos, I'll
  probably do it eventually simply because it's one of the containers that
  is on the short list of containers that pretty much every standard
  library has.
  
  - Jonathan M Davis
 
 It may be feasible to enhance the single-linked list to support both
 single- and double linking, via an additional template-parameter bool
 doubly or something like that and some static-ifs in the implementation.
 I once created a simple single/double-linked queue for D1 like that.

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

- Jonathan M Davis

Re: GSoC-2011 project:: Containers


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 (jmdavisp...@gmx.com)'s article


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


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


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

If no one else ever implements a doubly-linked list for Phobos, I'll
probably
do it eventually simply because it's one of the containers that is on
the
short list of containers that pretty much every standard library has.

- Jonathan M Davis


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

Cheers,
- Daniel


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


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

Re: GSoC-2011 project:: Containers


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 (jmdavisp...@gmx.com)'s article


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


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


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

If no one else ever implements a doubly-linked list for Phobos, I'll
probably
do it eventually simply because it's one of the containers that is on
the
short list of containers that pretty much every standard library has.

- Jonathan M Davis


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

Cheers,
- Daniel


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


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


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


If code duplication is a problem, create a utility function or inherit 
from a private class. These are implementation details. It should not 
make them share the same public API.

Re: GSoC-2011 project:: Containers


On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ kenn...@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

Re: GSoC-2011 project:: Containers


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 (jmdavisp...@gmx.com)'s article


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


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


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

If no one else ever implements a doubly-linked list for Phobos, I'll
probably
do it eventually simply because it's one of the containers that is on
the
short list of containers that pretty much every standard library has.

- Jonathan M Davis


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

Cheers,
- Daniel


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


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


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


Denis
--
_
vita es estrany
spir.wikidot.com

Re: GSoC-2011 project:: Containers


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 (jmdavisp...@gmx.com)'s article


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


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


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

If no one else ever implements a doubly-linked list for Phobos, I'll
probably
do it eventually simply because it's one of the containers that is on
the
short list of containers that pretty much every standard library has.

- Jonathan M Davis


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

Cheers,
- Daniel


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


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


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

If code duplication is a problem, create a utility function or inherit from a
private class. These are implementation details. It should not make them share
the same public API.


I agree. (Esp on not letting implementation details leak out to the public 
interface).


Denis
--
_
vita es estrany
spir.wikidot.com

Re: GSoC-2011 project:: Containers


On Mar 30, 11 21:09, Steven Schveighoffer wrote:

On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ kenn...@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.

Re: GSoC-2011 project:: Containers


On Wed, 30 Mar 2011 10:45:19 -0400, KennyTM~ kenn...@gmail.com wrote:


On Mar 30, 11 21:09, Steven Schveighoffer wrote:

On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ kenn...@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

Re: GSoC-2011 project:: Containers


On 03/30/2011 03:09 PM, Steven Schveighoffer wrote:

On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ kenn...@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

Re: GSoC-2011 project:: Containers


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 (jmdavisp...@gmx.com)'s article


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


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


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

If no one else ever implements a doubly-linked list for Phobos, I'll
probably
do it eventually simply because it's one of the containers that is on
the
short list of containers that pretty much every standard library has.

- Jonathan M Davis


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

Cheers,
- Daniel


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


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


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

Denis


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


Cheers,
- Daniel

Re: GSoC-2011 project:: Containers


On Wed, 30 Mar 2011 11:14:20 -0400, spir denis.s...@gmail.com wrote:


On 03/30/2011 03:09 PM, Steven Schveighoffer wrote:

On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ kenn...@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

Re: GSoC-2011 project:: Containers

On Wed, 30 Mar 2011 11:27:19 -0400, Daniel Gibson metalcae...@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 (jmdavisp...@gmx.com)'s article


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


For the most part I agree, but a doubly linked list might be  
**too**

simple. Linked lists are so trivial to implement that I'd tend to
roll my
own that does exactly what I need with regard additional behavior  
on
insertion, etc. rather than wrapping a library solution to get  
these

features.


A doubly-linked list is on the list of containers that every  
standard

library
should have or it's likely to be considered lacking. I can  
understand

rolling
your own for specific uses, but _I_ sure don't want to be doing that
if I
don't have to. If I want a doubly-linked list, I want to be able to
just
create a standard one and use it. C++, C#, and Java all have
doubly-linked
lists in their standard libraries.

If no one else ever implements a doubly-linked list for Phobos, I'll
probably
do it eventually simply because it's one of the containers that is  
on

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


- Jonathan M Davis


It may be feasible to enhance the single-linked list to support both
single- and double linking, via an additional template-parameter  
bool

doubly or something like that and some static-ifs in the
implementation.
I once created a simple single/double-linked queue for D1 like that.

Cheers,
- Daniel


It is always possible to combine types together with 'static if', but
the structure and interface is sufficiently different that  
doubly-linked

list should better be a separate type.


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


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

Denis


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


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

-Steve

Re: GSoC-2011 project:: Containers


Am 30.03.2011 17:31, schrieb Steven Schveighoffer:

On Wed, 30 Mar 2011 11:27:19 -0400, Daniel Gibson
metalcae...@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 (jmdavisp...@gmx.com)'s article


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


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


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

If no one else ever implements a doubly-linked list for Phobos, I'll
probably
do it eventually simply because it's one of the containers that
is on
the
short list of containers that pretty much every standard library
has.

- Jonathan M Davis


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

Cheers,
- Daniel


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


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


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

Denis


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


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

-Steve


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


Cheers,
- Daniel

Re: GSoC-2011 project:: Containers

2011-03-30 Thread Emil Madsen

On 30 March 2011 10:38, Jonathan M Davis jmdavisp...@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 (jmdavisp...@gmx.com)'s article
  
   The fancier stuff would be nice, but we don't even have a
 doubly-linked
   list yet. We should get the simpler stuff sorted out before we get
   particularly fancy, not to mention that it's usually the simple stuff
   that gets heavily used.
  
   For the most part I agree, but a doubly linked list might be **too**
   simple. Linked lists are so trivial to implement that I'd tend to roll
   my own that does exactly what I need with regard additional behavior
 on
   insertion, etc. rather than wrapping a library solution to get these
   features.
  
   A doubly-linked list is on the list of containers that every standard
   library should have or it's likely to be considered lacking. I can
   understand rolling your own for specific uses, but _I_ sure don't want
   to be doing that if I don't have to. If I want a doubly-linked list, I
   want to be able to just create a standard one and use it. C++, C#, and
   Java all have doubly-linked lists in their standard libraries.
  
   If no one else ever implements a doubly-linked list for Phobos, I'll
   probably do it eventually simply because it's one of the containers
 that
   is on the short list of containers that pretty much every standard
   library has.
  
   - Jonathan M Davis
 
  It may be feasible to enhance the single-linked list to support both
  single- and double linking, via an additional template-parameter bool
  doubly or something like that and some static-ifs in the implementation.
  I once created a simple single/double-linked queue for D1 like that.

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

 - Jonathan M Davis



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

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

Re: GSoC-2011 project:: Containers

On Wed, 30 Mar 2011 11:52:15 -0400, Daniel Gibson metalcae...@gmail.com  
wrote:



Am 30.03.2011 17:31, schrieb Steven Schveighoffer:

On Wed, 30 Mar 2011 11:27:19 -0400, Daniel Gibson
metalcae...@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

Re: GSoC-2011 project:: Containers

2011-03-30 Thread Jonathan M Davis

On 2011-03-30 09:18, Emil Madsen wrote:
 On 30 March 2011 10:38, Jonathan M Davis jmdavisp...@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 (jmdavisp...@gmx.com)'s article

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

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

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

If no one else ever implements a doubly-linked list for Phobos, I'll
probably do it eventually simply because it's one of the containers
  
  that
  
is on the short list of containers that pretty much every standard
library has.

- Jonathan M Davis
   
   It may be feasible to enhance the single-linked list to support both
   single- and double linking, via an additional template-parameter bool
   doubly or something like that and some static-ifs in the
   implementation. I once created a simple single/double-linked queue for
   D1 like that.
  
  To what end though? I don't think that that would save you much. While
  some of
  the implementation would be the same, so much of it would be different,
  that
  you'd practically have two complete types defined in one template. At
  that point, you might as well create a separate class/struct. It's just
  simpler to
  have them separate, and I don't see any real gain in combining them.
  Having both is great, since there are times that you want one and times
  when you want
  the other, but having both SList and DList (or whatever it would be
  called) as
  separate types makes sense.
  
  - Jonathan M Davis
 
 Just a question that popped into my mind, how does D's std.container handle
 cyclic lists? using static if?

And how would it get a cyclic list? The only linked list of any kind at the 
moment is SList, which is a singly-linked list. It only has elements in it 
where you inserted them. There's no way to tell it to insert anything 
cyclically. Sure, a cyclical list container could be implemented, but none 
such exists at the moment. std.container is one of the newer modules in Phobos 
and is still pretty sparse.

- Jonathan M Davis

Re: GSoC-2011 project:: Containers

2011-03-30 Thread Ishan Thilina

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?

Re: GSoC-2011 project:: Containers


On 03/30/2011 05:01 PM, Steven Schveighoffer wrote:

On Wed, 30 Mar 2011 10:45:19 -0400, KennyTM~ kenn...@gmail.com wrote:


On Mar 30, 11 21:09, Steven Schveighoffer wrote:

On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ kenn...@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

Re: GSoC-2011 project:: Containers


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

Re: GSoC-2011 project:: Containers


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

Re: GSoC-2011 project:: Containers


On Wed, 30 Mar 2011 14:21:35 -0400, spir denis.s...@gmail.com wrote:


On 03/30/2011 05:01 PM, Steven Schveighoffer wrote:

On Wed, 30 Mar 2011 10:45:19 -0400, KennyTM~ kenn...@gmail.com wrote:


On Mar 30, 11 21:09, Steven Schveighoffer wrote:
On Wed, 30 Mar 2011 04:55:52 -0400, KennyTM~ kenn...@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

Re: GSoC-2011 project:: Containers


On Wed, 30 Mar 2011 14:30:37 -0400, spir denis.s...@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

Re: GSoC-2011 project:: Containers


On Wed, 30 Mar 2011 14:28:49 -0400, KennyTM~ kenn...@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

Re: GSoC-2011 project:: Containers


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

Re: GSoC-2011 project:: Containers

2011-03-29 Thread Steven Schveighoffer

On Tue, 29 Mar 2011 01:45:02 -0400, Ishan Thilina ishanthil...@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

Re: GSoC-2011 project:: Containers

2011-03-29 Thread Ishan Thilina

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

Re: GSoC-2011 project:: Containers

2011-03-29 Thread spir


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

Re: GSoC-2011 project:: Containers

2011-03-29 Thread Fawzi Mohamed


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

Re: GSoC-2011 project:: Containers

2011-03-29 Thread Jonathan M Davis

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

Re: GSoC-2011 project:: Containers

2011-03-29 Thread bearophile

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

Re: GSoC-2011 project:: Containers

2011-03-29 Thread dsimcha

== Quote from Jonathan M Davis (jmdavisp...@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.

Re: GSoC-2011 project:: Containers

2011-03-29 Thread Jonathan M Davis

On 2011-03-29 14:50, dsimcha wrote:
 == Quote from Jonathan M Davis (jmdavisp...@gmx.com)'s article
 
  The fancier stuff would be nice, but we don't even have a doubly-linked
  list yet. We should get the simpler stuff sorted out before we get
  particularly fancy, not to mention that it's usually the simple stuff
  that gets heavily used.
 
 For the most part I agree, but a doubly linked list might be **too**
 simple. Linked lists are so trivial to implement that I'd tend to roll my
 own that does exactly what I need with regard additional behavior on
 insertion, etc. rather than wrapping a library solution to get these
 features.

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

If no one else ever implements a doubly-linked list for Phobos, I'll probably 
do it eventually simply because it's one of the containers that is on the 
short list of containers that pretty much every standard library has.

- Jonathan M Davis

Re: GSoC-2011 project:: Containers

2011-03-28 Thread Steven Schveighoffer

On Fri, 25 Mar 2011 18:37:26 -0400, Jonathan M Davis jmdavisp...@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

Re: GSoC-2011 project:: Containers

2011-03-28 Thread Ishan Thilina

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

Re: GSoC-2011 project:: Containers

2011-03-27 Thread Ishan Thilina

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?

Re: GSoC-2011 project:: Containers

2011-03-27 Thread Lutger Blijdestijn

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.

Re: GSoC-2011 project:: Containers

2011-03-26 Thread Lutger Blijdestijn

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

Re: GSoC-2011 project:: Containers

2011-03-26 Thread Andrej Mitrovic

On 3/26/11, Lutger Blijdestijn lutger.blijdest...@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.

Re: GSoC-2011 project:: Containers

2011-03-26 Thread Ishan Thilina

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

GSoC-2011 project:: Containers

Hi,

I'm the one who posted Interested in a GSoC project idea-
http://www.digitalmars.com/pnews/read.php?server=news.digitalmars.comgroup=digitalmars.Dartnum=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...!

Re: GSoC-2011 project:: Containers

2011-03-25 Thread Vladimir Panteleev

On Fri, 25 Mar 2011 12:12:08 +0200, Ishan Thilina ishanthil...@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,
 Vladimirmailto:vladi...@thecybershadow.net

Re: GSoC-2011 project:: Containers

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

Re: GSoC-2011 project:: Containers

2011-03-25 Thread Johannes Pfau

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

-- 
Johannes Pfau


signature.asc
Description: PGP signature

Re: GSoC-2011 project:: Containers

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

Re: GSoC-2011 project:: Containers

2011-03-25 Thread Steven Schveighoffer

On Fri, 25 Mar 2011 08:07:21 -0400, Ishan Thilina ishanthil...@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

Re: GSoC-2011 project:: Containers

2011-03-25 Thread Johannes Pfau

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

--
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 Andrei's article On Iteration', it's linked from there.
-- 
Johannes Pfau


signature.asc
Description: PGP signature

Re: GSoC-2011 project:: Containers

2011-03-25 Thread spir


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

Re: GSoC-2011 project:: Containers