1 /* -*- mode: c; tab-width: 4; c-basic-offset: 4; indent-tabs-mode: nil -*- */
3 /*********************************************************************
4 * Clustal Omega - Multiple sequence alignment
6 * Copyright (C) 2010 University College Dublin
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.
13 * This file is part of Clustal-Omega.
15 ********************************************************************/
18 * RCS $Id: list-C.h 143 2010-10-14 13:11:14Z andreas $
22 // Class for double-linked list
30 #include <iostream> // cin, cout
31 #include <stdlib.h> //
39 ////////////////////////////////////////////////////////////////////////////
40 // Double-linked list implementation with head and tail dummy elements
41 // We set head->prev=head and tail->next=tail.
42 // This makes sure that repeated current=current->next; ends up in tail
43 // and repeated current=current->prev; ends up in head.
44 // head and tail optionally contain a NULL element of Typ defined by method Null(Typ)
45 ////////////////////////////////////////////////////////////////////////////
49 ////////////////////////////////////////////////////////////////////////////
50 // Constructors and destructor
52 ////////////////////////////////////////////////////////////////////////////
53 // Creates empty List with two dummy elements
54 ////////////////////////////////////////////////////////////////////////////
58 head=new ListEl<Typ>();
59 if (!head) { cerr<<"Could not create new element\n"; return; }
60 tail=new ListEl<Typ>(head,NULL);
61 if (!tail) { cerr<<"Could not create new element\n"; return; }
69 ////////////////////////////////////////////////////////////////////////////
70 // Creates List with one element
71 ////////////////////////////////////////////////////////////////////////////
73 List<Typ>::List(Typ d)
75 head=new ListEl<Typ>();
76 if (!head) { cerr<<"Could not create new element\n"; return; }
77 tail=new ListEl<Typ>();
78 if (!tail) { cerr<<"Could not create new element\n"; return; }
79 ListEl<Typ>* el = new ListEl<Typ>(d,head,tail);
80 if (!el) { cerr<<"Could not create new element\n"; return; }
89 ////////////////////////////////////////////////////////////////////////////
90 // Destructor deletes List object
91 ////////////////////////////////////////////////////////////////////////////
95 ListEl<Typ>* n=head->next;
98 delete(head); head = NULL;
102 delete(head); head = NULL;
105 ////////////////////////////////////////////////////////////////////////////
107 ////////////////////////////////////////////////////////////////////////////
109 List<Typ>& List<Typ>::operator=(List<Typ>& l)
118 ////////////////////////////////////////////////////////////////////////////
119 // Reverse order of list
120 ////////////////////////////////////////////////////////////////////////////
122 void List<Typ>::Reverse()
124 ListEl<Typ> *n; // next list element; also for swapping
125 ListEl<Typ> *c; // current element to be sorted in. Everything to the left is already sorted
126 if (Size()<=1) return;
127 for (c=head; c!=tail; c=n)
129 // Swap prev and next pointers of all list elements
135 // Swap prev and next pointers of tail
136 tail->next = tail->prev;
148 ////////////////////////////////////////////////////////////////////////////
149 // Methods that act at the end of the list
151 ////////////////////////////////////////////////////////////////////////////
152 // Insert Element after LAST of list (and return address of data element)
153 ////////////////////////////////////////////////////////////////////////////
155 Typ* List<Typ>::Push(Typ d)
157 ListEl<Typ>* t=new ListEl<Typ>(d,tail->prev,tail);
158 if (!t) { cerr<<"Could not create new element\n"; return 0; }
165 ////////////////////////////////////////////////////////////////////////////
166 // Remove and return LAST element of list. Returns head->data if empty
167 ////////////////////////////////////////////////////////////////////////////
171 if (!size) return head->data;
172 ListEl<Typ>* t=tail->prev;
173 if (current==t) current=tail;
184 ////////////////////////////////////////////////////////////////////////////
185 // Methods that act at the beginning of the list
187 ////////////////////////////////////////////////////////////////////////////
188 // Insert element as FIRST element of list (and return address of data element)
189 ////////////////////////////////////////////////////////////////////////////
191 Typ* List<Typ>::Enqueue(Typ d)
193 ListEl<Typ>* h = new ListEl<Typ>(d,head,head->next);
194 if (!h) { cerr<<"Could not create new element\n"; return 0; }
201 ////////////////////////////////////////////////////////////////////////////
202 // Remove element at BEGINNING of list
203 ////////////////////////////////////////////////////////////////////////////
205 Typ List<Typ>::Dequeue()
207 if (!size) return head->data;
208 ListEl<Typ>* h=head->next;
209 if (current==h) current=head;
218 ////////////////////////////////////////////////////////////////////////////
219 // Methods that work with 'current' position in the list
221 ////////////////////////////////////////////////////////////////////////////
222 // Reads next element; advances current position by 1
223 ////////////////////////////////////////////////////////////////////////////
225 inline Typ List<Typ>::ReadNext()
227 current = current->next;
228 return current->data;
231 ////////////////////////////////////////////////////////////////////////////
232 // Reads current element again (NULL if nothing read yet)
233 ////////////////////////////////////////////////////////////////////////////
235 inline Typ List<Typ>::ReadCurrent()
237 return current->data;
240 ////////////////////////////////////////////////////////////////////////////
241 // Reads previous element; moves current position back by 1
242 ////////////////////////////////////////////////////////////////////////////
244 inline Typ List<Typ>::ReadPrevious()
246 current = current->prev;
247 return current->data;
250 ////////////////////////////////////////////////////////////////////////////
251 // Reads next element; advances current position by 1
252 ////////////////////////////////////////////////////////////////////////////
254 inline Typ* List<Typ>::ReadNextAddress()
256 current = current->next;
257 if (current==tail) return NULL;
258 return &(current->data);
261 ////////////////////////////////////////////////////////////////////////////
262 // Reads address of current element again, returns NULL if at end of list
263 ////////////////////////////////////////////////////////////////////////////
265 inline Typ* List<Typ>::ReadCurrentAddress()
267 if (current==tail) return NULL;
268 return &(current->data);
271 ////////////////////////////////////////////////////////////////////////////
272 // Sets current position to k and reads k'th element (first=1)
273 ////////////////////////////////////////////////////////////////////////////
275 Typ List<Typ>::Read(int pos)
277 if (pos>size) {current = tail; return tail->data;}
278 if (pos<=0) {current = head; return head->data;}
279 current = head->next;
280 for (; pos>1; pos--) current = current->next; //If pos==2 do 1 iteration
281 return current->data;
284 ////////////////////////////////////////////////////////////////////////////
285 // Inserts element d AFTER current element and sets current element to inserted
286 ////////////////////////////////////////////////////////////////////////////
288 void List<Typ>::Insert(Typ d)
290 ListEl<Typ>* el = new ListEl<Typ>(d,current,current->next);
291 if (!el) { cerr<<"Could not create new element\n"; return; }
292 (current->next)->prev = el;
298 ////////////////////////////////////////////////////////////////////////////
299 // Deletes current element and returns content of deleted element. Current element
300 // will be previous one after Delete(). After Reset() delete first element (not 0'th)
301 ////////////////////////////////////////////////////////////////////////////
303 Typ List<Typ>::Delete()
307 if (!size || current==tail) return tail->data;
308 if (current==head) current = head->next; // After Reset() delete first element (not 0'th)
309 (current->prev)->next = current->next;
310 (current->next)->prev = current->prev;
313 delete current; current = NULL;
319 ////////////////////////////////////////////////////////////////////////////
320 // Methods that return useful information about the list
322 ////////////////////////////////////////////////////////////////////////////
323 // Get current position within list (0 <= pos <= Size+1)
324 ////////////////////////////////////////////////////////////////////////////
326 int List<Typ>::GetPos()
330 for (el = head; el!=current; el=el->next) pos++;
334 ////////////////////////////////////////////////////////////////////////////
336 ////////////////////////////////////////////////////////////////////////////
338 void List<Typ>::PrintList()
341 ListEl<Typ>* c=current;
347 cout<<j<<" "<<ReadNext()<<" ";
348 if (!(j%10)) cout<<"\n ";
354 ////////////////////////////////////////////////////////////////////////////
355 // Get largest data element
356 ////////////////////////////////////////////////////////////////////////////
358 Typ List<Typ>::Largest()
360 Typ* result= &((tail->prev)->data);
364 if (*result<ReadNext()) result=ReadCurrentAddress();
369 ////////////////////////////////////////////////////////////////////////////
370 // Get smallest data element
371 ////////////////////////////////////////////////////////////////////////////
373 Typ List<Typ>::Smallest()
375 Typ* result= &((tail->prev)->data);
379 if (ReadNext()<*result) result=ReadCurrentAddress();
384 /////////////////////////////////////////////////////////////////////////////
385 // Methods that manipulate the list as a whole
387 ////////////////////////////////////////////////////////////////////////////
388 // Copies list 0 into list object
389 ////////////////////////////////////////////////////////////////////////////
391 void List<Typ>::Copy(List<Typ>* list)
393 if (list==this) return;
394 while (!End()) Pop(); //empty list
396 while (!list->End()) Push(list->ReadNext());
399 ////////////////////////////////////////////////////////////////////////////
400 // Appends a copy of list2 to class object
401 ////////////////////////////////////////////////////////////////////////////
403 void List<Typ>::AppendCopy(List<Typ>* list2)
405 List<Typ>* cpy=new List<Typ>;
408 delete cpy; cpy = NULL;
411 ////////////////////////////////////////////////////////////////////////////
412 // Appends list2 to class object
413 ////////////////////////////////////////////////////////////////////////////
415 void List<Typ>::Append(List<Typ>* list)
417 if (this==list) { AppendCopy(list); return;}
418 (tail->prev)->next = list->head->next;
419 (list->head->next)->prev = tail->prev;
420 if (current==tail) current=tail->prev;
425 // Reuse old tail as new tail t for list2 and initialize pointers for empty list
430 list->head->prev=list->head;
431 t->data=list->head->data;
432 list->current=list->head;
436 ////////////////////////////////////////////////////////////////////////////
437 // Use QUICKSORT to sort list in ascending order between two list elements
438 ////////////////////////////////////////////////////////////////////////////
440 void List<Typ>::SortList(ListEl<Typ>* left, ListEl<Typ>* right, int sz)
442 if (sz<=1) return; // when SortList() is called, left=head->next, right=tail->prev
443 ListEl<Typ> *l=left->prev, *r=right->next;
445 // Choose *random* pivot element!!
446 // (Otherwise, complexity for an already sorted list is N^2 => recursive calls may lead to stack overflow)
448 for (int i=1; i<(int)(float(rand())*sz/(RAND_MAX+0.999)); i++) c = c->next;
451 Typ pivot = left->data;
452 // Typ* pivot= &(left->data);
454 // cout<<"Sorting between "<<left->data<<" and "<<right->data<<". Pivot="<<pivot<<endl;
458 do {r=r->prev; sz0--;} while (pivot < r->data);
459 do l=l->next; while (l->data < pivot);
460 if (l==r || l->prev==r) break;
463 SortList(left,r,sz0);
464 SortList(r->next,right,sz-sz0);
465 pivot = tail->data; // to avoid calling the destructor of Typ on some real data element
468 ////////////////////////////////////////////////////////////////////////////
469 // Use QUICKSORT to sort list of POINTERS by comparing the objects the pointers point to
470 ////////////////////////////////////////////////////////////////////////////
472 void List<Typ>::SortPointerList(ListEl<Typ>* left, ListEl<Typ>* right)
474 if (right==left || right->next==left) return;
475 ListEl<Typ> *l=left->prev, *r=right->next;
476 Typ pivot=left->data;
477 // cout<<"Sorting between "<<left->data<<" and "<<right->data<<". Pivot="<<pivot<<endl;
484 // cout<<"r=r->prev. r->data="<<r->data<<endl;
485 } while(*pivot < *(r->data));
489 // cout<<"l=l->next l->data="<<l->data<<endl;
490 } while (*(l->data) < *pivot);
491 if (l==r || l->prev==r) break;
494 SortPointerList(left,r);
495 SortPointerList(r->next,right);
498 // Use INSERTSORT to sort list in asscending order between two list elements. Use only for presorted lists, otherwise time O(N^2)!
500 void List<Typ>::ResortList()
502 ListEl<Typ> *c; // current element to be sorted in. Everything to the left is already sorted
503 ListEl<Typ> *n; // next element to be sorted in
504 ListEl<Typ> *p; // pointer for looping through sorted part of list
505 ListEl<Typ> *pnext; // for swapping
506 if (Size()<=1) return;
512 if (c->data < p->data)
514 do {p=p->prev;} while (p!=head && c->data < p->data);
515 // Connect c->prev to c->next ...
516 c->next->prev=c->prev;
517 c->prev->next=c->next;
518 // ... and insert c between p and p->next ...
533 // //Main program: test class List
538 // List<int>* plist=new List<int>(11);
539 // List<int> list(22);
544 // plist->Enqueue(17);
545 // plist->Enqueue(29);
546 // printf("List 1 with pushed and enqueued elements:\n");
547 // plist->PrintList();
550 // printf("List 1 with list 2 appended:\n");
551 // plist->Append(&list);
552 // plist->PrintList();
554 // printf("Pushing one element three times into list 2:\n");
558 // printf("Printing plist and list with three elements:\n");
560 // plist->PrintList();
562 // printf("list.Copy(plist). Printing list 1 and 2:\n");
564 // plist->PrintList();
567 // printf("Appending list 1 to itself:\n");
568 // plist->Append(plist);
569 // plist->PrintList();
571 // cout<<"Popping "<<plist->Pop()<<"\n";
572 // cout<<"Popping "<<plist->Pop()<<"\n";
573 // plist->PrintList();
575 // cout<<"Dequeing "<<plist->Dequeue()<<"\n";
576 // cout<<"Dequeing "<<plist->Dequeue()<<"\n";
577 // plist->PrintList();
579 // cout<<"Reversing list\n";
581 // plist->PrintList();
583 // cout<<"Reversing to original list\n";
585 // plist->PrintList();
587 // for (p=plist->Reset(); p>=5;p--)
588 // {cout<<plist->GetPos()<<": "<<plist->Read(p)<<"\n";}
590 // cout<<"Deleting "<<plist->Delete()<<"\n";
591 // cout<<"Deleting "<<plist->Delete()<<"\n";
592 // plist->PrintList();
594 // plist->Append(plist);
595 // plist->PrintList();
596 // cout<<"List 1 sorted:\n";
597 // plist->SortList();
598 // plist->PrintList();