binaries/src/clustalo/src/hhalign/list-C.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-C.h 143 2010-10-14 13:11:14Z andreas $
  19  */
  20
  21 // list.C
  22 // Class for double-linked list
  23
  24
  25
  26 #ifndef JLIST
  27 #define JLIST
  28
  29 #ifndef MAIN
  30 #include <iostream>   // cin, cout
  31 #include <stdlib.h>   //
  32 #include <stdio.h>    //
  33 using std::cout;
  34 using std::cerr;
  35 #endif
  36
  37 #include "list.h"
  38
  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 ////////////////////////////////////////////////////////////////////////////
  46
  47
  48
  49 ////////////////////////////////////////////////////////////////////////////
  50 // Constructors and destructor
  51
  52 ////////////////////////////////////////////////////////////////////////////
  53 // Creates empty List with two dummy elements
  54 ////////////////////////////////////////////////////////////////////////////
  55 template <class Typ>
  56 List<Typ>::List()
  57 {
  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; }
  62   tail->next = tail;
  63   head->prev = head;
  64   head->next = tail;
  65   current = head;
  66   size=0;
  67 }
  68
  69 ////////////////////////////////////////////////////////////////////////////
  70 // Creates List with one element
  71 ////////////////////////////////////////////////////////////////////////////
  72 template <class Typ>
  73 List<Typ>::List(Typ d)
  74 {
  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; }
  81   head->prev = head;
  82   head->next = el;
  83   tail->prev = el;
  84   tail->next = tail;
  85   current = head;
  86   size=1;
  87 }
  88
  89 ////////////////////////////////////////////////////////////////////////////
  90 // Destructor deletes List object
  91 ////////////////////////////////////////////////////////////////////////////
  92 template <class Typ>
  93 List<Typ>::~List()
  94 {
  95   ListEl<Typ>* n=head->next;
  96   while(head!=n)
  97     {
  98       delete(head); head = NULL;
  99       head=n;
 100       n=head->next;
 101   }
 102   delete(head); head = NULL;
 103 }
 104
 105 ////////////////////////////////////////////////////////////////////////////
 106 // Flat copy
 107 ////////////////////////////////////////////////////////////////////////////
 108 template <class Typ>
 109 List<Typ>& List<Typ>::operator=(List<Typ>& l)
 110 {
 111   head = l.head;
 112   tail = l.tail;
 113   current = l.current;
 114   size = l.size;
 115 }
 116
 117
 118 ////////////////////////////////////////////////////////////////////////////
 119 // Reverse order of list
 120 ////////////////////////////////////////////////////////////////////////////
 121 template <class Typ>
 122 void List<Typ>::Reverse()
 123 {
 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)
 128     {
 129       // Swap prev and next pointers of all list elements
 130       n = c->next;
 131       c->next = c->prev;
 132       c->prev = n;
 133     }
 134
 135   // Swap prev and next pointers of tail
 136   tail->next = tail->prev;
 137   tail->prev = tail;
 138
 139   // Swap head an tail
 140   n = head;
 141   head = tail;
 142   tail = n;
 143 }
 144
 145
 146
 147
 148 ////////////////////////////////////////////////////////////////////////////
 149 // Methods that act at the end of the list
 150
 151 ////////////////////////////////////////////////////////////////////////////
 152 // Insert Element after LAST of list  (and return address of data element)
 153 ////////////////////////////////////////////////////////////////////////////
 154 template <class Typ>
 155 Typ* List<Typ>::Push(Typ d)
 156 {
 157   ListEl<Typ>* t=new ListEl<Typ>(d,tail->prev,tail);
 158   if (!t) { cerr<<"Could not create new element\n"; return 0; }
 159   tail->prev->next=t;
 160   tail->prev = t;
 161   size++;
 162   return &(t->data);
 163 }
 164
 165 ////////////////////////////////////////////////////////////////////////////
 166 // Remove and return LAST element of list. Returns head->data if empty
 167 ////////////////////////////////////////////////////////////////////////////
 168 template <class Typ>
 169 Typ List<Typ>::Pop()
 170 {
 171   if (!size) return head->data;
 172   ListEl<Typ>* t=tail->prev;
 173   if (current==t) current=tail;
 174   Typ d=t->data;
 175   t->prev->next=tail;
 176   tail->prev=t->prev;
 177   delete t; t = NULL;
 178   size--;
 179   return d;
 180 }
 181
 182
 183
 184 ////////////////////////////////////////////////////////////////////////////
 185 // Methods that act at the beginning of the list
 186
 187 ////////////////////////////////////////////////////////////////////////////
 188 // Insert element as FIRST element of list (and return address of data element)
 189 ////////////////////////////////////////////////////////////////////////////
 190 template <class Typ>
 191 Typ* List<Typ>::Enqueue(Typ d)
 192 {
 193   ListEl<Typ>* h = new ListEl<Typ>(d,head,head->next);
 194   if (!h) { cerr<<"Could not create new element\n"; return 0; }
 195   h->next->prev = h;
 196   head->next=h;
 197   size++;
 198   return &(h->data);
 199 }
 200
 201 ////////////////////////////////////////////////////////////////////////////
 202 // Remove element at BEGINNING of list
 203 ////////////////////////////////////////////////////////////////////////////
 204 template <class Typ>
 205 Typ List<Typ>::Dequeue()
 206 {
 207   if (!size) return head->data;
 208   ListEl<Typ>* h=head->next;
 209   if (current==h) current=head;
 210   Typ d=h->data;
 211   h->next->prev=head;
 212   head->next=h->next;
 213   delete h; h = NULL;
 214   size--;
 215   return d;
 216 }
 217
 218 ////////////////////////////////////////////////////////////////////////////
 219 // Methods that work with 'current' position in the list
 220
 221 ////////////////////////////////////////////////////////////////////////////
 222 // Reads next element; advances current position by 1
 223 ////////////////////////////////////////////////////////////////////////////
 224 template <class Typ>
 225 inline Typ List<Typ>::ReadNext()
 226 {
 227   current = current->next;
 228   return current->data;
 229 }
 230
 231 ////////////////////////////////////////////////////////////////////////////
 232 // Reads current element again (NULL if nothing read yet)
 233 ////////////////////////////////////////////////////////////////////////////
 234 template <class Typ>
 235 inline Typ List<Typ>::ReadCurrent()
 236 {
 237   return current->data;
 238 }
 239
 240 ////////////////////////////////////////////////////////////////////////////
 241 // Reads previous element; moves current position back by 1
 242 ////////////////////////////////////////////////////////////////////////////
 243 template <class Typ>
 244 inline Typ List<Typ>::ReadPrevious()
 245 {
 246   current = current->prev;
 247   return current->data;
 248 }
 249
 250 ////////////////////////////////////////////////////////////////////////////
 251 // Reads next element; advances current position by 1
 252 ////////////////////////////////////////////////////////////////////////////
 253 template <class Typ>
 254 inline Typ* List<Typ>::ReadNextAddress()
 255 {
 256   current = current->next;
 257   if (current==tail) return NULL;
 258   return &(current->data);
 259 }
 260
 261 ////////////////////////////////////////////////////////////////////////////
 262 // Reads address of current element again, returns NULL if at end of list
 263 ////////////////////////////////////////////////////////////////////////////
 264 template <class Typ>
 265 inline Typ* List<Typ>::ReadCurrentAddress()
 266 {
 267   if (current==tail) return NULL;
 268   return &(current->data);
 269 }
 270
 271 ////////////////////////////////////////////////////////////////////////////
 272 // Sets current position to k and reads k'th element (first=1)
 273 ////////////////////////////////////////////////////////////////////////////
 274 template <class Typ>
 275 Typ List<Typ>::Read(int pos)
 276 {
 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;
 282 }
 283
 284 ////////////////////////////////////////////////////////////////////////////
 285 // Inserts element d AFTER current element and sets current element to inserted
 286 ////////////////////////////////////////////////////////////////////////////
 287 template <class Typ>
 288 void List<Typ>::Insert(Typ d)
 289 {
 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;
 293   current->next = el;
 294   current=el;
 295   size++;
 296 }
 297
 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 ////////////////////////////////////////////////////////////////////////////
 302 template <class Typ>
 303 Typ List<Typ>::Delete()
 304 {
 305   Typ d;
 306   ListEl<Typ>* p;
 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;
 311   d = current->data;
 312   p = current->prev;
 313   delete current; current = NULL;
 314   current = p;
 315   size--;
 316   return d;
 317 }
 318
 319 ////////////////////////////////////////////////////////////////////////////
 320 // Methods that return useful information about the list
 321
 322 ////////////////////////////////////////////////////////////////////////////
 323 // Get current position within list (0 <= pos <= Size+1)
 324 ////////////////////////////////////////////////////////////////////////////
 325 template <class Typ>
 326 int List<Typ>::GetPos()
 327 {
 328   int pos=0;
 329   ListEl<Typ>* el;
 330   for (el = head; el!=current; el=el->next) pos++;
 331   return pos;
 332 }
 333
 334 ////////////////////////////////////////////////////////////////////////////
 335 //print out list
 336 ////////////////////////////////////////////////////////////////////////////
 337 template <class Typ>
 338 void List<Typ>::PrintList()
 339 {
 340   int j=0;
 341   ListEl<Typ>* c=current;
 342   Reset();
 343   printf("List: ");
 344   while (!End())
 345     {
 346       j++;
 347       cout<<j<<" "<<ReadNext()<<"  ";
 348       if (!(j%10)) cout<<"\n      ";
 349     }
 350   cout<<"\n";
 351   current=c;
 352 }
 353
 354 ////////////////////////////////////////////////////////////////////////////
 355 // Get largest data element
 356 ////////////////////////////////////////////////////////////////////////////
 357 template <class Typ>
 358 Typ List<Typ>::Largest()
 359 {
 360   Typ* result= &((tail->prev)->data);
 361   Reset();
 362   while (!End())
 363     {
 364       if (*result<ReadNext()) result=ReadCurrentAddress();
 365     }
 366   return *result;
 367 }
 368
 369 ////////////////////////////////////////////////////////////////////////////
 370 // Get smallest data element
 371 ////////////////////////////////////////////////////////////////////////////
 372 template <class Typ>
 373 Typ List<Typ>::Smallest()
 374 {
 375   Typ* result= &((tail->prev)->data);
 376   Reset();
 377   while (!End())
 378     {
 379       if (ReadNext()<*result) result=ReadCurrentAddress();
 380     }
 381   return *result;
 382 }
 383
 384 /////////////////////////////////////////////////////////////////////////////
 385 // Methods that manipulate the list as a whole
 386
 387 ////////////////////////////////////////////////////////////////////////////
 388 // Copies list 0 into list object
 389 ////////////////////////////////////////////////////////////////////////////
 390 template <class Typ>
 391 void List<Typ>::Copy(List<Typ>* list)
 392 {
 393   if (list==this) return;
 394   while (!End()) Pop(); //empty list
 395   list->Reset();
 396   while (!list->End()) Push(list->ReadNext());
 397 }
 398
 399 ////////////////////////////////////////////////////////////////////////////
 400 // Appends a copy of list2 to class object
 401 ////////////////////////////////////////////////////////////////////////////
 402 template <class Typ>
 403 void List<Typ>::AppendCopy(List<Typ>* list2)
 404 {
 405   List<Typ>* cpy=new List<Typ>;
 406   cpy->Copy(list2);
 407   Append(cpy);
 408   delete cpy; cpy = NULL;
 409 }
 410
 411 ////////////////////////////////////////////////////////////////////////////
 412 // Appends list2 to class object
 413 ////////////////////////////////////////////////////////////////////////////
 414 template <class Typ>
 415 void List<Typ>::Append(List<Typ>* list)
 416 {
 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;
 421   ListEl<Typ>* t=tail;
 422   tail = list->tail;
 423   size += list->size;
 424
 425 // Reuse old tail as new tail t for list2 and initialize pointers for empty list
 426   list->tail=t;
 427   list->head->next=t;
 428   t->prev=list->head;
 429   t->next=t;
 430   list->head->prev=list->head;
 431   t->data=list->head->data;
 432   list->current=list->head;
 433   list->size = 0;
 434 }
 435
 436 ////////////////////////////////////////////////////////////////////////////
 437 // Use QUICKSORT to sort list in ascending order between two list elements
 438 ////////////////////////////////////////////////////////////////////////////
 439 template <class Typ>
 440 void List<Typ>::SortList(ListEl<Typ>* left, ListEl<Typ>* right, int sz)
 441 {
 442   if (sz<=1) return; // when SortList() is called, left=head->next, right=tail->prev
 443   ListEl<Typ> *l=left->prev, *r=right->next;
 444
 445   // Choose *random* pivot element!!
 446   // (Otherwise, complexity for an already sorted list is N^2 => recursive calls may lead to stack overflow)
 447   ListEl<Typ> *c=left;
 448   for (int i=1; i<(int)(float(rand())*sz/(RAND_MAX+0.999)); i++) c = c->next;
 449   SwapContent(left,c);
 450
 451   Typ pivot = left->data;
 452 //   Typ* pivot= &(left->data);
 453   int sz0=sz+1;
 454   //  cout<<"Sorting between "<<left->data<<" and "<<right->data<<". Pivot="<<pivot<<endl;
 455   while(1)
 456     {
 457 //        PrintList();
 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;
 461       SwapContent(l,r);
 462     }
 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
 466  }
 467
 468 ////////////////////////////////////////////////////////////////////////////
 469 // Use QUICKSORT to sort list of POINTERS by comparing the objects the pointers point to
 470 ////////////////////////////////////////////////////////////////////////////
 471 template <class Typ>
 472 void List<Typ>::SortPointerList(ListEl<Typ>* left, ListEl<Typ>* right)
 473 {
 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;
 478   while(1)
 479     {
 480 //        PrintList();
 481       do
 482         {
 483           r=r->prev;
 484 //        cout<<"r=r->prev. r->data="<<r->data<<endl;
 485         } while(*pivot < *(r->data));
 486       do
 487         {
 488           l=l->next;
 489 //        cout<<"l=l->next l->data="<<l->data<<endl;
 490         } while (*(l->data) < *pivot);
 491       if (l==r || l->prev==r) break;
 492       SwapContent(l,r);
 493     }
 494   SortPointerList(left,r);
 495   SortPointerList(r->next,right);
 496 }
 497
 498 // Use INSERTSORT to sort list in asscending order between two list elements. Use only for presorted lists, otherwise time O(N^2)!
 499 template <class Typ>
 500 void List<Typ>::ResortList()
 501 {
 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;
 507   c=head->next->next;
 508   while (c!=tail)
 509     {
 510       p=c->prev;
 511       n=c->next;
 512       if (c->data < p->data)
 513         {
 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 ...
 519           pnext=p->next;
 520           p->next=c;
 521           c->next=pnext;
 522           pnext->prev=c;
 523           c->prev=p;
 524         }
 525       c=n;
 526     }
 527 }
 528
 529
 530 #endif /* JLIST */
 531
 532
 533 // //Main program: test class List
 534
 535 //  int main()
 536 //  {
 537 //    int p;
 538 //    List<int>* plist=new List<int>(11);
 539 //    List<int> list(22);
 540
 541 //    plist->Push(24);
 542 //    plist->Push(18);
 543 //    plist->Push(3);
 544 //    plist->Enqueue(17);
 545 //    plist->Enqueue(29);
 546 //    printf("List 1 with pushed and enqueued elements:\n");
 547 //    plist->PrintList();
 548
 549 //    list.Push(222);
 550 //    printf("List 1 with list 2 appended:\n");
 551 //    plist->Append(&list);
 552 //    plist->PrintList();
 553
 554 //    printf("Pushing one element three times into list 2:\n");
 555 //    list.Push(333);
 556 //    list.Push(444);
 557 //    list.Push(555);
 558 //    printf("Printing plist and list with three elements:\n");
 559 //    list.PrintList();
 560 //    plist->PrintList();
 561
 562 //    printf("list.Copy(plist). Printing list 1 and 2:\n");
 563 //    list.Copy(plist);
 564 //    plist->PrintList();
 565 //    list.PrintList();
 566
 567 //    printf("Appending list 1 to itself:\n");
 568 //    plist->Append(plist);
 569 //    plist->PrintList();
 570
 571 //    cout<<"Popping "<<plist->Pop()<<"\n";
 572 //    cout<<"Popping "<<plist->Pop()<<"\n";
 573 //    plist->PrintList();
 574
 575 //    cout<<"Dequeing "<<plist->Dequeue()<<"\n";
 576 //    cout<<"Dequeing "<<plist->Dequeue()<<"\n";
 577 //    plist->PrintList();
 578
 579 //    cout<<"Reversing list\n";
 580 //    plist->Reverse();
 581 //    plist->PrintList();
 582
 583 //    cout<<"Reversing to original list\n";
 584 //    plist->Reverse();
 585 //    plist->PrintList();
 586
 587 //    for (p=plist->Reset(); p>=5;p--)
 588 //      {cout<<plist->GetPos()<<": "<<plist->Read(p)<<"\n";}
 589
 590 //    cout<<"Deleting "<<plist->Delete()<<"\n";
 591 //    cout<<"Deleting "<<plist->Delete()<<"\n";
 592 //    plist->PrintList();
 593
 594 //    plist->Append(plist);
 595 //    plist->PrintList();
 596 //    cout<<"List 1 sorted:\n";
 597 //    plist->SortList();
 598 //    plist->PrintList();
 599
 600 //  }