GSoC-2011 project:: Containers

[KennyTM~]

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