Week 12 — Strings: Structures and Algorithms¶

/* Week 12 -- Strings: Structures and Algorithms
 * C string memory: a char array plus the '\0' convention, strlen(), and a buffer-overflow edge case that is
 * FLAGGED but never executed (no out-of-bounds write is ever performed -- the guard `if (i == cap) break;`
 * stops the copy one write before it would happen).
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>
#include <string.h>

#define MAX_CAP 16

static char buf[MAX_CAP];

/* Copies src into buf, character by character, but never writes past index cap-1. If src needs more than
 * cap bytes (cap-1 characters plus the terminator), the copy stops as soon as it WOULD go out of bounds and
 * *overflow is set to 1 -- the out-of-bounds write is flagged, never executed. Returns the number of bytes
 * actually written (== cap on overflow, since buf[0..cap-1] are all filled and all valid). */
static int safe_store(const char *src, int cap, int *overflow) {
    int i = 0;
    while (src[i] != '\0') {
        if (i == cap) break;      /* would need buf[cap]: out of bounds -- stop, never write it */
        buf[i] = src[i];
        i++;
    }
    *overflow = (src[i] != '\0');
    if (!*overflow) buf[i] = '\0';
    return i;
}

static void run_scenario(const char *label, const char *text, int cap) {
    printf("-- %s --\n", label);
    printf("cap = %d, source = \"%s\" (%d letters)\n", cap, text, (int) strlen(text));
    int overflow = 0;
    int written = safe_store(text, cap, &overflow);
    if (overflow) {
        printf("overflow flagged after %d bytes: buf[%d] would be out of bounds (valid indices 0..%d) -- stopped, never executed\n", written, cap, cap - 1);
    } else {
        size_t len = strlen(buf);
        printf("stored \"%s\", strlen = %zu\n", buf, len);
    }
    printf("\n");
}

int main(void) {
    run_scenario("normal: cap=16, comfortable fit", "HELLOWORLD", 16);
    run_scenario("hard: cap=12, 1 byte of slack", "ALGORITHMS", 12);
    run_scenario("edge: cap=11, exact fit (0 bytes slack)", "ALGORITHMS", 11);
    run_scenario("edge: cap=8, overflow -- flagged, never executed", "STRUCTURES", 8);
    run_scenario("edge: cap=16, repeated character", "AAAAAAAAAA", 16);
    return 0;
}

/* Week 12 -- Strings: Structures and Algorithms
 * C string memory: a char array plus the '\0' convention, strlen(), and a buffer-overflow edge case that is
 * FLAGGED but never executed. Java strings carry their own length, so the overflow danger below is really a
 * C-only bug; we reproduce the same bounded-array exercise here so the two languages can be compared side by
 * side, with the identical safety guard.
 * CEN207 Data Structures (formerly CE205)
 */
public class CStringMemory {
    static final int MAX_CAP = 16;
    static char[] buf = new char[MAX_CAP];

    // Copies src into buf, character by character, but never writes past index cap-1. Returns the number of
    // characters actually written; overflow[0] is set to true if src needed more room than cap allowed.
    static int safeStore(String src, int cap, boolean[] overflow) {
        int i = 0;
        while (i < src.length()) {
            if (i == cap) break;      // would need buf[cap]: out of bounds -- stop, never write it
            buf[i] = src.charAt(i);
            i++;
        }
        overflow[0] = (i < src.length());
        return i;
    }

    static void runScenario(String label, String text, int cap) {
        System.out.println("-- " + label + " --");
        System.out.println("cap = " + cap + ", source = \"" + text + "\" (" + text.length() + " letters)");
        boolean[] overflow = new boolean[1];
        int written = safeStore(text, cap, overflow);
        if (overflow[0]) {
            System.out.println("overflow flagged after " + written + " bytes: buf[" + cap + "] would be out of bounds (valid indices 0.." + (cap - 1) + ") -- stopped, never executed");
        } else {
            String stored = new String(buf, 0, written);
            System.out.println("stored \"" + stored + "\", strlen = " + stored.length());
        }
        System.out.println();
    }

    public static void main(String[] args) {
        runScenario("normal: cap=16, comfortable fit", "HELLOWORLD", 16);
        runScenario("hard: cap=12, 1 byte of slack", "ALGORITHMS", 12);
        runScenario("edge: cap=11, exact fit (0 bytes slack)", "ALGORITHMS", 11);
        runScenario("edge: cap=8, overflow -- flagged, never executed", "STRUCTURES", 8);
        runScenario("edge: cap=16, repeated character", "AAAAAAAAAA", 16);
    }
}

/* Week 12 -- Strings: Structures and Algorithms
 * Growable string buffer: characters are appended one at a time; when full, a new block double the size is
 * allocated, every existing byte is copied across (realloc), then the new character is written. Appending is
 * O(1) most of the time and O(len) only on the rare growth step -- amortized O(1) overall.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

typedef struct {
    char *buf;
    int len;
    int cap;
    int growths;
} Builder;

static void builder_init(Builder *b, int init_cap) {
    b->cap = init_cap;
    b->buf = malloc((size_t) b->cap);
    b->len = 0;
    b->growths = 0;
}

static void builder_append(Builder *b, char c) {
    if (b->len == b->cap) {              /* full: grow before writing */
        b->cap = b->cap * 2;
        b->buf = realloc(b->buf, (size_t) b->cap);   /* copies every old byte across */
        b->growths++;
    }
    b->buf[b->len] = c;
    b->len++;
}

static void builder_free(Builder *b) {
    free(b->buf);
    b->buf = NULL;
}

static void run_scenario(const char *label, int init_cap, const char *chars) {
    printf("-- %s --\n", label);
    printf("initCap = %d, appending \"%s\" (%d letters)\n", init_cap, chars, (int) strlen(chars));
    Builder b;
    builder_init(&b, init_cap);
    for (int i = 0; chars[i] != '\0'; i++) builder_append(&b, chars[i]);
    printf("result: \"%.*s\", len = %d, finalCap = %d, growths = %d\n\n", b.len, b.buf, b.len, b.cap, b.growths);
    builder_free(&b);
}

int main(void) {
    run_scenario("normal: initCap=4", 4, "HELLOWORLD");
    run_scenario("hard: initCap=2, many growths back to back", 2, "ALGORITHMSDATA");
    run_scenario("edge: initCap=10, exact fit, no growth at all", 10, "ABCDEFGHIJ");
    run_scenario("edge: initCap=1, the smallest possible start", 1, "ABCDEFGHIJ");
    run_scenario("edge: initCap=9, a single growth right at the boundary", 9, "ABCDEFGHIJ");
    return 0;
}

/* Week 12 -- Strings: Structures and Algorithms
 * Growable string buffer, built by hand (java.lang.StringBuilder does exactly this internally). Characters
 * are appended one at a time; when full, a new array double the size is allocated, every existing character
 * is copied across, then the new character is written. Amortized O(1) append.
 * CEN207 Data Structures (formerly CE205)
 */
public class StringBuilderDemo {
    static class Builder {
        char[] buf;
        int len;
        int cap;
        int growths;

        Builder(int initCap) {
            cap = initCap;
            buf = new char[cap];
            len = 0;
            growths = 0;
        }

        void append(char c) {
            if (len == cap) {                          // full: grow before writing
                cap = cap * 2;
                char[] bigger = new char[cap];
                System.arraycopy(buf, 0, bigger, 0, len);   // copies every old byte across
                buf = bigger;
                growths++;
            }
            buf[len] = c;
            len++;
        }
    }

    static void runScenario(String label, int initCap, String chars) {
        System.out.println("-- " + label + " --");
        System.out.println("initCap = " + initCap + ", appending \"" + chars + "\" (" + chars.length() + " letters)");
        Builder b = new Builder(initCap);
        for (int i = 0; i < chars.length(); i++) b.append(chars.charAt(i));
        System.out.println("result: \"" + new String(b.buf, 0, b.len) + "\", len = " + b.len + ", finalCap = " + b.cap + ", growths = " + b.growths);
        System.out.println();
    }

    public static void main(String[] args) {
        runScenario("normal: initCap=4", 4, "HELLOWORLD");
        runScenario("hard: initCap=2, many growths back to back", 2, "ALGORITHMSDATA");
        runScenario("edge: initCap=10, exact fit, no growth at all", 10, "ABCDEFGHIJ");
        runScenario("edge: initCap=1, the smallest possible start", 1, "ABCDEFGHIJ");
        runScenario("edge: initCap=9, a single growth right at the boundary", 9, "ABCDEFGHIJ");
    }
}

/* Week 12 -- Strings: Structures and Algorithms
 * Trie (prefix tree): insert and search, one edge per character, a fixed 26-letter alphabet array per node.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define ALPHA 26

typedef struct TrieNode {
    struct TrieNode *child[ALPHA];
    bool is_end;
} TrieNode;

static TrieNode *new_node(void) {
    TrieNode *n = malloc(sizeof(TrieNode));
    for (int i = 0; i < ALPHA; i++) n->child[i] = NULL;
    n->is_end = false;
    return n;
}

static void insert(TrieNode *root, const char *word) {
    TrieNode *cur = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int c = word[i] - 'A';
        if (cur->child[c] == NULL)
            cur->child[c] = new_node();
        cur = cur->child[c];
    }
    cur->is_end = true;
}

static bool search(TrieNode *root, const char *word, bool *is_prefix) {
    TrieNode *cur = root;
    for (int i = 0; word[i] != '\0'; i++) {
        int c = word[i] - 'A';
        if (cur->child[c] == NULL) {
            *is_prefix = false;
            return false;
        }
        cur = cur->child[c];
    }
    *is_prefix = true;
    return cur->is_end;
}

static void free_trie(TrieNode *n) {
    if (n == NULL) return;
    for (int i = 0; i < ALPHA; i++) free_trie(n->child[i]);
    free(n);
}

static void run_scenario(const char *label, const char *const words[], int nwords, const char *const queries[], int nqueries) {
    printf("-- %s --\n", label);
    TrieNode *root = new_node();
    for (int i = 0; i < nwords; i++) {
        insert(root, words[i]);
        printf("insert(%s)\n", words[i]);
    }
    for (int i = 0; i < nqueries; i++) {
        bool is_prefix = false;
        bool found = search(root, queries[i], &is_prefix);
        printf("search(%s) -> found=%s, isPrefix=%s\n", queries[i], found ? "true" : "false", is_prefix ? "true" : "false");
    }
    free_trie(root);
    printf("\n");
}

int main(void) {
    const char *const w1[] = {"CAT", "CAR", "CARD", "DOG"};
    const char *const q1[] = {"CAR", "CARS", "DO"};
    run_scenario("normal: CAT, CAR, CARD, DOG; search CAR/CARS/DO", w1, 4, q1, 3);

    const char *const w2[] = {"TRIE", "TRIED", "TRIES", "TRY", "TRUE", "TRUCK"};
    const char *const q2[] = {"TRIE", "TR", "TRUCKS", "TRY", "TRUST"};
    run_scenario("hard: the TRIE word family, 5 searches", w2, 6, q2, 5);

    const char *const w3[] = {"AB", "CD", "EF", "GH", "IJ"};
    const char *const q3[] = {"AB", "XY", "A"};
    run_scenario("edge: no shared prefix, every word branches from the root", w3, 5, q3, 3);

    const char *const w4[] = {"DATA", "DATA", "STRUCTURE"};
    const char *const q4[] = {"DATA", "DAT", "STRUCTURES"};
    run_scenario("edge: duplicate insert of DATA (idempotent)", w4, 3, q4, 3);

    const char *const w5[] = {"A", "AB", "ABC", "ABCD"};
    const char *const q5[] = {"A", "ABCD", "ABCDE"};
    run_scenario("edge: a branchless chain A, AB, ABC, ABCD", w5, 4, q5, 3);

    return 0;
}

/* Week 12 -- Strings: Structures and Algorithms
 * Trie (prefix tree): insert and search, one edge per character, a HashMap of children per node.
 * CEN207 Data Structures (formerly CE205)
 */
import java.util.HashMap;
import java.util.Map;

public class TrieInsertSearch {
    static class TrieNode {
        Map<Character, TrieNode> child = new HashMap<>();
        boolean isEnd = false;
    }

    static void insert(TrieNode root, String word) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (!cur.child.containsKey(c))
                cur.child.put(c, new TrieNode());
            cur = cur.child.get(c);
        }
        cur.isEnd = true;
    }

    static boolean search(TrieNode root, String word, boolean[] isPrefix) {
        TrieNode cur = root;
        for (char c : word.toCharArray()) {
            if (!cur.child.containsKey(c)) {
                isPrefix[0] = false;
                return false;
            }
            cur = cur.child.get(c);
        }
        isPrefix[0] = true;
        return cur.isEnd;
    }

    static void runScenario(String label, String[] words, String[] queries) {
        System.out.println("-- " + label + " --");
        TrieNode root = new TrieNode();
        for (String w : words) {
            insert(root, w);
            System.out.println("insert(" + w + ")");
        }
        for (String q : queries) {
            boolean[] isPrefix = new boolean[1];
            boolean found = search(root, q, isPrefix);
            System.out.println("search(" + q + ") -> found=" + found + ", isPrefix=" + isPrefix[0]);
        }
        System.out.println();
    }

    public static void main(String[] args) {
        runScenario("normal: CAT, CAR, CARD, DOG; search CAR/CARS/DO",
                new String[]{"CAT", "CAR", "CARD", "DOG"}, new String[]{"CAR", "CARS", "DO"});

        runScenario("hard: the TRIE word family, 5 searches",
                new String[]{"TRIE", "TRIED", "TRIES", "TRY", "TRUE", "TRUCK"},
                new String[]{"TRIE", "TR", "TRUCKS", "TRY", "TRUST"});

        runScenario("edge: no shared prefix, every word branches from the root",
                new String[]{"AB", "CD", "EF", "GH", "IJ"}, new String[]{"AB", "XY", "A"});

        runScenario("edge: duplicate insert of DATA (idempotent)",
                new String[]{"DATA", "DATA", "STRUCTURE"}, new String[]{"DATA", "DAT", "STRUCTURES"});

        runScenario("edge: a branchless chain A, AB, ABC, ABCD",
                new String[]{"A", "AB", "ABC", "ABCD"}, new String[]{"A", "ABCD", "ABCDE"});
    }
}

/* Week 12 -- Strings: Structures and Algorithms
 * Compressed trie (radix tree): each edge carries a whole substring; a new word either extends an existing
 * edge, becomes a brand-new leaf edge, or SPLITS an existing edge at the point where it first diverges.
 * CEN207 Data Structures (formerly CE205)
 */
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define ALPHA 26

typedef struct RNode {
    char *label;                 /* edge INTO this node; root's label is "" */
    bool is_end;
    struct RNode *child[ALPHA];  /* indexed by the first letter of each child edge */
} RNode;

static char *dup_str(const char *s, int len) {
    char *r = malloc((size_t) len + 1);
    memcpy(r, s, (size_t) len);
    r[len] = '\0';
    return r;
}

static RNode *new_node(const char *label, int label_len, bool is_end) {
    RNode *n = malloc(sizeof(RNode));
    n->label = dup_str(label, label_len);
    n->is_end = is_end;
    for (int i = 0; i < ALPHA; i++) n->child[i] = NULL;
    return n;
}

static int common_prefix_len(const char *a, const char *b) {
    int j = 0;
    while (a[j] && b[j] && a[j] == b[j]) j++;
    return j;
}

static void insert(RNode *node, const char *word) {
    if (word[0] == '\0') { node->is_end = true; return; }   /* the empty word ends exactly at this node */
    int i = 0;
    while (word[i] != '\0') {
        int c = word[i] - 'A';
        if (node->child[c] == NULL) {
            node->child[c] = new_node(word + i, (int) strlen(word + i), true);   /* whole remaining suffix */
            return;
        }
        RNode *child = node->child[c];
        int label_len = (int) strlen(child->label);
        int j = common_prefix_len(word + i, child->label);
        if (j == label_len) {                 /* whole edge matches: descend */
            node = child;
            i += j;
            if (word[i] == '\0') { node->is_end = true; return; }
            continue;
        }
        /* split: a new node holds the shared prefix; child keeps only its tail */
        RNode *mid = new_node(child->label, j, false);
        char *tail = dup_str(child->label + j, label_len - j);
        free(child->label);
        child->label = tail;
        mid->child[(unsigned char) (child->label[0] - 'A')] = child;
        node->child[c] = mid;
        if (word[i + j] == '\0') {
            mid->is_end = true;                /* the inserted word ends exactly at the split point */
            return;
        }
        mid->child[word[i + j] - 'A'] = new_node(word + i + j, (int) strlen(word + i + j), true);
        return;
    }
}

static bool search(RNode *root, const char *word, bool *is_prefix) {
    RNode *node = root;
    int i = 0;
    while (word[i] != '\0') {
        int c = word[i] - 'A';
        if (node->child[c] == NULL) {
            *is_prefix = false;
            return false;
        }
        RNode *child = node->child[c];
        int label_len = (int) strlen(child->label);
        int j = common_prefix_len(word + i, child->label);
        if (j < label_len) {
            *is_prefix = (word[i + j] == '\0');
            return false;
        }
        node = child;
        i += j;
    }
    *is_prefix = true;
    return node->is_end;
}

static void free_radix(RNode *n) {
    if (n == NULL) return;
    for (int i = 0; i < ALPHA; i++) free_radix(n->child[i]);
    free(n->label);
    free(n);
}

static void run_scenario(const char *label, const char *const words[], int nwords, const char *const queries[], int nqueries) {
    printf("-- %s --\n", label);
    RNode *root = new_node("", 0, false);
    for (int i = 0; i < nwords; i++) {
        insert(root, words[i]);
        printf("insert(%s)\n", words[i]);
    }
    for (int i = 0; i < nqueries; i++) {
        bool is_prefix = false;
        bool found = search(root, queries[i], &is_prefix);
        printf("search(%s) -> found=%s, isPrefix=%s\n", queries[i], found ? "true" : "false", is_prefix ? "true" : "false");
    }
    free_radix(root);
    printf("\n");
}

int main(void) {
    const char *const w1[] = {"TEST", "TEA", "TEAM"};
    const char *const q1[] = {"TEA", "TE", "TEAMS"};
    run_scenario("normal: TEST, TEA, TEAM -- one edge splits in two", w1, 3, q1, 3);

    const char *const w2[] = {"ROMAN", "ROMANE", "ROMANUS", "ROMULUS"};
    const char *const q2[] = {"ROMAN", "ROM", "ROMANEQ", "ROMULUS"};
    run_scenario("hard: the ROMAN word family -- several splits back to back", w2, 4, q2, 4);

    const char *const w3[] = {"APPLE", "BANANA"};
    const char *const q3[] = {"APPLE", "AP"};
    run_scenario("edge: no shared prefix, every word is a single long edge", w3, 2, q3, 2);

    const char *const w4[] = {"CAR", "CARPET", "CARD"};
    const char *const q4[] = {"CAR", "CARP", "CARPET"};
    run_scenario("edge: CAR is a prefix of CARPET and CARD", w4, 3, q4, 3);

    const char *const w5[] = {"ANT", "ARM", "ART", "AXE"};
    const char *const q5[] = {"ART", "AR", "ARK"};
    run_scenario("edge: ANT, ARM, ART, AXE -- splits nested inside splits", w5, 4, q5, 3);

    return 0;
}