Mercurial > repos > clustalomega > clustalomega
view clustalomega/clustal-omega-0.2.0/src/hhalign/list-C.h @ 0:ea6d0e588642 default tip
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
author | clustalomega |
---|---|
date | Tue, 07 Jun 2011 16:13:02 -0400 |
parents | |
children |
line wrap: on
line source
/* -*- 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(); // }