Re: Help: my list adt is broken

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

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!!!).