dllist.h

   1 /* vim: set et sts=4 sw=4 fdm=indent fdl=1 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 /// Nodo de la lista doblemente enlazada.
  23 struct DLListNode {
  24
  25     /// Puntero al nodo anterior.
  26     DLListNode* prev;
  27
  28     /// Datos almacenados en el nodo.
  29     void* data;
  30
  31     /// Puntero al próximo nodo.
  32     DLListNode* next;
  33
  34     /// Constructor.
  35     DLListNode(DLListNode* prev = NULL, void* data = NULL,
  36             DLListNode* next = NULL): prev(prev), data(data), next(next) {}
  37
  38 };
  39
  40 /// Lista doblemente enlazada.
  41 class DLList {
  42
  43     protected:
  44
  45         /// Puntero al primer nodo.
  46         DLListNode* _first;
  47
  48         /// Puntero al nodo actual.
  49         DLListNode* _current;
  50
  51         /// Puntero al último nodo.
  52         DLListNode* _last;
  53
  54     public:
  55
  56         /// Crea una nueva lista.
  57         DLList(void);
  58
  59         /// Libera la memoria ocupada por una lista.
  60         virtual ~DLList(void);
  61
  62         /**
  63          * Indica si está vacía.
  64          *
  65          * \return true si está vacía, false si no.
  66          */
  67         bool empty(void);
  68
  69         /**
  70          * Apunta al primer elemento, devolviendolo.
  71          * Hace que el elemento actual sea el primero y devuelve su valor.
  72          * Si está vacía, devuelve NULL.
  73          * Siempre que se quiera recorrer la lista de izquierda a derecha
  74          * debería usarse esta función primero. Por ejemplo:
  75          * \code
  76          * DLList list;
  77          * char*  data;
  78          * ...
  79          * for (data = list.begin(); list.have_more(); data = list.next()) {
  80          *      printf("El elemento actual es '%s'.\\n", data);
  81          * }
  82          * \endcode
  83          *
  84          * \return  Primer elemento o NULL si está vacía.
  85          * \see     have_more(), next(), end(), prev()
  86          */
  87         void* begin(void);
  88
  89         /**
  90          * Apunta al último elemento, devolviendolo.
  91          * Hace que el elemento actual sea el último y devuelve su valor.
  92          * Si está vacía, devuelve NULL.
  93          * Siempre que se quiera recorrer la lista de derecha a izquierda
  94          * debería usarse esta función primero. Por ejemplo:
  95          * \code
  96          * DLList list;
  97          * char*  data;
  98          * ...
  99          * for (data = list.end(); list.have_more(); data = list.prev()) {
 100          *      printf("El elemento actual es '%s'.\\n", data);
 101          * }
 102          * \endcode
 103          *
 104          * \return  Último elemento o NULL si está vacía.
 105          * \see     DLList_have_more(), DLList_prev(), DLList_begin(), DLList_next()
 106          * \pre     La DLList debe estar \ref DLList_new "creada" correctamente.
 107          */
 108         void* end(void);
 109
 110         /**
 111          * Indica si se puede obtener otro elemento de la lista.
 112          *
 113          * \return true si se puede obtener otro elemento, false si no.
 114          * \see    begin(), end(), prev(), next()
 115          */
 116         bool have_more(void);
 117
 118         /**
 119          * Obtiene el elemento actual.
 120          *
 121          * \return Elemento actual o NULL si se terminó de recorrer o está vacía.
 122          * \see   prev(), next(), have_more()
 123          */
 124         void* current(void);
 125
 126         /**
 127          * Obtiene el próximo elemento.
 128          *
 129          * \return  Siguiente elemento o NULL si es el último.
 130          * \see     begin(), have_more(), current(), prev()
 131          */
 132         void* next(void);
 133
 134         /**
 135          * Obtiene el elemento anterior.
 136          *
 137          * \return  Elemento anterior o NULL si es el primero.
 138          * \see     begin(), have_more(), current(), next()
 139          */
 140         void* prev(void);
 141
 142         /**
 143          * Agrega un elemento al inicio.
 144          *
 145          * \param   data Elemento a agregar.
 146          *
 147          * \return  true si se agregó, false si no hay más memoria.
 148          * \see     push(), pop(), unshift()
 149          */
 150         bool unshift(void* data);
 151
 152         /**
 153          * Agrega un elemento al final.
 154          *
 155          * \param   data Elemento a agregar.
 156          *
 157          * \return  true si se agregó, false si no hay más memoria.
 158          * \see     pop(), shift(), unshift()
 159          */
 160         bool push(void* data);
 161
 162         /**
 163          * Saca el primer elemento.
 164          * Elimina el primer elemento devolviendo su contenido.
 165          * Ejemplo:
 166          * \code
 167          * DLList list;
 168          * char*  data;
 169          * ...
 170          * while (!list.empty()) {
 171          *      data = list.shift();
 172          *      printf("El elemento actual es '%s'.\\n", data);
 173          * }
 174          * \endcode
 175          *
 176          * \return  Primer elemento o NULL si está vacía.
 177          * \see     empty(), pop(), remove_current()
 178          * \warning Es necesario comprobar antes si está vacía, ya que puede
 179          *          devolver NULL también si el elemento de la lista es NULL.
 180          */
 181         void* shift(void);
 182
 183         /**
 184          * Saca el último elemento.
 185          * Elimina el último elemento devolviendo su contenido.
 186          * Ejemplo:
 187          * \code
 188          * DLList list;
 189          * char*   data;
 190          * ...
 191          * while (!list.empty()) {
 192          *      data = list.pop();
 193          *      printf("El elemento actual es '%s'.\\n", data);
 194          * }
 195          * \endcode
 196          *
 197          * \return  Último elemento o NULL si está vacía.
 198          * \see     empty(), shift(), remove_current()
 199          * \warning Es necesario comprobar antes si está vacía, ya que puede
 200          *          devolver NULL también si el elemento de la lista es NULL.
 201          */
 202         void* pop(void);
 203
 204         /**
 205          * Elimina el elemento actual.
 206          * Elimina el elemento actual devolviendo su contenido.
 207          *
 208          * \return  Elemento actual o NULL si no hay más elementos.
 209          * \see     empty(), current(), have_more()
 210          * \warning Es necesario comprobar antes si está vacía, ya que puede
 211          *          devolver NULL también si el elemento de la lista es NULL.
 212          */
 213         void* remove_current(void);
 214
 215 };
 216
 217 #endif /* DLLIST_H */