//LISTA.CPP

#include <stddef.h>			//för NULL
#include <assert.h>			//för assert()
#include <iostream.h>		//för in-ut matning
#include <conio.h>			//för getch();
#include <string.h>        //för säker inmatning
#include <stdlib.h>			//för atoi()

const int MAXLISTA = 20;
const int BUFFERSIZE = 100;
const int FALSE=0;
const int TRUE=!FALSE;

template <class T>
class listClass
{
public:
  listClass();
  ~listClass();
  int listIsEmpty();
  int listLength();
  int posIsOk(int position);
  int newDuplicate(T newItem);
  void listInsert(T newItem);
  void listDel(int position);
  void listSort();
  void listDisplay();
  int listSeek(T soktVarde);
  void listAntal();
private:
  struct listNode {
    T listContent;
    listNode* next;
  };
  typedef struct listNode listNode;
  typedef struct listNode* ptrType;
  ptrType head;
  int size;
};

/***************************************************/
/*CONSTRUCTOR                                      */
/*SÄTTER LISTSTORLEKEN TILL NOLL                   */
/*		precondition: TRUE                           */
/*		postcondition: TRUE                          */
/***************************************************/
template <class T>
listClass<T>::listClass():size(0), head(NULL){}

/***************************************************/
/*DESTRUCTOR                                       */
/*GÖR INGET, MEN MEN ANROPAS NÄR LISTAN DÖR        */
/*		precondition: TRUE                           */
/*		postcondition: TRUE                          */
/***************************************************/
template <class T>
listClass<T>::~listClass(){}

/***************************************************/
/*KOLLAR OM LISTAN ÄR TOM                          */
/*		precondition: TRUE                           */
/*		postcondition: TRUE                          */
/***************************************************/
template <class T>
int listClass<T>::listIsEmpty(){ return int (size == 0); }

/***************************************************/
/*RETURNERAR ANTALET ELEMENT I LISTAN              */
/*		precondition: TRUE                           */
/*		postcondition: TRUE                          */
/***************************************************/
template <class T>
int listClass<T>::listLength() { return size;}

/***************************************************/
/*LÄGGER TILL ETT NYTT ELEMENT I LISTAN            */
/*		precondition: minne fanns för att skapa fönst*/
/*    precondition: att listelementet inte finns   */
/*    postcondition: listan har ett nytt element   */
/***************************************************/
template <class T>
void listClass<T>::listInsert(T newItem)
{
  int newPosition=1;
  int newLength = listLength() + 1;
  size = newLength;
  ptrType newPtr = new listNode;
  if (newPtr != NULL) {
    newPtr -> listContent = newItem;
    newPtr ->next = head;
    head = newPtr;
  }
}

/***************************************************/
/*TAR BORT ELEMENT I LISTAN                        */
/*    precondition: att det finns en lista         */
/*		precondition: att positionen är OK           */
/*		postcondition: elementet har tagits bort     */
/***************************************************/
template <class T>
void listClass<T>::listDel(int position)
{
  ptrType trav=head, cur;
  size--;
  if (position == 1) {
    cur = head;
    head = head -> next;
    
  }
  else {
    for (int skip = 1 ; skip < position -1; skip++)
      trav = trav -> next;
    cur = trav -> next;
    trav -> next = cur ->next;
  }
  cur -> next = NULL;
  delete cur;
  cur = NULL;
}

/***************************************************/
/*SORTERAR LISTAN                                  */
/*		precondition: att det finns en lista         */
/*		postcondition: elementen ligger i ordning    */
/***************************************************/
template <class T>
void listClass<T>::listSort()
{
  T temp;
  int bytt;
  
  do {
    bytt=FALSE;
    for(ptrType cur=head ; cur->next != NULL ; cur = cur->next)
      if(cur->listContent > cur->next->listContent) {
	temp = cur->listContent;
	cur->listContent = cur->next->listContent;
	cur->next->listContent = temp;
	bytt=TRUE;
      }
  }while(bytt);
}
/***************************************************/
/*SKRIVER UT LISTAN PÅ SKÄRMEN                     */
/*		precondition: att det finns en lista         */
/*		postcondition: listan har skrivits ut        */
/***************************************************/
template <class T>
void listClass<T>::listDisplay()
{
  TWindow ruta;
  for(ptrType cur = head ; cur != NULL ; cur = cur->next) {
    ruta=cur->listContent;
    cout << ruta;
    ruta.move(11,0);
  }
}

/***************************************************/
/*SÖKER EFTER ETT ELEMENT I LISTAN                 */
/* 	precondition: att det finns en lista         */
/*		postcondition: TRUE                          */
/***************************************************/
template <class T>
int listClass<T>::listSeek(T soktVarde)
{
  ptrType cur;
  for(cur=head ; cur != NULL ; cur = cur->next)
    if(cur->listContent == soktVarde)
      return TRUE;
  return FALSE;
}

/***************************************************/
/*KOLLAR OM ETT ELEMENT FINNS                      */
/*		precondition: TRUE                           */
/*		postcondition: TRUE/FALSE                    */
/***************************************************/
template <class T>
int listClass<T>::newDuplicate(T newItem)
{
  ptrType cur;
  
  for(cur=head ; cur != NULL ; cur = cur->next)
    if(cur->listContent == newItem)
      return TRUE;
  return FALSE;
}

/***************************************************/
/*KONTROLLERAR OM EN POSITION FINNS                */
/*		precondition: att positionen är tillåten     */
/*		postcondition: TRUE/FALSE                    */
/***************************************************/
template <class T>
int listClass<T>::posIsOk(int position)
{
  if((position <= size) && (position > 0))
    return TRUE;
  else
    return FALSE;
}