/* -*- mode: c; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */

/*********************************************************************
 * Clustal Omega - Multiple sequence alignment
 *
 * Copyright (C) 2010 University College Dublin
 *
 * Clustal-Omega is free software; you can redistribute it and/or
 * modify it under the terms of the GNU General Public License as
 * published by the Free Software Foundation; either version 2 of the
 * License, or (at your option) any later version.
 *
 * This file is part of Clustal-Omega.
 *
 ********************************************************************/

/*
 * RCS $Id: list.h 143 2010-10-14 13:11:14Z andreas $
 */

// list.h


//////////////////////////////////////////////////////////////////////////////
// Double-linked list implementation with head and tail dummy elements
// We set head->prev=head and tail->next=tail.
// This makes sure that repeated current=current->next; ends up in tail
// and repeated current=current->prev; ends up in head.
// head and tail optionally contain a NULL element of Typ defined by method Null(Typ)
//////////////////////////////////////////////////////////////////////////////

template<class Typ> 
class List
{
protected:
template<class Typ1> 
class ListEl             //elements of List; essentially a data structure
  {
  public:
    Typ1 data;           //Typ is type of data to be stored in list
    ListEl* prev;        //points to previous list element
    ListEl* next;        //points to next list element
    ListEl() : prev(0), next(0) {}
    ListEl(Typ1 d) : data(d), prev(0), next(0) {}
    ListEl(ListEl* p, ListEl* n) : prev(p), next(n) {}
    ListEl(Typ1 d, ListEl* p, ListEl* n) : data(d), prev(p), next(n) {}
  };
  
  ListEl<Typ>* head;     //points to dummy element at beginning of list
  ListEl<Typ>* tail;     //points to dummy element at end of list    
  ListEl<Typ>* current;  //current element position within list
  int size;              //Number of elements in list

  // Use QUICKSORT to sort list in asscending order between two list elements
  void SortList(ListEl<Typ>*, ListEl<Typ>*, int); 
  // Use QUICKSORT to sort list of pointers by comparing elements they point to
  void SortPointerList(ListEl<Typ>*, ListEl<Typ>*);

  // Swap two list elements by making a flat copy (don't need two copies of data)
  // Warning: Gets slow if Typ is composite type with many variables (>=5)
  void SwapContent(ListEl<Typ>* e1, ListEl<Typ>* e2)
  { Typ d; if (e1!=e2) {d=e1->data; e1->data=e2->data; e2->data=d;} }

public:
//////////////////////////////////////////////////////////////////////////////
// General methods
  List();
  List(Typ d);
  ~List();
  List<Typ>& operator=(List<Typ>&);
    
  // Set Null element that will be returned when trying to read from an empty list
  void Null(Typ null) {head->data = tail->data = null;}


//////////////////////////////////////////////////////////////////////////////
// Methods that act at the end of the list 

  // Insert Element after LAST element of list (and return address of data element)
  Typ* Push(Typ);

  // Remove and return LAST element of list. Returns head->data if list empty
  Typ Pop();

  // return LAST element of list. Returns null element in head->data if list empty
  Typ ReadLast() {return tail->prev->data;}


//////////////////////////////////////////////////////////////////////////////
// Methods that act at the beginning of the list

  // Insert element as FIRST element of list (and return address of data element)
  Typ* Enqueue(Typ);

  // Remove and return element at BEGINNING of list. Returns head->data if list empty
  Typ Dequeue();

  // return FIRST element of list. Returns null element in head->data if list empty
  Typ ReadFirst() {if (size) return head->next->data; else return head->data;}


//////////////////////////////////////////////////////////////////////////////
// Methods that work with 'current' position in the list

  // Advances current position by 1 and reads next element; returns head->data if at end of list.
  Typ ReadNext(); 

  // Reads current element again
  Typ ReadCurrent(); 

  // Moves current position back by 1 and reads previous element; returns head->data if at beginning of list.
  Typ ReadPrevious(); 

  // Advances current position by 1 and reads address of next element; returns NULL if at end of list.
  Typ* ReadNextAddress(); 

  // Reads address of current element again, returns NULL if at end of list
  Typ* ReadCurrentAddress(); 

  // Sets current position to k and reads k'th element (first=1). Returns head->data if current points to no data element
  Typ Read(int);

  // Inserts element AFTER CURRENT element; current element will be set to inserted element
  void Insert(Typ);

  // Removes and returns element at CURRENT position. New position is one BEFORE current position. 
  // Returns head->data if current points to no data element. After Reset() delete first element (not 0'th)
  Typ Delete();

  // Overwrites data at current position with new data 
  void Overwrite(Typ d) {current->data=d;} 

  // Reset current position to 0 (one BEFORE the first)
  int Reset() {current = head; return size;} 

  // Reset current position to End (one AFTER the last)
  int SetToEnd() {current = tail; return size;} 


//////////////////////////////////////////////////////////////////////////////
// Methods that return information about the list

  // Return number of list elements (size>=0)
  int Size()  {return size;}  

  // return true if end of list, i.e. ReadNext would give tail->data (i.e. current position >= Size)
  char End()  {return (current==tail || current==tail->prev);}
  char End(void* curr)  {return ( curr == tail || curr == tail->prev);}

  // return true if start of list, i.e. ReadPrevious would give head->data (i.e. current position <=1)
  char Start()  {return (current==head || current==head->next);}

  // Get current position within list (0 <= pos <= Size+1) 
  int GetPos();

  //print out list (elements assumed int)
  void PrintList();

  // Get largest data element (Null element for empty list)
  Typ Largest();

  // Get smallest data element (Null element for empty list)
  Typ Smallest();

//////////////////////////////////////////////////////////////////////////////
// Methods that manipulate the list as a whole

  // Reverse list 
  void Reverse();

  // Copies list into list object
  void Copy(List<Typ>* list);

  // Appends a copy of list to class object
  void AppendCopy(List<Typ>* list);

  // Appends list to class object list
  void Append(List<Typ>* list); 

  // Use QUICKSORT to sort list in ascending order. Use only for UNSORTED lists, otherwise time O(N^2) instead of O(N*log(N))
/*   void SortList() {if (size>1) SortList(head->next, tail->prev);}  */
  void SortList() {if (size>1) SortList(head->next, tail->prev, size);} 
  void QuickSort() {if (size>1) SortList(head->next, tail->prev, size);} 

  // Use QUICKSORT to sort list of pointers in ascending order. Use only for UNSORTED lists, otherwwise time O(N^2)!
  void SortPointerList() {if (size>1) SortPointerList(head->next, tail->prev);} 
  void QuickSortPointer() {if (size>1) SortPointerList(head->next, tail->prev);} 

  // Use INSERTSORT to sort list in asscending order. Use only for PRESORTED lists, otherwise time O(N^2)!
  void ResortList(); 
};