#ifndef HEADER_ILLIST
#define HEADER_ILLIST

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

#ifdef DMALLOC
#include <dmalloc.h>
#endif

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

template <class itemtype>
class ilist {

  private:

    ielem<itemtype> *head;
    ielem<itemtype> *curptr;

    void adjust(ielem<itemtype> *item, int value) {
      ielem<itemtype> *temp=item;
      while(temp) {
	temp->item->index+=value;
	temp=temp->next;
      }
    }
 
 public:
 
    ilist() {
      head=NULL;
      curptr=NULL;
    }

    void init_trav() {
      curptr=head;
    }

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

    int insert_start(itemtype &item1) {
      ielem<itemtype> *newitem = new ielem<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;
      /* Set up the new indexes */
      head->item->index=0;
      adjust(newitem->next,1);
      return 0;
    }

    int insert_end(itemtype &item1) {
      ielem<itemtype> *newitem;
      ielem<itemtype> *temp;
      int lastitem;
      newitem = new ielem<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) {
	lastitem=1;
	while(temp->next) {
	  lastitem++;
	  temp=temp->next;
	}
	temp->next=newitem;
	temp->next->item->index=lastitem;
	return lastitem;
      } else {
	head=newitem;
	head->item->index=0;
	return 0;
      }
    }

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

    int insert_ascending(itemtype &item1) {
      ielem<itemtype> *newitem;
      ielem<itemtype> *theelem;
      int lastitem=0;
      newitem = new ielem<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->item->index=0;
	  newitem->next=head;
	  head=newitem;
	  adjust(head->next,1);
	  return 0;
	} else {
	  lastitem=1;
	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;
	      newitem->item->index=lastitem;
	      adjust(newitem->next,1);
	      return lastitem;
	    } else {
	      /* Go to the next item and restart loop */
	      lastitem++;
	      theelem=theelem->next;
	      goto loop;
	    }
	  } else {
	    /* There aren't any other elements.. insert it at the end */
	    newitem->item->index=lastitem;
	    newitem->next=NULL;
	    theelem->next=newitem;
	    return lastitem;
	  }
	}
      } else {
	/* The list is empty, make this element the list */
	newitem->item->index=0;
	newitem->next=NULL;
	head=newitem;
	return 0;
      }
    }

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

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

    int deleteitem(itemtype &theitem) {
      int retval=-1;
      ielem<itemtype> *temp=head;
      ielem<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 */
	  retval=temp->item->index;
	  delete temp->item;
	  head=temp->next;
	  adjust(head,-1);
	  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) {
	      retval=temp->next->item->index;
	      delete temp->next->item;
	      temp2=temp->next;
	      temp->next=temp->next->next;
	      adjust(temp->next,-1);
	      delete temp2;
	      break;
	    } else {
	      temp=temp->next;
	    }
	  }
	}
      }
      return retval;
    }

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

    int lastindex() {
      ielem<itemtype> *temp=head;
      while(temp) {
	if(!temp->next) {
	  return temp->item->index;
	} else {
	  temp=temp->next;
	}
      }
      return -1;
    }

};

#endif