/*
* DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS HEADER.
*
* Copyright 2008 Sun Microsystems, Inc. All rights reserved.
*
* THE BSD LICENSE
*
* Redistribution and use in source and binary forms, with or without
* modification, are permitted provided that the following conditions are met:
*
* Redistributions of source code must retain the above copyright notice, this
* list of conditions and the following disclaimer.
* Redistributions in binary form must reproduce the above copyright notice,
* this list of conditions and the following disclaimer in the documentation
* and/or other materials provided with the distribution.
*
* Neither the name of the nor the names of its contributors may be
* used to endorse or promote products derived from this software without
* specific prior written permission.
*
* THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
* "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
* LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
* A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
* OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
* EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
* PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR PROFITS;
* OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY,
* WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR
* OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF
* ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
*/
#ifndef _LINKED_LIST_H_
#define _LINKED_LIST_H_
/*
* Provided a template implementation of a simple linked list.
* It is a reference based container (stores the pointers to the
* objects contained) It doesn't check for duplicates etc and find
* (delete) will find(delete) the first occurence of an element.
*
* Iterator class can be used for traversal using the "++" operator.
*/
template <class C> class CList; // forward declaration
template <class C> class CListIterator; // forward declaration
template <class C> class CListConstIterator; // forward declaration
template <class C> class CListElmt {
friend class CList<C>;
friend class CListIterator<C>;
friend class CListConstIterator<C>;
private:
CListElmt(C* refP, int id) : _refP(refP), _nextP(0), _prevP(0), _id(id)
{
// Nothing really has to be done here
};
private:
int _id;
C *_refP;
#if defined(AIX)
CListElmt<C> *_nextP;
CListElmt<C> *_prevP;
#else
CListElmt *_nextP;
CListElmt *_prevP;
#endif
};
//
// NOTE : If you need the find functionality, make sure that
// class C has "==" defined.
//
template <class C> class CList {
friend class CListIterator<C>;
friend class CListConstIterator<C>;
private:
CListElmt<C>* _headP;
CListElmt<C>* _tailP;
CListElmt<C>* Lookup(C * memberP)
{
CListElmt<C> *curEltP = _headP;
while (curEltP)
{
if (curEltP->_refP == memberP)
break;
curEltP = curEltP->_nextP;
};
return(curEltP);
};
int _nextId;
int _numElts;
int autoDestroy;
C* Remove(CListElmt<C> *elmtP)
{
C *recP = NULL;
if (elmtP)
{
if (elmtP->_nextP)
elmtP->_nextP->_prevP = elmtP->_prevP;
if (elmtP->_prevP)
elmtP->_prevP->_nextP = elmtP->_nextP;
if (elmtP == _tailP)
_tailP = elmtP->_prevP;
if (elmtP == _headP)
_headP = _headP->_nextP;
recP = elmtP->_refP;
_numElts--;
delete elmtP;
};
if ( (1==autoDestroy) && recP) {
delete recP;
recP = NULL;
}
return(recP);
};
public:
CList() : _headP(0), _tailP(0), _nextId(0), _numElts(0), autoDestroy(0)
{
// Nothing really has to be done here
};
void setAutoDestroy(int setting)
{
autoDestroy = setting;
};
virtual ~CList()
{
while (_headP)
Remove(_headP);
};
int NextId()
{
return _nextId;
};
int Append(C* refP)
{
CListElmt<C> *newElmtP = new CListElmt<C>(refP, _nextId++);
newElmtP->_prevP = _tailP;
if (_tailP)
_tailP->_nextP = newElmtP;
if (_headP == 0)
_headP = newElmtP;
_tailP = newElmtP;
_numElts++;
return(newElmtP->_id);
};
int Member(C* memberP)
{
return(Lookup(memberP) != 0);
};
int Delete(C* memberP)
{
CListElmt<C> *listElmtP = Lookup(memberP);
if (listElmtP)
{
(void) Remove(listElmtP);
return(1);
}
return(0);
};
int NumEntries() const { return _numElts; }
C* Find(C* memberP) // Lookup based on == operator for class C
{
CListElmt<C> *curEltP = _headP;
while (curEltP)
{
if (curEltP->_refP == memberP)
break;
curEltP = curEltP->_nextP;
};
return(curEltP ? curEltP->_refP : 0);
};
C* First() { return(_headP ? _headP->_refP : 0); }
C* Last() { return(_tailP ? _tailP->_refP : 0); }
};
template <class C> class CListIterator {
private:
CList<C>* _listP;
int _curId;
public:
CListIterator(CList<C>* linkedListP) : _listP(linkedListP), _curId(-1)
{
// Nothing more to be done
};
virtual ~CListIterator()
{
_listP = NULL;
};
C* operator++() // Define ++ operator to move forward along the list.
{
C *valueP = NULL;
CListElmt<C> *curEltP = _listP->_headP;
while (curEltP)
{
if (curEltP->_id > _curId)
{
_curId = curEltP->_id;
return(curEltP->_refP);
}
curEltP = curEltP->_nextP;
}
_curId = -1;
return(NULL);
};
void operator()() // Overload the function operator to reset the iterator
{
_curId = -1;
};
};
template <class C> class CListConstIterator {
private:
const CList<C>* _listP;
int _curId;
public:
CListConstIterator(const CList<C>* linkedListP)
: _listP(linkedListP), _curId(-1)
{
// Nothing more to be done
};
virtual ~CListConstIterator()
{
_listP = NULL;
};
const C* operator++() // Define ++ operator to move forward along the list.
{
const C *valueP = NULL;
const CListElmt<C> *curEltP = _listP->_headP;
while (curEltP)
{
if (curEltP->_id > _curId)
{
_curId = curEltP->_id;
return(curEltP->_refP);
}
curEltP = curEltP->_nextP;
}
_curId = -1;
return(NULL);
};
void operator()() // Overload the function operator to reset the iterator
{
_curId = -1;
};
};
#endif // _LINKED_LIST_H_