/**
 * @file tools.h
 * @date 2011/12/01 16:44:17
 * @version $Revision$ 
 * @brief 
 *  
 **/



#ifndef  _KNZEUS_TOOLS_H_
#define  _KNZEUS_TOOLS_H_

#include "stdlibinc.h"

void dumpList(int* al, int num, int no = 0)
{
    if (NULL == al || 1 > num) return ;
    printf("%d : ", no);
    for (int i=0; i<num; ++i) {
        printf("%d ", al[i]);
    }
    printf("\n");
    return ;
}

void dumpList(int* al, int num, char* des)
{
    if (NULL == al || 1 > num) return ;
    if (NULL != des) {
        printf("%s : ", des);
    }
    for (int i=0; i<num; ++i) {
        printf("%d ", al[i]);
    }
    printf("\n");
    return ;
}

template <typename T>
T min(T t1, T t2)
{
    return ( (t1 > t2) ? t2 : t1 );
}

template <typename T>
T max(T t1, T t2)
{
    return ( (t1 < t2) ? t2 : t1 );
}

bool isSorted(int* al, int num)
{
    if (NULL == al) return false;
    for (int i=0; i<num-1; ++i)
    {
        if (al[i]>al[i+1]) return false;
    }
    return true;
}

void buildRandomList(int* al, int num, unsigned seed = 0)
{
    if (NULL == al) return ;
    if (seed != 0) srand(seed);
    for (int i=0; i<num; ++i) {
        al[i] = rand() % 101;
    }
    return ;
}

void copyList(int* al, int* bl, int num)
{
    if (NULL == al || NULL == bl || 1 > num) {
        return ;
    }
    for (int i=0; i<num; ++i) {
        al[i] = bl[i];
    }
    return ;
}

void swap(int * const al, int i, int j)
{
    if (NULL == al) return ;
    al[i] ^= al[j];
    al[j] ^= al[i];
    al[i] ^= al[j];
    return ;
}

/**
 * @brief 对数组al[s, e-1]进行反转
 *
 * */
void reverse(int *al, int s, int e)
{
    if (NULL == al || s > e-1) return ;
    --e;
    while (s < e) {
        swap(al, s++, e--);
    }
    return ;
}

/**
 * @brief 对al[s, e-1]进行循环右移step位
 * */
void rotateRight(int * al, int s, int e, int step)
{
    if (NULL == al || s > e-1) return ;
    step %= e - s;
    if (step == 0) return ;
    reverse(al, s, e - step);
    reverse(al, e - step, e);
    reverse(al, s, e);
    return ;
}

void rotateLeft(int * al, int s, int e, int step)
{
    if (NULL == al || s > e-1) return ;
    step %= e - s;
    if (step == 0) return ;
    reverse(al, s, s + step);
    reverse(al, s + step, e);
    reverse(al, s, e);
    return ;
}

/**
 * @brief 在有序数组al[0, num-1]中查找值为sv所在的位置，并将下标通过idx返回。
 *            查找成功返回0，不存在返回1，idx设置为第一个大于sv的数的下标。
 *
 * */
int binarySearch(int * al, int num, int &idx, int sv)
{
    idx = -1;
    if (al == NULL || num < 1) return -1;
    int l = 0;
    int h = num - 1;
    while (l < h) {
        int mid = l + (h - l) / 2;
        if (al[mid] > sv) {
            h = mid - 1;
        } else if (al[mid] < sv){
            l = mid + 1;
        } else {
            idx = mid;
            return 0;
        }
    }
    return -1;
}

#endif  //__TOOLS_H_