Mercurial > repos > clustalomega > clustalomega
diff clustalomega/clustal-omega-0.2.0/src/hhalign/list.h @ 0:ff1768533a07
Migrated tool version 0.2 from old tool shed archive to new tool shed repository
author | clustalomega |
---|---|
date | Tue, 07 Jun 2011 17:04:25 -0400 |
parents | |
children |
line wrap: on
line diff
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/clustalomega/clustal-omega-0.2.0/src/hhalign/list.h Tue Jun 07 17:04:25 2011 -0400 @@ -0,0 +1,193 @@ +/* -*- 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(); +}; + +