Primera version de la DLList orientada a objetos.

diff --git a/dllist.cpp b/dllist.cpp
new file mode 100644 (file)
index 0000000..a2994fd
--- /dev/null
+++ b/dllist.cpp
@@ -0,0 +1,197 @@
+/* vim: set et sts=4 sw=4 fdm=indent fdl=1 fdn=0 fo+=t tw=80:
+ *
+ * Taller de Programación (75.42).
+ *
+ * Ejercicio Número 2:
+ * Programa calculadora.
+ *
+ * Copyleft 2003 - Leandro Lucarella <llucare@fi.uba.ar>
+ * Puede copiar, modificar y distribuir este programa bajo los términos de
+ * la licencia GPL (http://www.gnu.org/).
+ *
+ * Creado: sáb ago 30 20:34:45 ART 2003
+ *
+ * $Id$
+ */
+
+// TODO metodos que devuelven NULL si la lista esta vacia.
+//      poner comentarios en línea simple?
+#include "dllist.h"
+
+DLList::DLList(void): first(NULL), current(NULL), last(NULL) {}
+
+DLList::~DLList(void) {
+    /* Elimino los nodos. */
+    while (!DLList_empty(list)) {
+        DLList_pop(list);
+    }
+}
+
+bool DLList::empty(void) {
+    return this->first == NULL;
+}
+
+void* DLList::begin(void) {
+    this->current = this->first;
+    /* Si hay un nodo, devulevo sus datos, si no NULL. */
+    return this->current ? this->current->data : NULL;
+}
+
+void* DLList::end(void) {
+    this->current = this->last;
+    /* Si hay un nodo, devulevo sus datos, si no NULL. */
+    return this->current ? this->current->data : NULL;
+}
+
+bool DLList::have_more(void) {
+    return this->current != NULL;
+}
+
+void* DLList::current(void) {
+    return this->current ? this->current->data : NULL;
+}
+
+void* DLList::next(void) {
+    DLListNode* cur = this->current;
+    /* Si no está vacía ni ya fue terminada de recorrer. */
+    if (cur) {
+        /* Apuntamos el actual al próximo. */
+        this->current = cur->next;
+        /* Devolvemos los datos del próximo o NULL si no había otro. */
+        return this->current ? this->current->data : NULL;
+    /* Si está vacía o ya fue terminada de recorrer devolvemos NULL. */
+    } else {
+        return NULL;
+    }
+}
+
+void* DLList::prev(void) {
+    DLListNode* cur = this->current;
+    /* Si no está vacía ni ya fue terminada de recorrer. */
+    if (cur) {
+        /* Apuntamos el actual al anterior. */
+        this->current = cur->prev;
+        /* Devolvemos los datos del anterior o NULL si no había otro. */
+        return this->current ? this->current->data : NULL;
+    /* Si está vacía o ya fue terminada de recorrer devolvemos NULL. */
+    } else {
+        return NULL;
+    }
+}
+
+bool DLList::unshift(void* data) {
+    DLListNode* node = new DLListNode(NULL, data, this->first);
+    /* Si obtenemos la memoria bien, actualizamos lo que sea necesario. */
+    if (node) {
+        /* Apunto el nodo actual al nuevo nodo. */
+        this->current = node;
+        /* Si la lista está vacía hay que hacer apuntar todo al nuevo nodo. */
+        if (this->first == NULL) {
+            this->first = node;
+            this->last  = node;
+        /* Si no está vacía. */
+        } else {
+            /* Apunto el nodo anterior al primer nodo de la lista al nuevo. */
+            this->first->prev = node;
+            /* Apunto el primer nodo de la lista al nuevo. */
+            this->first = node;
+        }
+        return true;
+    } else {
+        return false;
+    }
+}
+
+bool DLList::push(void* data) {
+    DLListNode* node = new DLListNode(this->last, data, NULL);
+    /* Si obtenemos la memoria bien, actualizamos lo que sea necesario. */
+    if (node) {
+        /* Apunto el nodo actual al nuevo nodo. */
+        this->current = node;
+        /* Si la lista está vacía hay que hacer apuntar todo al nuevo nodo. */
+        if (this->first == NULL) {
+            this->first = node;
+            this->last  = node;
+        /* Si no está vacía. */
+        } else {
+            /* Apunto el próximo nodo del último nodo de la lista al nuevo. */
+            this->last->next = node;
+            /* Apunto el último nodo de la lista al nuevo. */
+            this->last = node;
+        }
+        return true;
+    } else {
+        return false;
+    }
+}
+
+void* DLList::shift(void) {
+    /* Primer nodo */
+    DLListNode* node = this->first;
+    /* Datos del primer nodo. */
+    void* data = node->data;
+    /* Pongo como primer nodo al siguiente. */
+    this->first = node->next;
+    /* Pongo al primero como nodo actual. */
+    this->current = this->first;
+    /* Si era el único pongo el último en NULL. */
+    if (!this->first) {
+        this->last = NULL;
+    /* Si no, pongo el anterior en NULL. */
+    } else {
+        this->first->prev = NULL;
+    }
+    /* Libero memoria del nodo. */
+    delete node;
+    return data;
+}
+
+void* DLList::pop(void) {
+    /* Último nodo */
+    DLListNode* node = this->last;
+    /* Datos del último nodo. */
+    void* data = node->data;
+    /* Pongo como último nodo al anterior. */
+    this->last = node->prev;
+    /* Pongo al último como nodo actual. */
+    this->current = this->last;
+    /* Si era el único pongo el primero en NULL. */
+    if (!this->last) {
+        this->first = NULL;
+    /* Si no, pongo el siguiente en NULL. */
+    } else {
+        this->last->next = NULL;
+    }
+    /* Libero memoria del nodo. */
+    delete node;
+    return data;
+}
+
+void* DLList::remove_current(void) {
+    /* Nodo actual */
+    DLListNode* current = this->current;
+    /* Datos del nodo actual. */
+    void* data = current->data;
+    /* Si tiene siguiente. */
+    if (current->next) {
+        /* Se pone como anterior del siguiente al anterior del actual. */
+        current->next->prev = current->prev;
+    /* Si no tiene siguiente, se pone como último al anterior del actual. */
+    } else {
+        this->last = current->prev;
+    }
+    /* Si tiene anterior. */
+    if (current->prev) {
+        /* Se pone como siguiente del anterior al siguiente del actual. */
+        current->prev->next = current->next;
+    /* Si no tiene anterior, se pone como primero al siguiente del actual. */
+    } else {
+        this->first = current->next;
+    }
+    /* Pongo como elemento actual al próximo elemento. */
+    this->current = current->next;
+    /* Libero memoria del nodo. */
+    delete current;
+    return data;
+}
+

diff --git a/dllist.h b/dllist.h
new file mode 100644 (file)
index 0000000..94c7d54
--- /dev/null
+++ b/dllist.h
@@ -0,0 +1,207 @@
+/* vim: set et sts=4 sw=4 fdm=indent fdl=1 fdn=1 fo+=t tw=80:
+ *
+ * Taller de Programación (75.42).
+ *
+ * Ejercicio Número 3:
+ * TODO
+ *
+ * Copyleft 2003 - Leandro Lucarella <llucare@fi.uba.ar>
+ * Puede copiar, modificar y distribuir este programa bajo los términos de
+ * la licencia GPL (http://www.gnu.org/).
+ *
+ * Creado: Wed Sep 17 21:07:54 ART 2003
+ *
+ * $Id$
+ */
+
+#ifndef DLLIST_H
+#define DLLIST_H
+
+/** Nodo de la lista doblemente enlazada. */
+struct DLListNode {
+    /** Puntero al nodo anterior. */
+    DLListNode* prev;
+    /** Datos almacenados en el nodo. */
+    void* data;
+    /** Puntero al próximo nodo. */
+    DLListNode* next;
+};
+
+/**
+ * Lista doblemente enlazada.
+ */
+class DLList {
+
+    protected:
+        /** Puntero al primer nodo. */
+        DLListNode* first;
+        /** Puntero al nodo actual. */
+        DLListNode* current;
+        /** Puntero al último nodo. */
+        DLListNode* last;
+
+    public:
+        /**
+         * Crea una nueva lista.
+         */
+        DLList(void);
+
+        /**
+         * Libera la memoria ocupada por una lista.
+         */
+        ~DLList(void);
+
+        /**
+         * Indica si está vacía.
+         *
+         * \return true si está vacía, false si no.
+         */
+        bool empty(void);
+
+        /**
+         * Apunta al primer elemento, devolviendolo.
+         * Hace que el elemento actual sea el primero y devuelve su valor.
+         * Si está vacía, devuelve NULL.
+         * Siempre que se quiera recorrer la lista de izquierda a derecha
+         * debería usarse esta función primero. Por ejemplo:
+         * \code
+         * DLList list;
+         * char*  data;
+         * ...
+         * for (data = list.begin(); list.have_more(); data = list.next()) {
+         *      printf("El elemento actual es '%s'.\\n", data);
+         * }
+         * \endcode
+         *
+         * \return  Primer elemento o NULL si está vacía.
+         * \see     have_more(), next(), end(), prev()
+         */
+        void* begin(void);
+
+        /**
+         * Apunta al último elemento, devolviendolo.
+         * Hace que el elemento actual sea el último y devuelve su valor.
+         * Si está vacía, devuelve NULL.
+         * Siempre que se quiera recorrer la lista de derecha a izquierda
+         * debería usarse esta función primero. Por ejemplo:
+         * \code
+         * DLList list;
+         * char*  data;
+         * ...
+         * for (data = list.end(); list.have_more(); data = list.prev()) {
+         *      printf("El elemento actual es '%s'.\\n", data);
+         * }
+         * \endcode
+         *
+         * \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_new "creada" correctamente.
+         */
+        void* end(void);
+
+        /**
+         * Indica si se puede obtener otro elemento de la lista.
+         *
+         * \return true si se puede obtener otro elemento, false si no.
+         * \see    begin(), end(), prev(), next()
+         */
+        bool have_more(void);
+
+        /**
+         * Obtiene el elemento actual.
+         *
+         * \return Elemento actual o NULL si se terminó de recorrer o está vacía.
+         * \see   prev(), next(), have_more()
+         */
+        void* current(void);
+
+        /**
+         * Obtiene el próximo elemento.
+         *
+         * \return  Siguiente elemento o NULL si es el último.
+         * \see     begin(), have_more(), current(), prev()
+         */
+        void* next(void);
+
+        /**
+         * Obtiene el elemento anterior.
+         *
+         * \return  Elemento anterior o NULL si es el primero.
+         * \see     begin(), have_more(), current(), next()
+         */
+        void* prev(void);
+
+        /**
+         * Agrega un elemento al inicio.
+         *
+         * \param   data Elemento a agregar.
+         *
+         * \return  true si se agregó, false si no hay más memoria.
+         * \see     push(), pop(), unshift()
+         */
+        bool unshift(void* data);
+
+        /**
+         * Agrega un elemento al final.
+         *
+         * \param   data Elemento a agregar.
+         *
+         * \return  true si se agregó, false si no hay más memoria.
+         * \see     pop(), shift(), unshift()
+         */
+        bool push(void* data);
+
+        /**
+         * Saca el primer elemento.
+         * Elimina el primer elemento devolviendo su contenido.
+         * Ejemplo:
+         * \code
+         * DLList list;
+         * char*  data;
+         * ...
+         * while (!list.empty()) {
+         *      data = list.shift();
+         *      printf("El elemento actual es '%s'.\\n", data);
+         * }
+         * \endcode
+         *
+         * \return  Primer elemento o NULL si está vacía.
+         * \see     empty(), pop(), remove_current()
+         * \warning Es necesario comprobar antes si está vacía, ya que puede
+         *          devolver NULL también si el elemento de la lista es NULL.
+         */
+        void* shift(void);
+
+        /**
+         * Saca el último elemento.
+         * Elimina el último elemento devolviendo su contenido.
+         * Ejemplo:
+         * \code
+         * DLList list;
+         * char*   data;
+         * ...
+         * while (!list.empty()) {
+         *      data = list.pop();
+         *      printf("El elemento actual es '%s'.\\n", data);
+         * }
+         * \endcode
+         *
+         * \return  Último elemento o NULL si está vacía.
+         * \see     empty(), shift(), remove_current()
+         * \warning Es necesario comprobar antes si está vacía, ya que puede
+         *          devolver NULL también si el elemento de la lista es NULL.
+         */
+        void* pop(void);
+
+        /**
+         * Elimina el elemento actual.
+         * Elimina el elemento actual devolviendo su contenido.
+         *
+         * \return  Elemento actual o NULL si no hay más elementos.
+         * \see     empty(), current(), have_more()
+         * \warning Es necesario comprobar antes si está vacía, ya que puede
+         *          devolver NULL también si el elemento de la lista es NULL.
+         */
+        void* remove_current(void);
+
+#endif /* DLLIST_H */