dllist.h

   1 /* vim: set et sts=4 sw=4 fdm=marker fmr={,} fdn=1 fo+=t tw=80:
   2  *
   3  * Taller de Programación (75.42).
   4  *
   5  * Ejercicio Número 5:
   6  * Graficador de figuras.
   7  *
   8  * Copyleft 2003 - Leandro Lucarella <llucare@fi.uba.ar>
   9  * Puede copiar, modificar y distribuir este programa bajo los términos de
  10  * la licencia GPL (http://www.gnu.org/).
  11  *
  12  * Creado: Wed Sep 17 21:07:54 ART 2003
  13  *
  14  * $Id$
  15  */
  16
  17 #ifndef DLLIST_H
  18 #define DLLIST_H
  19
  20 #include <cstdlib>
  21
  22 #ifdef DEBUG
  23 #   include <iostream>
  24 #endif
  25
  26 /// Nodo de la lista doblemente enlazada.
  27 struct DLListNode {
  28
  29     /// Puntero al nodo anterior.
  30     DLListNode* prev;
  31
  32     /// Datos almacenados en el nodo.
  33     void* data;
  34
  35     /// Puntero al próximo nodo.
  36     DLListNode* next;
  37
  38     /// Constructor.
  39     DLListNode(DLListNode* prev = NULL, void* data = NULL,
  40             DLListNode* next = NULL): prev(prev), data(data), next(next) {
  41 #ifdef DEBUG
  42         std::cerr << "En constructor de DLListNode." << std::endl;
  43 #endif
  44     }
  45
  46     /// Destructor.
  47     virtual ~DLListNode(void) {
  48 #ifdef DEBUG
  49         std::cerr << "En destructor de DLListNode." << std::endl;
  50 #endif
  51     }
  52
  53 };
  54
  55 /// Lista doblemente enlazada.
  56 class DLList {
  57
  58     protected:
  59
  60         /// Puntero al primer nodo.
  61         DLListNode* first;
  62
  63         /// Puntero al nodo actual.
  64         DLListNode* curr;
  65
  66         /// Puntero al último nodo.
  67         DLListNode* last;
  68
  69     public:
  70
  71         /// Crea una nueva lista.
  72         DLList(void);
  73
  74         /// Libera la memoria ocupada por una lista.
  75         virtual ~DLList(void);
  76
  77         /**
  78          * Indica si está vacía.
  79          *
  80          * \return true si está vacía, false si no.
  81          */
  82         bool empty(void);
  83
  84         /**
  85          * Apunta al primer elemento, devolviendolo.
  86          * Hace que el elemento actual sea el primero y devuelve su valor.
  87          * Si está vacía, devuelve NULL.
  88          * Siempre que se quiera recorrer la lista de izquierda a derecha
  89          * debería usarse esta función primero. Por ejemplo:
  90          * \code
  91          * DLList list;
  92          * char*  data;
  93          * ...
  94          * for (data = list.begin(); list.have_more(); data = list.next()) {
  95          *      printf("El elemento actual es '%s'.\\n", data);
  96          * }
  97          * \endcode
  98          *
  99          * \return  Primer elemento o NULL si está vacía.
 100          * \see     have_more(), next(), end(), prev()
 101          */
 102         void* begin(void);
 103
 104         /**
 105          * Apunta al último elemento, devolviendolo.
 106          * Hace que el elemento actual sea el último y devuelve su valor.
 107          * Si está vacía, devuelve NULL.
 108          * Siempre que se quiera recorrer la lista de derecha a izquierda
 109          * debería usarse esta función primero. Por ejemplo:
 110          * \code
 111          * DLList list;
 112          * char*  data;
 113          * ...
 114          * for (data = list.end(); list.have_more(); data = list.prev()) {
 115          *      printf("El elemento actual es '%s'.\\n", data);
 116          * }
 117          * \endcode
 118          *
 119          * \return  Último elemento o NULL si está vacía.
 120          * \see     have_more(), prev(), begin(), next()
 121          */
 122         void* end(void);
 123
 124         /**
 125          * Indica si se puede obtener otro elemento de la lista.
 126          *
 127          * \return true si se puede obtener otro elemento, false si no.
 128          * \see    begin(), end(), prev(), next()
 129          */
 130         bool have_more(void);
 131
 132         /**
 133          * Obtiene el elemento actual.
 134          *
 135          * \return Elemento actual o NULL si se terminó de recorrer o está vacía.
 136          * \see   prev(), next(), have_more()
 137          */
 138         void* current(void);
 139
 140         /**
 141          * Obtiene el próximo elemento.
 142          *
 143          * \return  Siguiente elemento o NULL si es el último.
 144          * \see     begin(), have_more(), current(), prev()
 145          */
 146         void* next(void);
 147
 148         /**
 149          * Obtiene el elemento anterior.
 150          *
 151          * \return  Elemento anterior o NULL si es el primero.
 152          * \see     begin(), have_more(), current(), next()
 153          */
 154         void* prev(void);
 155
 156         /**
 157          * Agrega un elemento al inicio.
 158          *
 159          * \param   data Elemento a agregar.
 160          *
 161          * \return  true si se agregó, false si no hay más memoria.
 162          * \see     push(), pop(), unshift()
 163          */
 164         bool unshift(void* data);
 165
 166         /**
 167          * Agrega un elemento al final.
 168          *
 169          * \param   data Elemento a agregar.
 170          *
 171          * \return  true si se agregó, false si no hay más memoria.
 172          * \see     pop(), shift(), unshift()
 173          */
 174         bool push(void* data);
 175
 176         /**
 177          * Saca el primer elemento.
 178          * Elimina el primer elemento devolviendo su contenido.
 179          * Ejemplo:
 180          * \code
 181          * DLList list;
 182          * char*  data;
 183          * ...
 184          * while (!list.empty()) {
 185          *      data = list.shift();
 186          *      printf("El elemento actual es '%s'.\\n", data);
 187          * }
 188          * \endcode
 189          *
 190          * \return  Primer elemento o NULL si está vacía.
 191          * \see     empty(), pop(), remove_current()
 192          * \warning Es necesario comprobar antes si está vacía, ya que puede
 193          *          devolver NULL también si el elemento de la lista es NULL.
 194          */
 195         void* shift(void);
 196
 197         /**
 198          * Saca el último elemento.
 199          * Elimina el último elemento devolviendo su contenido.
 200          * Ejemplo:
 201          * \code
 202          * DLList list;
 203          * char*   data;
 204          * ...
 205          * while (!list.empty()) {
 206          *      data = list.pop();
 207          *      printf("El elemento actual es '%s'.\\n", data);
 208          * }
 209          * \endcode
 210          *
 211          * \return  Último elemento o NULL si está vacía.
 212          * \see     empty(), shift(), remove_current()
 213          * \warning Es necesario comprobar antes si está vacía, ya que puede
 214          *          devolver NULL también si el elemento de la lista es NULL.
 215          */
 216         void* pop(void);
 217
 218         /**
 219          * Elimina el elemento actual.
 220          * Elimina el elemento actual devolviendo su contenido.
 221          *
 222          * \return  Elemento actual o NULL si no hay más elementos.
 223          * \see     empty(), current(), have_more()
 224          * \warning Es necesario comprobar antes si está vacía, ya que puede
 225          *          devolver NULL también si el elemento de la lista es NULL.
 226          */
 227         void* remove_current(void);
 228
 229 };
 230
 231 #endif /* DLLIST_H */