http://d.puremagic.com/issues/show_bug.cgi?id=4420

           Summary: insertBack() for SList
           Product: D
           Version: D2
          Platform: Other
        OS/Version: Linux
            Status: NEW
          Severity: normal
          Priority: P2
         Component: Phobos
        AssignedTo: nobody@puremagic.com
        ReportedBy: jmdavisProg@gmail.com


--- Comment #0 from Jonathan M Davis <jmdavisProg@gmail.com> 2010-07-03 22:57:31 PDT ---
SList has an insertFront() but not an insertBack(). I assume that this is
because SList is a singly linked list and the last element does not have a link
to the element before it (in fact, looking at the implementation, you don't
even keep track of the last element).

However, if you keep track of just a bit more than the head node, you can
implement insertBack() as well better optimize some of its functions (like
findLastNode()). If you kept track of the last node in addition to the first
one, then you have the last node for functions like findLastNode() and you can
have back() and insertBack(). For that matter, if you made it the last two
nodes, then you could have popBack() as well. Now, that may complicate the
other list operations too much to be worthwhile, but it would expand SList's
capabilities without unduly increasing how much memory it takes like you would
with a doubly linked list.

So, it may be a bad idea when you really get down to it, but I thought that I should at least suggest it since it would make SList more versatile.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4420


Jonathan M Davis <jmdavisProg@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
           Severity|normal                      |enhancement


-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4420


Andrei Alexandrescu <andrei@metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |andrei@metalanguage.com


--- Comment #1 from Andrei Alexandrescu <andrei@metalanguage.com> 2010-07-04 02:01:26 PDT ---
SList can't implement insertBack due to complexity requirements. To append to a list, use lst.insertAfter(lst[], stuff).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4420



--- Comment #2 from Jonathan M Davis <jmdavisProg@gmail.com> 2010-07-04 02:40:40 PDT ---
Which complexity requirements? I understand that it can't do it as is because
that would be O(n). I was pointing out that it kept track of the last element
in addition to the first one, it could implement insertBack() in O(1) without
needing the extra space per node that a doubly linked list requires. And if it
keeps track of the next-to-last node as well, then it can implement popBack()
in O(1) as well. Is it that other operations no longer fit the appropriate
complexity requirements if it keeps track of the last element in addition to
the first? I would think that the other operations would have the same
complexity but with (in some cases) a slightly higher constant - as in xO(1)
would have a greater value of x rather than becoming O(n) or O(log n) or
anything worse than O(1).

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4420


Simen Kjaeraas <simen.kjaras@gmail.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
                 CC|                            |simen.kjaras@gmail.com


--- Comment #3 from Simen Kjaeraas <simen.kjaras@gmail.com> 2010-07-04 03:24:31 PDT ---
(In reply to comment #2)
> And if it keeps track of the next-to-last node as well, then it can implement
> popBack() in O(1) as well.

How could it? It could popBack once, then you'd need to recalculate next-to-last.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4420



--- Comment #4 from Jonathan M Davis <jmdavisProg@gmail.com> 2010-07-04 03:38:29 PDT ---
Ah. Good point. I obviously didn't think that one through thoroughly enough. You could popBack() once, but that would be it. Scratch that idea.

However, you could still have insertBack() and back() if you kept track of the
last element. back() would return that last element and insertBack() would
insert after it, adjusting the last element's pointer to its next element to
point to the new last element and adjusting the container's pointer to the last
element to point to the new last element. So, that should work in O(1), but no
popBack() wouldn't work.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4420


Andrei Alexandrescu <andrei@metalanguage.com> changed:

           What    |Removed                     |Added
----------------------------------------------------------------------------
             Status|NEW                         |RESOLVED
         Resolution|                            |WONTFIX


--- Comment #5 from Andrei Alexandrescu <andrei@metalanguage.com> 2010-07-04 12:42:42 PDT ---
The main selling point of SList is simplicity. Adding all sorts of storage aides is possible but would work against SList's charter. Feel free to propose a new type based on SList in an enhancement proposal.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------

http://d.puremagic.com/issues/show_bug.cgi?id=4420



--- Comment #6 from Jonathan M Davis <jmdavisProg@gmail.com> 2010-07-04 16:44:47 PDT ---
Well, like I said, the addition might not be worthwhile. It would complicate some of the other functions somewhat. It's just that it would be a fairly simple addition to get some extra functionality in comparison to say, a doubly-linked list. I have no problem if you don't think that it's appropriate to add that extra functionality to SList. I just thought that I'd point it out in case such a change would be desirable and the idea hadn't occurred to you.

Personally, in my code, I'd generally just as soon use a doubly-linked list in most cases if I'm going to use a list. But SList as-is definitely has its uses, and a doubly-linked list is overkill for some situations. It probably isn't worth creating a separate SList class with just the additions to support back() and insertBack() though.

In any case, this was just a suggestion, and if you don't want to use it, that's fine by me.

-- 
Configure issuemail: http://d.puremagic.com/issues/userprefs.cgi?tab=email
------- You are receiving this mail because: -------