#ifndef HEADER_LLIST
#define HEADER_LLIST

#include <stdio.h>
#include <stdlib.h>

template <class itemtype>
class elem {
  public:
    itemtype *item;
    elem *next;
    elem() {
      item=0;
      next=0;
    }
};

template <class itemtype>
class list {

  private:

    elem<itemtype> *head;
    elem<itemtype> *curptr;
    unsigned long size;

 public:
 
    list() {
      head=NULL;
      curptr=NULL;
      size=0;
    }

    list(list<itemtype>& thelist) {
      itemtype *temp;
      head=NULL;
      curptr=NULL;
      thelist.init_trav();
      while((temp=thelist.trav())) {
	insert_end(*temp);
      }
    }

    list<itemtype>& operator=(list<itemtype>& thelist) {
      itemtype *temp;
      clear();
      thelist.init_trav();
      while((temp=thelist.trav())) {
	insert_end(*temp);
      }
      return *this;
    }

    void init_trav() {
      curptr=head;
    }

    itemtype *trav() {
      itemtype *temp;
      if(curptr) {
	temp=curptr->item;
	curptr=curptr->next;
	return temp;
      } else {
	return NULL;
      }
    }

    int getsize() {
      return size;
    }

    void insert_start(itemtype &item1) {
      elem<itemtype> *newitem = new elem<itemtype>;
      if(!newitem) {
	fprintf(stderr,"Out of memory! Halp! Dunno what to do!\n");
	exit(1);
      }
      newitem->item = new itemtype(item1);
      if(!newitem->item) {
	fprintf(stderr,"Out of memory! Halp! Dunno what to do!\n");
	exit(1);
      }
      newitem->next = head;
      head = newitem;
      size++;
    }

    void insert_end(itemtype &item1) {
      elem<itemtype> *newitem;
      elem<itemtype> *temp;
      newitem = new elem<itemtype>;
      if(!newitem) {
	fprintf(stderr,"Out of memory! Halp! Dunno what to do!\n");
	exit(1);
      }
      newitem->item = new itemtype(item1);  
      if(!newitem->item) {
	fprintf(stderr,"Out of memory! Halp! Dunno what to do!\n");
	exit(1);
      }
      newitem->next = NULL;
      temp=head;
      if(temp) {
	while(temp->next) {
	  temp=temp->next;
	}
	temp->next=newitem;
      } else {
	head=newitem;
	size++;
      }
    }

    void clear() {
      elem<itemtype> *temp;
      temp=head;
      while(temp) {
	delete temp->item;
	temp=temp->next;
      }
      head=NULL;
      curptr=NULL;
      size=0;
    }

    void insert_ascending(itemtype &item1) {
      elem<itemtype> *newitem;
      elem<itemtype> *theelem;
      newitem = new elem<itemtype>;
      if(!newitem) {
	fprintf(stderr,"Out of memory! Halp! Dunno what to do!\n");
	exit(1);
      }
      newitem->item = new itemtype(item1);  
      if(!newitem->item) {
	fprintf(stderr,"Out of memory! Halp! Dunno what to do!\n");
	exit(1);
      }
      theelem=head;
      if(theelem) {
	/* There is a first element */
	/* Let's compare with the first element and see if we want to insert
       it right here */
	if(*(theelem->item)>=item1) {
	  /* The first element in the list is bigger, let's insert here */
	  newitem->next=head;
	  head=newitem;
	} else {
	loop:
	  if(theelem->next) {
	    /* There is a second element as well */
	    if(*(theelem->next->item)>=item1) {
	      /* Second is greater, insert before second, after first */
	      newitem->next=theelem->next;
	      theelem->next=newitem;
	    } else {
	      /* Go to the next item and restart loop */
	      theelem=theelem->next;
	      goto loop;
	    }
	  } else {
	    /* There aren't any other elements.. insert it at the end */
	    newitem->next=NULL;
	    theelem->next=newitem;
	  }
	}
      } else {
	/* The list is empty, make this element the list */
	newitem->next=NULL;
	head=newitem;
      }
      size++;
    }

    ~list() {
      elem<itemtype> *temp=head;
      elem<itemtype> *temp2;
      while(temp) {
	if(temp->item) delete temp->item;
	temp2=temp->next;
	delete temp;
	temp=temp2;
      }
    }

    itemtype *find(itemtype &theitem) {
      elem<itemtype> *temp=head;
      while(temp) {
	if(*(temp->item)==theitem) {
	  return temp->item;
	} else {
	  temp=temp->next;
	}
      }
      return NULL;
    }

    void deleteitem(itemtype &theitem) {
      elem<itemtype> *temp=head;
      elem<itemtype> *temp2;
      if(temp) {
	/* There's at least one item in the list */
	if(*(temp->item)==theitem) {
	  /* The first item in the list needs removed */
	  delete temp->item;
	  head=temp->next;
	  delete temp;
	} else {
	  while(temp->next) {
	    /* The first element didn't need deleting, so lets check all of the
	       "next" elements */
	    if(*(temp->next->item)==theitem) {
	      delete temp->next->item;
	      temp2=temp->next;
	      temp->next=temp->next->next;
	      delete temp2;
	      break;
	    } else {
	      temp=temp->next;
	    }
	  }
	}
      }
      size--;
    }

    int exists(itemtype &theitem) {
      elem<itemtype> *temp=head;
      while(temp) {
	if(*(temp->item)==theitem) return 1;
	temp=temp->next;
      }
      return 0;
    }

};

#endif