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