old stuff: algorithms

1 files changed, 346 insertions, 0 deletions

diff --git a/algorithms/list.c b/algorithms/list.c
new file mode 100644
index 0000000..1a38c19
--- /dev/null
+++ b/algorithms/list.c
@@ -0,0 +1,346 @@
+#include <stdlib.h>
+#include <string.h>
+#include "list.h"
+
+List
+*list_new(void)
+{
+  List *l = malloc(sizeof(List));
+
+  if (l) {
+    l->first = NULL;
+    l->last = NULL;
+  }
+
+  return l;
+}
+
+static Node
+*fill_node(char *item)
+{
+  char *buf = strdup(item);
+  Node *new_node;
+
+  if (!buf) {
+    return NULL;
+  }
+  if (!(new_node = malloc(sizeof(Node)))) {
+    free(buf);
+    return NULL;
+  }
+  new_node->next = NULL;
+  new_node->cont = buf;
+
+  return new_node;
+}
+
+static void
+free_node(Node *n)
+{
+  free(n->cont);
+  free(n);
+}
+
+int
+list_append(List *l, char *item)
+{
+  Node *new_node;
+
+  if (!(new_node = fill_node(item))) {
+    return -1;
+  }
+  if (!l->last) {
+    l->last = l->first = new_node;
+  } else {
+    l->last->next = new_node;
+    l->last = new_node;
+  }
+
+  return 0;
+}
+
+int
+list_len(List *l)
+{
+  int count=0;
+  Node *cur = l->first;
+
+  while (cur) {
+    count++;
+    cur = cur->next;
+  }
+
+  return count;
+}
+
+void
+list_free(List *l)
+{
+  Node *cur = l->first, *next;
+
+  while (cur) {
+    free(cur->cont);
+    next = cur->next;
+    free(cur);
+    cur = next;
+  }
+  free(l);
+}
+
+static Node*
+get_node_at(List *l, int index)
+{
+  Node *cur=l->first;
+
+  for (; cur&&index; index--) {
+    cur = cur->next;
+  }
+
+  return cur;
+}
+
+char*
+list_get_at(List *l, int index)
+{
+  Node *n=get_node_at(l, index);
+
+  if (n) {
+    return n->cont;
+  }
+
+  return NULL;
+}
+
+int 
+list_delete_at(List *l, int index)
+{
+  Node *to_del;
+
+  if (index==0) {
+    to_del = l->first;
+    l->first = to_del->next;
+    if (!l->first) {
+      l->last = NULL;
+    }
+  } else {
+    Node *prev=get_node_at(l, index-1);
+    if (!prev) {
+      return -1;
+    }
+    if (!(to_del = prev->next)) {
+      return -1;
+    }
+    prev->next = to_del->next;
+    if (!prev->next) {
+      l->last = prev;
+    }
+  }
+  free_node(to_del);
+
+  return 0;
+}
+
+int
+list_insert_before(List *l, char *item, int index)
+{
+  Node *new = fill_node(item);
+
+  if (index>0) {
+    Node *cur=get_node_at(l, index-1);
+    if (cur) {
+      new->next = cur->next;
+      cur->next = new;
+    } else {
+      free_node(new);
+      return -1;
+    }
+  } else if (index==0) {
+    if (!l->first) {
+      l->last = new;
+    }
+    new->next = l->first;
+    l->first = new;
+  } else {
+    free_node(new);
+    return -1;
+  }
+
+  return 0;
+}
+
+static Node*
+find_and_remove_smallest(Node **to_sort_ptr)
+{
+  Node *smallest=*to_sort_ptr, **smallest_chaining=to_sort_ptr;
+  Node *cur_node=*to_sort_ptr, **cur_chaining=to_sort_ptr;
+
+  while (cur_node) {
+    if (strcoll(cur_node->cont, smallest->cont)<0) {
+      smallest = cur_node;
+      smallest_chaining = cur_chaining;
+    }
+    cur_chaining = &(cur_node->next);
+    cur_node = cur_node->next;
+  }
+  *smallest_chaining = smallest->next;
+  return smallest;
+}
+
+void
+list_sort(List *l)
+{
+  Node **cur_el_ptr = &(l->first);
+  Node *smallest = NULL;
+
+  while (*cur_el_ptr) {
+    smallest = find_and_remove_smallest(cur_el_ptr);
+    smallest->next = *cur_el_ptr;
+    *cur_el_ptr = smallest;
+    cur_el_ptr = &(smallest->next);
+  }
+  l->last = smallest;
+}
+
+static Node**
+get_node_arr(List *l, int *arr_len)
+{
+  Node **node_arr, **arrEnt;
+  Node *cur=l->first;
+
+  *arr_len = list_len(l);
+  if (!(node_arr=malloc((*arr_len+1)*sizeof(Node*)))) {
+    return NULL;
+  }
+  for (arrEnt=node_arr; cur; cur=cur->next) {
+    *arrEnt++ = cur;
+  }
+  return node_arr;
+}
+
+static int
+node_compare(const void *a, const void *b)
+{
+  Node *node1=*(Node**)a, *node2=*(Node**)b;
+
+  return strcoll(node1->cont, node2->cont);
+}
+
+int
+list_quicksort(List *l)
+{
+  int arr_len, i;
+  Node **node_arr = get_node_arr(l, &arr_len);
+  Node *cur;
+
+  if (!node_arr) {
+    return -1;
+  }
+  qsort(node_arr, arr_len, sizeof(Node*), node_compare);
+
+  cur = l->first = node_arr[0];
+  for (i=1; i<arr_len; i++) {
+    cur->next = node_arr[i];
+    cur = cur->next;
+  }
+  node_arr[arr_len-1]->next = NULL;
+  l->last = cur;
+  free(node_arr);
+  return 0;
+}
+
+Iterator*
+list_iterator_new(List *l)
+{
+  Iterator *it=malloc(sizeof(Iterator));
+
+  if (it) {
+    it->list = l;
+    it->current = l->first;
+  }
+  return it;
+}
+
+void
+list_iterator_free(Iterator *i)
+{
+  free(i);
+}
+
+char*
+list_iterator_next(Iterator *it)
+{
+  char *res=NULL;
+
+  if (it->current) {
+    res = it->current->cont;
+    it->current = it->current->next;
+  }
+
+  return res;
+}
+
+List*
+list_split(char *str, char *split_str)
+{
+  char *part_start = str, *part_end;
+  List *new = list_new();
+
+  if (!new) {
+    return NULL;
+  }
+  part_end = strstr(part_start, split_str);
+  while (part_end) {
+    *part_end = 0;
+    if (list_append(new, part_start)) {
+      list_free(new);
+      return NULL;
+    }
+    part_start = part_end+strlen(split_str);
+    part_end = strstr(part_start, split_str);
+  }
+  list_append(new, part_start);
+  return new;
+}
+
+
+static int
+compute_summed_length(List *l)
+{
+  Node *cur = l->first;
+  int len_sum = 0;
+
+  while (cur) {
+    len_sum += strlen(cur->cont);
+    cur = cur->next;
+  }
+  return len_sum;
+}
+
+char*
+list_join(List *l, char *joiner)
+{
+  int new_length = compute_summed_length(l)+strlen(joiner)*(list_len(l)-1);
+  char *result = malloc((new_length+1)*sizeof(char));
+  char *cur_dest = result, *cur_src;
+  Node *cur;
+
+  if (!result) {
+    return NULL;
+  }
+  cur = l->first;
+  while (cur->next) {
+    for (cur_src=cur->cont; *cur_src;) {
+      *cur_dest++ = *cur_src++;
+    }
+    for (cur_src=joiner; *cur_src;) {
+      *cur_dest++ = *cur_src++;
+    }
+    cur = cur->next;
+  }
+  for (cur_src=cur->cont; *cur_src;) {
+    *cur_dest++ = *cur_src++;
+  }
+  *cur_dest = 0;
+  return result;
+}
+