LinkedList.h

/*  _________________________________________________________________________
 *
 *  UTILIB: A utility library for developing portable C++ codes.
 *  Copyright (c) 2001, Sandia National Laboratories.
 *  This software is distributed under the GNU Lesser General Public License.
 *  For more information, see the README file in the top UTILIB directory.
 *  _________________________________________________________________________
 */

//
// LinkedList.h
//
#ifndef __LinkedList_h
#define __LinkedList_h

#ifdef __GNUC__
#pragma interface
#endif

#ifdef NON_ANSI
#include <iostream.h>
#else
#include <iostream>
using namespace std;
#endif

#ifndef ANSI_HDRS
#include <stdlib.h>
#include <stddef.h>
#else
#include <cstdlib>
#include <cstddef>
#endif

#include "errmsg.h"
//#include "utilib_dll.h"
#include "_generic.h"

template <class T>
class UTILIB_API LinkedList;



template <class T>
class UTILIB_API ListItem {

  friend class LinkedList<T>;

public:

  ListItem( T& Data_)
                : Data(Data_) {next = prev = 0;}

  T& data() 
                {return Data;}
  int operator==(const ListItem<T>& item) 
                {return (Data == item.Data);}

  static void delete_unused();

protected:

  T Data;
  ListItem *next;
  ListItem *prev;

  static ListItem* unused;

  void *operator new(size_t);
  void operator delete(void*, size_t);

};



template <class T>
class UTILIB_API LinkedList
{
protected:

  enum {
        stackLL = 0,    
        queueLL = 1     
        };

public:

  LinkedList()
                { mode=queueLL; counter++; first = last = 0; Len=0; }  

  virtual ~LinkedList();

  ListItem<T>* find( T& data);
  ListItem<T>* head() const
                {return first;}
  ListItem<T>* tail() const
                {return last;}
  ListItem<T>* next(ListItem<T>* item) const
                {return item->next;}

  T& top()
                {
                if (Len <= 0) {
                   ErrAbort("LinkedList::top -- Empty list");
                   exit(0);
                   }
                if (mode == queueLL) return first->data();
                return last->data();
                }
  void add( T& data)
                { insert(data); }
  void add( T& data, ListItem<T>*& item)
                { item = insert(data); }
  ListItem<T>* insert( T& data, ListItem<T>* item = (ListItem<T>*)0);

  void remove( T& data) 
                {
                if (mode==queueLL) 
                   extract(first,data); 
                else
                   extract(last,data);
                }
  void remove( ListItem<T>* item) 
                {extract(item);}
  void remove(ListItem<T>* item, T& data) 
                {extract(item,data);}

  int empty() const;
  operator int() const
                {return (first == 0 ? FALSE : TRUE);}
  int size() const 
                {return Len;}
  int len() const 
                {return Len;}
  void stack_mode()
                {mode = stackLL;}
  void queue_mode()
                {mode = queueLL;}

protected:

  int mode;
  void extract(ListItem<T>* item);
  void extract(ListItem<T>* item, T& data)
                {data = item->Data; extract(item);}

  ListItem<T> *first;
  ListItem<T> *last;
  int Len;

  static int counter;

};


template <class T>
inline UTILIB_API LinkedList<T>& operator>>(LinkedList<T>& list, T& data)
{list.remove(data); return list;}

template <class T>
inline UTILIB_API LinkedList<T>& operator<<(LinkedList<T>& list, T& data)
{list.add(data); return list;}



//
// ListItem methods
//

template <class T>
ListItem<T> *ListItem<T>::unused = NULL;


template <class T>
void ListItem<T>::delete_unused()
{
ListItem<T> *curr = unused;
ListItem<T> *next;

while (curr) {
  next = curr->next;
  char* tmp = (char*) curr;
  delete [] tmp;
  curr = next;
  }

unused=NULL;
}


template <class T>
void* ListItem<T>::operator new(size_t size)
{
if (!unused)
   return new char[size];
else {
   ListItem<T> *ptr = unused;
   unused = unused->next;
   return ptr;
   }
}


template <class T>
void ListItem<T>::operator delete(void *p, size_t)
{
((ListItem<T>*)p)->next = unused;
unused = (ListItem<T>*)p;
}



//
// LinkedList methods
//

template <class T>
int LinkedList<T>::counter=0;


template <class T>
LinkedList<T>::~LinkedList()
{
while (!empty())
  extract(first);
counter--;

if (!counter)
   ListItem<T>::delete_unused();
}


template <class T>
int LinkedList<T>::empty() const
{
return (first == NULL ? TRUE : FALSE) ;
}


template <class T>
void LinkedList<T>::extract(ListItem<T>* item)
{
if (empty())
   ErrAbort("LinkedList<T>::extract : empty list");

if (item->prev) 
   item->prev->next = item->next;
else
   first = item->next;

if (item->next)
   item->next->prev = item->prev;
else
   last = item->prev;

delete item;
Len--;
}


template <class T>
ListItem<T>* LinkedList<T>::insert( T& data, ListItem<T>* next)
{
ListItem<T>* item = new ListItem<T>(data);

if (next) {
   if (next->prev)
      next->prev->next = item;
   else
      first = item;
   item->next = next;
   item->prev = next->prev;
   next->prev = item;
   }
else {                  // appending to end of list 
   if (last) {
      last->next = item;
      item->prev = last;
      last = item;
      }
   else
      first = last = item;
   }

Len++;
return item;
}


template <class T>
ListItem<T>* LinkedList<T>::find( T& data)
{
ListItem<T>* curr = first;

while (curr) {
  if (data == curr->data()) break;
  curr = curr->next;
  }

return curr;
}
#endif