home
***
CD-ROM
|
disk
|
FTP
|
other
***
search
/
Tricks of the Windows Gam…ming Gurus (2nd Edition)
/
Disc2.iso
/
msdn_vcb
/
samples
/
vc98
/
sdk
/
netds
/
winsock
/
dt_dll
/
nideque.h
< prev
next >
Wrap
C/C++ Source or Header
|
1997-10-08
|
15KB
|
787 lines
/*++
Copyright 1996-1997 Microsoft Corporation.
Copyright (c) 1995 Intel Corp
File Name:
nideque.h
Abstract:
Implements Deque structures. These are double linked lists that
can place and remove data from the beginning and end. This file
also contains an iterator for Deques. Important to notice is that
these are non-intrusive deques. Meaning the use of these classes
does not need to insert pointers into there classes to use these.
--*/
#ifndef _NIDEQUE_H_
#define _NIDEQUE_H_
#include "nowarn.h" /* turn off benign warnings */
#ifndef _WINSOCKAPI_
#define _WINSOCKAPI_ /* Prevent inclusion of winsock.h in windows.h */
#endif
#include <windows.h>
#include "nowarn.h" /* some warnings may have been turned back on */
#include "huerror.h"
template<class T> class NIDeque_c;
template<class T> class NIDequeIter_c;
// Class Name: NILNode_c
// Purpose: Simply holds data and pointer to form a double linked
// list.
// Context: Can be used anywhere.
template<class T> class NILNode_c {
friend class NIDeque_c<T>;
friend class NIDequeIter_c<T>;
private:
T Data;
NILNode_c *Next,
*Back;
public:
NILNode_c();
};
template<class T> NILNode_c<T>::NILNode_c()
{
// Make sure the members are correctly initialized.
Next = NULL;
Back = NULL;
} // NILNode_c::NILNode_c
// Class Name: NIDeque_c
// Purpose: Non-intrusize deque
// Context: Can be used anywhere.
template<class T> class NIDeque_c {
friend class NIDequeIter_c<T>;
private:
NILNode_c<T> *Root,
*Tail;
public:
NIDeque_c();
~NIDeque_c();
BOOL RemoveFromFront(T &data);
BOOL RemoveFromBack(T &data);
BOOL InsertIntoFront(T data);
BOOL InsertIntoBack(T data);
BOOL GetFromFront(T &data);
BOOL GetFromBack(T &data);
BOOL IsEmpty();
};
/*++
NIDeque_c::NIDeque_c()
Function Description:
Constructor
Arguments:
None.
Return Value:
None.
--*/
template<class T> NIDeque_c<T>::NIDeque_c()
{
Root = NULL;
Tail = NULL;
} // End of NINIDeque_c::NIDeque_c
/*++
NIDeque_c::~NIDeque_c()
Function Description:
Destructor
Arguments:
None.
Return Value:
None.
--*/
template<class T> NIDeque_c<T>::~NIDeque_c()
{
NILNode_c<T> *bptr = NULL,
*cptr = NULL;
for(bptr=NULL,cptr=Root;cptr;bptr=cptr,cptr=cptr->Next){
delete bptr;
}
delete bptr;
}
/*++
NIDeque_c::InsertIntoFront()
Function Description:
Inserts a piece of data onto the linked list.
Arguments:
Data -- Data to put on the linked list.
Return Value:
None.
--*/
template<class T> BOOL NIDeque_c<T>::InsertIntoFront(T Data)
{
NILNode_c<T> *nptr = NULL;
/* If the list contains something then move the root pointer down.
// Otherwise, put this new object on the root.
*/
if(!(nptr = new NILNode_c<T>)){
HUSetLastError(ALLOCERROR);
return FALSE;
}
nptr->Data = Data;
if(Root){
nptr->Next = Root;
Root->Back = nptr;
Root = nptr;
}else{
Root = nptr;
Tail = nptr;
}
return TRUE;
} // End of NIDeque_c::InsFront
/*++
NIDeque_c::RemoveFromFront()
Function Description:
Removes a piece of data from the front of the linked list.
Arguments:
Data -- Data to be taken off of the linked list.
Return Value:
None.
--*/
template<class T> BOOL NIDeque_c<T>::RemoveFromFront(T &Data)
{
NILNode_c<T> *nptr = NULL;
if(Root){
nptr = Root;
Root = Root->Next;
if(Root){
Root->Back = NULL;
}else{
Tail = NULL;
}
nptr->Next = NULL;
nptr->Back = NULL;
Data = nptr->Data;
delete nptr;
return TRUE;
}else{
Data = NULL;
return FALSE;
}
} // End of NIDeque_c::RemFront
/*++
NIDeque_c::InsertIntoBack()
Function Description:
Inserts a piece of data onto the back of the linked list.
Arguments:
Data -- Data to be taken off of the linked list.
Return Value:
None.
--*/
template<class T> BOOL NIDeque_c<T>::InsertIntoBack(T Data)
{
NILNode_c<T> *nptr = NULL;
if(!(nptr = new NILNode_c<T>)){
HUSetLastError(ALLOCERROR);
return FALSE;
}
nptr->Data = Data;
if(Root){
nptr->Back = Tail;
Tail->Next = nptr;
Tail = nptr;
}else{
Root = nptr;
Tail = nptr;
}
return TRUE;
} // End of NIDeque_c::InsBack
/*++
NIDeque_c::RemoveFromBack()
Function Description:
Removes a piece of data from the back of the linked list.
Arguments:
Data -- Data to be taken off of the linked list.
Return Value:
None.
--*/
template<class T> BOOL NIDeque_c<T>::RemoveFromBack(T &Data)
{
NILNode_c<T> *nptr = NULL;
if(Tail){
nptr = Tail;
Tail = Tail->Back;
if(Tail){
Tail->Next = NULL;
}else{
Root = NULL;
}
nptr->Next = NULL;
nptr->Back = NULL;
Data = nptr->Data;
delete nptr;
return TRUE;
}else{
Data = NULL;
return FALSE;
}
}
/*++
NIDeque_c::GetFromFront()
Function Description:
Gets a piece of data from the front of the linked list.
Arguments:
Data -- Data to be taken off of the linked list.
Return Value:
None.
--*/
template<class T> BOOL NIDeque_c<T>::GetFromFront(T &Data)
{
NILNode_c<T> *nptr = NULL;
if(Root){
Data = Root->Data;
return TRUE;
}else{
Data = NULL;
return FALSE;
}
} // End of NIDeque_c::GetFromFront
/*++
NIDeque_c::GetFromBack()
Function Description:
Gets a piece of data from the back of the linked list.
Arguments:
Data -- Data to be taken off of the linked list.
Return Value:
None.
--*/
template<class T> BOOL NIDeque_c<T>::GetFromBack(T &Data)
{
NILNode_c<T> *nptr = NULL;
if(Tail){
Data = Tail->Data;
return TRUE;
}else{
Data = NULL;
return FALSE;
}
} // End of NIDeque_c::RemFront
/*++
NIDeque_c::IsEmpty()
Function Description:
Determines whether a deques is empty
Arguments:
None.
Return Value:
None.
--*/
template<class T> BOOL NIDeque_c<T>::IsEmpty()
{
NILNode_c<T> *nptr = NULL;
if(Root){
return FALSE;
}else{
return TRUE;
}
} // End of NIDeque_c::IsEmpty
// Name: NIDequeIter_c
// Purpose: An iterator for the Deque_c class.
// Context: Of course only with Deque_c
template<class T> class NIDequeIter_c {
private:
NIDeque_c<T> *NIDeque;
NILNode_c<T> *Current;
private:
void RemoveData(NILNode_c<T> *cptr,T &data);
protected: // Derived class interface
inline NILNode_c<T> *GetCurrent();
inline NIDeque_c<T> *GetNIDeque();
public:
NIDequeIter_c();
NIDequeIter_c(NIDeque_c<T> &ANIDeque);
~NIDequeIter_c();
BOOL Initialize(NIDeque_c<T> &ANIDeque);
BOOL First(T &data);
BOOL Next(T &data);
BOOL Last(T &data);
BOOL Back(T &data);
BOOL Remove(T &data);
BOOL Replace(T &src,T chg);
};
//
// Private members
//
/*++
NIDequeIter_c::RemoveData()
Function Description:
To remove all of the data from the linked list.
Arguments:
cptr -- Current pointer in the linked list.
ret_data -- Return the data before deleting.
Return Value:
None.
--*/
template<class T> void NIDequeIter_c<T>::RemoveData(NILNode_c<T> *cptr,
T &ret_data)
{
NILNode_c<T> *bptr = NULL,
*nptr = NULL,
*fptr = NULL;
if(Current == cptr){
Current = cptr->Next;
}
fptr = cptr;
bptr = cptr->Back;
nptr = cptr->Next;
if(bptr != NULL){
bptr->Next = nptr;
}
if(nptr != NULL){
nptr->Back = bptr;
}
if(fptr == NIDeque->Root){
NIDeque->Root = nptr;
}
if(fptr == NIDeque->Tail){
NIDeque->Tail = bptr;
}
if(ret_data){
ret_data = fptr->Data;
}
delete fptr;
} // End of NINIDeque_c::RemoveData
//
// Public members
//
/*++
NIDequeIter_c::NIDequeIter_c()
Function Description:
Constructor.
Arguments:
ANIDeque -- The deque to iterate over.
Return Value:
None.
--*/
template<class T> NIDequeIter_c<T>::NIDequeIter_c(NIDeque_c<T> &ANIDeque)
{
NIDeque = &ANIDeque;
Current = NULL;
}
template<class T> NIDequeIter_c<T>::NIDequeIter_c()
{
NIDeque = NULL;
Current = NULL;
}
/*++
NIDequeIter_c::~NIDequeIter_c()
Function Description:
Destructor.
Arguments:
None.
Return Value:
None.
--*/
template<class T> NIDequeIter_c<T>::~NIDequeIter_c()
{
}
/*++
NIDequeIter_c::Initialize()
Function Description:
Initializes the iterator.
Arguments:
ANIDeque -> The deque to iterate over.
Return Value:
None.
--*/
template<class T> BOOL NIDequeIter_c<T>::Initialize(NIDeque_c<T> &ANIDeque)
{
NIDeque = &ANIDeque;
Current = NULL;
return TRUE;
}
/*++
NIDequeIter_c::First()
Function Description:
Returns the First data in the linked list. This primes the
current pointer so that next time the Next method is used to get
more linked list data.
Arguments:
data -- The data from the linked list.
Return Value:
TRUE -- If data is valid.
FALSE -- If data is not valid.
--*/
template<class T> BOOL NIDequeIter_c<T>::First(T &Data)
{
Current = NIDeque->Root;
if(Current != NULL){
Data = Current->Data;
return TRUE;
}else{
return FALSE;
}
} // End of NIDeque_c::First
/*++
NIDequeIter_c::Next()
Function Description:
Returns the Next data in the linked list.
Arguments:
data -- The data from the linked list.
Return Value:
TRUE -- If data is valid.
FALSE -- If data is not valid.
--*/
template<class T> BOOL NIDequeIter_c<T>::Next(T &Data)
{
if(Current){
Current = Current->Next;
if(Current){
Data = Current->Data;
return TRUE;
}
}
Data = NULL;
return FALSE;
} // End of NIDeque_c::Next
/*++
NIDequeIter_c::Last()
Function Description:
Returns the Last data in the linked list.
Arguments:
data -- The data from the linked list.
Return Value:
TRUE -- If data is valid.
FALSE -- If data is not valid.
--*/
template<class T> BOOL NIDequeIter_c<T>::Last(T &Data)
{
Current = NIDeque->Tail;
if(Current != NULL){
Data = Current->Data;
return TRUE;
}else{
return FALSE;
}
} // End of NIDeque_c::First
/*++
NIDequeIter_c::Back()
Function Description:
Returns the previous data in the linked list.
Arguments:
data -- The data from the linked list.
Return Value:
TRUE -- If data is valid.
FALSE -- If data is not valid.
--*/
template<class T> BOOL NIDequeIter_c<T>::Back(T &Data)
{
if(Current && (Current = Current->Back)){
Data = Current->Data;
return TRUE;
}else{
Data = NULL;
return FALSE;
}
} // End of NIDeque_c::Next
/*++
NIDequeIter_c::Replace()
Function Description:
Replaces src by chg.
Arguments:
src -- Data to search for.
chg -- The new data.
Return Value:
TRUE -- If data is valid.
FALSE -- If data is not valid.
--*/
template<class T> BOOL NIDequeIter_c<T>::Replace(T &src,T chg)
{
NILNode_c<T> *cptr = NULL;
if(Current != NULL){
src = Current->Data;
Current->Data = chg;
return TRUE;
}
return FALSE;
} // End of NIDeque_c::Replace
/*++
NIDequeIter_c::Remove()
Function Description:
Removes whatever the current pointer is pointing at.
Arguments:
data -- Data removed.
Return Value:
TRUE -- If data is valid.
FALSE -- If data is not valid.
--*/
template<class T> BOOL NIDequeIter_c<T>::Remove(T &data)
{
NILNode_c<T> *cptr = NULL;
T *vdata = NULL;
if(Current != NULL){
RemoveData(Current,data);
return TRUE;
}
return FALSE;
} // End of NIDeque_c<T>::Remove
#endif