/*
 * Create a telephone book. The book will have the telephone number
 * and the person’s first and last name in a data structure. Write
 * the code to achieve all of these:
 *  1. We need to create a new telephone book.
 *   [dev] use link list array. For simple phone number is just an unsigned int
 *  2. Add a few people to the telephone book.
 *   [dev] API to add new one
 *  3. Do a lookup by first or else last name.
 *   [dev] API to look up with input first or last or both name
 *  4. Do a lookup by telephone number.
 *   [dev] similar above
 *
 * Hint: Optimize for memory and access time
 * [dev] can optimize with binary search
 */

/* Include */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

/* Define */
#define NAME_MAX_CHAR       32
#define PHONE_NUM_INVALID   0xFFFFFFFF

struct person_info {
  char first[NAME_MAX_CHAR];
  char last[NAME_MAX_CHAR];
  unsigned int phone;

  struct person_info *next;
  struct person_info *prev;
};


struct person_info *person_start = NULL;
struct person_info *person_end = NULL;
unsigned int person_cnt = 0;

/* API */
/* Get current count of telephone book */
unsigned int get_phone_book_cnt() 
{
  return person_cnt;
}

/* Add new person to telephone book */
int add_phone_book(char *first, char *last, unsigned int phone)
{
  struct person_info *p;

  p = malloc(sizeof(struct person_info));
  memset(p, 0, sizeof(struct person_info));
  memcpy(p->first, first, strlen(first));
  memcpy(p->last, last, strlen(last));
  p->phone = phone;

  /* Update list */
  if (person_end) { /* List existed */
    person_end->next = p;
    p->next = NULL;
    p->prev = person_end;
    person_end = p;
  } else {  /* First times add, list was null */
    person_start = p;
    person_end = p;
    p->prev = NULL;
    p->next = NULL;
  }
   
  person_cnt++;
  return 0;
}

/* Search from telephone book */
/* TODO: optimize search with binary search */
int search_phone_book_by_name(char *first, char *last)
{
  struct person_info *p;
  int i, found = 0;

  p = person_start;
  for (i = 0; i < get_phone_book_cnt() ; i++) {
    /*
     * If user input first name, find match first name. Then check if:
     *  - If user input last name --> check matching more with last name
     *  - If user not input last name --> print result
     */
    if (strlen(first) && strncmp(p->first, first, strlen(first)) == 0) {
      if (strlen(last)) {
        if (strncmp(p->last, last, strlen(last)) == 0) {
          printf("\nFound %d. %s %s %d\n", i + 1, p->first, p->last, p->phone);
          found++;
        }
      } else {
        printf("\nFound %d. %s %s %d\n", i + 1, p->first, p->last, p->phone);
        found++;
      }

    /*
     * If user not input first name, then just check last name matching.
     */
    } else if (strlen(first) == 0) {
      if (strlen(last) && strncmp(p->last, last, strlen(last)) == 0) {
          printf("\nFound %d. %s %s %d\n", i + 1, p->first, p->last, p->phone);
          found++;
      }
    }

    /* Pointer to next person */
    p = p->next;
  }

  if (found == 0) {
    printf("\nCannot found this name in phone book !!\n");
    return -1;
  }

  return 0;
}

/* TODO: optimize search with binary search */
int search_phone_book_by_phone(unsigned int phone)
{
  struct person_info *p;
  int i, found = 0;

  p = person_start;
  for (i = 0; i < get_phone_book_cnt() ; i++) {
    if (phone == p->phone) {
      printf("\nFound %d. %s %s %d\n", i + 1, p->first, p->last, p->phone);
      found++;
    }

    /* Pointer to next person */
    p = p->next;
  }

  if (found == 0) {
    printf("\nCannot found this number in phone book !!\n");
    return -1;
  }

  return 0;
}

/* Main interract with user */
int main()
{
  struct person_info *p;
  char first[NAME_MAX_CHAR] = { 0 }, last[NAME_MAX_CHAR] = { 0 };
  unsigned int phone;
  int sel, i, cnt;

  /* User select option */
  while (1) {
    printf("\nSelection:\n");
    printf("1. Dump phone book\n");
    printf("2. Auto add pre-defined list to phone book\n");
    printf("3. Add input new person to phone book\n");
    printf("4. Search from phone book by name\n");
    printf("5. Search from phone book by phone\n");
    printf("\nSelect: ");

    /* User input */
    scanf("%d", &sel);

    /* Process */
    switch (sel) {
    case 1:
      cnt = get_phone_book_cnt();
      if (cnt == 0) {
        printf("\nPhone book is empty !!\n");
      } else {
        printf("\nPhone book (%d): \n", cnt);
        p = person_start;
        for (i = 0; i < cnt; i++) {
          printf("%d. %s %s %d\n", i + 1, p->first, p->last, p->phone);
          /* Pointer to next person */
          p = p->next;
        }
      }
      break;
    case 2:
      add_phone_book("Darth", "Vader", 669237);
      add_phone_book("Han", "Solo", 987543);
      add_phone_book("Luke", "Skywalker", 244865);
      add_phone_book("Boba", "Fett", 126324);
      add_phone_book("Storm", "Trooper", 245088);
      add_phone_book("Rey", "Skywalker", 873127);
      break;
    case 3:
      memset(first, 0, NAME_MAX_CHAR);
      memset(last, 0, NAME_MAX_CHAR);

      printf("\nFirst name: "); scanf("%s", first);
      printf("Last name: "); scanf("%s", last);
      printf("Phone (6 digits): "); scanf("%d", &phone);
      add_phone_book(first, last, phone);
      break;
    case 4:
      memset(first, 0, NAME_MAX_CHAR);
      memset(last, 0, NAME_MAX_CHAR);

      /* FIXME: scanf cannot input empty, so must input '-'' if not care */
      /* TODO: change to fgets */
      printf("\nInput info to search (put '-'' if don't care): \n");
      printf("First name: "); scanf("%s", first);
      printf("Last name: "); scanf("%s", last);

      /* Clear if user input space (not care) */
      if (strlen(first) && strncmp(&first[0], "-", 1) == 0)
        memset(first, 0, NAME_MAX_CHAR);
      if (strlen(last) && strncmp(&last[0], "-", 1) == 0)
        memset(last, 0, NAME_MAX_CHAR);

      search_phone_book_by_name(first, last);
      break;
    case 5:
      printf("\nInput info to search: \n");
      printf("Phone (6 digits): "); scanf("%d", &phone);
      search_phone_book_by_phone(phone);
      break;
    default:
      printf("No selection %d !!\n", sel);
      break;
    }
  }

  return 0;
}