/* -*- 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-C.h 143 2010-10-14 13:11:14Z andreas $
 */

// list.C
// Class for double-linked list 



#ifndef JLIST
#define JLIST

#ifndef MAIN
#include <iostream>   // cin, cout
#include <stdlib.h>   // 
#include <stdio.h>    // 
using std::cout;
using std::cerr;
#endif

#include "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)
////////////////////////////////////////////////////////////////////////////



////////////////////////////////////////////////////////////////////////////
// Constructors and destructor

////////////////////////////////////////////////////////////////////////////
// Creates empty List with two dummy elements
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
List<Typ>::List()
{
  head=new ListEl<Typ>();
  if (!head) { cerr<<"Could not create new element\n"; return; }
  tail=new ListEl<Typ>(head,NULL);
  if (!tail) { cerr<<"Could not create new element\n"; return; }
  tail->next = tail;
  head->prev = head;
  head->next = tail;
  current = head;
  size=0;
}

////////////////////////////////////////////////////////////////////////////
// Creates List with one element 
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
List<Typ>::List(Typ d)
{
  head=new ListEl<Typ>();
  if (!head) { cerr<<"Could not create new element\n"; return; }
  tail=new ListEl<Typ>();
  if (!tail) { cerr<<"Could not create new element\n"; return; }
  ListEl<Typ>* el = new ListEl<Typ>(d,head,tail);
  if (!el)   { cerr<<"Could not create new element\n"; return; }
  head->prev = head;
  head->next = el;
  tail->prev = el;
  tail->next = tail;
  current = head;
  size=1;
}

////////////////////////////////////////////////////////////////////////////
// Destructor deletes List object
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
List<Typ>::~List()
{
  ListEl<Typ>* n=head->next;
  while(head!=n)
    {
      delete(head); head = NULL;
      head=n;
      n=head->next;
  }
  delete(head); head = NULL;
}

////////////////////////////////////////////////////////////////////////////
// Flat copy
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
List<Typ>& List<Typ>::operator=(List<Typ>& l)
{
  head = l.head;
  tail = l.tail;
  current = l.current;
  size = l.size;
}


////////////////////////////////////////////////////////////////////////////
// Reverse order of list
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
void List<Typ>::Reverse()
{
  ListEl<Typ> *n; // next list element; also for swapping
  ListEl<Typ> *c; // current element to be sorted in. Everything to the left is already sorted
  if (Size()<=1) return;
  for (c=head; c!=tail; c=n)
    {
      // Swap prev and next pointers of all list elements
      n = c->next;
      c->next = c->prev;
      c->prev = n;
    }
  
  // Swap prev and next pointers of tail
  tail->next = tail->prev;
  tail->prev = tail;

  // Swap head an tail
  n = head;
  head = tail;
  tail = n;
}




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

////////////////////////////////////////////////////////////////////////////
// Insert Element after LAST of list  (and return address of data element)
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
Typ* List<Typ>::Push(Typ d)
{ 
  ListEl<Typ>* t=new ListEl<Typ>(d,tail->prev,tail); 
  if (!t) { cerr<<"Could not create new element\n"; return 0; }
  tail->prev->next=t;
  tail->prev = t;
  size++;
  return &(t->data);
} 

////////////////////////////////////////////////////////////////////////////
// Remove and return LAST element of list. Returns head->data if empty
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
Typ List<Typ>::Pop()
{
  if (!size) return head->data;
  ListEl<Typ>* t=tail->prev;
  if (current==t) current=tail;
  Typ d=t->data;
  t->prev->next=tail;
  tail->prev=t->prev;
  delete t; t = NULL;
  size--;
  return d;
}



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

////////////////////////////////////////////////////////////////////////////
// Insert element as FIRST element of list (and return address of data element)
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
Typ* List<Typ>::Enqueue(Typ d)
{
  ListEl<Typ>* h = new ListEl<Typ>(d,head,head->next); 
  if (!h) { cerr<<"Could not create new element\n"; return 0; }
  h->next->prev = h;
  head->next=h;
  size++;
  return &(h->data);
} 

////////////////////////////////////////////////////////////////////////////
// Remove element at BEGINNING of list
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
Typ List<Typ>::Dequeue()
{
  if (!size) return head->data;
  ListEl<Typ>* h=head->next;
  if (current==h) current=head;
  Typ d=h->data;
  h->next->prev=head;
  head->next=h->next;
  delete h; h = NULL;
  size--;
  return d;
} 

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

////////////////////////////////////////////////////////////////////////////
// Reads next element; advances current position by 1
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
inline Typ List<Typ>::ReadNext()
{
  current = current->next;
  return current->data;
}

////////////////////////////////////////////////////////////////////////////
// Reads current element again (NULL if nothing read yet)
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
inline Typ List<Typ>::ReadCurrent()
{
  return current->data;
}

////////////////////////////////////////////////////////////////////////////
// Reads previous element; moves current position back by 1
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
inline Typ List<Typ>::ReadPrevious()
{
  current = current->prev;
  return current->data;
}

////////////////////////////////////////////////////////////////////////////
// Reads next element; advances current position by 1
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
inline Typ* List<Typ>::ReadNextAddress()
{
  current = current->next;
  if (current==tail) return NULL;
  return &(current->data);
}

////////////////////////////////////////////////////////////////////////////
// Reads address of current element again, returns NULL if at end of list
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
inline Typ* List<Typ>::ReadCurrentAddress()
{
  if (current==tail) return NULL;
  return &(current->data);
}

////////////////////////////////////////////////////////////////////////////
// Sets current position to k and reads k'th element (first=1)
////////////////////////////////////////////////////////////////////////////
template <class Typ>
Typ List<Typ>::Read(int pos)
{
  if (pos>size) {current = tail; return tail->data;}
  if (pos<=0)   {current = head; return head->data;}
  current = head->next;
  for (; pos>1; pos--) current = current->next; //If pos==2 do 1 iteration
  return current->data;
}

////////////////////////////////////////////////////////////////////////////
// Inserts element d AFTER current element and sets current element to inserted
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
void List<Typ>::Insert(Typ d)
{
  ListEl<Typ>* el = new ListEl<Typ>(d,current,current->next); 
  if (!el) { cerr<<"Could not create new element\n"; return; }
  (current->next)->prev = el;
  current->next = el;
  current=el;
  size++;
}

////////////////////////////////////////////////////////////////////////////
// Deletes current element and returns content of deleted element. Current element 
// will be previous one after Delete(). After Reset() delete first element (not 0'th)
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
Typ List<Typ>::Delete()
{
  Typ d;
  ListEl<Typ>* p;
  if (!size || current==tail) return tail->data;
  if (current==head) current = head->next; // After Reset() delete first element (not 0'th)     
  (current->prev)->next = current->next;
  (current->next)->prev = current->prev;
  d = current->data;
  p = current->prev;
  delete current; current = NULL;
  current = p;
  size--;
  return d;
}

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

////////////////////////////////////////////////////////////////////////////
// Get current position within list (0 <= pos <= Size+1) 
////////////////////////////////////////////////////////////////////////////
template <class Typ>
int List<Typ>::GetPos()
{
  int pos=0;
  ListEl<Typ>* el;
  for (el = head; el!=current; el=el->next) pos++; 
  return pos;
}

////////////////////////////////////////////////////////////////////////////
//print out list
////////////////////////////////////////////////////////////////////////////
template <class Typ>
void List<Typ>::PrintList()
{
  int j=0;
  ListEl<Typ>* c=current;
  Reset();
  printf("List: ");
  while (!End()) 
    {
      j++;
      cout<<j<<" "<<ReadNext()<<"  ";
      if (!(j%10)) cout<<"\n      ";
    }
  cout<<"\n";
  current=c;
}

////////////////////////////////////////////////////////////////////////////
// Get largest data element
////////////////////////////////////////////////////////////////////////////
template <class Typ>
Typ List<Typ>::Largest()
{
  Typ* result= &((tail->prev)->data);
  Reset();
  while (!End()) 
    {
      if (*result<ReadNext()) result=ReadCurrentAddress();
    }
  return *result;
}

////////////////////////////////////////////////////////////////////////////
// Get smallest data element
////////////////////////////////////////////////////////////////////////////
template <class Typ>
Typ List<Typ>::Smallest()
{
  Typ* result= &((tail->prev)->data);
  Reset();
  while (!End()) 
    {
      if (ReadNext()<*result) result=ReadCurrentAddress();
    }
  return *result;
}

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

////////////////////////////////////////////////////////////////////////////
// Copies list 0 into list object
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
void List<Typ>::Copy(List<Typ>* list)
{
  if (list==this) return;
  while (!End()) Pop(); //empty list
  list->Reset();
  while (!list->End()) Push(list->ReadNext());
}

////////////////////////////////////////////////////////////////////////////
// Appends a copy of list2 to class object
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
void List<Typ>::AppendCopy(List<Typ>* list2)
{
  List<Typ>* cpy=new List<Typ>;
  cpy->Copy(list2);
  Append(cpy);
  delete cpy; cpy = NULL;
}

////////////////////////////////////////////////////////////////////////////
// Appends list2 to class object
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
void List<Typ>::Append(List<Typ>* list)
{
  if (this==list) { AppendCopy(list); return;}
  (tail->prev)->next = list->head->next;
  (list->head->next)->prev = tail->prev;
  if (current==tail) current=tail->prev; 
  ListEl<Typ>* t=tail;
  tail = list->tail;
  size += list->size;

// Reuse old tail as new tail t for list2 and initialize pointers for empty list 
  list->tail=t;
  list->head->next=t;
  t->prev=list->head;
  t->next=t;
  list->head->prev=list->head;
  t->data=list->head->data;
  list->current=list->head;
  list->size = 0;
}

////////////////////////////////////////////////////////////////////////////
// Use QUICKSORT to sort list in ascending order between two list elements
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
void List<Typ>::SortList(ListEl<Typ>* left, ListEl<Typ>* right, int sz) 
{
  if (sz<=1) return; // when SortList() is called, left=head->next, right=tail->prev
  ListEl<Typ> *l=left->prev, *r=right->next;

  // Choose *random* pivot element!! 
  // (Otherwise, complexity for an already sorted list is N^2 => recursive calls may lead to stack overflow)
  ListEl<Typ> *c=left;
  for (int i=1; i<(int)(float(rand())*sz/(RAND_MAX+0.999)); i++) c = c->next; 
  SwapContent(left,c);

  Typ pivot = left->data;
//   Typ* pivot= &(left->data);
  int sz0=sz+1;
  //  cout<<"Sorting between "<<left->data<<" and "<<right->data<<". Pivot="<<pivot<<endl;
  while(1)
    {
//        PrintList();
      do {r=r->prev; sz0--;} while (pivot < r->data); 
      do l=l->next; while (l->data < pivot);
      if (l==r || l->prev==r) break;
      SwapContent(l,r);
    }
  SortList(left,r,sz0);
  SortList(r->next,right,sz-sz0);
  pivot = tail->data; // to avoid calling the destructor of Typ on some real data element
 }

////////////////////////////////////////////////////////////////////////////
// Use QUICKSORT to sort list of POINTERS by comparing the objects the pointers point to
////////////////////////////////////////////////////////////////////////////
template <class Typ> 
void List<Typ>::SortPointerList(ListEl<Typ>* left, ListEl<Typ>* right) 
{
  if (right==left || right->next==left) return;
  ListEl<Typ> *l=left->prev, *r=right->next;
  Typ pivot=left->data;
//    cout<<"Sorting between "<<left->data<<" and "<<right->data<<". Pivot="<<pivot<<endl;
  while(1)
    {
//        PrintList();
      do
	{
	  r=r->prev;
//  	  cout<<"r=r->prev. r->data="<<r->data<<endl;
	} while(*pivot < *(r->data)); 
      do
	{
	  l=l->next;
//  	  cout<<"l=l->next l->data="<<l->data<<endl;
	} while (*(l->data) < *pivot);
      if (l==r || l->prev==r) break;
      SwapContent(l,r);
    }
  SortPointerList(left,r);
  SortPointerList(r->next,right);
}

// Use INSERTSORT to sort list in asscending order between two list elements. Use only for presorted lists, otherwise time O(N^2)!
template <class Typ> 
void List<Typ>::ResortList() 
{
  ListEl<Typ> *c; // current element to be sorted in. Everything to the left is already sorted
  ListEl<Typ> *n; // next element to be sorted in
  ListEl<Typ> *p; // pointer for looping through sorted part of list
  ListEl<Typ> *pnext; // for swapping
  if (Size()<=1) return;
  c=head->next->next;
  while (c!=tail) 
    {
      p=c->prev;
      n=c->next;
      if (c->data < p->data)
	{
	  do {p=p->prev;} while (p!=head && c->data < p->data);
	  // Connect c->prev to c->next ...
	  c->next->prev=c->prev;
	  c->prev->next=c->next;
	  // ... and insert c between p and p->next ...
	  pnext=p->next;
	  p->next=c;
	  c->next=pnext;
	  pnext->prev=c;
	  c->prev=p;
	}
      c=n;
    }
}


#endif /* JLIST */


// //Main program: test class List

//  int main()
//  {
//    int p;
//    List<int>* plist=new List<int>(11);
//    List<int> list(22);

//    plist->Push(24);
//    plist->Push(18);
//    plist->Push(3);
//    plist->Enqueue(17);
//    plist->Enqueue(29);
//    printf("List 1 with pushed and enqueued elements:\n");
//    plist->PrintList();

//    list.Push(222);
//    printf("List 1 with list 2 appended:\n");
//    plist->Append(&list);
//    plist->PrintList();

//    printf("Pushing one element three times into list 2:\n");
//    list.Push(333);
//    list.Push(444);
//    list.Push(555);
//    printf("Printing plist and list with three elements:\n");
//    list.PrintList();
//    plist->PrintList();
  
//    printf("list.Copy(plist). Printing list 1 and 2:\n");
//    list.Copy(plist);
//    plist->PrintList(); 
//    list.PrintList();

//    printf("Appending list 1 to itself:\n");
//    plist->Append(plist);
//    plist->PrintList();

//    cout<<"Popping "<<plist->Pop()<<"\n";
//    cout<<"Popping "<<plist->Pop()<<"\n";
//    plist->PrintList();

//    cout<<"Dequeing "<<plist->Dequeue()<<"\n";
//    cout<<"Dequeing "<<plist->Dequeue()<<"\n";
//    plist->PrintList();

//    cout<<"Reversing list\n";
//    plist->Reverse();
//    plist->PrintList();

//    cout<<"Reversing to original list\n";
//    plist->Reverse();
//    plist->PrintList();

//    for (p=plist->Reset(); p>=5;p--)
//      {cout<<plist->GetPos()<<": "<<plist->Read(p)<<"\n";}
  
//    cout<<"Deleting "<<plist->Delete()<<"\n";
//    cout<<"Deleting "<<plist->Delete()<<"\n";
//    plist->PrintList();

//    plist->Append(plist);
//    plist->PrintList();
//    cout<<"List 1 sorted:\n";
//    plist->SortList();
//    plist->PrintList();

//  }