list.cc

   1 /*-----------------------------------------------------------------------------
   2   List class
   3   Written by Francois Fleuret <francois.fleuret@inria.fr>
   4 -----------------------------------------------------------------------------*/
   5
   6 #ifndef LIST_H
   7 #define LIST_H
   8
   9 #include <stdio.h>
  10
  11 //-----------------------------------------------------------------------------
  12
  13 template <class T>
  14 class NodeList
  15 {
  16 public:
  17   T body;
  18   NodeList<T> *next;
  19 };
  20
  21 template <class T>
  22 class List
  23 {
  24 public:
  25   NodeList<T> *first;
  26
  27   List();
  28   ~List();
  29   void Insert(T t);
  30   NodeList<T> *DeleteNext(NodeList<T> *node);
  31   void Remove(T t);
  32   void Reverse();
  33   int Lenght();
  34 };
  35
  36 //-----------------------------------------------------------------------------
  37
  38 template<class T>
  39 List<T>::List() { first = NULL; }
  40
  41 template<class T>
  42 List<T>::~List()
  43 {
  44   NodeList<T> *node, *suivant;
  45   for(node=first; node != NULL;)
  46     {
  47       suivant = node->next;
  48       delete node;
  49       node = suivant;
  50     };
  51 }
  52
  53 template<class T>
  54 void List<T>::Insert(T t)
  55 {
  56   NodeList<T> *node;
  57   node = new NodeList<T>;
  58   node->body = t;
  59   node->next = first;
  60   first = node;
  61 }
  62
  63 template<class T>
  64 NodeList<T> *List<T>::DeleteNext(NodeList<T> *node)
  65 {
  66   NodeList<T> *next;
  67   if(node == 0)
  68     {
  69       next = first;
  70       delete first;
  71     }
  72   else
  73     {
  74       next = node->next;
  75       delete node;
  76     }
  77   return next;
  78 }
  79
  80 template<class T>
  81 void List<T>::Remove(T t)
  82 {
  83   NodeList<T> *node, *pred, *next;
  84   node = first;
  85   pred = NULL;
  86   while(node != NULL)
  87     {
  88       if(node->body == t)
  89         {
  90           next = node->next;
  91           if(pred == NULL) first = next;
  92           else pred->next = next;
  93           delete node;
  94           node = next;
  95         }
  96       else
  97         {
  98           pred = node;
  99           node = node->next;
 100         };
 101     };
 102 }
 103
 104 template<class T>
 105 void List<T>::Reverse()
 106 {
 107   NodeList<T> *node, *next, *pred;
 108   node = first;
 109   pred = NULL;
 110   while(node != NULL)
 111     {
 112       next = node->next;
 113       node->next = pred;
 114       pred = node;
 115       node = next;
 116     };
 117   first = pred;
 118 };
 119
 120 template<class T>
 121 int List<T>::Lenght()
 122 {
 123   NodeList<T> *node;
 124   int l;
 125   l = 0;
 126   for(node=first; node != NULL; node = node->next) l++;
 127   return l;
 128 }
 129
 130 //-----------------------------------------------------------------------------
 131
 132 #endif
 133
 134 //-----------------------------------------------------------------------------