From cf3a29feb5887344b6633ead1b4b6d5657a15a4b Mon Sep 17 00:00:00 2001 From: Patrick Simianer Date: Sun, 15 Jun 2014 03:24:33 +0200 Subject: old stuff: algorithms --- algorithms/list.c | 346 ++++++++++++++++++++++++++++++++++++++++++++++++++++++ 1 file changed, 346 insertions(+) create mode 100644 algorithms/list.c (limited to 'algorithms/list.c') 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 +#include +#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; inext = 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; +} + -- cgit v1.2.3