List.H

Go to the documentation of this file.

#ifdef CH_LANG_CC
/*
*      _______              __
*     / ___/ /  ___  __ _  / /  ___
*    / /__/ _ \/ _ \/  V \/ _ \/ _ \
*    \___/_//_/\___/_/_/_/_.__/\___/
*    Please refer to Copyright.txt, in Chombo's root directory.
*/
#endif

#ifndef _LIST_H_
#define _LIST_H_

#include "MayDay.H"
#include "Pool.H"

#include "BaseNamespaceHeader.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)
  {}

  void swap(ListLink<T>* a);

  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 ();

  inline List (bool usePool);

  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);

  void transfer(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;

  void sort();

  void checkLinks() const;
protected:

  void remove (ListLink<T> *ln);

  void removeLink(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>;

  static Pool linkPool;

  bool m_usePool;
};

//
// 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
{
  CH_assert(p != 0);
  return p->val;
}

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

template <class T>
inline
const T&
ListIterator<T>::operator* () const
{
  CH_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
{
  CH_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),
  m_usePool(true)
{}

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
{
  CH_assert(head != 0);
  return head->val;
}

template <class T>
inline
T&
List<T>::lastElement () const
{
  CH_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
{
  CH_assert(li.p != 0);
  return li.p->val;
}

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

template <class T>
inline
void
List<T>::replace (ListIterator<T>& li,
                  const T&         _val)
{
  CH_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 "BaseNamespaceFooter.H"

#include "ListImplem.H"

#endif /*_LIST_H_*/

---