/* ** Command & Conquer Renegade(tm) ** Copyright 2025 Electronic Arts Inc. ** ** This program is free software: you can redistribute it and/or modify ** it under the terms of the GNU General Public License as published by ** the Free Software Foundation, either version 3 of the License, or ** (at your option) any later version. ** ** This program is distributed in the hope that it will be useful, ** but WITHOUT ANY WARRANTY; without even the implied warranty of ** MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ** GNU General Public License for more details. ** ** You should have received a copy of the GNU General Public License ** along with this program. If not, see . */ /*************************************************************************** * * * Project Name : G * * * * File Name : SLIST.H * * * * Programmer : Philip W. Gorrow * * * * Start Date : 03/11/97 * * * * Last Update : March 11, 1997 [PWG] * * * * The Single List Class is responsible for all management functions that * * can be performed on a singular linked list. It uses the SLNode class * * to track the links and maintain a pointer to the object being tracked. * * * * The singlely linked list class is non destructive. That is only * * pointers to the actual data being stored in the nodes are kept. The * * users is responsible for creating the objects to be added and deleting * * the objects once they are removed from the list if they need to be. * *-------------------------------------------------------------------------* * Functions: * * *SList::Remove_Head -- Removes the head of the list * * *SList::Remove_Tail -- Removes the tail element from the list * * SList::Get_Count -- Returns a count of the entries in the list * * *SList::Head -- Returns the head node of the list * * *SList::Tail -- Returns the tail node of the list * * SList::Is_Empty -- Returns true if the list is empty * * SList::Add_Head -- Adds a node to the head of the list * * SList::Add_Head -- Adds a list to to the head of the list * * SList::Add_Tail -- Adds a node to the tail of the list * * SList::Add_Tail -- Adds a list to the tail of the list * * *SList::Find_Node -- returns first node in list matching the input * * - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - */ #if _MSC_VER >= 1000 #pragma once #endif // _MSC_VER >= 1000 #ifndef __SLIST_H__ #define __SLIST_H__ #include "slnode.h" #ifndef NULL #define NULL 0L #endif template class SList { private: SLNode *HeadNode; // Note: Constructor not called for pointer. SLNode *TailNode; public: // // This constructor is inlined because G++ will not create the // constructor correctly if it is not defined within the class // definition. // SList(void) { HeadNode = NULL; TailNode = NULL; }; virtual ~SList(void) { Remove_All(); }; // // Returns the current head of the list. Used to walk the list. // SLNode *Head(void) const; SLNode *Tail(void) const; SLNode *Find_Node(T * data) const; virtual bool Add_Head(T *data); // Add object to head of list virtual bool Add_Head(SList& list); // Add a list to head of list virtual bool Add_Tail(T *data); // Add object to tail of list virtual bool Add_Tail(SList& list); // Add a list to tail of list virtual T *Remove_Head(void); // Remove head node from list virtual T *Remove_Tail(void); // Remove tail node from list virtual bool Remove(T *element); // remove an individual element virtual void Remove_All(void); // Remove all nodes from list // Insert before oldnode, if oldnode is NULL then before head node virtual bool Insert_Before(T *newnode, T *oldnode = NULL); // Could possibly implement an InsertBefore that operates on a whole list // Insert after oldnode, if oldnode is NULL then insert at head virtual bool Insert_After(T *newnode, T *oldnode = NULL); // Could possibly implement an InsertAfter that operates on a whole list virtual bool Is_Empty(void) const; // True if list is empty virtual long Get_Count(void) const; // Returns number of nodes in list }; /************************************************************************** * SList::Insert_Before -- Inserts entry prior to specified entry * * * * Inserts an entry prior to the specified entry in the list. If the * * specified entry is null, it will add it prior to the head of the * * list. Returns true if sucessfully added, false otherwise. * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template bool SList::Insert_Before(T *newnode, T *oldnode) { // if not adding anything then just skip the add. if (newnode == NULL) return false; // if there is no head to the list then add it to head if (oldnode == NULL || HeadNode == NULL || HeadNode->Data() == oldnode) { return(Add_Head(newnode)); } // now we need to walk the list in an attempt to add the // node. since we are a singlely linked list we need // to stop one prior to the entry. SLNode *cur; for (cur=HeadNode; cur->Next() && cur->Next()->Data() != oldnode; cur=cur->Next()) {} // Verify that we found the entry as it might not have been in the list. // Note: Cur will be valid because it wont be assigned unless Next is // valid. if (cur->Next() != NULL && cur->Next()->Data() == oldnode) { SLNode *temp = new SLNode (newnode); temp->Set_Next(cur->Next()); cur->Set_Next(temp); return(true); } return(false); } /************************************************************************** * SList::Insert_After -- Inserts an entry after specified entry * * * * Inserts an entry after to the specified entry in the list. If the * * specified entry is null, it will add it prior to the head of the list. * * Returns true if sucessfully added, false otherwise. * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template bool SList::Insert_After(T *newnode, T *oldnode) { if (newnode == NULL) return false; if (oldnode == NULL || HeadNode == NULL) { return(Add_Head(newnode)); } // Search for oldnode in list SLNode *cur; for (cur = HeadNode; cur && cur->Data() != oldnode; cur = cur->Next()) {} // Did we find the data we want to insert after? if (cur != NULL && cur->Data() == oldnode) { if (cur == TailNode) { // Inserting after tail return(Add_Tail(newnode)); } SLNode *temp = new SLNode(newnode); temp->Set_Next(cur->Next()); cur->Set_Next(temp); return true; } return false; } /************************************************************************** * SList::Remove_All -- Removes all of the entries in the current list * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template void SList::Remove_All(void) { SLNode *next; for (SLNode *cur = HeadNode; cur; cur = next) { next = cur->Next(); delete cur; } HeadNode = TailNode = NULL; } /************************************************************************** * SList::Remove -- Removes an element in the list. * * * * INPUT: * * * * OUTPUT: true if element could be removed, false if it could not be * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template bool SList::Remove(T *element) { // if not adding anything then just skip the add. if (element == NULL || HeadNode == NULL) return false; // if the head is the element in question remove it if (HeadNode->Data() == element) { return(Remove_Head() != NULL ? true : false); } // now we need to walk the list in an attempt to add the // node. since we are a singlely linked list we need // to stop one prior to the entry. SLNode *cur; for (cur = HeadNode; cur->Next() && cur->Next()->Data() != element; cur=cur->Next()) { } // Verify that we found the entry as it might not have been in the list. // Note: Cur will be valid because it wont be assigned unless Next is // valid. if (cur->Next() != NULL && cur->Next()->Data() == element) { SLNode *temp = cur->Next(); cur->Set_Next(temp->Next()); if (temp == TailNode) TailNode = cur; delete temp; return true; } return(false); } /************************************************************************** * *SList::Remove_Head -- Removes the head of the list * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template T *SList::Remove_Head(void) { if (HeadNode == NULL) // Should make an assertion here instead! return ((T* )NULL); SLNode *temp = HeadNode; HeadNode = HeadNode->Next(); if (HeadNode == NULL) // Do we have empty list now? TailNode = NULL; T *data = temp->Data(); delete temp; return data; } // // Removes the tail of the list and returns a data pointer to the // element removed. Warning! On a singlely linked list it is // slow as hell to remove a tail! If you need to frequently remove // tails, then you should consider a doubly linked list. // /************************************************************************** * *SList::Remove_Tail -- Removes the tail element from the list * * * * INPUT: none * * * * OUTPUT: returns a pointer to the element removed * * * * WARNINGS: On a singlely linked list it is slow as hell to remove a * * tail! If you need to frequently remove tails, then you * * should consider a doubly linked list. * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template T *SList::Remove_Tail(void) { if (HeadNode == NULL) // Should make an assertion here instead! return ((T *)NULL); T* data = TailNode->Data(); return (Remove(data) ? data : (T*)NULL); } /************************************************************************** * SList::Get_Count -- Returns a count of the entries in the list * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template inline long SList::Get_Count(void) const { long count = 0; for (SLNode *cur = HeadNode; cur; cur = cur->Next()) count++; return count; } /************************************************************************** * *SList::Head -- Returns the head node of the list * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template inline SLNode *SList::Head(void) const { return(HeadNode); } /************************************************************************** * *SList::Tail -- Returns the tail node of the list * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template inline SLNode *SList::Tail(void) const { return(TailNode); } /************************************************************************** * SList::Is_Empty -- Returns true if the list is empty * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template inline bool SList::Is_Empty(void) const { return( HeadNode == NULL ? true : false); } /************************************************************************** * SList::Add_Head -- Adds a node to the head of the list * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template bool SList::Add_Head(T *data) { // we don't deal with lists that point to nothing if (!data) return false; SLNode *temp = new SLNode(data); temp->Set_Next(HeadNode); HeadNode = temp; if (!TailNode) TailNode = temp; return true; } /************************************************************************** * SList::Add_Head -- Adds a list to to the head of the list * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template bool SList::Add_Head(SList& list) { if (list.HeadNode == NULL) return false; // Save point for initial add of element. SLNode *addpoint = NULL; // We traverse list backwards so nodes are added in right order. for (SLNode *cur = list.HeadNode; cur; cur = cur->Next()) if (addpoint) { SLNode *temp = new SLNode(cur->Data()); temp->Set_Next(addpoint->Next()); addpoint->Set_Next(temp); addpoint = temp; } else { Add_Head(cur->Data()); addpoint = HeadNode; } return true; } /************************************************************************** * SList::Add_Tail -- Adds a node to the tail of the list * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template bool SList::Add_Tail(T *data) { if (data == NULL) return false; SLNode *temp = new SLNode (data); if (HeadNode == NULL) { // empty list HeadNode = TailNode = temp; } else { // non-empty list TailNode->Set_Next(temp); TailNode = temp; } return true; } /************************************************************************** * SList::Add_Tail -- Adds a list to the tail of the list * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 03/11/1997 PWG : Created. * *========================================================================*/ template bool SList::Add_Tail(SList& list) { if (list.HeadNode == NULL) return false; for (SLNode *cur = list.HeadNode; cur; cur = cur->Next()) Add_Tail(cur->Data()); return true; } /************************************************************************** * *SList::Find_Node -- returns first node in list matching the input * * * * INPUT: * * * * OUTPUT: * * * * WARNINGS: * * * * HISTORY: * * 08/22/1997 GH : Created. * *========================================================================*/ template inline SLNode *SList::Find_Node(T * data) const { SLNode * cur; for (cur = HeadNode; cur && cur->Data() != data; cur = cur->Next()); return cur; } #endif