Subject: Re: Adding items in a link list... HELP!
Date: 31 Jul 1998 02:21:53 EDT
From: "Keith"
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
(
geocities.com/~franzglaser)