xsdconvert/List.hh

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