You can not select more than 25 topics
Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.
332 lines
7.8 KiB
332 lines
7.8 KiB
#ifndef __LIST_H_INCLUDED__
|
|
#define __LIST_H_INCLUDED__
|
|
|
|
//+---------------------------------------------------------------------------
|
|
//
|
|
// Copyright (C) Microsoft Corporation, 1999.
|
|
//
|
|
// File: list.h
|
|
//
|
|
// Contents: Quick 'n dirty basic templated list class.
|
|
//
|
|
// History: 04-26-1999 Alan Shi (AlanShi) Created.
|
|
//
|
|
//----------------------------------------------------------------------------
|
|
|
|
//
|
|
// ListNode
|
|
//
|
|
|
|
typedef void * LISTNODE;
|
|
|
|
template <class Type> class ListNode {
|
|
public:
|
|
ListNode(Type item);
|
|
virtual ~ListNode();
|
|
|
|
void SetNext(ListNode *pNode);
|
|
void SetPrev(ListNode *pNode);
|
|
Type GetItem();
|
|
ListNode *GetNext();
|
|
ListNode *GetPrev();
|
|
|
|
private:
|
|
DWORD _dwSig;
|
|
Type _type;
|
|
ListNode *_pNext;
|
|
ListNode *_pPrev;
|
|
};
|
|
|
|
//
|
|
// List
|
|
//
|
|
|
|
template <class Type> class List {
|
|
public:
|
|
List();
|
|
~List();
|
|
|
|
LISTNODE AddHead(const Type &item);
|
|
LISTNODE AddTail(const Type &item);
|
|
|
|
LISTNODE GetHeadPosition();
|
|
LISTNODE GetTailPosition();
|
|
void RemoveAt(LISTNODE pNode);
|
|
void RemoveAll();
|
|
LISTNODE Find(const Type &item);
|
|
int GetCount();
|
|
Type GetNext(LISTNODE &pNode);
|
|
Type GetAt(LISTNODE pNode);
|
|
LISTNODE AddSorted(const Type &item, LPVOID pfn);
|
|
|
|
public:
|
|
DWORD _dwSig;
|
|
|
|
private:
|
|
ListNode<Type> *_pHead;
|
|
ListNode<Type> *_pTail;
|
|
int _iCount;
|
|
};
|
|
|
|
//
|
|
// ListNode Implementation
|
|
//
|
|
|
|
template <class Type> ListNode<Type>::ListNode(Type item)
|
|
: _pNext(NULL)
|
|
, _pPrev(NULL)
|
|
, _type(item)
|
|
{
|
|
_dwSig = 'EDON';
|
|
}
|
|
|
|
template <class Type> ListNode<Type>::~ListNode()
|
|
{
|
|
}
|
|
|
|
template <class Type> void ListNode<Type>::SetNext(ListNode *pNode)
|
|
{
|
|
_pNext = pNode;
|
|
}
|
|
|
|
template <class Type> void ListNode<Type>::SetPrev(ListNode *pNode)
|
|
{
|
|
_pPrev = pNode;
|
|
}
|
|
|
|
template <class Type> Type ListNode<Type>::GetItem()
|
|
{
|
|
return _type;
|
|
}
|
|
|
|
template <class Type> ListNode<Type> *ListNode<Type>::GetNext()
|
|
{
|
|
return _pNext;
|
|
}
|
|
|
|
template <class Type> ListNode<Type> *ListNode<Type>::GetPrev()
|
|
{
|
|
return _pPrev;
|
|
}
|
|
|
|
|
|
//
|
|
// List Implementation
|
|
//
|
|
|
|
|
|
template <class Type> List<Type>::List()
|
|
: _pHead(NULL)
|
|
, _pTail(NULL)
|
|
, _iCount(0)
|
|
{
|
|
_dwSig = 'TSIL';
|
|
}
|
|
|
|
template <class Type> List<Type>::~List()
|
|
{
|
|
RemoveAll();
|
|
}
|
|
|
|
template <class Type> LISTNODE List<Type>::AddHead(const Type &item)
|
|
{
|
|
ListNode<Type> *pNode = NULL;
|
|
|
|
pNode = new ListNode<Type>(item);
|
|
if (pNode) {
|
|
_iCount++;
|
|
pNode->SetNext(_pHead);
|
|
pNode->SetPrev(NULL);
|
|
if (_pHead == NULL) {
|
|
_pTail = pNode;
|
|
}
|
|
else {
|
|
_pHead->SetPrev(pNode);
|
|
}
|
|
_pHead = pNode;
|
|
}
|
|
|
|
return (LISTNODE)pNode;
|
|
}
|
|
|
|
template <class Type> LISTNODE List<Type>::AddSorted(const Type &item,
|
|
LPVOID pfn)
|
|
{
|
|
ListNode<Type> *pNode = NULL;
|
|
LISTNODE pCurrNode = NULL;
|
|
LISTNODE pPrevNode = NULL;
|
|
int i;
|
|
Type curItem;
|
|
|
|
LONG (*pFN) (const Type item1, const Type item2);
|
|
|
|
pFN = (LONG (*) (const Type item1, const Type item2))pfn;
|
|
|
|
if(_pHead == NULL) {
|
|
return AddHead(item);
|
|
}
|
|
else {
|
|
pCurrNode = GetHeadPosition();
|
|
curItem = ((ListNode<Type> *) pCurrNode)->GetItem();
|
|
for (i = 0; i < _iCount; i++) {
|
|
if (pFN(item, curItem) < 1) {
|
|
pNode = new(ListNode<Type>(item));
|
|
pNode->SetPrev((ListNode<Type> *)pPrevNode);
|
|
pNode->SetNext((ListNode<Type> *)pCurrNode);
|
|
if(pPrevNode) {
|
|
((ListNode<Type> *)pPrevNode)->SetNext(pNode);
|
|
}
|
|
else {
|
|
_pHead = pNode;
|
|
}
|
|
_iCount++;
|
|
break;
|
|
}
|
|
pPrevNode = pCurrNode;
|
|
curItem = GetNext(pCurrNode);
|
|
if(i+1 == _iCount)
|
|
return AddTail(item);
|
|
}
|
|
}
|
|
|
|
return (LISTNODE)pNode;
|
|
}
|
|
|
|
template <class Type> LISTNODE List<Type>::AddTail(const Type &item)
|
|
{
|
|
ListNode<Type> *pNode = NULL;
|
|
|
|
pNode = new ListNode<Type>(item);
|
|
if (pNode) {
|
|
_iCount++;
|
|
if (_pTail) {
|
|
pNode->SetPrev(_pTail);
|
|
_pTail->SetNext(pNode);
|
|
_pTail = pNode;
|
|
}
|
|
else {
|
|
_pHead = _pTail = pNode;
|
|
}
|
|
}
|
|
|
|
return (LISTNODE)pNode;
|
|
}
|
|
|
|
template <class Type> int List<Type>::GetCount()
|
|
{
|
|
return _iCount;
|
|
}
|
|
|
|
template <class Type> LISTNODE List<Type>::GetHeadPosition()
|
|
{
|
|
return (LISTNODE)_pHead;
|
|
}
|
|
|
|
template <class Type> LISTNODE List<Type>::GetTailPosition()
|
|
{
|
|
return (LISTNODE)_pTail;
|
|
}
|
|
|
|
template <class Type> Type List<Type>::GetNext(LISTNODE &pNode)
|
|
{
|
|
Type item;
|
|
ListNode<Type> *pListNode = (ListNode<Type> *)pNode;
|
|
|
|
// Faults if you pass NULL
|
|
item = pListNode->GetItem();
|
|
pNode = (LISTNODE)(pListNode->GetNext());
|
|
|
|
return item;
|
|
}
|
|
|
|
template <class Type> void List<Type>::RemoveAll()
|
|
{
|
|
int i;
|
|
LISTNODE listNode = NULL;
|
|
ListNode<Type> *pDelNode = NULL;
|
|
|
|
listNode = GetHeadPosition();
|
|
|
|
for (i = 0; i < _iCount; i++) {
|
|
pDelNode = (ListNode<Type> *)listNode;
|
|
GetNext(listNode);
|
|
delete pDelNode;
|
|
}
|
|
|
|
_iCount = 0;
|
|
_pHead = NULL;
|
|
_pTail = NULL;
|
|
}
|
|
|
|
template <class Type> void List<Type>::RemoveAt(LISTNODE pNode)
|
|
{
|
|
ListNode<Type> *pListNode = (ListNode<Type> *)pNode;
|
|
ListNode<Type> *pPrevNode = NULL;
|
|
ListNode<Type> *pNextNode = NULL;
|
|
|
|
if (pNode) {
|
|
pPrevNode = pListNode->GetPrev();
|
|
pNextNode = pListNode->GetNext();
|
|
|
|
if (pPrevNode) {
|
|
pPrevNode->SetNext(pNextNode);
|
|
if (pNextNode) {
|
|
pNextNode->SetPrev(pPrevNode);
|
|
}
|
|
else {
|
|
// We're removing the last node, so we have a new tail
|
|
_pTail = pPrevNode;
|
|
}
|
|
delete pNode;
|
|
pNode = NULL;
|
|
}
|
|
else {
|
|
// No previous, so we are the head of the list
|
|
_pHead = pNextNode;
|
|
if (pNextNode) {
|
|
pNextNode->SetPrev(NULL);
|
|
}
|
|
else {
|
|
// No previous, or next. There was only one node.
|
|
_pHead = NULL;
|
|
_pTail = NULL;
|
|
}
|
|
delete pNode;
|
|
}
|
|
|
|
_iCount--;
|
|
}
|
|
}
|
|
|
|
|
|
template <class Type> LISTNODE List<Type>::Find(const Type &item)
|
|
{
|
|
int i;
|
|
Type curItem;
|
|
LISTNODE pNode = NULL;
|
|
LISTNODE pMatchNode = NULL;
|
|
ListNode<Type> * pListNode = NULL;
|
|
|
|
pNode = GetHeadPosition();
|
|
for (i = 0; i < _iCount; i++) {
|
|
pListNode = (ListNode<Type> *)pNode;
|
|
curItem = GetNext(pNode);
|
|
if (curItem == item) {
|
|
pMatchNode = (LISTNODE)pListNode;
|
|
break;
|
|
}
|
|
}
|
|
|
|
return pMatchNode;
|
|
}
|
|
|
|
template <class Type> Type List<Type>::GetAt(LISTNODE pNode)
|
|
{
|
|
ListNode<Type> *pListNode = (ListNode<Type> *)pNode;
|
|
|
|
// Faults if pListNode == NULL
|
|
return pListNode->GetItem();
|
|
}
|
|
|
|
#endif
|
|
|