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));
}

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_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)
{
	assert(list != NULL && "list can't be NULL");
	assert(cmp != NULL && "cmp can't be NULL");

	if(List_count(list) <= SUB_LIST_MIN_SIZE) {
		int rc = List_bubble_sort(list, cmp);

		assert(rc == 0 && "Bubble sort failed.");

		return list;
	}

	List *left = List_create();
	List *right = List_create();

	int middle = List_count(list) / 2;

	List_split(list, left, middle, right, List_count(list) - middle);

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

	if(sort_left != left) List_clear_destroy(left);
	if(sort_right != right) List_clear_destroy(right);
	
	List *merged_list = List_merge(sort_left, sort_right, cmp);

	List_clear_destroy(sort_left);
	List_clear_destroy(sort_right);

	return merged_list;
}

Menu * Menu_create(SDL_Window * window, SDL_Rect * size,
		SDL_Color background_color) {
	Menu * menu = (Menu *) malloc(sizeof(Menu));

	if (menu != NULL) {
		menu->window = window;

		if (size) {
			menu->surface = SDL_CreateRGBSurface(0, size->w, size->h, 32, 0, 0,
					0, 0);
		} else {
			SDL_Surface * surface = SDL_GetWindowSurface(window);

			Uint32 rmask, gmask, bmask, amask;

			rmask = 0xff000000;
			gmask = 0x00ff0000;
			bmask = 0x0000ff00;
			amask = 0x000000ff;

			menu->surface = SDL_CreateRGBSurface(0, surface->w, surface->h, 32,
					rmask, gmask, bmask, amask);
		}

		if (menu->surface != NULL) {

			menu->rect = (SDL_Rect *) malloc(sizeof(SDL_Rect));

			if (size) {
				menu->rect->x = size->x;
				menu->rect->y = size->y;
			} else {
				menu->rect->x = 0;
				menu->rect->y = 0;
			}

			menu->rect->w = menu->surface->w;
			menu->rect->h = menu->surface->h;

			menu->background_color = background_color;

			menu->buttons = List_create();
			menu->inputs = List_create();
			menu->labels = List_create();
		} else {
			printf("Erro ao criar o menu: %s\n", SDL_GetError());
		}
	}

	return menu;
}

/**
 * Inserting "value" and "index" into the correct location in the 
 * sparse array "head"
 * 
 * Arguments: 
 * head      A pointer pointing to the first element of the linked list.
 * value     The "value" of the value
 * index     The "value" of the index
 *
 * Returns:
 * A sparse array
 *
 * This function inserts the node ["value", "index"] into the sparse
 * array "head", and ensures that the nodes remain in ascending order
 * by their "index".
 *
 * Before and after the call to this function, "head" must be in
 * ASCENDING order by the "index" of each node.
 */
Node * List_insert_ascend(Node * head, int value, int index)
{
	if(head == NULL){
		head = List_create(value, index);
		return head;
	}

	Node* p = head;
	while(p->next != NULL){
		p = p->next;
	}
	p->next = List_create(value, index);
	return head;
}

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;
}

char *test_genotype_hard_copy_genotype_t_list(){
	List *new_list = List_create();
	List *old = List_create();
	genotype_t *geno = genotype_init_genotype();
	int count = 10;
	char base = 'C';
	genotype_set_base_count(geno, base, count);
	mu_assert(geno->c_count==10,"Wrong number of C bases recorded");
	List_push(old,geno);
	genotype_hard_copy_genotype_t_list(new_list,old);
	mu_assert(List_count(new_list) == 1, "Wrong number of elements in list.");
	LIST_FOREACH(new_list, first, next, cur){
		//Only one element...
		mu_assert(((genotype_t *)cur->value)->c_count == 10, "Wrong c count in copied value.");
	}

int serial_find(int com, int timeout, char* ack1, char* ack2) {
	if (!recvlst) {
		recvlst = List_create();
	}
	int i;
	for (i = 0; i <= timeout * 10; i++) {
		if (!serial_read(com, __serial_buf2)) {
			delay(100);
			continue;
		}	
		console_write(__serial_buf2);

		char* x = strtok(__serial_buf2, "\n");
		while (x != 0) {
			if (ack1 && strstr(x, ack1) == x) {
				return 1;	 
			}
			if (ack2 && strstr(x, ack2) == x) {
				return 1;	 
			}
			x = strtok(0, "\n");
		}						
	}
//	console_write("ERROR/TIMEOUT\n");
	return 0;
}

/*
 * Match ranges
 */
static void init_ranges(Parser *parser)
{
    if (parser == NULL) {
        return;
    }

    if (parser->ranges == NULL) {
        parser->range_count = get_delimeted_group_count(
            parser,
            parser->symbols[SYMBOL_RANGE_BEG],
            parser->symbols[SYMBOL_RANGE_END]);

        if (parser->range_count > 0) {
            parser->ranges = malloc(parser->range_count * sizeof(List *));
            if (parser->ranges != NULL) {
                unsigned int i;
                for (i = 0; i < parser->range_count; ++i) {
                    parser->ranges[i] = List_create();
                }

                get_delimited_tokens(parser,
                                     parser->symbols[SYMBOL_RANGE_BEG],
                                     parser->symbols[SYMBOL_RANGE_END],
                                     parser->ranges);
            }
        }
    }
}

List * List_copy(List * list, void * (*copy)(void *))
{
    List * newList;
    void * data, * copyData;
    ListIterator * iterator;

    if(list == NULL)
        return NULL;

    newList = List_create();
    iterator = ListIterator_create(list);

    data = ListIterator_seekToFirst(iterator);

    while(data != NULL)
    {
        copyData = copy(data);
        if(copyData != NULL)
        {
            List_addBack(newList, copyData);
        }
        
        data = ListIterator_nextItem(iterator);
    }

    ListIterator_destroy(iterator);

    return newList;
}

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;
}

static void clear_data(Parser *parser)
{
    if (parser != NULL) {
        List_destroy(parser->token_list, (Destructor) Token_destroy);

        if (parser->groups != NULL) {
            unsigned int i;
            for (i = 0; i < parser->group_count; ++i) {
                List_destroy(parser->groups[i], (Destructor) Token_destroy);
            }
            free(parser->groups);
            parser->groups = NULL;
        }

        if (parser->ranges != NULL) {
            unsigned int i;
            for (i = 0; i < parser->range_count; ++i) {
                List_destroy(parser->ranges[i], (Destructor) Token_destroy);
            }
            free(parser->ranges);
            parser->ranges = NULL;
        }

        parser->token_list = List_create();

        parser->group_count = 0;
        parser->range_count = 0;
    }
}

static List * List_split( List *words , int pos){

	List *second;
	assert( pos <= words->count);
	ListNode *middle = words->first; 

	int position = pos;
		
	while( pos != 0){
		middle = middle->next;
		assert(middle != NULL);
		pos--;
	}

	second =List_create();
	second->count = words->count - position;
	second->first = middle;
	second->last = words->last;
	
	words->count = position;
	words->last = middle->prev;
	words->last->next = NULL;
	middle->prev = NULL;
	
	return second;
}

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;
}

AnimatedSprite* AnimatedSprite_create(Sprite* sprite) {
	AnimatedSprite* this = malloc(sizeof(AnimatedSprite));
	this->sprite = sprite;
	this->animations = List_create();
	AnimationProgress_init(&this->progress, this, NULL);
	return this;
}

struct fd_state *
alloc_fd_state(struct event_base *base, evutil_socket_t fd)
{
    struct fd_state *state = malloc(sizeof(struct fd_state));
    if (!state)
        return NULL;
    state->read_event = event_new(base, fd, EV_READ|EV_PERSIST, do_read, state);
    if (!state->read_event) {
        free(state);
        return NULL;
    }

    state->write_event = event_new(base, fd, EV_WRITE|EV_PERSIST, do_write, state);
    if (!state->write_event) {
        event_free(state->read_event);
        free(state);
        return NULL;
    }

    state->rtmp = rtmp_create();
    state->buffer = RingBuffer_create(BUFFER_SIZE);
    state->outputs = List_create();

    assert(state->write_event);
    return state;
}

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;
}

void
cerebrod_speaker_data_initialize(void)
{
#if !WITH_CEREBROD_NO_THREADS
    Pthread_mutex_lock(&speaker_data_init_lock);
#endif /* !WITH_CEREBROD_NO_THREADS */
    if (speaker_data_init)
        goto out;

#if !WITH_CEREBROD_NO_THREADS
    /*
     * Must lock in this initialization routine, b/c the update thread
     * in a metric module may call the update state function.
     */
    Pthread_mutex_lock(&metric_list_lock);
#endif /* !WITH_CEREBROD_NO_THREADS */

    metric_list = List_create((ListDelF)_destroy_speaker_metric_info);

    if (_setup_metric_modules() < 0)
        CEREBRO_EXIT(("_setup_metric_modules"));

#if !WITH_CEREBROD_NO_THREADS
    Pthread_mutex_unlock(&metric_list_lock);
#endif /* !WITH_CEREBROD_NO_THREADS */

    speaker_data_init++;
out:
#if !WITH_CEREBROD_NO_THREADS
    Pthread_mutex_unlock(&speaker_data_init_lock);
#endif /* !WITH_CEREBROD_NO_THREADS */
    ;                             /* in case !WITH_CEREBRO_NO_THREADS */
}

char* test_split() {
  List* list_test = List_create();
  List_push(list_test, test1);
  List_push(list_test, test2);
  List_push(list_test, test3);
  List_push(list_test, test4);
  List_push(list_test, test5);
  List_push(list_test, test6);

  ListNode* split1 = List_find(list_test, test3);
  ListNode* split2 = List_find(list_test, test5);

  mu_assert(split1->value == test3, "Ridi");
  mu_assert(split2->value == test5, "Ridi");

  List** splits = List_split(list_test, 2, split1, split2);
  mu_assert(splits[0]->first->value == list_test->first->value, "Ridi");
  mu_assert(splits[0]->first->next->value == list_test->first->next->value, "Ridi");
  mu_assert(splits[0]->last->value == list_test->first->next->next->value, "Ridi");

  mu_assert(splits[1]->first->value == list_test->first->next->next->next->value, "Ridi");
  mu_assert(splits[1]->last->value == list_test->first->next->next->next->next->value, "Ridi");

  mu_assert(splits[2]->first->value == list_test->last->value, "Ridi");

  return NULL;
}