Mercurial > repos > clustalomega > clustalomega

comparison clustalomega/clustal-omega-0.2.0/src/hhalign/list.h @ 0:ff1768533a07

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
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
comparison
equal deleted inserted replaced
-1:000000000000 0:ff1768533a07
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