Help: my list adt is broken

["chris.danx" <chris.danx@ntlworld.com>]

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