List.H

Go to the documentation of this file.

/* _______              __
  / ___/ /  ___  __ _  / /  ___
 / /__/ _ \/ _ \/  ' \/ _ \/ _ \
 \___/_//_/\___/_/_/_/_.__/\___/ 
*/
//
// This software is copyright (C) by the Lawrence Berkeley
// National Laboratory.  Permission is granted to reproduce
// this software for non-commercial purposes provided that
// this notice is left intact.
// 
// It is acknowledged that the U.S. Government has rights to
// this software under Contract DE-AC03-765F00098 between
// the U.S.  Department of Energy and the University of
// California.
//
// This software is provided as a professional and academic
// contribution for joint exchange. Thus it is experimental,
// is provided ``as is'', with no warranties of any kind
// whatsoever, no support, no promise of updates, or printed
// documentation. By using this software, you acknowledge
// that the Lawrence Berkeley National Laboratory and
// Regents of the University of California shall have no
// liability with respect to the infringement of other
// copyrights by any part of this software.
//


#ifndef _LIST_H_
#define _LIST_H_

#include "MayDay.H"


template <class T> class ListLink;
template <class T> class ListIterator;
template <class T> class List;

// this is so this internal class doesn't appear in doxygen documentation
#ifndef DOXYGEN


// Internal helper class for the List class
template <class T>
class ListLink
{
private:
    friend class List<T>;
    friend class ListIterator<T>;

    ListLink (const T&     _val,
              ListLink<T>* _pre,
              ListLink<T>* _suc)
        : val(_val),
          pre(_pre),
          suc(_suc)
    {}

private:
    T            val;
    ListLink<T>* pre;
    ListLink<T>* suc;
};

#endif // doxygen 



template <class T>
class ListIterator
{
public:
  
  inline ListIterator (const List<T>& aList);
  
  inline ListIterator (const ListIterator<T>& rhs);
  
  inline void rewind ();


  inline void begin();

  inline const T& operator() () const;
 
  inline T& operator() () ;

  inline const T& operator* () const;


  inline operator bool () const;


  inline bool ok() const ;
  
  inline bool operator! () const;

  inline const T& value () const;
  
  const T& value ();
  

  inline ListIterator<T>& operator++ ();


  inline ListIterator<T>& operator-- ();


  inline ListIterator<T> operator-- (int);


  inline ListIterator<T> operator++ (int);
  

  inline bool operator== (const ListIterator<T>&) const;
  
  
  inline bool operator!= (const ListIterator<T>&) const;

protected:

  inline ListIterator (const List<T>& _list,
                       ListLink<T>*   _p);

  const List<T>& list;

  ListLink<T>* p;

private:
    friend class List<T>;
    //
    // These are disallowed.
    //
    ListIterator ();
    ListIterator<T>& operator= (const ListIterator<T>&);
};



template <class T>
class List
{
public:
    
  inline List ();
  
  
  List (const List<T>& rhs);
  
  List<T>& operator= (const List<T>& rhs);


  inline ~List();

  inline void prepend (const T& value);

  inline void append (const T& value);

  void add (const T& value);
  
  void join (const List<T>& src);


  void catenate (List<T>& src);

  void clear ();


  inline List<T>* copy () const;


  inline T& firstElement () const;

  inline T& lastElement () const;
  

  bool includes (const T& value) const;
  

  bool operator== (const List<T>& rhs) const;
  
  bool operator!= (const List<T>& rhs) const;
  
  
  inline bool isEmpty () const;
  
  inline bool isNotEmpty () const;
  
  int length () const;
  
  
  inline void removeFirst ();
  
  inline void removeLast ();
  
  inline const T& operator[] (const ListIterator<T>& li) const;
  
  inline T& operator[] (const ListIterator<T>& li);

  void remove (const T& value);
  
  void remove (const List<T>& lst);

  void remove (ListIterator<T>& lit);

  inline void replace (ListIterator<T>& li,
                       const T&         val);
  
  inline void addAfter (ListIterator<T>& lit,
                        const T&         val);
  
  inline void addBefore (ListIterator<T>& lit,
                         const T&         val);

  inline ListIterator<T> listIterator () const;

  inline ListIterator<T> first () const;


  inline ListIterator<T> last () const;
  
protected:

  void remove (ListLink<T> *ln);

  ListLink<T>* addBefore (ListLink<T>* ln,
                          const T&     val);

  ListLink<T>* addAfter (ListLink<T>* ln,
                         const T&     val);

  ListLink<T>* head;


  ListLink<T>* tail;

  friend class ListIterator<T>;
  
};

//
// Inlines.
//

//
// The ListIterator stuff.
//

template <class T>
inline
ListIterator<T>::ListIterator (const List<T>& _list,
                               ListLink<T>*   _p)
  : list(_list),
    p(_p)
{}

template <class T>
inline
ListIterator<T>::ListIterator (const List<T>& aList)
  : list(aList)
{
  p = list.head;
}

template <class T>
inline
ListIterator<T>::ListIterator (const ListIterator<T>& li)
  : list(li.list),
    p(li.p)
{}

template <class T>
inline
void
ListIterator<T>::rewind ()
{
  p = list.head;
}

template <class T>
inline
void
ListIterator<T>::begin ()
{
  p = list.head;
}

template <class T>
inline
const T&
ListIterator<T>::operator() () const
{
  assert(p != 0);
  return p->val;
}

template <class T>
inline
T&
ListIterator<T>::operator() () 
{
  assert(p != 0);
  return p->val;
}

template <class T>
inline
const T&
ListIterator<T>::operator* () const
{
  assert(p != 0);
  return p->val;
}

template <class T>
inline
bool
ListIterator<T>::ok() const
{
  return p != 0 ? true : false;
}

template <class T>
inline
ListIterator<T>::operator bool () const
{
  return ok() ;
}

template <class T>
inline
bool
ListIterator<T>::operator! () const
{
  return p == 0 ? true : false;
}

template <class T>
inline
const T&
ListIterator<T>::value () const
{
  assert(p != 0);
  return p->val;
}

template <class T>
inline
ListIterator<T>&
ListIterator<T>::operator++ ()
{
  if (p)
    p = p->suc;
  return *this;
}

template <class T>
inline
ListIterator<T>&
ListIterator<T>::operator-- ()
{
  if (p)
    p = p->pre;
  return *this;
}

template <class T>
inline
ListIterator<T>
ListIterator<T>::operator++ (int)
{
  const ListIterator<T> li = *this;
  ++(*this);
  return li;
}

template <class T>
inline
ListIterator<T>
ListIterator<T>::operator-- (int)
{
  const ListIterator<T> li = *this;
  --(*this);
  return li;
}

template <class T>
inline
bool
ListIterator<T>::operator== (const ListIterator<T>& _li) const
{
  return (&list == &_li.list && p == _li.p) ? true : false;
}

template <class T>
inline
bool
ListIterator<T>::operator!= (const ListIterator<T>& _li) const
{
  return ! ListIterator<T>::operator==(_li);
}

//
// List stuff.
//

template <class T>
inline
List<T>::List ()
    : head(0),
      tail(0)
{}

template <class T>
inline
List<T>::~List ()
{
  clear();
}

template <class T>
inline
void
List<T>::prepend (const T& value)
{
  addBefore(head, value);
}

template <class T>
inline
void
List<T>::append (const T& value)
{
  addAfter(tail, value);
}

template <class T>
inline
List<T>*
List<T>::copy () const
{
  List<T>* newlist = new List<T>(*this);
  if (newlist == 0)
    MayDay::Error("Out of memory in List::copy ");
  return newlist;
}

template <class T>
inline
T&
List<T>::firstElement () const
{
  assert(head != 0);
  return head->val;
}

template <class T>
inline
T&
List<T>::lastElement () const
{
  assert(tail != 0);
  return tail->val;
}

template <class T>
inline
bool
List<T>::isEmpty () const
{
  return head == 0 && tail == 0;
}

template <class T>
inline
bool
List<T>::isNotEmpty () const
{
  return !isEmpty();
}

template <class T>
inline
void
List<T>::removeFirst ()
{
  remove(head);
}

template <class T>
inline
void
List<T>::removeLast ()
{
  remove(tail);
}

template <class T>
inline
const T&
List<T>::operator[] (const ListIterator<T>& li) const
{
  assert(li.p != 0);
  return li.p->val;
}

template <class T>
inline
T&
List<T>::operator[] (const ListIterator<T>& li)
{
  assert(li.p != 0);
  return li.p->val;
}

template <class T>
inline
void
List<T>::replace (ListIterator<T>& li,
                  const T&         _val)
{
  assert(li.p != 0);
  li.p->val = _val;
}

template <class T>
inline
void
List<T>::addAfter (ListIterator<T>& lit,
                   const T&         val)
{
  addAfter(lit.p, val);
}

template <class T>
inline
void
List<T>::addBefore (ListIterator<T>& lit,
                    const T&         val)
{
  addBefore(lit.p, val);
}

template <class T>
inline
ListIterator<T>
List<T>::first () const
{
  return ListIterator<T>(*this,head);
}

template <class T>
inline
ListIterator<T>
List<T>::listIterator () const
{
  return ListIterator<T>(*this,head);  //[NOTE: same as first()]
}

template <class T>
inline
ListIterator<T>
List<T>::last () const
{
  return ListIterator<T>(*this,tail);
}

#include "ListImplem.H"

#endif /*_LIST_H_*/

---