learning-cc4e

commit 89e1c586aa7e054e98bae814b2dd7c75dd12bcd4
parent 4875c6b899dcedcfb5cc886b9980258776686acb
Author: Yuval Langer <yuval.langer@gmail.com>
Date:   Wed,  8 Nov 2023 16:18:34 +0200

Add solution to linkedtreemap.

Diffstat:
M
linked-tree-map/solution.c
 | 
147
+++++++++++++++++++++++++++++++++++++++++++++++++++++++------------------------

1 file changed, 102 insertions(+), 45 deletions(-)
diff --git a/linked-tree-map/solution.c b/linked-tree-map/solution.c
@@ -1,64 +1,121 @@
 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.
-     */
-
-    /* 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. */
-
-    /* Empty list - add first entry */
-    if ( self->__head == NULL ) {
-        self->__head = new;
-        self->__root = new;
-        return;
+  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;
     }
 
-    /* Keep this in here - it will help you debug the above code */
-    __Map_check(self, left, key, right);
+    old = cur;
+
+    if (cmp < 0) {
+      right = cur;
+      cur = cur->__left;
+    }
+
+    if (cmp > 0) {
+      left = cur;
+      cur = cur->__right;
+    }
+  }
 
-    /* TODO: Insert into the sorted linked list */
+  ++self->__count;
 
-    /* TODO: Insert into the tree */
+  /* 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;
+  int cmp;
+  struct TreeMapEntry *cur;
+
+  if ( self == NULL || key == NULL || self->__root == NULL ) return def;
 
-    if ( self == NULL || key == NULL || self->__root == NULL ) return def;
+  cur = self->__root;
 
-    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).
+   */
 
-    /* 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;
+  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.
-     */
-    return NULL;
+  /* 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;
 }