352 lines
6.6 KiB
C++
352 lines
6.6 KiB
C++
// ----------------------------------------------------------------------------
|
|
//
|
|
// llist.hpp
|
|
//
|
|
// Author: Sameer Nene
|
|
// Date: 05/24/96
|
|
// Version: 0.1
|
|
// Modification History:
|
|
// Bugs:
|
|
//
|
|
// ----------------------------------------------------------------------------
|
|
|
|
#ifndef LLIST_INCLUDED
|
|
#define LLIST_INCLUDED
|
|
|
|
//#include <iostream.h>
|
|
|
|
// forward class declarations
|
|
|
|
template<class Type> class LListIter;
|
|
template<class Type> class LListManip;
|
|
|
|
template<class Type> class LLink {
|
|
|
|
// Private members
|
|
|
|
Type d_data;
|
|
LLink<Type> *d_next_p;
|
|
|
|
// Links cannot be copied or assigned
|
|
|
|
LLink(const LLink<Type>&);
|
|
LLink<Type>& operator=(const LLink<Type>&);
|
|
|
|
// Public members
|
|
|
|
public:
|
|
|
|
// Construct & Destroy
|
|
|
|
inline LLink(LLink<Type> **addLinkPtr, const Type &data);
|
|
~LLink() {}
|
|
|
|
// Modifiers
|
|
|
|
inline void setData(const Type &data);
|
|
inline void setNext(LLink<Type> *link);
|
|
inline LLink<Type>*& getNextRef(); // generally a bad practice
|
|
|
|
// Accessors
|
|
|
|
inline Type& getData();
|
|
inline LLink<Type>* getNext() const;
|
|
|
|
};
|
|
|
|
template<class Type> class LList {
|
|
|
|
// Private members
|
|
|
|
int d_length;
|
|
LLink<Type> *d_head_p;
|
|
|
|
// Friends
|
|
|
|
friend LListIter<Type>;
|
|
friend LListManip<Type>;
|
|
|
|
// Public members
|
|
|
|
public:
|
|
|
|
// Construct & Destroy
|
|
|
|
LList();
|
|
LList(const LList<Type>&);
|
|
~LList();
|
|
|
|
// Modifiers
|
|
|
|
LList<Type>& operator=(const LList<Type> &list);
|
|
LList<Type>& operator+=(const Type &i);
|
|
LList<Type>& operator+=(const LList<Type> &list);
|
|
LList<Type>& prepend(const Type &i);
|
|
LList<Type>& prepend(const LList<Type> &list);
|
|
|
|
// Accessors
|
|
|
|
int length() const;
|
|
|
|
};
|
|
|
|
//template<class Type> ostream& operator<<(ostream& o, const LList<Type>& list);
|
|
|
|
template<class Type> class LListIter {
|
|
|
|
// Private Data
|
|
|
|
LLink<Type> *d_current_p;
|
|
|
|
// Public Members
|
|
|
|
public:
|
|
|
|
// Construct and Destroy
|
|
|
|
inline LListIter(const LList<Type> &list);
|
|
inline LListIter(const LListIter<Type> &iter);
|
|
~LListIter() {}
|
|
|
|
// Modifiers
|
|
inline LListIter<Type>& operator=(const LListIter<Type> &iter);
|
|
inline void operator++();
|
|
|
|
// Accessors
|
|
inline operator const void* () const;
|
|
inline Type& operator()() const;
|
|
|
|
};
|
|
|
|
template<class Type> class LListManip {
|
|
|
|
// Private Data
|
|
|
|
LList<Type> *d_list_p;
|
|
LLink<Type> **d_current_p;
|
|
|
|
// Links cannot be copied or assigned
|
|
|
|
LListManip(const LListManip<Type> &manip);
|
|
LListManip<Type>& operator=(const LListManip<Type> &manip);
|
|
|
|
// Public Members
|
|
|
|
public:
|
|
// Construct and Destroy
|
|
inline LListManip(LList<Type> *list);
|
|
~LListManip() {}
|
|
|
|
// Modifiers
|
|
inline void operator++();
|
|
inline void insert (const Type &data);
|
|
inline void remove ();
|
|
|
|
// Accessors
|
|
inline operator const void *() const;
|
|
inline Type& operator()() const;
|
|
|
|
};
|
|
|
|
template<class Type> LLink<Type>::LLink(LLink<Type> **addLinkPtr, const Type &data) : d_next_p(*addLinkPtr), d_data(data)
|
|
{
|
|
*addLinkPtr = this;
|
|
}
|
|
|
|
template<class Type> void LLink<Type>::setData(const Type &data)
|
|
{
|
|
d_data = data;
|
|
}
|
|
|
|
template<class Type> void LLink<Type>::setNext(LLink<Type> *link)
|
|
{
|
|
d_next_p = link;
|
|
}
|
|
|
|
template<class Type> LLink<Type>*& LLink<Type>::getNextRef()
|
|
{
|
|
return d_next_p;
|
|
}
|
|
|
|
template<class Type> Type& LLink<Type>::getData()
|
|
{
|
|
return d_data;
|
|
}
|
|
|
|
template<class Type> LLink<Type>* LLink<Type>::getNext() const
|
|
{
|
|
return d_next_p;
|
|
}
|
|
|
|
template<class Type> LList<Type>::LList() : d_head_p(0), d_length(0)
|
|
{
|
|
}
|
|
|
|
template<class Type> LList<Type>::LList(const LList<Type>& list) : d_head_p(0)
|
|
{
|
|
LListManip<Type> m(this);
|
|
LListIter<Type> l(list);
|
|
|
|
while(l) {
|
|
m.insert(l());
|
|
++l;
|
|
++m;
|
|
}
|
|
}
|
|
|
|
template<class Type> LList<Type>::~LList()
|
|
{
|
|
LListManip<Type> m(this);
|
|
|
|
while(m != 0)
|
|
m.remove();
|
|
}
|
|
|
|
template<class Type> LList<Type>& LList<Type>::operator=(const LList<Type>& list)
|
|
{
|
|
LListManip<Type> m(this);
|
|
LListIter<Type> l(list);
|
|
|
|
if(this != &list) {
|
|
while(m)
|
|
m.remove();
|
|
while(l) {
|
|
m.insert(l());
|
|
++l;
|
|
++m;
|
|
}
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
template<class Type> LList<Type>& LList<Type>::operator+=(const Type &i)
|
|
{
|
|
LListManip<Type> m(this);
|
|
|
|
while(m)
|
|
++m;
|
|
m.insert(i);
|
|
return *this;
|
|
}
|
|
|
|
template<class Type> LList<Type>& LList<Type>::operator+=(const LList<Type>& list)
|
|
{
|
|
unsigned i, s;
|
|
LListIter<Type> l(list);
|
|
LListManip<Type> m(this);
|
|
|
|
while(m)
|
|
++m;
|
|
s = list.d_length;
|
|
for(i = 0; i < s; ++i) {
|
|
m.insert(l());
|
|
++m;
|
|
++l;
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
template<class Type> LList<Type>& LList<Type>::prepend(const Type &i)
|
|
{
|
|
LListManip<Type> m(this);
|
|
|
|
m.insert(i);
|
|
return *this;
|
|
}
|
|
|
|
template<class Type> LList<Type>& LList<Type>::prepend(const LList<Type> &list)
|
|
{
|
|
LListIter<Type> l(list);
|
|
LListManip<Type> m(this);
|
|
|
|
while(l) {
|
|
m.insert(l());
|
|
++m;
|
|
++l;
|
|
}
|
|
return *this;
|
|
}
|
|
|
|
template<class Type> int LList<Type>::length() const
|
|
{
|
|
return d_length;
|
|
}
|
|
|
|
//template<class Type> ostream& operator<<(ostream &o, const LList<Type>& list)
|
|
//{
|
|
// LListIter<Type> l(list);
|
|
//
|
|
// o << "[ ";
|
|
// while(l != 0) {
|
|
// o << l();
|
|
// o << " ";
|
|
// ++l;
|
|
// }
|
|
// return o << "]";
|
|
//}
|
|
|
|
template<class Type> LListIter<Type>::LListIter(const LList<Type> &list) : d_current_p(list.d_head_p)
|
|
{
|
|
}
|
|
|
|
template<class Type> LListIter<Type>::LListIter(const LListIter<Type> &iter) : d_current_p(iter.d_current_p)
|
|
{
|
|
}
|
|
|
|
template<class Type> LListIter<Type>& LListIter<Type>::operator=(const LListIter<Type> &iter)
|
|
{
|
|
d_current_p = iter.d_current_p;
|
|
return *this;
|
|
}
|
|
|
|
template<class Type> void LListIter<Type>::operator++()
|
|
{
|
|
d_current_p = d_current_p -> getNext();
|
|
}
|
|
|
|
template<class Type> Type& LListIter<Type>::operator()() const
|
|
{
|
|
return d_current_p -> getData();
|
|
}
|
|
|
|
template<class Type> LListIter<Type>::operator const void* () const
|
|
{
|
|
return d_current_p;
|
|
}
|
|
|
|
template<class Type> LListManip<Type>::LListManip(LList<Type> *list) : d_current_p(&(list -> d_head_p)), d_list_p(list)
|
|
{
|
|
}
|
|
|
|
template<class Type> void LListManip<Type>::operator++()
|
|
{
|
|
d_current_p = &((*d_current_p) -> getNextRef());
|
|
}
|
|
|
|
template<class Type> void LListManip<Type>::insert(const Type &data)
|
|
{
|
|
new LLink<Type>(d_current_p, data);
|
|
++(d_list_p -> d_length);
|
|
}
|
|
|
|
template<class Type> void LListManip<Type>::remove()
|
|
{
|
|
LLink<Type> *t = *d_current_p;
|
|
|
|
*d_current_p = (*d_current_p) -> getNext();
|
|
delete t;
|
|
--(d_list_p -> d_length);
|
|
}
|
|
|
|
template<class Type> LListManip<Type>::operator const void* () const
|
|
{
|
|
return *d_current_p;
|
|
}
|
|
|
|
template<class Type> Type& LListManip<Type>::operator()() const
|
|
{
|
|
return (*d_current_p) -> getData();
|
|
}
|
|
|
|
#endif
|