/*============================================================================
#     FileName: seqlist.c
#       Author: Huoty
#        Email: sudohuoty@163.com
#     HomePage: http://konghy.blog.163.com/
#      Version: 0.0.1
#   CreateDate: 2014-12-19 15:02:18
#      History: 
#  Description: 顺序存储序列实现
============================================================================*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "seqlist.h"


/**
 * @brief 初始化顺序存储序列结构
 *
 * @param seql -- 顺序存储序列结构指针
 *
 * @returns 成功返回0;失败返回-1
 */
int seqlist_init(SeqList *seql)
{
    seql->max = 10;
    seql->len = 0;
    seql->slp = (DataType *)malloc(sizeof(DataType) * seql->max);

    if (!seql->slp)
    {
        fprintf(stderr, "In function seqlist_init(): malloc fail.");
        return -1;
    }

    return 0;
}

/**
 * @brief 销毁顺序序列
 *
 * @param seql -- 顺序存储序列结构指针
 */
void seqlist_destroy(SeqList *seql)
{
    int i;

    if (seql->slp)
    {
        for(i = 0; i < seql->len; i++)
        {
            if (seql->slp[i].key)
            {
                free(seql->slp[i].key);
                seql->slp[i].key = NULL;
            }

            if (seql->slp[i].val)
            {
                free(seql->slp[i].val);
                seql->slp[i].val = NULL;
            }
        }

        free(seql->slp);
        seql->slp = NULL;
    }

    seql->max = 0;
    seql->len = 0;
}

/**
 * @brief 向顺序序列中添加数据
 *
 * @param seql -- 顺序存储序列结构指针
 * @param key -- 键
 * @param val -- 键所对应的值
 *
 * @returns 
 */
int seqlist_add_data(SeqList *seql, char *key, char *val)
{
    if (!key || !val)
    {
        return -1;
    }

    if (seql->len >= seql->max)
    {
        seql->max = (seql->len/10 + 1) * 10; //向上取10的倍数
        seql->slp = (DataType *)realloc(seql->slp, sizeof(DataType) * seql->max);
        if (seql->slp == NULL)
        {
            fprintf(stderr, "In function seqlist_add_data(): realloc fail.");
            return -1;
        }
    }

    seql->slp[seql->len].key = strdup(key);
    seql->slp[seql->len].val = strdup(val);
    seql->len++;

    return 0;
}

/**
 * @brief 合并两侧已排完序的序列
 *
 * @param seql -- 顺序存储序列结构指针
 * @param start -- 序列起始坐标
 * @param mid -- 序列中间坐标
 * @param end -- 序列结尾坐标
 */
static void merge(SeqList *seql, int start, int mid, int end)
{
    int i, j, k;
    DataType b[end + 1];

    for (i = start; i <= end; i++)
        b[i] = seql->slp[i];  // init b[] = a[]

    i = start;  
    j = mid + 1;  
    k = start;

    while (i <= mid && j <= end)
    {
        if (strcmp(b[i].key, b[j].key) < 0)
            seql->slp[k++] = b[i++];
        else                
            seql->slp[k++] = b[j++];
    }

    while (i <= mid)
        seql->slp[k++] = b[i++];
    while (j <= end)          
        seql->slp[k++] = b[j++];
}

/**
 * @brief 归并排序算法
 *
 * @param seql -- 顺序存储序列结构指针
 * @param start -- 序列起始坐标
 * @param end -- 序列结尾坐标
 */
static void sort(SeqList *seql, int start, int end)
{
    int mid;  // middle position

    /* 序列只有一个元素时不必再排序 */
    if (start >= end)
        return;

    /* 计算中间坐标 */
    mid = (start + end) / 2;

    /* 首先将左边的序列排序 */
    sort(seql, start, mid);

    /* 然后将右边的序列排序 */
    sort(seql, mid+1, end);

    /* 最后合并左右两侧都排完序的序列 */
    merge(seql, start, mid, end);
}

/**
 * @brief 整理序列中的数据，使其有序
 *
 * @param seql -- 顺序存储序列结构指针
 */
void seqlist_data_sort(SeqList *seql)
{
    sort(seql, 0, seql->len - 1);
}

/**
 * @brief 查找key所对应的值，折半查找实现
 *
 * @param seql -- 顺序存储序列结构指针
 * @param key -- 要查找的键
 *
 * @returns 成功返回key所对应的值，失败返回NULL
 */
char *seqlist_data_search(SeqList *seql, const char *key)
{
    int l, mid, r;  // left, middle, right

    l = 0;
    r = seql->len - 1;

    while (l <= r)
    {
        mid = (l+r) / 2;
        if (strcmp(key, seql->slp[mid].key) < 0)  
            r = mid - 1;  // 如果小于中间的值则在左边找
        else if (strcmp(key, seql->slp[mid].key) > 0)  
            l = mid + 1;  // 如果大于中间的值则在右边找
        else
            return seql->slp[mid].val;  // 找到返回对应的值
    }

    return NULL;  //没找到返回NULL
}

#ifdef DEBUG
int main(void)
{
    int i;
    SeqList seql;

    /* 初始化顺序序列 */
    seqlist_init(&seql);

    /* 添加数据 */
    seqlist_add_data(&seql, "d", "dxc");
    seqlist_add_data(&seql, "c", "cxc");
    seqlist_add_data(&seql, "b", "bxc");
    seqlist_add_data(&seql, "k", "khy");
    seqlist_add_data(&seql, "a", "axc");
    seqlist_add_data(&seql, "y", "axc");
    seqlist_add_data(&seql, "g", "axc");
    seqlist_add_data(&seql, "h", "axc");
    seqlist_add_data(&seql, "5", "axc");
    seqlist_add_data(&seql, "0", "axc");
    seqlist_add_data(&seql, "m", "axc");
    seqlist_add_data(&seql, "9", "axc");

    /* 排序整理，以供查找 */
    seqlist_data_sort(&seql);
    
    /* 打印序列中所有数据 */
    printf("SeqList length: %d\n", seql.len);
    printf("SeqList maximum: %d\n", seql.max);
    for (i = 0; i < seql.len; i++)
    {
        printf("<%d> %s: %s\n", i+1, seql.slp[i].key, seql.slp[i].val);
    }
    
    printf("search k: %s\n", seqlist_data_search(&seql, "k"));
    
    seqlist_destroy(&seql);

    return 0;
}
#endif