List *quick_sort(List *list)
{
    int count = List_Node_count(list);
    if(count==1 || count==0)
    {
        return list;
    }
    List *lesser = List_create();
    List *greater = List_create();
    Node *pivot = list->first;
    Node *current = pivot->next;
    Node *to_push;
    while(current!=NULL)
    {
        to_push = current;
        current = current->next;
        to_push->previous = NULL;
        to_push->next = NULL;
        if(to_push->data<pivot->data)
        {
            List_push(lesser, to_push);
        }
        else
        {
            List_push(greater, to_push);
        }
    }
    pivot->next = NULL;
    pivot->previous = NULL;
    return concatenate(quick_sort(lesser), pivot, quick_sort(greater));
}

char *test_push_pop()
{
    List_push(list, test1);
    mu_assert(List_last(list) == test1, "Wrong last value");

    List_push(list, test2);
    mu_assert(List_last(list) == test2, "Wrong last value");

    List_push(list, test3);
    mu_assert(List_last(list) == test3, "Wrong last value");

    mu_assert(List_count(list) == 3, "Wrong count on push");

    char *val = List_pop(list);
    mu_assert(val == test3, "Wrong value on pop");

    val = List_pop(list);
    mu_assert(val == test2, "Wrong value on pop");

    val = List_pop(list);
    mu_assert(val == test1, "Wrong value on pop");

    mu_assert(List_count(list) == 0, "Wrong count after pop.");

    return NULL;
}

List *List_merge_sort(List *list, List_compare cmp)
{
	// 未初始化的List，视为不能排序
	if(list == NULL) return NULL;
	// 空List和只有一个节点的List视为已经排序
	if(List_count(list) < 2) return list;

	int i = 1;
	ListNode *cur = list->first;
	List *left = List_create();
	List *right= List_create();
	int middle = List_count(list) / 2;
	// 拆成两个List，分别排序
	for(i = 1; i < middle; i++)
	{
		List_push(left, cur->value);
		cur=cur->next;
	}
	for(i = 1; i <= List_count(list) - middle; i++)
	{
		List_push(right, cur->value);
		cur=cur->next;
	}

	List *sort_left = List_merge_sort(left, cmp);
	List *sort_right =	List_merge_sort(right, cmp);

	if(sort_left != left) List_destroy(left);
	if(sort_right != right) List_destroy(right);
	

	// merge
	return List_merge(sort_left, sort_right, cmp);

}

List *List_merge_sort(List *list, List_compare cmp){
	if(List_count(list)<=1){
		return list;
	}
	
	List *left=List_create();
	List *right=List_create();
	int middle=List_count(list)/2;
	
	LIST_FOREACH(list, first, next, cur){
		if(middle>0){
			List_push(left, cur->value);
		} else {
			List_push(right, cur->value);
		}
		
		middle--;
	}
	
	List *sort_left=List_merge_sort(left, cmp);
	List *sort_right=List_merge_sort(right, cmp);
	
	if(sort_left !=left) List_destroy(left);
	if(sort_right !=right)List_destroy(right);
	
	return List_merge(sort_left, sort_right, cmp);
}

List *List_merge(List *left, List *right, List_compare cmp) {
	List *result = List_create();
	void *val = NULL;

	while(List_count(left) != 0 && List_count(right) != 0) {
		if(cmp(List_first(left), List_first(right)) <= 0) {
			val = List_shift(left);
            List_push(result, val);
		} else {
			val = List_shift(right);
            List_push(result, val);
		}
	}

	while(List_count(left) != 0) {
		val = List_shift(left);
        List_push(result, val);
	}

	while(List_count(right) != 0) {
		val = List_shift(right);
		List_push(result, val);
	}

	return result;
}

void remove_mid(List *list) {
    List_push(list, 12);
    List_push(list, 7);
    List_push(list, 8);
    List_remove(list, List_index(list, 1));
    assert(List_size(list) == 2);
    assert(List_first(list)->data == 12);
    assert(List_last(list)->data == 8);
}

char *test_read()
{
    List_push(list, tv1);
    List_push(list, tv2);
    List_push(list, tv3);
    LIST_ITERATOR(list){
        printf("%s\n", current->value);
    }

    return NULL;
}

void str_push_pop(List *list) {
    SET_TYPE(list, string);
    List_push(list, "hello world");
    List_push(list, "bad boy");
    assert(strcmp(List_index(list, 0)->data, "hello world") == 0);
    assert(strcmp(List_index(list, 1)->data, "bad boy") == 0);
    assert(strcmp(List_first(list)->data, "hello world") == 0);
    assert(strcmp(List_last(list)->data, "bad boy") == 0);
    List_pop(list);
    List_pop(list);
}

char *test()
{
    List *list = List_create();
    List_push(list, 5);
    List_push(list, 4);
    List_push(list, 3);
    List_push(list, 2);
    List_push(list, 1);

    List_bubble_sort(list);

    return NULL;

}

void push_shift(List *list) {
    List_push(list, 12);
    List_push(list, 7);
    List_push(list, 2);
    assert(List_index(list, 0)->data == 12);
    assert(List_index(list, 1)->data == 7);
    assert(List_first(list)->data == 12);
    assert(List_last(list)->data == 2);
    List_shift(list);
    assert(List_first(list)->data == 7);
    List_shift(list);
    assert(List_first(list)->data == 2);
    List_shift(list);
    assert(List_first(list) == NULL);
}

char* test_copy() {
  src = List_create();
  dest = List_create();
  List_push(src, test1);
  List_push(src, test2);
  List_push(src, test3);

  List_copy(dest, src);

  mu_assert(List_count(dest) == 3, "Wrong copy - count.");
  mu_assert(List_first(dest) == test1, "Wrong copy - first.");
  mu_assert(List_last(dest) == test3, "Wrong copy - last.");

  return NULL;
}

__declspec(dllexport) void* curl_shim_multi_info_read(void* pvHandle,
    int* nMsgs)
{
    // cast return from GetProcAddress as a CPROC
    List_T lst = NULL;
    CPVPROC pcp = (CPVPROC)GetProcAddress(g_hModCurl,
        "curl_multi_info_read");
    void* pvItem;
    int i, nLocalMsgs, j = 0;
    unsigned int *pnReturn = NULL;
    unsigned int *pnItem;

    *nMsgs = 0;
    while ((pvItem = pcp(pvHandle, &nLocalMsgs)) != NULL)
        lst = List_push(lst, pvItem);

    *nMsgs = List_length(lst);
    if (*nMsgs == 0)
        return NULL;
    pnReturn = (unsigned int*)malloc(3 * (*nMsgs) * sizeof(unsigned int));
    for (i = 0; i < (*nMsgs); i++)
    {
        lst = List_pop(lst, (void**)&pnItem);
        pnReturn[j++] = pnItem[0];
        pnReturn[j++] = pnItem[1];
        pnReturn[j++] = pnItem[2];            
    }
    List_free(&lst);
    return pnReturn;
}

inline List *List_merge(List *left, List *right, List_val_compare cmp) {
    check((left != NULL) || (right != NULL), "Tried to merge NULL.");

    List *merged = List_create();
    void *val = NULL;

    while(List_count(left) > 0 || List_count(right) > 0) {
        if(List_count(left) > 0 && List_count(right) > 0) {
            if(cmp(List_first(left), List_first(right)) <= 0) {
                val = List_fpop(left);
            } else {
                val = List_fpop(right);
            }

            List_push(merged, val);
        } else if(List_count(left) > 0) {
            merged = List_join(merged, left);
            break;
        } else if(List_count(right) > 0) {
            merged = List_join(merged, right);
            break;
        }
    }

    return merged;

error:
    return NULL;
}

/* push lines to the line_stack, to be read next - they need to be pushed
   in reverse order, i.e. last pushed is next to be retrieved
   line may contain multiple lines separated by '\n', they are split and
   pushed back-to-forth so that first text is first to retrieve from getline() */
void SrcFile_ungetline( SrcFile *self, char *lines )
{
	char *next_line, *line;
	size_t len;

	/* search next line after first '\n' */
	next_line = search_next_line( lines );

	/* recurse to push this line at the end */
	if ( next_line )
		SrcFile_ungetline( self, next_line );

	/* now push this line, add a newline if missing */
	len = next_line ? next_line - lines : strlen( lines );

	if ( len > 0 && lines[ len - 1 ] == '\n' )
		len--;							/* ignore newline */

	line = m_malloc( len + 2 );			/* 2 bytes extra for '\n' and '\0' */
	strncpy( line, lines, len );
	line[ len     ] = '\n';
	line[ len + 1 ] = '\0';

	List_push( & self->line_stack, line );
}

int
main(int argc, char** argv)
{
	if (argc != 3)
		print_usage("Invalid parameter count");

	Server* server = NULL;

	if (strcmp(argv[1], "unix") == 0)
		server = (Server*)UnixServer_new("/tmp/echo.sock");
	else if (strcmp(argv[1], "tcp") == 0)
		server = (Server*)TCPServer_new("0.0.0.0", 6666);
	else
		print_usage("Invalid server type");

	int worker_count = atoi(argv[2]);

	int i;
	for (i = 0; i < worker_count; i++)
		List_push(server->workers, ConnectionWorker_new(EchoConnection_new, &connection_callbacks));

	server->callbacks = &server_callbacks;

	Server_start(server);         // blocks
}

static List *neighbours_list(World *world, Point *point, Point *destination, Hashmap *nodes)
{
  List *neighbours = List_create();
  int nx, ny;

  for(nx = point->x - 1; nx <= point->x + 1; nx++) {
    if(nx < 0 || nx >= world->width) continue;
    for(ny = point->y - 1; ny <= point->y + 1; ny++) {
      if(ny < 0 || ny >= world->height ||
	 (ny == point->y && nx == point->x) ||
	 (!World_can_enter(world, nx, ny, point->z) &&
	  !(nx == destination->x && ny == destination->y))) continue;

      Point *p  = Point_create(nx, ny, point->z);
      Node *node = Node_create(p, 0, 0, NULL);

      Node *old_node = Hashmap_get(nodes, node);
      if(old_node) {
	Node_destroy(node);
	node = old_node;
      } else {
	Hashmap_set(nodes, node, node);
      }

      List_push(neighbours, node);
    }
  }

  return neighbours;
}

List *split_access_get_all_split_sections(char *file_loc){
	assert(file_loc != NULL);
	FILE *file;
	char *chr = NULL;
	seq_region_t *reg = NULL;
	file = fopen(file_loc,"r");
	check(file != NULL,"Error opening split list file.");
	char line[250];
	int i=0;
	List *li = List_create();

	while ( fgets(line,sizeof(line),file) != NULL ){
		i++;
		chr = malloc(sizeof(char) * 250);
		check_mem(chr);
		int start_zero_based = 0;
		int stop = 0;
		int chk = sscanf(line,"%s\t%d\t%d",chr,&start_zero_based,&stop);
		check(chk==3,"Error parsing split file line number %d: %s.",i,line);
		reg = malloc(sizeof(struct seq_region_t));
		check_mem(reg);
		reg->beg = start_zero_based+1;
		reg->end = stop;
		reg->chr_name = chr;
		List_push(li,reg);
	}
	return li;
error:
	if(reg){
		if(reg->chr_name) free(reg->chr_name);
		free(reg);
	}
	if(chr) free(chr);
	return NULL;
}

int main(void)
{
    List *list = NULL;
    list = List_create();

    // Int Data
    int n1 = 1;
    int n2 = 2;
    int n3 = 3;

    List_push(list, &n1);
    List_push(list, &n2);
    List_push(list, &n3);
    List_print(list, Int_printer);

    List_destroy(list);
}

void List_join(List *left, List *right)
{
    check(left != NULL, "Destination list is NULL");
    check(right != NULL, "Source list is NULL");

    LIST_FOREACH(right, first, next, cur) {
         List_push(left, cur->value);
    }

char *test_copy()
{
  list = List_create();

  mu_assert(List_count(list) == 0, "Wrong count before copy.");
  List_push(list, test1);
  List_push(list, test2);
  List_push(list, test3);
  List_push(list, test4);

  mu_assert(List_count(list) == 4, "Wrong count after push.");

  List *copy = List_copy(list);
  mu_assert(copy != list, "Copy and list have same address.");
  mu_assert(List_count(copy) == 4, "Copy has wrong count.");

  return NULL;
}