Re: Bug in Linked Lists?

[Roger M. Burkhart]

Kevin Crowston writes:

> The bug is that the list ends up empty.  Apparently when I remove the last
> item in the list, the next next puts me back to the beginning--so I go
> through the list a second time and this time delete everything, thinking
> it's a repeat.

I haven't been able to reproduce your problem in an independent test, at
least with as simple a cause as you suggest.  Here's a sample loop that
duplicates the sequence of index operations you're performing, but without
anything else:

  index = [aList begin: scratchZone];

  [index setLoc: Start];
  [index next];
  while ( [index getLoc] == Member ) {
    [index remove];
    printf( "after [index remove]: %s\n", [[index getLoc] getName] );
    [index next];
    printf( "after [index next]: %s\n", [[index getLoc] getName] );
  }

(BTW, your use of setLoc: and getLoc in a list that may contain zero
integer values is exactly how these messages are intended to be used.  I
keep them in the example but took out your operations on a separate array
that you perform on selected members.)

When the input to this code block is a list containing two members, each of
these two members is removed, with the last remove being on the one and
only member remaining in the list at that time.  Here's the resulting output
from the print statements:

after [index remove]: Removed
after [index next]: Member
after [index remove]: Removed
after [index next]: End

This is the intended, correct behavior -- remove always leaves the index
set at a special "Removed" location, but next advances it to the next
location that would have followed.  If the member removed was the
one-and-only member remaining, and the next operation is "next," then the
next location obtained is End.  (If the next operation had been "prev,"
the subsequent location obtained would have been Start; everything is
supposed to be entirely symmetrical in both directions.  The index has no
notion of a current direction of processing; the next location obtained is
determined by the operation requested.)

> The documentation says that removing the last element leaves you at End,
> but in fact it leaves you with [point getLoc] == "Removed".  Doing a next
> from this Removed node seems to take you to the front of the list.

In looking carefully at the List code, I can't find a logical path that
would ever take an index back around to the beginning (short of a new
[... setLoc: Start]), but that isn't saying there isn't such a possibility,
just that I haven't found it or been able to reproduce it in a simple test
case.

On the documentation for removing the last element using an index, the
Index interface reference (in
www.santafe.edu/projects/swarm/swarmdocs/src/collections/Index.html)
indicates that the immediate location is always "Removed," followed by the
location that would have followed the member had it not been removed:

  The remove message removes the member at the current location of an
  index, and returns the member value removed. The index position is set
  to a special position between the members which previously preceded and
  followed the removed member. If there is no preceding or following
  member, the index is set to the special location before the start or
  after the end of all members. After a current member is removed, there
  is no member at the current index location, but a subsequent next or
  prev message will continue with the same member that would have been
  accessed had the current member not been removed.

I scarcely claim that this is the most transparent wording to explain how
an index behaves after removing a member, but I think it does match the
values returned by the test case above.

Index traversal behavior is extremely basic to all collections (where they
play the same role as the lightweight iterators that Alexander Stepanov
promoted convincingly for the C++ Standard Template Library), so if
there's any case at all where they don't behave as they're supposed to
it's extremely critical that we track it down.  The best form of bug
report is a block of code that can be independently compiled to reliably
create an example of the problem, and which does so in as simple a form as
possible.  If the problem can be created in a self-contained test file, it's
usually easy to track down what's happening very quickly.  (Finding the
right test case is often the hardest part.)  Can you suggest anything else
that might differ in your usage of a list and index than the case I tried?

Roger Burkhart

                  ==================================
   Swarm-Support is for discussion of the technical details of the day
   to day usage of Swarm.  For list administration needs (esp.
   [un]subscribing), please send a message to <address@hidden>
   with "help" in the body of the message.
                  ==================================