// This is a template for implementing an ordered set (list) 
// with elements being objects of class T and the set (list) 
// is ordered according to the value key() (of type Key) of 
// each element.  
// The class T does not contain a linking pointer for the 
// ordered set (list) structure.
//
// For example, to instantiate an ordered set (list) of items 
// of class PROF with a value of class NAME as the key, you
// can simply declare
//         List<PROF, NANE> prof_list;
// It requires that class PROF must have the following 
// member functions:
//   Name key();       //return the key value of the object
//   int  equal( Name somename);     //key() == somename?
//   int  less_than( Name somename ) //key() < somename?
//   void print()                    //print the object
//
// Then, the following functions are available for use:
//   void prof_list.add( Prof * ); 
//   void prof_list.remove( Name );
//   Prof * search( Name ); 
//   void print_all();
// ---------------------------------------------------------
// Author: S. Yu
// Last modification: Feb. 6, 1997

#define FALSE 0
#define TRUE  1
#define null  0

// List item class
//
template <class T> 
class ListItem
{
public:
    T * object;
    ListItem * next;
    ListItem( T * obj=null, ListItem * p=null ) 
        { object = obj; next = p; }
};

// List class
//
template <class T, class Key>
class List
{
    ListItem<T> * head;
    ListItem<T> * look_for( Key );
public:
    List();
    ~List(); 
    void add( T * );
    void remove( Key );
    T * search( Key );
    void print_all();
};

template<class T, class Key>  //constructor
List<T,Key>::List()
{
    head = new ListItem<T>;
}

template<class T, class Key>  //destructor
List<T,Key>::~List()
{
    ListItem<T> * current; 
    ListItem<T> * next;
    current = head;
    next = head->next;

    while (next != null) {
        delete current;
        current = next;
        next = next->next;
    }
    delete current;
}


// Given an object, find p such that p->next contains an object 
// equal to the given object or greater than the object 
//
template<class T, class Key>
ListItem<T> * List<T,Key>::look_for( Key key)
{
    int  found;
    ListItem<T> * p;
    p = head;
    found = FALSE;
    while ((p->next != null) && (found == FALSE)) {
         if ((p->next)->object->equal( key ))
             found = TRUE;  //found the item
         else if ((p->next)->object->less_than( key ))
             p = p->next;   //not found yet
         else
             found = TRUE; //found the place to add
    }
    return p;
}

//Given a pointer to an object, add the object to the list
//in the order of the key
//class T should have functions: Key key();
//
template<class T, class Key>
void List<T,Key>::add( T* object )
{
    ListItem<T> * p;
    ListItem<T> * new_p;
    p = look_for( object->key() );
    if ((p->next != null) && ((p->next)->object)->equal( object->key() )) 
        cerr << "Object exists. Addition is not done.\n"; 
    else {
        new_p = new ListItem<T>(object, p->next);
        p->next = new_p;
    }
}

// Given a key, delete the item that has the key 
//
template<class T, class Key>
void List<T,Key>::remove( Key key )
{
    ListItem<T> * item;
    ListItem<T> * old_item;
    item = look_for( key );
    if ((item->next != null) && (item->next)->object->equal( key )) {
        old_item = item->next;
        item->next = old_item->next;
        delete old_item;
        }
    else
        cerr << "Object does not exist. Deletion is not done.\n";
}

// Given a key, return the pointer to the object that has the key
//
template<class T, class Key>
T * List<T,Key>::search( Key key )
{
    ListItem<T> * item;
    item = look_for( key );
    if ((item->next != null) && ((item->next)->object)->equal( key ))
        return item->next->object;
    else {
        // cerr << "Object does not exist.\n";
        return null;
    }
}

template<class T, class Key>
void List<T,Key>::print_all()
{
    ListItem<T> * p;
    p = head->next;
    while (p != null) {
        (p->object)->print();
        cout << '\n';
        p = p->next;
    }
}