commit cdf85a7432ce92a45e5e201b3c6333046b5592f2 parent 28fedd305c1af00928cae6d09c4cb24411b79ee2 Author: Yuval Langer <yuval.langer@gmail.com> Date: Wed, 8 Nov 2023 16:29:25 +0200 Add count-words solution. Also move files into better locations. Diffstat:
16 files changed, 325 insertions(+), 4 deletions(-)
diff --git a/hash-map/student.c b/hash-map/student.c @@ -1 +0,0 @@ -/home/yuval/foo/cc4e/hash-map/solution.c -\ No newline at end of file diff --git a/linked-tree-map/student.c b/linked-tree-map/student.c @@ -1 +0,0 @@ -solution.c -\ No newline at end of file diff --git a/tree-maps-and-hash-maps/count-words/input.txt b/tree-maps-and-hash-maps/count-words/input.txt @@ -0,0 +1,2 @@ +the clown ran after the car and the car ran into the +tent and the tent fell down on the clown and the car +\ No newline at end of file diff --git a/tree-maps-and-hash-maps/count-words/main.c b/tree-maps-and-hash-maps/count-words/main.c @@ -0,0 +1,52 @@ +#include <stdio.h> +#include <stdlib.h> +#include <string.h> +#include <ctype.h> + +#include "student.c" + +/** + * The main program to read, parse, and count words + */ +int main(void) +{ + struct TreeMap * map = TreeMap_new(); + struct TreeMapEntry *cur; + struct TreeMapIter *iter; + char word[100]; /* Yes, this is dangerous */ + int i,j; + int count, maxvalue; + char *maxkey; + + setvbuf(stdout, NULL, _IONBF, 0); /* Internal */ + + /* Turn off debug */ + map->debug = 0; + + /* Loop over each word in the file */ + while (scanf("%s", word) != EOF) { + for (i=0, j=0; word[i] != '\0'; i++) { + if ( ! isalpha(word[i]) ) continue; + word[j++] = tolower(word[i]); + } + word[j] = '\0'; + count = map->get(map, word, 0); + map->put(map, word, count+1); + } + + maxkey = NULL; + maxvalue = -1; + iter = map->iter(map); + while(1) { + cur = iter->next(iter); + if ( cur == NULL ) break; + if ( maxkey == NULL || cur->value > maxvalue ) { + maxkey = cur->key; + maxvalue = cur->value; + } + } + iter->del(iter); + printf("\n%s %d\n", maxkey, maxvalue); + + map->del(map); +} diff --git a/tree-maps-and-hash-maps/count-words/solution.c b/tree-maps-and-hash-maps/count-words/solution.c @@ -0,0 +1,260 @@ +/* You have to build everything except the main program here + * You should not need to write any new code - just gather your + * working TreeMap code and the supplied code together from the previous + * assignment and combine them together. + */ + +struct TreeMapEntry { + char *key; /* public */ + int value; /* public */ + struct TreeMapEntry *__next; + struct TreeMapEntry *__left; + struct TreeMapEntry *__right; +}; + +struct TreeMapIter { + struct TreeMapEntry *__current; + + struct TreeMapEntry* (*next)(struct TreeMapIter* self); + void (*del)(struct TreeMapIter* self); +}; + +struct TreeMap { + /* Attributes */ + struct TreeMapEntry *__head; + struct TreeMapEntry *__root; + int __count; + int debug; + + /* Methods */ + void (*put)(struct TreeMap* self, char *key, int value); + int (*get)(struct TreeMap* self, char *key, int def); + int (*size)(struct TreeMap* self); + void (*dump)(struct TreeMap* self); + struct TreeMapIter* (*iter)(struct TreeMap* self); + void (*del)(struct TreeMap* self); +}; + +void __TreeMap_del(struct TreeMap* self) { + struct TreeMapEntry *cur, *next; + cur = self->__head; + while(cur) { + free(cur->key); + /* value is just part of the struct */ + next = cur->__next; + free(cur); + cur = next; + } + free((void *)self); +} + +void __TreeMapIter_del(struct TreeMapIter* self) { + free((void *)self); +} + +void __TreeMap_dump_tree(struct TreeMapEntry *cur, int depth) +{ + int i; + if ( cur == NULL ) return; + for(i=0;i<depth;i++) printf("| "); + printf("%s=%d\n", cur->key, cur->value); + if ( cur->__left != NULL ) { + __TreeMap_dump_tree(cur->__left, depth+1); + } + if ( cur->__right != NULL ) { + __TreeMap_dump_tree(cur->__right, depth+1); + } +} + +void __TreeMap_dump(struct TreeMap* self) +{ + struct TreeMapEntry *cur; + printf("Object TreeMap count=%d\n", self->__count); + for(cur = self->__head; cur != NULL ; cur = cur->__next ) { + printf(" %s=%d\n", cur->key, cur->value); + } + printf("\n"); + __TreeMap_dump_tree(self->__root, 0); + printf("\n"); +} + +/* Run a check to see if left and right are broken */ +void __Map_check(struct TreeMap* self, struct TreeMapEntry *left, char *key, struct TreeMapEntry *right) +{ + if ( self->debug ) + printf("Check position: %s < %s > %s\n", (left ? left->key : "0"), + key, (right ? right->key : "0") ); + + /* Check our location in the linked list */ + if ( left != NULL ) { + if ( left->__next != right ) { + printf("FAIL left->__next != right\n"); + } + } else { + if ( self->__head != right ) { + printf("FAIL self->__head != right\n"); + } + } + + /* Check our location in the tree */ + if ( right != NULL && right->__left == NULL ) { + /* OK */ + } else if ( left != NULL && left->__right == NULL ) { + /* OK */ + } else { + printf("FAIL Neither right->__left nor left->__right are available\n"); + } +} + +void __TreeMap_put(struct TreeMap* self, char *key, int value) { + struct TreeMapEntry *cur, *left, *right; + int cmp; + struct TreeMapEntry *old, *new; + char *new_key; + + cur = self->__root; + left = NULL; + right = NULL; + + /* TODO: Loop through the tree from the root. If the matches + * the node, update the value and return. Ad the tree is scanned, + * keep track of the node containing largest key less than "key" + * in the variable left and the node containing the smallest key + * greater than "key" in the variable "right". So if the key is + * not found, left will be the closest lower neighbor or null + * and right will be the closest greater neighbor or null. + */ + + while (cur != NULL) { + cmp = strcmp(key, cur->key); + if (cmp == 0) { + cur->value = value; + return; + } + + old = cur; + + if (cmp < 0) { + right = cur; + cur = cur->__left; + } + + if (cmp > 0) { + left = cur; + cur = cur->__right; + } + } + + ++self->__count; + + /* Not found - time to insert into the linked list after old */ + new = malloc(sizeof(*new)); + + /* TODO: Set up the new node with its new data. */ + new_key = malloc(sizeof(*new_key) * (strlen(key) + 1)); + new_key = strcpy(new_key, key); + new->key = new_key; + new->value = value; + new->__next = NULL; + new->__left = NULL; + new->__right = NULL; + + /* Empty list - add first entry */ + if ( self->__head == NULL ) { + self->__head = new; + self->__root = new; + return; + } + + /* Keep this in here - it will help you debug the above code */ + __Map_check(self, left, key, right); + + /* TODO: Insert into the sorted linked list */ + if (left == NULL) { + new->__next = self->__head; + self->__head = new; + } else if (right == NULL) { + left->__next = new; + } else { + new->__next = right; + left->__next = new; + } + + /* TODO: Insert into the tree */ + if (cmp > 0) { + old->__right = new; + } else { + old->__left = new; + } +} + +int __TreeMap_get(struct TreeMap* self, char *key, int def) +{ + int cmp; + struct TreeMapEntry *cur; + + if ( self == NULL || key == NULL || self->__root == NULL ) return def; + + cur = self->__root; + + /* TODO: scan down the tree and if the key is found, return the value. + * If the key is not found, return the default value (def). + */ + + while (cur != NULL) { + cmp = strcmp(key, cur->key); + if (cmp == 0) { + return cur->value; + } else if (cmp < 0) { + cur = cur->__left; + } else { + cur = cur->__right; + } + } + + return def; +} + +struct TreeMapEntry* __TreeMapIter_next(struct TreeMapIter* self) +{ + /* Advance the iterator. Recall that when we first + * create the iterator __current points to the first item + * so we must return an item and then advance the iterator. + */ + struct TreeMapEntry *cur = self->__current; + if (self->__current != NULL) { + self->__current = cur->__next; + } + return cur; +} + +int __TreeMap_size(struct TreeMap* self) +{ + return self->__count; +} + +struct TreeMapIter* __TreeMap_iter(struct TreeMap* self) +{ + struct TreeMapIter *iter = malloc(sizeof(*iter)); + iter->__current = self->__head; + iter->next = &__TreeMapIter_next; + iter->del = &__TreeMapIter_del; + return iter; +} + +struct TreeMap * TreeMap_new() { + struct TreeMap *p = malloc(sizeof(*p)); + + p->__head = NULL; + p->__root = NULL; + p->__count = 0; + p->debug = 0; + + p->put = &__TreeMap_put; + p->get = &__TreeMap_get; + p->size = &__TreeMap_size; + p->dump = &__TreeMap_dump; + p->iter = &__TreeMap_iter; + p->del = &__TreeMap_del; + return p; +} diff --git a/tree-maps-and-hash-maps/count-words/template.c b/tree-maps-and-hash-maps/count-words/template.c @@ -0,0 +1,5 @@ +/* You have to build everything except the main program here + * You should not need to write any new code - just gather your + * working TreeMap code and the supplied code together from the previous + * assignment and combine them together. + */ +\ No newline at end of file diff --git a/hash-map/main.c b/tree-maps-and-hash-maps/hash-map/main.c diff --git a/hash-map/output.txt b/tree-maps-and-hash-maps/hash-map/output.txt diff --git a/hash-map/solution.c b/tree-maps-and-hash-maps/hash-map/solution.c diff --git a/tree-maps-and-hash-maps/hash-map/student.c b/tree-maps-and-hash-maps/hash-map/student.c @@ -0,0 +1 @@ +/home/yuval/foo/cc4e/hash-map/solution.c +\ No newline at end of file diff --git a/linked-tree-map/Makefile b/tree-maps-and-hash-maps/linked-tree-map/Makefile diff --git a/linked-tree-map/main.c b/tree-maps-and-hash-maps/linked-tree-map/main.c diff --git a/linked-tree-map/output.txt b/tree-maps-and-hash-maps/linked-tree-map/output.txt diff --git a/linked-tree-map/solution.c b/tree-maps-and-hash-maps/linked-tree-map/solution.c diff --git a/tree-maps-and-hash-maps/linked-tree-map/student.c b/tree-maps-and-hash-maps/linked-tree-map/student.c @@ -0,0 +1 @@ +solution.c +\ No newline at end of file diff --git a/linked-tree-map/template.c b/tree-maps-and-hash-maps/linked-tree-map/template.c