Subject:    Re: Adding items in a link list... HELP!
      Date:    31 Jul 1998 02:21:53 EDT
      From:    "Keith" <ty3295@concentric.net>
 Organization: Concentric Internet Services
 Newsgroups:   comp.lang.pascal.borland


Unit LList;
    {                      LLIST v1.1                             }
    { (c) 1994 Keith Tysinger -- Released into the Public Domain  }
    { This unit creates a double-linked list that handles Strings }

Interface
TYPE
      Plist_rec = ^ List_rec;
       List_Rec = Record
         Next_link,
         Prev_link : Plist_rec;
         Field     : ^String;
       end; {record}
TYPE
  ListO = Object
  Private
     LL,First,
     Temp,last,
     Nxt, Prv : Plist_rec;
     No_Links : word;
  Public
                    {* INDEXES START AT 1 *}
  Constructor Init;
  Procedure   Add_Link ( S : String );             { Add new string to LL }
  Procedure   Remove_Link ( LI : word );           { Removes link  }
  Function    Current_Link : String;               { Returns current link }
  Procedure   Replace_Link ( LI : word; S : String );
  Procedure   Insert_Link ( LI : word; S : String );
  Function    Get_Link ( LI : word ): String;      { Returns link }
  Function    Goto_Link ( LI : word ) : boolean;   { true if sucessful }
  Function    Next_Link : Boolean;                 { true if sucessful }
  Function    Previous_Link : Boolean;             { true if sucessful }
  Function    Number_of_Links : word;
  Procedure   ABC;                                 { Quicksort }
  Procedure   Out_of_Memory_Message; Virtual;
  Destructor  Done;
end; {object}

Implementation

Uses Crt;
  Constructor ListO.Init;
   Begin
     No_Links := 0;
     First := nil;
     Last := nil;
   end;

  Procedure ListO.Add_Link ( S : String );
    Begin
     if MaxAvail < length(s)+10 then Out_of_Memory_Message;

      If First = nil then
       Begin
        New ( ll );
        First := ll;
        LL^.Prev_Link := nil;
        LL^.Next_Link := nil;
       end else
       Begin
        ll := Last;
        New ( ll^.Next_link );
        Last := ll;
        ll := ll^.Next_link; {advance}
        LL^.Prev_Link := Last;
        LL^.Next_Link := nil;
       end;
        { CREATE ONLY ENOUGH ROOM FOR STRING LENGTH+1: }
        Getmem ( ll^.Field, Succ ( Length ( S ) ) );
        ll^.Field^ := S;
        Inc ( No_links );
        Last := ll;
    end;{add}
  Procedure ListO.Replace_Link ( LI : word; S : String );
  Begin
      If not (( LI > no_links ) OR ( LI < 1 ) or (first = nil)) then
      Begin
        Goto_Link ( LI );
        Freemem ( ll^.field, Succ ( Length ( ll^.field^ ) ) );
        Getmem ( ll^.Field, Succ ( Length ( S ) ) );
        ll^.Field^ := S;
      end;
  end;
    Procedure ListO.Insert_Link ( LI : word; S : String ) ;
    Begin
      If not (( LI > no_links ) OR ( LI < 1 ) or (first = nil)) then
      Begin
        Goto_Link ( LI );
        If Li = 1 then
        Begin {FIRST LINK}
          New ( LL );
          ll^.next_link := first;
          ll^.prev_link := nil;
          First := ll;
          ll := ll^.next_link;
          ll^.prev_link := first;
          ll := first;
        end else
        if Li = no_links then {more than one link & last link}
        Begin
          prv := ll^.prev_link;
          New ( ll );
          temp := ll;
          ll^.next_link := last;
          ll^.prev_link := prv;
          ll := Prv; ll^.next_link := temp;
          ll := last; ll^.prev_link := temp;
          ll := temp
        end else
        Begin {middle link}
          prv := ll^.prev_link;
          nxt := ll;
          New ( ll );
          temp := ll;
          ll^.next_link := nxt;
          ll^.prev_link := prv;
          ll := prv; ll^.next_link := temp;
          ll := nxt; ll^.prev_link := temp;
          ll := temp;
        end;
      Getmem ( ll^.Field, Succ ( Length ( S ) ) );
      ll^.Field^ := S;
      Inc ( No_links );
      End else If ( first = nil ) or (li > no_links) then
      Add_Link ( S );
    end;

  Procedure ListO.Remove_Link ( LI : word );
  Begin
        If not (( LI > no_links ) OR ( LI < 1 ) or (first = nil)) then
        Begin
          Goto_link ( li );
          If li=1 then {first link}
            Begin
              Temp := ll^.next_link;
              Freemem ( ll^.field, Succ ( Length ( ll^.field^ ) ) );
              Dispose ( ll );
              If no_links > 1 then
              Begin First := Temp; ll := first; ll^.prev_link := nil;end
else
              Begin first := nil; last := nil; end;
            end else
            if Li = no_links then {nore than one link & last link}
            Begin
              Last := ll^.prev_link;
              Freemem ( ll^.field, Succ ( Length ( ll^.field^ ) ) );
              Dispose ( ll );
              ll := last;
              ll^. next_link := nil;
            end else
            Begin  {more than one link & middle link}
              Temp := ll;
              Nxt := ll^.next_link;
              Prv := ll^.prev_link;
              Freemem ( ll^.field, Succ ( Length ( ll^.field^ ) ) );
              Dispose ( ll );
              LL := nxt; ll ^.prev_link := prv;
              LL := prv; ll^.next_link := Nxt;
            end;
          Dec ( No_Links );
        end
  end;

  Function  ListO.Current_Link : String;
    Begin
      If first = nil then Current_Link := ''
      else
       Current_Link := ll^.field^;
    end;

  Function  ListO.Get_Link ( LI : word ): String;
   var L : word;
    Begin
      If ( LI > no_links ) OR ( LI < 1 ) or (first = nil) then Get_Link :=''
else
       Begin
          If li < no_links shr 1 then
          Begin
            ll := first;
            For L := 1 to Pred (LI) do ll := ll^.next_link;
          end else
          Begin
            ll := last;
            For L := LI to pred (no_links) do ll := ll^.prev_link;;
          end;
          Get_Link := ll^.field^;
       end;{begin}
    end;{method}

  Function  ListO.Goto_Link ( LI : word ) : boolean;
   var L : word;
    Begin
      If ( LI > (no_links) ) OR ( LI < 0 ) or (first = nil) then Goto_Link
:=false else
       Begin
          If li < no_links shr 1 then
          Begin
            ll := first;
            For L := 1 to Pred (LI) do ll := ll^.next_link;
          end else
          Begin
            ll := last;
            For L := LI to pred (no_links) do ll := ll^.prev_link;;
          end;
          Goto_Link := true;
       end;{begin}
    end;{method}

  Function  ListO.Next_Link : Boolean;
    Begin
      If ll^.next_link <> nil then
       Begin
         ll := ll^.next_link;
         next_link := true;
       end else next_link := false;
    end;

  Function  ListO.Previous_Link : Boolean;
    Begin
      If ll^.prev_link <> nil then
       Begin
         ll := ll^.prev_link;
         Previous_link := true;
       end else Previous_link := false;
    end;

  Function  ListO.Number_of_Links : word;
   Begin
     Number_of_links := no_links;
   end;

Procedure ListO.ABC;
procedure Sort(l, r: Integer);
var
  i, j  : Integer;
  x     : String;
  ip,ij : Pointer;
  ii,jj : Pointer;
  C     : word;
begin
  i := l; j := r;
  Goto_link ( (l+r) shr 1 );
  x := ll^.field^;
  repeat
   { FIND LINK }
   If i < no_links shr 1 then
    Begin
       ll := first;
       For c := 1 to Pred (I) do ll := ll^.next_link;
    end else
    Begin
       ll := last;
       For c := I to pred (no_links) do ll := ll^.prev_link;;
    end;
    while ll^.field^ < x do Begin Inc (i); LL := ll^.next_link; end;
    ii := ll;
   { FIND LINK }
    If J < no_links shr 1 then
    Begin
      ll := first;
       For c := 1 to Pred (j) do ll := ll^.next_link;
     end else
     Begin
       ll := last;
       For c := j to pred (no_links) do ll := ll^.prev_link;;
     end;
    while x <  ll^.field^ do Begin Dec (j); LL := ll^.prev_link; end;
    jj := ll;
    if i <= j then
    begin
      { Switch string pointer field }
      ll := ii;
      ip := ll^.field;
      ll := jj;
      ij := ll^.field;
      ll^.field := ip;
      ll := ii;
      ll^.field := ij;
      Inc (i); Dec (j);
    end;
  until i > j;
  if l < j then Sort(l, j);
  if i < r then Sort(i, r);
end;
begin {sort}
 sort ( 1, no_links );
end; {abc}

  Destructor ListO.Done;
  Begin
    LL := First;
    While ll <> nil do
     Begin
       Last := ll^.next_link;
       Freemem ( ll^.field, Succ ( Length ( ll^.field^ ) ) );
       Dispose ( ll );
       ll := last;
    end;
  end;

Procedure ListO.Out_of_Memory_Message;
begin
  textbackground ( 0 ); textcolor ( 7 ); window ( 1,1,80,25 );
  clrscr;
  Writeln;
  Writeln ( 'OUT OF MEMORY -- Application terminated.');
  sound (8);
  delay ( 10 );
  sound (100);
  delay ( 10 );
  sound (8);
  delay ( 10 );
  nosound;
  halt;
end;
end.

Hope this helps. This code has been fully tested, but isn't at all
guaranteed...


Ollie B. Bommel wrote in message <6ppqkv$dn6@reader3.wxs.nl>...
>>Could anybody please demonstrate to me how to add items to a link list
>>properly.
>>
>>I guess I don't understand pointers correctly yet.
>>
>>Any help would be greatly appreciated.
>>
>>Thanks in advance..
>
>
>Hi, for a good example on this, take a look at the site www.technojock.com,
>they have a very good toolkit of TP including sources. Included are single
>and double linked lists.
>
>Hope this help you,
>
>
>Remko Weijnen