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 3:
   6  * Lista 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* _current;
  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     DLList_have_more(), DLList_prev(), DLList_begin(), DLList_next()
 121          * \pre     La DLList debe estar \ref DLList_new "creada" correctamente.
 122          */
 123         void* end(void);
 124
 125         /**
 126          * Indica si se puede obtener otro elemento de la lista.
 127          *
 128          * \return true si se puede obtener otro elemento, false si no.
 129          * \see    begin(), end(), prev(), next()
 130          */
 131         bool have_more(void);
 132
 133         /**
 134          * Obtiene el elemento actual.
 135          *
 136          * \return Elemento actual o NULL si se terminó de recorrer o está vacía.
 137          * \see   prev(), next(), have_more()
 138          */
 139         void* current(void);
 140
 141         /**
 142          * Obtiene el próximo elemento.
 143          *
 144          * \return  Siguiente elemento o NULL si es el último.
 145          * \see     begin(), have_more(), current(), prev()
 146          */
 147         void* next(void);
 148
 149         /**
 150          * Obtiene el elemento anterior.
 151          *
 152          * \return  Elemento anterior o NULL si es el primero.
 153          * \see     begin(), have_more(), current(), next()
 154          */
 155         void* prev(void);
 156
 157         /**
 158          * Agrega un elemento al inicio.
 159          *
 160          * \param   data Elemento a agregar.
 161          *
 162          * \return  true si se agregó, false si no hay más memoria.
 163          * \see     push(), pop(), unshift()
 164          */
 165         bool unshift(void* data);
 166
 167         /**
 168          * Agrega un elemento al final.
 169          *
 170          * \param   data Elemento a agregar.
 171          *
 172          * \return  true si se agregó, false si no hay más memoria.
 173          * \see     pop(), shift(), unshift()
 174          */
 175         bool push(void* data);
 176
 177         /**
 178          * Saca el primer elemento.
 179          * Elimina el primer elemento devolviendo su contenido.
 180          * Ejemplo:
 181          * \code
 182          * DLList list;
 183          * char*  data;
 184          * ...
 185          * while (!list.empty()) {
 186          *      data = list.shift();
 187          *      printf("El elemento actual es '%s'.\\n", data);
 188          * }
 189          * \endcode
 190          *
 191          * \return  Primer elemento o NULL si está vacía.
 192          * \see     empty(), pop(), remove_current()
 193          * \warning Es necesario comprobar antes si está vacía, ya que puede
 194          *          devolver NULL también si el elemento de la lista es NULL.
 195          */
 196         void* shift(void);
 197
 198         /**
 199          * Saca el último elemento.
 200          * Elimina el último elemento devolviendo su contenido.
 201          * Ejemplo:
 202          * \code
 203          * DLList list;
 204          * char*   data;
 205          * ...
 206          * while (!list.empty()) {
 207          *      data = list.pop();
 208          *      printf("El elemento actual es '%s'.\\n", data);
 209          * }
 210          * \endcode
 211          *
 212          * \return  Último elemento o NULL si está vacía.
 213          * \see     empty(), shift(), remove_current()
 214          * \warning Es necesario comprobar antes si está vacía, ya que puede
 215          *          devolver NULL también si el elemento de la lista es NULL.
 216          */
 217         void* pop(void);
 218
 219         /**
 220          * Elimina el elemento actual.
 221          * Elimina el elemento actual devolviendo su contenido.
 222          *
 223          * \return  Elemento actual o NULL si no hay más elementos.
 224          * \see     empty(), current(), have_more()
 225          * \warning Es necesario comprobar antes si está vacía, ya que puede
 226          *          devolver NULL también si el elemento de la lista es NULL.
 227          */
 228         void* remove_current(void);
 229
 230 };
 231
 232 #endif /* DLLIST_H */