/*
** 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