Contributor: MICHAEL DALES
unit OrdLists;
{--------------------------------------------------------------------------}
{ Abstract Data Type for a key ordered list. }
{ By Michael Dales 30th May 1996 }
{ }
{ A simple ordered list ADT. All you need to use are the decalred }
{ methods below, you don't even need to know how the type works either. }
{ To use the list just assign the list variable the type TOrdList, and }
{ rember to use CreateList before you try and do any operations on it. The }
{ data in each node is stored as a pointer, and each node has a key by }
{ which the list is ordered which is a 32 character array, type called }
{ TKey. The type of each node is called PListNode. }
{ }
{ I've designed this as an abstract data type, which means that although }
{ you can look at the code and see how I've implemented it, you can (and }
{ should) use just the methods I've declared in the interface of this }
{ unit. Hence the word abstract in abstract data type. So there. }
{ }
{ If you have any comments the email me at: 9402198d@udcf.gla.ac.uk }
{ URL: http://www.gla.ac.uk/Clubs/WebSoc/~9402198d/index.html }
{--------------------------------------------------------------------------}
interface
uses Strings;
const null = nil; {Non specific terminator}
type TKey = array[0..32] of char;
PListNode = ^TListNode; {Pointer to node}
TListNode = record {Node record}
Key : TKey; {Key for node}
Item : Pointer; {Pointer to node data}
Next : PListNode; {Next node}
Previous : PListNode; {Previous node}
end;
TOrdList = record {Holder for list}
First : PListNode; {Pointer to start of list}
Rear : PListNode; {Pointer to end of list}
Size : integer; {Size of list}
end;
{CreateList - Initiates a new list}
procedure CreateList(var L : TOrdList);
{DestroyList - Frees up all memory used by list and sets list to nil}
procedure DestroyList(var L : TOrdList);
{AddNewNode - Adds new node to list L, filling it with the data
supplied. Returns true is new node sucessfully
added, otherwise returns false.}
procedure AddNewNode(var L : TOrdList; AKey : PChar; Data : Pointer);
{DeleteNode - Deletes an element passed.}
procedure DeleteNode(var L : TOrdList; ANode : PListNode);
{GetFirstNode - Returns the first node in a given list}
function GetFirstNode(L : TOrdList) : PListNode;
{FindFirstNode - Finds the first node with a matching key}
function FindFirstNode(L : TOrdList; AKey : TKey) : PListNode;
{GetNextNode - Returns the successor of the given node}
function GetNextNode(Node : PListNode) : PListNode;
{GetNodeData - Returns the data in a specific node}
procedure GetNodeData(Node : PListNode; var Data : Pointer);
{GetNodeKey - Returns the key for a given node}
procedure GetNodeKey(Node : PListNode; var AKey : TKey);
{UpdateNode - Replaces a nodes details with new ones}
procedure UpdateNode(Node : PListNode; Data : Pointer);
{--------------------------------------------------------------------------}
implementation
{--------------------------------------------------------------------------}
{CreateList - Initiates a new list}
procedure CreateList(var L : TOrdList);
begin
L.First := nil; {No list yet}
L.Rear := nil;
L.Size := 0; {No length yet}
end;
{RemoveLastNode - Deletes last node on the list}
procedure RemoveLastNode(var L : TOrdList);
begin
with L do {With the list}
begin
if Size > 0 then {If nodes in list}
begin
if Size = 1 then {If just one node}
begin
if First^.Item <> nil then {If data in node then}
Dispose(First^.Item); {Dispose of it}
Dispose(First); {Dispose of first node}
First := nil;
Rear := nil; {Set rear to nil}
end else
begin {If more than one node}
if Rear^.Item <> nil then
Dispose(Rear^.Item);
Rear := Rear^.Previous; {Set rear to second last}
Dispose(Rear^.Next); {Remove last node}
end;
Size := Size-1; {Decrement list size}
end;
end;
end;
{DestroyList - Frees up all memory used by list and sets list to nil}
procedure DestroyList(var L : TOrdList);
begin
while L.First <> nil do {While still nodes left}
RemoveLastNode(L); {Remove last node}
CreateList(L);
end;
{GetFirstNode - Returns the first node in a given list}
function GetFirstNode(L : TOrdList) : PListNode;
begin
GetFirstNode := L.First;
end;
{FindFirstNode - Finds the first node with a matching key}
function FindFirstNode(L : TOrdList; AKey : TKey) : PListNode;
var temp : PListNode;
found : boolean;
begin
found := false;
temp := L.First;
while (temp <> nil) and not found do
begin
found := temp^.Key = AKey;
if not found then temp := temp^.Next;
end;
FIndFirstNode := temp;
end;
{GetNextNode - Returns the successor of the given node}
function GetNextNode(Node : PListNode) : PListNode;
begin
if Node <> nil then
GetNextNode := Node^.Next
else
GetNextNode := nil;
end;
{GetNodeData - Returns the data in a specific node}
procedure GetNodeData(Node : PListNode; var Data : Pointer);
begin
if Node <> nil then
Data := Node^.Item
else
Data := nil;
end;
{GetNodeKey - Returns the key for a given node}
procedure GetNodeKey(Node : PListNode; var AKey : TKey);
begin
if node <> nil then
AKey := Node^.Key;
end;
{AddNewNode - Adds new node to list L, filling it with the data
supplied. Returns true is new node sucessfully
added, otherwise returns false.}
procedure AddNewNode(var L : TOrdList; AKey : PChar; Data : Pointer);
var temp : PListNode;
CurNode : PListNode;
Match : boolean;
begin
new(temp); {Create new node}
with temp^ do {Fill node}
begin
StrCopy(Key, AKey);
Item := Data;
Next := nil;
Previous := nil;
end;
if L.Size = 0 then
begin
L.First := temp;
L.Rear := temp;
end else
begin
CurNode := L.First;
Match := false;
while (CurNode <> nil) and not Match do
begin
if StrComp(CurNode^.Key, AKey) >= 0 then
Match := true
else
CurNode := CurNode^.Next;
end;
if not Match then
begin
temp^.Previous := L.Rear;
L.Rear^.Next := temp;
L.Rear := temp;
end else
begin
temp^.Next := CurNode;
temp^.Previous := CurNode^.Previous;
if (CurNode^.Previous <> nil) then
CurNode^.Previous^.Next := temp
else
L.First := temp;
CurNode^.Previous := temp;
end;
end;
L.Size := L.Size + 1; {Increment list length}
end;
{UpdateNode - Replaces a nodes details with new ones}
procedure UpdateNode(Node : PListNode; Data : Pointer);
begin
if Node <> nil then
begin
Node^.Item := Data;
end;
end;
{DeleteNode - Deletes an element passed.}
procedure DeleteNode(var L : TOrdList; ANode : PListNode);
begin
if (L.Size = 1) or (ANode^.Next = nil) then
RemoveLastNode(L)
else
begin
if (ANode = L.First) then
begin
L.First := L.First^.Next;
L.First^.Previous := nil;
Dispose(ANode);
end else
begin
ANode^.Previous^.Next := ANode^.next;
ANode^.Next^.Previous := ANode^.Previous;
Dispose(ANode);
end;
L.Size := L.Size-1;
end;
end;
end.