chained List manipulation without recusrsion : lost the begining of my List!

chained List manipulation without recusrsion : lost the begining of my List!

[Zeg]

Hi all,
I'm trying to make a procedure to insert an integer (at this natural
position) in a chained List without recursion but
each time I lost the begining of my List, i understand why but i don't find
the trick.

I think it would be very easy for most of you,
Thanks in Advance .
                                        Zeg

  type Element is new Integer;

   type Maillon;

   type Liste is access Maillon;

   type Maillon is record
      Valeur  : Element;
      Suivant : Liste := null;
   end record;


procedure Insert_iteratif(E : in Element; L : in out Liste) is
Aux : Liste := L;
Z : Liste := null;
begin
      if (Aux = null) then
         Aux := new Maillon'(E,null);
      else
         while  (Aux /= null) loop
              if (Aux.all.valeur > E) then
                  L := new Maillon'(E,Aux);
                  exit;
            elsif (Aux.all.suivant = null) then
                  L:= new Maillon'(E,null);
                  exit;
            end if;
            z := Aux ;
            Aux := Aux.all.suivant;
         end loop;
     end if;

end Insert_iteratif;

--========================
begin
L := new Maillon'( 3,new Maillon'(4,new Maillon'(5,new Maillon'(7,new
Maillon'(8,new Maillon'(10,new Maillon'(99,null)))))));
Insert_iteratif(9,L);

end
 --=======================

Re: chained List manipulation without recusrsion : lost the begining of my List!

[Simon Wright]

"Zeg" <zeg.nospam@9online.fr> writes:

> procedure Insert_iteratif(E : in Element; L : in out Liste) is
> Aux : Liste := L;
> Z : Liste := null;

You don't need to initialize access variables, they are automatically
set to null for you

> begin
>       if (Aux = null) then
>          Aux := new Maillon'(E,null);

L was empty, so what is it pointing to now? Should you have altered it?

>       else
>          while  (Aux /= null) loop
>               if (Aux.all.valeur > E) then
>                   L := new Maillon'(E,Aux);

What has happened to all the previous elements in the list? (that L
used to be pointing to)

>                   exit;
>             elsif (Aux.all.suivant = null) then
>                   L:= new Maillon'(E,null);

What has happened to all the previous elements in the list?

>                   exit;
>             end if;
>             z := Aux ;

What is Z for? You don't read it anywhere

>             Aux := Aux.all.suivant;
>          end loop;
>      end if;
> 
> end Insert_iteratif;

It might help you to draw a picture of Maillons linked into a Liste,
and how you want a new Maillon to be linked in.

Re: chained List manipulation without recusrsion : lost the begining of my List!

[Zeg]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2308 bytes --]

Got it!!
It's a really good exercise to understand pointers and recursivity!
Thanks.

procedure Insert_iteratif(E : in Element; L : in out Liste) is

Aux : Liste := L;

Z : Liste;

begin

                if (L = null) then

            L := new Maillon'(E,null);

                else

                                while (Aux /= null) loop

                                            if (Aux.all.valeur > E) then

                      z.all.suivant := new Maillon'(E,Aux);

                                                            exit;

                                             elsif (Aux.all.suivant = null)
then

                       z.all.suivant := new Maillon'(E,null);

                                                              exit;

                                             end if;


           z := Aux ;

                              Aux := Aux.all.suivant;


                            end loop;

                end if;


end Insert_iteratif;

"Simon Wright" <simon@pushface.org> a �crit dans le message de
news:x7vfzngg39y.fsf@smaug.pushface.org...
> "Zeg" <zeg.nospam@9online.fr> writes:
>
> > procedure Insert_iteratif(E : in Element; L : in out Liste) is
> > Aux : Liste := L;
> > Z : Liste := null;
>
> You don't need to initialize access variables, they are automatically
> set to null for you
>
> > begin
> >       if (Aux = null) then
> >          Aux := new Maillon'(E,null);
>
> L was empty, so what is it pointing to now? Should you have altered it?
>
> >       else
> >          while  (Aux /= null) loop
> >               if (Aux.all.valeur > E) then
> >                   L := new Maillon'(E,Aux);
>
> What has happened to all the previous elements in the list? (that L
> used to be pointing to)
>
> >                   exit;
> >             elsif (Aux.all.suivant = null) then
> >                   L:= new Maillon'(E,null);
>
> What has happened to all the previous elements in the list?
>
> >                   exit;
> >             end if;
> >             z := Aux ;
>
> What is Z for? You don't read it anywhere
>
> >             Aux := Aux.all.suivant;
> >          end loop;
> >      end if;
> >
> > end Insert_iteratif;
>
> It might help you to draw a picture of Maillons linked into a Liste,
> and how you want a new Maillon to be linked in.

Re: chained List manipulation without recusrsion : lost the begining of my List!

[Zeg]

[-- Warning: decoded text below may be mangled, UTF-8 assumed --]
[-- Attachment #1: Type: text/plain, Size: 2382 bytes --]

I missed inserting at the head of the List so this the

 ultimate code

procedure Insert_iteratif(E : in Element; L : in out Liste) is

Aux : Liste := L;

Z : Liste;

begin
                if (L = null) then
                        L := new Maillon'(E,null);
                else
                         while (Aux /= null) loop
                                 if (Aux.all.valeur > E) then
                     if (z = null) then
                          L := new Maillon'(E,L);
                     else

z.all.suivant := new Maillon'(E,Aux);
                     end if;
                                          exit;
                                  elsif (Aux.all.suivant = null) then
                                           z.all.suivant := new
Maillon'(E,null);
                                           exit;
                                  end if;
                                  z := Aux ;
                                 Aux := Aux.all.suivant;
                           end loop;
                end if;

end Insert_iteratif;



"Simon Wright" <simon@pushface.org> a �crit dans le message de
news:x7vfzngg39y.fsf@smaug.pushface.org...
> "Zeg" <zeg.nospam@9online.fr> writes:
>
> > procedure Insert_iteratif(E : in Element; L : in out Liste) is
> > Aux : Liste := L;
> > Z : Liste := null;
>
> You don't need to initialize access variables, they are automatically
> set to null for you
>
> > begin
> >       if (Aux = null) then
> >          Aux := new Maillon'(E,null);
>
> L was empty, so what is it pointing to now? Should you have altered it?
>
> >       else
> >          while  (Aux /= null) loop
> >               if (Aux.all.valeur > E) then
> >                   L := new Maillon'(E,Aux);
>
> What has happened to all the previous elements in the list? (that L
> used to be pointing to)
>
> >                   exit;
> >             elsif (Aux.all.suivant = null) then
> >                   L:= new Maillon'(E,null);
>
> What has happened to all the previous elements in the list?
>
> >                   exit;
> >             end if;
> >             z := Aux ;
>
> What is Z for? You don't read it anywhere
>
> >             Aux := Aux.all.suivant;
> >          end loop;
> >      end if;
> >
> > end Insert_iteratif;
>
> It might help you to draw a picture of Maillons linked into a Liste,
> and how you want a new Maillon to be linked in.

Re: chained List manipulation without recusrsion : lost the begining of my List!

[Jeffrey Carter]

Zeg wrote:
> I missed inserting at the head of the List so this the
> 
>  ultimate code

I've reformatted it to help me understand it, used consistent 
capitalization, added some blank lines and removed others, and removed 
unnecessary parentheses and ".all"s. This was to help me more than 
anything, but good formatting and consistent capitalization are 
generally a Good Thing. It's usually not a Good Idea to use tabs for 
indentation; 2-4 blanks is usually good.

> 
> procedure Insert_iteratif (E : in Element; L : in out Liste) is
>    Aux : Liste := L;
>    Z   : Liste;
> begin

Do you check your precondition (L is sorted) anywhere?

>    if L = null then
>       L := new Maillon'(E, null);
>    else
>       while Aux /= null loop
>          if Aux.Valeur > E then
>             if Z = null then
>                L := new Maillon'(E, L);
>             else
>                Z.Suivant := new Maillon'(E, Aux);
>             end if;
 >
>             exit;
>          elsif Aux.suivant = null then
>             Z.Suivant := new Maillon'(E, null);

At the end of the list. It seems to me that it is possible for Z to be 
null here, for example if L has exactly 1 element.

 >
>             exit;
>          end if;
 >
>          Z := Aux;
>          Aux := Aux.Suivant;
>       end loop;
>    end if;
> end Insert_iteratif;

It seems you've missed the case of adding to the end of a single-element 
list.

It would be clearer what you're doing if you used names such as 
"Current" and "Previous" rather than "Aux" and "Z". (You might prefer 
French equivalents.)

You don't need to put parentheses around conditions, the way you have to 
in some languages. Nor do you have to put ".all" when referencing a 
component of something designated by an access value. This is part of 
the idea of allowing something to change from statically allocated to 
dynamically allocated (or from dynamic to static) without having to add 
or remove a bunch of ".all"s.

-- 
Jeff Carter
"I'm a lumberjack and I'm OK."
Monty Python's Flying Circus

Re: chained List manipulation without recusrsion : lost the begining of my List!

[Robert A Duff]

Simon Wright <simon@pushface.org> writes:

> "Zeg" <zeg.nospam@9online.fr> writes:

> > Z : Liste := null;
> 
> You don't need to initialize access variables, they are automatically
> set to null for you

True, but I think a good style is to always use explicit initialization
if you are going to depend on the initial "null" (as opposed to just
using it to trip up uninitialized pointers).

- Bob

Re: chained List manipulation without recusrsion : lost the begining of my List!

[Simon Wright]

Robert A Duff <bobduff@shell01.TheWorld.com> writes:

> Simon Wright <simon@pushface.org> writes:
> 
> > "Zeg" <zeg.nospam@9online.fr> writes:
> 
> > > Z : Liste := null;
> > 
> > You don't need to initialize access variables, they are automatically
> > set to null for you
> 
> True, but I think a good style is to always use explicit initialization
> if you are going to depend on the initial "null" (as opposed to just
> using it to trip up uninitialized pointers).

I suppose we just have to disagree here! (but only a little). To me it
feels to be rather like

   if Boolean_Variable = True then