/************************************************
*	 Laboration 4 i
*	 Datastrukturer och Algoritmer
*	 Dijkstras Shortest Path
*************************************************
*	 Christian Ohlsson
*	 Karlstads universitet, 1999
*
*   list.h
*   Innehåller definitioner och funktioner
*   för en templatelista.
*************************************************/

#ifndef _LISTA_H_
#define _LISTA_H_

#include "header.h"

/*===============================================
* list
*  Denna klass skapar en templatelista.
*  Varje nod innehåller ett godtyckligt data-
*  fält och en pekare till nästa nod.
-------------------------------------------------*/
template <class T>
class list {
  private:
	 struct nod {          // En template nod
		T data;
		nod *next;
	 };
	 int size;             // Storleken på listan.
	 nod *head;            // Pekar på första elementet i listan.
  public:
	 list();
	 ~list();
	 int listLength();                //Storleken på listan
	 void insert(T data);             //Sätter in en nod
	 void del(int place);             //Tar bort en nod
	 void sort(void);                 //Sorterar listan
	 int seek(T data);                //Söker i listan
	 int isFree(void);                //Kollar om det finns element i listan
	 void delAll(void);               //Tar bort allt i listan
	 int occupiedExist(T data);       //Kollar om inmatat värde existerar
	 int occupied(int place);         //Testar om det finns plats
	 void setNode(nod *dat, T data);  //Mata in data i den nya noden
	T printElement(int place);        //Visar Innehållet på bestämd plats.
	T *getPtr(int place);             //Returnera platsen på place position
};


/*===============================================
*  list
*   Construktor, skapar en lista
-------------------------------------------------*/
template <class T>
list<T>::list() {
  head = NULL;
  size = 0;
}

/*===============================================
* ~list
*  Destruktor. Anropar delAll
-------------------------------------------------*/
template <class T>
list<T>::~list() { delAll(); }

/*===============================================
* insert
*  Sätter in en ny nod i listan
-------------------------------------------------*/
template <class T>
void list<T>::insert(T data) {
	nod *newNode = new nod;
	newNode->next = head;
	head = newNode;
	size++;
	newNode->data = data;
}

/*===============================================
* del
*  Tar bort ett element på en viss
*  position i listan
-------------------------------------------------*/
template <class T>
void list<T>::del(int place) {
	int i = 1;
	nod *temp1;
	temp1 = head;
	nod *temp2;
	temp2 = head->next;
	if(temp2 == NULL || place == 1) {       //Bara ett element i listan
		head = temp1->next;
		delete temp1;
		size--;
	}
	else {                                  //Flera element i listan
		temp2 = head;
		while(i < place) {
			temp1 = temp2;
			temp2 = temp1->next;
			i++;
		}
		temp1->next = temp2->next;
		delete temp2;
		size--;
	}
}

/*===============================================
*  isFree
*   Kollar om listan är tom. Returnerar
*   true om listan är tom
-------------------------------------------------*/
template <class T>
int list<T>::isFree() {
	if(size == 0) return true;
	else return false;
}

/*===============================================
* occupied
*  Kollar om plats finns på en angiven
*  position.
-------------------------------------------------*/
template <class T>
int list<T>::occupied(int place) {
	if( (place < 1) || (place > size) ) return false;
	else return true;
}

/*===============================================
* listLength
*  Returnerar antalet element i listan
-------------------------------------------------*/
template <class T>
int list<T>::listLength() { return size; }

/*===============================================
*  sort
*   Sorterar elementen i listan
-------------------------------------------------*/
template <class T>
void list<T>::sort() {
	nod *temp;
	T sop;
	int changed;
	do {
		changed = 0;
		for(temp = head; temp != NULL; temp = temp->next)
			if(temp->data > temp->next->data) {
				sop = temp->data;
				temp->data = temp->next->data;
				temp->next->data = sop;
				changed = 1;
			}
	}while(changed);
}

/*===============================================
* delAll
*  Tar bort alla element i listan.
*  Sätter sedan storleken till 0
-------------------------------------------------*/
template <class T>
void list<T>::delAll() {
	nod *temp1 = head;
	nod *temp2;
	head = NULL;
	while(temp1 != NULL) {
		temp2 = temp1;
		temp1 = temp1->next;
		delete temp2;
	}
	size = 0;
}

/*===============================================
*
*
-------------------------------------------------*/
template <class T>
int list<T>::occupiedExist(T data) {      //Kollar om inmatat värde existerar
	nod *temp;
	for(temp = head; temp != NULL; temp = temp->next)
		if(temp->data == data)
			return true;
	return false;
}

/*===============================================
*
*
-------------------------------------------------*/
template <class T>
int list<T>::seek(T data) {              //Söker efter ett element i listan
	nod *temp;
	int position = 0;
	for(temp = head; temp != NULL; temp = temp->next) {
		position++;
		if(temp->data == data)
			return position;                //Funnet! Returnera positionen
	}
	position = 0;
	return position;                      //Inget hittades, returnera 0
}

/*===============================================
* printElement
*  Hämtar element på en angiven plats
-------------------------------------------------*/
template <class T>
T list<T>::printElement(int place) {
	nod *temp1 = head;
	int i = 1;
	while(i < place && i < size) {
		temp1 = temp1->next;
		i++;
	}
	return temp1->data;
}

/*===============================================
* getPtr
*  Returnera adressen till ett element
*  på en angiven plats
-------------------------------------------------*/
template <class T>
T *list<T>::getPtr(int place) {
	nod *temp1 = head;
	int i = 1;
	while(i < place && i < size) {
		temp1 = temp1->next;
		i++;
	}
	return &(temp1->data);
}
#endif