Commit | Line | Data |
---|---|---|
970ed795 | 1 | /////////////////////////////////////////////////////////////////////////////// |
3abe9331 | 2 | // Copyright (c) 2000-2015 Ericsson Telecom AB |
970ed795 EL |
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 | /////////////////////////////////////////////////////////////////////////////// | |
8 | #ifndef LIST_HH_ | |
9 | #define LIST_HH_ | |
10 | ||
11 | #include <cstdio> | |
12 | #include <cstdlib> | |
13 | #include <cstring> | |
14 | ||
970ed795 | 15 | template <class T> |
3abe9331 | 16 | class Item { |
970ed795 | 17 | Item(const Item<T> & other); // not implemented |
3abe9331 | 18 | Item<T> & operator=(const Item<T> & rhs); // not implemented |
970ed795 EL |
19 | // Default destructor is used |
20 | public: | |
21 | Item(); | |
22 | ||
23 | T Data; | |
24 | Item * Next; // pointer to the next element | |
25 | Item * Prev; // pointer to the previous element | |
26 | }; | |
27 | ||
28 | template <class T> | |
29 | Item<T>::Item() | |
30 | : Data(T()) | |
31 | , Next(NULL) | |
3abe9331 | 32 | , Prev(NULL) { |
33 | } | |
970ed795 EL |
34 | |
35 | template <class T> | |
3abe9331 | 36 | class List { |
970ed795 EL |
37 | private: |
38 | ||
39 | /** | |
40 | * Number of nodes in the list | |
41 | */ | |
42 | size_t Size; | |
43 | ||
44 | /** | |
45 | * The initial node in the list | |
46 | */ | |
47 | Item<T> * First; | |
48 | ||
49 | /** | |
50 | * The final node in the list | |
51 | */ | |
52 | Item<T> * Last; | |
53 | ||
54 | /** | |
55 | * Memory free up | |
56 | */ | |
57 | void freeMemory(); | |
58 | ||
59 | public: | |
60 | List(); | |
61 | List(const List<T> & other); | |
3abe9331 | 62 | List<T> & operator=(const List<T> & other); |
970ed795 EL |
63 | ~List(); |
64 | ||
65 | typedef Item<T> * iterator; | |
66 | ||
67 | /** | |
68 | * Returns the size of the list | |
69 | */ | |
3abe9331 | 70 | size_t length() const { |
71 | return Size; | |
72 | } | |
73 | ||
74 | size_t size() const { | |
75 | return Size; | |
76 | } | |
970ed795 EL |
77 | |
78 | /** | |
79 | * True if List is empty, false otherwise | |
80 | */ | |
3abe9331 | 81 | bool empty() const { |
82 | return Size == 0; | |
83 | } | |
970ed795 EL |
84 | |
85 | /** | |
86 | * Clear list | |
87 | */ | |
88 | void clear(); | |
89 | ||
90 | /** | |
91 | * Sort the list using the < operator. | |
92 | * To be used when T is a type with operator< | |
93 | */ | |
94 | void sort(); | |
95 | ||
96 | /** | |
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. | |
99 | */ | |
100 | void sort(bool (*comparison_function)(const T lhs, const T rhs)); | |
101 | ||
102 | /** | |
103 | * Returns with a pointer to the begin of the list | |
104 | */ | |
3abe9331 | 105 | Item<T> * begin() const { |
106 | return First; | |
107 | } | |
970ed795 EL |
108 | |
109 | /** | |
110 | * Returns with a pointer to the end of the list | |
111 | */ | |
3abe9331 | 112 | Item<T> * end() const { |
113 | return Last; | |
114 | } | |
970ed795 EL |
115 | |
116 | /** | |
117 | * Returns with reference to the first element | |
118 | */ | |
3abe9331 | 119 | T & front() { |
120 | return First->Data; | |
121 | } | |
122 | ||
123 | const T & front() const { | |
124 | return First->Data; | |
125 | } | |
970ed795 EL |
126 | |
127 | /** | |
128 | * Returns with reference to the last element | |
129 | */ | |
3abe9331 | 130 | T & back() { |
131 | return Last->Data; | |
132 | } | |
133 | ||
134 | const T & back() const { | |
135 | return Last->Data; | |
136 | } | |
970ed795 EL |
137 | |
138 | /** | |
139 | * Pushes element at the end of the list | |
140 | */ | |
141 | void push_back(const T & element); | |
142 | ||
3abe9331 | 143 | /** |
144 | * Pushes element at the front of the list | |
145 | */ | |
146 | void push_front(const T & element); | |
147 | ||
970ed795 EL |
148 | /** |
149 | * Removes the final element in the list | |
150 | */ | |
151 | void pop_back(); | |
152 | ||
153 | /** | |
154 | * Removes the node from the list | |
155 | */ | |
156 | void remove(iterator& node); | |
970ed795 | 157 | |
3abe9331 | 158 | /** |
159 | * Removes duplicated elements from the list. | |
160 | */ | |
161 | void remove_dups(); | |
162 | }; | |
970ed795 EL |
163 | |
164 | template <class T> | |
165 | List<T>::List() | |
166 | : Size(0) | |
167 | , First(NULL) | |
3abe9331 | 168 | , Last(NULL) { |
169 | } | |
970ed795 EL |
170 | |
171 | template <class T> | |
172 | List<T>::List(const List<T> & other) | |
173 | : Size(0) | |
174 | , First(NULL) | |
3abe9331 | 175 | , Last(NULL) { |
970ed795 EL |
176 | if (other.empty()) return; |
177 | ||
178 | Item<T> * CurrentNode = other.First; | |
179 | Item<T> * MyFinalNode = NULL; | |
180 | ||
3abe9331 | 181 | while (CurrentNode != NULL) { |
182 | if (MyFinalNode == NULL) // first element | |
970ed795 EL |
183 | { |
184 | MyFinalNode = new Item<T>; | |
185 | MyFinalNode->Data = CurrentNode->Data; | |
186 | MyFinalNode->Next = NULL; | |
187 | MyFinalNode->Prev = NULL; | |
188 | First = MyFinalNode; | |
189 | Last = MyFinalNode; | |
3abe9331 | 190 | } else { |
970ed795 EL |
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; | |
196 | Last = MyFinalNode; | |
197 | } | |
198 | ||
199 | CurrentNode = CurrentNode->Next; | |
200 | ++Size; | |
201 | } | |
202 | } | |
203 | ||
204 | template <class T> | |
3abe9331 | 205 | List<T>::~List() { |
970ed795 EL |
206 | freeMemory(); |
207 | } | |
208 | ||
209 | template <class T> | |
3abe9331 | 210 | List<T> & List<T>::operator=(const List<T> & other) { |
970ed795 EL |
211 | freeMemory(); |
212 | ||
213 | if (other.empty()) return *this; | |
214 | ||
215 | Item<T> * CurrentNode = other.First; | |
216 | Item<T> * MyFinalNode = NULL; | |
217 | ||
3abe9331 | 218 | while (CurrentNode != NULL) { |
219 | if (MyFinalNode == NULL) { | |
970ed795 EL |
220 | MyFinalNode = new Item<T>; |
221 | MyFinalNode->Data = CurrentNode->Data; | |
222 | MyFinalNode->Next = NULL; | |
223 | MyFinalNode->Prev = NULL; | |
224 | First = MyFinalNode; | |
225 | Last = MyFinalNode; | |
3abe9331 | 226 | } else { |
970ed795 EL |
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; | |
232 | Last = MyFinalNode; | |
233 | } | |
234 | ||
235 | CurrentNode = CurrentNode->Next; | |
236 | ++Size; | |
237 | } | |
238 | ||
239 | return *this; | |
240 | } | |
241 | ||
242 | template <class T> | |
3abe9331 | 243 | void List<T>::freeMemory() { |
244 | if (Size > 0) // if list is not empty | |
970ed795 EL |
245 | { |
246 | Item<T> * CurrentNode = First; | |
247 | Item<T> * NodeForDelete = NULL; | |
248 | ||
3abe9331 | 249 | for (size_t i = 0; i != Size; ++i) { |
970ed795 EL |
250 | NodeForDelete = CurrentNode; |
251 | CurrentNode = CurrentNode->Next; | |
252 | delete NodeForDelete; | |
253 | } | |
254 | ||
255 | Size = 0; | |
256 | } | |
257 | ||
258 | First = NULL; | |
259 | Last = NULL; | |
260 | } | |
261 | ||
262 | template <class T> | |
3abe9331 | 263 | void List<T>::remove(iterator& node) { |
970ed795 EL |
264 | if (Size == 0) return; |
265 | ||
266 | if (node == NULL) return; | |
267 | ||
3abe9331 | 268 | if (node->Prev == NULL) // if this node was the first element in the list |
970ed795 EL |
269 | { |
270 | First = node->Next; | |
3abe9331 | 271 | } else { |
970ed795 EL |
272 | node->Prev->Next = node->Next; |
273 | } | |
274 | ||
3abe9331 | 275 | if (node->Next == NULL) // if this node was the last element in the list |
970ed795 EL |
276 | { |
277 | Last = node->Prev; | |
3abe9331 | 278 | } else { |
970ed795 EL |
279 | node->Next->Prev = node->Prev; |
280 | } | |
281 | ||
282 | delete(node); | |
283 | node = 0; | |
284 | ||
285 | --Size; | |
286 | } | |
287 | ||
288 | template <class T> | |
3abe9331 | 289 | void List<T>::clear() { |
970ed795 EL |
290 | freeMemory(); |
291 | } | |
292 | ||
293 | template <class T> | |
3abe9331 | 294 | void List<T>::sort() { |
970ed795 EL |
295 | if (Size <= 1) return; |
296 | ||
297 | // Selection sort | |
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; | |
302 | } | |
303 | ||
304 | if (mini) { // swap! | |
305 | T temp(mini->Data); | |
306 | mini->Data = left->Data; | |
307 | left->Data = temp; | |
308 | } | |
309 | } | |
310 | } | |
311 | ||
312 | template <class T> | |
3abe9331 | 313 | void List<T>::sort(bool (*comparison_function)(const T lhs, const T rhs)) { |
970ed795 EL |
314 | if (Size <= 1) return; |
315 | ||
316 | // Selection sort | |
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) { | |
3abe9331 | 320 | if (comparison_function(curr->Data, mini->Data)) mini = curr; |
970ed795 EL |
321 | } |
322 | ||
323 | if (mini) { // swap! | |
324 | T temp(mini->Data); | |
325 | mini->Data = left->Data; | |
326 | left->Data = temp; | |
327 | } | |
328 | } | |
329 | } | |
330 | ||
331 | template <class T> | |
3abe9331 | 332 | void List<T>::push_back(const T & element) { |
970ed795 EL |
333 | Item<T> * NewNode = new Item<T>; |
334 | NewNode->Data = element; | |
335 | NewNode->Next = NULL; | |
336 | ||
3abe9331 | 337 | if (Size == 0) // if list is empty |
970ed795 EL |
338 | { |
339 | NewNode->Prev = NULL; | |
340 | First = NewNode; | |
341 | Last = NewNode; | |
3abe9331 | 342 | } else { |
970ed795 EL |
343 | NewNode->Prev = Last; |
344 | Last->Next = NewNode; | |
345 | Last = NewNode; | |
346 | } | |
347 | ||
348 | ++Size; | |
349 | } | |
350 | ||
351 | template <class T> | |
3abe9331 | 352 | void List<T>::push_front(const T & element) { |
353 | Item<T> * NewNode = new Item<T>; | |
354 | NewNode->Data = element; | |
355 | NewNode->Prev = NULL; | |
970ed795 | 356 | |
3abe9331 | 357 | if (Size == 0) // if list is empty |
970ed795 | 358 | { |
3abe9331 | 359 | NewNode->Next = NULL; |
360 | First = NewNode; | |
361 | Last = NewNode; | |
362 | } else { | |
363 | NewNode->Next = First; | |
364 | First->Prev = NewNode; | |
365 | First = NewNode; | |
366 | } | |
367 | ||
368 | ++Size; | |
369 | } | |
370 | ||
371 | template <class T> | |
372 | void List<T>::pop_back() { | |
373 | Item<T> * LastNode = Last; | |
374 | ||
375 | if (Size == 1) { | |
970ed795 EL |
376 | First = NULL; |
377 | Last = NULL; | |
378 | delete(LastNode); | |
379 | --Size; | |
3abe9331 | 380 | } else if (Size > 1) { |
970ed795 EL |
381 | Last->Prev->Next = NULL; |
382 | Last = Last->Prev; | |
383 | delete(LastNode); | |
384 | --Size; | |
385 | } | |
386 | } | |
387 | ||
3abe9331 | 388 | template <class T> |
389 | void List<T>::remove_dups() { | |
390 | Item<T>* ptr1 = First, *ptr2, *dup; | |
391 | ||
392 | while (ptr1 != NULL && ptr1->Next != NULL) { | |
393 | ptr2 = ptr1; | |
394 | while (ptr2->Next != NULL) { | |
395 | if (ptr1->Data == ptr2->Next->Data) { | |
396 | dup = ptr2->Next; | |
397 | ptr2->Next = ptr2->Next->Next; | |
398 | //If the last element is a duplicate | |
399 | if (ptr2->Next == NULL) { | |
400 | Last = ptr2; | |
401 | } else { | |
402 | ptr2->Next->Prev = ptr2; | |
403 | } | |
404 | delete(dup); | |
405 | Size--; | |
406 | } else { | |
407 | ptr2 = ptr2->Next; | |
408 | } | |
409 | } | |
410 | ptr1 = ptr1->Next; | |
411 | } | |
412 | ||
413 | } | |
414 | ||
970ed795 | 415 | #endif /* LIST_HH_ */ |