#include <stdlib.h>
#include <string.h>
#include "list.h"

List
*list_new(void)
{
  List *l = malloc(sizeof(List));

  if (l) {
    l->first = NULL;
    l->last = NULL;
  }

  return l;
}

static Node
*fill_node(char *item)
{
  char *buf = strdup(item);
  Node *new_node;

  if (!buf) {
    return NULL;
  }
  if (!(new_node = malloc(sizeof(Node)))) {
    free(buf);
    return NULL;
  }
  new_node->next = NULL;
  new_node->cont = buf;

  return new_node;
}

static void
free_node(Node *n)
{
  free(n->cont);
  free(n);
}

int
list_append(List *l, char *item)
{
  Node *new_node;

  if (!(new_node = fill_node(item))) {
    return -1;
  }
  if (!l->last) {
    l->last = l->first = new_node;
  } else {
    l->last->next = new_node;
    l->last = new_node;
  }

  return 0;
}

int
list_len(List *l)
{
  int count=0;
  Node *cur = l->first;

  while (cur) {
    count++;
    cur = cur->next;
  }

  return count;
}

void
list_free(List *l)
{
  Node *cur = l->first, *next;

  while (cur) {
    free(cur->cont);
    next = cur->next;
    free(cur);
    cur = next;
  }
  free(l);
}

static Node*
get_node_at(List *l, int index)
{
  Node *cur=l->first;

  for (; cur&&index; index--) {
    cur = cur->next;
  }

  return cur;
}

char*
list_get_at(List *l, int index)
{
  Node *n=get_node_at(l, index);

  if (n) {
    return n->cont;
  }

  return NULL;
}

int 
list_delete_at(List *l, int index)
{
  Node *to_del;

  if (index==0) {
    to_del = l->first;
    l->first = to_del->next;
    if (!l->first) {
      l->last = NULL;
    }
  } else {
    Node *prev=get_node_at(l, index-1);
    if (!prev) {
      return -1;
    }
    if (!(to_del = prev->next)) {
      return -1;
    }
    prev->next = to_del->next;
    if (!prev->next) {
      l->last = prev;
    }
  }
  free_node(to_del);

  return 0;
}

int
list_insert_before(List *l, char *item, int index)
{
  Node *new = fill_node(item);

  if (index>0) {
    Node *cur=get_node_at(l, index-1);
    if (cur) {
      new->next = cur->next;
      cur->next = new;
    } else {
      free_node(new);
      return -1;
    }
  } else if (index==0) {
    if (!l->first) {
      l->last = new;
    }
    new->next = l->first;
    l->first = new;
  } else {
    free_node(new);
    return -1;
  }

  return 0;
}

static Node*
find_and_remove_smallest(Node **to_sort_ptr)
{
  Node *smallest=*to_sort_ptr, **smallest_chaining=to_sort_ptr;
  Node *cur_node=*to_sort_ptr, **cur_chaining=to_sort_ptr;

  while (cur_node) {
    if (strcoll(cur_node->cont, smallest->cont)<0) {
      smallest = cur_node;
      smallest_chaining = cur_chaining;
    }
    cur_chaining = &(cur_node->next);
    cur_node = cur_node->next;
  }
  *smallest_chaining = smallest->next;
  return smallest;
}

void
list_sort(List *l)
{
  Node **cur_el_ptr = &(l->first);
  Node *smallest = NULL;

  while (*cur_el_ptr) {
    smallest = find_and_remove_smallest(cur_el_ptr);
    smallest->next = *cur_el_ptr;
    *cur_el_ptr = smallest;
    cur_el_ptr = &(smallest->next);
  }
  l->last = smallest;
}

static Node**
get_node_arr(List *l, int *arr_len)
{
  Node **node_arr, **arrEnt;
  Node *cur=l->first;

  *arr_len = list_len(l);
  if (!(node_arr=malloc((*arr_len+1)*sizeof(Node*)))) {
    return NULL;
  }
  for (arrEnt=node_arr; cur; cur=cur->next) {
    *arrEnt++ = cur;
  }
  return node_arr;
}

static int
node_compare(const void *a, const void *b)
{
  Node *node1=*(Node**)a, *node2=*(Node**)b;

  return strcoll(node1->cont, node2->cont);
}

int
list_quicksort(List *l)
{
  int arr_len, i;
  Node **node_arr = get_node_arr(l, &arr_len);
  Node *cur;

  if (!node_arr) {
    return -1;
  }
  qsort(node_arr, arr_len, sizeof(Node*), node_compare);

  cur = l->first = node_arr[0];
  for (i=1; i<arr_len; i++) {
    cur->next = node_arr[i];
    cur = cur->next;
  }
  node_arr[arr_len-1]->next = NULL;
  l->last = cur;
  free(node_arr);
  return 0;
}

Iterator*
list_iterator_new(List *l)
{
  Iterator *it=malloc(sizeof(Iterator));

  if (it) {
    it->list = l;
    it->current = l->first;
  }
  return it;
}

void
list_iterator_free(Iterator *i)
{
  free(i);
}

char*
list_iterator_next(Iterator *it)
{
  char *res=NULL;

  if (it->current) {
    res = it->current->cont;
    it->current = it->current->next;
  }

  return res;
}

List*
list_split(char *str, char *split_str)
{
  char *part_start = str, *part_end;
  List *new = list_new();

  if (!new) {
    return NULL;
  }
  part_end = strstr(part_start, split_str);
  while (part_end) {
    *part_end = 0;
    if (list_append(new, part_start)) {
      list_free(new);
      return NULL;
    }
    part_start = part_end+strlen(split_str);
    part_end = strstr(part_start, split_str);
  }
  list_append(new, part_start);
  return new;
}


static int
compute_summed_length(List *l)
{
  Node *cur = l->first;
  int len_sum = 0;

  while (cur) {
    len_sum += strlen(cur->cont);
    cur = cur->next;
  }
  return len_sum;
}

char*
list_join(List *l, char *joiner)
{
  int new_length = compute_summed_length(l)+strlen(joiner)*(list_len(l)-1);
  char *result = malloc((new_length+1)*sizeof(char));
  char *cur_dest = result, *cur_src;
  Node *cur;

  if (!result) {
    return NULL;
  }
  cur = l->first;
  while (cur->next) {
    for (cur_src=cur->cont; *cur_src;) {
      *cur_dest++ = *cur_src++;
    }
    for (cur_src=joiner; *cur_src;) {
      *cur_dest++ = *cur_src++;
    }
    cur = cur->next;
  }
  for (cur_src=cur->cont; *cur_src;) {
    *cur_dest++ = *cur_src++;
  }
  *cur_dest = 0;
  return result;
}