#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/* =========================
 * Stack (array + top index)
 * ========================= */

#define STACK_MAX 1024

typedef struct {
  int data[STACK_MAX];
  int top;
} Stack;

static void stack_init(Stack *s) {
  s->top = -1;
}

static int stack_is_empty(const Stack *s) {
  return s->top < 0;
}

static int stack_is_full(const Stack *s) {
  return s->top >= STACK_MAX - 1;
}

static int stack_push(Stack *s, int value) {
  if (stack_is_full(s)) return 0;
  s->data[++s->top] = value;
  return 1;
}

static int stack_top(const Stack *s, int *out) {
  if (stack_is_empty(s)) return 0;
  *out = s->data[s->top];
  return 1;
}

static int stack_pop(Stack *s, int *out) {
  if (stack_is_empty(s)) return 0;
  *out = s->data[s->top--];
  return 1;
}

static int eval_postfix(const char *tokens[], int n, int *result) {
  Stack s;
  stack_init(&s);
  for (int i = 0; i < n; i++) {
    const char *t = tokens[i];
    if (strlen(t) == 1 && strchr("+-*/", t[0])) {
      int b, a;
      if (!stack_pop(&s, &b) || !stack_pop(&s, &a)) return 0;
      switch (t[0]) {
        case '+': stack_push(&s, a + b); break;
        case '-': stack_push(&s, a - b); break;
        case '*': stack_push(&s, a * b); break;
        case '/': stack_push(&s, a / b); break;
      }
    } else {
      stack_push(&s, atoi(t));
    }
  }
  return stack_pop(&s, result);
}

/* =========================
 * Queue (circular array)
 * ========================= */

#define QUEUE_MAX 1024

typedef struct {
  int data[QUEUE_MAX];
  int head;
  int tail;
  int size;
} Queue;

static void queue_init(Queue *q) {
  q->head = 0;
  q->tail = 0;
  q->size = 0;
}

static int queue_is_empty(const Queue *q) {
  return q->size == 0;
}

static int queue_is_full(const Queue *q) {
  return q->size == QUEUE_MAX;
}

static int queue_enqueue(Queue *q, int value) {
  if (queue_is_full(q)) return 0;
  q->data[q->tail] = value;
  q->tail = (q->tail + 1) % QUEUE_MAX;
  q->size++;
  return 1;
}

static int queue_head(const Queue *q, int *out) {
  if (queue_is_empty(q)) return 0;
  *out = q->data[q->head];
  return 1;
}

static int queue_dequeue(Queue *q, int *out) {
  if (queue_is_empty(q)) return 0;
  *out = q->data[q->head];
  q->head = (q->head + 1) % QUEUE_MAX;
  q->size--;
  return 1;
}

/* =========================
 * List (array pool version)
 * ========================= */

#define MEM_MAX 1024

typedef struct {
  int value[MEM_MAX];
  int next[MEM_MAX];
  int free;
} Pool;

static void pool_init(Pool *p) {
  for (int i = 0; i < MEM_MAX - 1; i++) {
    p->next[i] = i + 1;
  }
  p->next[MEM_MAX - 1] = -1;
  p->free = 0;
}

static int cell(Pool *p, int value, int next) {
  if (p->free == -1) return -1;
  int idx = p->free;
  p->free = p->next[idx];
  p->value[idx] = value;
  p->next[idx] = next;
  return idx;
}

static void pool_free(Pool *p, int idx) {
  p->next[idx] = p->free;
  p->free = idx;
}

static int list_insert_at(Pool *p, int head, int pos, int value) {
  if (pos == 0) {
    int node = cell(p, value, head);
    return node;
  }
  int cur = head;
  for (int i = 0; i < pos - 1 && cur != -1; i++) {
    cur = p->next[cur];
  }
  if (cur == -1) return head;
  int node = cell(p, value, p->next[cur]);
  if (node == -1) return head;
  p->next[cur] = node;
  return head;
}

static int list_remove_at(Pool *p, int head, int pos) {
  if (head == -1) return -1;
  if (pos == 0) {
    int next = p->next[head];
    pool_free(p, head);
    return next;
  }
  int cur = head;
  for (int i = 0; i < pos - 1 && cur != -1; i++) {
    cur = p->next[cur];
  }
  if (cur == -1 || p->next[cur] == -1) return head;
  int to_delete = p->next[cur];
  p->next[cur] = p->next[to_delete];
  pool_free(p, to_delete);
  return head;
}

static void list_print(const Pool *p, int head) {
  printf("[");
  for (int cur = head; cur != -1; cur = p->next[cur]) {
    printf("%d", p->value[cur]);
    if (p->next[cur] != -1) printf(", ");
  }
  printf("]\n");
}

/* =========================
 * Map (list of pairs)
 * ========================= */

typedef struct PairNode {
  int key;
  int value;
  struct PairNode *next;
} PairNode;

static PairNode *map_bind(PairNode *head, int key, int value) {
  for (PairNode *n = head; n; n = n->next) {
    if (n->key == key) {
      n->value = value;
      return head;
    }
  }
  PairNode *n = malloc(sizeof(PairNode));
  if (!n) return head;
  n->key = key;
  n->value = value;
  n->next = head;
  return n;
}

static int map_lookup(const PairNode *head, int key, int *out) {
  for (const PairNode *n = head; n; n = n->next) {
    if (n->key == key) {
      *out = n->value;
      return 1;
    }
  }
  return 0;
}

static void map_free(PairNode *head) {
  while (head) {
    PairNode *next = head->next;
    free(head);
    head = next;
  }
}

/* =========================
 * Tree (BST) and tree sort
 * ========================= */

typedef struct TreeNode {
  int value;
  struct TreeNode *left;
  struct TreeNode *right;
} TreeNode;

static TreeNode *node_new(int value) {
  TreeNode *n = malloc(sizeof(TreeNode));
  if (!n) return NULL;
  n->value = value;
  n->left = NULL;
  n->right = NULL;
  return n;
}

static TreeNode *bst_insert(TreeNode *root, int value) {
  if (!root) return node_new(value);
  if (value < root->value) {
    root->left = bst_insert(root->left, value);
  } else if (value > root->value) {
    root->right = bst_insert(root->right, value);
  }
  return root;
}

static void bst_inorder(const TreeNode *root, int *out, int *i) {
  if (!root) return;
  bst_inorder(root->left, out, i);
  out[(*i)++] = root->value;
  bst_inorder(root->right, out, i);
}

static void bst_free(TreeNode *root) {
  if (!root) return;
  bst_free(root->left);
  bst_free(root->right);
  free(root);
}

static void tree_sort(int *arr, int n) {
  TreeNode *root = NULL;
  for (int i = 0; i < n; i++) {
    root = bst_insert(root, arr[i]);
  }
  int idx = 0;
  bst_inorder(root, arr, &idx);
  bst_free(root);
}

/* =========================
 * Demos
 * ========================= */

static void demo_stack_postfix(int argc, char **argv) {
  const char *default_tokens[] = {"3", "4", "+", "2", "*"};
  const char **tokens = default_tokens;
  int n = 5;

  if (argc > 1) {
    tokens = (const char **)(argv + 1);
    n = argc - 1;
  }

  int result = 0;
  if (eval_postfix(tokens, n, &result)) {
    printf("Postfix result: %d\n", result);
  } else {
    printf("Error evaluating postfix expression.\n");
  }
}

static void demo_queue_round_robin(void) {
  Queue q;
  queue_init(&q);

  for (int i = 1; i <= 5; i++) {
    queue_enqueue(&q, i);
  }

  printf("Round-robin order: ");
  for (int i = 0; i < 8; i++) {
    int task = 0;
    if (queue_dequeue(&q, &task)) {
      printf("T%d ", task);
      queue_enqueue(&q, task);
    }
  }
  printf("\n");
}

static void demo_list_pool(void) {
  Pool p;
  pool_init(&p);

  int head = -1;
  head = list_insert_at(&p, head, 0, 10);
  head = list_insert_at(&p, head, 1, 20);
  head = list_insert_at(&p, head, 2, 30);
  head = list_insert_at(&p, head, 1, 15);

  printf("List after inserts: ");
  list_print(&p, head);

  head = list_remove_at(&p, head, 2);
  printf("List after remove pos 2: ");
  list_print(&p, head);
}

static void demo_map_translator(int argc, char **argv) {
  const char *english[] = {"hello", "world", "cat", "dog", "tree", "cpu"};
  const char *french[]  = {"bonjour", "monde", "chat", "chien", "arbre", "processeur"};
  const int n = (int)(sizeof(english) / sizeof(english[0]));

  PairNode *dict = NULL;
  for (int i = 0; i < n; i++) {
    dict = map_bind(dict, i, i);
  }

  if (argc <= 1) {
    const char *sample[] = {"hello", "world", "cat", "cpu"};
    int sample_n = (int)(sizeof(sample) / sizeof(sample[0]));
    printf("Translate: ");
    for (int i = 0; i < sample_n; i++) {
      printf("%s ", sample[i]);
    }
    printf("\nResult:    ");
    for (int i = 0; i < sample_n; i++) {
      int key = -1;
      for (int k = 0; k < n; k++) {
        if (strcmp(sample[i], english[k]) == 0) {
          key = k;
          break;
        }
      }
      int val = -1;
      if (key != -1 && map_lookup(dict, key, &val)) {
        printf("%s ", french[val]);
      } else {
        printf("? ");
      }
    }
    printf("\n");
  } else {
    printf("Result: ");
    for (int i = 1; i < argc; i++) {
      int key = -1;
      for (int k = 0; k < n; k++) {
        if (strcmp(argv[i], english[k]) == 0) {
          key = k;
          break;
        }
      }
      int val = -1;
      if (key != -1 && map_lookup(dict, key, &val)) {
        printf("%s ", french[val]);
      } else {
        printf("? ");
      }
    }
    printf("\n");
  }

  map_free(dict);
}

static void demo_tree_sort(void) {
  int arr[] = {7, 2, 9, 1, 5, 8, 3, 6, 4};
  int n = (int)(sizeof(arr) / sizeof(arr[0]));

  printf("Before: ");
  for (int i = 0; i < n; i++) printf("%d ", arr[i]);
  printf("\n");

  tree_sort(arr, n);

  printf("After:  ");
  for (int i = 0; i < n; i++) printf("%d ", arr[i]);
  printf("\n");
}

int main(int argc, char **argv) {
#if defined(DEMO1)
  demo_stack_postfix(argc, argv);
#elif defined(DEMO2)
  demo_queue_round_robin();
#elif defined(DEMO3)
  demo_list_pool();
#elif defined(DEMO4)
  demo_map_translator(argc, argv);
#elif defined(DEMO5)
  demo_tree_sort();
#else
  (void)argc;
  (void)argv;
  printf("Build with -DDEMO1..DEMO5 to run a demo.\n");
#endif
  return 0;
}