List.H

Go to the documentation of this file.

/*   _______              __
    / ___/ /  ___  __ _  / /  ___
   / /__/ _ \/ _ \/  V \/ _ \/ _ \
   \___/_//_/\___/_/_/_/_.__/\___/
*/
// CHOMBO Copyright (c) 2000-2004, The Regents of the University of
// California, through Lawrence Berkeley National Laboratory (subject to
// receipt of any required approvals from U.S. Dept. of Energy).  All
// rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// (1) Redistributions of source code must retain the above copyright
// notice, this list of conditions and the following disclaimer.
// (2) 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.
// (3) Neither the name of Lawrence Berkeley National Laboratory, U.S.
// Dept. of Energy 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.
//
// You are under no obligation whatsoever to provide any bug fixes,
// patches, or upgrades to the features, functionality or performance of
// the source code ("Enhancements") to anyone; however, if you choose to
// make your Enhancements available either publicly, or directly to
// Lawrence Berkeley National Laboratory, without imposing a separate
// written license agreement for such Enhancements, then you hereby grant
// the following license: a non-exclusive, royalty-free perpetual license
// to install, use, modify, prepare derivative works, incorporate into
// other computer software, distribute, and sublicense such Enhancements or
// derivative works thereof, in binary and source code form.
//
// TRADEMARKS. Product and company names mentioned herein may be the
// trademarks of their respective owners.  Any rights not expressly granted
// herein are reserved.
//

#ifndef _LIST_H_
#define _LIST_H_

#include "MayDay.H"
#include "Pool.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);

  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;

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

//
// 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)
{}

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 "ListImplem.H"

#endif /*_LIST_H_*/

---