From 9ffedecaa55862a034a7b7d206cccf10f5eba649 Mon Sep 17 00:00:00 2001
From: Alexandre P Francisco <aplf@ist.utl.pt>
Date: Tue, 13 May 2014 14:17:03 +0100
Subject: [PATCH] Adding aula10.

---
 aula10/Makefile |  15 ++++++
 aula10/item.h   |  15 ++++++
 aula10/list.c   | 127 ++++++++++++++++++++++++++++++++++++++++++++++++
 aula10/list.h   |  28 +++++++++++
 aula10/main.c   |  23 +++++++++
 5 files changed, 208 insertions(+)
 create mode 100644 aula10/Makefile
 create mode 100644 aula10/item.h
 create mode 100644 aula10/list.c
 create mode 100644 aula10/list.h
 create mode 100644 aula10/main.c

diff --git a/aula10/Makefile b/aula10/Makefile
new file mode 100644
index 0000000..0cbc301
--- /dev/null
+++ b/aula10/Makefile
@@ -0,0 +1,15 @@
+CC=gcc
+CFLAGS=-g -Wall
+
+EXECS=prog
+
+OBJS=main.o list.o
+HDRS=list.h item.h
+
+all: ${EXECS}
+
+prog: ${OBJS} ${HDRS}
+	${CC} ${CFLAGS} -o $@ ${OBJS}
+
+clean:
+	rm -f *.o ${EXECS}
diff --git a/aula10/item.h b/aula10/item.h
new file mode 100644
index 0000000..5697036
--- /dev/null
+++ b/aula10/item.h
@@ -0,0 +1,15 @@
+#ifndef ITEM_H
+#define ITEM_H
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+
+typedef char* Item;
+
+#define newItem strdup
+#define itemCompare strcmp
+#define showItem(A) printf("%s\n", A)
+#define deleteItem free
+
+#endif /* ITEM_H */
diff --git a/aula10/list.c b/aula10/list.c
new file mode 100644
index 0000000..175f69d
--- /dev/null
+++ b/aula10/list.c
@@ -0,0 +1,127 @@
+#include <stdlib.h>
+#include "list.h"
+
+list* create() {
+  list * l = malloc(sizeof(list));
+  l->first = l->last = NULL;
+  return l;
+}
+
+void insertBegin(list* l, Item i) {
+  link n = malloc(sizeof(struct node));
+  n->item = newItem(i);
+  n->next = l->first;
+  n->prev = NULL;
+  
+  if (l->first) l->first->prev = n;
+  else l->last = n;
+
+  l->first = n;
+}
+
+void insertEnd(list* l, Item i) {
+  link n = malloc(sizeof(struct node));
+  n->item = newItem(i);
+  n->next = NULL;
+  n->prev = l->last;
+  
+  if (l->last) l->last->next = n;
+  else l->first = n;
+
+  l->last = n;
+}
+
+void insertSorted(list* l, Item i) {
+  link n, iter;
+
+  for (iter = l->first; iter && itemCompare(iter->item, i) < 0; iter = iter->next);
+ 
+  n = malloc(sizeof(struct node));
+  n->item = newItem(i);
+  
+  n->next = iter;
+ 
+
+  if (iter) {
+    n->prev = iter->prev;
+
+    if (iter->prev) iter->prev->next = n;
+    else l->first = n;
+
+    iter->prev = n;
+
+  } else {
+    n->prev = l->last;
+
+    if (l->last) l->last->next = n;
+    else l->first = n;
+
+    l->last = n;
+  }
+}
+
+void show(list* l) {
+  link iter;
+  for (iter = l->first; iter; iter = iter->next)
+    showItem(iter->item);
+}
+
+void clear(list* l) {
+  link tofree;
+  
+  while (l->first) {
+    tofree = l->first;
+    l->first = l->first->next;
+    deleteItem(tofree->item);
+    free(tofree);
+  }
+
+  free(l);
+}
+
+void removeFirst(list* l, Item i) {
+  link iter = l->first;
+  int cmp;
+
+  /* Assumindo que esta' ordeando. */
+  for (; iter && (cmp = itemCompare(iter->item, i)) < 0; iter = iter->next);
+
+  if (iter && !cmp) {
+
+    if (iter->prev) iter->prev->next = iter->next;
+    else l->first = iter->next;
+
+    if (iter->next) iter->next->prev = iter->prev;
+    else l->last = iter->prev;
+
+    deleteItem(iter->item);
+    free(iter);
+  }
+}
+
+void removeAll(list* l, Item i) {
+  link iter = l->first, tofree;
+  int cmp;
+
+  /* Assumindo que esta' ordeando. */
+  while (iter && (cmp = itemCompare(iter->item, i)) <= 0) {
+
+    if (!cmp) {
+
+      if (iter->prev) iter->prev->next = iter->next;
+      else l->first = iter->next;
+
+      if (iter->next) iter->next->prev = iter->prev;
+      else l->last = iter->prev;
+     
+      tofree = iter;
+      iter = iter->next;
+
+      deleteItem(tofree->item);
+      free(tofree);
+
+    } else
+      iter = iter->next;
+  }
+}
+
diff --git a/aula10/list.h b/aula10/list.h
new file mode 100644
index 0000000..64abeba
--- /dev/null
+++ b/aula10/list.h
@@ -0,0 +1,28 @@
+#ifndef LIST_H
+#define LIST_H
+
+#include "item.h"
+
+typedef struct node *link;
+
+struct node {
+        Item item;
+        link next;
+        link prev;
+};
+
+typedef struct {
+     link first;
+     link last;
+} list;
+
+list* create();
+void insertBegin(list* l, Item i);
+void insertEnd(list* l, Item i);
+void insertSorted(list* l, Item i);
+void show(list* l);
+void clear(list* l);
+void removeFirst(list* l, Item i);
+void removeAll(list* l, Item i);
+
+#endif /* LIST_H */
diff --git a/aula10/main.c b/aula10/main.c
new file mode 100644
index 0000000..1799a03
--- /dev/null
+++ b/aula10/main.c
@@ -0,0 +1,23 @@
+#include <stdio.h>
+#include <stdio.h>
+
+#include "list.h"
+
+/**
+ * Testar com:
+ * valgrind ./prog sadkfh kdsfkj kdjdas kjhdsja xpto zasd xpto zzz yusadyf ab be
+ */
+int main(int argc, char * argv[]) {
+  list * lst = NULL;
+
+  lst = create();
+
+  while (argc--)
+    insertSorted(lst, argv[argc]);
+
+  removeAll(lst, "xpto");
+  show(lst);
+  clear(lst);
+
+  return EXIT_SUCCESS;
+}
-- 
2.30.2