#include <stdlib.h>
#include <stdio.h>
#include "userconst.h"

static void merge(struct list_node *head, unsigned int element);                       /* 每次輸入后進行整合 */
static void print_list(struct list_node *head);                                         /* 鏈表輸出 */
static struct list_node *find_node(struct list_node *begin_addr, unsigned int element, struct list_node *head);     /* 尋找目標節點 */
static struct list_node *compare(struct list_node *head, struct list_node *need_ptr);     /* 根據頻度進行排序 */
static void insert(struct list_node *new_node, struct list_node *orgin_node);            /* 節點的插入 */

struct list_node *init_list(struct list_node *head)
{
	unsigned int length = 0;
	unsigned int i = 0;

    struct list_node *current;
	struct list_node *temp_ptr;

	current = head;

	printf("請您輸入鏈表的長度\n");

	scanf("%u", &length);

	printf("\n");

	head->data = length;

	if(0 == length)
	{
		printf("鏈表為空\n");
		 
		exit(1);
	}

	printf("請您輸入鏈表中的元素\n");

    for(i = 0; i < length; i++)
	{
		temp_ptr = (struct list_node *)malloc(sizeof(struct list_node));
   
        scanf("%u", &(temp_ptr->data));

		temp_ptr->freq = 0;

		current->next = temp_ptr;
		temp_ptr->prior = current;

		temp_ptr->next = head;
		head->prior = temp_ptr;

		current = current->next;

/*
    	free(temp_ptr);
*/
	}

	printf("雙向鏈表建立成功\n");

	print_list(head);

	return head;
}

void output_list(struct list_node *head, unsigned int element)
{
	merge(head, element);

	print_list(head);
}





static void merge(struct list_node *head, unsigned int element)
{
	struct list_node *temp_ptr;
	temp_ptr = head;

	while(head != temp_ptr->next)
	{
		 temp_ptr = temp_ptr->next;             /* 從頭結點或者找到元素的結點后一個作為起始位 */
		 temp_ptr = find_node(temp_ptr, element, head);

		 if(NULL == temp_ptr)
		 {
			 return;
		 }

		 temp_ptr->freq = temp_ptr->freq + 1;
		 
         insert(temp_ptr, compare(head, temp_ptr));
	}
}


static void print_list(struct list_node *head)
{
	 unsigned int temp_len;
     struct list_node *temp_ptr;

	 temp_ptr = head;

	 temp_len = head->data;
	 
     if(0 != temp_len)
	 {
		 while(head != (temp_ptr->next))
         {
			 temp_ptr = temp_ptr->next;

			 printf("%u ", temp_ptr->data);
		 }

		 printf("\n頻數為\n");

		 temp_ptr = head;

		 while(head != (temp_ptr->next))
         {
			 temp_ptr = temp_ptr->next;

			 printf("%u ", temp_ptr->freq);
		 }

		 printf("\n");
	 }
}

static struct list_node *find_node(struct list_node *begin_addr, unsigned int element, struct list_node *head)
{
    struct list_node *temp_ptr;

	temp_ptr = begin_addr;

	while((element != (temp_ptr->data)) && (head != temp_ptr->next))   /* temp_ptr從頭結點后一個結點開始 */
	{
		temp_ptr = temp_ptr->next;
	}

	if((element != (temp_ptr->data) && head == temp_ptr->next))
	{
		temp_ptr = NULL;                                          /* 從頭到尾沒有要求的元素 */
	}

	return temp_ptr;                     /* 返回找到元素的結點地址 可以處理多個數字相同情況 */
}

static struct list_node *compare(struct list_node *head, struct list_node *need)
{
	struct list_node *ptr;
	ptr = head->next;

	while(need != ptr)
	{
		if(need->freq <= ptr->freq)         /* 比較頻度 */
		{
			ptr = ptr->next;
		}
		else
		{
			return ptr;
		}
	}

	return ptr;
}

static void insert(struct list_node *new_node, struct list_node *orgin_node)
{	
	if(new_node == orgin_node)
    {
		return;
	}

    new_node->prior->next = new_node->next;     /* 解決新結點的問題*/
    new_node->next->prior = new_node->prior;

    orgin_node->prior->next = new_node;
    new_node->next = orgin_node;

//	new_node->prior = orgin_node->prior->next;

	new_node->prior = orgin_node->prior;
//	orgin_node->prior = new_node;

	orgin_node->prior = new_node;
}