website/archive/binaries/mac/src/clustalw/src/general/RandomAccessLList.h

   1 /**
   2  * Author: Mark Larkin
   3  *
   4  * Copyright (c) 2007 Des Higgins, Julie Thompson and Toby Gibson.
   5  */
   6 /**
   7  * Author: Mark Larkin UCD Conway Institute
   8  *
   9  * This class is to be used as a linked list type container.
  10  * The features are as follows:
  11  * 1) It allows efficient deletions anywhere.
  12  * 2) It also allows efficient random access.
  13  * 3) Its maximum size is fixed at creation.
  14  * 4) Items can only be added at the end.
  15  * 5) when it is destroyed it will delete the structure, but not the elements.
  16  *
  17  * Limitations:
  18  * It returns the ListElements directly, this is not the best way. A better way would be
  19  * to return an iterator of some kind, but this would take alot more work. At the moment
  20  * it is possible to have 2 LList objects and get an element from one list, and delete
  21  * it from another list. But this is ok for the time being. I will fix this later.
  22  */
  23 #ifndef RANDOMACCESSLLIST_H
  24 #define RANDOMACCESSLLIST_H
  25
  26 namespace clustalw
  27 {
  28
  29 template <class T>
  30 class ListElement
  31 {
  32     public:
  33         ListElement()
  34         {
  35             // Do nothing
  36         }
  37
  38         ListElement(T* e, ListElement* n, ListElement* p, unsigned int _index)
  39         {
  40             element = e;
  41             next = n;
  42             prev = p;
  43             index = _index;
  44         }
  45
  46         ~ListElement()
  47         {
  48             element = 0;
  49             next = 0;
  50         }
  51
  52         unsigned int getIndex(){return index;}
  53
  54         T* element;
  55         ListElement* next;
  56         ListElement* prev;
  57     private:
  58         unsigned int index;
  59 };
  60
  61 template <class T>
  62 class RandomAccessLList
  63 {
  64     public:
  65         RandomAccessLList(int size)
  66          : maxSize(size),
  67            numElements(0)
  68         {
  69             elements = new ListElement<T>*[size];
  70             for(int i = 0; i < size; i++)
  71             {
  72                 elements[i] = 0;
  73             }
  74         }
  75
  76         ~RandomAccessLList()
  77         {
  78             for(int i = 0; i < maxSize; i++)
  79             {
  80                 if(elements[i] != 0)
  81                 {
  82                     delete elements[i];
  83                 }
  84             }
  85             delete [] elements;
  86         }
  87
  88         unsigned int getNumElements(){return numElements;}
  89
  90         void addElementToBack(T* element)
  91         {
  92             if(numElements < maxSize)
  93             {
  94                 // Add the element
  95                 elements[numElements] = new ListElement<T>(element, 0, 0, numElements);
  96
  97                 if(numElements == 0)
  98                 {
  99                     // First element
 100                     elements[numElements]->next = 0;
 101                     elements[numElements]->prev = 0;
 102                     firstElementInList = elements[numElements];
 103                     numElements++;
 104                 }
 105                 else if(numElements > 0) // If it is not the first element
 106                 {
 107                     elements[numElements - 1]->next = elements[numElements];
 108                     elements[numElements]->prev = elements[numElements - 1];
 109                     elements[numElements]->next = 0;
 110                     numElements++;
 111                 }
 112             }
 113         }
 114
 115         ListElement<T>* getAt(int index)
 116         {
 117             if(index >= 0 && index < maxSize)
 118             {
 119                 return elements[index];
 120             }
 121             else
 122             {
 123                 cout << "\nCannot get item : " << index << "\n";
 124                 return 0;
 125             }
 126         }
 127
 128         ListElement<T>* getFirst()
 129         {
 130             return firstElementInList;
 131         }
 132
 133         void removeItem(ListElement<T>* item)
 134         {
 135             if(item != 0 )
 136             {
 137                 int index = item->getIndex();
 138                 if(elements[index] != 0)
 139                 {
 140                     if(item->prev == 0 && item->next == 0) // Last item in the list
 141                     {
 142                         firstElementInList = 0;
 143                         delete item; // Not sure if this is good or not.
 144                         item = 0;
 145                         numElements--;
 146                     }
 147                     else if(item->prev == 0) // remove First in the list
 148                     {
 149                         firstElementInList = item->next;
 150                         firstElementInList->prev = 0;
 151                         item->next = 0;
 152                         delete item; // Not sure if this is good or not.
 153                         item = 0;
 154                         numElements--;
 155                     }
 156                     else if(item->next == 0) // remove last item
 157                     {
 158                         ListElement<T>* prevElem = item->prev;
 159                         prevElem->next = 0;
 160                         item->prev = 0;
 161                         delete item; // Not sure if this is good or not.
 162                         item = 0;
 163                         numElements--;
 164                     }
 165                     else // remove middle item
 166                     {
 167                         ListElement<T>* prevElem = item->prev;
 168                         ListElement<T>* nextElem = item->next;
 169                         prevElem->next = nextElem;
 170                         nextElem->prev = prevElem;
 171                         item->prev = 0;
 172                         item->next = 0;
 173                         delete item; // Not sure if this is good or not.
 174                         item = 0;
 175                         numElements--;
 176                     }
 177                     elements[index] = 0;
 178                 }
 179             }
 180             else
 181             {
 182                 cout << "ERROR: trying to remove item outside the bounds\n";
 183             }
 184         }
 185
 186     private:
 187         ListElement<T>** elements;
 188         ListElement<T>* firstElementInList;
 189         int maxSize;
 190         unsigned int numElements;
 191
 192 };
 193
 194 }
 195
 196 #endif