1 ///////////////////////////////////////////////////////////////////////////////
2 // Copyright (c) 2000-2015 Ericsson Telecom AB
3 // All rights reserved. This program and the accompanying materials
4 // are made available under the terms of the Eclipse Public License v1.0
5 // which accompanies this distribution, and is available at
6 // http://www.eclipse.org/legal/epl-v10.html
7 ///////////////////////////////////////////////////////////////////////////////
17 Item(const Item<T> & other); // not implemented
18 Item<T> & operator=(const Item<T> & rhs); // not implemented
19 // Default destructor is used
24 Item * Next; // pointer to the next element
25 Item * Prev; // pointer to the previous element
40 * Number of nodes in the list
45 * The initial node in the list
50 * The final node in the list
61 List(const List<T> & other);
62 List<T> & operator=(const List<T> & other);
65 typedef Item<T> * iterator;
68 * Returns the size of the list
70 size_t length() const {
79 * True if List is empty, false otherwise
91 * Sort the list using the < operator.
92 * To be used when T is a type with operator<
97 * Sort the list using the compare function.
98 * To be used when T is a pointer but we don't want to compare the pointers.
100 void sort(bool (*comparison_function)(const T lhs, const T rhs));
103 * Returns with a pointer to the begin of the list
105 Item<T> * begin() const {
110 * Returns with a pointer to the end of the list
112 Item<T> * end() const {
117 * Returns with reference to the first element
123 const T & front() const {
128 * Returns with reference to the last element
134 const T & back() const {
139 * Pushes element at the end of the list
141 void push_back(const T & element);
144 * Pushes element at the front of the list
146 void push_front(const T & element);
149 * Removes the final element in the list
154 * Removes the node from the list
156 void remove(iterator& node);
159 * Removes duplicated elements from the list.
172 List<T>::List(const List<T> & other)
176 if (other.empty()) return;
178 Item<T> * CurrentNode = other.First;
179 Item<T> * MyFinalNode = NULL;
181 while (CurrentNode != NULL) {
182 if (MyFinalNode == NULL) // first element
184 MyFinalNode = new Item<T>;
185 MyFinalNode->Data = CurrentNode->Data;
186 MyFinalNode->Next = NULL;
187 MyFinalNode->Prev = NULL;
191 MyFinalNode->Next = new Item<T>;
192 MyFinalNode->Next->Data = CurrentNode->Data;
193 MyFinalNode->Next->Next = NULL;
194 MyFinalNode->Next->Prev = MyFinalNode;
195 MyFinalNode = MyFinalNode->Next;
199 CurrentNode = CurrentNode->Next;
210 List<T> & List<T>::operator=(const List<T> & other) {
213 if (other.empty()) return *this;
215 Item<T> * CurrentNode = other.First;
216 Item<T> * MyFinalNode = NULL;
218 while (CurrentNode != NULL) {
219 if (MyFinalNode == NULL) {
220 MyFinalNode = new Item<T>;
221 MyFinalNode->Data = CurrentNode->Data;
222 MyFinalNode->Next = NULL;
223 MyFinalNode->Prev = NULL;
227 MyFinalNode->Next = new Item<T>;
228 MyFinalNode->Next->Data = CurrentNode->Data;
229 MyFinalNode->Next->Next = CurrentNode->Next;
230 MyFinalNode->Next->Prev = MyFinalNode;
231 MyFinalNode = MyFinalNode->Next;
235 CurrentNode = CurrentNode->Next;
243 void List<T>::freeMemory() {
244 if (Size > 0) // if list is not empty
246 Item<T> * CurrentNode = First;
247 Item<T> * NodeForDelete = NULL;
249 for (size_t i = 0; i != Size; ++i) {
250 NodeForDelete = CurrentNode;
251 CurrentNode = CurrentNode->Next;
252 delete NodeForDelete;
263 void List<T>::remove(iterator& node) {
264 if (Size == 0) return;
266 if (node == NULL) return;
268 if (node->Prev == NULL) // if this node was the first element in the list
272 node->Prev->Next = node->Next;
275 if (node->Next == NULL) // if this node was the last element in the list
279 node->Next->Prev = node->Prev;
289 void List<T>::clear() {
294 void List<T>::sort() {
295 if (Size <= 1) return;
298 for (Item<T>* left = First; left; left = left->Next) {
299 Item<T>* mini = left;
300 for (Item<T>* curr = left->Next; curr; curr = curr->Next) {
301 if (curr->Data < mini->Data) mini = curr;
306 mini->Data = left->Data;
313 void List<T>::sort(bool (*comparison_function)(const T lhs, const T rhs)) {
314 if (Size <= 1) return;
317 for (Item<T>* left = First; left; left = left->Next) {
318 Item<T>* mini = left;
319 for (Item<T>* curr = left->Next; curr; curr = curr->Next) {
320 if (comparison_function(curr->Data, mini->Data)) mini = curr;
325 mini->Data = left->Data;
332 void List<T>::push_back(const T & element) {
333 Item<T> * NewNode = new Item<T>;
334 NewNode->Data = element;
335 NewNode->Next = NULL;
337 if (Size == 0) // if list is empty
339 NewNode->Prev = NULL;
343 NewNode->Prev = Last;
344 Last->Next = NewNode;
352 void List<T>::push_front(const T & element) {
353 Item<T> * NewNode = new Item<T>;
354 NewNode->Data = element;
355 NewNode->Prev = NULL;
357 if (Size == 0) // if list is empty
359 NewNode->Next = NULL;
363 NewNode->Next = First;
364 First->Prev = NewNode;
372 void List<T>::pop_back() {
373 Item<T> * LastNode = Last;
380 } else if (Size > 1) {
381 Last->Prev->Next = NULL;
389 void List<T>::remove_dups() {
390 Item<T>* ptr1 = First, *ptr2, *dup;
392 while (ptr1 != NULL && ptr1->Next != NULL) {
394 while (ptr2->Next != NULL) {
395 if (ptr1->Data == ptr2->Next->Data) {
397 ptr2->Next = ptr2->Next->Next;
398 //If the last element is a duplicate
399 if (ptr2->Next == NULL) {
402 ptr2->Next->Prev = ptr2;
415 #endif /* LIST_HH_ */