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