Help: my list adt is broken

Help: my list adt is broken

[chris.danx]

Hi,

i seem to have a problem with my (doubly) linked list ADT, and i can't
figure out what's wrong.

here is the output of the test program

>     -- display list before it get a choppin'
>    display a list of  5 elements
 >    5 4 3 2 1

>    -- remove head
>    display a list of  4 elements
>    4 3 2 1

>    -- remove an arbitary element
>    display a list of  3 elements
>    4 2 1

>    -- remove tail
>    display a list of  2 elements
>    4 2 1

>    -- remove head again
>    display a list of  1 elements
>    2 1

>    -- remove last element
>    no elements


i think the problem occurs when removing the tail.  it doesn't seem to be
erased but it should be.  i know
it's removed one from the size variable, so the code should be executed in
full.


i think the errror lies in the following routine, but i can't see it.

   -- remove item at current position from list;
   -- position will no longer be valid after execution;
   --
   -- will raise
   --   1. empty_list_error if list empty;
   --   2. position_error if position invalid;
   --
   procedure remove (l : in out list;
                     p : in out list_position) is
      t   :   list_position;
   begin
      if is_empty(l) then
         raise empty_list_error;
      end if;
      if is_invalid(p) then
         raise position_error;
      end if;

      if head(l) = p then
         l.head := p.next;
         l.size := l.size - 1;
         delete_node(p);
      elsif tail(l) = p then
         l.tail := p.prev;
         l.size := l.size - 1;
         delete_node(p);
      else
         t := p;

         -- dereference p;
         t.prev.next := p.next;
         t.next.prev := p.prev;

         -- delete p;
         delete_node(p);

         l.size := l.size - 1;
      end if;
   end remove;


i've also included the delete_node routine

   -- delete a node and give its' space back to pool;
   --
   procedure delete_node (n : in out list_position) is
      procedure free
         is new ada.unchecked_deallocation
                (node, list_position);
   begin
      free (n);
   end delete_node;

if it's any help.

list_position is simply a pointer to a node which contains

    1.        a pointer to the next and previous nodes
    2.        the data

oh, i almost forgot, the list type maintains a pointer to the head and tail,
as well as the size of the list.

i think i've been staring at it too long!!!  i'll let someone else takeover.


Thanks in advance,
Chris Campbell

Help: my list adt is broken

[chris.danx]

Hi,

i seem to have a problem with my (doubly) linked list ADT, and i can't
figure out what's wrong.

here is the output of the test program

>     -- display list before it get a choppin'
>    display a list of  5 elements
 >    5 4 3 2 1

>    -- remove head
>    display a list of  4 elements
>    4 3 2 1

>    -- remove an arbitary element
>    display a list of  3 elements
>    4 2 1

>    -- remove tail
>    display a list of  2 elements
>    4 2 1

>    -- remove head again
>    display a list of  1 elements
>    2 1

>    -- remove last element
>    no elements


i think the problem occurs when removing the tail.  it doesn't seem to be
erased but it should be.  i know
it's removed one from the size variable, so the code should be executed in
full.


i think the errror lies in the following routine, but i can't see it.

   -- remove item at current position from list;
   -- position will no longer be valid after execution;
   --
   -- will raise
   --   1. empty_list_error if list empty;
   --   2. position_error if position invalid;
   --
   procedure remove (l : in out list;
                     p : in out list_position) is
      t   :   list_position;
   begin
      if is_empty(l) then
         raise empty_list_error;
      end if;
      if is_invalid(p) then
         raise position_error;
      end if;

      if head(l) = p then
         l.head := p.next;
         l.size := l.size - 1;
         delete_node(p);
      elsif tail(l) = p then
         l.tail := p.prev;
         l.size := l.size - 1;
         delete_node(p);
      else
         t := p;

         -- dereference p;
         t.prev.next := p.next;
         t.next.prev := p.prev;

         -- delete p;
         delete_node(p);

         l.size := l.size - 1;
      end if;
   end remove;


i've also included the delete_node routine

   -- delete a node and give its' space back to pool;
   --
   procedure delete_node (n : in out list_position) is
      procedure free
         is new ada.unchecked_deallocation
                (node, list_position);
   begin
      free (n);
   end delete_node;

if it's any help.

list_position is simply a pointer to a node which contains

    1.        a pointer to the next and previous nodes
    2.        the data

oh, i almost forgot, the list type maintains a pointer to the head and tail,
as well as the size of the list.

i think i've been staring at it too long!!!  i'll let someone else takeover.


Thanks in advance,
Chris Campbell

Re: Help: my list adt is broken

[chris.danx]

That's weird!  I didn't send it twice!!!
Must be an Outlook Exp thing.

Re: Help: my list adt is broken

[Larry Hazel]

You didn't show the code that is extracting the list data for printing.  My
guess is it follows the links until it finds a null pointer and doesn't check
size.  After you delete the tail, you may need to store a null in the new tail's
next link.  The deallocated old tail data is probably still in memory.

Larry

I tried to quote the original post and got an error message about too much
included text.

Re: Help: my list adt is broken

[tmoran]

Each list node is pointed to by two things: its successor and its
predecessor.  When you delete an item in mid-list you make two fixes:
         t.prev.next := p.next;
         t.next.prev := p.prev;
But when you delete a head item, or a tail item, you only make one fix.
  The tail error you saw when you traversed the list forward.  The head
error you simply haven't noticed yet since you haven't tried traversing
the list backward.

Re: Help: my list adt is broken

[Chad R. Meiners]

I assume this for a class since writing this ADT is a very common
assignment
for a second semester university course.  I'll give you some advice on
debugging.

First, you don't provide enough of the information in your test
output.  You
need to look at all of the information in the data structure.  You
should
print out the Head element, tail element and the size each time you
change
the list data type.  Second, you should print out the value of the
neighboring nodes or at least whether or not the pointers are null.

Another method (if you don't want to write the code to display the above
information) would be to desk check your code.  Draw a representation of
your list and draw the list's representation during each change done by
the
remove procedure.

Using either method should reveal to you that the first call to the
remove
procedure leaves the ADT in an incorrect state.

>i think i've been staring at it too long!!!  i'll let someone else
>takeover.

You should not give up so easily.  If you follow the above methods I am
sure
you should be able to fix your ADT by yourself.  Writing correct code
requires a good deal of effort and deligence.  Gathering all of the
data and
having a clear understanding of the problem are the most effective
methods
of preventing yourself from staring at the code until you give up ;)

Good Luck,
Chad R. Meiners



Sent via Deja.com
http://www.deja.com/

Re: Help: my list adt is broken

[chris.danx]

thanks for everyones help,
Chris Campbell

Re: Help: my list adt is broken

[chris.danx]

Hi,
    Thanks again for everyones help.  In the end it only took 6 lines of
code to fix (two if statements ...).  One thing interests me though.  Why
wasn't an exception generated when i walked the list?  I deleted the node p
in the code, so it shouldn't be there, should it?



Thanks a million,
Chris Campbell

(i definetly need to improve my debugging skills).

Re: Help: my list adt is broken

[John English]

"chris.danx" wrote:
> 
> Hi,
>     Thanks again for everyones help.  In the end it only took 6 lines of
> code to fix (two if statements ...).  One thing interests me though.  Why
> wasn't an exception generated when i walked the list?  I deleted the node p
> in the code, so it shouldn't be there, should it?

Your list still pointed to the deleted item; the block of memory is
still there (you haven't deleted a chunk of physical RAM ;-) but you
were lucky (unlucky?) that the block hadn't been reallocated and
used for something else.

It's your responsibility to avoid referring to memory blocks that you
delete, and that's why the deletion is done by a procedure called
UNCHECKED_Deallocation... there are no runtime checks to ensure that
your pointers are all still valid afterwards.

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.it.bton.ac.uk/staff/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------

Re: Help: my list adt is broken

[Ted Dennison]

In article <5aDh6.11952$BQ3.215984@news6-win.server.ntlworld.com>,
  "chris.danx" <chris.danx@ntlworld.com> wrote:

> i seem to have a problem with my (doubly) linked list ADT, and i can't
> figure out what's wrong.
...
> i think the problem occurs when removing the tail.  it doesn't seem to
>  be erased but it should be.  i know
> it's removed one from the size variable, so the code should be
> executed in full.

I don't see anything obviously wrong in the routine you posted, but its
tough to tell since there's no indication as to what the types you are
using are, or how the fundamental algorithms you are using are written.
If I had to take a wild guess, I'd say that your logic for setting up
the ".prev" links is bad, since that could cause what you are seeing,
and the stuff that *is* working doesn't seem to use those .prev links
(but again, that isn't shown here).

One debugging trick I often find useful for data structures is to get
out a pencil and a piece of paper (or a whiteboard) and run through the
source code like I'm the computer. Data elements can be represented as
boxes, and link fields can be represented by drawing arrows between the
boxes.

--
T.E.D.

http://www.telepath.com/~dennison/Ted/TED.html


Sent via Deja.com
http://www.deja.com/

Re: Help: my list adt is broken

[chris.danx]

thanks,
Chris Campbell

Re: Help: my list adt is broken

[chris.danx]

Hi,
    it's me again!!!  This isn't about a broken ADT as such, more of a
problem i'm having visualising and implementing an operation.

I want to be able to swap two elements on the same list (if you don't use
the same list it's your problem basically, since to guarantee this i would
have to walk the list).  The problem is i can't get it to work.

I've been testing the possible conditions for failure, and my solution fails
on the first -- when you swap head and tail (it will fail if i swap the head
or tail with any position in the list, me thinks).

I would like to know how to do it.  I've been trying this for ages, and have
loads of wee diagrams to prove it.

Since i'm implementing a doubly linked list i have to update the next/prev
for each position given, but somewhere along the lines it get's screwed up.
I tried two different solutions.  The first would move the tail to the head
position the rest of the list would be gone (since the new head wasn't
pointing to the rest of the list).  My second solution raised a constraint
error.  This i think was caused by something along these lines

    p1.prev.next := p2;            --    can't do for head since p1.prev is
null;
    p2.next.prev := p1;            --    similar thing here.

I know what the problems are.  I thought combining both the solutions for
these might have worked.  Alas, it didn't, but maybe it's just me.  {next
time i do something like this i'm gonna use sentinels!}


I'd be grateful for anyones assistance with this.


These are my data structures

(item is generic)

>      -- incomplete definition;
>      --
>      type node;

>      -- type representing position in list;
>      --
>      type list_position is access node;

>      -- a type representing a node in the
>      -- list;
>      --
>      type node    is record
>                         data   : item;
>                         next   : list_position;
>                         prev   : list_position;
>                   end record;

>      -- a type represting the list;
>      --
>      type list    is record
>                         size   : natural;
>                         head   : list_position;
>                         tail   : list_position;
>                   end record;


and this is the spec of the swap routine


>   -- swap two positions in a list;
>   --
>   -- will raise
>   --   1. empty_list_error if list empty;
>   --   2. position_error if either positions is
>   --      invalid;
>   --
>   procedure swap (p1, p2 : in out list_position;
>                              l      : in out list );


thanks (yet again),
Chris Campbell


p.s. i'm not being lazy, i just can't work out what to do.
(i don't even know if i'll ever have the need to swap two positions
about!!!).

Re: Help: my list adt is broken

[tmoran]

Just approach the problem one step at a time.  An arbitrary node has
how many incoming and outgoing pointer fields?  You have two nodes to
move, so write down assignment statements to change all the pointers.
If a node is a head node, its prev is null, which means its actual
prev is "head".  So any assignment that uses x.prev.all needs an "if"
to check that x.prev is not null, and, if it is null, use "head"
instead.  Similarly for a tail node.  Now make sure that in the
assignment statements you haven't tried to use something's old value
after changing it, eg "x.next := something_new;" followed by using
x.next as if it still had something_old as its value.  If so, make a
temporary copy of something_old before destroying it with "x.next :=
something_new".

Re: Help: my list adt is broken

[schwarza]

Chris;

There are exactly two (2) ways of implementating a doubly-linked
list (unless I become reasonable - nah, never happen):

[1] Each end of the doubly linked list terminates in a null and
    the list head points to the first element of the list:

    ptr ->   null <- cell -> ... <- cell -> null

[2] There is a unique list header which points to both the list
    header and tail (and is itself a list cell) with a pointer
    to the header cell being the external 'name' of the list:

    ptr ->   unique list header cell
                                top   -> <- cell -> ... <- cell -> .
                                bot                     ->         |
                                 ^                                 |
                                 |                                 |
                                 .---------------------------------.

I prefer two to one (2 to 1) but that is not material.

Now, to do any list switching the order of operations is very, very
important. If you don't do things in the proper order, carefully,
things get fouled up fast. So let's see:

Suppose we do the following:

   1. Save the left pointer of the first cell.
   2. Put into the left pointer of the first cell, the left pointer
      of the 'new cell'.
   3. Put into the left pointer of the second cell, the (saved) left
      pointer of the first cell.
   4. Put into the right pointer of the cell pointed to by the second
      cell a pointer to the current cell. And here is where the two
      implementations differ. For [1], it is possible for the left
      pointer of the second cell to be null. For [2] there is no such
      worry (it works in all cases).
   5. Repeat for the right pointers.
   6. If you have implemented [1], then some fixup is required:
      a. If the second cell is the list top, then the 'ptr' must
         be changed to the first cell (the new list top).
      b. If the first cell is the list top then the contrawise
         operation has to be done.

And now for the kicker. This is not a place to get your homework
assignments done. Having said that, let me amplify a comment concerning
debugging (instrumenting your code with output statements). Code for
failure!! Assume nothing (NOTHING) will work correctly and provide
print statements accordingly. It's easier than asking questions. And,
allow the print statements to be turned on or off, as in:

   if this_is_some_kind_of_debug_thing then PRINT;

Disappointingly you will find that the volume of code required to code
for failure is larger than that for your actual classroom assignments.
Encouragingly you will shine amongst your peers because you will be able
to identify your errors quickly and solve them even more quickly.

art

PS: If any of you are real, real old programmers then [2] is SLIP
(Symmetric
    LIst Processor) from way, way back (circa 1960).  I believe that Eliza
    was programmed in SLIP and in FORTRAN at MIT.

PSST: I am a real, real old programmer and still have copies of the
original
    SLIP implementation circa 1964 at the University of Wisconsin; in
FORTRAN.

Re: Help: my list adt is broken

[chris.danx]

Actually, it isn't a homework assignment!  I'd already done that ages ago, i
wanted a proper linked list for future use.  My last attempt (for the
assignment (well before christmas)), wasn't suitable as i had to modify it
horribly.  First a routine had to be added to split a list in two and then
another to join them.  I was implementing a recursive quicksort on a doubly
linked list.  Somewhere in these two routines the ADT got mangled and the
display routine displayed the list infitely (the tail pointed to the head,
or something) i didn't have time to weed out the bug.

{
they don't really encourage debugging at uni, it never got a mention.  this
was probably because they don't  keep level 1 and level 2 courses in sync.
it so annoying!  they don't know what we've done and what we ain't.  someone
should give them a kick up the pants!  the level 1 IP (introductory
programming) module didn't do debugging as it simplified learning Ada by
wrapping things up in a neat little package -- i've been programming for 8
years so it wasn't really hard especially with my Pascal background, but it
was fun.  FP1 (further programming level 1) was pants to put it mildly.  The
guy more or less stuck slides on the OHP and read from them (word for word,
i might add).  I and many others hated it!  Come back Quintin, that's what i
say!

maybe i should start a new thread:

how not to teach Ada at uni.

any interest?

[i'd never implemented a linked lists until i got to uni.  why?  well i had
one book (a small one) which didn't cover them.  when i got a copy of C and
1000+ page book (before Ada 95 came along) i freaked, and stuck with Pascal.
i wonder why]

just don't get me started on HCI1 and CF1.
}



So, don't go assuming that it's for homework.  I'd say as much if it were
the case.


{If you really must know, i'm using the ADT in an Adjacency List
implementation of a graphs (so i can tinker with program representation and
visualisation ).}




A somewhat tired (and frustrated) but thankful,
Chris Campbell

p.s. i appologise for being short, i'm very tired and frustrated.  It's been
a long day.

p.p.s i know i waffle a lot.


the opinions here in are my own, and not those of my uni.

Re: Help: my list adt is broken

[Jeffrey Carter]

You can certainly save a lot of effort by reusing an existing,
production-quality, industrial-strength list rather than rolling your
own. You can probably find a number of implementations at
www.adapower.com.

Shameless_Plug : begin
   I recommend PragmARC.List_Unbounded from the PragmAda Reusable
Components available from

   http://home.earthlink.net/~jrcarter010/pragmarc.htm

   (also mirrored at adapower).
end Shameless_Plug;

If this IS a homework assignment, you can rest assured that your
professor is aware of these lists and will recognize any plagiarism, but
studying them might help you learn techniques useful in your assignment.
I assume this is NOT a homework assignment, and encourage you to enjoy
the benefits of reuse.

-- 
Jeff Carter
"Perfidious English mouse-dropping hoarders."
Monty Python & the Holy Grail

Re: Help: my list adt is broken

[schwarza]

From: "chris.danx" <chris.danx@ntlworld.com>


Actually, it isn't a homework assignment!

  <sigh> I always get in trouble when I jump to contusions. Sorry!

  [1] Algorithms for linked lists are standard fare in textbooks
      on Data Structures and on Algorithms (and sometimes on
      Compiler Design). I assume that you have them and have
      looked at them. Mine are old (old ... old - but still good.)
  [2] There are a number of Ada implementations of the C Standard
      Template Library (?) STL. If you are interested I'll try to
      find some URL's and send them to you.
  [3] I have a full implementation of SLIP, a really full implementation
      of doubly linked lists akin to LISP, written in C and Ada83,
      both languages without class. And, I have a word document which
      is a retyped version (with diagrams) of a SLIP description
      written in Sammett's book "Programming Languages", 1967. The
      book stuff is excellent. My internal documentation is almost
      non-existent. If you'd like, I'll send the whole nine yards
      to you - tho' I advise a shovel for the dirt.

      (There are some reasonable extensions yet to be done that have
      been on my 'wannado' list for years - hint, hint, hint. One is
      an implementation for dynamic memory management. Because the
      'language' is written as an API it is really not possible to
      write something for dynamic memory management (with garbage
      collection) but that doesn't mean that something can't be
      done.)

  Other than that, nothing. Sorry.

art

Re: Help: my list adt is broken

[John English]

schwarza@gdls.com wrote:
>   [2] There are a number of Ada implementations of the C Standard
>       Template Library (?) STL. If you are interested I'll try to
>       find some URL's and send them to you.
>   [3] I have a full implementation of SLIP, a really full implementation
>       of doubly linked lists akin to LISP, written in C and Ada83,
>       both languages without class. And, I have a word document which
>       is a retyped version (with diagrams) of a SLIP description
>       written in Sammett's book "Programming Languages", 1967. The
>       book stuff is excellent. My internal documentation is almost
>       non-existent. If you'd like, I'll send the whole nine yards
>       to you - tho' I advise a shovel for the dirt.

Hmm, I'd be interested in both of these too!

Cheers,

-----------------------------------------------------------------
 John English              | mailto:je@brighton.ac.uk
 Senior Lecturer           | http://www.it.bton.ac.uk/staff/je
 Dept. of Computing        | ** NON-PROFIT CD FOR CS STUDENTS **
 University of Brighton    |    -- see http://burks.bton.ac.uk
-----------------------------------------------------------------