xsdconvert/List.hh

   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 ///////////////////////////////////////////////////////////////////////////////
   8 #ifndef LIST_HH_
   9 #define LIST_HH_
  10
  11 #include <cstdio>
  12 #include <cstdlib>
  13 #include <cstring>
  14
  15 template <class T>
  16 class Item {
  17   Item(const Item<T> & other); // not implemented
  18   Item<T> & operator=(const Item<T> & rhs); // not implemented
  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)
  32 , Prev(NULL) {
  33 }
  34
  35 template <class T>
  36 class List {
  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);
  62   List<T> & operator=(const List<T> & other);
  63   ~List();
  64
  65   typedef Item<T> * iterator;
  66
  67   /**
  68    * Returns the size of the list
  69    */
  70   size_t length() const {
  71     return Size;
  72   }
  73
  74   size_t size() const {
  75     return Size;
  76   }
  77
  78   /**
  79    * True if List is empty, false otherwise
  80    */
  81   bool empty() const {
  82     return Size == 0;
  83   }
  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    */
 105   Item<T> * begin() const {
 106     return First;
 107   }
 108
 109   /**
 110    * Returns with a pointer to the end of the list
 111    */
 112   Item<T> * end() const {
 113     return Last;
 114   }
 115
 116   /**
 117    * Returns with reference to the first element
 118    */
 119   T & front() {
 120     return First->Data;
 121   }
 122
 123   const T & front() const {
 124     return First->Data;
 125   }
 126
 127   /**
 128    * Returns with reference to the last element
 129    */
 130   T & back() {
 131     return Last->Data;
 132   }
 133
 134   const T & back() const {
 135     return Last->Data;
 136   }
 137
 138   /**
 139    * Pushes element at the end of the list
 140    */
 141   void push_back(const T & element);
 142
 143   /**
 144    * Pushes element at the front of the list
 145    */
 146   void push_front(const T & element);
 147
 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);
 157
 158   /**
 159    * Removes duplicated elements from the list.
 160    */
 161   void remove_dups();
 162 };
 163
 164 template <class T>
 165 List<T>::List()
 166 : Size(0)
 167 , First(NULL)
 168 , Last(NULL) {
 169 }
 170
 171 template <class T>
 172 List<T>::List(const List<T> & other)
 173 : Size(0)
 174 , First(NULL)
 175 , Last(NULL) {
 176   if (other.empty()) return;
 177
 178   Item<T> * CurrentNode = other.First;
 179   Item<T> * MyFinalNode = NULL;
 180
 181   while (CurrentNode != NULL) {
 182     if (MyFinalNode == NULL) // first element
 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;
 190     } else {
 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>
 205 List<T>::~List() {
 206   freeMemory();
 207 }
 208
 209 template <class T>
 210 List<T> & List<T>::operator=(const List<T> & other) {
 211   freeMemory();
 212
 213   if (other.empty()) return *this;
 214
 215   Item<T> * CurrentNode = other.First;
 216   Item<T> * MyFinalNode = NULL;
 217
 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;
 224       First = MyFinalNode;
 225       Last = MyFinalNode;
 226     } else {
 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>
 243 void List<T>::freeMemory() {
 244   if (Size > 0) // if list is not empty
 245   {
 246     Item<T> * CurrentNode = First;
 247     Item<T> * NodeForDelete = NULL;
 248
 249     for (size_t i = 0; i != Size; ++i) {
 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>
 263 void List<T>::remove(iterator& node) {
 264   if (Size == 0) return;
 265
 266   if (node == NULL) return;
 267
 268   if (node->Prev == NULL) // if this node was the first element in the list
 269   {
 270     First = node->Next;
 271   } else {
 272     node->Prev->Next = node->Next;
 273   }
 274
 275   if (node->Next == NULL) // if this node was the last element in the list
 276   {
 277     Last = node->Prev;
 278   } else {
 279     node->Next->Prev = node->Prev;
 280   }
 281
 282   delete(node);
 283   node = 0;
 284
 285   --Size;
 286 }
 287
 288 template <class T>
 289 void List<T>::clear() {
 290   freeMemory();
 291 }
 292
 293 template <class T>
 294 void List<T>::sort() {
 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>
 313 void List<T>::sort(bool (*comparison_function)(const T lhs, const T rhs)) {
 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) {
 320       if (comparison_function(curr->Data, mini->Data)) mini = curr;
 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>
 332 void List<T>::push_back(const T & element) {
 333   Item<T> * NewNode = new Item<T>;
 334   NewNode->Data = element;
 335   NewNode->Next = NULL;
 336
 337   if (Size == 0) // if list is empty
 338   {
 339     NewNode->Prev = NULL;
 340     First = NewNode;
 341     Last = NewNode;
 342   } else {
 343     NewNode->Prev = Last;
 344     Last->Next = NewNode;
 345     Last = NewNode;
 346   }
 347
 348   ++Size;
 349 }
 350
 351 template <class T>
 352 void List<T>::push_front(const T & element) {
 353   Item<T> * NewNode = new Item<T>;
 354   NewNode->Data = element;
 355   NewNode->Prev = NULL;
 356
 357   if (Size == 0) // if list is empty
 358   {
 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) {
 376     First = NULL;
 377     Last = NULL;
 378     delete(LastNode);
 379     --Size;
 380   } else if (Size > 1) {
 381     Last->Prev->Next = NULL;
 382     Last = Last->Prev;
 383     delete(LastNode);
 384     --Size;
 385   }
 386 }
 387
 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
 415 #endif /* LIST_HH_ */