Contributor: MICHAEL DALES
unit Lists;
{--------------------------------------------------------------------------}
{ Abstract Data Type for dynamically sized list }
{ By Michael Dales 30th May 1996 }
{ }
{ Here is a simple list unit, that has the advantage of being dynamically }
{ sized, unlike normal arrays. To use the list you only need to know the }
{ data type names and the methods declared in the interface of this unit }
{ are used to manipulate them without the need to know the underlying }
{ representation. }
{ }
{ Deaclare your list variable to be of type TList, and remeber to use }
{ CreateList on it before you carry out any operations using it. Data is }
{ stored in nodes as pointers, just so you can have a list which isn't }
{ tied to just one kind of data type. Remeber though that because of this }
{ you'll need to typecast your pointers when you retrieve them from the }
{ list. Each node is has a type called PListNode, and an invalid node has }
{ the value null. }
{ }
{ Email comments to: 9402198d@udcf.gla.ac.uk }
{ URL: http://www.gla.ac.uk/Clubs/WebSoc/~9402198d/index.html }
{--------------------------------------------------------------------------}
interface
const null = nil; {Non specific terminator}
type PListNode = ^TListNode; {Pointer to node}
TListNode = record {Node record}
Item : Pointer; {Pointer to node data}
Next : PListNode; {Next node}
Previous : PListNode; {Previous node}
end;
TList = 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 : TList);
{DestroyList - Frees up all memory used by list and sets list to nil}
procedure DestroyList(var L : TList);
{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 : TList; Data : Pointer);
{DeleteListElement - Deletes an element passed.}
procedure DeleteNode(var L : TList; ANode : PListNode);
{GetFirstNode - Returns the first node in a given list}
function GetFirstNode(L:TList):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);
{UpdateNode - Replaces a nodes details with new ones}
procedure UpdateNode(Node:PListNode; Data:Pointer);
{--------------------------------------------------------------------------}
implementation
{--------------------------------------------------------------------------}
{CreateList - Initiates a new list}
procedure CreateList(var L : TList);
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 : TList);
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}
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 : TList);
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 : TList) : PListNode;
begin
GetFirstNode := L.First;
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;
{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:TList; Data:Pointer);
var temp : PListNode;
begin
new(temp); {Create new node}
with temp^ do {Fill node}
begin
Item := Data;
Next := nil;
Previous := L.Rear;
end;
If (L.Size = 0) then {If empty list...}
begin
L.First := temp; {Add as first node}
L.Rear := temp;
end else {else add at end}
begin
L.Rear^.Next := temp; {Make old rear of list point to new}
L.Rear := temp; {Make rear point to new node}
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;
{DeleteListElement - Deletes an element passed.}
procedure DeleteNode(var L : TList; ANode : PListNode);
begin
if (L.Size = 1) or (ANode^.Next = nil) then {If we're deeling with}
RemoveLastNode(L) {last node then that's easy}
else {otherwise...}
begin
if (ANode = L.First) then {if we're deleting the first node}
begin
L.First := L.First^.Next; {Start list from second node}
L.First^.Previous := nil; {Set new starts previous link}
Dispose(ANode); {Dispose of old first}
end else
begin
ANode^.Previous^.Next := ANode^.next; {Move pointers...}
ANode^.Next^.Previous := ANode^.Previous;
Dispose(ANode); {Dispose of node}
end;
L.Size := L.Size-1; {Note new list size}
end;
end;
end.