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

typedef struct Item_ {
  int id;
  struct Item_ *next;
} Item;

typedef struct {
  Item *item;
} TMenu;


Item *newItem_(int const id) {
  Item *item = malloc(sizeof(Item));
  item->id = id;
  item->next = NULL;
  return item;
}

Item **endOfList_(Item **const begin) {
  Item **item = begin;
  for (; *item; item = &(*item)->next);
  return item;
}

Item **findItem_(Item **const begin, int const id) {
  Item **item = begin;
  for (; *item && (*item)->id != id; item = &(*item)->next);
  return item;
}

void spliceItem_(Item **const item, int const id) {
  Item *next = *item;
  *item = newItem_(id);
  (*item)->next = next;
}


void appendItem(TMenu *const menu, int const id) {
  Item **item = endOfList_(&menu->item);
  *item = newItem_(id);
}

void prependItem(TMenu *const menu, int const id) {
  spliceItem_(&menu->item, id);
}

Item *findItem(TMenu *const menu, int const id) {
  return *findItem_(&menu->item, id);
}

void insertAfter(TMenu *const menu, int const id, int const newId) {
  Item *item = *findItem_(&menu->item, id);
  if (!item) {
    return;
  }

  spliceItem_(&item->next, newId);
}

void insertBefore(TMenu *const menu, int const id, int const newId) {
  Item **item = findItem_(&menu->item, id);
  if (!*item) {
    return;
  }

  spliceItem_(item, newId);
}

void removeItem(TMenu *const menu, int const id) {
  Item **item = findItem_(&menu->item, id);
  if (!*item) {
    return;
  }

  Item *item_ = *item;
  (*item) = (*item)->next;
  free(item_);
}


void destroyList(TMenu *const menu) {
  for (Item *item = menu->item; item;) {
    Item *item_ = item;
    item = item->next;
    free(item_);
  }
}

void printList(TMenu const *const menu) {
  for (Item *item = menu->item; item; item = item->next) {
    printf("%i ", item->id);
  }
  printf("\n");
}


int main() {
  TMenu menu = {NULL};

  appendItem(&menu, 1);
  appendItem(&menu, 2);
  printList(&menu);           // 1, 2
  prependItem(&menu, 0);
  printList(&menu);           // 0, 1, 2
  insertAfter(&menu, 0, 4);
  printList(&menu);           // 0, 4, 1, 2
  insertBefore(&menu, 0, 5);
  printList(&menu);           // 5, 0, 4, 1, 2
  insertBefore(&menu, 4, 6);
  printList(&menu);           // 5, 0, 6, 4, 1, 2
  removeItem(&menu, 4);
  printList(&menu);           // 5, 0, 6, 1, 2
  removeItem(&menu, 2);
  printList(&menu);           // 5, 0, 6, 1

  printf("\nfound %i\n", findItem(&menu, 1)->id);

  destroyList(&menu);
}