OrderedList.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.
 *  _________________________________________________________________________
 */

//
// OrderedList.h
//
#ifndef __OrderedList_h
#define __OrderedList_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"
#include "errmsg.h"


template <class T,class V>
class UTILIB_API OrderedList;


template <class T, class V>
class UTILIB_API OrderedListItem {

  friend class OrderedList<T,V>;

public:

  OrderedListItem( T Data_, V Key_) 
        : Data(Data_), Key(Key_) {next = prev = 0;}

  T& data()  {return Data;}
  V key() {return Key;}
  int operator==(const OrderedListItem<T,V>& item) 
        {return (Key == item.Key);}

protected:

  T Data;
  V Key;

  OrderedListItem *next;
  OrderedListItem *prev;

  static OrderedListItem* unused;
  static void delete_unused();

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



template <class T,class V>
class UTILIB_API OrderedList
{
public:

  OrderedList() 
                { counter++; first = last = 0; Len=0; }
  OrderedList(const OrderedList<T,V>& list)
                { counter++; first = last = 0; Len=0; *this = list;}
  virtual ~OrderedList();

  OrderedList<T,V>& operator=(const OrderedList<T,V>& list);

  OrderedListItem<T,V>* find( V& key);
  OrderedListItem<T,V>* head() const
                {return first;}
  OrderedListItem<T,V>* tail() const
                {return last;}
  OrderedListItem<T,V>* next(OrderedListItem<T,V>* item) const
                {return item->next;}         

  T& top()
                {
                if (Len == 0) {
                   ErrAbort("OrderedList::top -- Empty list");
                   exit(0);
                   }
                return first->data();
                }
  void add( T& data, V& key)
                {insert(data,key);}
  void add( T& data, V& key, OrderedListItem<T,V>*& item ) 
                {item = insert(data,key);}
  void remove( T& data, V& key)
                {extract(first,data,key);}
  void remove(OrderedListItem<T,V>*& item)
                {extract(item);}
  void remove(OrderedListItem<T,V>*& item, T& data, V& key)
                {extract(item,data,key);}

  void update(OrderedListItem<T,V>* item, V& key);

  int empty() const;
  operator int() const 
                {return (first == 0 ? FALSE : TRUE);}
  int len() const 
                {return Len;}

protected:

  void extract(OrderedListItem<T,V>* item, T& data, V& key)
                { data = item->Data; key = item->Key; extract(item); }
  void extract(OrderedListItem<T,V>* item);

  OrderedListItem<T,V>* insert( T& data, V& key);
  void extract_all();

  OrderedListItem<T,V> *first;
  OrderedListItem<T,V> *last;

  int Len;

  static int counter;

};




//
// OrderedListItem methods
//

template <class T,class V>
OrderedListItem<T,V> *OrderedListItem<T,V>::unused = NULL;


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

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

unused = NULL;
}


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


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



//
// OrderedList methods
//

template <class T,class V>
int OrderedList<T,V>::counter=0;


template <class T,class V>
OrderedList<T,V>::~OrderedList()
{
extract_all();
counter--;

if (!counter)
   OrderedListItem<T,V>::delete_unused();
}


template <class T,class V>
void OrderedList<T,V>::extract_all()
{
while (!empty())
  extract(first);
}


template <class T, class V>
OrderedList<T,V>& OrderedList<T,V>::operator=(const OrderedList<T,V>& list)
{
extract_all();
OrderedListItem<T,V>* curr = list.head();

while (curr) {
  T tdata = curr->data();
  V tkey  = curr->key();
  add(tdata,tkey);
  curr = list.next(curr);
  }
return *this;
}



//
// This is a stupid way of doing this.  I should simply update the key
// value and move the 'item'.
//
template <class T,class V>
void OrderedList<T,V>::update(OrderedListItem<T,V>* item, V& key)
{
insert(item->Data,key);
extract(item);
}


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


template <class T,class V>
void OrderedList<T,V>::extract(OrderedListItem<T,V>* item)
{
if (empty()) {
   cerr << "extract() on empty list" << endl;
   exit(-1);
   }

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,class V>
OrderedListItem<T,V>* OrderedList<T,V>::insert( T& data, V& key)
{
OrderedListItem<T,V>* item = new OrderedListItem<T,V>(data,key);

OrderedListItem<T,V>* curr = last;

while (curr && (item->Key < curr->Key))
  curr = curr->prev;

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

else {                  // insert at beginning of list
   item->prev = NULL;
   item->next = first;
   if (first)
      first->prev = item;
   first = item;
   if (!last) 
      last = item;
   }

Len++;
return item;
}


template <class T,class V>
OrderedListItem<T,V>* OrderedList<T,V>::find( V& key)
{
OrderedListItem<T,V>* curr = first;

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

return curr;
}          
#endif