4 * Copyright (c) 2007 Des Higgins, Julie Thompson and Toby Gibson.
7 * Author: Mark Larkin UCD Conway Institute
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.
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.
23 #ifndef RANDOMACCESSLLIST_H
24 #define RANDOMACCESSLLIST_H
38 ListElement(T* e, ListElement* n, ListElement* p, unsigned int _index)
52 unsigned int getIndex(){return index;}
62 class RandomAccessLList
65 RandomAccessLList(int size)
69 elements = new ListElement<T>*[size];
70 for(int i = 0; i < size; i++)
78 for(int i = 0; i < maxSize; i++)
88 unsigned int getNumElements(){return numElements;}
90 void addElementToBack(T* element)
92 if(numElements < maxSize)
95 elements[numElements] = new ListElement<T>(element, 0, 0, numElements);
100 elements[numElements]->next = 0;
101 elements[numElements]->prev = 0;
102 firstElementInList = elements[numElements];
105 else if(numElements > 0) // If it is not the first element
107 elements[numElements - 1]->next = elements[numElements];
108 elements[numElements]->prev = elements[numElements - 1];
109 elements[numElements]->next = 0;
115 ListElement<T>* getAt(int index)
117 if(index >= 0 && index < maxSize)
119 return elements[index];
123 cout << "\nCannot get item : " << index << "\n";
128 ListElement<T>* getFirst()
130 return firstElementInList;
133 void removeItem(ListElement<T>* item)
137 int index = item->getIndex();
138 if(elements[index] != 0)
140 if(item->prev == 0 && item->next == 0) // Last item in the list
142 firstElementInList = 0;
143 delete item; // Not sure if this is good or not.
147 else if(item->prev == 0) // remove First in the list
149 firstElementInList = item->next;
150 firstElementInList->prev = 0;
152 delete item; // Not sure if this is good or not.
156 else if(item->next == 0) // remove last item
158 ListElement<T>* prevElem = item->prev;
161 delete item; // Not sure if this is good or not.
165 else // remove middle item
167 ListElement<T>* prevElem = item->prev;
168 ListElement<T>* nextElem = item->next;
169 prevElem->next = nextElem;
170 nextElem->prev = prevElem;
173 delete item; // Not sure if this is good or not.
182 cout << "ERROR: trying to remove item outside the bounds\n";
187 ListElement<T>** elements;
188 ListElement<T>* firstElementInList;
190 unsigned int numElements;