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

	for(i = 1; i < List_count(list); i++)
	{	
		cur = list->first;
		for(j = 1; j < List_count(list); j++)
		{
			if(cmp((char *)cur->value, (char *)cur->next->value)>0)
			{
				// 交换节点的数据域
				Swap_value(cur, cur->next);
			}
			cur = cur->next;
		}

	}

	return 0;

}

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

int List_bubble_sort(List *list, List_compare cmp)
{
  // int sorted = 1;

  if(List_count(list) <= 1) {
    return 0; // already sorted
  }

   
  int count = List_count(list);

  do {
    int current = 0;
    int reducer = 0; 
    LIST_FOREACH_LIMIT(list, first, next, cur, count, reducer) {
      if(cur->next) {
        if(cmp(cur->value, cur->next->value) > 0) {
          ListNode_swap(cur, cur->next);
          reducer = current;
        }
      }
      current++;
    }
    count = reducer;
  } while(count != 0);
   
   return 0;
}

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

char *test_shift() {
  mu_assert(List_count(list) != 0, "Wrong count before shift");

  char *val = List_shift(list);
  mu_assert(val = test3, "Wrong value on shift");

  val = List_shift(list);
  mu_assert(val == test1, "Wrong value on shift");
  mu_assert(List_count(list) == 0, "Wrong count after shift");

  return NULL;
}

char *test_genotype_calculate_genotypes(){
	char *ref_base = "A";
	int cn = 2;
	List *genos = genotype_calculate_genotypes(cn,ref_base);
	mu_assert(genos != NULL, "Genotypes list was NULL");
	mu_assert(List_count(genos) == 7, "Wrong number of genotypes returned in cn 2 test.");
	cn = 4;
	List *sec_genos = genotype_calculate_genotypes(4,ref_base);
	mu_assert(sec_genos != NULL, "Genotypes list was NULL");
	mu_assert(List_count(sec_genos) == 13, "Wrong number of genotypes returned in cn 4 test.");
	genotype_clear_genotype_cache();
	return NULL;
}

char *test_join()
{
  mu_assert(List_count(list) == 4, "Wrong count before join.");

  List *b = List_create();
  List_push(b, test4);
  mu_assert(List_count(b) == 1, "List 'b' has wrong count.");

  List_join(list, b);
  mu_assert(List_count(list) == 5, "Wrong count after join.");

  return NULL;
}

// just convert to Darray
int List_bubble_sort(List *list, List_compare cmp)
{
    int i;
    int j;
    int sorted;
    void *tmp;
    Darray *array;
    ListNode *node;

    if (list == NULL) {
        return -1;
    }

    if (cmp == NULL) {
        return -1;
    }

    // already sorted
    if (list->count <= 1) {
        return 0;
    }

    array = List_to_darray(list);
    if (array == NULL) {
        return -1;
    }

    for (i = 1; i < List_count(list); i++) {
        sorted = 1;
        for (j = 1; j < List_count(list); j++) {
            if (cmp(array->contents[j-1], array->contents[j]) <= 0) {
                tmp = array->contents[j-1];
                array->contents[j-1] = array->contents[j];
                array->contents[j] = tmp;
                sorted = 0;
            }
        }

        if (sorted) {
            break;
        }
    }

    for (i = 0, node = list->first; i < List_count(list); i++, node = node->next) {
        node->value = array->contents[i];
    }

    Darray_destroy(array);

    return 0;
}

void Staff_manage()
{
	char dirname[] = "./Date/Staff.txt";
	FILE *fp;
	pList head;
	int n,count;
	fp = File_open(dirname);
	head = File_read(fp,sizeof(struct staff_t));
	count = List_count(head);
	while(1)
	{	 
		system("cls");
		printf("\n\n\n\t\t\t员工管理界面\n\n");
		printf("\t\t\t1、增加员工\n\n"); 
		printf("\t\t\t2、删除员工\n\n");
		printf("\t\t\t3、修改员工\n\n"); 
		printf("\t\t\t4、查询员工\n\n"); 
		printf("\t\t\t5、返回\n\n"); 
		printf("\t\t\t请输入要操作的功能：");
		n = glb_putString(NULL,'1','5',1,2);
		switch(n)
		{
		case 1:	
			List_print(head,staff_print);
			File_add(fp,head,sizeof(struct staff_t),staff_add);
			List_print(head,staff_print);		
			break;
		case 2:
			List_print(head,staff_print);
			File_remove(fp,head,sizeof(struct staff_t),staff_remove);
			head = File_read(fp,sizeof(struct staff_t));
			List_print(head,staff_print);			
			break;
		case 3:
			List_print(head,staff_print);
			File_updata(fp,head,sizeof(struct staff_t),staff_updata);
			head = File_read(fp,sizeof(struct staff_t));
			List_print(head,staff_print);		
			break;
		case 4:  
			staff_search(head);			
			break;
		case 5:
			break;
		}
		if (n == 5)
		{
			break;
		}
		else
		{
            printf("\n按<Esc>键返回...");
			while(getch() != 27)
			{}
		}
		
		
	}
	List_free(head);
}

int
List_bubble_sort(List *list, List_compare cmp)
{
	int n = List_count(list);
	check(n >= 0, "List contains no elements");
	debug("List contains %d elements", n);
	int sorted = 0;
	/* repeat until sorted */
	for ( ; n > 0 && !sorted ; n--) {
		sorted = 1;
		LIST_FOREACH(list, first, next, cur) {
			check(cur, "List contains a NULL Node.");
			ListNode *next = Node_next(cur);
			/* if this pair is out of order */
			if ( next && cmp(Node_value(cur), Node_value(next)) > 0) {
				debug("%s is greater than %s", (char *)Node_value(cur), (char *)Node_value(next));
				swap_nodes(cur, next);
				sorted = 0;
			} else if (! next) {
				debug("The list is over.");
			} else {
				debug("%s is less than %s", (char *)Node_value(cur), (char *)Node_value(next));
			}
		}
		debug("We have %d rounds to go, and list is%ssorted", n, sorted ? " " : " not ");
		debug("We will%sgo to the next cycle.", (n > 0 && !sorted) ? " " : " not ");
	}

int List_bubble_sort(List *list, List_compare cmp)
{
	assert(list != NULL && "list can't be NULL");
	assert(cmp != NULL && "cmp can't be NULL");

	int n = List_count(list);

	if(n <= 1) {
		return 0; // already sorted
	}

	do {
		int j = 0;
		int new_n = 0;

		LIST_FOREACH(list, first, next, cur) {
			if(j == n - 1) break;
		
			if(cmp(cur->value, cur->next->value) > 0) {
				ListNode_swap(cur, cur->next);

				new_n = j + 1;
			}

			j++;
		}

		n = new_n;

	} while(n != 0);

	return 0;
}

void unit_purge_and_target (unit_t * unit)
{
    if (List_count (unit->pids))
        unit_enter_stopterm (unit);
    else
        unit_enter_state (unit, unit->target);
}

static int private_link_archive( const void* buildParameters, const void* providerContext, const void* targetIDirectory )
{
    int status = 1;

    const BuildParameters* parameters = (BuildParameters*) buildParameters;
    const ProviderContext* context = (ProviderContext*) providerContext;
    const IDirectory*      target = (IDirectory*) targetIDirectory;

    const char* target_location = Path_getCondensed( Directory_getRealPath( target ) );

    //	Linux: ar rcs <LIBNAME> <OBJECTS>...
    //	Win32: lib /OUT:<LIBNAME> <OBJECTS>...

    char* name = CharString_between( context->package_name, "", "-" );
    if ( !name )
    {
        name = new_CharString( context->package_name );
    }
    {
        char* libname           = CharString_cat2( name, ".a" );
        char* full_lib_location = CharString_cat3( target_location, "/lib/", libname );
        char* obj_dir           = CharString_cat2( target_location, "/obj/" );

        if ( 0 < List_count( context->objectFiles ) )
        {
            Command* command;
            IList* arguments = new_List();
            IList* native_arguments;

            List_copyItem( arguments, context->archiver );
            List_copyItem( arguments, "rcs" );
            List_copyItem( arguments, full_lib_location );
            addFlags( arguments, obj_dir, context->objectFiles );


            native_arguments = Path_ConvertListToNative( arguments );
            command = new_Command( context->archiver, (const char**) native_arguments->items );
            Command_print( command, stderr );

//			if ( !BuildParameters_isNo( parameters ) && Command_run( command ) && Command_waitFor( command ) )
//			{
//				status &= Command_getResult( command );
//			} else {
//				fprintf( stderr, "failed: " );
//				Command_print( command, stderr );
//			}
            free_Command( command );
            free_List( native_arguments );
            free_List( arguments );
        }

        free_CharString( obj_dir );
        free_CharString( full_lib_location );
        free_CharString( libname );
    }
    free_CharString( name );

    return status;
}

rpc_svc_t * svc_list_to_rpc_svc_array (svc_list box)
{
    register unsigned s_index = 0;
    rpc_svc_t * newRpc_svclist;

    if (List_count (box) == 0)
        return 0;

    newRpc_svclist = malloc (List_count (box) * sizeof (rpc_svc_t));

    for (svc_list_iterator it = svc_list_begin (box); it != NULL;
         svc_list_iterator_next (&it))
    {
        newRpc_svclist[s_index++] = svc_to_rpc_svc (it->val);
    }

    return newRpc_svclist;
}

static void addFlags( IList* arguments, const char* flag, const IList* includeDirs )
{
    unsigned int i;
    unsigned int count = List_count( includeDirs );
    for ( i=0; i < count; i++ )
    {
        List_copyItem2( arguments, flag, includeDirs->items[i] );
    }
}

rpc_property_t * property_list_to_rpc_property_array (prop_list box)
{
    register unsigned p_index = 0;
    rpc_property_t * newRpc_plist;

    if (List_count (box) == 0)
        return 0;

    newRpc_plist = malloc (List_count (box) * sizeof (rpc_property_t));

    for (prop_list_iterator it = prop_list_begin (box); it != NULL;
         prop_list_iterator_next (&it))
    {
        newRpc_plist[p_index++] = property_to_rpc_property (it->val);
    }

    return newRpc_plist;
}

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