Primera versión moderadamente probada de la lista.

diff --git a/dllist.c b/dllist.c
index ed2b62ca385dc3e3f6d0805f6879d4dd42cf1dba..629f7f5733d23753385fdac162470a482bdd5201 100644 (file)
--- a/dllist.c
+++ b/dllist.c
@@ -1,4 +1,4 @@
-/* vim: set et sts=4 sw=4 fdm=indent fdl=1 fdn=1 fo+=t tw=80:
+/* vim: set et sts=4 sw=4 fdm=indent fdl=1 fdn=0 fo+=t tw=80:
  *
  * Taller de Programación (75.42).
  *
@@ -18,36 +18,70 @@
 #include <stdlib.h>
 
 bool DLList_init(DLList* list) {
-    list = (DLList*)malloc(sizeof(DLList));
+    /* Aloco memoria para la lista. */
+    /*list = (DLList*)malloc(sizeof(DLList));*/
+    /* Si la obtuve, inicializo todo a NULL y devuelvo TRUE. */
     if (list) {
         list->first      = NULL;
         list->current    = NULL;
         list->last       = NULL;
+        return TRUE;
+    /* Si no hay más memoria devuelvo FALSE. */
+    } else {
+        return FALSE;
     }
-    return list ? TRUE : FALSE;
 }
 
 bool DLList_empty(DLList* list) {
     return list->first == NULL;
 }
 
-void* DLList_reset(DLList* list) {
+void* DLList_begin(DLList* list) {
     list->current = list->first;
+    /* Si hay un nodo, devulevo sus datos, si no NULL. */
     return list->current ? list->current->data : NULL;
 }
 
+void* DLList_end(DLList* list) {
+    list->current = list->last;
+    /* Si hay un nodo, devulevo sus datos, si no NULL. */
+    return list->current ? list->current->data : NULL;
+}
+
+bool DLList_have_more(DLList* list) {
+    return list->current != NULL;
+}
+
 void* DLList_current(DLList* list) {
     return list->current ? list->current->data : NULL;
 }
 
 void* DLList_next(DLList* list) {
-    DLNode* ret;
-    ret = list->current;
-    if (ret) {
-        list->current = ret->next;
+    DLNode* current = list->current;
+    /* Si no está vacía ni ya fue terminada de recorrer. */
+    if (current) {
+        /* Apuntamos el actual al próximo. */
+        list->current = current->next;
+        /* Devolvemos los datos del próximo o NULL si no había otro. */
         return list->current ? list->current->data : NULL;
+    /* Si está vacía o ya fue terminada de recorrer devolvemos NULL. */
+    } else {
+        return NULL;
+    }
+}
+
+void* DLList_prev(DLList* list) {
+    DLNode* current = list->current;
+    /* Si no está vacía ni ya fue terminada de recorrer. */
+    if (current) {
+        /* Apuntamos el actual al anterior. */
+        list->current = current->prev;
+        /* Devolvemos los datos del anterior o NULL si no había otro. */
+        return list->current ? list->current->data : NULL;
+    /* Si está vacía o ya fue terminada de recorrer devolvemos NULL. */
+    } else {
+        return NULL;
     }
-    return NULL;
 }
 
 bool DLList_unshift(DLList* list, void* data) {
@@ -58,10 +92,11 @@ bool DLList_unshift(DLList* list, void* data) {
         node->prev = NULL;
         node->data = data;
         node->next = list->first;
+        /* Apunto el nodo actual al nuevo nodo. */
+        list->current = node;
         /* Si la lista está vacía hay que hacer apuntar todo al nuevo nodo. */
         if (DLList_empty(list)) {
             list->first   = node;
-            list->current = node;
             list->last    = node;
         /* Si no está vacía. */
         } else {
@@ -82,10 +117,11 @@ bool DLList_push(DLList* list, void* data) {
         node->prev = list->last;
         node->data = data;
         node->next = NULL;
+        /* Apunto el nodo actual al nuevo nodo. */
+        list->current = node;
         /* Si la lista está vacía hay que hacer apuntar todo al nuevo nodo. */
         if (DLList_empty(list)) {
             list->first   = node;
-            list->current = node;
             list->last    = node;
         /* Si no está vacía. */
         } else {
@@ -105,6 +141,10 @@ void* DLList_shift(DLList* list) {
     void* data = node->data;
     /* Pongo como primer nodo al siguiente. */
     list->first = node->next;
+    /* Pongo el nodo anterior al primero como NULL. */
+    list->first->prev = NULL;
+    /* Lo pongo como nodo actual. */
+    list->current = list->first;
     /* Si era el único actualizo los otros punteros. */
     if (!list->first) {
         list->last    = NULL;
@@ -122,6 +162,10 @@ void* DLList_pop(DLList* list) {
     void* data = node->data;
     /* Pongo como último nodo al anterior. */
     list->last = node->prev;
+    /* Pongo el nodo siguiente al último como NULL. */
+    list->last->next = NULL;
+    /* Lo pongo como nodo actual. */
+    list->current = list->last;
     /* Si era el único actualizo los otros punteros. */
     if (!list->last) {
         list->first   = NULL;

diff --git a/dllist.h b/dllist.h
index dc2621440e848eda06f5c52d3d99e7f45ddde27a..d9ad1f781d59330e05f2731a67bbbef7f7b191c8 100644 (file)
--- a/dllist.h
+++ b/dllist.h
@@ -38,26 +38,21 @@ struct DLNodeStruct {
 };
 
 /** Lista doblemente enlazada. */
-typedef struct DLListStruct DLList;
-
-/** Lista doblemente enlazada. */
-struct DLListStruct {
+typedef struct {
     /** Puntero al primer nodo. */
     DLNode* first;
     /** Puntero al nodo actual. */
     DLNode* current;
     /** Puntero al último nodo. */
     DLNode* last;
-};
+} DLList;
 
 /**
  * Inicializa la DLList.
- * Se crea (alocando memoria) e inicializa la DLList.
  *
  * \param   list DLList a inicializar.
  *
  * \return  TRUE si se inicializó bien, FALSE si hay error.
- * \post    Se crea una nueva DLList, reservando una porción de memoria.
  */
 bool DLList_init(DLList* list);
 
@@ -72,27 +67,61 @@ bool DLList_init(DLList* list);
 bool DLList_empty(DLList* list);
 
 /**
- * Reinicia la DLList devolviendo el primer elemento.
- * Hace que el elemento actual de la DLList vuelva a ser el primero.
- * Siempre que se quiera recorrer la DLList debería usarse esta función
- * primero. Por ejemplo:
+ * Apunta al primer elemento de la DLList devolviendolo.
+ * Hace que el elemento actual de la DLList sea el primero y devuelve su valor.
+ * Si está vacía, devuelve NULL.
+ * Siempre que se quiera recorrer la DLList de izquierda a derecha debería
+ * usarse esta función primero. Por ejemplo:
  * \code
- * DLList* list;
- * NodeType*   node;
+ * DLList* l;
+ * char*   data;
  * ...
- * for (node = DLList_reset(list); node; node = DLList_next(list)) {
- *      printf("Uso el elemento actual aquí.\\n");
+ * for (data = DLList_begin(l); DLList_have_more(l); data = DLList_next(l)) {
+ *      printf("El elemento actual es '%s'.\\n", data);
  * }
  * \endcode
  *
- * \param   list DLList de la cual obtener el siguiente elemento.
+ * \param   list DLList de la cual obtener el primer elemento.
+ *
+ * \return  Primer elemento o NULL si está vacía.
+ * \see     DLList_have_more(), DLList_next(), DLList_end(), DLList_prev()
+ * \pre     La DLList debe estar \ref DLList_init "inicializada".
+ */
+void* DLList_begin(DLList* list);
+
+/**
+ * Apunta al último elemento de la DLList devolviendolo.
+ * Hace que el elemento actual de la DLList sea el último y devuelve su valor.
+ * Si está vacía, devuelve NULL.
+ * Siempre que se quiera recorrer la DLList de derecha a izquierda debería
+ * usarse esta función primero. Por ejemplo:
+ * \code
+ * DLList* l;
+ * char*   data;
+ * ...
+ * for (data = DLList_end(l); DLList_have_more(l); data = DLList_prev(l)) {
+ *      printf("El elemento actual es '%s'.\\n", data);
+ * }
+ * \endcode
+ *
+ * \param   list DLList de la cual obtener el último elemento.
  *
- * \return  Puntero al primer elemento o NULL si está vacía.
- * \see     DLList_current()
- * \see     DLList_next()
+ * \return  Último elemento o NULL si está vacía.
+ * \see     DLList_have_more(), DLList_prev(), DLList_begin(), DLList_next()
  * \pre     La DLList debe estar \ref DLList_init "inicializada".
  */
-void* DLList_reset(DLList* list);
+void* DLList_end(DLList* list);
+
+/**
+ * Indica si se puede obtener otro elemento de la lista en una iteración.
+ *
+ * \param   list DLList a verificar.
+ *
+ * \return  TRUE si se puede obtener otro elemento, FALSE si no.
+ * \see     DLList_begin(), DLList_end(), DLList_prev(), DLList_next()
+ * \pre     La DLList debe estar \ref DLList_init "inicializada".
+ */
+bool DLList_have_more(DLList* list);
 
 /**
  * Obtiene el elemento actual de la DLList.
@@ -100,8 +129,7 @@ void* DLList_reset(DLList* list);
  * \param   list DLList de la cual obtener el elemento actual.
  *
  * \return  Elemento actual o NULL si se terminó de recorrer o está vacía.
- * \see     DLList_reset()
- * \see     DLList_next()
+ * \see     DLList_prev(), DLList_next(), DLList_have_more()
  * \pre     La DLList debe estar \ref DLList_init "inicializada".
  */
 void* DLList_current(DLList* list);
@@ -111,13 +139,23 @@ void* DLList_current(DLList* list);
  *
  * \param   list DLList de la cual obtener el siguiente elemento.
  *
- * \return  Puntero al próximo elemento o NULL si es el último.
- * \see     DLList_reset()
- * \see     DLList_current()
+ * \return  Siguiente elemento o NULL si es el último.
+ * \see     DLList_begin(), DLList_have_more(), DLList_current(), DLList_prev()
  * \pre     La DLList debe estar \ref DLList_init "inicializada".
  */
 void* DLList_next(DLList* list);
 
+/**
+ * Obtiene el elemento anterior de la DLList.
+ *
+ * \param   list DLList de la cual obtener el elemento anterior.
+ *
+ * \return  Elemento anterior o NULL si es el primero.
+ * \see     DLList_begin(), DLList_have_more(), DLList_current(), DLList_next()
+ * \pre     La DLList debe estar \ref DLList_init "inicializada".
+ */
+void* DLList_prev(DLList* list);
+
 /**
  * Agrega un elemento al inicio de la DLList.
  *
@@ -125,10 +163,9 @@ void* DLList_next(DLList* list);
  * \param   data Elemento a agregar.
  *
  * \return  TRUE si se agregó, FALSE si no hay más memoria.
- * \see     DLList_push()
- * \see     DLList_pop()
- * \see     DLList_unshift()
+ * \see     DLList_push(), DLList_pop(), DLList_unshift()
  * \pre     La DLList debe estar \ref DLList_init "inicializada".
+ * \post    El puntero interno de la DLList apunta al nuevo elemento.
  */
 bool DLList_unshift(DLList* list, void* data);
 
@@ -139,10 +176,9 @@ bool DLList_unshift(DLList* list, void* data);
  * \param   data Elemento a agregar.
  *
  * \return  TRUE si se agregó, FALSE si no hay más memoria.
- * \see     DLList_pop()
- * \see     DLList_shift()
- * \see     DLList_unshift()
+ * \see     DLList_pop(), DLList_shift(), DLList_unshift()
  * \pre     La DLList debe estar \ref DLList_init "inicializada".
+ * \post    El puntero interno de la DLList apunta al nuevo elemento.
  */
 bool DLList_push(DLList* list, void* data);
 
@@ -153,11 +189,10 @@ bool DLList_push(DLList* list, void* data);
  * \param   list DLList de la cual sacar el elemento.
  *
  * \return  Primer elemento de la DLList.
- * \see     DLList_push()
- * \see     DLList_shift()
- * \see     DLList_unshift()
+ * \see     DLList_push(), DLList_shift(), DLList_unshift()
  * \pre     La DLList debe estar \ref DLList_init "inicializada" y no
  *          \ref DLList_empty "vacía".
+ * \post    El puntero interno de la DLList apunta primer elemento.
  */
 void* DLList_shift(DLList* list);
 
@@ -168,11 +203,10 @@ void* DLList_shift(DLList* list);
  * \param   list DLList de la cual sacar el elemento.
  *
  * \return  último elemento de la DLList.
- * \see     DLList_push()
- * \see     DLList_shift()
- * \see     DLList_unshift()
+ * \see     DLList_push(), DLList_shift(), DLList_unshift()
  * \pre     La DLList debe estar \ref DLList_init "inicializada" y no
  *          \ref DLList_empty "vacía".
+ * \post    El puntero interno de la DLList apunta último elemento.
  */
 void* DLList_pop(DLList* list);