summaryrefslogtreecommitdiff
diff options
context:
space:
mode:
Diffstat
-rw-r--r--lab04/Makefile23
-rw-r--r--lab04/README.md47
-rw-r--r--lab04/container_of.h49
-rw-r--r--lab04/expression.h319
-rw-r--r--lab04/list.h370
-rw-r--r--lab04/main.c9
-rw-r--r--lab04/polynomial.h876
-rw-r--r--lab04/stack.h219
-rw-r--r--lab04/tests/Makefile18
-rw-r--r--lab04/tests/test.c497
-rw-r--r--lab04/tui.c190
-rw-r--r--lab04/tui.h38
-rw-r--r--lab04/ui.c1543
-rw-r--r--lab04/ui.h9
-rw-r--r--lab04/vec.h1183
15 files changed, 5390 insertions, 0 deletions
diff --git a/lab04/Makefile b/lab04/Makefile
new file mode 100644
index 0000000..dc9f8ab
--- /dev/null
+++ b/lab04/Makefile
@@ -0,0 +1,23 @@
+CC ?= gcc
+CFLAGS ?= -std=gnu11 -Wall -Wextra -O2
+LDLIBS ?= -lm
+
+TARGET := calculator
+SOURCES := main.c ui.c tui.c
+OBJECTS := $(SOURCES:.c=.o)
+
+.PHONY: all clean test
+
+all: $(TARGET)
+
+test:
+ $(MAKE) -C tests run
+
+$(TARGET): $(OBJECTS)
+ $(CC) $(CFLAGS) $(OBJECTS) $(LDLIBS) -o $@
+
+%.o: %.c
+ $(CC) $(CFLAGS) -c $< -o $@
+
+clean:
+ rm -f $(TARGET) $(OBJECTS)
diff --git a/lab04/README.md b/lab04/README.md
new file mode 100644
index 0000000..c2b753b
--- /dev/null
+++ b/lab04/README.md
@@ -0,0 +1,47 @@
+# 数据结构实验 04
+
+## 功能简介
+
+本项目使用 GNU C11 实现一个简单的终端计算器，包含：
+
+- 线性表的添加、插入、删除、修改、查找和遍历；
+- 向量加法、减法和夹角余弦计算；
+- 顺序表多项式的加减、乘法和求导；
+- 链表多项式的加减、乘法和求导。
+- 四则运算表达式求值。
+
+底层实现使用自定义的 `vec` 动态数组和循环双向链表。
+
+## 编译说明
+
+在项目根目录执行：
+
+```sh
+make
+```
+
+默认使用 GNU C11 标准编译，生成可执行文件 `calculator`。
+
+编译参数包括 `-std=gnu11 -Wall -Wextra -O2`，链接时使用数学库 `-lm`。
+
+清理编译文件：
+
+```sh
+make clean
+```
+
+## 使用说明
+
+运行程序：
+
+```sh
+./calculator
+```
+
+在主菜单中选择线性表、向量、顺序表多项式，链表多项式或者四则运算表达式功能。菜单支持方向键或 `j`/`k` 移动，按 Enter 确认，按 `Esc` 或 `q` 返回或退出。
+
+运行测试：
+
+```sh
+make test
+```
diff --git a/lab04/container_of.h b/lab04/container_of.h
new file mode 100644
index 0000000..bffe7b7
--- /dev/null
+++ b/lab04/container_of.h
@@ -0,0 +1,49 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+/**
+ * @file container_of.h
+ * @brief Provides type-aware container and member offset macros.
+ */
+#ifndef _CONTAINER_OF_H
+#define _CONTAINER_OF_H
+
+#include <stddef.h>
+
+/** @brief Checks whether two expressions have compatible types. */
+#define __same_type(a, b) __builtin_types_compatible_p(typeof(a), typeof(b))
+
+/** @brief Computes a member offset using the compiler builtin. */
+#undef offsetof
+#define offsetof(TYPE, MEMBER) __builtin_offsetof(TYPE, MEMBER)
+
+/** @brief Obtains the type of a member of a structure type. */
+#define typeof_member(T, m) typeof(((T*)0)->m)
+
+/**
+ * @brief Converts a pointer to a structure member to its containing object.
+ * @param ptr A pointer to the member.
+ * @param type The type of the containing structure.
+ * @param member The member name within `type`.
+ *
+ * The macro performs a compile-time type compatibility check before applying
+ * the member offset.
+ */
+#define container_of(ptr, type, member) ({ \
+ _Static_assert(__same_type(*(ptr), typeof_member(type, member)) || \
+ __same_type(*(ptr), void), \
+ "pointer type mismatch in container_of()"); \
+ (type *)((void *)(ptr) - offsetof(type, member)); })
+
+
+/**
+ * @brief Converts a member pointer while preserving its const qualification.
+ * @param ptr A pointer to the member.
+ * @param type The type of the containing structure.
+ * @param member The member name within `type`.
+ */
+#define container_of_const(ptr, type, member) \
+ _Generic(ptr, \
+ const typeof(*(ptr)) *: ((const type *)container_of(ptr, type, member)),\
+ default: ((type *)container_of(ptr, type, member)) \
+ )
+
+#endif /* _CONTAINER_OF_H */
diff --git a/lab04/expression.h b/lab04/expression.h
new file mode 100644
index 0000000..f0e2847
--- /dev/null
+++ b/lab04/expression.h
@@ -0,0 +1,319 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+#ifndef EXPRESSION_H
+#define EXPRESSION_H
+
+#include <ctype.h>
+#include <errno.h>
+#include <stdbool.h>
+#include <stddef.h>
+#include <stdlib.h>
+#include <string.h>
+
+#include "stack.h"
+
+#define EXPRESSION_NAME_MAX 64
+
+enum expression_error_code {
+ EXPRESSION_OK,
+ EXPRESSION_SYNTAX_ERROR,
+ EXPRESSION_PAREN_ERROR,
+ EXPRESSION_UNKNOWN_VARIABLE,
+ EXPRESSION_UNSET_VARIABLE,
+ EXPRESSION_DIVISION_BY_ZERO,
+};
+
+struct expression_error {
+ enum expression_error_code code;
+ size_t position;
+};
+
+struct expression_variable {
+ char name[EXPRESSION_NAME_MAX];
+ double value;
+ bool assigned;
+};
+
+struct expression_context {
+ struct vec variables;
+};
+
+static inline void expression_init(struct expression_context *ctx)
+{
+ vec_init(&ctx->variables, struct expression_variable);
+}
+
+static inline void expression_destroy(struct expression_context *ctx)
+{
+ vec_destroy(&ctx->variables);
+}
+
+static inline void expression_error(struct expression_error *error,
+ enum expression_error_code code,
+ size_t position)
+{
+ if (error) {
+ error->code = code;
+ error->position = position;
+ }
+}
+
+static inline bool expression_name_start(unsigned char c)
+{
+ return isalpha(c) || c == '_';
+}
+
+static inline bool expression_name_char(unsigned char c)
+{
+ return isalnum(c) || c == '_';
+}
+
+static inline struct expression_variable *
+expression_variable(struct expression_context *ctx, const char *name)
+{
+ for (size_t i = 0; i < ctx->variables.size; ++i) {
+ struct expression_variable *v = vec_at(&ctx->variables, i);
+ if (strcmp(v->name, name) == 0) {
+ return v;
+ }
+ }
+ return NULL;
+}
+
+static inline bool expression_set_variable(struct expression_context *ctx,
+ const char *name,
+ double value)
+{
+ if (!expression_name_start((unsigned char)name[0]) ||
+ strlen(name) >= EXPRESSION_NAME_MAX) return false;
+ for (const unsigned char *p = (const unsigned char *)name + 1; *p; ++p) {
+ if (!expression_name_char(*p)) {
+ return false;
+ }
+ }
+ struct expression_variable *v = expression_variable(ctx, name);
+ if (!v) {
+ struct expression_variable item = { .value = value, .assigned = true };
+ strcpy(item.name, name);
+ if (!vec_push_back(&ctx->variables, &item)) {
+ return false;
+ }
+ } else {
+ v->value = value;
+ v->assigned = true;
+ }
+ return true;
+}
+
+static inline bool expression_collect_variables(struct expression_context *ctx,
+ const char *text,
+ struct expression_error *error)
+{
+ vec_clear(&ctx->variables);
+ for (size_t i = 0; text[i];) {
+ unsigned char c = (unsigned char)text[i];
+ if (isspace(c)) {
+ ++i;
+ } else if (expression_name_start(c)) {
+ size_t start = i++;
+ while (expression_name_char((unsigned char)text[i])) {
+ ++i;
+ }
+ size_t length = i - start;
+ if (length >= EXPRESSION_NAME_MAX) {
+ expression_error(error, EXPRESSION_SYNTAX_ERROR, start);
+ return false;
+ }
+ char name[EXPRESSION_NAME_MAX];
+ memcpy(name, text + start, length);
+ name[length] = '\0';
+ if (!expression_variable(ctx, name)) {
+ struct expression_variable item = { .assigned = false };
+ strcpy(item.name, name);
+ if (!vec_push_back(&ctx->variables, &item)) {
+ expression_error(error, EXPRESSION_SYNTAX_ERROR, start);
+ return false;
+ }
+ }
+ } else if (isdigit(c) || c == '.' || c == '+' || c == '-' ||
+ c == '*' || c == '/' || c == '(' || c == ')') {
+ ++i;
+ } else {
+ expression_error(error, EXPRESSION_SYNTAX_ERROR, i);
+ return false;
+ }
+ }
+ expression_error(error, EXPRESSION_OK, 0);
+ return true;
+}
+
+/** @brief An operator and its byte offset in the expression. */
+struct expression_operator {
+ char symbol;
+ size_t position;
+};
+
+/** @brief Returns precedence; `p` and `n` denote unary plus and minus. */
+static inline int expression_precedence(char symbol)
+{
+ switch (symbol) {
+ case 'p': case 'n': return 3;
+ case '*': case '/': return 2;
+ case '+': case '-': return 1;
+ default: return 0;
+ }
+}
+
+/** @brief Applies the top operator to the value stack. */
+static inline bool expression_apply(stack *values, stack *operators,
+ struct expression_error *error)
+{
+ struct expression_operator op = *stack_top_as(operators, struct expression_operator);
+ stack_pop(operators);
+ bool unary = op.symbol == 'p' || op.symbol == 'n';
+ if (stack_size(values) < (unary ? 1u : 2u)) {
+ expression_error(error, EXPRESSION_SYNTAX_ERROR, op.position);
+ return false;
+ }
+ if (unary) {
+ if (op.symbol == 'n') *stack_top_as(values, double) *= -1;
+ return true;
+ }
+ double rhs = *stack_top_as(values, double);
+ stack_pop(values);
+ double *lhs = stack_top_as(values, double);
+ switch (op.symbol) {
+ case '+': *lhs += rhs; break;
+ case '-': *lhs -= rhs; break;
+ case '*': *lhs *= rhs; break;
+ case '/':
+ if (rhs == 0.0) {
+ expression_error(error, EXPRESSION_DIVISION_BY_ZERO, op.position);
+ return false;
+ }
+ *lhs /= rhs;
+ break;
+ }
+ return true;
+}
+
+/**
+ * @brief Evaluates an expression using value and operator stacks.
+ * @param ctx The variable table used for name lookup.
+ * @param text The null-terminated expression.
+ * @param result Receives the value on success; unchanged on failure.
+ * @param error Receives the error code and byte offset, or may be null.
+ * @return `true` on success; otherwise `false`.
+ * @pre `ctx` is initialized; `text` and `result` are valid pointers.
+ */
+static inline bool expression_eval(const struct expression_context *ctx,
+ const char *text,
+ double *result,
+ struct expression_error *error)
+{
+ STACK(values, double);
+ STACK(operators, struct expression_operator);
+ bool expect_operand = true;
+ bool success = false;
+ size_t position = 0;
+
+ while (text[position]) {
+ unsigned char c = (unsigned char)text[position];
+ if (isspace(c)) {
+ ++position;
+ continue;
+ }
+ if (isdigit(c) || c == '.' || expression_name_start(c)) {
+ if (!expect_operand) goto syntax_error;
+ double value;
+ if (expression_name_start(c)) {
+ size_t start = position++;
+ while (expression_name_char((unsigned char)text[position])) ++position;
+ size_t length = position - start;
+ if (length >= EXPRESSION_NAME_MAX) {
+ position = start;
+ goto syntax_error;
+ }
+ const struct expression_variable *variable = NULL;
+ for (size_t i = 0; i < ctx->variables.size; ++i) {
+ const struct expression_variable *v = vec_at_const(&ctx->variables, i);
+ if (strlen(v->name) == length &&
+ strncmp(v->name, text + start, length) == 0) {
+ variable = v;
+ break;
+ }
+ }
+ if (!variable || !variable->assigned) {
+ expression_error(error, variable ? EXPRESSION_UNSET_VARIABLE
+ : EXPRESSION_UNKNOWN_VARIABLE, start);
+ goto done;
+ }
+ value = variable->value;
+ } else {
+ char *end;
+ errno = 0;
+ value = strtod(text + position, &end);
+ if (end == text + position || errno == ERANGE) goto syntax_error;
+ position = (size_t)(end - text);
+ }
+ if (!stack_push(&values, &value)) goto syntax_error;
+ expect_operand = false;
+ continue;
+ }
+ struct expression_operator op = { .symbol = (char)c, .position = position };
+ if (c == '(') {
+ if (!expect_operand) goto syntax_error;
+ } else if (c == ')') {
+ if (expect_operand) goto syntax_error;
+ while (!stack_empty(&operators) &&
+ stack_top_as(&operators, struct expression_operator)->symbol != '(') {
+ if (!expression_apply(&values, &operators, error)) goto done;
+ }
+ if (stack_empty(&operators)) goto paren_error;
+ stack_pop(&operators);
+ ++position;
+ continue;
+ } else if (c == '+' || c == '-' || c == '*' || c == '/') {
+ if (expect_operand) {
+ if (c != '+' && c != '-') goto syntax_error;
+ op.symbol = c == '+' ? 'p' : 'n';
+ } else {
+ while (!stack_empty(&operators) &&
+ expression_precedence(stack_top_as(&operators,
+ struct expression_operator)->symbol) >= expression_precedence(op.symbol)) {
+ if (!expression_apply(&values, &operators, error)) goto done;
+ }
+ }
+ } else {
+ goto syntax_error;
+ }
+ if (!stack_push(&operators, &op)) goto syntax_error;
+ expect_operand = true;
+ ++position;
+ }
+ if (expect_operand) goto syntax_error;
+ while (!stack_empty(&operators)) {
+ struct expression_operator op = *stack_top_as(&operators, struct expression_operator);
+ if (op.symbol == '(') {
+ position = op.position;
+ goto paren_error;
+ }
+ if (!expression_apply(&values, &operators, error)) goto done;
+ }
+ if (stack_size(&values) != 1) goto syntax_error;
+ *result = *stack_top_as(&values, double);
+ expression_error(error, EXPRESSION_OK, 0);
+ success = true;
+ goto done;
+
+syntax_error:
+ expression_error(error, EXPRESSION_SYNTAX_ERROR, position);
+ goto done;
+paren_error:
+ expression_error(error, EXPRESSION_PAREN_ERROR, position);
+done:
+ stack_destroy(&values);
+ stack_destroy(&operators);
+ return success;
+}
+
+#endif /* EXPRESSION_H */
diff --git a/lab04/list.h b/lab04/list.h
new file mode 100644
index 0000000..7d4ca23
--- /dev/null
+++ b/lab04/list.h
@@ -0,0 +1,370 @@
+/* SPDX-License-Identifier: GPL-2.0 */
+
+/**
+ * @file list.h
+ * @brief Intrusive circular doubly linked list primitives.
+ *
+ * A list node is embedded in the structure that owns it. The list head is
+ * represented by a sentinel `struct list_head` whose links point to itself
+ * when the list is empty.
+ */
+#ifndef LIST_H
+#define LIST_H
+
+#include <stddef.h>
+#include <stdbool.h>
+#include <assert.h>
+
+#include "container_of.h"
+
+/**
+ * @brief A node in an intrusive circular doubly linked list.
+ */
+struct list_head {
+ struct list_head *next;
+ struct list_head *prev;
+};
+
+/** @brief Poison value written to a deleted node's `next` link. */
+#define LIST_POISON1 ((void *) 0x100)
+
+/** @brief Poison value written to a deleted node's `prev` link. */
+#define LIST_POISON2 ((void *) 0x122)
+
+/**
+ * @brief Circular doubly linked list implementation.
+ *
+ * Some internal functions are useful when manipulating whole lists because
+ * the neighboring nodes are already known.
+ */
+
+/** @brief Initializes a list head initializer. */
+#define LIST_HEAD_INIT(name) { &(name), &(name) }
+
+/**
+ * @brief Declares and initializes an empty list head.
+ * @param name The list head variable name.
+ */
+#define LIST_HEAD(name) \
+ struct list_head name = LIST_HEAD_INIT(name)
+
+/**
+ * @brief Initializes a list node or list head.
+ *
+ * The node is made self-linked. When used as a list head, this represents
+ * an empty list.
+ *
+ * @param list The node or list head to initialize.
+ * @post `list->next == list`.
+ * @post `list->prev == list`.
+ */
+static inline void INIT_LIST_HEAD(struct list_head *list)
+{
+ list->next = list;
+ list->prev = list;
+}
+
+/**
+ * @internal
+ * @brief Links a node between two known adjacent nodes.
+ */
+static inline void __list_add(struct list_head *node,
+ struct list_head *prev,
+ struct list_head *next)
+{
+ next->prev = node;
+ node->next = next;
+ node->prev = prev;
+ prev->next = node;
+}
+
+/**
+ * @brief Inserts a node immediately after a list node.
+ *
+ * This operation is suitable for stack-like insertion.
+ *
+ * @param node The node to insert.
+ * @param head The node after which `node` is inserted.
+ * @pre `node` is not currently linked into a list.
+ */
+static inline void list_add(struct list_head *node,
+ struct list_head *head)
+{
+ __list_add(node, head, head->next);
+}
+
+/**
+ * @brief Inserts a node immediately before a list node.
+ *
+ * This operation is suitable for queue-like insertion when `head` is the
+ * list sentinel.
+ *
+ * @param node The node to insert.
+ * @param head The node before which `node` is inserted.
+ * @pre `node` is not currently linked into a list.
+ */
+static inline void list_add_tail(struct list_head *node,
+ struct list_head *head)
+{
+ __list_add(node, head->prev, head);
+}
+
+/**
+ * @internal
+ * @brief Unlinks the range between two known adjacent nodes.
+ */
+static inline void __list_del(struct list_head *prev,
+ struct list_head *next)
+{
+ next->prev = prev;
+ prev->next = next;
+}
+
+/**
+ * @internal
+ * @brief Unlinks a node using its stored neighboring links.
+ */
+static inline void __list_del_entry(struct list_head *entry)
+{
+ __list_del(entry->prev, entry->next);
+}
+
+/**
+ * @brief Removes a node from its list.
+ *
+ * After this operation, the node's links contain poison values and must not
+ * be used for list traversal.
+ *
+ * @param entry The node to remove.
+ * @pre `entry` belongs to a valid list.
+ */
+static inline void list_del(struct list_head *entry)
+{
+ __list_del_entry(entry);
+ entry->next = LIST_POISON1;
+ entry->prev = LIST_POISON2;
+}
+
+/**
+ * @brief Replaces one list node with another.
+ *
+ * The replacement node takes the position of the old node.
+ *
+ * @param old The node to replace.
+ * @param new The replacement node.
+ * @pre `old` belongs to a valid list.
+ * @pre `new` is not currently linked into a list.
+ */
+static inline void list_replace(struct list_head *old,
+ struct list_head *new)
+{
+ new->next = old->next;
+ new->next->prev = new;
+ new->prev = old->prev;
+ new->prev->next = new;
+}
+
+/**
+ * @brief Replaces one node and reinitializes the old node.
+ *
+ * @param old The node to replace.
+ * @param new The replacement node.
+ * @pre `old` belongs to a valid list.
+ * @pre `new` is not currently linked into a list.
+ * @post `old` is a self-linked standalone node.
+ */
+static inline void list_replace_init(struct list_head *old,
+ struct list_head *new)
+{
+ list_replace(old, new);
+ INIT_LIST_HEAD(old);
+}
+
+/**
+ * @brief Removes a node from its list and inserts it after `head`.
+ *
+ * @param list The node to move.
+ * @param head The node that precedes the moved node.
+ * @pre `list` belongs to a valid list.
+ */
+static inline void list_move(struct list_head *list, struct list_head *head)
+{
+ __list_del_entry(list);
+ list_add(list, head);
+}
+
+/**
+ * @brief Removes a node from its list and inserts it before `head`.
+ *
+ * @param list The node to move.
+ * @param head The node that follows the moved node.
+ * @pre `list` belongs to a valid list.
+ */
+static inline void list_move_tail(struct list_head *list,
+ struct list_head *head)
+{
+ __list_del_entry(list);
+ list_add_tail(list, head);
+}
+
+/**
+ * @brief Tests whether a node is the first entry in a list.
+ *
+ * @param list The node to test.
+ * @param head The list head.
+ * @return Nonzero if `list` is the first entry; zero otherwise.
+ */
+static inline int list_is_first(const struct list_head *list, const struct list_head *head)
+{
+ return list->prev == head;
+}
+
+/**
+ * @brief Tests whether a node is the last entry in a list.
+ *
+ * @param list The node to test.
+ * @param head The list head.
+ * @return Nonzero if `list` is the last entry; zero otherwise.
+ */
+static inline int list_is_last(const struct list_head *list, const struct list_head *head)
+{
+ return list->next == head;
+}
+
+/**
+ * @brief Tests whether a node is the list head.
+ *
+ * @param list The node to test.
+ * @param head The list head.
+ * @return Nonzero if `list == head`; zero otherwise.
+ */
+static inline int list_is_head(const struct list_head *list, const struct list_head *head)
+{
+ return list == head;
+}
+
+/**
+ * @brief Tests whether a list is empty.
+ *
+ * @param head The list head.
+ * @return Nonzero if the list contains no entries; zero otherwise.
+ */
+static inline int list_empty(const struct list_head *head)
+{
+ return head->next == head;
+}
+
+/**
+ * @brief Returns the containing structure for a list node.
+ *
+ * @param ptr A pointer to the embedded `struct list_head`.
+ * @param type The containing structure type.
+ * @param member The embedded list member.
+ * @return A pointer to the containing structure.
+ */
+#define list_entry(ptr, type, member) \
+ container_of(ptr, type, member)
+
+/**
+ * @brief Returns the first containing structure in a list.
+ *
+ * @param ptr The list head.
+ * @param type The containing structure type.
+ * @param member The embedded list member.
+ * @pre The list is not empty.
+ */
+#define list_first_entry(ptr, type, member) \
+ list_entry((ptr)->next, type, member)
+
+/**
+ * @brief Returns the last containing structure in a list.
+ *
+ * @param ptr The list head.
+ * @param type The containing structure type.
+ * @param member The embedded list member.
+ * @pre The list is not empty.
+ */
+#define list_last_entry(ptr, type, member) \
+ list_entry((ptr)->prev, type, member)
+
+/**
+ * @brief Returns the containing structure following the current node.
+ *
+ * @param pos The typed cursor.
+ * @param member The embedded list member.
+ * @return The next containing structure.
+ */
+#define list_next_entry(pos, member) \
+ list_entry((pos)->member.next, typeof(*(pos)), member)
+
+/**
+ * @brief Returns the containing structure preceding the current node.
+ *
+ * @param pos The typed cursor.
+ * @param member The embedded list member.
+ * @return The previous containing structure.
+ */
+#define list_prev_entry(pos, member) \
+ list_entry((pos)->member.prev, typeof(*(pos)), member)
+
+/**
+ * @brief Tests whether a typed cursor refers to the list head.
+ *
+ * @param pos The typed cursor.
+ * @param head The list head.
+ * @param member The embedded list member.
+ * @return Nonzero if `pos` refers to `head`; zero otherwise.
+ */
+#define list_entry_is_head(pos, head, member) \
+ (&pos->member == (head))
+
+/**
+ * @brief Iterates over containing structures in forward order.
+ *
+ * Example:
+ * @code
+ * struct item *pos;
+ * list_for_each_entry(pos, &head, link) {
+ * use_item(pos);
+ * }
+ * @endcode
+ *
+ * @param pos The typed loop cursor.
+ * @param head The list head.
+ * @param member The embedded list member.
+ */
+#define list_for_each_entry(pos, head, member) \
+ for (pos = list_first_entry(head, typeof(*pos), member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = list_next_entry(pos, member))
+
+/**
+ * @brief Iterates over containing structures in reverse order.
+ *
+ * @param pos The typed loop cursor.
+ * @param head The list head.
+ * @param member The embedded list member.
+ */
+#define list_for_each_entry_reverse(pos, head, member) \
+ for (pos = list_last_entry(head, typeof(*pos), member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = list_prev_entry(pos, member))
+
+/**
+ * @brief Iterates over containing structures while allowing removal.
+ *
+ * The additional cursor stores the next entry before the loop body runs, so
+ * the current entry may be removed safely from the list.
+ *
+ * @param pos The typed loop cursor.
+ * @param n The temporary typed cursor.
+ * @param head The list head.
+ * @param member The embedded list member.
+ */
+#define list_for_each_entry_safe(pos, n, head, member) \
+ for (pos = list_first_entry(head, typeof(*pos), member), \
+ n = list_next_entry(pos, member); \
+ !list_entry_is_head(pos, head, member); \
+ pos = n, n = list_next_entry(n, member))
+
+#endif /* LIST_H */
diff --git a/lab04/main.c b/lab04/main.c
new file mode 100644
index 0000000..3b51f82
--- /dev/null
+++ b/lab04/main.c
@@ -0,0 +1,9 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+#include "ui.h"
+
+int main(void)
+{
+ return ui_run();
+}
diff --git a/lab04/polynomial.h b/lab04/polynomial.h
new file mode 100644
index 0000000..a270211
--- /dev/null
+++ b/lab04/polynomial.h
@@ -0,0 +1,876 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+#ifndef POLYNOMIAL_H
+#define POLYNOMIAL_H
+
+#include <stddef.h>
+#include <stdbool.h>
+#include <limits.h>
+#include <math.h>
+#include <stdlib.h>
+
+#include "vec.h"
+#include "list.h"
+
+/*
+ * Polynomial term:
+ *
+ * coef * x^exp
+ *
+ * exp >= 0
+ */
+struct poly_term {
+ double coef;
+ unsigned int exp;
+};
+
+/*
+ * ============================================================
+ * Sequential representation
+ * ============================================================
+ *
+ * Terms are stored in descending order of exponent:
+ *
+ * 5x^4 + 3x^2 - 7
+ *
+ * [ {5,4}, {3,2}, {-7,0} ]
+ *
+ * Invariants:
+ *
+ * terms.elem_size == sizeof(struct poly_term)
+ * terms are ordered by exp descending
+ * duplicate exponents do not exist
+ * zero-coefficient terms do not exist
+ */
+
+struct poly_vec {
+ struct vec terms;
+};
+
+/*
+ * ============================================================
+ * Linked representation
+ * ============================================================
+ */
+
+struct poly_node {
+ struct poly_term term;
+ struct list_head link;
+};
+
+struct poly_list {
+ struct list_head head;
+ size_t size;
+};
+
+/*
+ * ============================================================
+ * Initialization / destruction
+ * ============================================================
+ */
+
+static inline void poly_vec_init(struct poly_vec *poly)
+{
+ vec_init(&poly->terms, struct poly_term);
+}
+
+static inline void poly_vec_clear(struct poly_vec *poly)
+{
+ vec_clear(&poly->terms);
+}
+
+static inline void poly_vec_destroy(struct poly_vec *poly)
+{
+ vec_destroy(&poly->terms);
+}
+
+static inline void poly_list_init(struct poly_list *poly)
+{
+ INIT_LIST_HEAD(&poly->head);
+ poly->size = 0;
+}
+
+static inline void poly_list_clear(struct poly_list *poly)
+{
+ struct list_head *pos = poly->head.next;
+
+ while (pos != &poly->head) {
+ struct list_head *next = pos->next;
+ struct poly_node *node = list_entry(pos, struct poly_node, link);
+ list_del(pos);
+ free(node);
+ pos = next;
+ }
+
+ INIT_LIST_HEAD(&poly->head);
+ poly->size = 0;
+}
+
+static inline void poly_list_destroy(struct poly_list *poly)
+{
+ poly_list_clear(poly);
+}
+
+static inline void __poly_vec_replace(struct poly_vec *dst,
+ struct poly_vec *src)
+{
+ struct vec old = dst->terms;
+ dst->terms = src->terms;
+ src->terms = old;
+ vec_destroy(&src->terms);
+}
+
+static inline void __poly_list_replace(struct poly_list *dst,
+ struct poly_list *src)
+{
+ poly_list_clear(dst);
+ if (src->size == 0) {
+ return;
+ }
+
+ dst->head.next = src->head.next;
+ dst->head.prev = src->head.prev;
+ dst->head.next->prev = &dst->head;
+ dst->head.prev->next = &dst->head;
+ dst->size = src->size;
+
+ INIT_LIST_HEAD(&src->head);
+ src->size = 0;
+}
+
+/*
+ * ============================================================
+ * Basic properties
+ * ============================================================
+ */
+
+static inline bool poly_vec_empty(const struct poly_vec *poly)
+{
+ return vec_empty(&poly->terms);
+}
+
+static inline size_t poly_vec_size(const struct poly_vec *poly)
+{
+ return vec_size(&poly->terms);
+}
+
+
+static inline bool poly_list_empty(const struct poly_list *poly)
+{
+ return list_empty(&poly->head);
+}
+
+static inline size_t poly_list_size(const struct poly_list *poly)
+{
+ return poly->size;
+}
+
+/*
+ * ============================================================
+ * Term access
+ * ============================================================
+ *
+ * Sequential representation supports indexed access.
+ */
+
+static inline struct poly_term *
+poly_vec_at(struct poly_vec *poly, size_t index)
+{
+ return vec_at(&poly->terms, index);
+}
+
+static inline const struct poly_term *
+poly_vec_at_const(const struct poly_vec *poly, size_t index)
+{
+ return vec_at_const(&poly->terms, index);
+}
+
+
+/*
+ * ============================================================
+ * Term modification
+ * ============================================================
+ *
+ * poly_*_set_term():
+ *
+ * Sets the coefficient for x^exp.
+ *
+ * Existing exponent:
+ * replace coefficient
+ *
+ * Missing exponent:
+ * insert at the proper position
+ *
+ * coef == 0:
+ * remove that exponent
+ *
+ *
+ * poly_*_add_term():
+ *
+ * Adds coef*x^exp to the polynomial.
+ *
+ * Existing exponent:
+ * old_coef += coef
+ *
+ * Result coefficient == 0:
+ * remove that term
+ *
+ * These two operations preserve all polynomial invariants.
+ */
+
+static inline size_t __poly_vec_find(const struct poly_vec *poly,
+ unsigned int exp,
+ bool *found)
+{
+ size_t i;
+
+ for (i = 0; i < vec_size(&poly->terms); ++i) {
+ const struct poly_term *term = vec_at_const(&poly->terms, i);
+ if (term->exp == exp) {
+ *found = true;
+ return i;
+ }
+ if (term->exp < exp) {
+ break;
+ }
+ }
+
+ *found = false;
+ return i;
+}
+
+static inline bool poly_vec_remove_term(struct poly_vec *poly,
+ unsigned int exp);
+
+static inline bool poly_vec_set_term(struct poly_vec *poly,
+ double coef,
+ unsigned int exp)
+{
+ if (coef == 0.0) {
+ poly_vec_remove_term(poly, exp);
+ return true;
+ }
+
+ bool found;
+ size_t index = __poly_vec_find(poly, exp, &found);
+ if (found) {
+ poly_vec_at(poly, index)->coef = coef;
+ return true;
+ }
+
+ struct poly_term term = { .coef = coef, .exp = exp };
+ return vec_insert(&poly->terms, index, &term);
+}
+
+static inline bool poly_vec_add_term(struct poly_vec *poly,
+ double coef,
+ unsigned int exp)
+{
+ if (coef == 0.0) {
+ return true;
+ }
+
+ bool found;
+ size_t index = __poly_vec_find(poly, exp, &found);
+ if (found) {
+ struct poly_term *term = poly_vec_at(poly, index);
+ double result = term->coef + coef;
+ if (result == 0.0) {
+ vec_erase(&poly->terms, index);
+ } else {
+ term->coef = result;
+ }
+ return true;
+ }
+
+ struct poly_term term = { .coef = coef, .exp = exp };
+ return vec_insert(&poly->terms, index, &term);
+}
+
+static inline bool poly_vec_remove_term(struct poly_vec *poly,
+ unsigned int exp)
+{
+ bool found;
+ size_t index = __poly_vec_find(poly, exp, &found);
+ if (!found) {
+ return false;
+ }
+
+ vec_erase(&poly->terms, index);
+ return true;
+}
+
+static inline bool poly_vec_get_term(const struct poly_vec *poly,
+ unsigned int exp,
+ double *coef)
+{
+ bool found;
+ size_t index = __poly_vec_find(poly, exp, &found);
+ if (!found) {
+ return false;
+ }
+
+ *coef = poly_vec_at_const(poly, index)->coef;
+ return true;
+}
+
+static inline bool poly_list_remove_term(struct poly_list *poly,
+ unsigned int exp);
+
+static inline bool poly_list_set_term(struct poly_list *poly,
+ double coef,
+ unsigned int exp)
+{
+ if (coef == 0.0) {
+ poly_list_remove_term(poly, exp);
+ return true;
+ }
+
+ struct list_head *pos = poly->head.next;
+ while (pos != &poly->head) {
+ struct poly_node *node = list_entry(pos, struct poly_node, link);
+ if (node->term.exp == exp) {
+ node->term.coef = coef;
+ return true;
+ }
+ if (node->term.exp < exp) {
+ break;
+ }
+ pos = pos->next;
+ }
+
+ struct poly_node *node = malloc(sizeof(*node));
+ if (!node) {
+ return false;
+ }
+ node->term.coef = coef;
+ node->term.exp = exp;
+ __list_add(&node->link, pos->prev, pos);
+ ++poly->size;
+ return true;
+}
+
+static inline bool poly_list_add_term(struct poly_list *poly,
+ double coef,
+ unsigned int exp)
+{
+ if (coef == 0.0) {
+ return true;
+ }
+
+ struct list_head *pos = poly->head.next;
+ while (pos != &poly->head) {
+ struct poly_node *node = list_entry(pos, struct poly_node, link);
+ if (node->term.exp == exp) {
+ double result = node->term.coef + coef;
+ if (result == 0.0) {
+ list_del(pos);
+ free(node);
+ --poly->size;
+ } else {
+ node->term.coef = result;
+ }
+ return true;
+ }
+ if (node->term.exp < exp) {
+ break;
+ }
+ pos = pos->next;
+ }
+
+ struct poly_node *node = malloc(sizeof(*node));
+ if (!node) {
+ return false;
+ }
+ node->term.coef = coef;
+ node->term.exp = exp;
+ __list_add(&node->link, pos->prev, pos);
+ ++poly->size;
+ return true;
+}
+
+static inline bool poly_list_remove_term(struct poly_list *poly,
+ unsigned int exp)
+{
+ struct list_head *pos = poly->head.next;
+ while (pos != &poly->head) {
+ struct poly_node *node = list_entry(pos, struct poly_node, link);
+ if (node->term.exp == exp) {
+ list_del(pos);
+ free(node);
+ --poly->size;
+ return true;
+ }
+ if (node->term.exp < exp) {
+ return false;
+ }
+ pos = pos->next;
+ }
+ return false;
+}
+
+static inline bool poly_list_get_term(const struct poly_list *poly,
+ unsigned int exp,
+ double *coef)
+{
+ const struct list_head *pos = poly->head.next;
+ while (pos != &poly->head) {
+ const struct poly_node *node =
+ list_entry(pos, const struct poly_node, link);
+ if (node->term.exp == exp) {
+ *coef = node->term.coef;
+ return true;
+ }
+ if (node->term.exp < exp) {
+ return false;
+ }
+ pos = pos->next;
+ }
+ return false;
+}
+
+
+/*
+ * ============================================================
+ * Copy / conversion
+ * ============================================================
+ */
+
+static inline bool poly_vec_copy(struct poly_vec *dst,
+ const struct poly_vec *src)
+{
+ struct poly_vec tmp;
+ poly_vec_init(&tmp);
+
+ if (!vec_append(&tmp.terms, src->terms.data, src->terms.size)) {
+ poly_vec_destroy(&tmp);
+ return false;
+ }
+
+ __poly_vec_replace(dst, &tmp);
+ return true;
+}
+
+static inline bool poly_list_copy(struct poly_list *dst,
+ const struct poly_list *src)
+{
+ struct poly_list tmp;
+ poly_list_init(&tmp);
+
+ const struct list_head *pos = src->head.next;
+ while (pos != &src->head) {
+ const struct poly_node *node =
+ list_entry(pos, const struct poly_node, link);
+ if (!poly_list_set_term(&tmp, node->term.coef, node->term.exp)) {
+ poly_list_destroy(&tmp);
+ return false;
+ }
+ pos = pos->next;
+ }
+
+ __poly_list_replace(dst, &tmp);
+ return true;
+}
+
+
+/*
+ * Conversion between the two representations.
+ */
+static inline bool poly_vec_from_list(struct poly_vec *dst,
+ const struct poly_list *src)
+{
+ struct poly_vec tmp;
+ poly_vec_init(&tmp);
+
+ const struct list_head *pos = src->head.next;
+ while (pos != &src->head) {
+ const struct poly_node *node =
+ list_entry(pos, const struct poly_node, link);
+ if (!poly_vec_add_term(&tmp, node->term.coef, node->term.exp)) {
+ poly_vec_destroy(&tmp);
+ return false;
+ }
+ pos = pos->next;
+ }
+
+ __poly_vec_replace(dst, &tmp);
+ return true;
+}
+
+static inline bool poly_list_from_vec(struct poly_list *dst,
+ const struct poly_vec *src)
+{
+ struct poly_list tmp;
+ poly_list_init(&tmp);
+
+ for (size_t i = 0; i < src->terms.size; ++i) {
+ const struct poly_term *term =
+ vec_at_const(&src->terms, i);
+ if (!poly_list_add_term(&tmp, term->coef, term->exp)) {
+ poly_list_destroy(&tmp);
+ return false;
+ }
+ }
+
+ __poly_list_replace(dst, &tmp);
+ return true;
+}
+
+
+/*
+ * ============================================================
+ * Arithmetic
+ * ============================================================
+ *
+ * dst may alias lhs or rhs unless otherwise documented.
+ */
+
+static inline bool __poly_vec_add_scaled(struct poly_vec *dst,
+ const struct poly_vec *src,
+ double scale)
+{
+ for (size_t i = 0; i < src->terms.size; ++i) {
+ const struct poly_term *term =
+ vec_at_const(&src->terms, i);
+ if (!poly_vec_add_term(dst, term->coef * scale, term->exp)) {
+ return false;
+ }
+ }
+ return true;
+}
+
+static inline bool __poly_list_add_scaled(struct poly_list *dst,
+ const struct poly_list *src,
+ double scale)
+{
+ const struct list_head *pos = src->head.next;
+ while (pos != &src->head) {
+ const struct poly_node *node =
+ list_entry(pos, const struct poly_node, link);
+ if (!poly_list_add_term(dst, node->term.coef * scale,
+ node->term.exp)) {
+ return false;
+ }
+ pos = pos->next;
+ }
+ return true;
+}
+
+static inline bool poly_vec_add(struct poly_vec *dst,
+ const struct poly_vec *lhs,
+ const struct poly_vec *rhs)
+{
+ struct poly_vec tmp;
+ poly_vec_init(&tmp);
+ if (!__poly_vec_add_scaled(&tmp, lhs, 1.0) ||
+ !__poly_vec_add_scaled(&tmp, rhs, 1.0)) {
+ poly_vec_destroy(&tmp);
+ return false;
+ }
+ __poly_vec_replace(dst, &tmp);
+ return true;
+}
+
+static inline bool poly_vec_sub(struct poly_vec *dst,
+ const struct poly_vec *lhs,
+ const struct poly_vec *rhs)
+{
+ struct poly_vec tmp;
+ poly_vec_init(&tmp);
+ if (!__poly_vec_add_scaled(&tmp, lhs, 1.0) ||
+ !__poly_vec_add_scaled(&tmp, rhs, -1.0)) {
+ poly_vec_destroy(&tmp);
+ return false;
+ }
+ __poly_vec_replace(dst, &tmp);
+ return true;
+}
+
+static inline bool poly_list_add(struct poly_list *dst,
+ const struct poly_list *lhs,
+ const struct poly_list *rhs)
+{
+ struct poly_list tmp;
+ poly_list_init(&tmp);
+ if (!__poly_list_add_scaled(&tmp, lhs, 1.0) ||
+ !__poly_list_add_scaled(&tmp, rhs, 1.0)) {
+ poly_list_destroy(&tmp);
+ return false;
+ }
+ __poly_list_replace(dst, &tmp);
+ return true;
+}
+
+static inline bool poly_list_sub(struct poly_list *dst,
+ const struct poly_list *lhs,
+ const struct poly_list *rhs)
+{
+ struct poly_list tmp;
+ poly_list_init(&tmp);
+ if (!__poly_list_add_scaled(&tmp, lhs, 1.0) ||
+ !__poly_list_add_scaled(&tmp, rhs, -1.0)) {
+ poly_list_destroy(&tmp);
+ return false;
+ }
+ __poly_list_replace(dst, &tmp);
+ return true;
+}
+
+
+/*
+ * ============================================================
+ * Extended operations
+ * ============================================================
+ */
+
+static inline bool poly_vec_mul(struct poly_vec *dst,
+ const struct poly_vec *lhs,
+ const struct poly_vec *rhs)
+{
+ struct poly_vec tmp;
+ poly_vec_init(&tmp);
+
+ for (size_t i = 0; i < lhs->terms.size; ++i) {
+ const struct poly_term *left =
+ vec_at_const(&lhs->terms, i);
+ for (size_t j = 0; j < rhs->terms.size; ++j) {
+ const struct poly_term *right =
+ vec_at_const(&rhs->terms, j);
+ if (left->exp > UINT_MAX - right->exp ||
+ !poly_vec_add_term(&tmp,
+ left->coef * right->coef,
+ left->exp + right->exp)) {
+ poly_vec_destroy(&tmp);
+ return false;
+ }
+ }
+ }
+
+ __poly_vec_replace(dst, &tmp);
+ return true;
+}
+
+static inline bool poly_list_mul(struct poly_list *dst,
+ const struct poly_list *lhs,
+ const struct poly_list *rhs)
+{
+ struct poly_list tmp;
+ poly_list_init(&tmp);
+
+ const struct list_head *left_pos = lhs->head.next;
+ while (left_pos != &lhs->head) {
+ const struct poly_node *left =
+ list_entry(left_pos, const struct poly_node, link);
+ const struct list_head *right_pos = rhs->head.next;
+ while (right_pos != &rhs->head) {
+ const struct poly_node *right =
+ list_entry(right_pos, const struct poly_node, link);
+ if (left->term.exp > UINT_MAX - right->term.exp ||
+ !poly_list_add_term(&tmp,
+ left->term.coef * right->term.coef,
+ left->term.exp + right->term.exp)) {
+ poly_list_destroy(&tmp);
+ return false;
+ }
+ right_pos = right_pos->next;
+ }
+ left_pos = left_pos->next;
+ }
+
+ __poly_list_replace(dst, &tmp);
+ return true;
+}
+
+
+/*
+ * Differentiate polynomial 'order' times.
+ *
+ * order == 0:
+ * dst = src
+ */
+static inline bool poly_vec_derivative(struct poly_vec *dst,
+ const struct poly_vec *src,
+ unsigned int order)
+{
+ struct poly_vec tmp;
+ poly_vec_init(&tmp);
+
+ for (size_t i = 0; i < src->terms.size; ++i) {
+ const struct poly_term *term =
+ vec_at_const(&src->terms, i);
+ if (term->exp < order) {
+ continue;
+ }
+
+ double coef = term->coef;
+ unsigned int exp = term->exp;
+ for (unsigned int j = 0; j < order; ++j) {
+ coef *= exp;
+ --exp;
+ }
+ if (!poly_vec_add_term(&tmp, coef, exp)) {
+ poly_vec_destroy(&tmp);
+ return false;
+ }
+ }
+
+ __poly_vec_replace(dst, &tmp);
+ return true;
+}
+
+static inline bool poly_list_derivative(struct poly_list *dst,
+ const struct poly_list *src,
+ unsigned int order)
+{
+ struct poly_list tmp;
+ poly_list_init(&tmp);
+
+ const struct list_head *pos = src->head.next;
+ while (pos != &src->head) {
+ const struct poly_node *node =
+ list_entry(pos, const struct poly_node, link);
+ if (node->term.exp >= order) {
+ double coef = node->term.coef;
+ unsigned int exp = node->term.exp;
+ for (unsigned int i = 0; i < order; ++i) {
+ coef *= exp;
+ --exp;
+ }
+ if (!poly_list_add_term(&tmp, coef, exp)) {
+ poly_list_destroy(&tmp);
+ return false;
+ }
+ }
+ pos = pos->next;
+ }
+
+ __poly_list_replace(dst, &tmp);
+ return true;
+}
+
+
+/*
+ * ============================================================
+ * Evaluation
+ * ============================================================
+ */
+
+static inline double poly_vec_eval(const struct poly_vec *poly, double x)
+{
+ double result = 0.0;
+
+ for (size_t i = 0; i < poly->terms.size; ++i) {
+ const struct poly_term *term =
+ vec_at_const(&poly->terms, i);
+ result += term->coef * pow(x, term->exp);
+ }
+ return result;
+}
+
+static inline double poly_list_eval(const struct poly_list *poly, double x)
+{
+ double result = 0.0;
+ const struct list_head *pos = poly->head.next;
+
+ while (pos != &poly->head) {
+ const struct poly_node *node =
+ list_entry(pos, const struct poly_node, link);
+ result += node->term.coef * pow(x, node->term.exp);
+ pos = pos->next;
+ }
+ return result;
+}
+
+
+/*
+ * ============================================================
+ * Comparison
+ * ============================================================
+ *
+ * eps controls floating-point coefficient comparison.
+ */
+
+static inline bool poly_vec_equal(const struct poly_vec *lhs,
+ const struct poly_vec *rhs,
+ double eps)
+{
+ if (lhs->terms.size != rhs->terms.size) {
+ return false;
+ }
+
+ for (size_t i = 0; i < lhs->terms.size; ++i) {
+ const struct poly_term *left =
+ vec_at_const(&lhs->terms, i);
+ const struct poly_term *right =
+ vec_at_const(&rhs->terms, i);
+ if (left->exp != right->exp ||
+ !(fabs(left->coef - right->coef) <= eps)) {
+ return false;
+ }
+ }
+ return true;
+}
+
+static inline bool poly_list_equal(const struct poly_list *lhs,
+ const struct poly_list *rhs,
+ double eps)
+{
+ if (lhs->size != rhs->size) {
+ return false;
+ }
+
+ const struct list_head *left_pos = lhs->head.next;
+ const struct list_head *right_pos = rhs->head.next;
+ while (left_pos != &lhs->head) {
+ const struct poly_node *left =
+ list_entry(left_pos, const struct poly_node, link);
+ const struct poly_node *right =
+ list_entry(right_pos, const struct poly_node, link);
+ if (left->term.exp != right->term.exp ||
+ !(fabs(left->term.coef - right->term.coef) <= eps)) {
+ return false;
+ }
+ left_pos = left_pos->next;
+ right_pos = right_pos->next;
+ }
+ return true;
+}
+
+
+/*
+ * ============================================================
+ * Iteration: sequential representation
+ * ============================================================
+ */
+
+#define poly_vec_for_each(term, poly) \
+ for (size_t __poly_i = 0; \
+ __poly_i < poly_vec_size(poly) && \
+ (((term) = poly_vec_at((poly), __poly_i)), true); \
+ ++__poly_i)
+
+#define poly_vec_for_each_const(term, poly) \
+ for (size_t __poly_i = 0; \
+ __poly_i < poly_vec_size(poly) && \
+ (((term) = poly_vec_at_const((poly), __poly_i)), true); \
+ ++__poly_i)
+
+
+/*
+ * ============================================================
+ * Iteration: linked representation
+ * ============================================================
+ */
+
+#define poly_list_for_each(node, poly) \
+ list_for_each_entry((node), &(poly)->head, link)
+
+#define poly_list_for_each_reverse(node, poly) \
+ list_for_each_entry_reverse((node), &(poly)->head, link)
+
+#define poly_list_for_each_safe(node, next, poly) \
+ list_for_each_entry_safe((node), (next), &(poly)->head, link)
+
+
+#endif /* POLYNOMIAL_H */
diff --git a/lab04/stack.h b/lab04/stack.h
new file mode 100644
index 0000000..06e4d67
--- /dev/null
+++ b/lab04/stack.h
@@ -0,0 +1,219 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+#ifndef STACK_H
+#define STACK_H
+
+/**
+ * @file stack.h
+ * @brief LIFO stack primitives backed by a dynamically sized vector.
+ *
+ * A stack stores elements by value and uses the last vector element as its
+ * top. The element size is fixed when the stack is initialized.
+ */
+
+#include "vec.h"
+
+/**
+ * @brief A generic last-in, first-out stack.
+ */
+typedef struct stack {
+ /** @brief Contiguous storage for the stack elements. */
+ vec container;
+} stack;
+
+/** @name Initialization */
+/** @{ */
+
+/**
+ * @brief Produces an initializer for an empty stack of the given type.
+ * @param type The element type.
+ * @return An initializer for a `stack` object.
+ */
+#define STACK_INIT(type) { \
+ .container = VEC_INIT(type), \
+}
+
+/**
+ * @brief Declares and initializes an empty stack.
+ * @param name The stack variable name.
+ * @param type The element type.
+ */
+#define STACK(name, type) \
+ stack name = STACK_INIT(type)
+
+/**
+ * @brief Initializes an existing stack for elements of `type`.
+ * @param s A pointer to the stack.
+ * @param type The element type.
+ * @post `s` is empty and its element size is `sizeof(type)`.
+ */
+#define stack_init(s, type) \
+ vec_init(&(s)->container, type)
+
+/**
+ * @brief Destroys a stack and releases its allocated storage.
+ * @param s A pointer to the stack.
+ * @pre `s` points to a stack initialized by `STACK` or `stack_init`.
+ */
+static inline void stack_destroy(stack *s)
+{
+ vec_destroy(&s->container);
+}
+
+/** @} */
+
+/** @name Basic properties */
+/** @{ */
+
+/**
+ * @brief Returns the number of elements in the stack.
+ * @param s A pointer to the stack.
+ * @return The number of elements in the stack.
+ * @pre `s` points to an initialized stack.
+ */
+static inline size_t stack_size(const stack *s)
+{
+ return vec_size(&s->container);
+}
+
+/**
+ * @brief Tests whether the stack is empty.
+ * @param s A pointer to the stack.
+ * @return `true` when the stack contains no elements; otherwise `false`.
+ * @pre `s` points to an initialized stack.
+ */
+static inline bool stack_empty(const stack *s)
+{
+ return vec_empty(&s->container);
+}
+
+/**
+ * @brief Removes all elements without releasing the allocated capacity.
+ * @param s A pointer to the stack.
+ * @post The stack is empty and its allocated capacity is unchanged.
+ * @pre `s` points to an initialized stack.
+ */
+static inline void stack_clear(stack *s)
+{
+ vec_clear(&s->container);
+}
+
+/**
+ * @brief Exchanges the contents of two stacks.
+ * @param a A pointer to the first stack.
+ * @param b A pointer to the second stack.
+ * @pre Both stacks are initialized with the same element size.
+ */
+static inline void stack_swap(stack *a, stack *b)
+{
+ vec_swap(&a->container, &b->container);
+}
+
+/** @} */
+
+/** @name Top element */
+/** @{ */
+
+/**
+ * @brief Returns a writable pointer to the top element.
+ * @param s A pointer to the stack.
+ * @return A pointer to the top element.
+ * @pre `s` points to an initialized stack containing at least one element.
+ */
+static inline void *stack_top(stack *s)
+{
+ return vec_back(&s->container);
+}
+
+/**
+ * @brief Returns a read-only pointer to the top element.
+ * @param s A pointer to the stack.
+ * @return A pointer to the top element.
+ * @pre `s` points to an initialized stack containing at least one element.
+ */
+static inline const void *stack_top_const(const stack *s)
+{
+ return vec_back_const(&s->container);
+}
+
+/** @} */
+
+/** @name Insertion and erasure */
+/** @{ */
+
+/**
+ * @brief Pushes one raw element onto the stack.
+ * @param s A pointer to the stack.
+ * @param value A pointer to the element to copy.
+ * @return `true` on success; `false` for invalid input or allocation failure.
+ * @pre `s` points to an initialized stack.
+ */
+static inline bool stack_push(stack *s, const void *value)
+{
+ return vec_push_back(&s->container, value);
+}
+
+/**
+ * @brief Pushes a typed value after checking its size.
+ * @param s A pointer to the stack.
+ * @param value The value to copy onto the stack.
+ * @pre `s` points to an initialized stack whose element type is `typeof(value)`.
+ */
+#define stack_push_value(s, value) ({ \
+ typeof(value) __stack_tmp = (value); \
+ assert(sizeof(__stack_tmp) == \
+ (s)->container.elem_size); \
+ stack_push((s), &__stack_tmp); \
+})
+
+/**
+ * @brief Removes the top element, if one exists.
+ * @param s A pointer to the stack.
+ *
+ * Like `std::stack::pop`, this function does not return the removed value.
+ * @pre `s` points to an initialized stack.
+ */
+static inline void stack_pop(stack *s)
+{
+ vec_pop_back(&s->container);
+}
+
+/**
+ * @brief Removes the top element and copies it to `out`.
+ * @param s A pointer to the stack.
+ * @param out A pointer receiving the removed element.
+ * @return `true` on success; `false` when the stack is empty or invalid.
+ * @pre `s` points to an initialized stack.
+ */
+static inline bool stack_pop_copy(stack *s, void *out)
+{
+ return vec_pop_back_copy(&s->container, out);
+}
+
+/** @} */
+
+/** @name Typed access helpers */
+/** @{ */
+
+/**
+ * @brief Returns the top element converted to a writable typed pointer.
+ * @param s A pointer to the stack.
+ * @param type The element type.
+ * @pre `s` points to an initialized, non-empty stack.
+ */
+#define stack_top_as(s, type) \
+ ((type *)stack_top((s)))
+
+/**
+ * @brief Returns the top element converted to a read-only typed pointer.
+ * @param s A pointer to the stack.
+ * @param type The element type.
+ * @pre `s` points to an initialized, non-empty stack.
+ */
+#define stack_top_as_const(s, type) \
+ ((const type *)stack_top_const((s)))
+
+/** @} */
+
+#endif /* STACK_H */
diff --git a/lab04/tests/Makefile b/lab04/tests/Makefile
new file mode 100644
index 0000000..5724f6f
--- /dev/null
+++ b/lab04/tests/Makefile
@@ -0,0 +1,18 @@
+CC ?= gcc
+CFLAGS ?= -std=gnu11 -Wall -Wextra -Werror -O2
+LDLIBS ?= -lm
+
+TARGET := test_runner
+
+.PHONY: all run clean
+
+all: $(TARGET)
+
+$(TARGET): test.c ../container_of.h ../list.h ../vec.h ../polynomial.h ../expression.h ../stack.h
+ $(CC) $(CFLAGS) -I.. test.c $(LDLIBS) -o $@
+
+run: $(TARGET)
+ ./$(TARGET)
+
+clean:
+ rm -f $(TARGET)
diff --git a/lab04/tests/test.c b/lab04/tests/test.c
new file mode 100644
index 0000000..c10b130
--- /dev/null
+++ b/lab04/tests/test.c
@@ -0,0 +1,497 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+#include "container_of.h"
+#include "expression.h"
+#include "list.h"
+#include "polynomial.h"
+#include "vec.h"
+
+#include <math.h>
+#include <stdbool.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+
+#define CHECK(condition) \
+ do { \
+ if (!(condition)) { \
+ fprintf(stderr, " failed: %s:%d: %s\n", \
+ __FILE__, __LINE__, #condition); \
+ return false; \
+ } \
+ } while (0)
+
+static int compare_int(const void *lhs, const void *rhs)
+{
+ int left = *(const int *)lhs;
+ int right = *(const int *)rhs;
+ return (left > right) - (left < right);
+}
+
+static bool test_vec_lifecycle_and_access(void)
+{
+ struct vec vector;
+ vec_init(&vector, int);
+ CHECK(vec_empty(&vector));
+ CHECK(vec_elem_size(&vector) == sizeof(int));
+
+ int values[] = { 10, 20, 30 };
+ for (size_t i = 0; i < sizeof(values) / sizeof(values[0]); ++i) {
+ CHECK(vec_push_back(&vector, &values[i]));
+ }
+ CHECK(vec_size(&vector) == 3);
+ CHECK(vec_capacity(&vector) >= 3);
+ CHECK(*(int *)vec_front(&vector) == 10);
+ CHECK(*(int *)vec_back(&vector) == 30);
+ CHECK(*(int *)vec_at_checked(&vector, 1) == 20);
+ CHECK(vec_at_checked(&vector, 3) == NULL);
+
+ vec_destroy(&vector);
+ CHECK(vector.data == NULL);
+ CHECK(vector.size == 0);
+ CHECK(vector.capacity == 0);
+ CHECK(vector.elem_size == 0);
+ return true;
+}
+
+static bool test_vec_insert_erase_and_assign(void)
+{
+ struct vec vector;
+ vec_init(&vector, int);
+ int initial[] = { 1, 3 };
+ CHECK(vec_append(&vector, initial, 2));
+
+ int two = 2;
+ CHECK(vec_insert(&vector, 1, &two));
+ int tail[] = { 4, 5 };
+ CHECK(vec_insert_range(&vector, vector.size, tail, 2));
+ CHECK(vector.size == 5);
+ CHECK(*(int *)vec_at(&vector, 0) == 1);
+ CHECK(*(int *)vec_at(&vector, 4) == 5);
+
+ vec_erase(&vector, 1);
+ CHECK(*(int *)vec_at(&vector, 1) == 3);
+ vec_erase_n(&vector, 1, 2);
+ CHECK(vector.size == 2);
+ CHECK(*(int *)vec_at(&vector, 0) == 1);
+ CHECK(*(int *)vec_at(&vector, 1) == 5);
+
+ int replacement[] = { 7, 8, 9 };
+ CHECK(vec_assign_range(&vector, replacement, 3));
+ CHECK(vector.size == 3);
+ int repeated = 4;
+ CHECK(vec_assign_n(&vector, 2, &repeated));
+ CHECK(vector.size == 2);
+ CHECK(*(int *)vec_at(&vector, 0) == 4);
+ CHECK(*(int *)vec_at(&vector, 1) == 4);
+
+ vec_destroy(&vector);
+ return true;
+}
+
+static bool test_vec_resize_capacity_and_swap(void)
+{
+ struct vec vector;
+ vec_init(&vector, int);
+ CHECK(vec_reserve(&vector, 16));
+ CHECK(vector.capacity >= 16);
+ CHECK(vec_resize_zero(&vector, 4));
+ for (size_t i = 0; i < vector.size; ++i) {
+ CHECK(*(int *)vec_at(&vector, i) == 0);
+ }
+
+ int value = 11;
+ CHECK(vec_assign_n(&vector, 1, &value));
+ CHECK(vec_resize(&vector, 4));
+ CHECK(*(int *)vec_at(&vector, 0) == 11);
+ CHECK(vec_resize(&vector, 1));
+ CHECK(vec_shrink_to_fit(&vector));
+ CHECK(vector.capacity == vector.size);
+
+ struct vec other;
+ vec_init(&other, int);
+ int other_value = 22;
+ CHECK(vec_push_back(&other, &other_value));
+ vec_swap(&vector, &other);
+ CHECK(*(int *)vec_front(&vector) == 22);
+ CHECK(*(int *)vec_front(&other) == 11);
+ CHECK(!vec_reserve(&vector, SIZE_MAX));
+
+ vec_destroy(&vector);
+ vec_destroy(&other);
+ return true;
+}
+
+static bool test_vec_iterators_and_comparison(void)
+{
+ struct vec vector;
+ vec_init(&vector, int);
+ int values[] = { 1, 2, 3 };
+ CHECK(vec_append(&vector, values, 3));
+
+ int *begin = vec_begin_as(&vector, int);
+ int *end = vec_end_as(&vector, int);
+ CHECK(vec_iter_distance(begin, end) == 3);
+ CHECK(vec_iter_distance((int *)NULL, (int *)NULL) == 0);
+ CHECK(*begin == 1);
+ CHECK(*(end - 1) == 3);
+
+ struct vec_reverse_iterator reverse = vec_rbegin(&vector);
+ struct vec_reverse_iterator reverse_end = vec_rend(&vector);
+ CHECK(vec_reverse_distance(reverse, reverse_end) == 3);
+ CHECK(*(int *)vec_reverse_deref(reverse) == 3);
+ vec_reverse_next(&reverse);
+ CHECK(*(int *)vec_reverse_deref(reverse) == 2);
+ vec_reverse_next(&reverse);
+ CHECK(*(int *)vec_reverse_deref(reverse) == 1);
+
+ struct vec same;
+ vec_init(&same, int);
+ CHECK(vec_append(&same, values, 3));
+ CHECK(vec_equal(&vector, &same, compare_int));
+ CHECK(vec_compare(&vector, &same, compare_int) == 0);
+ vec_pop_back(&same);
+ CHECK(vec_compare(&same, &vector, compare_int) < 0);
+
+ vec_destroy(&vector);
+ vec_destroy(&same);
+ return true;
+}
+
+struct list_test_item {
+ int value;
+ struct list_head link;
+};
+
+static bool test_list_and_container_of(void)
+{
+ LIST_HEAD(head);
+ struct list_test_item first = { .value = 1 };
+ struct list_test_item second = { .value = 2 };
+ struct list_test_item third = { .value = 3 };
+ INIT_LIST_HEAD(&first.link);
+ INIT_LIST_HEAD(&second.link);
+ INIT_LIST_HEAD(&third.link);
+
+ list_add(&first.link, &head);
+ list_add_tail(&second.link, &head);
+ list_add_tail(&third.link, &head);
+ CHECK(!list_empty(&head));
+ CHECK(list_is_first(&first.link, &head));
+ CHECK(list_is_last(&third.link, &head));
+ CHECK(list_entry(head.next, struct list_test_item, link)->value == 1);
+ CHECK(list_entry(head.prev, struct list_test_item, link)->value == 3);
+
+ struct list_test_item *cursor;
+ int expected = 1;
+ list_for_each_entry(cursor, &head, link) {
+ CHECK(cursor->value == expected);
+ ++expected;
+ }
+ list_move_tail(&first.link, &head);
+ CHECK(list_entry(head.prev, struct list_test_item, link)->value == 1);
+ list_del(&second.link);
+ CHECK(list_entry(head.next, struct list_test_item, link)->value == 3);
+ CHECK(list_entry_is_head(list_entry(head.next, struct list_test_item, link),
+ &head, link) == false);
+ return true;
+}
+
+static bool test_poly_vec_normalization(void)
+{
+ struct poly_vec poly;
+ poly_vec_init(&poly);
+ CHECK(poly_vec_add_term(&poly, 3.0, 2));
+ CHECK(poly_vec_add_term(&poly, 1.0, 5));
+ CHECK(poly_vec_add_term(&poly, 2.0, 2));
+ CHECK(poly_vec_size(&poly) == 2);
+ CHECK(poly_vec_at_const(&poly, 0)->exp == 5);
+ CHECK(poly_vec_at_const(&poly, 0)->coef == 1.0);
+ CHECK(poly_vec_at_const(&poly, 1)->exp == 2);
+ CHECK(poly_vec_at_const(&poly, 1)->coef == 5.0);
+ CHECK(poly_vec_set_term(&poly, 0.0, 5));
+ CHECK(!poly_vec_get_term(&poly, 5, &(double){ 0.0 }));
+ CHECK(poly_vec_remove_term(&poly, 2));
+ CHECK(poly_vec_empty(&poly));
+ poly_vec_destroy(&poly);
+ return true;
+}
+
+static bool test_poly_vec_add_sub_and_alias(void)
+{
+ struct poly_vec a;
+ struct poly_vec b;
+ struct poly_vec result;
+ poly_vec_init(&a);
+ poly_vec_init(&b);
+ poly_vec_init(&result);
+ CHECK(poly_vec_add_term(&a, 3.0, 2));
+ CHECK(poly_vec_add_term(&a, 2.0, 1));
+ CHECK(poly_vec_add_term(&a, 1.0, 0));
+ CHECK(poly_vec_add_term(&b, 1.0, 2));
+ CHECK(poly_vec_add_term(&b, -2.0, 1));
+ CHECK(poly_vec_add_term(&b, 4.0, 0));
+
+ CHECK(poly_vec_add(&result, &a, &b));
+ CHECK(poly_vec_equal(&result, &b, 0.0) == false);
+ CHECK(poly_vec_get_term(&result, 2, &(double){ 0.0 }));
+ CHECK(result.terms.size == 2);
+ CHECK(poly_vec_at_const(&result, 0)->coef == 4.0);
+ CHECK(poly_vec_at_const(&result, 1)->exp == 0);
+ CHECK(poly_vec_at_const(&result, 1)->coef == 5.0);
+
+ CHECK(poly_vec_sub(&result, &a, &b));
+ CHECK(poly_vec_at_const(&result, 0)->coef == 2.0);
+ CHECK(poly_vec_at_const(&result, 1)->coef == 4.0);
+ CHECK(poly_vec_at_const(&result, 2)->coef == -3.0);
+
+ CHECK(poly_vec_add(&a, &a, &b));
+ CHECK(a.terms.size == 2);
+ CHECK(poly_vec_at_const(&a, 0)->coef == 4.0);
+ CHECK(poly_vec_at_const(&a, 1)->coef == 5.0);
+
+ poly_vec_destroy(&a);
+ poly_vec_destroy(&b);
+ poly_vec_destroy(&result);
+ return true;
+}
+
+static bool test_poly_vec_mul_derivative_and_eval(void)
+{
+ struct poly_vec x_plus_one;
+ struct poly_vec x_minus_one;
+ struct poly_vec result;
+ struct poly_vec derivative;
+ poly_vec_init(&x_plus_one);
+ poly_vec_init(&x_minus_one);
+ poly_vec_init(&result);
+ poly_vec_init(&derivative);
+ CHECK(poly_vec_add_term(&x_plus_one, 1.0, 1));
+ CHECK(poly_vec_add_term(&x_plus_one, 1.0, 0));
+ CHECK(poly_vec_add_term(&x_minus_one, 1.0, 1));
+ CHECK(poly_vec_add_term(&x_minus_one, -1.0, 0));
+ CHECK(poly_vec_mul(&result, &x_plus_one, &x_minus_one));
+ CHECK(result.terms.size == 2);
+ CHECK(poly_vec_at_const(&result, 0)->exp == 2);
+ CHECK(poly_vec_at_const(&result, 0)->coef == 1.0);
+ CHECK(poly_vec_at_const(&result, 1)->exp == 0);
+ CHECK(poly_vec_at_const(&result, 1)->coef == -1.0);
+ CHECK(poly_vec_derivative(&derivative, &result, 1));
+ CHECK(derivative.terms.size == 1);
+ CHECK(poly_vec_at_const(&derivative, 0)->coef == 2.0);
+ CHECK(poly_vec_eval(&result, 3.0) == 8.0);
+
+ poly_vec_destroy(&x_plus_one);
+ poly_vec_destroy(&x_minus_one);
+ poly_vec_destroy(&result);
+ poly_vec_destroy(&derivative);
+ return true;
+}
+
+static bool test_poly_list_normalization_and_conversion(void)
+{
+ struct poly_list list;
+ struct poly_vec vector;
+ struct poly_list copy;
+ poly_list_init(&list);
+ poly_vec_init(&vector);
+ poly_list_init(&copy);
+ CHECK(poly_list_add_term(&list, 2.0, 1));
+ CHECK(poly_list_add_term(&list, 5.0, 4));
+ CHECK(poly_list_add_term(&list, 3.0, 1));
+ CHECK(poly_list_size(&list) == 2);
+ CHECK(poly_list_get_term(&list, 1, &(double){ 0.0 }));
+ CHECK(list_entry(list.head.next, struct poly_node, link)->term.exp == 4);
+ CHECK(poly_vec_from_list(&vector, &list));
+ CHECK(poly_vec_size(&vector) == 2);
+ CHECK(poly_vec_at_const(&vector, 0)->exp == 4);
+ CHECK(poly_vec_at_const(&vector, 1)->coef == 5.0);
+ CHECK(poly_list_from_vec(&copy, &vector));
+ CHECK(poly_list_equal(&list, &copy, 0.0));
+ CHECK(poly_list_remove_term(&list, 4));
+ CHECK(poly_list_size(&list) == 1);
+
+ poly_list_destroy(&list);
+ poly_vec_destroy(&vector);
+ poly_list_destroy(&copy);
+ return true;
+}
+
+static bool test_poly_list_arithmetic_and_alias(void)
+{
+ struct poly_list a;
+ struct poly_list b;
+ struct poly_list result;
+ struct poly_list derivative;
+ poly_list_init(&a);
+ poly_list_init(&b);
+ poly_list_init(&result);
+ poly_list_init(&derivative);
+ CHECK(poly_list_add_term(&a, 3.0, 2));
+ CHECK(poly_list_add_term(&a, 1.0, 0));
+ CHECK(poly_list_add_term(&b, 1.0, 2));
+ CHECK(poly_list_add_term(&b, -1.0, 0));
+ CHECK(poly_list_add(&result, &a, &b));
+ double coefficient;
+ CHECK(poly_list_get_term(&result, 2, &coefficient));
+ CHECK(coefficient == 4.0);
+ CHECK(!poly_list_get_term(&result, 0, &coefficient));
+ CHECK(poly_list_sub(&result, &a, &b));
+ CHECK(poly_list_get_term(&result, 0, &coefficient));
+ CHECK(coefficient == 2.0);
+ CHECK(poly_list_derivative(&derivative, &a, 1));
+ CHECK(poly_list_get_term(&derivative, 1, &coefficient));
+ CHECK(coefficient == 6.0);
+ CHECK(poly_list_eval(&a, 2.0) == 13.0);
+ CHECK(poly_list_add(&a, &a, &b));
+ CHECK(poly_list_get_term(&a, 2, &coefficient));
+ CHECK(coefficient == 4.0);
+
+ poly_list_destroy(&a);
+ poly_list_destroy(&b);
+ poly_list_destroy(&result);
+ poly_list_destroy(&derivative);
+ return true;
+}
+
+static bool test_expression_nested_precedence_and_variables(void)
+{
+ struct expression_context context;
+ struct expression_error error;
+ double result;
+ expression_init(&context);
+ CHECK(expression_collect_variables(&context,
+ "-(A + 2.5) * (B - (-C + 4)) / 2", &error));
+ CHECK(context.variables.size == 3);
+ CHECK(expression_set_variable(&context, "A", 3.0));
+ CHECK(expression_set_variable(&context, "B", 10.0));
+ CHECK(expression_set_variable(&context, "C", 2.0));
+ CHECK(expression_eval(&context,
+ "-(A + 2.5) * (B - (-C + 4)) / 2", &result, &error));
+ CHECK(fabs(result + 22.0) < 1e-12);
+ expression_destroy(&context);
+ return true;
+}
+
+static bool test_expression_variable_dedup_and_update(void)
+{
+ struct expression_context context;
+ struct expression_error error;
+ double result;
+ expression_init(&context);
+ CHECK(expression_collect_variables(&context,
+ "A1 + A1 * B2 - (B2 / 2) + C", &error));
+ CHECK(context.variables.size == 3);
+ CHECK(expression_set_variable(&context, "A1", 4.0));
+ CHECK(expression_set_variable(&context, "B2", 6.0));
+ CHECK(expression_set_variable(&context, "C", 1.0));
+ CHECK(expression_eval(&context,
+ "A1 + A1 * B2 - (B2 / 2) + C", &result, &error));
+ CHECK(fabs(result - 26.0) < 1e-12);
+ CHECK(expression_set_variable(&context, "B2", 10.0));
+ CHECK(expression_eval(&context,
+ "A1 + A1 * B2 - (B2 / 2) + C", &result, &error));
+ CHECK(result == 40.0);
+ expression_destroy(&context);
+ return true;
+}
+
+static bool test_expression_unary_and_decimal_values(void)
+{
+ struct expression_context context;
+ struct expression_error error;
+ double result;
+ expression_init(&context);
+ CHECK(expression_collect_variables(&context,
+ "--5 + -(+2.5) * (3 - -1) + .5", &error));
+ CHECK(expression_eval(&context,
+ "--5 + -(+2.5) * (3 - -1) + .5", &result, &error));
+ CHECK(fabs(result + 4.5) < 1e-12);
+ expression_destroy(&context);
+ return true;
+}
+
+static bool test_expression_deep_parentheses_and_associativity(void)
+{
+ struct expression_context context;
+ struct expression_error error;
+ double result;
+ expression_init(&context);
+ CHECK(expression_collect_variables(&context,
+ "1 - 2 - 3 + 4 * (5 + (6 - (7 - 8)))", &error));
+ CHECK(expression_eval(&context,
+ "1 - 2 - 3 + 4 * (5 + (6 - (7 - 8)))", &result, &error));
+ CHECK(fabs(result - 44.0) < 1e-12);
+ expression_destroy(&context);
+ return true;
+}
+
+static bool test_expression_error_paths(void)
+{
+ struct expression_context context;
+ struct expression_error error;
+ double result;
+ expression_init(&context);
+ CHECK(expression_collect_variables(&context, "X + 1", &error));
+ CHECK(!expression_eval(&context, "X + 1", &result, &error));
+ CHECK(error.code == EXPRESSION_UNSET_VARIABLE);
+ CHECK(expression_set_variable(&context, "X", 2.0));
+ CHECK(!expression_eval(&context, "X / (3 - 3)", &result, &error));
+ CHECK(error.code == EXPRESSION_DIVISION_BY_ZERO);
+ CHECK(!expression_eval(&context, "X + (2 * 3", &result, &error));
+ CHECK(error.code == EXPRESSION_PAREN_ERROR);
+ CHECK(!expression_collect_variables(&context, "X @ 2", &error));
+ CHECK(error.code == EXPRESSION_SYNTAX_ERROR);
+ expression_destroy(&context);
+ return true;
+}
+
+struct test_case {
+ const char *name;
+ bool (*function)(void);
+};
+
+int main(void)
+{
+ const struct test_case tests[] = {
+ { "vec lifecycle and access", test_vec_lifecycle_and_access },
+ { "vec insert, erase and assign", test_vec_insert_erase_and_assign },
+ { "vec resize, capacity and swap", test_vec_resize_capacity_and_swap },
+ { "vec iterators and comparison", test_vec_iterators_and_comparison },
+ { "list and container_of", test_list_and_container_of },
+ { "poly_vec normalization", test_poly_vec_normalization },
+ { "poly_vec add, sub and alias", test_poly_vec_add_sub_and_alias },
+ { "poly_vec multiply, derivative and eval",
+ test_poly_vec_mul_derivative_and_eval },
+ { "poly_list normalization and conversion",
+ test_poly_list_normalization_and_conversion },
+ { "poly_list arithmetic and alias",
+ test_poly_list_arithmetic_and_alias },
+ { "expression nested precedence and variables",
+ test_expression_nested_precedence_and_variables },
+ { "expression variable dedup and update",
+ test_expression_variable_dedup_and_update },
+ { "expression unary and decimal values",
+ test_expression_unary_and_decimal_values },
+ { "expression deep parentheses and associativity",
+ test_expression_deep_parentheses_and_associativity },
+ { "expression error paths", test_expression_error_paths },
+ };
+ size_t failures = 0;
+
+ for (size_t i = 0; i < sizeof(tests) / sizeof(tests[0]); ++i) {
+ printf("[%zu/%zu] %s\n", i + 1,
+ sizeof(tests) / sizeof(tests[0]), tests[i].name);
+ if (tests[i].function()) {
+ puts(" passed");
+ } else {
+ ++failures;
+ puts(" failed");
+ }
+ }
+ printf("\n%zu/%zu tests passed\n",
+ sizeof(tests) / sizeof(tests[0]) - failures,
+ sizeof(tests) / sizeof(tests[0]));
+ return failures == 0 ? EXIT_SUCCESS : EXIT_FAILURE;
+}
diff --git a/lab04/tui.c b/lab04/tui.c
new file mode 100644
index 0000000..d5abdd2
--- /dev/null
+++ b/lab04/tui.c
@@ -0,0 +1,190 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+#include "tui.h"
+
+#include <poll.h>
+#include <stdarg.h>
+#include <stdio.h>
+#include <termios.h>
+#include <unistd.h>
+
+struct tui_state {
+ struct termios saved_termios;
+ bool termios_saved;
+ bool raw_mode;
+ bool alternate_screen;
+};
+
+static struct tui_state tui_state;
+
+static int tui_read_byte(void)
+{
+ unsigned char byte;
+ ssize_t count = read(STDIN_FILENO, &byte, sizeof(byte));
+
+ return count == (ssize_t)sizeof(byte) ? byte : -1;
+}
+
+bool tui_init(void)
+{
+ if (tcgetattr(STDIN_FILENO, &tui_state.saved_termios) < 0) {
+ return false;
+ }
+ tui_state.termios_saved = true;
+
+ struct termios raw = tui_state.saved_termios;
+ cfmakeraw(&raw);
+
+ raw.c_oflag |= OPOST | ONLCR;
+
+ if (tcsetattr(STDIN_FILENO, TCSAFLUSH, &raw) < 0) {
+ tui_state.termios_saved = false;
+ return false;
+ }
+ tui_state.raw_mode = true;
+
+ /* DEC private mode 1049: 切换到备用屏幕缓冲区 */
+ fputs("\033[?1049h\033[H\033[?25l", stdout);
+ fflush(stdout);
+ tui_state.alternate_screen = true;
+ return true;
+}
+
+void tui_shutdown(void)
+{
+ if (tui_state.alternate_screen) {
+ tui_show_cursor();
+ fputs("\033[?1049l", stdout);
+ fflush(stdout);
+ tui_state.alternate_screen = false;
+ }
+
+ if (tui_state.raw_mode && tui_state.termios_saved) {
+ tcsetattr(STDIN_FILENO, TCSAFLUSH, &tui_state.saved_termios);
+ tui_state.raw_mode = false;
+ }
+}
+
+void tui_clear(void)
+{
+ fputs("\033[2J\033[H", stdout);
+}
+
+void tui_hide_cursor(void)
+{
+ fputs("\033[?25l", stdout);
+}
+
+void tui_show_cursor(void)
+{
+ fputs("\033[?25h", stdout);
+}
+
+void tui_printf(const char *format, ...)
+{
+ va_list arguments;
+
+ va_start(arguments, format);
+ vprintf(format, arguments);
+ va_end(arguments);
+}
+
+struct tui_event tui_read_key(void)
+{
+ int character = tui_read_byte();
+ if (character < 0) {
+ return (struct tui_event){ .kind = TUI_KEY_ESCAPE };
+ }
+
+ if (character == '\033') {
+ struct pollfd input = {
+ .fd = STDIN_FILENO,
+ .events = POLLIN,
+ };
+ if (poll(&input, 1, 25) <= 0) {
+ return (struct tui_event){ .kind = TUI_KEY_ESCAPE };
+ }
+
+ int sequence = tui_read_byte();
+ if (sequence == '[') {
+ int code = tui_read_byte();
+ switch (code) {
+ case 'A':
+ return (struct tui_event){ .kind = TUI_KEY_UP };
+ case 'B':
+ return (struct tui_event){ .kind = TUI_KEY_DOWN };
+ case 'C':
+ return (struct tui_event){ .kind = TUI_KEY_RIGHT };
+ case 'D':
+ return (struct tui_event){ .kind = TUI_KEY_LEFT };
+ default:
+ break;
+ }
+ }
+ return (struct tui_event){ .kind = TUI_KEY_ESCAPE };
+ }
+
+ if (character == '\r' || character == '\n') {
+ return (struct tui_event){ .kind = TUI_KEY_ENTER };
+ }
+ if (character == '\b' || character == 127) {
+ return (struct tui_event){ .kind = TUI_KEY_BACKSPACE };
+ }
+ return (struct tui_event){
+ .kind = TUI_KEY_CHARACTER,
+ .character = character,
+ };
+}
+
+bool tui_read_line(const char *prompt, char *buffer, size_t capacity)
+{
+ size_t length = 0;
+
+ if (capacity == 0) {
+ return false;
+ }
+ tui_show_cursor();
+ buffer[0] = '\0';
+ if (prompt && *prompt) {
+ tui_printf("%s", prompt);
+ }
+ fflush(stdout);
+
+ for (;;) {
+ struct tui_event event = tui_read_key();
+ if (event.kind == TUI_KEY_ENTER) {
+ fputc('\n', stdout);
+ tui_hide_cursor();
+ return true;
+ }
+ if (event.kind == TUI_KEY_ESCAPE) {
+ fputc('\n', stdout);
+ tui_hide_cursor();
+ return false;
+ }
+ if (event.kind == TUI_KEY_BACKSPACE) {
+ if (length > 0) {
+ buffer[--length] = '\0';
+ fputs("\b \b", stdout);
+ fflush(stdout);
+ }
+ continue;
+ }
+ if (event.kind == TUI_KEY_CHARACTER &&
+ event.character >= 32 && event.character != 127 &&
+ length + 1 < capacity) {
+ buffer[length++] = (char)event.character;
+ buffer[length] = '\0';
+ fputc(event.character, stdout);
+ fflush(stdout);
+ }
+ }
+}
+
+void tui_wait(void)
+{
+ fputs("\n\n按任意键返回...", stdout);
+ fflush(stdout);
+ (void)tui_read_key();
+}
diff --git a/lab04/tui.h b/lab04/tui.h
new file mode 100644
index 0000000..e28e698
--- /dev/null
+++ b/lab04/tui.h
@@ -0,0 +1,38 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+#ifndef TUI_H
+#define TUI_H
+
+#include <stdbool.h>
+#include <stddef.h>
+
+enum tui_key_kind {
+ TUI_KEY_CHARACTER,
+ TUI_KEY_UP,
+ TUI_KEY_DOWN,
+ TUI_KEY_LEFT,
+ TUI_KEY_RIGHT,
+ TUI_KEY_ENTER,
+ TUI_KEY_ESCAPE,
+ TUI_KEY_BACKSPACE,
+};
+
+struct tui_event {
+ enum tui_key_kind kind;
+ int character;
+};
+
+bool tui_init(void);
+void tui_shutdown(void);
+
+void tui_clear(void);
+void tui_hide_cursor(void);
+void tui_show_cursor(void);
+void tui_printf(const char *format, ...);
+
+struct tui_event tui_read_key(void);
+bool tui_read_line(const char *prompt, char *buffer, size_t capacity);
+void tui_wait(void);
+
+#endif /* TUI_H */
diff --git a/lab04/ui.c b/lab04/ui.c
new file mode 100644
index 0000000..a6f6b1d
--- /dev/null
+++ b/lab04/ui.c
@@ -0,0 +1,1543 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+#include "ui.h"
+
+#include "polynomial.h"
+#include "expression.h"
+#include "tui.h"
+
+#include <ctype.h>
+#include <errno.h>
+#include <inttypes.h>
+#include <limits.h>
+#include <math.h>
+#include <stdarg.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <string.h>
+#include <sys/ioctl.h>
+#include <unistd.h>
+
+#define STYLE_RESET "\033[0m"
+#define STYLE_BOLD "\033[1m"
+#define STYLE_DIM "\033[2m"
+#define STYLE_SELECTED "\033[7;1m"
+#define COLOR_CYAN "\033[1;36m"
+#define COLOR_GREEN "\033[1;32m"
+#define COLOR_RED "\033[1;31m"
+#define COLOR_YELLOW "\033[1;33m"
+
+enum ui_vector_result_kind {
+ UI_VECTOR_RESULT_NONE,
+ UI_VECTOR_RESULT_VALUE,
+ UI_VECTOR_RESULT_COSINE,
+};
+
+struct ui_state {
+ struct vec linear;
+
+ struct vec vector_a;
+ struct vec vector_b;
+ struct vec vector_result;
+ enum ui_vector_result_kind vector_result_kind;
+ double vector_cosine;
+
+ struct poly_vec poly_vec_a;
+ struct poly_vec poly_vec_b;
+ struct poly_vec poly_vec_result;
+ bool poly_vec_result_valid;
+
+ struct poly_list poly_list_a;
+ struct poly_list poly_list_b;
+ struct poly_list poly_list_result;
+ bool poly_list_result_valid;
+
+ struct expression_context expression;
+ char expression_text[256];
+ double expression_result;
+ bool expression_result_valid;
+
+ char status[256];
+};
+
+static void ui_set_status(struct ui_state *state, const char *format, ...)
+{
+ va_list arguments;
+
+ va_start(arguments, format);
+ vsnprintf(state->status, sizeof(state->status), format, arguments);
+ va_end(arguments);
+}
+
+static void ui_clear_status(struct ui_state *state)
+{
+ state->status[0] = '\0';
+}
+
+/* 计算 UTF-8 字符串在终端中的实际显示列宽（中文字符占 2 列） */
+static size_t ui_str_display_width(const char *str)
+{
+ size_t width = 0;
+ while (*str) {
+ unsigned char c = (unsigned char)*str;
+ if (c < 0x80) {
+ width += 1;
+ str += 1;
+ } else if ((c & 0xE0) == 0xC0) {
+ width += 1;
+ str += 2;
+ } else if ((c & 0xF0) == 0xE0) {
+ width += 2;
+ str += 3;
+ } else if ((c & 0xF8) == 0xF0) {
+ width += 2;
+ str += 4;
+ } else {
+ str += 1;
+ }
+ }
+ return width;
+}
+
+static int ui_terminal_width(void)
+{
+ struct winsize size;
+ if (ioctl(STDOUT_FILENO, TIOCGWINSZ, &size) == 0 && size.ws_col > 0) {
+ return size.ws_col;
+ }
+ return 50;
+}
+
+static void ui_print_rule(char character)
+{
+ int width = ui_terminal_width();
+ for (int i = 0; i < width; ++i) {
+ putchar(character);
+ }
+ putchar('\n');
+}
+
+static void ui_print_centered(const char *text, int width)
+{
+ size_t disp_w = ui_str_display_width(text);
+ int pad = (width > (int)disp_w) ? (width - (int)disp_w) / 2 : 0;
+ for (int i = 0; i < pad; ++i) {
+ putchar(' ');
+ }
+ printf("%s\n", text);
+}
+
+static void ui_print_header(const char *title)
+{
+ int width = ui_terminal_width();
+ printf(COLOR_CYAN);
+ ui_print_rule('=');
+ printf(STYLE_BOLD);
+ ui_print_centered(title, width);
+ printf(STYLE_RESET);
+ printf(COLOR_CYAN);
+ ui_print_rule('=');
+ printf(STYLE_RESET "\n");
+}
+
+static void ui_print_status(const struct ui_state *state)
+{
+ if (state->status[0] != '\0') {
+ printf("\n" STYLE_DIM);
+ ui_print_rule('-');
+ printf(STYLE_RESET);
+ if (strncmp(state->status, "错误", 6) == 0) {
+ printf(COLOR_RED " [!] %s" STYLE_RESET "\n", state->status);
+ } else if (strncmp(state->status, "已取消", 9) == 0) {
+ printf(COLOR_YELLOW " [*] %s" STYLE_RESET "\n", state->status);
+ } else {
+ printf(COLOR_GREEN " [√] %s" STYLE_RESET "\n", state->status);
+ }
+ }
+}
+
+static void ui_print_footer(const char *text)
+{
+ printf("\n" STYLE_DIM);
+ ui_print_rule('-');
+ printf(STYLE_RESET);
+ printf(STYLE_DIM " %s" STYLE_RESET "\n", text);
+}
+
+static void ui_print_menu(const char *const *items,
+ size_t count,
+ size_t selected,
+ const char *zero_item)
+{
+ for (size_t i = 0; i < count; ++i) {
+ if (i == selected) {
+ printf(STYLE_SELECTED " > %zu. %s " STYLE_RESET "\n", i + 1, items[i]);
+ } else {
+ printf(" %zu. %s\n", i + 1, items[i]);
+ }
+ }
+ if (selected == count) {
+ printf(STYLE_SELECTED " > 0. %s " STYLE_RESET "\n", zero_item);
+ } else {
+ printf(STYLE_DIM " 0. %s" STYLE_RESET "\n", zero_item);
+ }
+}
+
+static int ui_menu_input(size_t *selected, size_t count)
+{
+ size_t total = count + 1;
+ struct tui_event event = tui_read_key();
+
+ if (event.kind == TUI_KEY_UP) {
+ *selected = *selected == 0 ? total - 1 : *selected - 1;
+ return -2;
+ }
+ if (event.kind == TUI_KEY_DOWN) {
+ *selected = (*selected + 1) % total;
+ return -2;
+ }
+ if (event.kind == TUI_KEY_CHARACTER &&
+ (event.character == 'k' || event.character == 'K')) {
+ *selected = *selected == 0 ? total - 1 : *selected - 1;
+ return -2;
+ }
+ if (event.kind == TUI_KEY_CHARACTER &&
+ (event.character == 'j' || event.character == 'J')) {
+ *selected = (*selected + 1) % total;
+ return -2;
+ }
+ if (event.kind == TUI_KEY_ENTER) {
+ if (*selected == count) {
+ return -1;
+ }
+ return (int)*selected;
+ }
+ if (event.kind == TUI_KEY_ESCAPE ||
+ (event.kind == TUI_KEY_CHARACTER &&
+ (event.character == 'q' || event.character == 'Q' ||
+ event.character == '0'))) {
+ return -1;
+ }
+ if (event.kind == TUI_KEY_CHARACTER &&
+ event.character >= '1' &&
+ event.character <= '0' + (int)count) {
+ return event.character - '1';
+ }
+ return -2;
+}
+
+static void ui_print_vec_int(const struct vec *vector)
+{
+ printf("[");
+ for (size_t i = 0; i < vector->size; ++i) {
+ if (i != 0) {
+ printf(", ");
+ }
+ printf("%d", *(const int *)vec_at_const(vector, i));
+ }
+ printf("]");
+}
+
+static void ui_print_vec_double(const struct vec *vector)
+{
+ printf("[");
+ for (size_t i = 0; i < vector->size; ++i) {
+ if (i != 0) {
+ printf(", ");
+ }
+ printf("%g", *(const double *)vec_at_const(vector, i));
+ }
+ printf("]");
+}
+
+static void ui_print_poly_term(double coefficient,
+ unsigned int exponent,
+ bool *first)
+{
+ double magnitude = fabs(coefficient);
+
+ if (*first) {
+ if (coefficient < 0.0) {
+ printf("-");
+ }
+ *first = false;
+ } else {
+ printf(coefficient < 0.0 ? " - " : " + ");
+ }
+
+ if (exponent == 0) {
+ printf("%g", magnitude);
+ return;
+ }
+ if (magnitude != 1.0) {
+ printf("%g", magnitude);
+ }
+ printf("x");
+ if (exponent != 1) {
+ printf("^%u", exponent);
+ }
+}
+
+static void ui_print_poly_vec(const struct poly_vec *poly)
+{
+ bool first = true;
+
+ for (size_t i = 0; i < poly->terms.size; ++i) {
+ const struct poly_term *term = vec_at_const(&poly->terms, i);
+ ui_print_poly_term(term->coef, term->exp, &first);
+ }
+ if (first) {
+ printf("0");
+ }
+}
+
+static void ui_print_poly_list(const struct poly_list *poly)
+{
+ bool first = true;
+ const struct list_head *position = poly->head.next;
+
+ while (position != &poly->head) {
+ const struct poly_node *node =
+ list_entry(position, const struct poly_node, link);
+ ui_print_poly_term(node->term.coef, node->term.exp, &first);
+ position = position->next;
+ }
+ if (first) {
+ printf("0");
+ }
+}
+
+static const char *ui_skip_space(const char *text)
+{
+ while (isspace((unsigned char)*text)) {
+ ++text;
+ }
+ return text;
+}
+
+static bool ui_parse_int(const char *text, int *value)
+{
+ char *end;
+ const char *start = ui_skip_space(text);
+
+ errno = 0;
+ long parsed = strtol(start, &end, 10);
+ if (start == end || errno == ERANGE || parsed < INT_MIN ||
+ parsed > INT_MAX || *ui_skip_space(end) != '\0') {
+ return false;
+ }
+ *value = (int)parsed;
+ return true;
+}
+
+static bool ui_parse_size(const char *text, size_t *value)
+{
+ char *end;
+ const char *start = ui_skip_space(text);
+
+ if (*start == '-') {
+ return false;
+ }
+ errno = 0;
+ uintmax_t parsed = strtoumax(start, &end, 10);
+ if (start == end || errno == ERANGE || parsed > SIZE_MAX ||
+ *ui_skip_space(end) != '\0') {
+ return false;
+ }
+ *value = (size_t)parsed;
+ return true;
+}
+
+static bool ui_parse_unsigned(const char *text, unsigned int *value)
+{
+ char *end;
+ const char *start = ui_skip_space(text);
+
+ if (*start == '-') {
+ return false;
+ }
+ errno = 0;
+ uintmax_t parsed = strtoumax(start, &end, 10);
+ if (start == end || errno == ERANGE || parsed > UINT_MAX ||
+ *ui_skip_space(end) != '\0') {
+ return false;
+ }
+ *value = (unsigned int)parsed;
+ return true;
+}
+
+static bool ui_parse_vector(const char *text, struct vec *destination)
+{
+ struct vec temporary;
+ vec_init(&temporary, double);
+ const char *position = text;
+
+ for (;;) {
+ char *end;
+ position = ui_skip_space(position);
+ if (*position == '\0') {
+ break;
+ }
+
+ errno = 0;
+ double value = strtod(position, &end);
+ if (position == end || errno == ERANGE ||
+ !vec_push_back(&temporary, &value)) {
+ vec_destroy(&temporary);
+ return false;
+ }
+ position = end;
+ }
+
+ if (temporary.size == 0) {
+ vec_destroy(&temporary);
+ return false;
+ }
+ vec_swap(destination, &temporary);
+ vec_destroy(&temporary);
+ return true;
+}
+
+static bool ui_parse_poly_vec(const char *text, struct poly_vec *destination)
+{
+ struct poly_vec temporary;
+ poly_vec_init(&temporary);
+ const char *position = text;
+ size_t term_count = 0;
+
+ for (;;) {
+ char *end;
+ position = ui_skip_space(position);
+ if (*position == '\0') {
+ break;
+ }
+
+ errno = 0;
+ double coefficient = strtod(position, &end);
+ if (position == end || errno == ERANGE) {
+ poly_vec_destroy(&temporary);
+ return false;
+ }
+ position = ui_skip_space(end);
+
+ if (*position == '-') {
+ poly_vec_destroy(&temporary);
+ return false;
+ }
+ errno = 0;
+ uintmax_t exponent = strtoumax(position, &end, 10);
+ if (position == end || errno == ERANGE || exponent > UINT_MAX) {
+ poly_vec_destroy(&temporary);
+ return false;
+ }
+ if (!poly_vec_add_term(&temporary, coefficient,
+ (unsigned int)exponent)) {
+ poly_vec_destroy(&temporary);
+ return false;
+ }
+ ++term_count;
+ position = end;
+ }
+
+ if (term_count == 0) {
+ poly_vec_destroy(&temporary);
+ return false;
+ }
+ vec_swap(&destination->terms, &temporary.terms);
+ poly_vec_destroy(&temporary);
+ return true;
+}
+
+static bool ui_parse_poly_list(const char *text, struct poly_list *destination)
+{
+ struct poly_list temporary;
+ poly_list_init(&temporary);
+ const char *position = text;
+ size_t term_count = 0;
+
+ for (;;) {
+ char *end;
+ position = ui_skip_space(position);
+ if (*position == '\0') {
+ break;
+ }
+
+ errno = 0;
+ double coefficient = strtod(position, &end);
+ if (position == end || errno == ERANGE) {
+ poly_list_destroy(&temporary);
+ return false;
+ }
+ position = ui_skip_space(end);
+
+ if (*position == '-') {
+ poly_list_destroy(&temporary);
+ return false;
+ }
+ errno = 0;
+ uintmax_t exponent = strtoumax(position, &end, 10);
+ if (position == end || errno == ERANGE || exponent > UINT_MAX) {
+ poly_list_destroy(&temporary);
+ return false;
+ }
+ if (!poly_list_add_term(&temporary, coefficient,
+ (unsigned int)exponent)) {
+ poly_list_destroy(&temporary);
+ return false;
+ }
+ ++term_count;
+ position = end;
+ }
+
+ if (term_count == 0) {
+ poly_list_destroy(&temporary);
+ return false;
+ }
+ __poly_list_replace(destination, &temporary);
+ return true;
+}
+
+/* 原位输入框：保留界面上下文数据 */
+static bool ui_prompt_inline(const char *title,
+ const char *description,
+ char *buffer,
+ size_t capacity)
+{
+ printf("\n" COLOR_YELLOW "┌── %s" STYLE_RESET "\n", title);
+ if (description != NULL && *description != '\0') {
+ printf(COLOR_YELLOW "│ " STYLE_RESET "%s\n", description);
+ }
+ printf(COLOR_YELLOW "└─> " STYLE_RESET);
+ fflush(stdout);
+ return tui_read_line("", buffer, capacity);
+}
+
+static bool ui_confirm(const char *title, const char *question)
+{
+ char input[16];
+
+ if (!ui_prompt_inline(title, question, input, sizeof(input))) {
+ return false;
+ }
+ return input[0] == 'y' || input[0] == 'Y';
+}
+
+static bool ui_state_init(struct ui_state *state)
+{
+ memset(state, 0, sizeof(*state));
+ vec_init(&state->linear, int);
+ vec_init(&state->vector_a, double);
+ vec_init(&state->vector_b, double);
+ vec_init(&state->vector_result, double);
+ poly_vec_init(&state->poly_vec_a);
+ poly_vec_init(&state->poly_vec_b);
+ poly_vec_init(&state->poly_vec_result);
+ poly_list_init(&state->poly_list_a);
+ poly_list_init(&state->poly_list_b);
+ poly_list_init(&state->poly_list_result);
+ expression_init(&state->expression);
+
+ int linear_values[] = { 10, 20, 30, 40 };
+ double vector_a_values[] = { 1.0, 2.0, 3.0 };
+ double vector_b_values[] = { 4.0, 5.0, 6.0 };
+ for (size_t i = 0; i < sizeof(linear_values) / sizeof(linear_values[0]);
+ ++i) {
+ if (!vec_push_back(&state->linear, &linear_values[i])) {
+ return false;
+ }
+ }
+ for (size_t i = 0; i < sizeof(vector_a_values) / sizeof(vector_a_values[0]);
+ ++i) {
+ if (!vec_push_back(&state->vector_a, &vector_a_values[i]) ||
+ !vec_push_back(&state->vector_b, &vector_b_values[i])) {
+ return false;
+ }
+ }
+
+ if (!poly_vec_add_term(&state->poly_vec_a, 5.0, 4) ||
+ !poly_vec_add_term(&state->poly_vec_a, 3.0, 2) ||
+ !poly_vec_add_term(&state->poly_vec_a, 1.0, 0) ||
+ !poly_vec_add_term(&state->poly_vec_b, 2.0, 3) ||
+ !poly_vec_add_term(&state->poly_vec_b, -3.0, 2) ||
+ !poly_vec_add_term(&state->poly_vec_b, 7.0, 0) ||
+ !poly_list_add_term(&state->poly_list_a, 5.0, 4) ||
+ !poly_list_add_term(&state->poly_list_a, 3.0, 2) ||
+ !poly_list_add_term(&state->poly_list_a, 1.0, 0) ||
+ !poly_list_add_term(&state->poly_list_b, 2.0, 3) ||
+ !poly_list_add_term(&state->poly_list_b, -3.0, 2) ||
+ !poly_list_add_term(&state->poly_list_b, 7.0, 0)) {
+ return false;
+ }
+ return true;
+}
+
+static void ui_state_destroy(struct ui_state *state)
+{
+ vec_destroy(&state->linear);
+ vec_destroy(&state->vector_a);
+ vec_destroy(&state->vector_b);
+ vec_destroy(&state->vector_result);
+ poly_vec_destroy(&state->poly_vec_a);
+ poly_vec_destroy(&state->poly_vec_b);
+ poly_vec_destroy(&state->poly_vec_result);
+ poly_list_destroy(&state->poly_list_a);
+ poly_list_destroy(&state->poly_list_b);
+ poly_list_destroy(&state->poly_list_result);
+ expression_destroy(&state->expression);
+}
+
+static void ui_draw_linear(const struct ui_state *state, size_t selected)
+{
+ static const char *const items[] = {
+ "尾部添加",
+ "指定位置插入",
+ "删除元素",
+ "修改元素",
+ "查找元素",
+ "遍历线性表",
+ "清空线性表",
+ "查看内部状态",
+ };
+
+ tui_clear();
+ ui_print_header("线性表操作");
+ printf(COLOR_CYAN "当前线性表: " STYLE_BOLD);
+ ui_print_vec_int(&state->linear);
+ printf(STYLE_RESET "\n" STYLE_DIM "size = %zu capacity = %zu" STYLE_RESET "\n\n",
+ state->linear.size, state->linear.capacity);
+
+ ui_print_menu(items, sizeof(items) / sizeof(items[0]), selected, "返回");
+ ui_print_status(state);
+ ui_print_footer("↑/↓ 或 j/k 选择 Enter 确认 q/Esc 返回");
+ fflush(stdout);
+}
+
+static bool ui_read_int_value(const char *title,
+ const char *description,
+ int *value,
+ struct ui_state *state)
+{
+ char input[128];
+
+ if (!ui_prompt_inline(title, description, input, sizeof(input))) {
+ ui_set_status(state, "已取消");
+ return false;
+ }
+ if (!ui_parse_int(input, value)) {
+ ui_set_status(state, "错误：输入格式无效");
+ return false;
+ }
+ return true;
+}
+
+static bool ui_read_size_value(const char *title,
+ const char *description,
+ size_t *value,
+ struct ui_state *state)
+{
+ char input[128];
+
+ if (!ui_prompt_inline(title, description, input, sizeof(input))) {
+ ui_set_status(state, "已取消");
+ return false;
+ }
+ if (!ui_parse_size(input, value)) {
+ ui_set_status(state, "错误：输入格式无效");
+ return false;
+ }
+ return true;
+}
+
+static void ui_linear_append(struct ui_state *state)
+{
+ int value;
+
+ if (!ui_read_int_value("尾部添加", "元素值：", &value, state)) {
+ return;
+ }
+ if (!vec_push_back(&state->linear, &value)) {
+ ui_set_status(state, "错误：内存分配失败");
+ return;
+ }
+ ui_set_status(state, "已添加元素 %d", value);
+}
+
+static void ui_linear_insert(struct ui_state *state)
+{
+ size_t index;
+ int value;
+
+ if (!ui_read_size_value("指定位置插入", "插入位置：", &index, state) ||
+ !ui_read_int_value("指定位置插入", "元素值：", &value, state)) {
+ return;
+ }
+ if (index > state->linear.size) {
+ ui_set_status(state, "错误：插入位置超出范围");
+ return;
+ }
+ if (!vec_insert(&state->linear, index, &value)) {
+ ui_set_status(state, "错误：内存分配失败");
+ return;
+ }
+ ui_set_status(state, "已在位置 %zu 插入 %d", index, value);
+}
+
+static void ui_linear_erase(struct ui_state *state)
+{
+ size_t index;
+
+ if (!ui_read_size_value("删除元素", "删除位置：", &index, state)) {
+ return;
+ }
+ if (index >= state->linear.size) {
+ ui_set_status(state, "错误：删除位置超出范围");
+ return;
+ }
+ vec_erase(&state->linear, index);
+ ui_set_status(state, "已删除位置 %zu 的元素", index);
+}
+
+static void ui_linear_modify(struct ui_state *state)
+{
+ size_t index;
+ int value;
+
+ if (!ui_read_size_value("修改元素", "修改位置：", &index, state) ||
+ !ui_read_int_value("修改元素", "新元素值：", &value, state)) {
+ return;
+ }
+ int *element = vec_at_checked(&state->linear, index);
+ if (element == NULL) {
+ ui_set_status(state, "错误：修改位置超出范围");
+ return;
+ }
+ *element = value;
+ ui_set_status(state, "已修改位置 %zu", index);
+}
+
+static void ui_linear_find(struct ui_state *state)
+{
+ int value;
+
+ if (!ui_read_int_value("查找元素", "查找值：", &value, state)) {
+ return;
+ }
+ for (size_t i = 0; i < state->linear.size; ++i) {
+ if (*(const int *)vec_at_const(&state->linear, i) == value) {
+ ui_set_status(state, "元素 %d 位于位置 %zu", value, i);
+ return;
+ }
+ }
+ ui_set_status(state, "未找到元素 %d", value);
+}
+
+static void ui_linear_traverse(const struct ui_state *state)
+{
+ tui_clear();
+ ui_print_header("遍历线性表");
+ printf("当前线性表：");
+ ui_print_vec_int(&state->linear);
+ printf("\n");
+ tui_wait();
+}
+
+static void ui_linear_clear(struct ui_state *state)
+{
+ if (!ui_confirm("清空线性表", "确定清空当前线性表？ [y/N]")) {
+ ui_set_status(state, "已取消");
+ return;
+ }
+ vec_clear(&state->linear);
+ ui_set_status(state, "已清空线性表");
+}
+
+static void ui_linear_state(const struct ui_state *state)
+{
+ tui_clear();
+ ui_print_header("线性表内部状态");
+ printf("size = %zu\n", state->linear.size);
+ printf("capacity = %zu\n", state->linear.capacity);
+ printf("elem_size = %zu\n\n", state->linear.elem_size);
+ printf("下标 元素\n");
+ printf("────────────────────────\n");
+ for (size_t i = 0; i < state->linear.size; ++i) {
+ printf("%-11zu %d\n", i,
+ *(const int *)vec_at_const(&state->linear, i));
+ }
+ tui_wait();
+}
+
+static void ui_linear_action(struct ui_state *state, int choice)
+{
+ ui_clear_status(state);
+ switch (choice) {
+ case 0:
+ ui_linear_append(state);
+ break;
+ case 1:
+ ui_linear_insert(state);
+ break;
+ case 2:
+ ui_linear_erase(state);
+ break;
+ case 3:
+ ui_linear_modify(state);
+ break;
+ case 4:
+ ui_linear_find(state);
+ break;
+ case 5:
+ ui_linear_traverse(state);
+ break;
+ case 6:
+ ui_linear_clear(state);
+ break;
+ case 7:
+ ui_linear_state(state);
+ break;
+ default:
+ break;
+ }
+}
+
+static void ui_linear_page(struct ui_state *state)
+{
+ size_t selected = 0;
+
+ for (;;) {
+ ui_draw_linear(state, selected);
+ int choice = ui_menu_input(&selected, 8);
+ if (choice == -1) {
+ return;
+ }
+ if (choice >= 0) {
+ ui_linear_action(state, choice);
+ }
+ }
+}
+
+static void ui_draw_vector(const struct ui_state *state, size_t selected)
+{
+ static const char *const items[] = {
+ "输入向量 A",
+ "输入向量 B",
+ "A + B",
+ "A - B",
+ "计算夹角余弦",
+ };
+
+ tui_clear();
+ ui_print_header("向量运算");
+ printf(COLOR_CYAN "A = " STYLE_BOLD);
+ ui_print_vec_double(&state->vector_a);
+ printf(STYLE_RESET "\n" COLOR_CYAN "B = " STYLE_BOLD);
+ ui_print_vec_double(&state->vector_b);
+ printf(STYLE_RESET "\n\n");
+
+ ui_print_menu(items, sizeof(items) / sizeof(items[0]), selected, "返回");
+
+ if (state->vector_result_kind == UI_VECTOR_RESULT_VALUE) {
+ printf("\n" COLOR_GREEN "结果：" STYLE_BOLD);
+ ui_print_vec_double(&state->vector_result);
+ printf(STYLE_RESET "\n");
+ } else if (state->vector_result_kind == UI_VECTOR_RESULT_COSINE) {
+ printf("\n" COLOR_GREEN "cos(A, B) = %.6f" STYLE_RESET "\n", state->vector_cosine);
+ }
+
+ ui_print_status(state);
+ ui_print_footer("↑/↓ 或 j/k 选择 Enter 确认 q/Esc 返回");
+ fflush(stdout);
+}
+
+static void ui_vector_input(struct vec *destination,
+ const char *name,
+ struct ui_state *state)
+{
+ char input[512];
+ char description[128];
+
+ snprintf(description, sizeof(description),
+ "请输入各分量，以空格分隔（向量 %s）：", name);
+ if (!ui_prompt_inline(name, description, input, sizeof(input))) {
+ ui_set_status(state, "已取消");
+ return;
+ }
+ if (!ui_parse_vector(input, destination)) {
+ ui_set_status(state, "错误：向量输入格式无效");
+ return;
+ }
+ state->vector_result_kind = UI_VECTOR_RESULT_NONE;
+ ui_set_status(state, "已更新向量 %s", name);
+}
+
+static void ui_vector_binary(struct ui_state *state, bool subtract)
+{
+ if (state->vector_a.size != state->vector_b.size) {
+ ui_set_status(state, "错误：两个向量维度不同");
+ return;
+ }
+
+ struct vec temporary;
+ vec_init(&temporary, double);
+ for (size_t i = 0; i < state->vector_a.size; ++i) {
+ double left = *(const double *)vec_at_const(&state->vector_a, i);
+ double right = *(const double *)vec_at_const(&state->vector_b, i);
+ double value = subtract ? left - right : left + right;
+ if (!vec_push_back(&temporary, &value)) {
+ vec_destroy(&temporary);
+ ui_set_status(state, "错误：内存分配失败");
+ return;
+ }
+ }
+ vec_swap(&state->vector_result, &temporary);
+ vec_destroy(&temporary);
+ state->vector_result_kind = UI_VECTOR_RESULT_VALUE;
+ ui_set_status(state, "已计算 A %c B", subtract ? '-' : '+');
+}
+
+static void ui_vector_cosine(struct ui_state *state)
+{
+ if (state->vector_a.size != state->vector_b.size) {
+ ui_set_status(state, "错误：两个向量维度不同");
+ return;
+ }
+
+ double dot = 0.0;
+ double norm_a = 0.0;
+ double norm_b = 0.0;
+ for (size_t i = 0; i < state->vector_a.size; ++i) {
+ double left = *(const double *)vec_at_const(&state->vector_a, i);
+ double right = *(const double *)vec_at_const(&state->vector_b, i);
+ dot += left * right;
+ norm_a += left * left;
+ norm_b += right * right;
+ }
+ if (norm_a == 0.0 || norm_b == 0.0) {
+ ui_set_status(state, "错误：零向量无法计算夹角余弦");
+ return;
+ }
+ state->vector_cosine = dot / (sqrt(norm_a) * sqrt(norm_b));
+ state->vector_result_kind = UI_VECTOR_RESULT_COSINE;
+ ui_set_status(state, "已计算夹角余弦");
+}
+
+static void ui_vector_action(struct ui_state *state, int choice)
+{
+ ui_clear_status(state);
+ switch (choice) {
+ case 0:
+ ui_vector_input(&state->vector_a, "输入向量 A", state);
+ break;
+ case 1:
+ ui_vector_input(&state->vector_b, "输入向量 B", state);
+ break;
+ case 2:
+ ui_vector_binary(state, false);
+ break;
+ case 3:
+ ui_vector_binary(state, true);
+ break;
+ case 4:
+ ui_vector_cosine(state);
+ break;
+ default:
+ break;
+ }
+}
+
+static void ui_vector_page(struct ui_state *state)
+{
+ size_t selected = 0;
+
+ for (;;) {
+ ui_draw_vector(state, selected);
+ int choice = ui_menu_input(&selected, 5);
+ if (choice == -1) {
+ return;
+ }
+ if (choice >= 0) {
+ ui_vector_action(state, choice);
+ }
+ }
+}
+
+static void ui_draw_poly_vec(const struct ui_state *state, size_t selected)
+{
+ static const char *const items[] = {
+ "输入多项式 A",
+ "输入多项式 B",
+ "A + B",
+ "A - B",
+ "A × B",
+ "多项式求导",
+ "查看存储结构",
+ };
+
+ tui_clear();
+ ui_print_header("顺序表多项式");
+ printf(COLOR_CYAN "A(x) = " STYLE_BOLD);
+ ui_print_poly_vec(&state->poly_vec_a);
+ printf(STYLE_RESET "\n" COLOR_CYAN "B(x) = " STYLE_BOLD);
+ ui_print_poly_vec(&state->poly_vec_b);
+ printf(STYLE_RESET "\n\n");
+
+ ui_print_menu(items, sizeof(items) / sizeof(items[0]), selected, "返回");
+
+ if (state->poly_vec_result_valid) {
+ printf("\n" COLOR_GREEN "结果：" STYLE_BOLD);
+ ui_print_poly_vec(&state->poly_vec_result);
+ printf(STYLE_RESET "\n");
+ }
+
+ ui_print_status(state);
+ ui_print_footer("↑/↓ 或 j/k 选择 Enter 确认 q/Esc 返回");
+ fflush(stdout);
+}
+
+static void ui_poly_vec_input(struct poly_vec *destination,
+ const char *name,
+ struct ui_state *state)
+{
+ char input[512];
+ char description[256];
+
+ snprintf(description, sizeof(description),
+ "输入格式：系数 指数；多个项用空格分隔\n例如：5 4 3 2 1 0\n输入多项式 %s：",
+ name);
+ if (!ui_prompt_inline("输入多项式", description, input, sizeof(input))) {
+ ui_set_status(state, "已取消");
+ return;
+ }
+ if (!ui_parse_poly_vec(input, destination)) {
+ ui_set_status(state, "错误：输入格式无效，应输入“系数 指数”对");
+ return;
+ }
+ state->poly_vec_result_valid = false;
+ ui_set_status(state, "已更新多项式 %s", name);
+}
+
+static void ui_poly_vec_binary(struct ui_state *state, char operation)
+{
+ bool success;
+
+ switch (operation) {
+ case '+':
+ success = poly_vec_add(&state->poly_vec_result,
+ &state->poly_vec_a, &state->poly_vec_b);
+ break;
+ case '-':
+ success = poly_vec_sub(&state->poly_vec_result,
+ &state->poly_vec_a, &state->poly_vec_b);
+ break;
+ default:
+ success = poly_vec_mul(&state->poly_vec_result,
+ &state->poly_vec_a, &state->poly_vec_b);
+ break;
+ }
+ if (!success) {
+ ui_set_status(state, "错误：多项式运算失败");
+ return;
+ }
+ state->poly_vec_result_valid = true;
+ ui_set_status(state, "已计算 A %c B", operation);
+}
+
+static void ui_poly_vec_derivative(struct ui_state *state)
+{
+ char input[128];
+ unsigned int which;
+ unsigned int order;
+ const struct poly_vec *source;
+
+ if (!ui_prompt_inline("多项式求导", "选择多项式（1=A，2=B）：",
+ input, sizeof(input))) {
+ ui_set_status(state, "已取消");
+ return;
+ }
+ if (!ui_parse_unsigned(input, &which) || (which != 1 && which != 2)) {
+ ui_set_status(state, "错误：多项式选择无效");
+ return;
+ }
+ if (!ui_prompt_inline("多项式求导", "输入求导阶数：",
+ input, sizeof(input))) {
+ ui_set_status(state, "已取消");
+ return;
+ }
+ if (!ui_parse_unsigned(input, &order)) {
+ ui_set_status(state, "错误：求导阶数无效");
+ return;
+ }
+ source = which == 1 ? &state->poly_vec_a : &state->poly_vec_b;
+ if (!poly_vec_derivative(&state->poly_vec_result, source, order)) {
+ ui_set_status(state, "错误：多项式求导失败");
+ return;
+ }
+ state->poly_vec_result_valid = true;
+ ui_set_status(state, "已完成多项式求导");
+}
+
+static void ui_poly_vec_storage(const struct ui_state *state)
+{
+ tui_clear();
+ ui_print_header("顺序表存储结构");
+ printf("A(x) = ");
+ ui_print_poly_vec(&state->poly_vec_a);
+ printf("\nsize = %zu capacity = %zu\n",
+ state->poly_vec_a.terms.size,
+ state->poly_vec_a.terms.capacity);
+ printf("下标 系数 指数\n");
+ printf("─────────────────────────────\n");
+ for (size_t i = 0; i < state->poly_vec_a.terms.size; ++i) {
+ const struct poly_term *term =
+ vec_at_const(&state->poly_vec_a.terms, i);
+ printf("%-12zu %-12.6g %u\n", i, term->coef, term->exp);
+ }
+ printf("\nB(x) = ");
+ ui_print_poly_vec(&state->poly_vec_b);
+ printf("\nsize = %zu capacity = %zu\n",
+ state->poly_vec_b.terms.size,
+ state->poly_vec_b.terms.capacity);
+ tui_wait();
+}
+
+static void ui_poly_vec_action(struct ui_state *state, int choice)
+{
+ ui_clear_status(state);
+ switch (choice) {
+ case 0:
+ ui_poly_vec_input(&state->poly_vec_a, "A", state);
+ break;
+ case 1:
+ ui_poly_vec_input(&state->poly_vec_b, "B", state);
+ break;
+ case 2:
+ ui_poly_vec_binary(state, '+');
+ break;
+ case 3:
+ ui_poly_vec_binary(state, '-');
+ break;
+ case 4:
+ ui_poly_vec_binary(state, '*');
+ break;
+ case 5:
+ ui_poly_vec_derivative(state);
+ break;
+ case 6:
+ ui_poly_vec_storage(state);
+ break;
+ default:
+ break;
+ }
+}
+
+static void ui_poly_vec_page(struct ui_state *state)
+{
+ size_t selected = 0;
+
+ for (;;) {
+ ui_draw_poly_vec(state, selected);
+ int choice = ui_menu_input(&selected, 7);
+ if (choice == -1) {
+ return;
+ }
+ if (choice >= 0) {
+ ui_poly_vec_action(state, choice);
+ }
+ }
+}
+
+static void ui_draw_poly_list(const struct ui_state *state, size_t selected)
+{
+ static const char *const items[] = {
+ "输入多项式 A",
+ "输入多项式 B",
+ "A + B",
+ "A - B",
+ "A × B",
+ "多项式求导",
+ "查看链表结构",
+ };
+
+ tui_clear();
+ ui_print_header("链表多项式");
+ printf(COLOR_CYAN "A(x) = " STYLE_BOLD);
+ ui_print_poly_list(&state->poly_list_a);
+ printf(STYLE_RESET "\n" COLOR_CYAN "B(x) = " STYLE_BOLD);
+ ui_print_poly_list(&state->poly_list_b);
+ printf(STYLE_RESET "\n\n");
+
+ ui_print_menu(items, sizeof(items) / sizeof(items[0]), selected, "返回");
+
+ if (state->poly_list_result_valid) {
+ printf("\n" COLOR_GREEN "结果：" STYLE_BOLD);
+ ui_print_poly_list(&state->poly_list_result);
+ printf(STYLE_RESET "\n");
+ }
+
+ ui_print_status(state);
+ ui_print_footer("↑/↓ 或 j/k 选择 Enter 确认 q/Esc 返回");
+ fflush(stdout);
+}
+
+static void ui_poly_list_input(struct poly_list *destination,
+ const char *name,
+ struct ui_state *state)
+{
+ char input[512];
+ char description[256];
+
+ snprintf(description, sizeof(description),
+ "输入格式：系数 指数；多个项用空格分隔\n例如：5 4 3 2 1 0\n输入多项式 %s：",
+ name);
+ if (!ui_prompt_inline("输入多项式", description, input, sizeof(input))) {
+ ui_set_status(state, "已取消");
+ return;
+ }
+ if (!ui_parse_poly_list(input, destination)) {
+ ui_set_status(state, "错误：输入格式无效，应输入“系数 指数”对");
+ return;
+ }
+ state->poly_list_result_valid = false;
+ ui_set_status(state, "已更新多项式 %s", name);
+}
+
+static void ui_poly_list_binary(struct ui_state *state, char operation)
+{
+ bool success;
+
+ switch (operation) {
+ case '+':
+ success = poly_list_add(&state->poly_list_result,
+ &state->poly_list_a, &state->poly_list_b);
+ break;
+ case '-':
+ success = poly_list_sub(&state->poly_list_result,
+ &state->poly_list_a, &state->poly_list_b);
+ break;
+ default:
+ success = poly_list_mul(&state->poly_list_result,
+ &state->poly_list_a, &state->poly_list_b);
+ break;
+ }
+ if (!success) {
+ ui_set_status(state, "错误：多项式运算失败");
+ return;
+ }
+ state->poly_list_result_valid = true;
+ ui_set_status(state, "已计算 A %c B", operation);
+}
+
+static void ui_poly_list_derivative(struct ui_state *state)
+{
+ char input[128];
+ unsigned int which;
+ unsigned int order;
+ const struct poly_list *source;
+
+ if (!ui_prompt_inline("多项式求导", "选择多项式（1=A，2=B）：",
+ input, sizeof(input))) {
+ ui_set_status(state, "已取消");
+ return;
+ }
+ if (!ui_parse_unsigned(input, &which) || (which != 1 && which != 2)) {
+ ui_set_status(state, "错误：多项式选择无效");
+ return;
+ }
+ if (!ui_prompt_inline("多项式求导", "输入求导阶数：",
+ input, sizeof(input))) {
+ ui_set_status(state, "已取消");
+ return;
+ }
+ if (!ui_parse_unsigned(input, &order)) {
+ ui_set_status(state, "错误：求导阶数无效");
+ return;
+ }
+ source = which == 1 ? &state->poly_list_a : &state->poly_list_b;
+ if (!poly_list_derivative(&state->poly_list_result, source, order)) {
+ ui_set_status(state, "错误：多项式求导失败");
+ return;
+ }
+ state->poly_list_result_valid = true;
+ ui_set_status(state, "已完成多项式求导");
+}
+
+static void ui_poly_list_storage(const struct ui_state *state)
+{
+ tui_clear();
+ ui_print_header("链表存储结构");
+ printf("A(x) = ");
+ ui_print_poly_list(&state->poly_list_a);
+ printf("\n节点数：%zu\n\n", state->poly_list_a.size);
+ printf("HEAD");
+ const struct list_head *position = state->poly_list_a.head.next;
+ while (position != &state->poly_list_a.head) {
+ const struct poly_node *node =
+ list_entry(position, const struct poly_node, link);
+ printf(" <-> [ %g, %u ]", node->term.coef, node->term.exp);
+ position = position->next;
+ }
+ printf(" <-> HEAD\n");
+ printf("\n每个节点：[ coef | exp | link ]\n");
+ printf("\nB(x) = ");
+ ui_print_poly_list(&state->poly_list_b);
+ printf("\n节点数：%zu\n", state->poly_list_b.size);
+ tui_wait();
+}
+
+static void ui_poly_list_action(struct ui_state *state, int choice)
+{
+ ui_clear_status(state);
+ switch (choice) {
+ case 0:
+ ui_poly_list_input(&state->poly_list_a, "A", state);
+ break;
+ case 1:
+ ui_poly_list_input(&state->poly_list_b, "B", state);
+ break;
+ case 2:
+ ui_poly_list_binary(state, '+');
+ break;
+ case 3:
+ ui_poly_list_binary(state, '-');
+ break;
+ case 4:
+ ui_poly_list_binary(state, '*');
+ break;
+ case 5:
+ ui_poly_list_derivative(state);
+ break;
+ case 6:
+ ui_poly_list_storage(state);
+ break;
+ default:
+ break;
+ }
+}
+
+static void ui_poly_list_page(struct ui_state *state)
+{
+ size_t selected = 0;
+
+ for (;;) {
+ ui_draw_poly_list(state, selected);
+ int choice = ui_menu_input(&selected, 7);
+ if (choice == -1) {
+ return;
+ }
+ if (choice >= 0) {
+ ui_poly_list_action(state, choice);
+ }
+ }
+}
+
+static const char *ui_expression_error_text(enum expression_error_code code)
+{
+ switch (code) {
+ case EXPRESSION_SYNTAX_ERROR: return "表达式语法错误";
+ case EXPRESSION_PAREN_ERROR: return "括号不匹配";
+ case EXPRESSION_UNKNOWN_VARIABLE: return "变量不存在";
+ case EXPRESSION_UNSET_VARIABLE: return "变量尚未赋值";
+ case EXPRESSION_DIVISION_BY_ZERO: return "除数不能为零";
+ default: return "表达式错误";
+ }
+}
+
+static void ui_draw_expression(const struct ui_state *state, size_t selected)
+{
+ static const char *const items[] = {
+ "输入新表达式",
+ "修改变量值",
+ "计算表达式",
+ };
+
+ tui_clear();
+ ui_print_header("表达式计算");
+ printf(COLOR_CYAN "当前表达式：" STYLE_RESET "\n %s\n\n",
+ state->expression_text[0] ? state->expression_text : "（未输入）");
+ printf(COLOR_CYAN "变量表：" STYLE_RESET "\n");
+ if (state->expression.variables.size == 0) {
+ printf(" （无变量）\n");
+ }
+ for (size_t i = 0; i < state->expression.variables.size; ++i) {
+ const struct expression_variable *v =
+ vec_at_const(&state->expression.variables, i);
+ if (v->assigned) printf(" %s = %g\n", v->name, v->value);
+ else printf(" %s = （未赋值）\n", v->name);
+ }
+ printf("\n" COLOR_CYAN "计算结果：" STYLE_RESET "\n");
+ if (state->expression_result_valid) printf(" %g\n", state->expression_result);
+ else printf(" （未计算）\n");
+ ui_print_menu(items, 3, selected, "返回");
+ ui_print_status(state);
+ ui_print_footer("↑/↓ 或 j/k 选择 Enter 确认 q/Esc 返回");
+ fflush(stdout);
+}
+
+static void ui_expression_input(struct ui_state *state)
+{
+ char input[sizeof(state->expression_text)];
+ if (!ui_prompt_inline("输入新表达式", "例如：3+4*X2-2*(20-5*2)",
+ input, sizeof(input))) return;
+ struct expression_error error;
+ if (!expression_collect_variables(&state->expression, input, &error)) {
+ ui_set_status(state, "错误：%s（位置 %zu）",
+ ui_expression_error_text(error.code), error.position);
+ return;
+ }
+ strcpy(state->expression_text, input);
+ state->expression_result_valid = false;
+ ui_set_status(state, "已更新表达式");
+}
+
+static void ui_expression_set_variable(struct ui_state *state)
+{
+ char name[EXPRESSION_NAME_MAX];
+ char input[64];
+ if (state->expression.variables.size == 0) {
+ ui_set_status(state, "当前表达式没有变量");
+ return;
+ }
+ if (!ui_prompt_inline("修改变量值", "输入变量名：", name, sizeof(name))) return;
+ struct expression_variable *variable = expression_variable(&state->expression, name);
+ if (!variable) {
+ ui_set_status(state, "错误：变量不存在");
+ return;
+ }
+ if (!ui_prompt_inline("修改变量值", "输入新值：", input, sizeof(input))) return;
+ char *end;
+ errno = 0;
+ double value = strtod(input, &end);
+ if (end == input || errno == ERANGE || *ui_skip_space(end) != '\0') {
+ ui_set_status(state, "错误：数值格式无效");
+ return;
+ }
+ variable->value = value;
+ variable->assigned = true;
+ state->expression_result_valid = false;
+ ui_set_status(state, "已更新变量 %s", name);
+}
+
+static void ui_expression_calculate(struct ui_state *state)
+{
+ if (state->expression_text[0] == '\0') {
+ ui_set_status(state, "错误：请先输入表达式");
+ return;
+ }
+ struct expression_error error;
+ if (!expression_eval(&state->expression, state->expression_text,
+ &state->expression_result, &error)) {
+ state->expression_result_valid = false;
+ ui_set_status(state, "错误：%s（位置 %zu）",
+ ui_expression_error_text(error.code), error.position);
+ return;
+ }
+ state->expression_result_valid = true;
+ ui_set_status(state, "计算完成");
+}
+
+static void ui_expression_action(struct ui_state *state, int choice)
+{
+ switch (choice) {
+ case 0:
+ ui_expression_input(state);
+ break;
+ case 1:
+ ui_expression_set_variable(state);
+ break;
+ case 2:
+ ui_expression_calculate(state);
+ break;
+ default:
+ break;
+ }
+}
+
+static void ui_expression_page(struct ui_state *state)
+{
+ size_t selected = 0;
+ for (;;) {
+ ui_draw_expression(state, selected);
+ int choice = ui_menu_input(&selected, 3);
+ if (choice == -1) {
+ return;
+ }
+ if (choice >= 0) {
+ ui_expression_action(state, choice);
+ }
+ }
+}
+
+static void ui_draw_main(const struct ui_state *state, size_t selected)
+{
+ static const char *const items[] = {
+ "线性表操作",
+ "向量运算",
+ "顺序表多项式",
+ "链表多项式",
+ "表达式计算",
+ };
+
+ (void)state;
+ tui_clear();
+ printf(COLOR_CYAN);
+ ui_print_rule('=');
+ printf(STYLE_BOLD);
+ ui_print_centered("简单计算器", ui_terminal_width());
+ printf(STYLE_RESET);
+ printf(COLOR_CYAN);
+ ui_print_rule('=');
+ printf(STYLE_RESET "\n");
+ ui_print_menu(items, sizeof(items) / sizeof(items[0]), selected, "退出");
+ ui_print_footer("↑/↓ 或 j/k 选择 Enter 确认 q 退出");
+ fflush(stdout);
+}
+
+int ui_run(void)
+{
+ struct ui_state state;
+
+ if (!ui_state_init(&state)) {
+ ui_state_destroy(&state);
+ fputs("初始化数据失败\n", stderr);
+ return 1;
+ }
+ if (!tui_init()) {
+ ui_state_destroy(&state);
+ fputs("无法初始化终端交互\n", stderr);
+ return 1;
+ }
+
+ size_t selected = 0;
+ for (;;) {
+ ui_draw_main(&state, selected);
+ int choice = ui_menu_input(&selected, 5);
+ if (choice == -1) {
+ break;
+ }
+ switch (choice) {
+ case 0:
+ ui_linear_page(&state);
+ break;
+ case 1:
+ ui_vector_page(&state);
+ break;
+ case 2:
+ ui_poly_vec_page(&state);
+ break;
+ case 3:
+ ui_poly_list_page(&state);
+ break;
+ case 4:
+ ui_expression_page(&state);
+ break;
+ default:
+ break;
+ }
+ }
+
+ tui_shutdown();
+ ui_state_destroy(&state);
+ return 0;
+}
diff --git a/lab04/ui.h b/lab04/ui.h
new file mode 100644
index 0000000..d7e2c9b
--- /dev/null
+++ b/lab04/ui.h
@@ -0,0 +1,9 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+#ifndef UI_H
+#define UI_H
+
+int ui_run(void);
+
+#endif /* LAB02_UI_H */
diff --git a/lab04/vec.h b/lab04/vec.h
new file mode 100644
index 0000000..d62df76
--- /dev/null
+++ b/lab04/vec.h
@@ -0,0 +1,1183 @@
+/* SPDX-License-Identifier: GPL-2.0-or-later */
+/* Copyright (C) 2026 Richard Qin */
+
+/**
+ * @file vec.h
+ * @brief A dynamically sized contiguous sequence with byte-based storage.
+ *
+ * `struct vec` stores the element size rather than a type. The caller is
+ * responsible for using the type associated with the initialized element size.
+ */
+#ifndef VEC_H
+#define VEC_H
+
+#include <stddef.h>
+#include <stdbool.h>
+#include <assert.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <string.h>
+
+/**
+ * @brief A dynamically sized contiguous sequence.
+ *
+ * `data` points to storage for at most `capacity` elements. The first
+ * `size` positions contain valid elements.
+ */
+typedef struct vec {
+ void *data;
+ size_t size;
+ size_t capacity;
+ size_t elem_size;
+} vec;
+
+/**
+ * @brief Compares two elements.
+ *
+ * @return A value less than, equal to, or greater than zero when the left
+ * element is less than, equal to, or greater than the right element.
+ */
+typedef int (*vec_compare_fn)(const void *lhs, const void *rhs);
+
+/** @name Initialization */
+/** @{ */
+
+/**
+ * @brief Produces an initializer for an empty vector of the given element type.
+ * @param type The element type.
+ */
+#define VEC_INIT(type) { \
+ .data = NULL, \
+ .size = 0, \
+ .capacity = 0, \
+ .elem_size = sizeof(type), \
+}
+
+/**
+ * @brief Declares and initializes a vector for the given element type.
+ * @param name The vector variable name.
+ * @param type The element type.
+ */
+#define VEC(name, type) \
+ struct vec name = VEC_INIT(type)
+
+/**
+ * @brief Initializes an existing vector.
+ * @param v A pointer to the vector.
+ * @param type The element type.
+ */
+#define vec_init(v, type) \
+ (*(v) = (struct vec)VEC_INIT(type))
+
+/** @} */
+
+/** @name Basic properties */
+/** @{ */
+
+/** @brief Returns the number of valid elements in the vector. */
+static inline size_t vec_size(const struct vec *v)
+{
+ return v->size;
+}
+
+/** @brief Returns the current storage capacity of the vector. */
+static inline size_t vec_capacity(const struct vec *v)
+{
+ return v->capacity;
+}
+
+/** @brief Returns the size of one element in bytes. */
+static inline size_t vec_elem_size(const struct vec *v)
+{
+ return v->elem_size;
+}
+
+/**
+ * @brief Returns the maximum number of elements representable at this element size.
+ */
+static inline size_t vec_max_size(const struct vec *v)
+{
+ return SIZE_MAX / v->elem_size;
+}
+
+/** @brief Tests whether the vector is empty. */
+static inline int vec_empty(const struct vec *v)
+{
+ return v->size == 0;
+}
+
+/** @} */
+
+/** @name Lifetime and capacity */
+/** @{ */
+
+/**
+ * @brief Removes all valid elements from the vector.
+ *
+ * The operation does not release the allocated capacity.
+ */
+static inline void vec_clear(struct vec *v)
+{
+ v->size = 0;
+}
+
+/**
+ * @brief Destroys the vector and releases its storage.
+ */
+static inline void vec_destroy(struct vec *v)
+{
+ free(v->data);
+
+ v->data = NULL;
+ v->size = 0;
+ v->capacity = 0;
+ v->elem_size = 0;
+}
+
+/**
+ * @brief Ensures that the vector has at least the requested capacity.
+ * @param v A pointer to the vector.
+ * @param capacity The minimum requested number of elements.
+ * @return `true` on success; `false` on overflow or allocation failure.
+ */
+static inline bool vec_reserve(struct vec *v, size_t capacity)
+{
+ if (!v || v->elem_size == 0) {
+ return false;
+ }
+ // 当前容量已满足需求，直接返回成功
+ if (capacity <= v->capacity) {
+ return true;
+ }
+ // 乘法溢出检查 (capacity * elem_size > SIZE_MAX)
+ if (capacity > SIZE_MAX / v->elem_size) {
+ return false;
+ }
+
+ size_t new_bytes = capacity * v->elem_size;
+ void *new_data = realloc(v->data, new_bytes);
+ if (!new_data) {
+ return false; // 分配失败，原 v->data 依然有效
+ }
+
+ v->data = new_data;
+ v->capacity = capacity;
+ return true;
+}
+
+/**
+ * @brief Changes the number of valid elements in the vector.
+ *
+ * Elements added by growing the vector are uninitialized.
+ *
+ * @param v A pointer to the vector.
+ * @param size The new number of elements.
+ * @return `true` on success; `false` on allocation failure.
+ */
+static inline bool vec_resize(struct vec *v, size_t size)
+{
+ if (!v) {
+ return false;
+ }
+
+ if (size > v->capacity) {
+ if (!vec_reserve(v, size)) {
+ return false;
+ }
+ }
+ v->size = size;
+ return true;
+}
+
+/**
+ * @brief Changes the vector size and clears newly added bytes.
+ *
+ * Clearing bytes does not guarantee a type-specific zero value; it only
+ * guarantees that the corresponding storage bytes are zero.
+ */
+static inline bool vec_resize_zero(struct vec *v, size_t size)
+{
+ if (!v) {
+ return false;
+ }
+ size_t old_size = v->size;
+
+ if (size > old_size) {
+ if (size > v->capacity) {
+ if (!vec_reserve(v, size)) {
+ return false;
+ }
+ }
+ /* 这里使用 memset 清零字节，不保证所有元素类型都得到
+ * 该类型语义上的零值。 */
+ char *start = (char *)v->data + (old_size * v->elem_size);
+ size_t zero_bytes = (size - old_size) * v->elem_size;
+ memset(start, 0, zero_bytes);
+ }
+
+ v->size = size;
+ return true;
+}
+
+/**
+ * @brief Attempts to reduce the capacity to the current size.
+ * @return `true` on success; `false` if reallocation fails.
+ */
+static inline bool vec_shrink_to_fit(struct vec *v)
+{
+ if (!v || v->elem_size == 0) {
+ return false;
+ }
+ // 已经完全贴合，无需缩容
+ if (v->capacity == v->size) {
+ return true;
+ }
+
+ // 当 size == 0 时，彻底归还堆内存
+ if (v->size == 0) {
+ free(v->data);
+ v->data = NULL;
+ v->capacity = 0;
+ return true;
+ }
+
+ // 缩容至刚好容纳 size 个元素
+ size_t bytes = v->size * v->elem_size;
+ void *new_data = realloc(v->data, bytes);
+ if (!new_data) {
+ return false; // 极少数情况下缩容可能失败，保持原样
+ }
+
+ v->data = new_data;
+ v->capacity = v->size;
+ return true;
+}
+
+/** @} */
+
+/** @name Raw element access */
+/** @{ */
+
+/** @brief Returns a writable pointer to the vector storage. */
+static inline void *vec_data(struct vec *v)
+{
+ return v->data;
+}
+
+/** @brief Returns a read-only pointer to the vector storage. */
+static inline const void *vec_data_const(const struct vec *v)
+{
+ return v->data;
+}
+
+/**
+ * @brief Tests two vectors for equality using a comparison function.
+ */
+static inline bool vec_equal(const struct vec *a,
+ const struct vec *b,
+ vec_compare_fn compare)
+{
+ if (a->elem_size != b->elem_size || a->size != b->size) {
+ return false;
+ }
+
+ for (size_t i = 0; i < a->size; ++i) {
+ const void *lhs = (const unsigned char *)a->data
+ + i * a->elem_size;
+ const void *rhs = (const unsigned char *)b->data
+ + i * b->elem_size;
+ if (compare(lhs, rhs) != 0) {
+ return false;
+ }
+ }
+ return true;
+}
+
+/**
+ * @brief Compares two vectors lexicographically.
+ * @return -1, 0, or 1 when the left vector is less than, equal to, or
+ * greater than the right vector.
+ */
+static inline int vec_compare(const struct vec *a,
+ const struct vec *b,
+ vec_compare_fn compare)
+{
+ size_t common_size = a->size < b->size ? a->size : b->size;
+
+ for (size_t i = 0; i < common_size; ++i) {
+ const void *lhs = (const unsigned char *)a->data
+ + i * a->elem_size;
+ const void *rhs = (const unsigned char *)b->data
+ + i * b->elem_size;
+ int result = compare(lhs, rhs);
+ if (result < 0) {
+ return -1;
+ }
+ if (result > 0) {
+ return 1;
+ }
+ }
+
+ if (a->size < b->size) {
+ return -1;
+ }
+ if (a->size > b->size) {
+ return 1;
+ }
+ return 0;
+}
+
+/**
+ * @brief Returns a writable pointer to the element at `index`.
+ * @pre `index < v->size`.
+ */
+static inline void *vec_at(struct vec *v, size_t index)
+{
+ assert(index < v->size);
+
+ return (unsigned char *)v->data
+ + index * v->elem_size;
+}
+
+/**
+ * @brief Returns a read-only pointer to the element at `index`.
+ * @pre `index < v->size`.
+ */
+static inline const void *vec_at_const(const struct vec *v,
+ size_t index)
+{
+ assert(index < v->size);
+
+ return (const unsigned char *)v->data
+ + index * v->elem_size;
+}
+
+/**
+ * @brief Returns a writable pointer to the element at `index`, or `NULL`
+ * when `index` is out of range.
+ */
+static inline void *vec_at_checked(struct vec *v, size_t index)
+{
+ if (index >= v->size) {
+ return NULL;
+ }
+
+ return (unsigned char *)v->data
+ + index * v->elem_size;
+}
+
+/**
+ * @brief Returns a read-only pointer to the element at `index`, or `NULL`
+ * when `index` is out of range.
+ */
+static inline const void *vec_at_checked_const(const struct vec *v,
+ size_t index)
+{
+ if (index >= v->size) {
+ return NULL;
+ }
+
+ return (const unsigned char *)v->data
+ + index * v->elem_size;
+}
+
+/**
+ * @brief Returns a writable pointer to the first element.
+ * @pre The vector is not empty.
+ */
+static inline void *vec_front(struct vec *v)
+{
+ assert(v->size);
+ return v->data;
+}
+
+/**
+ * @brief Returns a read-only pointer to the first element.
+ * @pre The vector is not empty.
+ */
+static inline const void *vec_front_const(const struct vec *v)
+{
+ assert(v->size);
+ return v->data;
+}
+
+/**
+ * @brief Returns a writable pointer to the last element.
+ * @pre The vector is not empty.
+ */
+static inline void *vec_back(struct vec *v)
+{
+ assert(v->size);
+ return vec_at(v, v->size - 1);
+}
+
+/**
+ * @brief Returns a read-only pointer to the last element.
+ * @pre The vector is not empty.
+ */
+static inline const void *vec_back_const(const struct vec *v)
+{
+ assert(v->size);
+ return vec_at_const(v, v->size - 1);
+}
+
+/** @} */
+
+/** @name Typed access macros */
+/** @{ */
+
+/** @brief Converts the storage pointer to a writable pointer of `type`. */
+#define vec_data_as(v, type) \
+ ((type *)vec_data(v))
+
+/** @brief Converts the storage pointer to a read-only pointer of `type`. */
+#define vec_data_as_const(v, type) \
+ ((const type *)vec_data_const(v))
+
+/** @brief Accesses the writable element at `i` as `type`. */
+#define vec_at_as(v, type, i) \
+ (*(type *)vec_at((v), (i)))
+
+/** @brief Accesses the read-only element at `i` as `type`. */
+#define vec_at_as_const(v, type, i) \
+ (*(const type *)vec_at_const((v), (i)))
+
+/** @brief Accesses the first element as a writable `type`. */
+#define vec_front_as(v, type) \
+ (*(type *)vec_front(v))
+
+/** @brief Accesses the first element as a read-only `type`. */
+#define vec_front_as_const(v, type) \
+ (*(const type *)vec_front_const(v))
+
+/** @brief Accesses the last element as a writable `type`. */
+#define vec_back_as(v, type) \
+ (*(type *)vec_back(v))
+
+/** @brief Accesses the last element as a read-only `type`. */
+#define vec_back_as_const(v, type) \
+ (*(const type *)vec_back_const(v))
+
+/** @} */
+
+/** @name Raw element insertion */
+/** @{ */
+
+/* 内部辅助函数：按 2 倍几何级数扩容，确保至少容纳 needed 个元素 */
+static inline bool __vec_grow_to(struct vec *v, size_t needed)
+{
+ size_t max_elements = SIZE_MAX / v->elem_size;
+ if (needed > max_elements) {
+ return false;
+ }
+ if (needed <= v->capacity) {
+ return true;
+ }
+ // 初始默认给 8 个元素容量，之后每次翻倍
+ size_t new_cap = v->capacity ? v->capacity : 8;
+ if (new_cap > max_elements) {
+ new_cap = max_elements;
+ }
+ while (new_cap < needed) {
+ // 防止翻倍超过最大元素数量
+ if (new_cap > max_elements / 2) {
+ new_cap = max_elements;
+ break;
+ }
+ new_cap *= 2;
+ }
+ return vec_reserve(v, new_cap);
+}
+
+/**
+ * @brief Reserves an uninitialized slot at the end of the vector.
+ * @return A pointer to the new slot, or `NULL` on failure.
+ */
+static inline void *vec_emplace_back(struct vec *v)
+{
+ if (!v || v->elem_size == 0) {
+ return NULL;
+ }
+ size_t max_elements = SIZE_MAX / v->elem_size;
+ if (v->size >= max_elements) {
+ return NULL;
+ }
+ size_t needed = v->size + 1;
+ /* Grow the storage when the current capacity is exhausted. */
+ if (v->size >= v->capacity) {
+ if (!__vec_grow_to(v, needed)) {
+ return NULL;
+ }
+ }
+ void *slot = (char *)v->data + (v->size * v->elem_size);
+ v->size++;
+ return slot;
+}
+
+static inline size_t __vec_source_index(const struct vec *v,
+ const void *elem)
+{
+ if (!v || !v->data || !elem || v->elem_size == 0) {
+ return SIZE_MAX;
+ }
+
+ uintptr_t base = (uintptr_t)v->data;
+ uintptr_t address = (uintptr_t)elem;
+ if (address < base) {
+ return SIZE_MAX;
+ }
+
+ uintptr_t offset = address - base;
+ if (offset % v->elem_size != 0) {
+ return SIZE_MAX;
+ }
+
+ size_t index = (size_t)(offset / v->elem_size);
+ return index < v->size ? index : SIZE_MAX;
+}
+
+/**
+ * @brief Appends one raw element to the vector.
+ * @param v A pointer to the vector.
+ * @param elem A pointer to the element to copy.
+ * @return `true` on success; `false` on invalid input or allocation failure.
+ */
+static inline bool vec_push_back(struct vec *v,
+ const void *elem)
+{
+ if (!elem) {
+ return false;
+ }
+ size_t source_index = __vec_source_index(v, elem);
+ void *slot = vec_emplace_back(v);
+ if (!slot) {
+ return false;
+ }
+ const void *source = source_index == SIZE_MAX
+ ? elem
+ : (const unsigned char *)v->data
+ + source_index * v->elem_size;
+ memcpy(slot, source, v->elem_size);
+ return true;
+}
+
+/**
+ * @brief Reserves an uninitialized slot at `index`.
+ * @param v A pointer to the vector.
+ * @param index The insertion index in the range `[0, size]`.
+ * @return A pointer to the new slot, or `NULL` on failure.
+ */
+static inline void *vec_emplace(struct vec *v,
+ size_t index)
+{
+ if (!v || v->elem_size == 0 || index > v->size) {
+ return NULL;
+ }
+ size_t max_elements = SIZE_MAX / v->elem_size;
+ if (v->size >= max_elements) {
+ return NULL;
+ }
+ size_t needed = v->size + 1;
+ if (v->size >= v->capacity) {
+ if (!__vec_grow_to(v, needed)) {
+ return NULL;
+ }
+ }
+ char *slot = (char *)v->data + (index * v->elem_size);
+
+ /* Shift the suffix when insertion is not at the end. */
+ if (index < v->size) {
+ memmove(slot + v->elem_size, slot, (v->size - index) * v->elem_size);
+ }
+
+ v->size++;
+ return (void *)slot;
+
+}
+
+/**
+ * @brief Inserts one raw element at `index`.
+ * @param v A pointer to the vector.
+ * @param index The insertion index in the range `[0, size]`.
+ * @param elem A pointer to the element to copy.
+ * @return `true` on success; `false` on invalid input or allocation failure.
+ */
+static inline bool vec_insert(struct vec *v,
+ size_t index,
+ const void *elem)
+{
+ if (!elem) {
+ return false;
+ }
+ size_t source_index = __vec_source_index(v, elem);
+ void *slot = vec_emplace(v, index);
+ if (!slot) {
+ return false;
+ }
+ if (source_index != SIZE_MAX && source_index >= index) {
+ source_index++;
+ }
+ const void *source = source_index == SIZE_MAX
+ ? elem
+ : (const unsigned char *)v->data
+ + source_index * v->elem_size;
+ memcpy(slot, source, v->elem_size);
+ return true;
+}
+
+/**
+ * @brief Inserts a range of raw elements at `index`.
+ *
+ * The source range must not refer to the vector's storage.
+ *
+ * @param v A pointer to the vector.
+ * @param index The insertion index in the range `[0, size]`.
+ * @param src The source range.
+ * @param count The number of elements to insert.
+ * @return `true` on success; `false` on invalid input or allocation failure.
+ */
+static inline bool vec_insert_range(struct vec *v,
+ size_t index,
+ const void *src,
+ size_t count)
+{
+ /* 前置条件：src 不得指向当前 vector 的存储区，
+ * 这与 std::vector::insert(position, first, last) 一致。 */
+ if (!v || v->elem_size == 0 || index > v->size) {
+ return false;
+ }
+ if (count == 0) {
+ return true; /* Inserting zero elements succeeds. */
+ }
+ if (!src) {
+ return false;
+ }
+ /* Check for overflow in size + count. */
+ if (count > SIZE_MAX - v->size) {
+ return false;
+ }
+
+ size_t needed = v->size + count;
+ if (needed > v->capacity) {
+ if (!__vec_grow_to(v, needed)) {
+ return false;
+ }
+ }
+
+ char *dest = (char *)v->data + (index * v->elem_size);
+
+ /* Shift the suffix when insertion is not at the end. */
+ if (index < v->size) {
+ memmove(dest + (count * v->elem_size), dest, (v->size - index) * v->elem_size);
+ }
+
+ /* Copy the source range into the newly opened gap. */
+ memcpy(dest, src, count * v->elem_size);
+ v->size += count;
+ return true;
+}
+
+/**
+ * @brief Replaces the vector with `count` copies of one raw element.
+ * @param v A pointer to the vector.
+ * @param count The resulting number of elements.
+ * @param value A pointer to the value to copy.
+ * @return `true` on success; `false` on invalid input or allocation failure.
+ */
+static inline bool vec_assign_n(struct vec *v,
+ size_t count,
+ const void *value)
+{
+ if (!v || v->elem_size == 0) {
+ return false;
+ }
+ if (count == 0) {
+ v->size = 0;
+ return true;
+ }
+ if (!value || count > vec_max_size(v)) {
+ return false;
+ }
+
+ size_t source_index = __vec_source_index(v, value);
+ if (count > v->capacity && !vec_reserve(v, count)) {
+ return false;
+ }
+
+ const void *source = source_index == SIZE_MAX
+ ? value
+ : (const unsigned char *)v->data
+ + source_index * v->elem_size;
+ for (size_t i = 0; i < count; ++i) {
+ void *dest = (unsigned char *)v->data + i * v->elem_size;
+ memmove(dest, source, v->elem_size);
+ }
+ v->size = count;
+ return true;
+}
+
+/**
+ * @brief Replaces the vector with a range of raw elements.
+ *
+ * The source range must not refer to the vector's storage.
+ *
+ * @param v A pointer to the vector.
+ * @param src The source range.
+ * @param count The number of elements to assign.
+ * @return `true` on success; `false` on invalid input or allocation failure.
+ */
+static inline bool vec_assign_range(struct vec *v,
+ const void *src,
+ size_t count)
+{
+ /* 前置条件：src 不得指向当前 vector 的存储区。 */
+ if (!v || v->elem_size == 0) {
+ return false;
+ }
+ if (count == 0) {
+ v->size = 0;
+ return true;
+ }
+ if (!src || count > vec_max_size(v)) {
+ return false;
+ }
+ if (count > v->capacity && !vec_reserve(v, count)) {
+ return false;
+ }
+
+ memmove(v->data, src, count * v->elem_size);
+ v->size = count;
+ return true;
+}
+
+/**
+ * @brief Appends a range of raw elements to the vector.
+ *
+ * The source range must not refer to the vector's storage.
+ *
+ * @param v A pointer to the vector.
+ * @param src The source range.
+ * @param count The number of elements to append.
+ * @return `true` on success; `false` on invalid input or allocation failure.
+ */
+static inline bool vec_append(struct vec *v,
+ const void *src,
+ size_t count)
+{
+ /* The source must not refer to the vector's storage. */
+ if (!v) {
+ return false;
+ }
+ /* Reuse vec_insert_range() at the current end position. */
+ return vec_insert_range(v, v->size, src, count);
+}
+
+
+/** @} */
+
+/** @name Value insertion wrappers */
+/** @{ */
+
+/** @brief Appends a typed value after checking its size. */
+#define vec_push(v, value) ({ \
+ typeof(value) __vec_tmp = (value); \
+ assert(sizeof(__vec_tmp) == \
+ (v)->elem_size); \
+ vec_push_back((v), &__vec_tmp); \
+})
+
+/** @brief Inserts a typed value after checking its size. */
+#define vec_insert_value(v, index, value) ({ \
+ typeof(value) __vec_tmp = (value); \
+ assert(sizeof(__vec_tmp) == \
+ (v)->elem_size); \
+ vec_insert((v), (index), &__vec_tmp); \
+})
+
+/** @brief Reserves a typed slot at the end of the vector. */
+#define vec_emplace_back_as(v, type) \
+ ((type *)vec_emplace_back(v))
+
+/** @brief Reserves a typed slot at the specified index. */
+#define vec_emplace_as(v, type, index) \
+ ((type *)vec_emplace((v), (index)))
+
+
+/** @} */
+
+/** @name Erasure */
+/** @{ */
+
+/** @brief Removes the last element, if one exists. */
+static inline void vec_pop_back(struct vec *v)
+{
+ if (!v || v->size == 0) {
+ return;
+ }
+ v->size--;
+}
+
+/**
+ * @brief Removes the last element and copies it to `out`.
+ * @return `true` on success; `false` when the vector is empty or `out` is null.
+ */
+static inline bool vec_pop_back_copy(struct vec *v,
+ void *out)
+{
+ if (!v || !out || v->size == 0) {
+ return false;
+ }
+ v->size--;
+ const char *last_elem = (const char *)v->data + (v->size * v->elem_size);
+ memcpy(out, last_elem, v->elem_size);
+ return true;
+}
+
+/**
+ * @brief Removes up to `count` elements starting at `index`.
+ */
+static inline void vec_erase_n(struct vec *v,
+ size_t index,
+ size_t count)
+{
+ if (!v || index >= v->size || count == 0) {
+ return;
+ }
+
+ /* Limit the count without allowing index + count to overflow. */
+ if (count > v->size - index) {
+ count = v->size - index;
+ }
+
+ size_t trailing_elems = v->size - (index + count);
+ if (trailing_elems > 0) {
+ char *dest = (char *)v->data + (index * v->elem_size);
+ const char *src = (const char *)v->data + ((index + count) * v->elem_size);
+ /* The source and destination overlap, so use memmove. */
+ memmove(dest, src, trailing_elems * v->elem_size);
+ }
+
+ v->size -= count;
+}
+
+/** @brief Removes the element at `index`, if it exists. */
+static inline void vec_erase(struct vec *v,
+ size_t index)
+{
+ vec_erase_n(v, index, 1);
+}
+
+/**
+ * @brief Removes the half-open range `[first, last)`.
+ * @return A pointer to the element now at `first`, or the end pointer.
+ */
+static inline void *vec_erase_range(struct vec *v,
+ size_t first,
+ size_t last)
+{
+ if (!v || first > last || last > v->size) {
+ return NULL;
+ }
+
+ vec_erase_n(v, first, last - first);
+ if (first == v->size) {
+ if (!v->data) {
+ return NULL;
+ }
+ return (unsigned char *)v->data + v->size * v->elem_size;
+ }
+ return (unsigned char *)v->data + first * v->elem_size;
+}
+
+/** @brief Exchanges the contents of two vectors. */
+static inline void vec_swap(struct vec *a, struct vec *b)
+{
+ struct vec tmp = *a;
+ *a = *b;
+ *b = tmp;
+}
+
+
+/**
+ * @brief Removes an element by replacing it with the last element.
+ *
+ * The order of the remaining elements is not preserved.
+ */
+static inline void vec_swap_erase(struct vec *v,
+ size_t index)
+{
+ if (!v || index >= v->size) {
+ return;
+ }
+
+ size_t last_idx = v->size - 1;
+ /* Move the last element over the erased element when necessary. */
+ if (index < last_idx) {
+ char *dest = (char *)v->data + (index * v->elem_size);
+ const char *src = (const char *)v->data + (last_idx * v->elem_size);
+ memcpy(dest, src, v->elem_size);
+ }
+
+ v->size--;
+}
+
+/** @} */
+
+/** @name Forward iterators */
+/** @{ */
+
+/** @brief Returns a writable iterator to the first element. */
+static inline void *vec_begin(struct vec *v)
+{
+ return v->data;
+}
+
+/** @brief Returns a read-only iterator to the first element. */
+static inline const void *vec_cbegin(const struct vec *v)
+{
+ return v->data;
+}
+
+/** @brief Returns a writable iterator past the last element. */
+static inline void *vec_end(struct vec *v)
+{
+ if (!v->data)
+ return NULL;
+
+ return (unsigned char *)v->data
+ + v->size * v->elem_size;
+}
+
+/** @brief Returns a read-only iterator past the last element. */
+static inline const void *vec_cend(const struct vec *v)
+{
+ if (!v->data)
+ return NULL;
+
+ return (const unsigned char *)v->data
+ + v->size * v->elem_size;
+}
+
+/** @brief Returns the first element as a typed writable iterator. */
+#define vec_begin_as(v, type) \
+ ((type *)vec_begin(v))
+
+/** @brief Returns the end as a typed writable iterator. */
+#define vec_end_as(v, type) \
+ ((type *)vec_end(v))
+
+/** @brief Returns the first element as a typed read-only iterator. */
+#define vec_cbegin_as(v, type) \
+ ((const type *)vec_cbegin(v))
+
+/** @brief Returns the end as a typed read-only iterator. */
+#define vec_cend_as(v, type) \
+ ((const type *)vec_cend(v))
+
+
+/** @} */
+
+/** @name Iterator helpers */
+/** @{ */
+
+/** @brief Advances a pointer iterator by one element. */
+#define vec_iter_next(it) \
+ (++(it))
+
+/** @brief Moves a pointer iterator back by one element. */
+#define vec_iter_prev(it) \
+ (--(it))
+
+/**
+ * @brief Returns the distance between two pointer iterators.
+ *
+ * Equal iterators, including two null pointers, have distance zero.
+ */
+#define vec_iter_distance(first, last) ({ \
+ __auto_type __vec_first = (first); \
+ __auto_type __vec_last = (last); \
+ __vec_first == __vec_last \
+ ? 0 \
+ : __vec_last - __vec_first; \
+})
+
+/**
+ * @brief A reverse iterator over mutable vector storage.
+ */
+struct vec_reverse_iterator {
+ void *data;
+ size_t size;
+ size_t elem_size;
+ size_t offset;
+};
+
+/**
+ * @brief A reverse iterator over read-only vector storage.
+ */
+struct vec_const_reverse_iterator {
+ const void *data;
+ size_t size;
+ size_t elem_size;
+ size_t offset;
+};
+
+/** @brief Returns a reverse iterator to the last element. */
+static inline struct vec_reverse_iterator vec_rbegin(struct vec *v)
+{
+ return (struct vec_reverse_iterator){
+ .data = v->data,
+ .size = v->size,
+ .elem_size = v->elem_size,
+ .offset = 0,
+ };
+}
+
+/** @brief Returns a reverse iterator past the first element. */
+static inline struct vec_reverse_iterator vec_rend(struct vec *v)
+{
+ return (struct vec_reverse_iterator){
+ .data = v->data,
+ .size = v->size,
+ .elem_size = v->elem_size,
+ .offset = v->size,
+ };
+}
+
+/** @brief Returns a read-only reverse iterator to the last element. */
+static inline struct vec_const_reverse_iterator
+vec_crbegin(const struct vec *v)
+{
+ return (struct vec_const_reverse_iterator){
+ .data = v->data,
+ .size = v->size,
+ .elem_size = v->elem_size,
+ .offset = 0,
+ };
+}
+
+/** @brief Returns a read-only reverse iterator past the first element. */
+static inline struct vec_const_reverse_iterator
+vec_crend(const struct vec *v)
+{
+ return (struct vec_const_reverse_iterator){
+ .data = v->data,
+ .size = v->size,
+ .elem_size = v->elem_size,
+ .offset = v->size,
+ };
+}
+
+/** @brief Dereferences a mutable reverse iterator. */
+static inline void *vec_reverse_deref(struct vec_reverse_iterator it)
+{
+ return (unsigned char *)it.data
+ + (it.size - it.offset - 1) * it.elem_size;
+}
+
+/** @brief Dereferences a read-only reverse iterator. */
+static inline const void *
+vec_reverse_deref_const(struct vec_const_reverse_iterator it)
+{
+ return (const unsigned char *)it.data
+ + (it.size - it.offset - 1) * it.elem_size;
+}
+
+/** @brief Advances a mutable reverse iterator. */
+static inline void vec_reverse_next(struct vec_reverse_iterator *it)
+{
+ ++it->offset;
+}
+
+/** @brief Advances a read-only reverse iterator. */
+static inline void
+vec_reverse_next_const(struct vec_const_reverse_iterator *it)
+{
+ ++it->offset;
+}
+
+/** @brief Moves a mutable reverse iterator backwards. */
+static inline void vec_reverse_prev(struct vec_reverse_iterator *it)
+{
+ --it->offset;
+}
+
+/** @brief Moves a read-only reverse iterator backwards. */
+static inline void
+vec_reverse_prev_const(struct vec_const_reverse_iterator *it)
+{
+ --it->offset;
+}
+
+/** @brief Compares two mutable reverse iterators. */
+static inline bool vec_reverse_equal(struct vec_reverse_iterator lhs,
+ struct vec_reverse_iterator rhs)
+{
+ return lhs.data == rhs.data && lhs.offset == rhs.offset;
+}
+
+/** @brief Compares two read-only reverse iterators. */
+static inline bool
+vec_reverse_equal_const(struct vec_const_reverse_iterator lhs,
+ struct vec_const_reverse_iterator rhs)
+{
+ return lhs.data == rhs.data && lhs.offset == rhs.offset;
+}
+
+/** @brief Returns the distance between mutable reverse iterators. */
+static inline ptrdiff_t
+vec_reverse_distance(struct vec_reverse_iterator first,
+ struct vec_reverse_iterator last)
+{
+ return (ptrdiff_t)last.offset - (ptrdiff_t)first.offset;
+}
+
+/** @brief Returns the distance between read-only reverse iterators. */
+static inline ptrdiff_t
+vec_reverse_distance_const(struct vec_const_reverse_iterator first,
+ struct vec_const_reverse_iterator last)
+{
+ return (ptrdiff_t)last.offset - (ptrdiff_t)first.offset;
+}
+
+
+/** @} */
+
+/** @name Traversal */
+/** @{ */
+
+/**
+ * @brief Iterates over mutable vector elements.
+ *
+ * Example:
+ * @code
+ * int *it;
+ * vec_for_each(it, &v, int)
+ * printf("%d\\n", *it);
+ * @endcode
+ */
+
+#define vec_for_each(pos, v, type) \
+ for ((pos) = vec_begin_as((v), type); \
+ (pos) != vec_end_as((v), type); \
+ ++(pos))
+
+/** @brief Iterates over read-only vector elements. */
+#define vec_for_each_const(pos, v, type) \
+ for ((pos) = vec_cbegin_as((v), type); \
+ (pos) != vec_cend_as((v), type); \
+ ++(pos))
+
+/**
+ * @brief Iterates over vector indexes in ascending order.
+ */
+
+#define vec_for_each_index(i, v) \
+ for (size_t i = 0; i < (v)->size; ++i)
+
+/** @brief Iterates over vector indexes in descending order. */
+#define vec_for_each_index_reverse(i, v) \
+ for (size_t i = (v)->size; i-- > 0; )
+
+/** @} */
+
+#endif /* VEC_H */
generated by cgit v1.2.3 (git 2.46.0) at 2026-10-28 22:32:18 +0000