--- /dev/null
+/* -*- 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();
+
+// }
git://source.jalview.org / jabaws.git / blobdiff