// Template for a linked list class


#ifndef LIST_DECL


#define LIST_DECL true


#define MAX_CAT_LEVELS 10       // Number of levels in the category hierarchy


template <class T> class tlist
{
private:

    struct list_item
    {
        T* data;
        list_item* next;
        list_item* prev;
    };

    list_item* head;            // Ptr to head of list

    list_item* tail;            // Ptr to tail of list

    list_item* current;         // Ptr to currently selected item


    list_item* compare1;        // Ptr to item to use for sorting

    list_item* compare2;        // Ptr to item to use for sorting


    void swap( void );          // Swaps the two items at compare1 and compare2


public:

    int  items;                 // No. of items in list


    tlist();                        // Constructor - initialise empty list

    ~tlist();                   // Destructor - removes list and frees up memory

  
    bool insert( T* );          // Calls traverse function

    void move_first( void );    // Moves "current" pointer to head of list

    T* get_item();              // Returns "current" item, and move "current" on one place

    void sort( void );          // Sorts the list into alpha order according to categories

};

template <class T> tlist<T>::tlist()             // list constructor

{
    head = NULL;
    tail = NULL;
    current = NULL;
    items = 0;
}

template <class T> tlist<T>::~tlist()            // list destructor

{
    list_item* current_item;
    list_item* next_item;
  
    current_item = head;

    while ( current_item != NULL )
    {
        next_item = current_item -> next;
        delete current_item -> data;
        delete current_item;
        current_item = next_item;
    }
}

template <class T> bool tlist<T>::insert( T* data )
{
    list_item* new_item;

    new_item = new list_item;           // allocate memory

    if ( new_item == NULL )
        return false;                   // unable to allocate memory

    
    new_item -> data = data;
    new_item -> prev = tail;            // link element into the list

    new_item -> next = NULL;
    
    if (head == NULL)
        head = new_item;
    
    if (tail != NULL)
        tail -> next = new_item;
    
    tail = new_item;                    // make new item the head


    items++;                            // increment item count

    return true;
}

template <class T> void tlist<T>::move_first( void )
{
    current = head;
}

template <class T> T* tlist<T>::get_item( void )
{
    T* value;
    if ( current == NULL )              // At end of list

        return NULL;
    else
    {
        value = current -> data;        // Store data to return

        current = current -> next;      // Move current element on one place

        return value;                   // Return pointer to stored element's data

    }
}

template <class T> void tlist<T>::swap()
{
    T *temp;

    temp = compare2 -> data;
    compare2 -> data = compare1 -> data;
    compare1 -> data = temp;
}

template <class T> void tlist<T>::sort()
{
    // Perform sort using bubble sort - slow but simple


    char value1[MAX_CAT_LEVELS * 52], value2[MAX_CAT_LEVELS * 52];

    for (compare1 = head; compare1 != NULL; compare1 = compare1 -> next)
        for (compare2 = compare1 -> next; compare2 != NULL; compare2 = compare2 -> next)
            {
            compare1 -> data -> cat_string(value1);
            compare2 -> data -> cat_string(value2);

            if (stricmp(value2, value1) < 0)
                swap();
            }
}

#endif