From mboxrd@z Thu Jan  1 00:00:00 1970
X-Spam-Checker-Version: SpamAssassin 3.4.4 (2020-01-24) on polar.synack.me
X-Spam-Level: 
X-Spam-Status: No, score=-1.9 required=5.0 tests=BAYES_00,XPRIO autolearn=ham
	autolearn_force=no version=3.4.4
X-Google-Language: ENGLISH,ASCII-7-bit
X-Google-Thread: 103376,a676349b69fa778f,start
X-Google-Attributes: gid103376,public
X-Google-ArrivalTime: 2001-02-11 13:15:29 PST
Path: 
 supernews.google.com!sn-xit-02!supernews.com!bignews.mediaways.net!fr.usenet-edu.net!usenet-edu.net!fr.clara.net!heighliner.fr.clara.net!grolier!btnet-peer0!btnet!news5-gui.server.ntli.net!ntli.net!news2-win.server.ntlworld.com.POSTED!not-for-mail
From: "chris.danx" <chris.danx@ntlworld.com>
Newsgroups: comp.lang.ada
Subject: Help: my list adt is broken
X-Priority: 3
X-MSMail-Priority: Normal
X-Newsreader: Microsoft Outlook Express 5.00.2615.200
X-MimeOLE: Produced By Microsoft MimeOLE V5.00.2615.200
Message-ID: <79Dh6.10732$zz4.264993@news2-win.server.ntlworld.com>
Date: Sun, 11 Feb 2001 21:04:58 -0000
NNTP-Posting-Host: 62.253.8.208
X-Complaints-To: abuse@ntlworld.com
X-Trace: news2-win.server.ntlworld.com 981925571 62.253.8.208 (Sun,
 11 Feb 2001 21:06:11 GMT)
NNTP-Posting-Date: Sun, 11 Feb 2001 21:06:11 GMT
Organization: ntlworld News Service
Xref: supernews.google.com comp.lang.ada:5127
Date: 2001-02-11T21:04:58+00:00
List-Id: <comp.lang.ada>

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