[Back to POINTERS SWAG index] [Back to Main SWAG index] [Original]

    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.

[Back to POINTERS SWAG index] [Back to Main SWAG index] [Original]