website/archive/binaries/mac/src/clustalo/src/hhalign/list.h

   1 /* -*- mode: c; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
   2
   3 /*********************************************************************
   4  * Clustal Omega - Multiple sequence alignment
   5  *
   6  * Copyright (C) 2010 University College Dublin
   7  *
   8  * Clustal-Omega is free software; you can redistribute it and/or
   9  * modify it under the terms of the GNU General Public License as
  10  * published by the Free Software Foundation; either version 2 of the
  11  * License, or (at your option) any later version.
  12  *
  13  * This file is part of Clustal-Omega.
  14  *
  15  ********************************************************************/
  16
  17 /*
  18  * RCS $Id: list.h 143 2010-10-14 13:11:14Z andreas $
  19  */
  20
  21 // list.h
  22
  23
  24 //////////////////////////////////////////////////////////////////////////////
  25 // Double-linked list implementation with head and tail dummy elements
  26 // We set head->prev=head and tail->next=tail.
  27 // This makes sure that repeated current=current->next; ends up in tail
  28 // and repeated current=current->prev; ends up in head.
  29 // head and tail optionally contain a NULL element of Typ defined by method Null(Typ)
  30 //////////////////////////////////////////////////////////////////////////////
  31
  32 template<class Typ>
  33 class List
  34 {
  35 protected:
  36 template<class Typ1>
  37 class ListEl             //elements of List; essentially a data structure
  38   {
  39   public:
  40     Typ1 data;           //Typ is type of data to be stored in list
  41     ListEl* prev;        //points to previous list element
  42     ListEl* next;        //points to next list element
  43     ListEl() : prev(0), next(0) {}
  44     ListEl(Typ1 d) : data(d), prev(0), next(0) {}
  45     ListEl(ListEl* p, ListEl* n) : prev(p), next(n) {}
  46     ListEl(Typ1 d, ListEl* p, ListEl* n) : data(d), prev(p), next(n) {}
  47   };
  48
  49   ListEl<Typ>* head;     //points to dummy element at beginning of list
  50   ListEl<Typ>* tail;     //points to dummy element at end of list
  51   ListEl<Typ>* current;  //current element position within list
  52   int size;              //Number of elements in list
  53
  54   // Use QUICKSORT to sort list in asscending order between two list elements
  55   void SortList(ListEl<Typ>*, ListEl<Typ>*, int);
  56   // Use QUICKSORT to sort list of pointers by comparing elements they point to
  57   void SortPointerList(ListEl<Typ>*, ListEl<Typ>*);
  58
  59   // Swap two list elements by making a flat copy (don't need two copies of data)
  60   // Warning: Gets slow if Typ is composite type with many variables (>=5)
  61   void SwapContent(ListEl<Typ>* e1, ListEl<Typ>* e2)
  62   { Typ d; if (e1!=e2) {d=e1->data; e1->data=e2->data; e2->data=d;} }
  63
  64 public:
  65 //////////////////////////////////////////////////////////////////////////////
  66 // General methods
  67   List();
  68   List(Typ d);
  69   ~List();
  70   List<Typ>& operator=(List<Typ>&);
  71
  72   // Set Null element that will be returned when trying to read from an empty list
  73   void Null(Typ null) {head->data = tail->data = null;}
  74
  75
  76 //////////////////////////////////////////////////////////////////////////////
  77 // Methods that act at the end of the list
  78
  79   // Insert Element after LAST element of list (and return address of data element)
  80   Typ* Push(Typ);
  81
  82   // Remove and return LAST element of list. Returns head->data if list empty
  83   Typ Pop();
  84
  85   // return LAST element of list. Returns null element in head->data if list empty
  86   Typ ReadLast() {return tail->prev->data;}
  87
  88
  89 //////////////////////////////////////////////////////////////////////////////
  90 // Methods that act at the beginning of the list
  91
  92   // Insert element as FIRST element of list (and return address of data element)
  93   Typ* Enqueue(Typ);
  94
  95   // Remove and return element at BEGINNING of list. Returns head->data if list empty
  96   Typ Dequeue();
  97
  98   // return FIRST element of list. Returns null element in head->data if list empty
  99   Typ ReadFirst() {if (size) return head->next->data; else return head->data;}
 100
 101
 102 //////////////////////////////////////////////////////////////////////////////
 103 // Methods that work with 'current' position in the list
 104
 105   // Advances current position by 1 and reads next element; returns head->data if at end of list.
 106   Typ ReadNext();
 107
 108   // Reads current element again
 109   Typ ReadCurrent();
 110
 111   // Moves current position back by 1 and reads previous element; returns head->data if at beginning of list.
 112   Typ ReadPrevious();
 113
 114   // Advances current position by 1 and reads address of next element; returns NULL if at end of list.
 115   Typ* ReadNextAddress();
 116
 117   // Reads address of current element again, returns NULL if at end of list
 118   Typ* ReadCurrentAddress();
 119
 120   // Sets current position to k and reads k'th element (first=1). Returns head->data if current points to no data element
 121   Typ Read(int);
 122
 123   // Inserts element AFTER CURRENT element; current element will be set to inserted element
 124   void Insert(Typ);
 125
 126   // Removes and returns element at CURRENT position. New position is one BEFORE current position.
 127   // Returns head->data if current points to no data element. After Reset() delete first element (not 0'th)
 128   Typ Delete();
 129
 130   // Overwrites data at current position with new data
 131   void Overwrite(Typ d) {current->data=d;}
 132
 133   // Reset current position to 0 (one BEFORE the first)
 134   int Reset() {current = head; return size;}
 135
 136   // Reset current position to End (one AFTER the last)
 137   int SetToEnd() {current = tail; return size;}
 138
 139
 140 //////////////////////////////////////////////////////////////////////////////
 141 // Methods that return information about the list
 142
 143   // Return number of list elements (size>=0)
 144   int Size()  {return size;}
 145
 146   // return true if end of list, i.e. ReadNext would give tail->data (i.e. current position >= Size)
 147   char End()  {return (current==tail || current==tail->prev);}
 148   char End(void* curr)  {return ( curr == tail || curr == tail->prev);}
 149
 150   // return true if start of list, i.e. ReadPrevious would give head->data (i.e. current position <=1)
 151   char Start()  {return (current==head || current==head->next);}
 152
 153   // Get current position within list (0 <= pos <= Size+1)
 154   int GetPos();
 155
 156   //print out list (elements assumed int)
 157   void PrintList();
 158
 159   // Get largest data element (Null element for empty list)
 160   Typ Largest();
 161
 162   // Get smallest data element (Null element for empty list)
 163   Typ Smallest();
 164
 165 //////////////////////////////////////////////////////////////////////////////
 166 // Methods that manipulate the list as a whole
 167
 168   // Reverse list
 169   void Reverse();
 170
 171   // Copies list into list object
 172   void Copy(List<Typ>* list);
 173
 174   // Appends a copy of list to class object
 175   void AppendCopy(List<Typ>* list);
 176
 177   // Appends list to class object list
 178   void Append(List<Typ>* list);
 179
 180   // Use QUICKSORT to sort list in ascending order. Use only for UNSORTED lists, otherwise time O(N^2) instead of O(N*log(N))
 181 /*   void SortList() {if (size>1) SortList(head->next, tail->prev);}  */
 182   void SortList() {if (size>1) SortList(head->next, tail->prev, size);}
 183   void QuickSort() {if (size>1) SortList(head->next, tail->prev, size);}
 184
 185   // Use QUICKSORT to sort list of pointers in ascending order. Use only for UNSORTED lists, otherwwise time O(N^2)!
 186   void SortPointerList() {if (size>1) SortPointerList(head->next, tail->prev);}
 187   void QuickSortPointer() {if (size>1) SortPointerList(head->next, tail->prev);}
 188
 189   // Use INSERTSORT to sort list in asscending order. Use only for PRESORTED lists, otherwise time O(N^2)!
 190   void ResortList();
 191 };
 192
 193